AFTD Auto-Formalizing Theoretical Domains

condorcet_dimension_le_three_of_le_five

theoremverified

Every election with at most 5 candidates (and at least 1 voter) has a Condorcet winning set of at most 3 candidates.

Statement

theorem condorcet_dimension_le_three_of_le_five (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m))
    (hn : 0 < n) (hm : m ≤ 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 4

The proof, explained

The proof splits into cases on the number of candidates m. For m ≤ 4, the claim holds by an earlier result. For m = 5, a helper theorem implies that if every 3-candidate subset had at most half the voters' top choices, there would have to be at least 6 candidates; hence some 3-candidate set S must contain the top choice of a strict majority of voters. Because a majority ranks a candidate in S first, no candidate outside S can beat all candidates in S by a majority, making S a Condorcet winning set.

  1. The theorem holds when there are at most 4 candidates.

    We perform a case split on whether m ≤ 4. If m ≤ 4, the result follows directly from the previously proved lemma condorcet_dimension_le_three_of_le_four.

    lines 5–6

    uses condorcet_dimension_le_three_of_le_four

      by_cases hm4 : m ≤ 4
      · exact condorcet_dimension_le_three_of_le_four n m P hn hm4
  2. In the remaining case, the candidate count satisfies 4 ≤ m and 0 < m.

    Since m ≤ 5 and the case m ≤ 4 has already been resolved, m must be 5, so in particular 4 ≤ m and m is positive.

    lines 7–8

      have hm_ge4 : 4 ≤ m := by omega
      have hm_pos : 0 < m := by omega
  3. It is false that every 3-candidate subset contains the top choice of at most half the voters.

    We proceed by contradiction: assuming every 3-candidate subset contains the top choice of at most n / 2 voters, condorcet_balanced_top_implies_six_le_candidates would force m ≥ 6. But m ≤ 5, giving an arithmetic contradiction.

    lines 9–13

    uses condorcet_balanced_top_implies_six_le_candidates

      have hbal : ¬ (∀ S : Finset (Fin m), S.card = 3 →
          2 * (Finset.univ.filter fun v => (P v).symm ⟨0, by omega⟩ ∈ S).card ≤ n) := by
        intro h
        have h6 := condorcet_balanced_top_implies_six_le_candidates n m P hn hm_ge4 h
        omega
  4. There exists a 3-candidate subset S whose members are the first choice of a strict majority of voters.

    Negating the universal statement yields a set S of 3 candidates such that 2 · |{v | top(v) ∈ S}| > n.

    lines 14–15

      push Not at hbal
      obtain ⟨S, hScard, hSgt⟩ := hbal
  5. The number of voters whose top choice is in S and those whose top choice is outside S sum to n.

    Partitioning the full voter set Fin n into those whose top choice is in S and those whose top choice is not via Finset.card_filter_add_card_filter_not, and simplifying using Finset.card_univ and Fintype.card_fin, gives an equality summing to n.

    lines 16–18

    uses Finset.card_filter_add_card_filter_not, Finset.card_univ, Fintype.card_fin

      have hpart := Finset.card_filter_add_card_filter_not
        (fun v => (P v).symm ⟨0, hm_pos⟩ ∈ S) (s := (Finset.univ : Finset (Fin n)))
      simp only [Finset.card_univ, Fintype.card_fin] at hpart
  6. Strictly fewer than half of the voters have their top choice outside S.

    Because strictly more than n / 2 voters have their top choice in S and the two groups sum to n, linear arithmetic (omega) establishes that 2 · |{v | top(v) ∉ S}| < n.

    lines 19–20

      have h_not : 2 * (Finset.univ.filter fun v => (P v).symm ⟨0, hm_pos⟩ ∉ S).card < n := by
        omega
  7. S is a Condorcet winning set of size at most 3.

    We provide S as the required witness. Its cardinality is 3 (hence ≤ 3), and because strictly fewer than half the voters have their top choice outside S, condorcet_winning_set_of_top_choice_majority guarantees that S is a Condorcet winning set.

    lines 21–22

    uses condorcet_winning_set_of_top_choice_majority

      refine ⟨S, by omega, ?_⟩
      exact condorcet_winning_set_of_top_choice_majority P hm_pos S h_not
condorcet_dimension_le_three_of_le_four
In an election with at least one voter and at most 4 candidates, there exists a Condorcet winning set of size at most 3.
condorcet_balanced_top_implies_six_le_candidates
In an election with at least one voter and at least 4 candidates, if every 3-candidate subset contains the first choice of at most half the voters, then there must be at least 6 candidates.
Finset.card_filter_add_card_filter_not
For any finite set and decidable predicate, the number of elements satisfying the predicate plus the number of elements satisfying its negation equals the cardinality of the set.
Finset.card_univ
The cardinality of the universal finset of a finite type is equal to the cardinality of that type.
Fintype.card_fin
The cardinality of the finite type Fin n is n.
condorcet_winning_set_of_top_choice_majority
If strictly fewer than half of the voters have their top choice outside a candidate set S, then S is a Condorcet winning set.

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 five candidates has a Condorcet winning set of size at most three. -/theorem condorcet_dimension_le_three_of_le_five (n m : ℕ) (P : Fin n → Equiv.Perm (Fin m))    (hn : 0 < n) (hm : m ≤ 5) :    ∃ S : Finset (Fin m), S.card ≤ 3 ∧ is_condorcet_winning_set P S := by  by_cases hm4 : m ≤ 4  · exact condorcet_dimension_le_three_of_le_four n m P hn hm4  have hm_ge4 : 4 ≤ m := by omega  have hm_pos : 0 < m := by omega  have hbal : ¬ (∀ S : Finset (Fin m), S.card = 3 →      2 * (Finset.univ.filter fun v => (P v).symm ⟨0, by omega⟩ ∈ S).card ≤ n) := by    intro h    have h6 := condorcet_balanced_top_implies_six_le_candidates n m P hn hm_ge4 h    omega  push Not at hbal  obtain ⟨S, hScard, hSgt⟩ := hbal  have hpart := Finset.card_filter_add_card_filter_not    (fun v => (P v).symm ⟨0, hm_pos⟩ ∈ S) (s := (Finset.univ : Finset (Fin n)))  simp only [Finset.card_univ, Fintype.card_fin] at hpart  have h_not : 2 * (Finset.univ.filter fun v => (P v).symm ⟨0, hm_pos⟩ ∉ S).card < n := by    omega  refine ⟨S, by omega, ?_⟩  exact condorcet_winning_set_of_top_choice_majority P hm_pos S h_not
See it in the graphDiscuss this resultChallenge it