AFTD Auto-Formalizing Theoretical Domains

cycle_cover_reverse_reachable

theoremverified

If p is a cycle cover of a relation R on a finite type (every point is sent to an R-successor), then every image p v can reach back to v along R.

Statement

theorem cycle_cover_reverse_reachable {V : Type*} [Fintype V] (R : V → V → Prop)
    (p : Equiv.Perm V) (hp : ∀ v, R v (p v)) :
    ∀ v, Relation.ReflTransGen R (p v) v
Source
step towards simple_graph_normalized_hop_group_quadratic_word_diameter
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 1

The proof, explained

To show that p(v) can reach v along R, we first prove by induction that p(v) can reach any forward iterate p^k(p(v)). Because V is finite, p has a finite positive order d = orderOf(p), meaning that applying p exactly d times is the identity map. Choosing k = d - 1, the iterate p^(d - 1)(p(v)) equals p^d(v) = v, so the path along R from p(v) leads directly back to v.

  1. Fixing an arbitrary vertex v, every forward iterate p^k(p(v)) is reachable from p(v) along R.

    We introduce an arbitrary vertex v and prove by induction on k ∈ ℕ that p(v) can reach p^k(p(v)) via R. The base case k = 0 holds by reflexivity, since p^0(p(v)) = p(v). For the induction step k + 1, writing p^(k+1)(p(v)) as p(p^k(p(v))), the induction hypothesis gives a path from p(v) to p^k(p(v)), and the hypothesis hp provides an R-step from p^k(p(v)) to p(p^k(p(v))). Appending this step extends the reachability path.

    lines 5–12

    uses Relation.ReflTransGen.refl, Function.iterate_succ', Relation.ReflTransGen.tail

      intro v
      have h_iter : ∀ k, Relation.ReflTransGen R (p v) ((p^[k]) (p v)) := by
        intro k
        induction k with
        | zero => exact Relation.ReflTransGen.refl
        | succ k ih =>
          rw [Function.iterate_succ']
          exact Relation.ReflTransGen.tail ih (hp ((p^[k]) (p v)))
  2. The permutation p has finite positive order d, and p(v) can reach p^(d - 1)(p(v)) along R.

    Because V is a finite type, the permutation p has a strictly positive order d = orderOf(p) > 0. Specializing the reachability property to k = d - 1, we obtain that p(v) can reach p^(d - 1)(p(v)) along R.

    lines 13–14

    uses orderOf_pos

      have h_ord : 0 < orderOf p := orderOf_pos p
      have h := h_iter (orderOf p - 1)
  3. The (d - 1)-st iterate of p applied to p(v) equals v.

    We express p^(d - 1)(p(v)) as the (d - 1 + 1)-st iterate p^(d - 1 + 1)(v). Since d > 0, (d - 1) + 1 = d. In the permutation group Equiv.Perm V, p^d = 1, so p^d(v) = id(v) = v.

    lines 15–21

    uses Function.iterate_succ, Nat.sub_add_cancel, Equiv.Perm.coe_pow, pow_orderOf_eq_one

      have h_eq : (p^[orderOf p - 1]) (p v) = v := by
        have h1 : (p^[orderOf p - 1]) (p v) = (p^[orderOf p - 1 + 1]) v := by
          rw [Function.iterate_succ]
          rfl
        rw [Nat.sub_add_cancel h_ord] at h1
        rw [h1, ← Equiv.Perm.coe_pow, pow_orderOf_eq_one]
        rfl
  4. The reachability path from p(v) terminates at v, so p(v) reaches v along R.

    Substituting p^(d - 1)(p(v)) = v into the reachability path established earlier shows that p(v) can reach v along R.

    lines 22–23

      rw [h_eq] at h
      exact h
Relation.ReflTransGen.refl
Every element is related to itself in the reflexive-transitive closure of a relation.
Function.iterate_succ'
The (n + 1)-st iterate of a function satisfies f^(n+1) = f ∘ f^n.
Relation.ReflTransGen.tail
If a reaches b in the reflexive-transitive closure of r and r b c holds, then a reaches c.
orderOf_pos
In a finite cancellation monoid or finite group, every element has strictly positive order.
Function.iterate_succ
The (n + 1)-st iterate of a function satisfies f^(n+1) = f^n ∘ f.
Nat.sub_add_cancel
For natural numbers with m ≤ n, (n - m) + m = n.
Equiv.Perm.coe_pow
The n-th power of a permutation in the permutation group coincides with iterating the permutation n times as a function.
pow_orderOf_eq_one
Raising an element of a monoid to the power of its order yields the identity element.

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

/-- A cycle cover of a finite relation sends each point to a point that can reach it back. -/theorem cycle_cover_reverse_reachable {V : Type*} [Fintype V] (R : V → V → Prop)    (p : Equiv.Perm V) (hp : ∀ v, R v (p v)) :    ∀ v, Relation.ReflTransGen R (p v) v := by  intro v  have h_iter : ∀ k, Relation.ReflTransGen R (p v) ((p^[k]) (p v)) := by    intro k    induction k with    | zero => exact Relation.ReflTransGen.refl    | succ k ih =>      rw [Function.iterate_succ']      exact Relation.ReflTransGen.tail ih (hp ((p^[k]) (p v)))  have h_ord : 0 < orderOf p := orderOf_pos p  have h := h_iter (orderOf p - 1)  have h_eq : (p^[orderOf p - 1]) (p v) = v := by    have h1 : (p^[orderOf p - 1]) (p v) = (p^[orderOf p - 1 + 1]) v := by      rw [Function.iterate_succ]      rfl    rw [Nat.sub_add_cancel h_ord] at h1    rw [h1, ← Equiv.Perm.coe_pow, pow_orderOf_eq_one]    rfl  rw [h_eq] at h  exact h
See it in the graphDiscuss this resultChallenge it