AFTD Auto-Formalizing Theoretical Domains

single_counter_step_preserves_one_coord

theoremverified

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

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.

  1. 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.

    line 6

      rcases hstep with (⟨w₁, w₂, htr, h₁, h₂⟩ | ⟨_, _, h⟩ | ⟨_, _, h⟩)
  2. 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$.

    lines 7–16

    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
  3. 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$.

    lines 17–18

    uses congr_arg, Prod.fst

      · left
        exact congr_arg Prod.fst h
  4. 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$.

    lines 19–20

    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$.

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

/-- 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
See it in the graphDiscuss this resultChallenge it