AFTD Auto-Formalizing Theoretical Domains

condorcet_winning_set_of_top_choices

theoremverified

For any election with at least one candidate, the set of top-choice candidates of any subset of voters V0 is a Condorcet winning set provided that strictly fewer than n/2 voters lie outside V0.

Statement

theorem condorcet_winning_set_of_top_choices {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m))
    (hm : 0 < m) (V0 : Finset (Fin n)) (hV0 : 2 * (n - V0.card) < n) :
    is_condorcet_winning_set P (V0.image fun v => (P v).symm ⟨0, hm⟩)
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…
Used by 1

The proof, explained

To prove that the set S of top-choice candidates of voters in V0 forms a Condorcet winning set, we show that for any candidate a ∉ S, strictly fewer than n/2 voters prefer a to every member of S. No voter in V0 can prefer a to all of S, because S already contains their top-ranked candidate (rank 0), which cannot be strictly beaten. Therefore, all voters preferring a to every candidate in S must lie outside V0, limiting their count to at most |V0ᶜ| = n - |V0|. Since 2 * (n - |V0|) < n by hypothesis, strictly fewer than half of the voters prefer a to all candidates in S.

  1. To show that the set of top choices S is a Condorcet winning set, it suffices to show that for any candidate a ∉ S, strictly fewer than n/2 voters prefer a to all candidates in S.

    We introduce an arbitrary candidate a and the assumption ha that a does not belong to S = V0.image (fun v => (P v).symm ⟨0, hm⟩). By the definition of is_condorcet_winning_set, the remaining goal is to show that 2 * |{v | ∀ b ∈ S, P v a < P v b}| < n.

    line 5

      intro a ha
  2. Any voter who strictly prefers candidate a to all candidates in S must belong to the complement of V0.

    We prove that the set of voters preferring a to all b ∈ S is a subset of Finset.univ \ V0. Suppose for contradiction that such a voter v belongs to V0. Then voter v's top choice candidate (P v).symm ⟨0, hm⟩ is an element of S (via Finset.mem_image.mpr). Since v prefers a to every candidate in S, we have P v a < P v ((P v).symm ⟨0, hm⟩). By Equiv.apply_symm_apply, P v ((P v).symm ⟨0, hm⟩) = ⟨0, hm⟩, which implies P v a < 0. But in Fin m (where m is nonzero by Nat.pos_iff_ne_zero.mp), no element is strictly less than 0 (Fin.not_lt_zero), giving a contradiction. Membership in the complement is simplified using Finset.mem_filter, Finset.mem_univ, Finset.mem_sdiff, and true_and.

    lines 6–19

    uses Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_sdiff, Finset.mem_image.mpr, Equiv.apply_symm_apply, Nat.pos_iff_ne_zero.mp, Fin.not_lt_zero

      have hsub : (Finset.univ.filter fun v =>
          ∀ b ∈ V0.image (fun v => (P v).symm ⟨0, hm⟩), P v a < P v b)
          ⊆ Finset.univ \ V0 := by
        intro v hv
        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hv
        simp only [Finset.mem_sdiff, Finset.mem_univ, true_and]
        intro hvV
        have htop : (P v).symm ⟨0, hm⟩ ∈ V0.image (fun v => (P v).symm ⟨0, hm⟩) :=
          Finset.mem_image.mpr ⟨v, hvV, rfl⟩
        have hlt := hv _ htop
        have hzero : P v ((P v).symm ⟨0, hm⟩) = ⟨0, hm⟩ := Equiv.apply_symm_apply _ _
        rw [hzero] at hlt
        haveI : NeZero m := ⟨Nat.pos_iff_ne_zero.mp hm⟩
        exact Fin.not_lt_zero (P v a) hlt
  3. The number of voters who prefer candidate a to all candidates in S is at most n - |V0|.

    By subset monotonicity of cardinality (Finset.card_le_card), the number of such voters is bounded by |univ \ V0|. Since univ \ V0 is the complement V0ᶜ, its size is |Fin n| - |V0| = n - |V0|, using Finset.card_compl and Fintype.card_fin.

    lines 20–29

    uses Finset.card_le_card, Finset.card_compl, Fintype.card_fin

      have hcard : (Finset.univ.filter fun v =>
          ∀ b ∈ V0.image (fun v => (P v).symm ⟨0, hm⟩), P v a < P v b).card
          ≤ n - V0.card := by
        calc
          (Finset.univ.filter fun v =>
              ∀ b ∈ V0.image (fun v => (P v).symm ⟨0, hm⟩), P v a < P v b).card
              ≤ (Finset.univ \ V0).card := Finset.card_le_card hsub
          _ = n - V0.card := by
            rw [show Finset.univ \ V0 = V0ᶜ by ext; simp]
            rw [Finset.card_compl, Fintype.card_fin]
  4. Twice the number of voters who prefer candidate a to all candidates in S is strictly less than n.

    The number of such voters is at most n - |V0|, and the assumption hV0 states that 2 * (n - |V0|) < n. Linear integer arithmetic closes the goal.

    line 30

      omega
