reversible_transition_reachability_equivalence
For any finite type V and any injective transition function f : V → V, the reachability relation (fun s t => ∃ m : ℕ, f^[m] s = t) is an equivalence relation on V, and for all s, t : V, if t is reachable from s, then there exists a return exponent k < Fintype.card V such that f^[k] t = s.
Statement
theorem reversible_transition_reachability_equivalence {V : Type*} [Fintype V] (f : V → V) (hf : Function.Injective f) : Equivalence (fun s t : V => ∃ m : ℕ, f^[m] s = t) ∧ ∀ s t : V, (∃ m : ℕ, f^[m] s = t) → ∃ k < Fintype.card V, f^[k] t = s
- Related work
- Lange, McKenzie, Tapp 1997, Reversible Space Equals Deterministic Space; Sipser, Section 8.2
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
For every finite type V and every injective function f : V → V: 1. The reachability relation on V defined by (s, t) ↦ (∃ m : ℕ, f^[m] s = t) is an equivalence relation (reflexive, symmetric, and transitive); and 2. For all s, t : V, if there exists m : ℕ such that f^[m] s = t, then there exists a natural number k < Fintype.card V such that f^[k] t = s.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
Because f is an injective self-map on a finite set V, every element belongs to a periodic cycle whose minimal period p is at most |V|. Given a forward path f^[m] s = t, the return exponent k = (p - m % p) % p satisfies k < p ≤ |V| and satisfies p ∣ (k + m), which ensures f^[k] t = f^[k + m] s = s. This bounded return property immediately yields symmetry, while reflexivity (exponent 0) and transitivity (exponent addition) complete the proof that reachability is an equivalence relation.
The return condition reduces to showing f^[k + m] s = s for an exponent k < |V|.
Suppose t is reachable from s with f^[m] s = t. Let p be the minimal period of s under f. Since V is finite and f is injective, s is periodic, so its minimal period p is strictly positive and at most |V|. We define the candidate return exponent k = (p - m % p) % p, which satisfies k < p ≤ |V|. Rewriting t as f^[m] s and using the composition law for iteration, the goal f^[k] t = s reduces to f^[k + m] s = s.
uses
Injective.mem_periodicPts,minimalPeriod_pos_of_mem_periodicPts,Nat.mod_lt,lt_of_lt_of_le,minimalPeriod_le_card,iterate_add_applyopen Function in have h_ret : ∀ s t : V, (∃ m : ℕ, f^[m] s = t) → ∃ k < Fintype.card V, f^[k] t = s := by intro s t ⟨m, hm⟩ set p := minimalPeriod f s have hmem : s ∈ periodicPts f := Injective.mem_periodicPts hf s have hp : 0 < p := minimalPeriod_pos_of_mem_periodicPts hmem set k := (p - m % p) % p have hk_lt_p : k < p := Nat.mod_lt _ hp have hk_lt_card : k < Fintype.card V := lt_of_lt_of_le hk_lt_p minimalPeriod_le_card refine ⟨k, hk_lt_card, ?_⟩ rw [← hm, ← iterate_add_apply]
The minimal period p divides k + m.
Expanding the definition of k, we case split on whether m % p is zero or positive. If m % p = 0, then k = 0 and p divides m, so p divides k + m. If m % p > 0, then p - m % p < p, so the outer modulo is identity and k = p - m % p. By the division algorithm m = p * (m / p) + m % p, the sum k + m simplifies to p * (m / p) + p, which is a sum of multiples of p and therefore divisible by p.
uses
Nat.eq_zero_or_pos,Nat.dvd_of_mod_eq_zero,Nat.mod_lt,Nat.mod_eq_of_lt,Nat.div_add_mod,dvd_add,dvd_mul_right,dvd_rflhave hdvd : p ∣ k + m := by dsimp [k] rcases Nat.eq_zero_or_pos (m % p) with h0 | hpos · rw [h0] simp [Nat.dvd_of_mod_eq_zero h0] · have hlt : m % p < p := Nat.mod_lt m hp have h1 : p - m % p < p := by omega rw [Nat.mod_eq_of_lt h1] have : p - m % p + m = p * (m / p) + p := by have hm' : m = p * (m / p) + m % p := (Nat.div_add_mod m p).symm omega rw [this] exact dvd_add (dvd_mul_right p (m / p)) dvd_rfl
f^[k] t = s, establishing the existence of a return path bounded by |V|.
Because the minimal period p divides k + m, the state s is periodic with period k + m, which gives f^[k + m] s = s. This completes the subproof of the return lemma h_ret: whenever t is reachable from s, there is an exponent k < |V| such that f^[k] t = s.
uses
isPeriodicPt_iff_minimalPeriod_dvd.mprexact isPeriodicPt_iff_minimalPeriod_dvd.mpr hdvdReachability is reflexive.
We split the theorem into proving that reachability is an equivalence relation and supplying the return bound h_ret. For reflexivity, choosing the exponent 0 gives f^[0] s = s for any state s.
refine ⟨⟨?_, ?_, ?_⟩, h_ret⟩ · intro s exact ⟨0, rfl⟩
Reachability is symmetric.
If t is reachable from s, the return lemma h_ret provides an exponent k < |V| such that f^[k] t = s. This directly exhibits a witness showing that s is reachable from t.
· intro s t hst obtain ⟨k, -, hk⟩ := h_ret s t hst exact ⟨k, hk⟩
Reachability is transitive.
If f^[m] s = t and f^[n] t = u, then iterating n + m times gives f^[n + m] s = f^[n] (f^[m] s) = f^[n] t = u, so reachability is transitive with witness n + m.
uses
Function.iterate_add_apply· intro s t u ⟨m, hm⟩ ⟨n, hn⟩ refine ⟨n + m, ?_⟩ rw [Function.iterate_add_apply, hm, hn]
Injective.mem_periodicPts- For an injective function on a finite type, every point is periodic.
minimalPeriod_pos_of_mem_periodicPts- The minimal period of any periodic point is strictly positive.
Nat.mod_lt- For any positive divisor, the remainder is strictly less than the divisor.
lt_of_lt_of_le- Strict inequality is transitive with non-strict inequality: if a < b and b ≤ c, then a < c.
minimalPeriod_le_card- On a finite type, the minimal period of any point is at most the cardinality of the type.
iterate_add_apply- Iterating a function m + n times equals iterating it m times after n iterations: f^[m + n] x = f^[m] (f^[n] x).
Nat.eq_zero_or_pos- Every natural number is either 0 or strictly positive.
Nat.dvd_of_mod_eq_zero- If the remainder of n divided by m is zero, then m divides n.
Nat.mod_eq_of_lt- If a < b, then a % b = a.
Nat.div_add_mod- Division with remainder identity: n * (m / n) + m % n = m.
dvd_add- If a divides b and a divides c, then a divides b + c.
dvd_mul_right- For any a and b, a divides a * b.
dvd_rfl- Every element divides itself.
isPeriodicPt_iff_minimalPeriod_dvd.mpr- If the minimal period of x divides n, then x is periodic with period n (f^[n] x = x).
Function.iterate_add_apply- Iterating a function m + n times equals iterating it m times after n iterations: f^[m + n] x = f^[m] (f^[n] x).
- The lemma `isPeriodicPt_iff_minimalPeriod_dvd` is stated in terms of `IsPeriodicPt f n x`, which is definitionally equal to `f^[n] x = 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
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 a finite reversible transition system, reachability under f is an equivalence relation, and reverse paths exist with length strictly bounded by |V|. -/theorem reversible_transition_reachability_equivalence {V : Type*} [Fintype V] (f : V → V) (hf : Function.Injective f) : Equivalence (fun s t : V => ∃ m : ℕ, f^[m] s = t) ∧ ∀ s t : V, (∃ m : ℕ, f^[m] s = t) → ∃ k < Fintype.card V, f^[k] t = s := by open Function in have h_ret : ∀ s t : V, (∃ m : ℕ, f^[m] s = t) → ∃ k < Fintype.card V, f^[k] t = s := by intro s t ⟨m, hm⟩ set p := minimalPeriod f s have hmem : s ∈ periodicPts f := Injective.mem_periodicPts hf s have hp : 0 < p := minimalPeriod_pos_of_mem_periodicPts hmem set k := (p - m % p) % p have hk_lt_p : k < p := Nat.mod_lt _ hp have hk_lt_card : k < Fintype.card V := lt_of_lt_of_le hk_lt_p minimalPeriod_le_card refine ⟨k, hk_lt_card, ?_⟩ rw [← hm, ← iterate_add_apply] have hdvd : p ∣ k + m := by dsimp [k] rcases Nat.eq_zero_or_pos (m % p) with h0 | hpos · rw [h0] simp [Nat.dvd_of_mod_eq_zero h0] · have hlt : m % p < p := Nat.mod_lt m hp have h1 : p - m % p < p := by omega rw [Nat.mod_eq_of_lt h1] have : p - m % p + m = p * (m / p) + p := by have hm' : m = p * (m / p) + m % p := (Nat.div_add_mod m p).symm omega rw [this] exact dvd_add (dvd_mul_right p (m / p)) dvd_rfl exact isPeriodicPt_iff_minimalPeriod_dvd.mpr hdvd refine ⟨⟨?_, ?_, ?_⟩, h_ret⟩ · intro s exact ⟨0, rfl⟩ · intro s t hst obtain ⟨k, -, hk⟩ := h_ret s t hst exact ⟨k, hk⟩ · intro s t u ⟨m, hm⟩ ⟨n, hn⟩ refine ⟨n + m, ?_⟩ rw [Function.iterate_add_apply, hm, hn]