AFTD Auto-Formalizing Theoretical Domains

condorcet_acyclic_cover_realizes_critical_signatures

theoremverified

Suppose n=k+q induced acyclic vertex sets cover each vertex at least q times, and every set of at most k vertices has an outside common predecessor. Then every q-element subset of the n set indices occurs as the EXACT activity signature of some vertex. The relation has arbitrary finite order. This forces all ten signatures in the S2 three-of-five auxiliary and all twenty signatures in a six-support balanced S3 half-cover, but gives no upper bound on cohort multiplicity.

Statement

theorem condorcet_acyclic_cover_realizes_critical_signatures
    (m n k q : ℕ) (hn : n=k+q) (R : Fin m → Fin m → Prop)
    (U : Fin n → Finset (Fin m))
    (hroot : ∀ J : Finset (Fin m), J.card ≤ k →
      ∃ a,a∉J ∧ ∀ b∈J,R a b)
    (hU : ∀ v,WellFounded (fun a b : {a : Fin m // a∈U v} => R a.val b.val))
    (hcover : ∀ a,q≤(univ.filter fun v => a∈U v).card) :
    ∀ S : Finset (Fin n), S.card=q →
      ∃ a : Fin m,∀ v,a∈U v ↔ v∈S
Source
IN-383, OP-19 campaign session9, 2026-10-30. General source-selection argument underlying the bounded activity-signature searches. Supporting structural lemma only; no new election bound or research novelty is claimed.
Verified
30 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1

The proof, explained

To realize an arbitrary q-element target signature S ⊆ Fin n, we consider its complement W = (Fin n) \ S, which has cardinality n - q = k. For each index v, acyclicity (well-foundedness) of U(v) yields a source vertex b(v) with no incoming R-edges from within U(v). The set of these sources for v ∈ W has at most k vertices, so by the root hypothesis there is an outside vertex a that precedes all of them under R. This prevents a from belonging to U(v) for any v ∈ W, forcing the active index set I = {v | a ∈ U(v)} to be a subset of S; since |I| ≥ q = |S| by the covering hypothesis, we obtain I = S.

  1. For each index v, we can choose a vertex b(v) that has no predecessor in U(v) under R.

    We first apply the common-predecessor hypothesis (hroot) to the empty set to obtain a fallback vertex r. For each index v, if U(v) is nonempty, the well-foundedness of R restricted to U(v) provides a minimal element b ∈ U(v) with no incoming R-edge from any vertex in U(v) (via has_min and Set.mem_univ). If U(v) is empty, the fallback vertex r vacuously satisfies this condition (handled via False.elim). Applying the axiom of choice (choose) yields a choice function b such that no vertex in U(v) precedes b(v) under R.

    lines 13–22

    uses has_min, Set.mem_univ, False.elim

      classical
      obtain ⟨r,_,_⟩ := hroot ∅ (by simp)
      have hsources : ∀ v,∃ b,∀ a∈U v,¬R a b := by
        intro v
        by_cases hne : (U v).Nonempty
        · obtain ⟨a,ha⟩ := hne
          obtain ⟨b,_,hmin⟩ := (hU v).has_min Set.univ ⟨⟨a,ha⟩,Set.mem_univ _⟩
          exact ⟨b.val,fun a ha hab => hmin ⟨a,ha⟩ (Set.mem_univ _) hab⟩
        · exact ⟨r,fun a ha => False.elim (hne ⟨a,ha⟩)⟩
      choose b hb using hsources
  2. For any target signature S of size q, its complement W = univ \ S has cardinality k.

    Fixing an arbitrary subset S ⊆ Fin n with |S| = q, we define its complement W = (univ \ S). By card_sdiff, inter_univ, card_univ, and Fintype.card_fin, |W| = n - q. Since n = k + q, linear arithmetic (omega) shows |W| = k.

    lines 23–28

    uses card_sdiff, inter_univ, card_univ, Fintype.card_fin

      intro S hS
      let W := univ \ S
      have hW : W.card=k := by
        dsimp only [W]
        rw [card_sdiff,inter_univ,card_univ,Fintype.card_fin,hS,hn]
        omega
  3. There exists a vertex a that is an outside common predecessor to all source vertices b(v) for v ∈ W.

    The image set {b(v) | v ∈ W} has cardinality at most |W| = k by card_image_le. By the root hypothesis (hroot), there exists a vertex a outside this image that precedes every vertex in it under R, so R a (b v) holds for every v ∈ W.

    line 29

    uses card_image_le

      obtain ⟨a,_,ha⟩ := hroot (W.image b) (card_image_le.trans (by omega))
  4. The vertex a does not belong to U(v) for any index v in the complement W.

    Suppose for contradiction that a ∈ U(v) for some v ∈ W. By the minimal property of b(v), no vertex in U(v) precedes b(v), so ¬R a (b v). But a was chosen to precede every element in {b(w) | w ∈ W}, including b(v) (by mem_image.mpr), so R a (b v) holds, a contradiction.

    lines 30–32

    uses mem_image.mpr

      have hav : ∀ v∈W,a∉U v := by
        intro v hv hau
        exact hb v a hau (ha (b v) (mem_image.mpr ⟨v,hv,rfl⟩))
  5. The active index set I = {v | a ∈ U(v)} is a subset of the target signature S.

    Let I be the set of indices v such that a ∈ U(v). For any v ∈ I, if v were not in S, then v would belong to the complement W (by mem_sdiff.mpr and mem_univ). But we established that a ∉ U(v) for all v ∈ W, contradicting a ∈ U(v) (extracted by mem_filter.mp). Hence v ∈ S, proving I ⊆ S.

    lines 33–37

    uses mem_sdiff.mpr, mem_univ, mem_filter.mp

      let I := univ.filter fun v => a∈U v
      have hIS : I ⊆ S := by
        intro v hv
        by_contra hnS
        exact hav v (mem_sdiff.mpr ⟨mem_univ _,hnS⟩) (mem_filter.mp hv).2
  6. The active index set I is exactly equal to the target signature S.

    We have I ⊆ S. The covering hypothesis (hcover) guarantees that a belongs to at least q sets U(v), meaning |I| ≥ q. Since |S| = q, we have |S| ≤ |I|. For finite sets, a subset of cardinality at least that of the ambient set must equal it (eq_of_subset_of_card_le), so I = S.

    lines 38–40

    uses eq_of_subset_of_card_le

      have heq : I=S := eq_of_subset_of_card_le hIS (by
        rw [hS]
        exact hcover a)
  7. Vertex a realizes the exact activity signature S, completing the proof.

    We supply a as the witness. For every index v, the membership a ∈ U(v) is by definition equivalent to v ∈ I, which is equivalent to v ∈ S since I = S.

    lines 41–45

      refine ⟨a,?_⟩
      intro v
      change a∈U v ↔ v∈S
      rw [← heq]
      simp [I]
has_min
In a well-founded relation, every nonempty set contains a minimal element with no predecessor in that set.
Set.mem_univ
Every element of a type belongs to the universal set Set.univ.
False.elim
From a contradiction (a proof of False), any proposition can be derived.
card_sdiff
The cardinality of t \ s equals the cardinality of t minus the cardinality of s ∩ t.
inter_univ
The intersection of any finite set with the universal finite set is the set itself.
card_univ
The cardinality of the universal finite set Finset.univ on a finite type equals the cardinality of the type.
Fintype.card_fin
The cardinality of Fin n is n.
card_image_le
The cardinality of the image of a finite set under any function is at most the cardinality of the set.
mem_image.mpr
If an element is the image of some element in a finite set, then it belongs to the image set.
mem_sdiff.mpr
If an element belongs to s and not to t, then it belongs to the difference s \ t.
mem_univ
Every element of a finite type belongs to Finset.univ.
mem_filter.mp
If an element belongs to the filtered set {x ∈ s | p x}, then it satisfies the predicate p.
eq_of_subset_of_card_le
If s ⊆ t and |t| ≤ |s| for finite sets, then s = t.

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 Finsetset_option maxHeartbeats 4000000theorem condorcet_acyclic_cover_realizes_critical_signatures    (m n k q : ℕ) (hn : n=k+q) (R : Fin m → Fin m → Prop)    (U : Fin n → Finset (Fin m))    (hroot : ∀ J : Finset (Fin m), J.card ≤ k →      ∃ a,a∉J ∧ ∀ b∈J,R a b)    (hU : ∀ v,WellFounded (fun a b : {a : Fin m // a∈U v} => R a.val b.val))    (hcover : ∀ a,q≤(univ.filter fun v => a∈U v).card) :    ∀ S : Finset (Fin n), S.card=q →      ∃ a : Fin m,∀ v,a∈U v ↔ v∈S := by  classical  obtain ⟨r,_,_⟩ := hroot ∅ (by simp)  have hsources : ∀ v,∃ b,∀ a∈U v,¬R a b := by    intro v    by_cases hne : (U v).Nonempty    · obtain ⟨a,ha⟩ := hne      obtain ⟨b,_,hmin⟩ := (hU v).has_min Set.univ ⟨⟨a,ha⟩,Set.mem_univ _⟩      exact ⟨b.val,fun a ha hab => hmin ⟨a,ha⟩ (Set.mem_univ _) hab⟩    · exact ⟨r,fun a ha => False.elim (hne ⟨a,ha⟩)⟩  choose b hb using hsources  intro S hS  let W := univ \ S  have hW : W.card=k := by    dsimp only [W]    rw [card_sdiff,inter_univ,card_univ,Fintype.card_fin,hS,hn]    omega  obtain ⟨a,_,ha⟩ := hroot (W.image b) (card_image_le.trans (by omega))  have hav : ∀ v∈W,a∉U v := by    intro v hv hau    exact hb v a hau (ha (b v) (mem_image.mpr ⟨v,hv,rfl⟩))  let I := univ.filter fun v => a∈U v  have hIS : I ⊆ S := by    intro v hv    by_contra hnS    exact hav v (mem_sdiff.mpr ⟨mem_univ _,hnS⟩) (mem_filter.mp hv).2  have heq : I=S := eq_of_subset_of_card_le hIS (by    rw [hS]    exact hcover a)  refine ⟨a,?_⟩  intro v  change a∈U v ↔ v∈S  rw [← heq]  simp [I]
See it in the graphDiscuss this resultChallenge it