Equiv.apply_symm_apply
Applying an equivalence to the image of an element under its inverse yields the original element: e (e.symm x) = x.
Fin.not_lt_zero
In Fin n, no element is strictly less than zero.
Finset.card_compl
The cardinality of the complement of a subset s in a finite type is the cardinality of the type minus the cardinality of s.
Finset.card_le_card
If s is a subset of t, then the cardinality of s is at most the cardinality of t.
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_image.mpr
An element belongs to the image of a set under a function if it is the image of some element in that set.
Finset.mem_sdiff
An element belongs to the set difference s \ t if and only if it belongs to s and does not belong to t.
Finset.mem_univ
Every element of a finite type belongs to the universal finset.
Fintype.card_fin
The cardinality of Fin n is n.
Nat.pos_iff_ne_zero.mp
If a natural number is strictly positive, then it is nonzero.
true_and
Conjunction with True is equivalent to the proposition itself: (True ∧ p) = p.

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

/-- The set of top-choice candidates of a voter subset V0 is a Condorcet winning set if strictly fewer than n/2 voters lie outside V0. -/theorem condorcet_winning_set_of_top_choices {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m))    (hm : 0 < m) (V0 : Finset (Fin n)) (hV0 : 2 * (n - V0.card) < n) :    is_condorcet_winning_set P (V0.image fun v => (P v).symm ⟨0, hm⟩) := by  intro a ha  have hsub : (Finset.univ.filter fun v =>      ∀ b ∈ V0.image (fun v => (P v).symm ⟨0, hm⟩), P v a < P v b)      ⊆ Finset.univ \ V0 := by    intro v hv    simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hv    simp only [Finset.mem_sdiff, Finset.mem_univ, true_and]    intro hvV    have htop : (P v).symm ⟨0, hm⟩ ∈ V0.image (fun v => (P v).symm ⟨0, hm⟩) :=      Finset.mem_image.mpr ⟨v, hvV, rfl⟩    have hlt := hv _ htop    have hzero : P v ((P v).symm ⟨0, hm⟩) = ⟨0, hm⟩ := Equiv.apply_symm_apply _ _    rw [hzero] at hlt    haveI : NeZero m := ⟨Nat.pos_iff_ne_zero.mp hm⟩    exact Fin.not_lt_zero (P v a) hlt  have hcard : (Finset.univ.filter fun v =>      ∀ b ∈ V0.image (fun v => (P v).symm ⟨0, hm⟩), P v a < P v b).card      ≤ n - V0.card := by    calc      (Finset.univ.filter fun v =>          ∀ b ∈ V0.image (fun v => (P v).symm ⟨0, hm⟩), P v a < P v b).card          ≤ (Finset.univ \ V0).card := Finset.card_le_card hsub      _ = n - V0.card := by        rw [show Finset.univ \ V0 = V0ᶜ by ext; simp]        rw [Finset.card_compl, Fintype.card_fin]  omega
See it in the graphDiscuss this resultChallenge it