is_condorcet_winning_set_mono
Condorcet winning sets are upward closed: if S is a Condorcet winning set and S is a subset of T, then T is also a Condorcet winning set.
Statement
theorem is_condorcet_winning_set_mono {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m))
{S T : Finset (Fin m)} (hS : is_condorcet_winning_set P S) (hST : S ⊆ T) :
is_condorcet_winning_set P T- Related work
- folklore
- Verified
- 20 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…
Read back from the Lean
For any natural numbers $n$ and $m$, any profile of voter preferences $P : \text{Fin } n \to \text{Equiv.Perm}(\text{Fin } m)$, and any subsets of alternatives $S, T \subseteq \text{Fin } m$, if $S$ is a Condorcet winning set with respect to $P$ and $S \subseteq T$, then $T$ is also a Condorcet winning set with respect to $P$.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To prove that any superset T of a Condorcet winning set S is also a Condorcet winning set, consider any candidate a ∉ T. Since S ⊆ T, candidate a is also not in S, so by the Condorcet winning property for S fewer than n / 2 voters prefer a to all of S. Because any voter who prefers a to all candidates in T must also prefer a to all candidates in S, the voters favoring a over T form a subset of those favoring a over S; their count is thus at most that for S, and hence strictly less than n / 2.
For any candidate a ∉ T, candidate a is also not in S, and fewer than n / 2 voters prefer a to every candidate in S.
To show that T is a Condorcet winning set, fix any candidate a ∉ T. Because S ⊆ T, candidate a cannot belong to S either. Applying the definition of a Condorcet winning set for S to a ∉ S yields the inequality 2 * |{v | ∀ b ∈ S, P v a < P v b}| < n.
intro a ha have haS : a ∉ S := fun h => ha (hST h) have hScard := hS a haS
The set of voters who prefer a to every candidate in T is a subset of the set of voters who prefer a to every candidate in S.
Take an arbitrary voter v who prefers candidate a to every candidate in T. Simplifying the membership condition in the filtered universal set using `Finset.mem_filter`, `Finset.mem_univ`, and `true_and`, this means that v prefers a to b for all b ∈ T. Since S ⊆ T, any b ∈ S is also in T, so v in particular prefers a to every b ∈ S. Therefore, v belongs to the corresponding set of voters for S.
uses
Finset.mem_filter,Finset.mem_univ,true_andhave hsub : (Finset.univ.filter fun v => ∀ b ∈ T, P v a < P v b) ⊆ (Finset.univ.filter fun v => ∀ b ∈ S, P v a < P v b) := by intro v hv simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hv ⊢ intro b hb exact hv b (hST hb)
The number of voters preferring a to all of T is at most the number of voters preferring a to all of S.
Applying `Finset.card_le_card` to the subset inclusion established in the previous step gives |{v | ∀ b ∈ T, P v a < P v b}| ≤ |{v | ∀ b ∈ S, P v a < P v b}|.
uses
Finset.card_le_cardhave hcard_le := Finset.card_le_card hsubTwice the number of voters preferring a to all of T is strictly less than n, concluding that T is a Condorcet winning set.
Combining the cardinality bound |V_T| ≤ |V_S| with the strict inequality 2 * |V_S| < n, linear integer arithmetic (`linarith`) immediately yields 2 * |V_T| < n.
linarith
Finset.mem_filter- An element belongs to `Finset.filter p s` if and only if it belongs to `s` and satisfies `p`.
Finset.mem_univ- Every element of a finite type belongs to `Finset.univ`.
true_and- For any proposition `p`, the conjunction `True ∧ p` is equivalent to `p`.
Finset.card_le_card- If `s ⊆ t` for finite sets `s` and `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
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.
/-- Monotonicity of Condorcet winning sets: any superset of a Condorcet winning set is also a Condorcet winning set. -/theorem is_condorcet_winning_set_mono {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m)) {S T : Finset (Fin m)} (hS : is_condorcet_winning_set P S) (hST : S ⊆ T) : is_condorcet_winning_set P T := by intro a ha have haS : a ∉ S := fun h => ha (hST h) have hScard := hS a haS have hsub : (Finset.univ.filter fun v => ∀ b ∈ T, P v a < P v b) ⊆ (Finset.univ.filter fun v => ∀ b ∈ S, P v a < P v b) := by intro v hv simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hv ⊢ intro b hb exact hv b (hST hb) have hcard_le := Finset.card_le_card hsub linarith