condorcet_paradox
The Condorcet paradox: there exists a preference profile of 3 voters over 3 alternatives, where each voter has a strict linear order of preferences, such that no alternative is a Condorcet winner.
Statement
theorem condorcet_paradox : ∃ (P : Fin 3 → Fin 3 → Fin 3 → Prop) (_ : ∀ v, DecidableRel (P v)), (∀ v, IsStrictTotalOrder (Fin 3) (P v)) ∧ ∀ x : Fin 3, ¬ condorcet_winner P x
- Formalizes
- Condorcet 1785, Essai sur l'application de l'analyse à la probabilité des décisions rendues à la pluralité des voix
- Verified
- 08 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- condorcet_winnerIn a profile of preferences P where a finite set of voters V have pairwise preferences over alternatives A, an alternative x : A is a…
Read back from the Lean
There exists a preference profile $P : \text{Fin } 3 \to \text{Fin } 3 \to \text{Fin } 3 \to \text{Prop}$ (representing binary preferences of 3 voters over 3 alternatives) with decidable relations for each voter, such that: 1. For every voter $v \in \text{Fin } 3$, $P(v)$ is a strict total order on $\text{Fin } 3$. 2. For every alternative $x \in \text{Fin } 3$, $x$ is not a Condorcet winner under $P$.
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 Condorcet paradox is demonstrated by constructing an explicit cyclic preference profile for 3 voters and 3 alternatives, where voter 0 prefers 0 > 1 > 2, voter 1 prefers 1 > 2 > 0, and voter 2 prefers 2 > 0 > 1. Each voter's preference is a strict total order induced by scoring, verified by exhaustive computation on the finite domain Fin 3. Pairwise majority votes form a cycle (0 beats 1, 1 beats 2, 2 beats 0), so no alternative defeats all others, meaning there is no Condorcet winner.
For each voter v, the preference relation between any two alternatives is decidable.
By unfolding the definition of the preference relation, deciding whether voter v prefers x to y reduces to checking whether the score of x is strictly greater than the score of y. Since the scores are natural numbers, this comparison is decidable by typeclass resolution.
uses
condorcet_paradox_prefintro x y unfold condorcet_paradox_pref infer_instance
Each voter's preference relation is trichotomous. automation
Reverting voter v yields a universally quantified statement over the finite domain Fin 3: for any voter and any two alternatives a and b, if a is not preferred to b and b is not preferred to a, then a = b. Since the domain is finite and the relation is decidable, Lean's decision procedure checks all cases by computation.
revert v decideEach voter's preference relation is irreflexive. automation
Reverting voter v leaves the claim that no voter prefers an alternative to itself. Since there are only 3 voters and 3 alternatives, the decision procedure verifies this by checking all 9 cases.
revert v decideEach voter's preference relation is transitive. automation
Reverting voter v yields the transitivity claim for all triples of alternatives. The decision procedure verifies all 3 × 3 × 3 × 3 = 81 combinations by exhaustive computation.
revert v decideNo alternative is a Condorcet winner under this preference profile. automation
Assume for contradiction that some alternative x is a Condorcet winner. Unfolding the definition, this means x wins the majority vote against every other alternative y. Reverting x and this hypothesis, the decision procedure exhaustively checks each candidate and determines that each candidate loses pairwise to another candidate (0 loses to 2, 1 loses to 0, and 2 loses to 1), deriving a contradiction.
uses
condorcet_winnerintro h unfold condorcet_winner at h revert x h decide
There exists a preference profile of 3 voters over 3 alternatives with strict total orders having no Condorcet winner.
The existential claim is witnessed by the cyclic preference relation condorcet_paradox_pref, together with its decidability instance condorcet_paradox_decidable_rel, the strict total order proof condorcet_paradox_strict_order, and the theorem condorcet_paradox_no_winner showing that no candidate wins.
uses
condorcet_paradox_pref,condorcet_paradox_decidable_rel,condorcet_paradox_strict_order,condorcet_paradox_no_winnerrefine ⟨condorcet_paradox_pref, condorcet_paradox_decidable_rel, condorcet_paradox_strict_order, condorcet_paradox_no_winner⟩
condorcet_paradox_pref- The preference relation for voter v, where v prefers x to y iff v assigns a higher score to x than to y.
condorcet_paradox_decidable_rel- Proof that condorcet_paradox_pref v is decidable for all alternatives x and y.
condorcet_paradox_strict_order- Proof that condorcet_paradox_pref v is a strict total order for every voter v.
condorcet_paradox_no_winner- Proof that no alternative x is a Condorcet winner under condorcet_paradox_pref.
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.
def condorcet_paradox_score : Fin 3 → Fin 3 → ℕ | 0, 0 => 2 | 0, 1 => 1 | 0, 2 => 0 | 1, 1 => 2 | 1, 2 => 1 | 1, 0 => 0 | 2, 2 => 2 | 2, 0 => 1 | 2, 1 => 0def condorcet_paradox_pref (v : Fin 3) (x y : Fin 3) : Prop := condorcet_paradox_score v x > condorcet_paradox_score v yinstance condorcet_paradox_decidable_rel (v : Fin 3) : DecidableRel (condorcet_paradox_pref v) := by intro x y unfold condorcet_paradox_pref infer_instancetheorem condorcet_paradox_strict_order (v : Fin 3) : IsStrictTotalOrder (Fin 3) (condorcet_paradox_pref v) where trichotomous := by revert v decide irrefl := by revert v decide trans := by revert v decidetheorem condorcet_paradox_no_winner (x : Fin 3) : ¬ condorcet_winner condorcet_paradox_pref x := by intro h unfold condorcet_winner at h revert x h decide/-- The Condorcet paradox: there exists an election with 3 voters and 3 candidates with strict linear preferences admitting no Condorcet winner. -/theorem condorcet_paradox : ∃ (P : Fin 3 → Fin 3 → Fin 3 → Prop) (_ : ∀ v, DecidableRel (P v)), (∀ v, IsStrictTotalOrder (Fin 3) (P v)) ∧ ∀ x : Fin 3, ¬ condorcet_winner P x := by refine ⟨condorcet_paradox_pref, condorcet_paradox_decidable_rel, condorcet_paradox_strict_order, condorcet_paradox_no_winner⟩