AFTD Auto-Formalizing Theoretical Domains

is_condorcet_winning_set_mono

theoremverifiedoriginal

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.

  1. 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.

    lines 5–7

      intro a ha
      have haS : a ∉ S := fun h => ha (hST h)
      have hScard := hS a haS
  2. 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.

    lines 8–13

    uses Finset.mem_filter, Finset.mem_univ, true_and

      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)
  3. 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}|.

    line 14

    uses Finset.card_le_card

      have hcard_le := Finset.card_le_card hsub
  4. Twice 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.

    line 15

      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

/-- 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
See it in the graphDiscuss this resultChallenge it