AFTD Auto-Formalizing Theoretical Domains

condorcet_winning_of_pairwise_dominated

theoremverified

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.

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

    lines 6–7

      intro a ha
      obtain ⟨b, hbS, hb⟩ := h a ha
  2. 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$.

    lines 8–12

    uses Finset.mem_filter, Finset.mem_univ, true_and

      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
  3. 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$.

    lines 13–14

    uses Finset.card_le_card

      have := 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

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

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