AFTD Auto-Formalizing Theoretical Domains

condorcet_sum_bad_outsiders_eq_sum_min_rank

theoremverified

Summing the number of voters who rank an outsider candidate above all of S across all outsiders equals the sum across voters of the minimum rank of S.

Statement

theorem condorcet_sum_bad_outsiders_eq_sum_min_rank {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m))
    (S : Finset (Fin m)) (hS : S.Nonempty) :
    (∑ a ∈ Finset.univ \ S, (Finset.univ.filter (fun v => ∀ s ∈ S, P v a < P v s)).card) =
      ∑ v : Fin n, (S.image (fun s => (P v s).val)).min' (hS.image _)
Source
step towards condorcet_dimension_le_three_balanced
Verified
24 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
Used by 1

The proof, explained

The proof uses double counting to exchange the order of summation between candidates and voters. After expressing the candidate-level voter counts as indicator sums, it swaps the two sums so that the outer sum runs over voters. For each fixed voter, the inner sum counts the outsider candidates ranked ahead of every candidate in S; by the voter-level lemma `condorcet_voter_bad_outsiders_eq_min_rank`, this count equals that voter's minimum rank of S.

  1. The total number of bad voters across outsiders is expressed as a double sum of indicator functions.

    Rewriting with `Finset.card_filter` replaces each outsider's voter count—the cardinality of voters ranking outsider a ahead of every member of S—with a sum over all voters of the indicator function that is 1 when the condition holds and 0 otherwise.

    line 6

    uses Finset.card_filter

      simp_rw [Finset.card_filter]
  2. The order of summation is swapped, placing the sum over voters on the outside.

    Applying `Finset.sum_comm` interchanges the outer sum over outsider candidates a ∉ S with the inner sum over voters v.

    line 7

    uses Finset.sum_comm

      rw [Finset.sum_comm]
  3. For each voter, the inner sum counts the outsiders beating S and is replaced by the voter's minimum rank in S, completing the proof.

    Applying `Finset.card_filter` in reverse folds the inner indicator sum back into the cardinality of outsider candidates ranked ahead of all of S by voter v. Then `condorcet_voter_bad_outsiders_eq_min_rank` evaluates this count as the minimum rank among candidates in S for voter v, matching the right-hand side.

    line 8

    uses Finset.card_filter, condorcet_voter_bad_outsiders_eq_min_rank

      simp_rw [← Finset.card_filter, condorcet_voter_bad_outsiders_eq_min_rank _ S hS]
Finset.card_filter
The cardinality of a filtered subset {x ∈ s | p x} equals the sum over x ∈ s of the indicator function of p (1 if p x holds, 0 otherwise).
Finset.sum_comm
The order of two finite summations can be exchanged: ∑ x ∈ s, ∑ y ∈ t, f x y = ∑ y ∈ t, ∑ x ∈ s, f x y.
condorcet_voter_bad_outsiders_eq_min_rank
For any voter's preference ranking and any nonempty set of candidates S, the number of outside candidates ranked strictly above all candidates in S equals the minimum rank assigned to members of 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

/-- The total number of bad voters across all outside candidates equals the sum of the minimum ranks of S over all voters. -/theorem condorcet_sum_bad_outsiders_eq_sum_min_rank {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m))    (S : Finset (Fin m)) (hS : S.Nonempty) :    (∑ a ∈ Finset.univ \ S, (Finset.univ.filter (fun v => ∀ s ∈ S, P v a < P v s)).card) =      ∑ v : Fin n, (S.image (fun s => (P v s).val)).min' (hS.image _) := by  simp_rw [Finset.card_filter]  rw [Finset.sum_comm]  simp_rw [← Finset.card_filter, condorcet_voter_bad_outsiders_eq_min_rank _ S hS]
See it in the graphDiscuss this resultChallenge it