💻 computer science

When Equality Fails as a Rewrite Principle: Provenance and Definedness for Measurement-Bearing Expressions

This paper presents a unified formal semantics for measurement-bearing expressions that tracks provenance and definedness to establish sound one-way rewriting and interchangeability judgments, demonstrating that ordinary algebraic equality fails as a rewrite principle due to issues like observation reuse and division-induced domain differences, with all results formalized in Lean 4.

Original authors: David B. Hulak, Arthur F. Ramos, Ruy J. G. B. de Queiroz

Published 2026-04-10

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: David B. Hulak, Arthur F. Ramos, Ruy J. G. B. de Queiroz

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a chef trying to perfect a recipe. You have a set of rules for simplifying your instructions: "If you add salt and then subtract the same amount of salt, you can just write '0 salt'." In a perfect, mathematical world, this rule always works.

But in the real world of measurements (like cooking with a slightly shaky hand, or measuring ingredients with a ruler that has a tiny bit of wiggle room), this simple rule can lead to disaster.

This paper is about why mathematical equality is a dangerous guide when you are dealing with real-world data, and how to build a better set of rules that doesn't break your experiment.

Here is the breakdown using simple analogies:

1. The Two Traps of Measurement

The authors say there are two main reasons why you can't just swap one measurement formula for another, even if they look the same on paper.

Trap #1: The "Copy-Paste" vs. "Two Different Cups" Problem (Provenance)

Imagine you have a cup of water.

Scenario A: You pour the water into a bowl, then pour it back into the cup. If you calculate "Water in bowl minus Water in cup," you get zero. This is safe because it's the same water (same "token").
Scenario B: You have two identical cups of water. You pour Cup 1 into a bowl, then pour Cup 2 into the bowl. If you calculate "Water from Cup 1 minus Water from Cup 2," you cannot assume the result is zero. Even if both cups say "250ml," one might actually be 250.1ml and the other 249.9ml.

The Lesson: In math, $x - x = 0$ . In measurements, if $x$ and $x$ come from two different observations (even if they look identical), $x - x$ is not necessarily zero. You need to track the "ID card" (provenance) of every measurement to know if they are the same object or just look-alikes.

Trap #2: The "Divide by Zero" Trap (Definedness)

Imagine a rule that says: "Divide any number by itself, and you get 1."

If you have a number like 5, $5/5 = 1$ . Safe.
But what if your measurement could potentially be zero? If you write $x/x$ , and $x$ happens to be 0, the math breaks (division by zero).
The number 1 is safe everywhere. But the formula $x/x$ is dangerous if $x$ can be zero.

The Lesson: You can safely replace a dangerous formula ( $x/x$ ) with a safe one ($1$) to fix a problem. But you cannot replace a safe formula ($1$) with a dangerous one ( $x/x$ ) just because they look equal. The "safety zone" (where the math works) has changed.

2. The New "Safety Rules"

The authors propose a new way to think about these formulas using two concepts:

The "Token" (The ID Card): Every measurement gets a unique ID. If you see the same ID twice, the computer knows it's the exact same hidden value. If you see two different IDs, even if they look the same, the computer treats them as potentially different.
The "Admissible Domain" (The Safety Zone): Before you simplify a formula, you must check: "Does this new formula work in every situation where the old one worked?"
- If the old formula worked when the temperature was 0°C, and the new formula crashes at 0°C, you cannot make the swap.
- If the old formula crashed at 0°C, and the new one works there, you can make the swap (you are making it safer).

3. Why This Matters (The "Chef's Dilemma")

The paper uses a specific example: Measuring a signal, subtracting a background noise, and dividing by a reference.

If you don't track the "ID cards," you might accidentally think you can cancel out noise that was actually measured twice separately.
If you don't check the "Safety Zone," you might simplify a formula that works fine for most temperatures into one that explodes if the temperature hits zero.

4. The "Strictness" Discovery

