AFTD Auto-Formalizing Theoretical Domains

cycle_cover_group_preserves_reachability

theoremverified

Every element k of the subgroup generated by the cycle covers of R maps each point x to a point reachable from x and reachable back to x along R. In particular k preserves the partition of V into mutual-reachability classes (the strongly connected components).

Statement

theorem cycle_cover_group_preserves_reachability {V : Type*} [Fintype V] (R : V → V → Prop)
    (k : Equiv.Perm V) (hk : k ∈ Subgroup.closure {p : Equiv.Perm V | ∀ v, R v (p v)}) (x : V) :
    Relation.ReflTransGen R x (k x) ∧ Relation.ReflTransGen R (k x) x
Source
step towards simple_graph_normalized_hop_group_quadratic_word_diameter
Verified
31 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • cycle_cover_reverse_reachableIf 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…

The proof, explained

We prove that every permutation in the subgroup generated by cycle covers preserves mutual reachability by induction on the subgroup closure. For a generating cycle cover, forward reachability holds in a single step, while backward reachability follows because orbits on a finite set form closed cycles. The property is preserved by the identity (by reflexivity), under composition (by transitivity of reachability), and under inversion (by evaluating the induction hypothesis at the inverse point).

  1. To prove mutual reachability for $k$, it suffices to establish by subgroup induction that every permutation in the generated subgroup preserves mutual reachability for all points.

    We generalize the theorem to an auxiliary lemma (`key`) asserting the mutual reachability property for all elements in the subgroup closure. We then apply `Subgroup.closure_induction`, reducing the claim to four cases: the generating cycle covers, the identity permutation, closure under multiplication, and closure under inversion.

    lines 5–10

    uses Subgroup.closure_induction

      have key : ∀ k ∈ Subgroup.closure {p : Equiv.Perm V | ∀ v, R v (p v)},
          ∀ x, Relation.ReflTransGen R x (k x) ∧ Relation.ReflTransGen R (k x) x := by
        intro k hk
        refine Subgroup.closure_induction
          (p := fun g _ => ∀ x, Relation.ReflTransGen R x (g x) ∧ Relation.ReflTransGen R (g x) x)
          ?_ ?_ ?_ ?_ hk
  2. Generating cycle covers preserve mutual reachability.

    Let $p$ be a cycle cover, so $R(v, p(v))$ for all $v$. For any vertex $x$, forward reachability $R^*(x, p(x))$ holds in one step by `Relation.ReflTransGen.single`. Reverse reachability $R^*(p(x), x)$ holds by `cycle_cover_reverse_reachable`, which uses the finiteness of $V$ to guarantee that the orbit of $x$ under $p$ forms a cycle that eventually returns to $x$ along $R$.

    lines 11–12

    uses Relation.ReflTransGen.single, cycle_cover_reverse_reachable

        · intro p hp x
          exact ⟨Relation.ReflTransGen.single (hp x), cycle_cover_reverse_reachable R p hp x⟩
  3. The identity permutation preserves mutual reachability.

    The identity permutation maps each vertex $x$ to $1(x) = x$. Reflexivity of reachability (`Relation.ReflTransGen.refl`) immediately gives $R^*(x, x)$ in both directions.

    lines 13–14

    uses Relation.ReflTransGen.refl

        · intro x
          exact ⟨Relation.ReflTransGen.refl, Relation.ReflTransGen.refl⟩
  4. Mutual reachability is preserved under composition of permutations.

    Assume $a$ and $b$ preserve mutual reachability for all points. By `Equiv.Perm.mul_apply`, $(a * b)(x) = a(b(x))$. The induction hypothesis for $b$ gives mutual reachability between $x$ and $b(x)$, and the induction hypothesis for $a$ at $b(x)$ gives mutual reachability between $b(x)$ and $a(b(x))$. Transitivity of reachability combines these paths into mutual reachability between $x$ and $a(b(x))$.

    lines 15–17

    uses Equiv.Perm.mul_apply

        · intro a b ha hb h1 h2 x
          rw [Equiv.Perm.mul_apply]
          exact ⟨(h2 x).1.trans (h1 (b x)).1, (h1 (b x)).2.trans (h2 x).2⟩
  5. Mutual reachability is preserved under inversion of permutations.

    Assume $a$ preserves mutual reachability for all points. Instantiating this assumption at the point $a^{-1}(x)$ gives that $a^{-1}(x)$ and $a(a^{-1}(x))$ are mutually reachable. Because $a(a^{-1}(x)) = x$, this is precisely the statement that $x$ and $a^{-1}(x)$ are mutually reachable.

    lines 18–19

        · intro a ha h1 x
          exact ⟨by simpa using (h1 (a⁻¹ x)).2, by simpa using (h1 (a⁻¹ x)).1⟩
  6. The permutation $k$ preserves mutual reachability for $x$.

    Specializing the auxiliary lemma `key` to the permutation $k$, the membership hypothesis $hk$, and the vertex $x$ completes the proof.

    line 20

      exact key k hk x
Subgroup.closure_induction
To prove a property for all elements in the subgroup generated by a set, it suffices to prove it for elements in the generating set, the identity, products, and inverses.
Relation.ReflTransGen.single
A single step of a relation $R(a, b)$ implies reachability $R^*(a, b)$ in its reflexive-transitive closure.
cycle_cover_reverse_reachable
For any cycle cover $p$ on a finite type $V$ (satisfying $R(v, p(v))$ for all $v$), every vertex $v$ is reachable from its image $p(v)$ along $R$.
Relation.ReflTransGen.refl
Every element is reachable from itself in zero steps in the reflexive-transitive closure of a relation ($R^*(a, a)$).
Equiv.Perm.mul_apply
Permutation multiplication acts by composition: $(f * g)(x) = f(g(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

/-- Every element of the cycle-cover group preserves both directions of R-reachability. -/theorem cycle_cover_group_preserves_reachability {V : Type*} [Fintype V] (R : V → V → Prop)    (k : Equiv.Perm V) (hk : k ∈ Subgroup.closure {p : Equiv.Perm V | ∀ v, R v (p v)}) (x : V) :    Relation.ReflTransGen R x (k x) ∧ Relation.ReflTransGen R (k x) x := by  have key : ∀ k ∈ Subgroup.closure {p : Equiv.Perm V | ∀ v, R v (p v)},      ∀ x, Relation.ReflTransGen R x (k x) ∧ Relation.ReflTransGen R (k x) x := by    intro k hk    refine Subgroup.closure_induction      (p := fun g _ => ∀ x, Relation.ReflTransGen R x (g x) ∧ Relation.ReflTransGen R (g x) x)      ?_ ?_ ?_ ?_ hk    · intro p hp x      exact ⟨Relation.ReflTransGen.single (hp x), cycle_cover_reverse_reachable R p hp x⟩    · intro x      exact ⟨Relation.ReflTransGen.refl, Relation.ReflTransGen.refl⟩    · intro a b ha hb h1 h2 x      rw [Equiv.Perm.mul_apply]      exact ⟨(h2 x).1.trans (h1 (b x)).1, (h1 (b x)).2.trans (h2 x).2⟩    · intro a ha h1 x      exact ⟨by simpa using (h1 (a⁻¹ x)).2, by simpa using (h1 (a⁻¹ x)).1⟩  exact key k hk x
See it in the graphDiscuss this resultChallenge it