condorcet_dimension_le_two_of_le_three
Every election with at most three candidates and at least one voter has a Condorcet winning set of at most two candidates.
Statement
theorem condorcet_dimension_le_two_of_le_three (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m))
(hn : 0 < n) (hm : m ≤ 3) :
∃ S : Finset (Fin m), S.card ≤ 2 ∧ is_condorcet_winning_set P S- Related work
- folklore
- Verified
- 20 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
- condorcet_winning_set_univThe set of all candidates is a Condorcet winning set.
Read back from the Lean
For any natural numbers $n$ and $m$, and any profile $P : \mathrm{Fin}\ n \to \mathrm{Equiv.Perm}(\mathrm{Fin}\ m)$ assigning each voter $v \in \mathrm{Fin}\ n$ a permutation of alternatives $\mathrm{Fin}\ m$, if $n > 0$ and $m \le 3$, then there exists a subset $S \subseteq \mathrm{Fin}\ m$ of size at most 2 such that $S$ is a Condorcet winning set under $P$ (i.e., is_condorcet_winning_set P S).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof splits on whether the candidate count m is strictly less than 3 or equal to 3. If m < 3, the universal set of all candidates already has size at most 2 and vacuously forms a Condorcet winning set. If m = 3, we define the sets of voters who rank each candidate first; since voter preferences are strict, these three sets are pairwise disjoint and their sizes sum to at most n. Because n > 0, an averaging argument shows that at least one candidate a is ranked first by strictly fewer than n/2 voters. Removing candidate a leaves a two-candidate set S = univ \ {a}, which is a Condorcet winning set because a is the sole candidate outside S and cannot beat all of S with a majority.
If m < 3, the entire set of candidates is a Condorcet winning set of size at most 2.
Under classical logic, we split on whether m < 3 or m ≥ 3 (`Nat.lt_or_ge`). If m < 3, the universal set of candidates has size at most 2 (`Finset.univ`), and the full candidate set is always a Condorcet winning set (`condorcet_winning_set_univ`).
uses
Nat.lt_or_ge,condorcet_winning_set_univclassical rcases Nat.lt_or_ge m 3 with hm2 | hm3 · exact ⟨Finset.univ, by simp; omega, condorcet_winning_set_univ P⟩
In the remaining case, m = 3.
From the branch hypothesis m ≥ 3 and the global assumption m ≤ 3, linear integer arithmetic (`omega`) establishes that m = 3, which is substituted into the goal.
obtain rfl : m = 3 := by omega
The sets of voters who rank each candidate first are pairwise disjoint.
For each candidate a ∈ Fin 3, define `top a` to be the set of voters who rank a strictly ahead of every other candidate b ≠ a. To prove these sets are pairwise disjoint (`Function.onFun`, `Finset.disjoint_left`), suppose some voter v belongs to both `top a` and `top b` for a ≠ b. Then v ∈ `top a` implies P(v)(a) < P(v)(b) (`Finset.mem_filter`, `Finset.mem_erase.2`, `Ne.symm`, `Finset.mem_univ`), while v ∈ `top b` implies P(v)(b) < P(v)(a). By transitivity of <, this implies P(v)(a) < P(v)(a), contradicting the irreflexivity of strict order (`lt_irrefl`).
uses
Function.onFun,Finset.disjoint_left,Finset.mem_filter,Finset.mem_erase.2,Ne.symm,Finset.mem_univ,lt_irrefllet top : Fin 3 → Finset (Fin n) := fun a => Finset.univ.filter fun v => ∀ b ∈ Finset.univ.erase a, P v a < P v b have hdisj : (↑(Finset.univ : Finset (Fin 3)) : Set (Fin 3)).PairwiseDisjoint top := by intro a _ b _ hab rw [Function.onFun, Finset.disjoint_left] intro v hva hvb simp only [top, Finset.mem_filter] at hva hvb have h1 := hva.2 b (Finset.mem_erase.2 ⟨Ne.symm hab, Finset.mem_univ _⟩) have h2 := hvb.2 a (Finset.mem_erase.2 ⟨hab, Finset.mem_univ _⟩) exact absurd (h1.trans h2) (lt_irrefl _)
The sum of the numbers of voters ranking each candidate first is at most n.
Because the sets `top a` are pairwise disjoint, the sum of their cardinalities equals the cardinality of their disjoint union (`Finset.card_biUnion`). Since the union is a subset of the n voters, its cardinality is bounded by |Fin n| = n (`Finset.card_le_univ`).
uses
Finset.card_biUnion,Finset.card_le_univhave hsum : ∑ a, (top a).card ≤ n := by rw [← Finset.card_biUnion hdisj] exact (Finset.card_le_univ _).trans (by simp)
There exists a candidate who is ranked first by strictly fewer than n/2 voters.
Suppose for contradiction that every candidate a satisfies 2 * |top a| ≥ n. Summing this inequality over all three candidates (`Finset.sum_le_sum`) and factoring out the constant 2 (`Finset.mul_sum`) yields 3n ≤ 2 * ∑ a, |top a| (`Finset.sum_const`, `Finset.card_univ`, `Fintype.card_fin`, `smul_eq_mul`). Combined with ∑ a, |top a| ≤ n, this forces 3n ≤ 2n, which contradicts n > 0 by linear arithmetic (`omega`).
uses
Finset.sum_le_sum,Finset.mul_sum,Finset.sum_const,Finset.card_univ,Fintype.card_fin,smul_eq_mulobtain ⟨a, ha⟩ : ∃ a, 2 * (top a).card < n := by by_contra h push Not at h have h3 : ∑ _a : Fin 3, n ≤ ∑ a, 2 * (top a).card := Finset.sum_le_sum fun a _ => h a rw [← Finset.mul_sum] at h3 simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul] at h3 omega
Removing this candidate leaves a Condorcet winning set of at most two candidates.
Let a be the candidate with 2 * |top a| < n. We choose S to be all candidates except a (`Finset.univ.erase a`). Since there are 3 candidates in total, |S| = 2 ≤ 2. Any challenger x ∉ S must be a itself. The voters preferring x = a to all members of S are precisely those who rank a first among all candidates, which is the set `top a`. Since 2 * |top a| < n by the choice of a, no majority can defeat S, proving that S is a Condorcet winning set.
refine ⟨Finset.univ.erase a, by simp, fun x hx => ?_⟩ have : x = a := by simpa using hx subst this exact ha
Nat.lt_or_ge- For any natural numbers n and m, either n < m or n ≥ m.
condorcet_winning_set_univ- The set of all candidates is always a Condorcet winning set, as there are no candidates outside it.
Function.onFun- The composition of a binary relation with a function on each argument: `Function.onFun f g x y = f (g x) (g y)`.
Finset.disjoint_left- Two finite sets are disjoint if and only if no element of the first set belongs to the second set.
Finset.mem_filter- An element belongs to `Finset.filter p s` if and only if it belongs to s and satisfies the predicate p.
Finset.mem_erase.2- If a ≠ b and a ∈ s, then a belongs to s with b removed (`s.erase b`).
Ne.symm- Inequality is symmetric: if a ≠ b, then b ≠ a.
Finset.mem_univ- Every element of a finite type belongs to the universal finite set of that type.
lt_irrefl- Strict inequality is irreflexive: no element is strictly less than itself.
Finset.card_biUnion- The cardinality of a pairwise disjoint union of finite sets equals the sum of their individual cardinalities.
Finset.card_le_univ- The cardinality of any finite subset is at most the total cardinality of the ambient finite type.
Finset.sum_le_sum- If f(i) ≤ g(i) for all elements i in a finite set, then the sum of f(i) is at most the sum of g(i).
Finset.mul_sum- A constant factor distributes over a finite sum: `c * ∑ i, f i = ∑ i, c * f i`.
Finset.sum_const- The sum of a constant value over a finite set equals the cardinality of the set scalar-multiplied by the constant.
Finset.card_univ- The cardinality of the universal set of a finite type equals the cardinality of the type.
Fintype.card_fin- The finite type `Fin n` has cardinality n.
smul_eq_mul- Scalar multiplication on a semiring coincides with multiplication: `a • b = a * b`.
- In the definition of `is_condorcet_winning_set`, voter preferences are represented as permutations where a smaller value indicates a higher preference: `P v a < P v b` means voter `v` prefers candidate `a` over `b`.
- A set of candidates S is a Condorcet winning set if no outside candidate a ∉ S is strictly preferred to every member of S by at least half the voters (encoded by the inequality `2 * |{v | ∀ b ∈ S, P v a < P v b}| < n`).
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.
/-- Every election with at most three candidates and at least one voter has a Condorcet winning set of at most two candidates. -/theorem condorcet_dimension_le_two_of_le_three (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m)) (hn : 0 < n) (hm : m ≤ 3) : ∃ S : Finset (Fin m), S.card ≤ 2 ∧ is_condorcet_winning_set P S := by classical rcases Nat.lt_or_ge m 3 with hm2 | hm3 · exact ⟨Finset.univ, by simp; omega, condorcet_winning_set_univ P⟩ obtain rfl : m = 3 := by omega let top : Fin 3 → Finset (Fin n) := fun a => Finset.univ.filter fun v => ∀ b ∈ Finset.univ.erase a, P v a < P v b have hdisj : (↑(Finset.univ : Finset (Fin 3)) : Set (Fin 3)).PairwiseDisjoint top := by intro a _ b _ hab rw [Function.onFun, Finset.disjoint_left] intro v hva hvb simp only [top, Finset.mem_filter] at hva hvb have h1 := hva.2 b (Finset.mem_erase.2 ⟨Ne.symm hab, Finset.mem_univ _⟩) have h2 := hvb.2 a (Finset.mem_erase.2 ⟨hab, Finset.mem_univ _⟩) exact absurd (h1.trans h2) (lt_irrefl _) have hsum : ∑ a, (top a).card ≤ n := by rw [← Finset.card_biUnion hdisj] exact (Finset.card_le_univ _).trans (by simp) obtain ⟨a, ha⟩ : ∃ a, 2 * (top a).card < n := by by_contra h push Not at h have h3 : ∑ _a : Fin 3, n ≤ ∑ a, 2 * (top a).card := Finset.sum_le_sum fun a _ => h a rw [← Finset.mul_sum] at h3 simp only [Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul] at h3 omega refine ⟨Finset.univ.erase a, by simp, fun x hx => ?_⟩ have : x = a := by simpa using hx subst this exact ha