condorcet_voter_bad_outsiders_eq_min_rank
For a permutation perm of Fin m and a nonempty subset S, the number of candidates outside S ranked strictly above every element of S by perm equals the minimum rank of S under perm.
Statement
theorem condorcet_voter_bad_outsiders_eq_min_rank {m : ℕ} (perm : Equiv.Perm (Fin m)) (S : Finset (Fin m)) (hS : S.Nonempty) : ((Finset.univ \ S).filter (fun a => ∀ s ∈ S, perm a < perm s)).card = (S.image (fun s => (perm s).val)).min' (hS.image _)
- Source
- step towards condorcet_dimension_le_three_balanced
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- LinearOrder.toTotalPreorderEvery
- Used by 1
- 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…
The proof, explained
To count candidates outside S ranked strictly above every element of S, we first note that no candidate in S can rank strictly above itself, so the restriction to outside candidates is redundant. Being ranked strictly above every member of S is equivalent to having a rank strictly less than the minimum rank r of S. Since voter preferences are a bijection on Fin m, the number of such candidates equals the number of elements in Fin m strictly less than r, which evaluates to min(m, r) = r because r < m.
Letting `r` be the minimum rank in `S`, the condition that a candidate lies outside `S` is redundant.
We define `r` to be the minimum rank of any element of `S` under `perm`. Any candidate `a` ranked strictly above every element of `S` cannot belong to `S` itself, since taking `s = a` would imply `perm a < perm a`, contradicting irreflexivity of `<` (`lt_irrefl`). Hence, filtering over `univ \ S` is identical to filtering over all of `univ`.
uses
Finset.mem_filter,Finset.mem_sdiff,Finset.mem_univ,true_and,lt_irreflset r := (S.image (fun s => (perm s).val)).min' (hS.image _) with hr have h_filter_sdiff : (Finset.univ \ S).filter (fun a => ∀ s ∈ S, perm a < perm s) = Finset.univ.filter (fun a => ∀ s ∈ S, perm a < perm s) := by ext a simp only [Finset.mem_filter, Finset.mem_sdiff, Finset.mem_univ, true_and] refine ⟨fun ⟨_, h⟩ => h, fun h => ⟨fun ha => lt_irrefl _ (h a ha), h⟩⟩ rw [h_filter_sdiff]
Ranking strictly above all elements of `S` is equivalent to having a rank strictly less than `r`.
By `Finset.lt_min'_iff`, a rank is strictly less than the minimum of a nonempty set if and only if it is strictly less than every rank in that set. Replacing this condition in the filter characterizes the set as all `a : Fin m` with `(perm a).val < r`.
uses
Finset.lt_min'_iff,Finset.mem_filter,Finset.mem_univ,true_andhave h_pred (a : Fin m) : (∀ s ∈ S, perm a < perm s) ↔ (perm a).val < r := by rw [hr, Finset.lt_min'_iff] simp have h_filter_eq : Finset.univ.filter (fun a => ∀ s ∈ S, perm a < perm s) = Finset.univ.filter (fun a => (perm a).val < r) := by ext a simp only [Finset.mem_filter, Finset.mem_univ, true_and, h_pred] rw [h_filter_eq]
The number of candidates with rank strictly less than `r` equals the number of indices in `Fin m` strictly less than `r`.
Because `perm` is a permutation of `Fin m`, its inverse `perm.symm` defines a bijection (embedding) from `{b : Fin m | b.val < r}` to `{a : Fin m | (perm a).val < r}`. By `Finset.card_map`, the two sets have the same cardinality.
uses
Finset.card_maphave h_card_perm : (Finset.univ.filter (fun a => (perm a).val < r)).card = (Finset.univ.filter (fun b : Fin m => b.val < r)).card := by have h_map : Finset.univ.filter (fun a => (perm a).val < r) = (Finset.univ.filter (fun b : Fin m => b.val < r)).map perm.symm.toEmbedding := by ext a simp rw [h_map, Finset.card_map] rw [h_card_perm]
The cardinality of `{b : Fin m | b.val < r}` is `r`.
By `Fin.card_filter_val_lt`, the number of elements in `Fin m` strictly below `r` is `min m r`. Since `S` is nonempty, the minimum rank `r` is attained at some `s ∈ S` (`Finset.min'_mem`, `Finset.mem_image`), and every element of `Fin m` has value strictly less than `m` (`Fin.isLt`), so `r < m`. Thus `min m r = r` (`min_eq_right`, `le_of_lt`), completing the proof.
uses
Fin.card_filter_val_lt,Finset.min'_mem,Finset.mem_image,Fin.isLt,min_eq_right,le_of_ltrw [Fin.card_filter_val_lt] have hr_lt : r < m := by rw [hr] have hr_mem := Finset.min'_mem (S.image (fun s => (perm s).val)) (hS.image _) simp only [Finset.mem_image] at hr_mem rcases hr_mem with ⟨s, _, hs⟩ rw [← hs] exact (perm s).isLt exact min_eq_right (le_of_lt hr_lt)
Fin.isLt- The underlying natural number of an element in `Fin n` is strictly less than `n`.
Fin.card_filter_val_lt- The number of elements in `Fin n` with numerical value strictly less than `m` is `min n m`.
Finset.card_map- Mapping a finite set along an embedding preserves its cardinality.
Finset.mem_filter- An element belongs to the filtered finset if and only if it belongs to the original finset and satisfies the predicate.
Finset.mem_image- An element belongs to the image of a finset under `f` if and only if it is the image of some element in the finset.
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 its universal finset `Finset.univ`.
Finset.lt_min'_iff- An element is strictly less than the minimum of a nonempty finite set if and only if it is strictly less than every element of that set.
Finset.min'_mem- The minimum element of a nonempty finite set belongs to the set.
le_of_lt- If `a < b`, then `a ≤ b`.
lt_irrefl- Strict inequality is irreflexive: `¬ a < a`.
min_eq_right- If `b ≤ a`, then `min a b = b`.
true_and- Conjunction with `True` simplifies to the proposition itself: `(True ∧ p) = p`.
- Candidates are indexed by `Fin m`, where lower numerical values correspond to higher (better) rankings under the preference permutation `perm`.
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.
/-- For a single voter, the number of outside candidates ranked above all members of S equals the minimum rank of S under that voter's preference permutation. -/theorem condorcet_voter_bad_outsiders_eq_min_rank {m : ℕ} (perm : Equiv.Perm (Fin m)) (S : Finset (Fin m)) (hS : S.Nonempty) : ((Finset.univ \ S).filter (fun a => ∀ s ∈ S, perm a < perm s)).card = (S.image (fun s => (perm s).val)).min' (hS.image _) := by set r := (S.image (fun s => (perm s).val)).min' (hS.image _) with hr have h_filter_sdiff : (Finset.univ \ S).filter (fun a => ∀ s ∈ S, perm a < perm s) = Finset.univ.filter (fun a => ∀ s ∈ S, perm a < perm s) := by ext a simp only [Finset.mem_filter, Finset.mem_sdiff, Finset.mem_univ, true_and] refine ⟨fun ⟨_, h⟩ => h, fun h => ⟨fun ha => lt_irrefl _ (h a ha), h⟩⟩ rw [h_filter_sdiff] have h_pred (a : Fin m) : (∀ s ∈ S, perm a < perm s) ↔ (perm a).val < r := by rw [hr, Finset.lt_min'_iff] simp have h_filter_eq : Finset.univ.filter (fun a => ∀ s ∈ S, perm a < perm s) = Finset.univ.filter (fun a => (perm a).val < r) := by ext a simp only [Finset.mem_filter, Finset.mem_univ, true_and, h_pred] rw [h_filter_eq] have h_card_perm : (Finset.univ.filter (fun a => (perm a).val < r)).card = (Finset.univ.filter (fun b : Fin m => b.val < r)).card := by have h_map : Finset.univ.filter (fun a => (perm a).val < r) = (Finset.univ.filter (fun b : Fin m => b.val < r)).map perm.symm.toEmbedding := by ext a simp rw [h_map, Finset.card_map] rw [h_card_perm] rw [Fin.card_filter_val_lt] have hr_lt : r < m := by rw [hr] have hr_mem := Finset.min'_mem (S.image (fun s => (perm s).val)) (hS.image _) simp only [Finset.mem_image] at hr_mem rcases hr_mem with ⟨s, _, hs⟩ rw [← hs] exact (perm s).isLt exact min_eq_right (le_of_lt hr_lt)