condorcet_acyclic_cover_uniformize
An acyclic family covering every vertex at least q times can be trimmed, independently at each vertex, to an acyclic subfamily with exactly q memberships per vertex. The relation is unchanged.
Statement
theorem condorcet_acyclic_cover_uniformize (m n q : ℕ) (R : Fin m → Fin m → Prop) (U : Fin n → Finset (Fin m)) (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) : ∃ V : Fin n → Finset (Fin m), (∀ v, V v ⊆ U v) ∧ (∀ v, WellFounded (fun a b : {a : Fin m // a ∈ V v} => R a.val b.val)) ∧ (∀ a, (univ.filter fun v => a ∈ V v).card = q)
- Source
- IN-391, OP-19 campaign session10, 2026-10-30. Supporting lemmas and precisely scoped method diagnostics for the rank-saturated acyclic-cover route. The main election theorem remains open; no new election bound or novelty is claimed.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- condorcet_failure_iff_acyclic_half_coverFix a positive number n of voters. There exists a finite election with these n voters in which every candidate set of size at most three…
- Used by 1
- condorcet_acyclic_cover_rank_minimumFor positive q, every finite S_k relation with an n-set acyclic family covering every vertex at least q times yields a trimmed exactly-q…
The proof, explained
The proof proceeds by dualizing the incidence between elements and sets. By the covering hypothesis and the axiom of choice, each element a is assigned a set S(a) of exactly q indices v for which a ∈ U v. Defining the subfamily by V v = {a | v ∈ S(a)} guarantees that each element belongs to exactly q sets in V, and that V v ⊆ U v. Finally, the well-foundedness of R on each V v is inherited from U v via the canonical subtype inclusion.
For each element a, there exists a set of indices S(a) of size q such that a ∈ U v for all v ∈ S(a).
By hypothesis `hcover`, the set of indices v such that a ∈ U v has cardinality at least q. Applying `exists_subset_card_eq`, every finite set of size at least q contains a subset of size exactly q. Using the axiom of choice (`choose`), we select a function S associating to each element a such a subset S(a) with cardinality q.
uses
exists_subset_card_eqclassical have hex : ∀ a : Fin m, ∃ S : Finset (Fin n), S ⊆ univ.filter (fun v => a ∈ U v) ∧ S.card = q := by intro a exact exists_subset_card_eq (hcover a) choose S hsub hcard using hex
Defining V v = {a | v ∈ S(a)}, every set V v is a subset of U v.
We define the family V by transposing membership: a ∈ V v if and only if v ∈ S(a). If a ∈ V v, then v ∈ S(a) ⊆ {w | a ∈ U w}, which means a ∈ U v. Thus V v ⊆ U v for every index v.
let V : Fin n → Finset (Fin m) := fun v => univ.filter fun a => v ∈ S a have hVU : ∀ v, V v ⊆ U v := by intro v a ha exact (mem_filter.mp (hsub a (mem_filter.mp ha).2)).2
The relation R restricted to each V v is well-founded.
We instantiate the existential witness with the family V and supply the inclusion proof V v ⊆ U v. For each v, the canonical inclusion map from {a // a ∈ V v} to {a // a ∈ U v} pulls back the relation R on U v to the relation R on V v. Since the relation on U v is well-founded by `hU v`, `InvImage.wf` implies that the restricted relation on V v is also well-founded.
uses
InvImage.wfrefine ⟨V,hVU,?_,?_⟩ · intro v exact InvImage.wf (fun a : {a : Fin m // a ∈ V v} => (⟨a.val,hVU v a.property⟩ : {a : Fin m // a ∈ U v})) (hU v)
For every element a, the number of sets V v containing a is exactly q.
By definition of V, an element a belongs to V v if and only if v ∈ S(a), so {v | a ∈ V v} is identical to S(a). Since S(a) was chosen to have cardinality q, rewriting with this equality shows that #{v | a ∈ V v} = q, which completes the proof.
· intro a have heq : univ.filter (fun v => a ∈ V v) = S a := by ext v simp [V] rw [heq,hcard]
exists_subset_card_eq- A finite set with cardinality at least q contains a subset with cardinality exactly q.
InvImage.wf- The inverse image (pullback) of a well-founded relation under any mapping is well-founded.
- In Lean, acyclicity of the relation on a finite set is represented by well-foundedness on the corresponding subtype. The fact that a subset inherits acyclicity is proved formally via `InvImage.wf` along the subtype inclusion.
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 100000000set_option maxRecDepth 30000theorem condorcet_acyclic_cover_uniformize (m n q : ℕ) (R : Fin m → Fin m → Prop) (U : Fin n → Finset (Fin m)) (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) : ∃ V : Fin n → Finset (Fin m), (∀ v, V v ⊆ U v) ∧ (∀ v, WellFounded (fun a b : {a : Fin m // a ∈ V v} => R a.val b.val)) ∧ (∀ a, (univ.filter fun v => a ∈ V v).card = q) := by classical have hex : ∀ a : Fin m, ∃ S : Finset (Fin n), S ⊆ univ.filter (fun v => a ∈ U v) ∧ S.card = q := by intro a exact exists_subset_card_eq (hcover a) choose S hsub hcard using hex let V : Fin n → Finset (Fin m) := fun v => univ.filter fun a => v ∈ S a have hVU : ∀ v, V v ⊆ U v := by intro v a ha exact (mem_filter.mp (hsub a (mem_filter.mp ha).2)).2 refine ⟨V,hVU,?_,?_⟩ · intro v exact InvImage.wf (fun a : {a : Fin m // a ∈ V v} => (⟨a.val,hVU v a.property⟩ : {a : Fin m // a ∈ U v})) (hU v) · intro a have heq : univ.filter (fun v => a ∈ V v) = S a := by ext v simp [V] rw [heq,hcard]