condorcet_sum_bad_outsiders_eq_sum_min_rank
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
- condorcet_voter_bad_outsiders_eq_min_rankFor a permutation
permofFin mand a nonempty subset S, the number of candidates outside S ranked strictly above every element of S…
- condorcet_voter_bad_outsiders_eq_min_rankFor a permutation
- Used by 1
- condorcet_winning_set_of_sum_min_rank_ltIf 2 * (sum of min ranks of S) < n, then S is a Condorcet winning set.
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.
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.
uses
Finset.card_filtersimp_rw [Finset.card_filter]
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.
uses
Finset.sum_commrw [Finset.sum_comm]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.
uses
Finset.card_filter,condorcet_voter_bad_outsiders_eq_min_ranksimp_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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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]