condorcet_winning_set_univ
The set of all candidates is a Condorcet winning set.
Statement
theorem condorcet_winning_set_univ {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m)) :
is_condorcet_winning_set P Finset.univ- Source
- sanity check of is_condorcet_winning_set
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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…
- Used by 2
- condorcet_dimension_le_two_of_le_threeEvery election with at most three candidates and at least one voter has a Condorcet winning set of at most two candidates.
- condorcet_dimension_le_three_of_le_fourEvery election with at most four candidates (and at least one voter) has a Condorcet winning set of at most three candidates: drop a…
The proof, explained
To show that the universal set of all candidates is a Condorcet winning set, we must show that any candidate outside it satisfies a pairwise condition against the set. However, every candidate belongs to the universal set by definition. Thus, the condition that a candidate lies outside the set is impossible, and the theorem holds vacuously.
The universal set of candidates satisfies the Condorcet winning set condition.
By definition, a set of candidates $S$ is a Condorcet winning set if every candidate $a \\notin S$ satisfies a certain pairwise majority condition. Supposing there were a candidate $a$ outside the universal set (the hypothesis $ha : a \\notin \\mathrm{univ}$), this directly contradicts the fact that every candidate belongs to the universal set by `Finset.mem_univ`. The claim therefore holds vacuously.
uses
Finset.mem_univintro a ha; exact absurd (Finset.mem_univ a) ha
Finset.mem_univ- Every element of a finite type belongs to the universal set `Finset.univ`.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem condorcet_winning_set_univ {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m)) : is_condorcet_winning_set P Finset.univ := by intro a ha; exact absurd (Finset.mem_univ a) ha