The authors found something surprising: Simplification is often a one-way street.

You can simplify a complex, dangerous formula into a simple, safe one.
But you often cannot go back. Once you remove the "danger" (the singularity), you lose the information about where the danger used to be. It's like taking a warning label off a box; the box is still there, but you've forgotten it might explode.

5. The "Proof" (The Computer Check)

The authors didn't just write this down; they built a massive digital proof system (using a tool called Lean 4) that checks every single step of their logic. They proved that:

If you ignore the "ID cards" (provenance), you get wrong answers.
If you ignore the "Safety Zones" (definedness), you get wrong answers.
You need both to be safe.

The Big Takeaway

In the world of science and engineering, mathematical equality is not enough. Two formulas might look identical, but if one relies on a specific measurement being reused, or if one crashes under specific conditions, they are not interchangeable.

To write safe software for scientists, we need a system that asks two questions before simplifying anything:

"Are these the same physical object, or just look-alikes?" (Provenance)
"Does this new formula work in all the places the old one worked?" (Definedness)

If you can't answer "Yes" to both, you must leave the formula alone.

1. Problem Statement

The paper addresses a fundamental flaw in applying standard algebraic equality to measurement-bearing expressions (expressions involving observed data with uncertainty). In scientific computing and symbolic manipulation, replacing one expression with another (rewriting) is often assumed safe if they are algebraically equal. However, the authors identify two distinct failure modes where algebraic equality fails as a sound rewrite principle:

Provenance Failure (Token Identity): Standard algebraic simplification ignores the origin of data.
- Example: Simplifying $x - x$ to $0$ is sound only if $x$ represents a single measurement token reused twice. If $x_1$ and $x_2$ are two separate measurements with identical intervals, $x_1 - x_2$ is not necessarily $0$.
- Issue: Classical interval arithmetic and dimensional analysis are "provenance-blind," treating all occurrences of a variable as independent, leading to incorrect simplifications or overestimation of uncertainty.
Definedness Failure (Singularities): Algebraic forms that agree on their common domain may differ in where they are defined.
- Example: The expression $x/x$ evaluates to $1$ wherever $x \neq 0$ , but is undefined at $x=0$ . The constant $1$ is defined everywhere. Replacing $1$ with $x/x$ introduces a singularity (making the expression undefined in cases where it was previously defined), which is unsafe.
- Issue: Standard equality checks often ignore domain restrictions, allowing "unsafe" simplifications that introduce singularities or fail to recognize that two functions are "the same" only on a restricted subset.

The core problem is that neither provenance tracking nor definedness checking alone is sufficient for sound rewrite classification in scientific contexts.

2. Methodology

The authors develop a unified semantic framework formalized in Lean 4 (without sorry, ensuring all proofs are complete). The methodology involves three layers of semantics:

A. Token-Sensitive Enclosure Semantics (Provenance Layer)

Syntax: Expressions consist of arithmetic operations and measured leaves defined as Meas(t, I, d), where $t$ is an opaque token (identifying the observation event), $I$ is a rational interval, and $d$ is a dimension.
Evaluation: A token environment $\sigma$ assigns an exact rational value to each token. An environment is "token-consistent" if the assigned value falls within the leaf's interval.
Warranted Enclosure: The set of all possible values an expression can take across all token-consistent environments. Crucially, if a token $t$ appears twice, $\sigma(t)$ is the same value in both instances, capturing the dependency.

B. Admissible-Domain Refinement (Definedness Layer)

Well-Definedness: An expression is well-defined at $\sigma$ if no division by zero occurs.
Admissible Domain ($AdmDom$): The set of token-consistent environments where the expression is well-defined.
Defined Enclosure: The set of values produced only within the admissible domain. This layer filters out values generated by singularities (e.g., $x/0$ ).

C. Rewrite Judgments

The paper defines three levels of rewrite judgments:

