AFTD Auto-Formalizing Theoretical Domains

condorcet_winning_set_of_bottom_three_majority

theoremverified

If S is a set of exactly three candidates and every candidate a outside S is ranked below all but at most two candidates by a strict majority of voters, then S is a Condorcet winning set.

Statement

theorem condorcet_winning_set_of_bottom_three_majority {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m))
    (S : Finset (Fin m)) (hS : S.card = 3)
    (h : ∀ a, a ∉ S → n < 2 * (Finset.univ.filter fun v =>
      (Finset.univ.filter fun c => P v a < P v c).card ≤ 2).card) :
    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 show that S is a Condorcet winning set, we must show that for any candidate a ∉ S, the set of voters bad who rank every candidate of S above a constitutes a strict minority, 2 * |bad| < n. For any voter in bad, all three candidates in S are ranked above a, so at least three candidates outrank a. However, the hypothesis guarantees a strict majority B of voters for whom at most two candidates outrank a, which makes bad and B disjoint. Since bad is disjoint from this majority B, their sizes satisfy |bad| + |B| ≤ n, which immediately implies 2 * |bad| < n.

  1. Fix an arbitrary candidate a ∉ S and define the voter sets B and bad.

    To show that S is a Condorcet winning set, we consider any candidate a not in S. We define B to be the set of voters v for whom at most two candidates c satisfy P(v)(a) < P(v)(c), and bad to be the set of voters v who rank every candidate b ∈ S above a, that is, P(v)(a) < P(v)(b) for all b ∈ S. By definition of a Condorcet winning set, it suffices to prove 2 * |bad| < n.

    lines 7–10

      intro a ha
      let B := Finset.univ.filter (fun v : Fin n =>
        (Finset.univ.filter fun c => P v a < P v c).card ≤ 2)
      let bad := Finset.univ.filter (fun v : Fin n => ∀ b ∈ S, P v a < P v b)
  2. The sets bad and B are disjoint.

    Using `Finset.disjoint_left`, we show that no voter v in bad can belong to B. For any v ∈ bad, every element b ∈ S satisfies P(v)(a) < P(v)(b), so S is a subset of the candidates ranked above a (`Finset.mem_filter`, `Finset.mem_univ`). By `Finset.card_le_card`, this implies that at least |S| = 3 candidates are ranked above a. However, any voter in B has at most 2 candidates ranked above a, which is an arithmetic contradiction 3 ≤ 2 resolved by `omega`.

    lines 11–22

    uses Finset.disjoint_left, Finset.mem_filter, Finset.mem_univ, Finset.card_le_card

      have h_disj : Disjoint bad B := by
        rw [Finset.disjoint_left]
        intro v hv
        rw [Finset.mem_filter] at hv ⊢
        intro ⟨_, h2⟩
        have h_sub : S ⊆ Finset.univ.filter (fun c => P v a < P v c) := by
          intro b hb
          rw [Finset.mem_filter]
          exact ⟨Finset.mem_univ _, hv.2 b hb⟩
        have h_le := Finset.card_le_card h_sub
        rw [hS] at h_le
        omega
  3. |bad| + |B| ≤ n.

    Since bad and B are disjoint, the sum of their sizes equals the size of their union by `Finset.card_union_of_disjoint`. Because their union is a subset of the universe of all n voters (`Finset.card_le_univ` and `Fintype.card_fin`), its cardinality cannot exceed n.

    lines 23–28

    uses Finset.card_union_of_disjoint, Finset.card_le_univ, Fintype.card_fin

      have h_card_add : bad.card + B.card ≤ n := by
        have h_union : bad.card + B.card = (bad ∪ B).card := (Finset.card_union_of_disjoint h_disj).symm
        rw [h_union]
        have h_le := Finset.card_le_univ (bad ∪ B)
        simp only [Fintype.card_fin] at h_le
        exact h_le
  4. 2 * |bad| < n, completing the proof.

    By the theorem's majority hypothesis h on a, the set B contains a strict majority of the voters, n < 2 * |B|. Combining this with |bad| + |B| ≤ n, linear arithmetic (`omega`) deduces 2 * |bad| < n, which establishes that S is a Condorcet winning set.

    lines 29–31

      have hB : n < 2 * B.card := h a ha
      show 2 * bad.card < n
      omega
Finset.disjoint_left
Two finite sets are disjoint if and only if no element of the first set belongs to the second set.
Finset.mem_filter
An element belongs to the filter of a finite set by a predicate 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 its universal finite set `univ`.
Finset.card_le_card
If one finite set is a subset of another, its cardinality is at most the cardinality of the other set.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities.
Finset.card_le_univ
The cardinality of any finite subset of a finite type is at most the cardinality of the type.
Fintype.card_fin
The cardinality of the type `Fin n` is n.

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

/-- Dual of the top-choice cover: a 3-set is winning as soon as every outside candidate sits in the bottom three of a strict majority of voters. -/theorem condorcet_winning_set_of_bottom_three_majority {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m))    (S : Finset (Fin m)) (hS : S.card = 3)    (h : ∀ a, a ∉ S → n < 2 * (Finset.univ.filter fun v =>      (Finset.univ.filter fun c => P v a < P v c).card ≤ 2).card) :    is_condorcet_winning_set P S := by  intro a ha  let B := Finset.univ.filter (fun v : Fin n =>    (Finset.univ.filter fun c => P v a < P v c).card ≤ 2)  let bad := Finset.univ.filter (fun v : Fin n => ∀ b ∈ S, P v a < P v b)  have h_disj : Disjoint bad B := by    rw [Finset.disjoint_left]    intro v hv    rw [Finset.mem_filter] at hv ⊢    intro ⟨_, h2⟩    have h_sub : S ⊆ Finset.univ.filter (fun c => P v a < P v c) := by      intro b hb      rw [Finset.mem_filter]      exact ⟨Finset.mem_univ _, hv.2 b hb⟩    have h_le := Finset.card_le_card h_sub    rw [hS] at h_le    omega  have h_card_add : bad.card + B.card ≤ n := by    have h_union : bad.card + B.card = (bad ∪ B).card := (Finset.card_union_of_disjoint h_disj).symm    rw [h_union]    have h_le := Finset.card_le_univ (bad ∪ B)    simp only [Fintype.card_fin] at h_le    exact h_le  have hB : n < 2 * B.card := h a ha  show 2 * bad.card < n  omega
See it in the graphDiscuss this resultChallenge it