condorcet_winning_of_pairwise_dominated
If every candidate outside S is pairwise strictly majority-defeated by some candidate in S, then S is a Condorcet winning set.
Statement
theorem condorcet_winning_of_pairwise_dominated {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m)) (S : Finset (Fin m)) (h : ∀ a, a ∉ S → ∃ b ∈ S, 2 * (Finset.univ.filter fun v => P v a < P v b).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 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…
The proof, explained
To prove that $S$ is a Condorcet winning set, we must show that for any candidate $a \notin S$, strictly fewer than half of all voters prefer $a$ to every candidate in $S$. By hypothesis, there is some candidate $b \in S$ that defeats $a$ in a pairwise majority vote. Since any voter ranking $a$ ahead of all candidates in $S$ must in particular rank $a$ ahead of $b$, the former set of voters is contained in the latter, and the result follows immediately by comparing set cardinalities.
Fix an arbitrary candidate $a \notin S$, and obtain a candidate $b \in S$ that pairwise defeats $a$ by majority.
To show that $S$ is a Condorcet winning set, we consider an arbitrary candidate $a \notin S$. Applying the hypothesis $h$ to $a$ yields a candidate $b \in S$ such that fewer than $n/2$ voters prefer $a$ to $b$, that is, $2 \cdot |\{v \mid P(v)(a) < P(v)(b)\}| < n$.
intro a ha obtain ⟨b, hbS, hb⟩ := h a ha
The set of voters preferring $a$ to every candidate in $S$ is a subset of the voters preferring $a$ to $b$.
Let $v$ be a voter who prefers $a$ to every candidate $c \in S$. Simplifying the set filter conditions with `Finset.mem_filter`, `Finset.mem_univ`, and `true_and` reduces membership in the filtered universe to the defining property. Since $b \in S$, specializing $v$'s preference to $c = b$ immediately shows that $v$ prefers $a$ to $b$.
uses
Finset.mem_filter,Finset.mem_univ,true_andhave hsub : (Finset.univ.filter fun v => ∀ c ∈ S, P v a < P v c) ⊆ (Finset.univ.filter fun v => P v a < P v b) := by intro v hv simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hv ⊢ exact hv b hbS
Strictly fewer than half of the voters prefer $a$ to all candidates in $S$, concluding that $S$ is a Condorcet winning set.
By `Finset.card_le_card`, the cardinality of the subset is at most the cardinality of the superset. Since $2 \cdot |\{v \mid P(v)(a) < P(v)(b)\}| < n$, linear integer arithmetic (`omega`) proves that $2 \cdot |\{v \mid \forall c \in S, P(v)(a) < P(v)(c)\}| < n$.
uses
Finset.card_le_cardhave := Finset.card_le_card hsub omega
Finset.mem_filter- an element belongs to a filtered set if and only if it belongs to the base set and satisfies the predicate
Finset.mem_univ- every element of a finite type belongs to the universal finset `Finset.univ`
true_and- for any proposition $p$, the conjunction `True ∧ p` simplifies to $p$
Finset.card_le_card- if one finite set is a subset of another, its cardinality is at most that of the superset
- In the formalization, preferences are represented by permutations where smaller values indicate higher preference, so $P(v)(a) < P(v)(b)$ means that voter $v$ prefers candidate $a$ to candidate $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
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.
/-- If every candidate outside S is pairwise majority-defeated by some candidate in S, then S is a Condorcet winning set. -/theorem condorcet_winning_of_pairwise_dominated {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m)) (S : Finset (Fin m)) (h : ∀ a, a ∉ S → ∃ b ∈ S, 2 * (Finset.univ.filter fun v => P v a < P v b).card < n) : is_condorcet_winning_set P S := by intro a ha obtain ⟨b, hbS, hb⟩ := h a ha have hsub : (Finset.univ.filter fun v => ∀ c ∈ S, P v a < P v c) ⊆ (Finset.univ.filter fun v => P v a < P v b) := by intro v hv simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hv ⊢ exact hv b hbS have := Finset.card_le_card hsub omega