diag_two_counter_machine_reach_rel_iff
The reachability relation of the diagonal machine between false and true consists exactly of pairs (u, v) with v = (u.1 + 1, u.2 + 1).
Statement
theorem diag_two_counter_machine_reach_rel_iff (u v : ℕ × ℕ) :
(u, v) ∈ two_counter_machine_reach_rel (⟨{(false, TwoCounterInstr.update 1 1, true)}⟩ : TwoCounterMachine Bool) false true ↔
v.1 = u.1 + 1 ∧ v.2 = u.2 + 1- Source
- step towards op_360_single_counter_update_strictly_less_expressive
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- two_counter_machine_reach_relFor a 2-counter machine M with state type Q and states q, q' in Q, the reachability relation two_counter_machine_reach_rel M q q' is the…
- 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…
- 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 determine the reachability relation of the diagonal machine between states false and true, the proof first characterizes single-step transitions, showing that a valid step must start in state false, end in state true, and increment both counters by 1. For reachability, any path from (false, u) to (true, v) cannot have length zero because false ≠ true. The first step necessarily reaches an intermediate configuration in state true with both counters incremented by 1, from which no further steps can occur because no transitions originate from state true. Conversely, the increment condition allows a single step that directly establishes reachability.
The single-step transition relation reduces to checking whether one of the machine's three possible instruction forms is satisfied.
We unfold the definition of a step for the diagonal machine M. A step is defined as a three-way disjunction corresponding to an update instruction or a zero-test on either counter, using transitions from M's transition set. We split the equivalence between the step relation and the component-wise specification into forward and backward directions.
dsimp [two_counter_machine_step, diag_two_counter_machine_reach_rel_iff_M] constructor
Any valid single step must transition from state false to state true and increment both counters by 1.
For the forward direction of the step characterization, we case-split on the type of instruction used. The two zero-test cases are immediately discarded because the machine's singleton transition set contains only an update instruction, not a zero-test. For the update instruction, membership in the singleton transition set requires the source state to be false, the target state to be true, and both counter updates to be 1, which implies both counters increase by 1.
uses
Finset.mem_singleton,Prod.mk.injEq,TwoCounterInstr.update.injEq· rintro (⟨w₁, w₂, h, h1, h2⟩ | ⟨h, -⟩ | ⟨h, -⟩) · simp only [Finset.mem_singleton, Prod.mk.injEq, TwoCounterInstr.update.injEq] at h obtain ⟨h1_st, ⟨rfl, rfl⟩, h2_st⟩ := h refine ⟨h1_st, h2_st, ?_, ?_⟩ · exact_mod_cast h1.symm · exact_mod_cast h2.symm · simp only [Finset.mem_singleton, Prod.mk.injEq] at h cases h.2.1 · simp only [Finset.mem_singleton, Prod.mk.injEq] at h cases h.2.1Conversely, any configuration in state false can step to a configuration in state true if both counters increase by 1.
Assuming the initial state is false, the final state is true, and both counters increase by 1, the machine's update transition with increments (1, 1) is enabled and directly witnesses the step relation.
· rintro ⟨h1, h2, h3, h4⟩ left refine ⟨1, 1, ?_, ?_, ?_⟩ · simp [h1, h2] · exact_mod_cast h3.symm · exact_mod_cast h4.symmThe reachability statement is rephrased as the reflexive-transitive closure of the step relation connecting (false, u) to (true, v).
By definition of the reachability relation for two-counter machines, configuration (false, u) reaches (true, v) if and only if they are related by the reflexive-transitive closure of the single-step relation. We split the equivalence into forward and backward directions.
change Relation.ReflTransGen (two_counter_machine_step diag_two_counter_machine_reach_rel_iff_M) (false, u) (true, v) ↔ v.1 = u.1 + 1 ∧ v.2 = u.2 + 1 constructor
A path of length zero between (false, u) and (true, v) is impossible.
Decomposing the reflexive-transitive reachability relation into either zero steps or at least one step, a zero-step path would require (false, u) = (true, v). This implies false = true, which is a contradiction.
uses
Relation.ReflTransGen.cases_head_iff,Prod.ext_iff.mp· intro h rw [Relation.ReflTransGen.cases_head_iff] at h rcases h with h_refl | ⟨c, hstep, hrest⟩ · exfalso have : false = true := (Prod.ext_iff.mp h_refl).1 cases this
The first step transitions to an intermediate configuration c in state true with incremented counters, which equals (true, v) if no further steps are taken.
Applying the step characterization lemma to the first step (false, u) → c, configuration c must have state true and counters (u.1 + 1, u.2 + 1). Decomposing the remaining path from c to (true, v), the zero-step case gives c = (true, v), which immediately establishes v.1 = u.1 + 1 and v.2 = u.2 + 1.
uses
diag_two_counter_machine_reach_rel_iff_step,Relation.ReflTransGen.cases_head_iff· rw [diag_two_counter_machine_reach_rel_iff_step] at hstep rcases hstep with ⟨-, hc_state, hu1, hu2⟩ rw [Relation.ReflTransGen.cases_head_iff] at hrest rcases hrest with rfl | ⟨c', hstep', -⟩ · rw [← hu1, ← hu2] exact ⟨rfl, rfl⟩
No further steps can be taken from configuration c.
If the remaining path from c took another step c → c', the step characterization lemma would require c to be in state false. However, c is already known to be in state true from the previous step, producing the contradiction true = false.
uses
diag_two_counter_machine_reach_rel_iff_step· exfalso rw [diag_two_counter_machine_reach_rel_iff_step] at hstep' rw [hc_state] at hstep' cases hstep'.1
Conversely, if v = (u.1 + 1, u.2 + 1), then (true, v) is reachable from (false, u) in a single step.
Assuming v.1 = u.1 + 1 and v.2 = u.2 + 1, the step characterization lemma ensures that (false, u) steps directly to (true, v). A single transition immediately satisfies the reflexive-transitive reachability relation.
uses
Relation.ReflTransGen.single,diag_two_counter_machine_reach_rel_iff_step· rintro ⟨h1, h2⟩ apply Relation.ReflTransGen.single rw [diag_two_counter_machine_reach_rel_iff_step] exact ⟨rfl, rfl, h1, h2⟩
Finset.mem_singleton- An element belongs to a singleton set {a} if and only if it equals a.
Prod.mk.injEq- Two pairs (a, b) and (c, d) are equal if and only if a = c and b = d.
TwoCounterInstr.update.injEq- Two counter update instructions are equal if and only if their respective counter increments are equal.
Relation.ReflTransGen.cases_head_iff- A reflexive-transitive reachability relation a →* b holds if and only if either a = b (0 steps) or there is an intermediate state c such that a → c and c →* b (at least 1 step).
Prod.ext_iff.mp- If two pairs are equal, then their first components are equal and their second components are equal.
diag_two_counter_machine_reach_rel_iff_step- A single-step transition between configurations c₁ and c₂ is valid in the diagonal machine if and only if c₁ is in state false, c₂ is in state true, and both counters increase by 1.
Relation.ReflTransGen.single- A single step a → b implies reflexive-transitive reachability a →* b.
- The formalization first proves an auxiliary lemma `diag_two_counter_machine_reach_rel_iff_step` characterizing single-step transitions before establishing the reflexive-transitive reachability relation in `diag_two_counter_machine_reach_rel_iff`.
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.
abbrev diag_two_counter_machine_reach_rel_iff_M : TwoCounterMachine Bool := ⟨{(false, TwoCounterInstr.update 1 1, true)}⟩theorem diag_two_counter_machine_reach_rel_iff_step (c₁ c₂ : Bool × ℕ × ℕ) : two_counter_machine_step diag_two_counter_machine_reach_rel_iff_M c₁ c₂ ↔ c₁.1 = false ∧ c₂.1 = true ∧ c₂.2.1 = c₁.2.1 + 1 ∧ c₂.2.2 = c₁.2.2 + 1 := by dsimp [two_counter_machine_step, diag_two_counter_machine_reach_rel_iff_M] constructor · rintro (⟨w₁, w₂, h, h1, h2⟩ | ⟨h, -⟩ | ⟨h, -⟩) · simp only [Finset.mem_singleton, Prod.mk.injEq, TwoCounterInstr.update.injEq] at h obtain ⟨h1_st, ⟨rfl, rfl⟩, h2_st⟩ := h refine ⟨h1_st, h2_st, ?_, ?_⟩ · exact_mod_cast h1.symm · exact_mod_cast h2.symm · simp only [Finset.mem_singleton, Prod.mk.injEq] at h cases h.2.1 · simp only [Finset.mem_singleton, Prod.mk.injEq] at h cases h.2.1 · rintro ⟨h1, h2, h3, h4⟩ left refine ⟨1, 1, ?_, ?_, ?_⟩ · simp [h1, h2] · exact_mod_cast h3.symm · exact_mod_cast h4.symm/-- The reachability relation of the diagonal machine between false and true consists exactly of pairs (u, v) with v = (u.1 + 1, u.2 + 1). -/theorem diag_two_counter_machine_reach_rel_iff (u v : ℕ × ℕ) : (u, v) ∈ two_counter_machine_reach_rel (⟨{(false, TwoCounterInstr.update 1 1, true)}⟩ : TwoCounterMachine Bool) false true ↔ v.1 = u.1 + 1 ∧ v.2 = u.2 + 1 := by change Relation.ReflTransGen (two_counter_machine_step diag_two_counter_machine_reach_rel_iff_M) (false, u) (true, v) ↔ v.1 = u.1 + 1 ∧ v.2 = u.2 + 1 constructor · intro h rw [Relation.ReflTransGen.cases_head_iff] at h rcases h with h_refl | ⟨c, hstep, hrest⟩ · exfalso have : false = true := (Prod.ext_iff.mp h_refl).1 cases this · rw [diag_two_counter_machine_reach_rel_iff_step] at hstep rcases hstep with ⟨-, hc_state, hu1, hu2⟩ rw [Relation.ReflTransGen.cases_head_iff] at hrest rcases hrest with rfl | ⟨c', hstep', -⟩ · rw [← hu1, ← hu2] exact ⟨rfl, rfl⟩ · exfalso rw [diag_two_counter_machine_reach_rel_iff_step] at hstep' rw [hc_state] at hstep' cases hstep'.1 · rintro ⟨h1, h2⟩ apply Relation.ReflTransGen.single rw [diag_two_counter_machine_reach_rel_iff_step] exact ⟨rfl, rfl, h1, h2⟩