AFTD Auto-Formalizing Theoretical Domains

diag_two_counter_machine_is_symmetric

theoremverified

The 2-counter machine over Bool with a single update (1, 1) from false to true is symmetric.

Statement

theorem diag_two_counter_machine_is_symmetric :
    two_counter_machine_is_symmetric (⟨{(false, TwoCounterInstr.update 1 1, true)}⟩ : TwoCounterMachine Bool)
Source
step towards op_360_single_counter_update_strictly_less_expressive
Verified
20 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • two_counter_machine_is_symmetricA 2-counter machine M with state type Q is symmetric if for every update transition from q to q' with integer weights (w₁, w₂), the…
  • TwoCounterMachineA structure TwoCounterMachine parameterized by a type of control states Q : Type*, consisting of a single field transitions which is a…
  • 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

To show that the machine is symmetric, we assume an update transition $(q, \text{update } w_1\ w_2, q')$ belongs to its transition set and show that the swapped transition $(q, \text{update } w_2\ w_1, q')$ also belongs to it. Since the machine contains only the single transition $(\text{false}, \text{update } 1\ 1, \text{true})$, any valid transition has $q = \text{false}$, $q' = \text{true}$, and $w_1 = w_2 = 1$. Swapping the two counter increments leaves the transition identical to the original, which immediately satisfies the symmetry requirement.

  1. Fix arbitrary states $q, q'$ and counter increments $w_1, w_2$, assuming $(q, \text{update } w_1\ w_2, q')$ is a transition of the machine, and reducing the goal to showing that $(q, \text{update } w_2\ w_1, q')$ is also a transition.

    By definition of symmetry (`two_counter_machine_is_symmetric`), a machine is symmetric if for every update transition, swapping the two counter updates produces another valid transition. We introduce the states, the weight increments, and the assumption that the transition is in the machine's transition set.

    line 4

      intro q q' w₁ w₂ h
  2. The assumption $h$ becomes $q = \text{false} \land w_1 = 1 \land w_2 = 1 \land q' = \text{true}$, and the goal becomes $q = \text{false} \land w_2 = 1 \land w_1 = 1 \land q' = \text{true}$.

    The machine's transition set is the singleton $\{(\text{false}, \text{update } 1\ 1, \text{true})\}$. Using `Finset.mem_singleton`, membership in this set is rewritten as equality to that single element. Then `Prod.mk.injEq` and `TwoCounterInstr.update.injEq` decompose equality of the transition triples and the update instructions into component-wise equalities.

    line 5

    uses Finset.mem_singleton, Prod.mk.injEq, TwoCounterInstr.update.injEq

      simp only [Finset.mem_singleton, Prod.mk.injEq, TwoCounterInstr.update.injEq] at h ⊢
  3. The goal is proved.

    Both the hypothesis and the goal require $q = \text{false}$, $q' = \text{true}$, and both counter updates to be $1$. Since conjunction is commutative, the goal follows directly from the hypothesis by propositional tautology.

    line 6

      tauto
Finset.mem_singleton
An element belongs to a singleton set if and only if it equals the single element of that set.
Prod.mk.injEq
Two pairs are equal if and only if their first components are equal and their second components are equal.
TwoCounterInstr.update.injEq
Two counter update instructions are equal if and only if their respective counter increments are equal.

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

/-- The 2-counter machine over Bool with a single update (1, 1) from false to true is symmetric. -/theorem diag_two_counter_machine_is_symmetric :    two_counter_machine_is_symmetric (⟨{(false, TwoCounterInstr.update 1 1, true)}⟩ : TwoCounterMachine Bool) := by  intro q q' w₁ w₂ h  simp only [Finset.mem_singleton, Prod.mk.injEq, TwoCounterInstr.update.injEq] at h ⊢  tauto
See it in the graphDiscuss this resultChallenge it