Enclosure-based: $e \rightsquigarrow e'$ if $Encl(e') \subseteq Encl(e)$ . (Focuses on value tightening).
Domain-aware: $e \rightsquigarrow_d e'$ $e ⇝_{d} e^{'}$ if:
- The target is admissible everywhere the source is ( $AdmDom(e) \subseteq AdmDom(e')$ ).
- The target's values on the source's domain lie within the source's defined enclosure.
Support-relative: Relativizes admissibility to a specific set of environments $S$ , allowing local theorems (e.g., "safe if the interval is positive") to be integrated into the global theory.

3. Key Contributions

Unified Semantics: A single framework that simultaneously tracks token identity (provenance) and division singularities (definedness), showing they are orthogonal but jointly necessary.
Formal Rewrite Judgments:
- One-way Rewriting: Identifies cases where simplification is safe (removing a singularity) but the reverse is not.
- Non-Transitivity: Proves that domain-safe rewriting is not transitive. A chain of sound local simplifications can lead to an unsound global result, requiring step-by-step verification.
- Domain Non-Collapse: Demonstrates cases where two expressions agree on their common domain but are incomparable regarding admissibility (e.g., $x/x$ vs. $(x-1)/(x-1)$ ), blocking replacement in either direction.
Classification Families:
- Provenance-driven: Distinguishes between "same-token cancellation" (sound) and "distinct-token cancellation" (unsound).
- Definedness-driven: Distinguishes between "positive-interval self-division" (interchangeable with 1) and "zero-crossing self-division" (one-way only).
Insufficiency Theorem: Proves that erasing token identity (forgetting provenance) collapses distinctions that definedness alone cannot recover, and vice versa. Both axes are strictly necessary.
Mechanization: All 143 theorems and 45 definitions are formalized in Lean 4 (approx. 2,700 lines), providing a machine-checked foundation for measurement semantics.

4. Key Results

Reduction Theorems: On the "universally admissible" fragment (where denominators never hit zero), the domain-aware layer collapses to the enclosure-based layer. This proves the new theory is a conservative extension of existing provenance theories.
Recovery Theorems: The framework internalizes standard scientific simplifications (cancellation, background subtraction, positive self-division) as contextual theorems within the support-relative layer.
Strictness Results:
- Removable Singularities: Simplifying $x/x \to 1$ is safe only if $x$ is guaranteed non-zero. If $x$ can be zero, the rewrite is strictly one-way ( $x/x \rightsquigarrow_d 1$ but not vice versa).
- Incomparable Singularities: Expressions like $x/x$ and $(x-1)/(x-1)$ are "equal" where both are defined, but neither can replace the other because their admissible domains exclude different points.
Non-Transitivity of Rewriting: The paper provides a mechanized witness showing that $A \rightsquigarrow_d B$ and $B \rightsquigarrow_d C$ does not imply $A \rightsquigarrow_d C$ . This challenges the assumption that local optimizations automatically compose.

5. Significance

Theoretical Impact: The paper challenges the assumption that algebraic equality is sufficient for symbolic optimization in scientific computing. It establishes that provenance (data origin) and definedness (domain constraints) are independent semantic dimensions that must be tracked simultaneously.
Practical Application: It provides a rigorous basis for building certified symbolic simplifiers for scientific workflows (e.g., signal processing, background subtraction in physics). It warns that automated tools relying solely on algebraic rules or interval arithmetic without token tracking will produce unsound results.
Formal Verification: By formalizing these concepts in Lean 4, the authors provide a "semantic certification" that prevents subtle errors in domain reasoning (such as assuming transitivity of safe rewrites) that are easy to miss in informal proofs.
Future Directions: The framework suggests that future rewrite engines for measurement-bearing data must incorporate token-awareness and admissibility checks at every step, rather than treating them as post-hoc checks.

In summary, the paper argues that equality is too weak for measurement rewriting. A sound rewrite system must be token-sensitive to handle data dependencies and domain-aware to handle singularities, with the two properties interacting in complex, non-transitive ways.