condorcet_acyclic_cover_realizes_critical_signatures
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
- condorcet_acyclic_half_cover_signature_pairs_ge_sevenLet a relation on Fin m have an outside common predecessor for every set of at most three vertices, and let a positive finite family of…
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.
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.
uses
has_min,Set.mem_univ,False.elimclassical 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
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.
uses
card_sdiff,inter_univ,card_univ,Fintype.card_finintro 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
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.
uses
card_image_leobtain ⟨a,_,ha⟩ := hroot (W.image b) (card_image_le.trans (by omega))
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.
uses
mem_image.mprhave 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⟩))
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.
uses
mem_sdiff.mpr,mem_univ,mem_filter.mplet 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
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.
uses
eq_of_subset_of_card_lehave heq : I=S := eq_of_subset_of_card_le hIS (by rw [hS] exact hcover a)
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.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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]