single_counter_step_preserves_one_coord
In any single step of a 2-counter machine with single-counter updates, at least one counter remains unchanged.
Statement
theorem single_counter_step_preserves_one_coord {Q : Type*} (M : TwoCounterMachine Q) (hsc : two_counter_machine_is_single_counter_update M) (c₁ c₂ : Q × ℕ × ℕ) (hstep : two_counter_machine_step M c₁ c₂) : c₂.2.1 = c₁.2.1 ∨ c₂.2.2 = c₁.2.2
- Source
- step towards op_360_single_counter_update_strictly_less_expressive
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- two_counter_machine_is_single_counter_updateA 2-counter machine M with state type Q has single-counter updates if for every update transition from q to q' with displacements (w₁,…
- two_counter_machine_stepThe one-step transition relation of a 2-counter machine M between configurations c₁ and c₂ in Q × (ℕ × ℕ): either an update transition…
- TwoCounterMachineA structure TwoCounterMachine parameterized by a type of control states Q : Type*, consisting of a single field transitions which is a…
- IsSingleCounterUpdateA pair of integer displacements (w₁, w₂) is a single-counter update if at least one coordinate is zero, that is, w₁ = 0 or w₂ = 0.
- TwoCounterInstrAn instruction of a 2-counter machine is either an update by a vector of integers (w₁, w₂), or a zero-test on the first counter or the…
- Used by 2
- op_360_single_counter_update_strictly_less_expressiveThere exists a symmetric 2-counter machine M over a finite state type Q and states q, q' in Q whose reachability relation…
- single_counter_symmetric_cannot_match_diag_reachNo finite-state symmetric 2-counter machine with single-counter updates can have reachability relation equal to that of the diagonal…
The proof, explained
The proof proceeds by case analysis on the transition taken by the machine. For a zero-test transition on either counter, neither counter changes, so the first counter is trivially preserved. For an update transition, the single-counter update hypothesis ensures that at least one coordinate has an increment of zero, leaving that counter's value unchanged.
It suffices to show the claim in each of the three possible transition types: a counter update, a zero-test on the first counter, or a zero-test on the second counter.
We perform a case split on the step hypothesis (`hstep`) according to the definition of `two_counter_machine_step`. In the first case, the machine executes an update transition modifying the counters by integer increments $w_1$ and $w_2$. In the second and third cases, the machine executes a zero-test on the first or second counter, respectively, leaving both counters unchanged.
rcases hstep with (⟨w₁, w₂, htr, h₁, h₂⟩ | ⟨_, _, h⟩ | ⟨_, _, h⟩)
For an update transition, at least one counter remains unchanged ($c_2.2.1 = c_1.2.1 \lor c_2.2.2 = c_1.2.2$).
Applying the single-counter update hypothesis (`hsc`) to the transition yields that at least one of the updates is zero ($w_1 = 0$ or $w_2 = 0$). In the first subcase ($w_1 = 0$), choosing the left disjunct (`left`) and substituting $w_1 = 0$ simplifies the update equation $\uparrow c_1.2.1 + 0 = \uparrow c_2.2.1$ via `add_zero` to $\uparrow c_1.2.1 = \uparrow c_2.2.1$. Injectivity of the integer cast (`Nat.cast_injective`) then gives $c_2.2.1 = c_1.2.1$. The second subcase ($w_2 = 0$) is symmetric: choosing the right disjunct (`right`) and simplifying with `add_zero` and `Nat.cast_injective` gives $c_2.2.2 = c_1.2.2$.
uses
add_zero,Nat.cast_injective· have hsc' := hsc c₁.1 c₂.1 w₁ w₂ htr rcases hsc' with hw₁ | hw₂ · left subst hw₁ simp only [add_zero] at h₁ exact Nat.cast_injective h₁.symm · right subst hw₂ simp only [add_zero] at h₂ exact Nat.cast_injective h₂.symm
For a zero-test on the first counter, the first counter remains unchanged ($c_2.2.1 = c_1.2.1$).
A zero-test transition on the first counter requires that both counter values are preserved ($c_2.2 = c_1.2$). Choosing the first disjunct (`left`), we apply `congr_arg Prod.fst` to project this equality of pairs onto the first coordinate, yielding $c_2.2.1 = c_1.2.1$.
uses
congr_arg,Prod.fst· left exact congr_arg Prod.fst h
For a zero-test on the second counter, the first counter remains unchanged ($c_2.2.1 = c_1.2.1$).
Likewise, a zero-test transition on the second counter leaves both counter values unchanged ($c_2.2 = c_1.2$). Choosing the first disjunct (`left`) and projecting onto the first coordinate via `congr_arg Prod.fst` gives $c_2.2.1 = c_1.2.1$.
uses
congr_arg,Prod.fst· left exact congr_arg Prod.fst h
add_zero- Adding zero to any element leaves it unchanged: $a + 0 = a$.
Nat.cast_injective- The canonical injection from the natural numbers into a characteristic-zero ring (such as $\mathbb{Z}$) is injective: if $\uparrow m = \uparrow n$, then $m = n$.
congr_arg- Applying a function to both sides of an equality preserves the equality: if $a_1 = a_2$, then $f(a_1) = f(a_2)$.
Prod.fst- The projection function extracting the first component of an ordered pair: $(x, y) \mapsto x$.
- Counter values are natural numbers while transition updates are integers, requiring the injectivity of the integer cast (`Nat.cast_injective`) to recover equality in `ℕ` after setting an update increment to zero.
- For zero-test transitions, the definition states that both counters are unchanged (`c₂.2 = c₁.2`), so either counter is preserved; the proof arbitrarily chooses the first counter.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- In any single step of a 2-counter machine with single-counter updates, at least one counter remains unchanged. -/theorem single_counter_step_preserves_one_coord {Q : Type*} (M : TwoCounterMachine Q) (hsc : two_counter_machine_is_single_counter_update M) (c₁ c₂ : Q × ℕ × ℕ) (hstep : two_counter_machine_step M c₁ c₂) : c₂.2.1 = c₁.2.1 ∨ c₂.2.2 = c₁.2.2 := by rcases hstep with (⟨w₁, w₂, htr, h₁, h₂⟩ | ⟨_, _, h⟩ | ⟨_, _, h⟩) · have hsc' := hsc c₁.1 c₂.1 w₁ w₂ htr rcases hsc' with hw₁ | hw₂ · left subst hw₁ simp only [add_zero] at h₁ exact Nat.cast_injective h₁.symm · right subst hw₂ simp only [add_zero] at h₂ exact Nat.cast_injective h₂.symm · left exact congr_arg Prod.fst h · left exact congr_arg Prod.fst h