AFTD Auto-Formalizing Theoretical Domains

condorcet_winning_set_of_sum_min_rank_lt

theoremverified

If 2 * (sum of min ranks of S) < n, then S is a Condorcet winning set.

Statement

theorem condorcet_winning_set_of_sum_min_rank_lt {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m))
    (S : Finset (Fin m)) (hS : S.Nonempty)
    (h_sum : 2 * (∑ v : Fin n, (S.image (fun s => (P v s).val)).min' (hS.image _)) < n) :
    is_condorcet_winning_set P S
Source
step towards condorcet_dimension_le_three_balanced
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • condorcet_sum_bad_outsiders_eq_sum_min_rankSumming the number of voters who rank an outsider candidate above all of S across all outsiders equals the sum across voters of the…
  • 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 outsider candidate a ∉ S, strictly fewer than n/2 voters prefer a to every candidate in S. The number of voters preferring a specific outsider a to all of S is bounded by the sum over all outsiders of the number of voters who prefer that outsider to S. By the identity condorcet_sum_bad_outsiders_eq_sum_min_rank, this total count of outsider-preferring voters equals the sum across all voters of the minimum rank of S. The hypothesis that twice this sum of minimum ranks is strictly less than n then immediately implies that twice the voter count for a is strictly less than n.

  1. To show that S is a Condorcet winning set, it suffices to consider an arbitrary candidate a ∉ S, noting that a ∈ univ \ S.

    By definition, S is a Condorcet winning set if for every candidate a ∉ S, twice the number of voters who prefer a to all candidates in S is strictly less than n. We introduce such an arbitrary candidate a with hypothesis ha : a ∉ S. Because a belongs to the universal set (Finset.mem_univ), it belongs to the complement Finset.univ \ S by Finset.mem_sdiff.mpr.

    lines 6–7

    uses Finset.mem_sdiff.mpr, Finset.mem_univ

      intro a ha
      have ha' : a ∈ Finset.univ \ S := Finset.mem_sdiff.mpr ⟨Finset.mem_univ a, ha⟩
  2. The number of voters preferring a to all of S is at most the total sum over all outsiders x ∈ univ \ S of the voters preferring x to all of S.

    Since voter counts are non-negative natural numbers (Nat.zero_le), a single summand corresponding to a ∈ univ \ S is bounded above by the sum over the entire set of outsiders (Finset.single_le_sum).

    lines 8–10

    uses Finset.single_le_sum, Nat.zero_le

      have h_le := @Finset.single_le_sum (Fin m) ℕ _ _
        (fun x => (Finset.univ.filter (fun v => ∀ s ∈ S, P v x < P v s)).card)
        (Finset.univ \ S) _ (fun _ _ => Nat.zero_le _) a ha'
  3. The sum over all outsiders x ∉ S of the count of voters preferring x to all of S equals the sum over all voters of their minimum rank of S.

    This combinatorial identity is provided directly by the theorem condorcet_sum_bad_outsiders_eq_sum_min_rank.

    line 11

    uses condorcet_sum_bad_outsiders_eq_sum_min_rank

      have h_sum_eq := condorcet_sum_bad_outsiders_eq_sum_min_rank P S hS
  4. Twice the number of voters preferring a to all of S is strictly less than n, completing the proof.

    We have that the voter count for a is bounded by the sum over outsiders, which equals the sum of minimum ranks across all voters. Since twice this sum of minimum ranks is strictly less than n by assumption, linear integer arithmetic (omega) finishes the proof.

    line 12

      omega
Finset.mem_sdiff.mpr
An element x belongs to the set difference s \ t if and only if x ∈ s and x ∉ t.
Finset.mem_univ
Every element of a finite type belongs to its universal set Finset.univ.
Finset.single_le_sum
In a finite sum of non-negative elements, any individual summand is bounded above by the total sum.
Nat.zero_le
Every natural number is greater than or equal to zero.
condorcet_sum_bad_outsiders_eq_sum_min_rank
For any nonempty set of candidates S, the sum over all outsiders x ∉ S of the number of voters ranking x ahead of all candidates in S equals the sum across all voters of the minimum rank assigned to S.

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 the sum of minimum ranks of S across all voters is strictly less than n/2, then S is a Condorcet winning set. -/theorem condorcet_winning_set_of_sum_min_rank_lt {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m))    (S : Finset (Fin m)) (hS : S.Nonempty)    (h_sum : 2 * (∑ v : Fin n, (S.image (fun s => (P v s).val)).min' (hS.image _)) < n) :    is_condorcet_winning_set P S := by  intro a ha  have ha' : a ∈ Finset.univ \ S := Finset.mem_sdiff.mpr ⟨Finset.mem_univ a, ha⟩  have h_le := @Finset.single_le_sum (Fin m) ℕ _ _    (fun x => (Finset.univ.filter (fun v => ∀ s ∈ S, P v x < P v s)).card)    (Finset.univ \ S) _ (fun _ _ => Nat.zero_le _) a ha'  have h_sum_eq := condorcet_sum_bad_outsiders_eq_sum_min_rank P S hS  omega
See it in the graphDiscuss this resultChallenge it