condorcet_winning_family_of_ordering_certificates
If every outsider selector on a finite committee family admits nonnegative integer weights such that every strict ranking satisfies claims of strictly less than half the total weight, every positive finite electorate has a Condorcet winning committee in that family. The universal certificate-existence hypothesis is explicit and unresolved for all triples.
Statement
theorem condorcet_winning_family_of_ordering_certificates (m q : ℕ) (S : Fin q → Finset (Fin m)) (hcert : ∀ f : Fin q → Fin m, (∀ i, f i ∉ S i) → ∃ w : Fin q → ℕ, ∀ σ : Equiv.Perm (Fin m), 2*(∑ i, if ∀ c ∈ S i, σ (f i) < σ c then w i else 0) < ∑ i, w i) : ∀ (n : ℕ) (hn : 0 < n) (P : Fin n → Equiv.Perm (Fin m)), ∃ i, is_condorcet_winning_set P (S i)
- Source
- Structural helpers for OP-19, following the strict definition in Social Choice and Welfare44(3):493-517 (2015), https://www.lamsade.dauphine.fr/~lang/papers/els15.pdf , and the selector/ordering framework in arXiv:2604.19851v2. No new Condorcet dimension bound or research advance is claimed.
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- condorcet_ordering_certificate_excludes_common_obstructionFor any finite family of challenger claims with nonnegative integer weights, if in every strict ranking their total satisfied weight is…
- 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…
- Used by 1
- condorcet_winning_family_of_subset_potentialsIf every outside-challenger selector for a finite committee family has nonnegative integer weights and a subset potential satisfying the…
The proof, explained
The theorem is proved by contradiction: assuming no committee S_i is Condorcet winning, every committee S_i admits an outsider candidate preferred to the entire committee by at least half of the voters. By the axiom of choice, these choices define an outsider selector function f. Applying the hypothesis to f provides a certificate weight vector w, which by an auxiliary lemma guarantees that some committee S_i is preferred to f(i) by more than half the voters. This contradicts the choice of f having majority support against S_i.
Assume for contradiction that no committee in the family is a Condorcet winning set.
We fix an electorate of size n > 0 with preference profile P, enable classical logic, and assume for contradiction that no index i gives a Condorcet winning set S_i.
classical intro n hn P by_contra hnone
Every committee S_i admits an outside candidate who defeats it with at least half of the vote.
Fix an arbitrary committee S_i. Since it is not a Condorcet winning set, we unfold the definition of `is_condorcet_winning_set` and push negations to find an outsider a ∉ S_i such that at least half the voters (n ≤ 2 * |{v | ∀ c ∈ S_i, P_v(a) < P_v(c)}|) prefer a to every member of S_i.
uses
is_condorcet_winning_sethave hbad : ∀ i, ∃ a : Fin m, a ∉ S i ∧ n ≤ 2*(univ.filter fun v => ∀ c ∈ S i, P v a < P v c).card := by intro i have hi : ¬is_condorcet_winning_set P (S i) := fun h => hnone ⟨i,h⟩ unfold is_condorcet_winning_set at hi push_neg at hi exact hi
There exists an outsider selector f choosing for each committee an outsider with majority support against it.
Using the axiom of choice (`choose`), we obtain a selector function f : Fin q → Fin m such that for each i, f(i) ∉ S_i and at least half the electorate prefers f(i) to all elements of S_i.
choose f hf hmaj using hbad
There exists a weight certificate w for the selector f.
Because f(i) ∉ S_i holds for every i, the hypothesis `hcert` supplies a certificate weight vector w : Fin q → ℕ satisfying the sub-majority weight inequality for every ranking.
obtain ⟨w,hw⟩ := hcert f hfThere exists some committee S_i against which strictly fewer than half the voters prefer the outsider f(i).
Applying `condorcet_ordering_certificate_excludes_common_obstruction` to the profile P, selector f, and certificate weights w produces an index i for which strictly fewer than half the voters prefer f(i) to all candidates in S_i.
uses
condorcet_ordering_certificate_excludes_common_obstructionobtain ⟨i,hi⟩ := condorcet_ordering_certificate_excludes_common_obstruction n m q hn P S f w hwContradiction.
For the committee S_i identified by the certificate lemma, the outsider f(i) has both weak majority support (at least n/2 voters prefer f(i) to all of S_i) by definition of f, and strict minority support (strictly fewer than n/2 voters prefer f(i) to all of S_i) by the certificate lemma. Linear integer arithmetic (`omega`) derives False from this contradiction.
have := hmaj i omega
is_condorcet_winning_set- A committee S is a Condorcet winning set for an electorate profile P if for every candidate a outside S, strictly fewer than half the voters rank a ahead of all members of S.
condorcet_ordering_certificate_excludes_common_obstruction- If nonnegative weights w satisfy the ordering certificate condition for an outsider selector f, then in any positive finite electorate profile P there exists some committee S_i such that strictly fewer than half of the voters prefer f(i) to every member of S_i.
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 2000000set_option maxRecDepth 10000theorem condorcet_winning_family_of_ordering_certificates (m q : ℕ) (S : Fin q → Finset (Fin m)) (hcert : ∀ f : Fin q → Fin m, (∀ i, f i ∉ S i) → ∃ w : Fin q → ℕ, ∀ σ : Equiv.Perm (Fin m), 2*(∑ i, if ∀ c ∈ S i, σ (f i) < σ c then w i else 0) < ∑ i, w i) : ∀ (n : ℕ) (hn : 0 < n) (P : Fin n → Equiv.Perm (Fin m)), ∃ i, is_condorcet_winning_set P (S i) := by classical intro n hn P by_contra hnone have hbad : ∀ i, ∃ a : Fin m, a ∉ S i ∧ n ≤ 2*(univ.filter fun v => ∀ c ∈ S i, P v a < P v c).card := by intro i have hi : ¬is_condorcet_winning_set P (S i) := fun h => hnone ⟨i,h⟩ unfold is_condorcet_winning_set at hi push_neg at hi exact hi choose f hf hmaj using hbad obtain ⟨w,hw⟩ := hcert f hf obtain ⟨i,hi⟩ := condorcet_ordering_certificate_excludes_common_obstruction n m q hn P S f w hw have := hmaj i omega