condorcet_failure_k_iff_acyclic_half_cover
For fixed voter count n and committee bound k, some finite n-voter election has no strict Condorcet winning committee of size at most k if and only if some finite relation has outside common predecessors for sets of size at most k and admits n induced acyclic sets covering every vertex at least half the time. This generalizes the existing k=3 equivalence and proves neither existence nor nonexistence of such objects.
Statement
theorem condorcet_failure_k_iff_acyclic_half_cover (n k : ℕ) : (∃ (m : ℕ) (P : Fin n → Equiv.Perm (Fin m)), ∀ S : Finset (Fin m), S.card ≤ k → ¬is_condorcet_winning_set P S) ↔ (∃ (q : ℕ) (R : Fin q → Fin q → Prop) (U : Fin n → Finset (Fin q)), (∀ J : Finset (Fin q), J.card ≤ k → ∃ a, a∉J ∧ ∀ b∈J, R a b) ∧ (∀ v, WellFounded (fun a b : {a : Fin q // a∈U v} => R a.val b.val)) ∧ (∀ a, n ≤ 2*(univ.filter fun v => a∈U v).card))
- Source
- IN-383, OP-19 campaign session 9, 2026-10-30. Structural verification of the maximum-potential neighborhood route suggested in IN-380. Generalization of the existing acyclic-cover reduction, whose strict election definition is from Condorcet winning sets, Social Choice and Welfare 44(3):493-517 (2015), https://www.lamsade.dauphine.fr/~lang/papers/els15.pdf . No new election bound or research novelty is claimed.
- Verified
- 30 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- condorcet_acyclic_cover_no_winning_kFor any voter count n and committee bound k, a finite relation having outside common predecessors for all sets of at most k vertices,…
- condorcet_acyclic_half_cover_of_no_winning_kFor any n and k, a finite n-voter election with no strict Condorcet winning set of size at most k yields a finite relation with outside…
- is_condorcet_winning_setWith n voters holding strict rankings of m candidates, S is a Condorcet winning set if for every candidate a ∉ S, strictly fewer than n/2…
The proof, explained
The theorem establishes an equivalence between the non-existence of a size-at-most-k Condorcet winning committee in an n-voter election and the existence of a finite relation where every subset of size at most k has an outside common predecessor, together with n induced acyclic subsets covering each vertex at least half the time. The proof decomposes the equivalence into two directions. The forward direction applies `condorcet_acyclic_half_cover_of_no_winning_k` to extract the relation and acyclic half-cover from an election profile lacking a winning committee, while the reverse direction applies `condorcet_acyclic_cover_no_winning_k` to construct such an election profile from the relational data.
The equivalence reduces to proving each implication separately.
Splitting the bidirectional equivalence with `constructor` yields two independent subgoals: the forward implication and the reverse implication.
constructorAn election profile with no Condorcet winning committee of size at most k implies the existence of an acyclic half-cover relation.
Assuming an election profile P on m candidates with no Condorcet winning set of size at most k, the lemma `condorcet_acyclic_half_cover_of_no_winning_k` directly constructs the candidate count q, relation R, and acyclic half-cover family U satisfying the three relational conditions.
uses
condorcet_acyclic_half_cover_of_no_winning_k· rintro ⟨m,P,hP⟩ exact condorcet_acyclic_half_cover_of_no_winning_k n m k P hPConversely, an acyclic half-cover relation implies the existence of an election profile with no Condorcet winning committee of size at most k.
Given a relation R on q elements with outside common predecessors for sets of size at most k and an acyclic half-cover U, the lemma `condorcet_acyclic_cover_no_winning_k` constructs an n-voter election profile P on q candidates where no committee of size at most k is winning. Providing q and P closes the reverse goal.
uses
condorcet_acyclic_cover_no_winning_k· rintro ⟨q,R,U,hroot,hacyclic,hhalf⟩ obtain ⟨P,hP⟩ := condorcet_acyclic_cover_no_winning_k n q k R U hroot hacyclic hhalf exact ⟨q,P,hP⟩
condorcet_acyclic_half_cover_of_no_winning_k- If an n-voter election on m candidates has no Condorcet winning committee of size at most k, then there exists a finite relation on q elements where every subset of size at most k has an outside common predecessor, and an n-family of induced acyclic subsets covering each vertex at least half the time.
condorcet_acyclic_cover_no_winning_k- If a relation on m elements has outside common predecessors for all subsets of size at most k and admits an n-family of induced acyclic subsets covering each vertex at least half the time, then there exists an n-voter election profile on m candidates in which no committee of size at most k is Condorcet winning.
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 Finsetopen scoped BigOperatorsset_option maxHeartbeats 4000000set_option maxRecDepth 10000theorem condorcet_failure_k_iff_acyclic_half_cover (n k : ℕ) : (∃ (m : ℕ) (P : Fin n → Equiv.Perm (Fin m)), ∀ S : Finset (Fin m), S.card ≤ k → ¬is_condorcet_winning_set P S) ↔ (∃ (q : ℕ) (R : Fin q → Fin q → Prop) (U : Fin n → Finset (Fin q)), (∀ J : Finset (Fin q), J.card ≤ k → ∃ a, a∉J ∧ ∀ b∈J, R a b) ∧ (∀ v, WellFounded (fun a b : {a : Fin q // a∈U v} => R a.val b.val)) ∧ (∀ a, n ≤ 2*(univ.filter fun v => a∈U v).card)) := by constructor · rintro ⟨m,P,hP⟩ exact condorcet_acyclic_half_cover_of_no_winning_k n m k P hP · rintro ⟨q,R,U,hroot,hacyclic,hhalf⟩ obtain ⟨P,hP⟩ := condorcet_acyclic_cover_no_winning_k n q k R U hroot hacyclic hhalf exact ⟨q,P,hP⟩