AFTD Auto-Formalizing Theoretical Domains

reversible_transition_reachability_equivalence

theoremverifiedoriginal

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.

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

    lines 6–16

    uses Injective.mem_periodicPts, minimalPeriod_pos_of_mem_periodicPts, Nat.mod_lt, lt_of_lt_of_le, minimalPeriod_le_card, iterate_add_apply

      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]
  2. 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.

    lines 17–29

    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_rfl

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

    line 30

    uses isPeriodicPt_iff_minimalPeriod_dvd.mpr

        exact isPeriodicPt_iff_minimalPeriod_dvd.mpr hdvd
  4. Reachability 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.

    lines 31–33

      refine ⟨⟨?_, ?_, ?_⟩, h_ret⟩
      · intro s
        exact ⟨0, rfl⟩
  5. 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.

    lines 34–36

      · intro s t hst
        obtain ⟨k, -, hk⟩ := h_ret s t hst
        exact ⟨k, hk⟩
  6. 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.

    lines 37–39

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

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