AFTD Auto-Formalizing Theoretical Domains

condorcet_winning_set_of_top_choice_majority

theoremverified

Any candidate set S whose complement contains the top choice of strictly fewer than n/2 voters (i.e. S contains the top choices of a strict majority of voters) is a Condorcet winning set.

Statement

theorem condorcet_winning_set_of_top_choice_majority {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m))
    (hm : 0 < m) (S : Finset (Fin m))
    (hS : 2 * (Finset.univ.filter fun v => (P v).symm ⟨0, hm⟩ ∉ S).card < n) :
    is_condorcet_winning_set P S
Source
step towards condorcet_dimension_le_three
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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…
  • outside_voters_subset_top_choices_complFor any candidate set S and candidate x, any voter who ranks x strictly above every member of S has their top-choice candidate outside S.
Used by 1

The proof, explained

To prove that S is a Condorcet winning set, we must show that for any candidate a ∉ S, strictly fewer than n/2 voters prefer a to every member of S. Any voter who prefers a over every candidate in S cannot have their top-ranked candidate in S, meaning such voters are a subset of those whose top choice lies outside S. Since by assumption strictly fewer than n/2 voters have their top choice outside S, the number of voters preferring a to all of S is also strictly less than n/2.

  1. To show that S is a Condorcet winning set, it suffices to show that for any candidate a ∉ S, strictly fewer than n/2 voters prefer a to every candidate in S.

    Unfolding the definition of is_condorcet_winning_set, we introduce an arbitrary candidate a and the assumption _ha that a ∉ S. The goal becomes showing that 2 * |{v | ∀ b ∈ S, P v a < P v b}| < n.

    line 6

      intro a _ha
  2. The number of voters who prefer a to every candidate in S is at most the number of voters whose top choice is outside S.

    By outside_voters_subset_top_choices_compl, any voter who ranks a ahead of all elements of S cannot have their top choice in S, so the set of such voters is a subset of {v | (P v).symm ⟨0, hm⟩ ∉ S}. Applying Finset.card_le_card then establishes that the cardinality of the former set is at most the cardinality of the latter.

    lines 7–8

    uses outside_voters_subset_top_choices_compl, Finset.card_le_card

      have hsub := outside_voters_subset_top_choices_compl P S a hm
      have hcard := Finset.card_le_card hsub
  3. Twice the number of voters preferring a to all of S is strictly less than n, completing the proof.

    The hypothesis hS guarantees that 2 * |{v | (P v).symm ⟨0, hm⟩ ∉ S}| < n. Combining this with the cardinality inequality hcard via linear integer arithmetic (omega) closes the goal 2 * |{v | ∀ b ∈ S, P v a < P v b}| < n.

    line 9

      omega
outside_voters_subset_top_choices_compl
The set of voters who strictly prefer candidate x to every candidate in S is a subset of the voters whose top choice is not in S.
Finset.card_le_card
If a finite set s is a subset of a finite set t, then the cardinality of s is at most the cardinality of t.

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

/-- A candidate set containing the top choice of a strict majority of voters is a Condorcet winning set. -/theorem condorcet_winning_set_of_top_choice_majority {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m))    (hm : 0 < m) (S : Finset (Fin m))    (hS : 2 * (Finset.univ.filter fun v => (P v).symm ⟨0, hm⟩ ∉ S).card < n) :    is_condorcet_winning_set P S := by  intro a _ha  have hsub := outside_voters_subset_top_choices_compl P S a hm  have hcard := Finset.card_le_card hsub  omega
See it in the graphDiscuss this resultChallenge it