outside_voters_subset_top_choices_compl
For any candidate set S and candidate x, any voter who ranks x strictly above every member of S has their top-choice candidate outside S.
Statement
theorem outside_voters_subset_top_choices_compl {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m)) (S : Finset (Fin m)) (x : Fin m) (hm : 0 < m) : (Finset.univ.filter fun v => ∀ c ∈ S, P v x < P v c) ⊆ Finset.univ.filter fun v => (P v).symm ⟨0, hm⟩ ∉ S
- Source
- step towards condorcet_dimension_le_three
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- condorcet_winning_set_of_top_choice_majorityAny candidate set S whose complement contains the top choice of strictly fewer than n/2 voters (i.e. S contains the top choices of a…
The proof, explained
The proof proceeds by contradiction. Consider any voter v who ranks candidate x strictly above every candidate in S. If v's top-choice candidate (the candidate assigned rank 0) were in S, then x would have to be ranked strictly ahead of this top choice. That would require x to have a numerical rank strictly less than 0, which is impossible for natural numbers.
Consider any voter v who ranks x strictly above every candidate in S; it suffices to derive a contradiction assuming that v's top choice belongs to S.
We take an arbitrary voter v in the subset. Unfolding the definition of set filtering with `Finset.mem_filter`, voter v satisfies `P v x < P v c` for all `c ∈ S`. To show that v belongs to the target set, it suffices to prove that v's top choice candidate `(P v).symm ⟨0, hm⟩` is not in S; we assume for contradiction that it is in S (`h_top_in_S`).
uses
Finset.mem_filterintro v hv rw [Finset.mem_filter] at hv ⊢ refine ⟨hv.1, fun h_top_in_S => ?_⟩
Voter v must rank candidate x with a numerical rank strictly less than 0: `P v x < 0`.
Since voter v's top choice `(P v).symm ⟨0, hm⟩` is assumed to belong to S, we can specialize the assumption that v ranks x strictly above every candidate in S to this top choice. This yields `P v x < P v ((P v).symm ⟨0, hm⟩)`. By `Equiv.apply_symm_apply`, `P v ((P v).symm ⟨0, hm⟩)` simplifies to `⟨0, hm⟩`, so `P v x < 0`.
uses
Equiv.apply_symm_applyhave h_lt := hv.2 ((P v).symm ⟨0, hm⟩) h_top_in_S rw [Equiv.apply_symm_apply] at h_lt
A contradiction is reached, completing the proof.
No natural number is strictly less than 0 (`Nat.not_lt_zero`), which directly contradicts the inequality `P v x < 0`.
uses
Nat.not_lt_zeroexact Nat.not_lt_zero _ h_lt
Finset.mem_filter- An element belongs to `Finset.filter p s` if and only if it belongs to `s` and satisfies the predicate `p`.
Equiv.apply_symm_apply- Applying an equivalence to the image of an element under its inverse returns the original element: `e (e.symm x) = x`.
Nat.not_lt_zero- No natural number is strictly less than zero.
- Voter preferences are modeled as permutations in `Equiv.Perm (Fin m)`, where smaller numerical values represent higher preferences. In particular, rank 0 represents the voter's top choice, written formally as `(P v).symm ⟨0, hm⟩`.
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.
/-- Any voter ranking x above every candidate in S must have their top choice outside S. -/theorem outside_voters_subset_top_choices_compl {n m : ℕ} (P : Fin n → Equiv.Perm (Fin m)) (S : Finset (Fin m)) (x : Fin m) (hm : 0 < m) : (Finset.univ.filter fun v => ∀ c ∈ S, P v x < P v c) ⊆ Finset.univ.filter fun v => (P v).symm ⟨0, hm⟩ ∉ S := by intro v hv rw [Finset.mem_filter] at hv ⊢ refine ⟨hv.1, fun h_top_in_S => ?_⟩ have h_lt := hv.2 ((P v).symm ⟨0, hm⟩) h_top_in_S rw [Equiv.apply_symm_apply] at h_lt exact Nat.not_lt_zero _ h_lt