diag_two_counter_machine_is_symmetric
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
- 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
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.
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.
intro q q' w₁ w₂ hThe 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.
uses
Finset.mem_singleton,Prod.mk.injEq,TwoCounterInstr.update.injEqsimp only [Finset.mem_singleton, Prod.mk.injEq, TwoCounterInstr.update.injEq] at h ⊢
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.
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
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.
/-- 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