AFTD Auto-Formalizing Theoretical Domains

zycle_hom_implies_closed_walk

theoremverifiedformalization

If f : ZMod ℓ × Fin 2 → α is a hypergraph homomorphism is_hypergraph_hom from the zycle Z_ℓ to a 3-uniform hypergraph G : Finset (Finset α), then there exists a closed walk W : ZMod ℓ → Finset α of length ℓ in the pair digraph of G satisfying pair_digraph_adj G (W i) (W (i + 1)) for all i in ZMod ℓ.

Statement

theorem zycle_hom_implies_closed_walk {α : Type*} [DecidableEq α]
    (ℓ : ℕ) [NeZero ℓ] (G : Finset (Finset α)) (hG : is_three_uniform G)
    (f : ZMod ℓ × Fin 2 → α) (hf : is_hypergraph_hom (zycle ℓ) G f) :
    ∃ W : ZMod ℓ → Finset α, ∀ i : ZMod ℓ, pair_digraph_adj G (W i) (W (i + 1))
Formalizes
arXiv:2611.16654 Lemma 2.3
Verified
14 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • zycleFor any positive integer ℓ, the 3-uniform zycle Z_ℓ has vertex set ZMod ℓ × Fin 2 and edge set consisting of the triples {(i,0), (i,1),…
  • is_hypergraph_homFor types V and W with decidable equality on W, finite hyperedge sets F : Finset (Finset V) and G : Finset (Finset W), and a map f : V →…
  • pair_digraph_adjTwo pairs P and Q of vertices form a directed arc P → Q in the pair digraph D(G) of a 3-uniform hypergraph G if both have cardinality 2…
  • is_three_uniformA hypergraph F (a finite family of finite sets of vertices) is 3-uniform if every hyperedge e in F has cardinality 3.
Used by 1

Read back from the Lean

Let α be a type with decidable equality, and let ℓ be a non-zero natural number. Let G be a finite collection of finite subsets of α such that every set in G has cardinality 3 (i.e., G is a 3-uniform hypergraph). Let f be a function from (ZMod ℓ × Fin 2) to α such that f is a hypergraph homomorphism from zycle ℓ to G (meaning that for every edge e of zycle ℓ, the image f(e) is in G). Then there exists a sequence of 2-element subsets W : ZMod ℓ → Finset α such that for every i ∈ ZMod ℓ, W(i) is adjacent to W(i + 1) in the pair digraph of G; that is: 1. |W(i)| = 2, 2. |W(i + 1)| = 2, and 3. for every vertex v ∈ W(i + 1), the set W(i) ∪ {v} is in G.

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

To show that a homomorphism f from the zycle Z_ℓ to a 3-uniform hypergraph G induces a closed walk in the pair digraph D(G), the walk is explicitly defined by setting W(i) = {f(i, 0), f(i, 1)} for each i in ZMod ℓ. Each W(i) has cardinality 2 because its elements are part of a 3-element hyperedge image in G, forcing f(i, 0) ≠ f(i, 1). Finally, for any vertex v in W(i+1), the set W(i) ∪ {v} is the image under f of one of the two hyperedges of Z_ℓ at step i, hence belongs to G by the homomorphism property, completing the adjacency requirement in D(G).

  1. If a finset {a, b, c} has cardinality 3, then a ≠ b.

    Suppose for contradiction that a = b. Then the three-element finset {a, b, c} collapses to {a, c}, which by Finset.card_le_two has cardinality at most 2. This directly contradicts the assumption that its cardinality is 3.

    lines 1–8

    uses Finset.card_le_two

    private lemma zycle_hom_implies_closed_walk_card_three_ne {α : Type*} [DecidableEq α] {a b c : α}
        (h : ({a,b,c} : Finset α).card = 3) : a ≠ b := by
      intro hab
      have key : ({a,b,c} : Finset α) = {a,c} := by ext x; simp [hab]
      rw [key] at h
      have := Finset.card_le_two (α := α) (a := a) (b := c)
      omega
    
  2. For each i ∈ ZMod ℓ, the image under f of {(i, 0), (i, 1), (i+1, 0)} is {f (i, 0), f (i, 1), f (i+1, 0)}, and similarly the image of {(i, 0), (i, 1), (i+1, 1)} is {f (i, 0), f (i, 1), f (i+1, 1)}.

    For each index i, set extensionality reduces equality of finsets to equivalence of membership. Using Finset.mem_image, Finset.mem_insert, and Finset.mem_singleton, an element x belongs to the image Finset.image f {(i,0), (i,1), (i+1,0)} if and only if x = f(i,0), x = f(i,1), or x = f(i+1,0). The two directions of the equivalence are verified by case analysis on the disjunctions using Or.inl and Or.inr. The identical argument applies to the second triple.

    lines 9–40

    uses Finset.mem_image, Finset.mem_insert, Finset.mem_singleton, Or.inl, Or.inr

    /-- A homomorphism from Z_ℓ to a 3-uniform hypergraph G implies a closed walk of length ℓ in D(G). -/
    theorem zycle_hom_implies_closed_walk {α : Type*} [DecidableEq α]
        (ℓ : ℕ) [NeZero ℓ] (G : Finset (Finset α)) (hG : is_three_uniform G)
        (f : ZMod ℓ × Fin 2 → α) (hf : is_hypergraph_hom (zycle ℓ) G f) :
        ∃ W : ZMod ℓ → Finset α, ∀ i : ZMod ℓ, pair_digraph_adj G (W i) (W (i + 1)) := by
      classical
      have himg1 : ∀ i : ZMod ℓ, Finset.image f ({(i,0),(i,1),(i+1,0)} : Finset (ZMod ℓ × Fin 2))
          = ({f (i,0), f (i,1), f (i+1,0)} : Finset α) := by
        intro i
        ext x; simp only [Finset.mem_image, Finset.mem_insert, Finset.mem_singleton]
        constructor
        · rintro ⟨a, h1 | h1 | h1, hx⟩
          · subst h1; exact Or.inl hx.symm
          · subst h1; exact Or.inr (Or.inl hx.symm)
          · subst h1; exact Or.inr (Or.inr hx.symm)
        · rintro (rfl | rfl | rfl)
          · exact ⟨(i,0), Or.inl rfl, rfl⟩
          · exact ⟨(i,1), Or.inr (Or.inl rfl), rfl⟩
          · exact ⟨(i+1,0), Or.inr (Or.inr rfl), rfl⟩
      have himg2 : ∀ i : ZMod ℓ, Finset.image f ({(i,0),(i,1),(i+1,1)} : Finset (ZMod ℓ × Fin 2))
          = ({f (i,0), f (i,1), f (i+1,1)} : Finset α) := by
        intro i
        ext x; simp only [Finset.mem_image, Finset.mem_insert, Finset.mem_singleton]
        constructor
        · rintro ⟨a, h1 | h1 | h1, hx⟩
          · subst h1; exact Or.inl hx.symm
          · subst h1; exact Or.inr (Or.inl hx.symm)
          · subst h1; exact Or.inr (Or.inr hx.symm)
        · rintro (rfl | rfl | rfl)
          · exact ⟨(i,0), Or.inl rfl, rfl⟩
          · exact ⟨(i,1), Or.inr (Or.inl rfl), rfl⟩
          · exact ⟨(i+1,1), Or.inr (Or.inr rfl), rfl⟩
  3. For every i ∈ ZMod ℓ, the triples {(i, 0), (i, 1), (i+1, 0)} and {(i, 0), (i, 1), (i+1, 1)} are hyperedges of zycle ℓ; their images under f belong to G and have cardinality 3.

    By definition of zycle ℓ as an indexed union (biUnion) over all i in the universal finset ZMod ℓ, both triples are members of zycle ℓ, as shown using Finset.mem_biUnion.mpr and Finset.mem_univ. Since f is a hypergraph homomorphism (hf), the image of any hyperedge of the zycle belongs to G. Furthermore, because G is 3-uniform (hG), every hyperedge in G has cardinality 3, so both image sets have cardinality 3.

    lines 41–58

    uses Finset.mem_biUnion.mpr, Finset.mem_univ

      have hmem1 : ∀ i : ZMod ℓ, ({(i,0),(i,1),(i+1,0)} : Finset (ZMod ℓ × Fin 2)) ∈ zycle ℓ := by
        intro i
        simp only [zycle]
        apply Finset.mem_biUnion.mpr
        exact ⟨i, Finset.mem_univ i, by simp⟩
      have hmem2 : ∀ i : ZMod ℓ, ({(i,0),(i,1),(i+1,1)} : Finset (ZMod ℓ × Fin 2)) ∈ zycle ℓ := by
        intro i
        simp only [zycle]
        apply Finset.mem_biUnion.mpr
        exact ⟨i, Finset.mem_univ i, by simp⟩
      have hG1 : ∀ i : ZMod ℓ, ({f (i,0), f (i,1), f (i+1,0)} : Finset α) ∈ G := by
        intro i; rw [← himg1 i]; exact hf _ (hmem1 i)
      have hG2 : ∀ i : ZMod ℓ, ({f (i,0), f (i,1), f (i+1,1)} : Finset α) ∈ G := by
        intro i; rw [← himg2 i]; exact hf _ (hmem2 i)
      have hcard1 : ∀ i : ZMod ℓ, ({f (i,0), f (i,1), f (i+1,0)} : Finset α).card = 3 :=
        fun i => hG _ (hG1 i)
      have hcard2 : ∀ i : ZMod ℓ, ({f (i,0), f (i,1), f (i+1,1)} : Finset α).card = 3 :=
        fun i => hG _ (hG2 i)
  4. Defining the candidate walk W(i) = {f(i, 0), f(i, 1)}, each vertex W(i) and W(i+1) has cardinality 2.

    We instantiate the existential closed walk with W(i) = {f(i, 0), f(i, 1)}. Unfolding the definition of pair_digraph_adj G (W i) (W (i+1)) requires showing |W(i)| = 2, |W(i+1)| = 2, and the adjacency condition. Because the image triple {f(i, 0), f(i, 1), f(i+1, 0)} has cardinality 3, the helper lemma zycle_hom_implies_closed_walk_card_three_ne ensures that f(i, 0) ≠ f(i, 1). Thus Finset.card_pair proves |W(i)| = 2. The exact same argument at index i+1 proves |W(i+1)| = 2.

    lines 59–66

    uses Finset.card_pair, zycle_hom_implies_closed_walk_card_three_ne

      refine ⟨fun i => ({f (i,0), f (i,1)} : Finset α), ?_⟩
      intro i
      rw [pair_digraph_adj]
      refine ⟨?_, ?_, ?_⟩
      · apply Finset.card_pair
        exact zycle_hom_implies_closed_walk_card_three_ne (hcard1 i)
      · apply Finset.card_pair
        exact zycle_hom_implies_closed_walk_card_three_ne (hcard1 (i+1))
  5. For every v ∈ W(i+1), the set W(i) ∪ {v} is a hyperedge in G, establishing pair_digraph_adj G (W i) (W (i+1)).

    An element v ∈ W(i+1) = {f(i+1, 0), f(i+1, 1)} is either f(i+1, 0) or f(i+1, 1). In the first case, W(i) ∪ {v} equals {f(i, 0), f(i, 1), f(i+1, 0)}, which was shown to belong to G. In the second case, W(i) ∪ {v} equals {f(i, 0), f(i, 1), f(i+1, 1)}, which also belongs to G. This verifies the third and final condition of pair_digraph_adj.

    lines 67–73

    uses Finset.mem_insert, Finset.mem_singleton

      · intro v hv
        simp only [Finset.mem_insert, Finset.mem_singleton] at hv
        rcases hv with rfl | rfl
        · rw [show (({f (i,0), f (i,1)} : Finset α) ∪ {f (i+1,0)}) = {f (i,0), f (i,1), f (i+1,0)} from by ext x; simp]
          exact hG1 i
        · rw [show (({f (i,0), f (i,1)} : Finset α) ∪ {f (i+1,1)}) = {f (i,0), f (i,1), f (i+1,1)} from by ext x; simp]
          exact hG2 i
Finset.card_le_two
For any elements a and b, the finset {a, b} has cardinality at most 2.
Finset.mem_image
An element b is in the image of a finset s under f if and only if there exists a ∈ s such that f a = b.
Finset.mem_insert
An element a belongs to insert b s if and only if a = b or a ∈ s.
Finset.mem_singleton
An element b belongs to the singleton {a} if and only if b = a.
Or.inl
From a proof of proposition a, derives the disjunction a ∨ b.
Or.inr
From a proof of proposition b, derives the disjunction a ∨ b.
Finset.mem_biUnion.mpr
If there exists an element a ∈ s such that b ∈ t a, then b belongs to the indexed union Finset.biUnion s t.
Finset.mem_univ
Every element of a finite type belongs to its universal finset Finset.univ.
Finset.card_pair
If a ≠ b, then the finset {a, b} has cardinality 2.
zycle_hom_implies_closed_walk_card_three_ne
If the finset {a, b, c} has cardinality 3, then a ≠ b.

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

private lemma zycle_hom_implies_closed_walk_card_three_ne {α : Type*} [DecidableEq α] {a b c : α}    (h : ({a,b,c} : Finset α).card = 3) : a ≠ b := by  intro hab  have key : ({a,b,c} : Finset α) = {a,c} := by ext x; simp [hab]  rw [key] at h  have := Finset.card_le_two (α := α) (a := a) (b := c)  omega/-- A homomorphism from Z_ℓ to a 3-uniform hypergraph G implies a closed walk of length ℓ in D(G). -/theorem zycle_hom_implies_closed_walk {α : Type*} [DecidableEq α]    (ℓ : ℕ) [NeZero ℓ] (G : Finset (Finset α)) (hG : is_three_uniform G)    (f : ZMod ℓ × Fin 2 → α) (hf : is_hypergraph_hom (zycle ℓ) G f) :    ∃ W : ZMod ℓ → Finset α, ∀ i : ZMod ℓ, pair_digraph_adj G (W i) (W (i + 1)) := by  classical  have himg1 : ∀ i : ZMod ℓ, Finset.image f ({(i,0),(i,1),(i+1,0)} : Finset (ZMod ℓ × Fin 2))      = ({f (i,0), f (i,1), f (i+1,0)} : Finset α) := by    intro i    ext x; simp only [Finset.mem_image, Finset.mem_insert, Finset.mem_singleton]    constructor    · rintro ⟨a, h1 | h1 | h1, hx⟩      · subst h1; exact Or.inl hx.symm      · subst h1; exact Or.inr (Or.inl hx.symm)      · subst h1; exact Or.inr (Or.inr hx.symm)    · rintro (rfl | rfl | rfl)      · exact ⟨(i,0), Or.inl rfl, rfl⟩      · exact ⟨(i,1), Or.inr (Or.inl rfl), rfl⟩      · exact ⟨(i+1,0), Or.inr (Or.inr rfl), rfl⟩  have himg2 : ∀ i : ZMod ℓ, Finset.image f ({(i,0),(i,1),(i+1,1)} : Finset (ZMod ℓ × Fin 2))      = ({f (i,0), f (i,1), f (i+1,1)} : Finset α) := by    intro i    ext x; simp only [Finset.mem_image, Finset.mem_insert, Finset.mem_singleton]    constructor    · rintro ⟨a, h1 | h1 | h1, hx⟩      · subst h1; exact Or.inl hx.symm      · subst h1; exact Or.inr (Or.inl hx.symm)      · subst h1; exact Or.inr (Or.inr hx.symm)    · rintro (rfl | rfl | rfl)      · exact ⟨(i,0), Or.inl rfl, rfl⟩      · exact ⟨(i,1), Or.inr (Or.inl rfl), rfl⟩      · exact ⟨(i+1,1), Or.inr (Or.inr rfl), rfl⟩  have hmem1 : ∀ i : ZMod ℓ, ({(i,0),(i,1),(i+1,0)} : Finset (ZMod ℓ × Fin 2)) ∈ zycle ℓ := by    intro i    simp only [zycle]    apply Finset.mem_biUnion.mpr    exact ⟨i, Finset.mem_univ i, by simp⟩  have hmem2 : ∀ i : ZMod ℓ, ({(i,0),(i,1),(i+1,1)} : Finset (ZMod ℓ × Fin 2)) ∈ zycle ℓ := by    intro i    simp only [zycle]    apply Finset.mem_biUnion.mpr    exact ⟨i, Finset.mem_univ i, by simp⟩  have hG1 : ∀ i : ZMod ℓ, ({f (i,0), f (i,1), f (i+1,0)} : Finset α) ∈ G := by    intro i; rw [← himg1 i]; exact hf _ (hmem1 i)  have hG2 : ∀ i : ZMod ℓ, ({f (i,0), f (i,1), f (i+1,1)} : Finset α) ∈ G := by    intro i; rw [← himg2 i]; exact hf _ (hmem2 i)  have hcard1 : ∀ i : ZMod ℓ, ({f (i,0), f (i,1), f (i+1,0)} : Finset α).card = 3 :=    fun i => hG _ (hG1 i)  have hcard2 : ∀ i : ZMod ℓ, ({f (i,0), f (i,1), f (i+1,1)} : Finset α).card = 3 :=    fun i => hG _ (hG2 i)  refine ⟨fun i => ({f (i,0), f (i,1)} : Finset α), ?_⟩  intro i  rw [pair_digraph_adj]  refine ⟨?_, ?_, ?_⟩  · apply Finset.card_pair    exact zycle_hom_implies_closed_walk_card_three_ne (hcard1 i)  · apply Finset.card_pair    exact zycle_hom_implies_closed_walk_card_three_ne (hcard1 (i+1))  · intro v hv    simp only [Finset.mem_insert, Finset.mem_singleton] at hv    rcases hv with rfl | rfl    · rw [show (({f (i,0), f (i,1)} : Finset α) ∪ {f (i+1,0)}) = {f (i,0), f (i,1), f (i+1,0)} from by ext x; simp]      exact hG1 i    · rw [show (({f (i,0), f (i,1)} : Finset α) ∪ {f (i+1,1)}) = {f (i,0), f (i,1), f (i+1,1)} from by ext x; simp]      exact hG2 i
See it in the graphDiscuss this resultChallenge it