AFTD Auto-Formalizing Theoretical Domains

condorcet_dimension_le_two_of_le_three

theoremverifiedoriginal

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

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.

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

    lines 5–7

    uses Nat.lt_or_ge, condorcet_winning_set_univ

      classical
      rcases Nat.lt_or_ge m 3 with hm2 | hm3
      · exact ⟨Finset.univ, by simp; omega, condorcet_winning_set_univ P⟩
  2. 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.

    line 8

      obtain rfl : m = 3 := by omega
  3. 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`).

    lines 9–18

    uses Function.onFun, Finset.disjoint_left, Finset.mem_filter, Finset.mem_erase.2, Ne.symm, Finset.mem_univ, lt_irrefl

      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 _)
  4. 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`).

    lines 19–21

    uses Finset.card_biUnion, Finset.card_le_univ

      have hsum : ∑ a, (top a).card ≤ n := by
        rw [← Finset.card_biUnion hdisj]
        exact (Finset.card_le_univ _).trans (by simp)
  5. 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`).

    lines 22–28

    uses Finset.sum_le_sum, Finset.mul_sum, Finset.sum_const, Finset.card_univ, Fintype.card_fin, smul_eq_mul

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

    lines 29–32

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

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

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