AFTD Auto-Formalizing Theoretical Domains

condorcet_dimension_le_three_of_voters_le_five

theoremverified

Every election with at most 5 voters (and at least 1 voter) has a Condorcet winning set of at most 3 candidates: selecting the top-choice candidate of each of the first min(n, 3) voters yields a winning set of size at most 3.

Statement

theorem condorcet_dimension_le_three_of_voters_le_five (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m))
    (hn : 0 < n) (hn5 : n ≤ 5) :
    ∃ S : Finset (Fin m), S.card ≤ 3 ∧ is_condorcet_winning_set P S
Source
step towards condorcet_dimension_le_three
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • condorcet_winning_set_of_top_choicesFor any election with at least one candidate, the set of top-choice candidates of any subset of voters V0 is a Condorcet winning set…
  • 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…

The proof, explained

The proof handles elections with at most 5 voters by taking the set S of top-choice candidates of the first min(n, 3) voters (or the empty set if there are no candidates). The size of S is at most min(n, 3) ≤ 3 by construction. By an established criterion (condorcet_winning_set_of_top_choices), these top choices form a Condorcet winning set whenever the unrepresented voters do not form a majority (2 * (n - |V₀|) < n), which holds for all 1 ≤ n ≤ 5 by finite case check.

  1. If there are no candidates (m = 0), the empty set is a Condorcet winning set of size at most 3.

    We split into cases on whether m = 0. When there are no candidates, S = ∅ has size 0 ≤ 3, and the condition for being a Condorcet winning set holds vacuously because there are no candidates outside S in Fin 0.

    lines 5–7

    uses is_condorcet_winning_set

      by_cases hm : m = 0
      · subst hm
        exact ⟨∅, by simp, by simp [is_condorcet_winning_set]⟩
  2. When m > 0, we choose candidate set S as the top choices of the first min(n, 3) voters.

    Since m ≠ 0, we have 0 < m by Nat.pos_of_ne_zero, so candidate 0 is well-defined. We define the voter subset V₀ = {v ∈ Fin n | v < 3} consisting of the first up to 3 voters, and propose S as the image of V₀ under each voter's top-choice candidate (P v)⁻¹(0). This leaves two goals: showing |S| ≤ 3 and that S is a Condorcet winning set.

    lines 8–9

    uses Nat.pos_of_ne_zero

      · have hm' : 0 < m := Nat.pos_of_ne_zero hm
        refine ⟨(Finset.univ.filter (fun v : Fin n => (v:ℕ) < 3)).image (fun v => (P v).symm ⟨0, hm'⟩), ?_, ?_⟩
  3. The proposed set S has cardinality at most 3.

    By Finset.card_image_le, the size of S is bounded by the cardinality of V₀ = {v ∈ Fin n | v < 3}. Since 1 ≤ n ≤ 5, exhaustive case analysis on n shows that |V₀| = min(n, 3) ≤ 3 in every case.

    lines 10–11

    uses Finset.card_image_le

        · calc _ ≤ (Finset.univ.filter (fun v : Fin n => (v:ℕ) < 3)).card := Finset.card_image_le
            _ ≤ 3 := by interval_cases n <;> decide
  4. The proposed set S is a Condorcet winning set.

    By condorcet_winning_set_of_top_choices, the top choices of voters V₀ form a Condorcet winning set if the remaining voters cannot form a majority, meaning 2 * (n - |V₀|) < n. We verify this inequality for each n ∈ {1, 2, 3, 4, 5} by case exhaustion: for n ≤ 3 the difference is 0; for n = 4 we have 2*(4-3) = 2 < 4; and for n = 5 we have 2*(5-3) = 4 < 5.

    lines 12–13

    uses condorcet_winning_set_of_top_choices

        · refine condorcet_winning_set_of_top_choices P hm' _ ?_
          interval_cases n <;> decide
is_condorcet_winning_set
A candidate set S is a Condorcet winning set if every candidate outside S is strictly preferred to all candidates in S by strictly less than half of the voters.
Nat.pos_of_ne_zero
A natural number is strictly positive if it is non-zero.
Finset.card_image_le
The cardinality of the image of a finite set under any function is at most the cardinality of the domain set.
condorcet_winning_set_of_top_choices
The set of top-choice candidates of a subset of voters V₀ is a Condorcet winning set provided that the remaining voters do not form a majority, that is, 2 * (n - |V₀|) < 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

/-- Every election with at most 5 voters and at least 1 voter has a Condorcet winning set of at most 3 candidates. -/theorem condorcet_dimension_le_three_of_voters_le_five (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m))    (hn : 0 < n) (hn5 : n ≤ 5) :    ∃ S : Finset (Fin m), S.card ≤ 3 ∧ is_condorcet_winning_set P S := by  by_cases hm : m = 0  · subst hm    exact ⟨∅, by simp, by simp [is_condorcet_winning_set]⟩  · have hm' : 0 < m := Nat.pos_of_ne_zero hm    refine ⟨(Finset.univ.filter (fun v : Fin n => (v:ℕ) < 3)).image (fun v => (P v).symm ⟨0, hm'⟩), ?_, ?_⟩    · calc _ ≤ (Finset.univ.filter (fun v : Fin n => (v:ℕ) < 3)).card := Finset.card_image_le        _ ≤ 3 := by interval_cases n <;> decide    · refine condorcet_winning_set_of_top_choices P hm' _ ?_      interval_cases n <;> decide
See it in the graphDiscuss this resultChallenge it