AFTD Auto-Formalizing Theoretical Domains

wild_no_closed_union_of_blocks

theoremverified

If every used color crosses every nonempty proper cut of the block labels under p, then no nonempty proper vertex set that is a union of p-fibers is closed under a used color.

Statement

theorem wild_no_closed_union_of_blocks {n k q : ℕ}
    (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k)) (p : Fin n → Fin q)
    (hcut : ∀ (e : (⊤ : SimpleGraph (Fin n)).edgeSet) (S : Finset (Fin q)),
      S.Nonempty → S ≠ Finset.univ →
      ∃ (u v : Fin n) (huv : u ≠ v), p u ∈ S ∧ p v ∉ S ∧ c ⟨s(u,v),wild_kn_mem huv⟩ = c e)
    (e : (⊤ : SimpleGraph (Fin n)).edgeSet) (U : Finset (Fin n))
    (hU : U.Nonempty) (hproper : U ≠ Finset.univ)
    (hsat : ∀ u ∈ U, ∀ v, p v = p u → v ∈ U) : ¬w279_closed c (c e) U
Source
Certificate-soundness and finite averaging helpers for the OP-306 campaign on arXiv:2610.22142, Sections 3.3.1 and 3.3.2. The thirteen-vertex equivalence is a reduction, not a proof of the conjectured equality; the moment criterion supplies no unproved universal numerical hypothesis.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 9
Used by 1

The proof, explained

The proof argues by contradiction: suppose a nonempty proper vertex set U, which is a union of fibers of p, is closed under the color of edge e. Its image S = p(U) in the block labels is nonempty, and it must be a proper subset because otherwise fiber-saturation would force U to contain every vertex. By hypothesis, every nonempty proper cut of block labels is crossed by an edge of color c(e), yielding an edge uv with p(u) ∈ S and p(v) ∉ S. By fiber-saturation, u must be in U; the closure of U then forces v into U, which contradicts p(v) ∉ S.

  1. Assume for contradiction that U is closed under color c(e), and define S to be the image p(U), which is nonempty.

    We assume for contradiction (hcl) that U is closed under monochromatic edges of color c(e). We define S to be the image of U under the block projection p. Since U is nonempty (hU), its image S is also nonempty.

    lines 13–16

      classical
      intro hcl
      let S : Finset (Fin q) := U.image p
      have hS : S.Nonempty := hU.image p
  2. S is a proper subset of the block labels (S ≠ Finset.univ).

    Suppose for contradiction that S = Finset.univ. To show this contradicts U ≠ Finset.univ (hproper), by Finset.eq_univ_of_forall it suffices to show every vertex v belongs to U. For any vertex v, its block p(v) belongs to S = Finset.univ by Finset.mem_univ. By definition of the image (Finset.mem_image.1), there is some u ∈ U such that p(u) = p(v). Since U is a union of fibers of p (hsat), p(v) = p(u) implies v ∈ U. Hence U would be the entire vertex set, contradicting hproper.

    lines 17–24

    uses Finset.eq_univ_of_forall, Finset.mem_univ, Finset.mem_image.1

      have hSp : S ≠ Finset.univ := by
        intro hh
        apply hproper
        apply Finset.eq_univ_of_forall
        intro v
        have hv : p v ∈ S := hh ▸ Finset.mem_univ _
        obtain ⟨u,hu,hp⟩ := Finset.mem_image.1 hv
        exact hsat u hu v hp.symm
  3. There is an edge uv of color c(e) crossing the cut between S and its complement.

    Because S is a nonempty proper subset of block labels, the cut-crossing hypothesis hcut applied to edge e and set S provides two distinct vertices u and v such that p(u) ∈ S, p(v) ∉ S, and the edge uv has color c(e).

    line 25

      obtain ⟨u,v,huv,hu,hv,hc⟩ := hcut e S hS hSp
  4. Both u and v must belong to U, contradicting p(v) ∉ S.

    Since p(u) ∈ S = p(U), there is some x ∈ U with p(x) = p(u) by Finset.mem_image.1. Because U is a union of fibers (hsat), u belongs to U. By the assumed closure of U under color c(e) (hcl), the edge uv of color c(e) forces v to belong to U as well. But if v ∈ U, then p(v) ∈ p(U) = S by Finset.mem_image_of_mem, which directly contradicts p(v) ∉ S.

    lines 26–29

    uses Finset.mem_image.1, Finset.mem_image_of_mem

      obtain ⟨x,hx,hpx⟩ := Finset.mem_image.1 hu
      have huU := hsat x hx u hpx.symm
      have hvU := hcl u huU v huv hc
      exact hv (Finset.mem_image_of_mem p hvU)
Finset.eq_univ_of_forall
A finite set s of a finite type contains all elements if and only if it is equal to the universal set.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
Finset.mem_image.1
If y belongs to the image f(s), then there exists some element x in s such that f(x) = y.
Finset.mem_image_of_mem
If an element a belongs to s, then f(a) belongs to the image f(s).

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

open scoped BigOperators Classicalset_option maxHeartbeats 1600000set_option maxRecDepth 100000theorem wild_no_closed_union_of_blocks {n k q : ℕ}    (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin k)) (p : Fin n → Fin q)    (hcut : ∀ (e : (⊤ : SimpleGraph (Fin n)).edgeSet) (S : Finset (Fin q)),      S.Nonempty → S ≠ Finset.univ →      ∃ (u v : Fin n) (huv : u ≠ v), p u ∈ S ∧ p v ∉ S ∧ c ⟨s(u,v),wild_kn_mem huv⟩ = c e)    (e : (⊤ : SimpleGraph (Fin n)).edgeSet) (U : Finset (Fin n))    (hU : U.Nonempty) (hproper : U ≠ Finset.univ)    (hsat : ∀ u ∈ U, ∀ v, p v = p u → v ∈ U) : ¬w279_closed c (c e) U := by  classical  intro hcl  let S : Finset (Fin q) := U.image p  have hS : S.Nonempty := hU.image p  have hSp : S ≠ Finset.univ := by    intro hh    apply hproper    apply Finset.eq_univ_of_forall    intro v    have hv : p v ∈ S := hh ▸ Finset.mem_univ _    obtain ⟨u,hu,hp⟩ := Finset.mem_image.1 hv    exact hsat u hu v hp.symm  obtain ⟨u,v,huv,hu,hv,hc⟩ := hcut e S hS hSp  obtain ⟨x,hx,hpx⟩ := Finset.mem_image.1 hu  have huU := hsat x hx u hpx.symm  have hvU := hcl u huU v huv hc  exact hv (Finset.mem_image_of_mem p hvU)
See it in the graphDiscuss this resultChallenge it