AFTD Auto-Formalizing Theoretical Domains

condorcet_paradox

theoremverifiedformalization

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.

  1. 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.

    lines 17–19

    uses condorcet_paradox_pref

      intro x y
      unfold condorcet_paradox_pref
      infer_instance
  2. 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.

    lines 24–25

        revert v
        decide
  3. Each 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.

    lines 27–28

        revert v
        decide
  4. Each 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.

    lines 30–31

        revert v
        decide
  5. No 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.

    lines 35–38

    uses condorcet_winner

      intro h
      unfold condorcet_winner at h
      revert x h
      decide
  6. 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.

    lines 44–45

    uses condorcet_paradox_pref, condorcet_paradox_decidable_rel, condorcet_paradox_strict_order, condorcet_paradox_no_winner

      refine ⟨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

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⟩
See it in the graphDiscuss this resultChallenge it