ejr_chain_singleton_ballots
If every voter approves at most one candidate, then there is an ordering of the candidates every prefix of which is an EJR committee of the corresponding size.
Statement
theorem ejr_chain_singleton_ballots {n m : ℕ} (A : Fin n → Finset (Fin m)) (hn : 0 < n) (hA : ∀ i, (A i).card ≤ 1) : ∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m → is_ejr_committee A k (Finset.univ.filter fun c => (σ c : ℕ) < k)
- Source
- step towards ejr_committee_monotone_chain_exists
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- is_ejr_committee_iff_candidate_subsetsEJR is equivalent to the correct committee size together with the underrepresented-supporter inequality for every nonempty candidate…
- exists_perm_with_prefix_eq_takeEvery duplicate-free list L of length m whose entries are the m candidates is the order of appearance of some permutation σ: for every k ≤…
- ejr_chain_iff_level_supportersA permutation whose every prefix of length k is an EJR committee exists if and only if there is a permutation such that for every k ≤ m…
- is_ejr_committeeA committee W with |W| = k satisfies EJR if for every ℓ ≥ 1 and every ℓ-cohesive group G some voter i ∈ G has |A_i ∩ W| ≥ ℓ.
- weightThe support $\mathrm{supp}(p) \subseteq \mathrm{Fin}\,n$ consists of coordinates where $p(i) \neq I$; the weight is…
The proof, explained
The proof orders the candidates in non-increasing order of their approval counts. Since every voter approves at most one candidate, double counting shows that the sum of all candidate approval counts is at most the number of voters $n$. Sorting candidates from most to least approved ensures that a candidate at 0-based position $p$ has approval count at most $n / (p + 1)$, which yields $s(c) \cdot \sigma(c) < n$. By the level-supporters characterization of EJR chains (`ejr_chain_iff_level_supporters`), any candidate test set $T$ with $|T| \ge 2$ has no supporters at all, while for a singleton $T = \{c\}$, the number of unsatisfied supporters times $k$ is bounded by $s(c) \cdot \sigma(c) < n$.
The sum of approval counts across all candidates is at most the number of voters: $\sum_{c} |\{i : c \in A(i)\}| \le n$.
We express the size of each candidate's supporter set as a sum of 0-1 indicator variables. Exchanging the order of summation transforms the total into the sum over voters of each ballot's size $\sum_{i} |A(i)|$. Since each voter approves at most one candidate ($|A(i)| \le 1$), bounding each summand by 1 yields $\sum_{i} 1 = n$.
uses
Finset.sum_congr,Finset.sum_boole,Finset.sum_comm,Finset.sum_le_sumclassical have h1 : ∑ c : Fin m, (Finset.univ.filter fun i : Fin n => c ∈ A i).card = ∑ c : Fin m, ∑ i : Fin n, (if c ∈ A i then 1 else 0) := by apply Finset.sum_congr rfl intro c _ rw [Finset.sum_boole] simp rw [h1, Finset.sum_comm] have h2 : ∑ i : Fin n, ∑ c : Fin m, (if c ∈ A i then 1 else 0) = ∑ i : Fin n, (A i).card := by apply Finset.sum_congr rfl intro i _ rw [Finset.sum_boole] simp rw [h2] calc ∑ i : Fin n, (A i).card ≤ ∑ i : Fin n, 1 := Finset.sum_le_sum (fun i _ => hA i) _ = n := by simp
Sorting candidates in non-increasing order of approval counts yields an antitone sequence of weights.
We sort the candidates using `Tuple.sort` with respect to the dual order of their approval counts $s(c)$. By `Tuple.monotone_sort`, the resulting permutation $\text{atPos}$ produces a monotone sequence in the dual order, meaning the approval counts $s(\text{atPos}(i))$ form an antitone (non-increasing) sequence across positions $i$.
uses
Tuple.sort,Tuple.monotone_sort,OrderDual.toDual_le_toDual.mpclassical set atPos : Equiv.Perm (Fin m) := Tuple.sort (fun c : Fin m => OrderDual.toDual (s c)) with hatPos have hmono : Monotone ((fun c : Fin m => OrderDual.toDual (s c)) ∘ atPos) := Tuple.monotone_sort _ have hanti : Antitone (fun i : Fin m => s (atPos i)) := by intro a b hab exact OrderDual.toDual_le_toDual.mp (hmono hab)
For every candidate $c$, placed at 0-based position $p = \text{atPos}^{-1}(c)$, the weight satisfies $s(c) \cdot (p + 1) \le n$.
Because the approval counts are non-increasing with position, index $p$ is strictly less than the number of positions with approval count at least $s(c)$ by `Tuple.lt_card_ge_iff_apply_ge_of_antitone`. Via the bijection $\text{atPos}$, this set of positions has the same cardinality as the set of all candidates with weight at least $s(c)$, so $p + 1 \le |\{x : s(c) \le s(x)\}|$. Each such candidate contributes at least $s(c)$ to the total weight, so $|\{x : s(c) \le s(x)\}| \cdot s(c) \le \sum_{x : s(c) \le s(x)} s(x) \le \sum_x s(x) \le n$. Combining inequalities gives $s(c) \cdot (p + 1) \le n$.
uses
Tuple.lt_card_ge_iff_apply_ge_of_antitone,Finset.card_bij,Finset.card_nsmul_le_sum,nsmul_eq_mul,Finset.sum_le_univ_sum_of_nonneg,Nat.zero_le,le_trans,Nat.mul_comm,Nat.mul_le_mul_righthave key : ∀ c : Fin m, s c * ((atPos.symm c : Fin m) : ℕ) < n := by intro c set p : Fin m := atPos.symm c with hp have hpc : atPos p = c := by simp [hp] have hlt : (p : ℕ) < (Finset.univ.filter fun i : Fin m => s c ≤ s (atPos i)).card := by rw [Tuple.lt_card_ge_iff_apply_ge_of_antitone (f := fun i : Fin m => s (atPos i)) (a := s c) (j := p) hanti] simp [hpc] have hcard : (Finset.univ.filter fun i : Fin m => s c ≤ s (atPos i)).card = (Finset.univ.filter fun x : Fin m => s c ≤ s x).card := by refine Finset.card_bij (fun i _ => atPos i) ?_ ?_ ?_ · intro i hi exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, (Finset.mem_filter.mp hi).2⟩ · intro i _ j _ hij exact atPos.injective hij · intro b hb exact ⟨atPos.symm b, Finset.mem_filter.mpr ⟨Finset.mem_univ _, by simpa using (Finset.mem_filter.mp hb).2⟩, by simp⟩ have hbound : (Finset.univ.filter fun x : Fin m => s c ≤ s x).card * s c ≤ n := by have step1 : (Finset.univ.filter fun x : Fin m => s c ≤ s x).card * s c ≤ ∑ x ∈ Finset.univ.filter (fun x : Fin m => s c ≤ s x), s x := by have := Finset.card_nsmul_le_sum (Finset.univ.filter (fun x : Fin m => s c ≤ s x)) s (s c) (fun x hx => (Finset.mem_filter.mp hx).2) simpa [nsmul_eq_mul] using this have step2 : ∑ x ∈ Finset.univ.filter (fun x : Fin m => s c ≤ s x), s x ≤ ∑ x, s x := Finset.sum_le_univ_sum_of_nonneg (fun x => Nat.zero_le _) exact le_trans step1 (le_trans step2 hsum) have hp1 : (p : ℕ) + 1 ≤ (Finset.univ.filter fun x : Fin m => s c ≤ s x).card := by omega have hle : s c * ((p : ℕ) + 1) ≤ n := by rw [Nat.mul_comm] exact le_trans (Nat.mul_le_mul_right (s c) hp1) hbound
The inverse permutation $\sigma = \text{atPos}^{-1}$ satisfies $s(c) \cdot \sigma(c) < n$ for all candidates $c$.
If $s(c) = 0$, then $s(c) \cdot p = 0 < n$ because $n > 0$. If $s(c) > 0$, multiplying the strict inequality $p < p + 1$ by $s(c)$ gives $s(c) \cdot p < s(c) \cdot (p + 1) \le n$. Thus the permutation $\sigma = \text{atPos}^{-1}$ orders candidates so that $s(c) \cdot \sigma(c) < n$ for all $c$.
uses
Nat.zero_mul,Nat.pos_of_ne_zero,Nat.mul_lt_mul_of_pos_left,Nat.lt_succ_self,lt_of_lt_of_leby_cases hsc : s c = 0 · rw [hsc, Nat.zero_mul]; exact hn · have hpos : 0 < s c := Nat.pos_of_ne_zero hsc have hstrict : s c * (p : ℕ) < s c * ((p : ℕ) + 1) := Nat.mul_lt_mul_of_pos_left (Nat.lt_succ_self _) hpos exact lt_of_lt_of_le hstrict hle exact ⟨atPos.symm, key⟩
It suffices to show that the permutation $\sigma$ satisfies the level-supporters condition for all committee sizes $k \le m$ and nonempty test sets $T$.
Let $s(c)$ be the number of approvals of candidate $c$. By the double counting lemma, $\sum_c s(c) \le n$, so the scheduling lemma provides a permutation $\sigma$ with $s(c) \cdot \sigma(c) < n$ for all $c$. By `ejr_chain_iff_level_supporters`, this permutation forms an EJR chain if and only if for every $k \le m$ and nonempty candidate set $T$, the number of voters who approve all of $T$ but have fewer than $|T|$ representatives in the top-$k$ prefix $W$ satisfies $|\{i : T \subseteq A(i) \wedge |A(i) \cap W| < |T|\}| \cdot k < |T| \cdot n$.
uses
ejr_chain_singleton_ballots_sum_support_le,ejr_chain_singleton_ballots_exists_perm,ejr_chain_iff_level_supportersclassical set s : Fin m → ℕ := fun c => (Finset.univ.filter fun i => c ∈ A i).card with hs have hsum : ∑ c, s c ≤ n := ejr_chain_singleton_ballots_sum_support_le A hA obtain ⟨σ, hσ⟩ := ejr_chain_singleton_ballots_exists_perm s hn hsum refine (ejr_chain_iff_level_supporters A).mpr ⟨σ, ?_⟩ intro k hk T hT set W : Finset (Fin m) := Finset.univ.filter fun c => (σ c : ℕ) < k with hW
When $|T| < 2$, the test set is a singleton $\{c\}$, and its unsatisfied supporters are precisely the voters who approve $c$ when $c$ is not in the prefix $W$.
Since $T$ is nonempty and $|T| < 2$, we have $|T| = 1$, so $T = \{c\}$ for some candidate $c$. A voter $i$ approving $c$ has $|A(i)| \le 1$, which forces $A(i) = \{c\}$. Thus the committee intersection $A(i) \cap W$ has size less than 1 if and only if $c \notin W$. The set of voters who approve $T$ and have fewer than $|T|$ committee members is therefore precisely the set of voters approving $c$ when $c \notin W$.
uses
Nat.lt_or_ge,Finset.card_pos.mpr,Finset.card_eq_one.mp,Finset.filter_congr,Finset.mem_singleton_self,Finset.mem_inter.mpr,Finset.singleton_subset_iff.mpr,Finset.mem_inter.mp,Finset.card_le_one.mp,Finset.card_singleton,Nat.one_mulrcases Nat.lt_or_ge T.card 2 with h2 | h2 · have hT1 : T.card = 1 := by have hpos : 0 < T.card := Finset.card_pos.mpr hT omega obtain ⟨c, rfl⟩ := Finset.card_eq_one.mp hT1 have hsupp : (Finset.univ.filter fun i => ({c} : Finset (Fin m)) ⊆ A i ∧ (A i ∩ W).card < 1) = Finset.univ.filter fun i => c ∈ A i ∧ c ∉ W := by apply Finset.filter_congr intro i _ constructor · rintro ⟨hsub, hlt⟩ refine ⟨hsub (Finset.mem_singleton_self c), ?_⟩ intro hcW have hpos : 0 < (A i ∩ W).card := Finset.card_pos.mpr ⟨c, Finset.mem_inter.mpr ⟨hsub (Finset.mem_singleton_self c), hcW⟩⟩ omega · rintro ⟨hc, hcW⟩ refine ⟨Finset.singleton_subset_iff.mpr hc, ?_⟩ have hempty : ¬ (A i ∩ W).Nonempty := by rintro ⟨x, hx⟩ obtain ⟨hxA, hxW⟩ := Finset.mem_inter.mp hx have hxc : x = c := Finset.card_le_one.mp (hA i) x hxA c hc exact hcW (hxc ▸ hxW) rw [Finset.card_eq_zero.mpr (Finset.not_nonempty_iff_eq_empty.mp hempty)] exact Nat.zero_lt_one rw [Finset.card_singleton, hsupp, Nat.one_mul]
For a singleton $T = \{c\}$, the number of unsatisfied supporters times $k$ is strictly less than $n$.
We case split on whether $c \in W$: if $c \in W$, then no voter satisfies $c \notin W$, making the supporter set empty and giving $0 \cdot k = 0 < n$. If $c \notin W$, then by the definition of $W = \{x : \sigma(x) < k\}$, the candidate's position satisfies $k \le \sigma(c)$. The number of voters approving $c$ is at most the total support $s(c)$, so the supporter count times $k$ is bounded by $s(c) \cdot k \le s(c) \cdot \sigma(c) < n$.
uses
Finset.filter_false_of_mem,Finset.card_empty,Nat.zero_mul,Finset.mem_filter,Finset.mem_univ,true_and,Finset.card_le_card,Nat.mul_le_mul_right,Nat.mul_le_mul_leftby_cases hcW : c ∈ W · have hempty : (Finset.univ.filter fun i : Fin n => c ∈ A i ∧ c ∉ W) = ∅ := by apply Finset.filter_false_of_mem intro i _ h exact h.2 hcW rw [hempty, Finset.card_empty, Nat.zero_mul] exact hn · have hksig : k ≤ (σ c : ℕ) := by rw [hW] at hcW simp only [Finset.mem_filter, Finset.mem_univ, true_and, not_lt] at hcW exact hcW have hcard : (Finset.univ.filter fun i : Fin n => c ∈ A i ∧ c ∉ W).card ≤ s c := by rw [hs] apply Finset.card_le_card intro i hi exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, (Finset.mem_filter.mp hi).2.1⟩ calc (Finset.univ.filter fun i : Fin n => c ∈ A i ∧ c ∉ W).card * k ≤ s c * k := Nat.mul_le_mul_right k hcard _ ≤ s c * (σ c : ℕ) := Nat.mul_le_mul_left (s c) hksig _ < n := hσ c
When $|T| \ge 2$, no voter can approve $T$, so the condition holds vacuously.
Since every ballot contains at most one candidate ($|A(i)| \le 1$), the condition $T \subseteq A(i)$ would imply $|T| \le 1$, contradicting $|T| \ge 2$. Hence the set of such voters is empty, its cardinality is 0, and $0 \cdot k = 0 < |T| \cdot n$ holds strictly because $n > 0$ and $|T| \ge 2$.
uses
Finset.filter_false_of_mem,Finset.card_le_card,Finset.card_empty,Nat.zero_mul,Nat.mul_pos· have hempty : (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < T.card) = ∅ := by apply Finset.filter_false_of_mem intro i _ h have h1 : T.card ≤ (A i).card := Finset.card_le_card h.1 have h2 := hA i omega rw [hempty, Finset.card_empty, Nat.zero_mul] exact Nat.mul_pos (by omega) hn
Finset.sum_congr- If two finite sets are equal and their summands agree on all elements, their sums are equal.
Finset.sum_boole- The sum of an indicator function (1 if true, 0 if false) over a finite set equals the cardinality of the subset satisfying the predicate.
Finset.sum_comm- In a finite double sum, the order of summation can be interchanged.
Finset.sum_le_sum- If each term in a finite sum is bounded by the corresponding term in another, the total sum is bounded accordingly.
Tuple.sort- The permutation of coordinates that sorts a tuple into monotone order.
Tuple.monotone_sort- Composing a tuple with its sorting permutation yields a monotone function.
OrderDual.toDual_le_toDual.mp- In the dual order, $x \le y$ is equivalent to $y \le x$ in the base order.
Tuple.lt_card_ge_iff_apply_ge_of_antitone- For an antitone sequence on $\text{Fin } m$, index $j$ is strictly less than the number of terms greater than or equal to $a$ if and only if the $j$-th term is at least $a$.
Finset.card_bij- A bijection between two finite sets implies they have the same cardinality.
Finset.card_nsmul_le_sum- If every element in a finite set has value at least $n$, then the cardinality times $n$ is at most the sum of the values.
nsmul_eq_mul- Scalar multiplication of an element by a natural number $n$ equals ordinary multiplication by $n$.
Finset.sum_le_univ_sum_of_nonneg- The sum of non-negative values over a sub-finset is at most the sum over the entire finite universe.
Nat.zero_le- Zero is less than or equal to any natural number.
le_trans- Inequality $\le$ on a preorder is transitive: if $a \le b$ and $b \le c$, then $a \le c$.
Nat.mul_comm- Multiplication of natural numbers is commutative: $n \cdot m = m \cdot n$.
Nat.mul_le_mul_right- Multiplying both sides of a natural number inequality $n \le m$ on the right by $k$ preserves the inequality.
Nat.zero_mul- Zero times any natural number is zero.
Nat.pos_of_ne_zero- A non-zero natural number is strictly positive.
Nat.mul_lt_mul_of_pos_left- Strict inequality between natural numbers is preserved when multiplying on the left by a strictly positive number.
Nat.lt_succ_self- Any natural number is strictly less than its successor: $n < n + 1$.
lt_of_lt_of_le- If $a < b$ and $b \le c$, then $a < c$.
ejr_chain_singleton_ballots_sum_support_le- When every ballot contains at most one candidate, the sum of approval counts across all candidates is at most the number of voters $n$.
ejr_chain_singleton_ballots_exists_perm- If non-negative weights on $m$ candidates sum to at most $n > 0$, the candidates can be permuted so that each candidate's weight times its 0-based position is strictly less than $n$.
ejr_chain_iff_level_supporters- A candidate ordering forms an EJR chain if and only if every nonempty candidate subset $T$ satisfies a strict supporter-count inequality for every committee size $k$.
Nat.lt_or_ge- For any natural numbers $n$ and $m$, either $n < m$ or $n \ge m$.
Finset.card_pos.mpr- A nonempty finite set has strictly positive cardinality.
Finset.card_eq_one.mp- A finite set of cardinality 1 is a singleton $\{a\}$.
Finset.filter_congr- Two filtered sets are equal if their defining predicates are equivalent on all elements of the base set.
Finset.mem_singleton_self- Every element belongs to its own singleton set: $a \in \{a\}$.
Finset.mem_inter.mpr- An element belonging to both $s$ and $t$ belongs to their intersection $s \cap t$.
Finset.singleton_subset_iff.mpr- If $x \in s$, then the singleton $\{x\}$ is a subset of $s$.
Finset.mem_inter.mp- If an element belongs to $s \cap t$, then it belongs to both $s$ and $t$.
Finset.card_le_one.mp- In a set with at most one element, any two elements are equal.
Finset.card_singleton- The cardinality of a singleton set is 1.
Nat.one_mul- One times any natural number equals that number.
Finset.filter_false_of_mem- Filtering a finite set by a predicate that holds for no element yields the empty set.
Finset.card_empty- The empty finite set has cardinality 0.
Finset.mem_filter- An element is in a filtered set if and only if it belongs to the base set and satisfies the predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal set `Finset.univ`.
true_and- The proposition $\text{True} \wedge p$ is equivalent to $p$.
Finset.card_le_card- If one finite set is a subset of another, its cardinality is at most the other's.
Nat.mul_le_mul_left- Multiplying both sides of a natural number inequality $n \le m$ on the left by $k$ preserves the inequality.
Nat.mul_pos- The product of two strictly positive natural numbers is strictly positive.
- In the Lean formalization, ordering candidates in descending order of approval count is expressed via `Tuple.sort` applied to `OrderDual.toDual (s c)`, which sorts in non-decreasing order in the dual order.
- The equivalence `ejr_chain_iff_level_supporters` is a characterization proven earlier in the library that reduces verifying an EJR committee chain to checking a supporter-count inequality for arbitrary candidate subsets $T$.
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.
/-- Double counting: the total number of approvals, summed over candidates, is at most the number of voters when every ballot approves at most one candidate. -/private lemma ejr_chain_singleton_ballots_sum_support_le {n m : ℕ} (A : Fin n → Finset (Fin m)) (hA : ∀ i, (A i).card ≤ 1) : ∑ c : Fin m, (Finset.univ.filter fun i => c ∈ A i).card ≤ n := by classical have h1 : ∑ c : Fin m, (Finset.univ.filter fun i : Fin n => c ∈ A i).card = ∑ c : Fin m, ∑ i : Fin n, (if c ∈ A i then 1 else 0) := by apply Finset.sum_congr rfl intro c _ rw [Finset.sum_boole] simp rw [h1, Finset.sum_comm] have h2 : ∑ i : Fin n, ∑ c : Fin m, (if c ∈ A i then 1 else 0) = ∑ i : Fin n, (A i).card := by apply Finset.sum_congr rfl intro i _ rw [Finset.sum_boole] simp rw [h2] calc ∑ i : Fin n, (A i).card ≤ ∑ i : Fin n, 1 := Finset.sum_le_sum (fun i _ => hA i) _ = n := by simp/-- Scheduling lemma: if the total weight `∑ s` is at most `n > 0`, the candidates can beordered so that a candidate `c` placed at 0-based position `σ c` satisfies `s c * σ c < n`;sorting by non-increasing weight works. -/private lemma ejr_chain_singleton_ballots_exists_perm {m n : ℕ} (s : Fin m → ℕ) (hn : 0 < n) (hsum : ∑ c, s c ≤ n) : ∃ σ : Equiv.Perm (Fin m), ∀ c, s c * (σ c : ℕ) < n := by classical set atPos : Equiv.Perm (Fin m) := Tuple.sort (fun c : Fin m => OrderDual.toDual (s c)) with hatPos have hmono : Monotone ((fun c : Fin m => OrderDual.toDual (s c)) ∘ atPos) := Tuple.monotone_sort _ have hanti : Antitone (fun i : Fin m => s (atPos i)) := by intro a b hab exact OrderDual.toDual_le_toDual.mp (hmono hab) have key : ∀ c : Fin m, s c * ((atPos.symm c : Fin m) : ℕ) < n := by intro c set p : Fin m := atPos.symm c with hp have hpc : atPos p = c := by simp [hp] have hlt : (p : ℕ) < (Finset.univ.filter fun i : Fin m => s c ≤ s (atPos i)).card := by rw [Tuple.lt_card_ge_iff_apply_ge_of_antitone (f := fun i : Fin m => s (atPos i)) (a := s c) (j := p) hanti] simp [hpc] have hcard : (Finset.univ.filter fun i : Fin m => s c ≤ s (atPos i)).card = (Finset.univ.filter fun x : Fin m => s c ≤ s x).card := by refine Finset.card_bij (fun i _ => atPos i) ?_ ?_ ?_ · intro i hi exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, (Finset.mem_filter.mp hi).2⟩ · intro i _ j _ hij exact atPos.injective hij · intro b hb exact ⟨atPos.symm b, Finset.mem_filter.mpr ⟨Finset.mem_univ _, by simpa using (Finset.mem_filter.mp hb).2⟩, by simp⟩ have hbound : (Finset.univ.filter fun x : Fin m => s c ≤ s x).card * s c ≤ n := by have step1 : (Finset.univ.filter fun x : Fin m => s c ≤ s x).card * s c ≤ ∑ x ∈ Finset.univ.filter (fun x : Fin m => s c ≤ s x), s x := by have := Finset.card_nsmul_le_sum (Finset.univ.filter (fun x : Fin m => s c ≤ s x)) s (s c) (fun x hx => (Finset.mem_filter.mp hx).2) simpa [nsmul_eq_mul] using this have step2 : ∑ x ∈ Finset.univ.filter (fun x : Fin m => s c ≤ s x), s x ≤ ∑ x, s x := Finset.sum_le_univ_sum_of_nonneg (fun x => Nat.zero_le _) exact le_trans step1 (le_trans step2 hsum) have hp1 : (p : ℕ) + 1 ≤ (Finset.univ.filter fun x : Fin m => s c ≤ s x).card := by omega have hle : s c * ((p : ℕ) + 1) ≤ n := by rw [Nat.mul_comm] exact le_trans (Nat.mul_le_mul_right (s c) hp1) hbound by_cases hsc : s c = 0 · rw [hsc, Nat.zero_mul]; exact hn · have hpos : 0 < s c := Nat.pos_of_ne_zero hsc have hstrict : s c * (p : ℕ) < s c * ((p : ℕ) + 1) := Nat.mul_lt_mul_of_pos_left (Nat.lt_succ_self _) hpos exact lt_of_lt_of_le hstrict hle exact ⟨atPos.symm, key⟩/-- The chain target holds when every voter approves at most one candidate. -/theorem ejr_chain_singleton_ballots {n m : ℕ} (A : Fin n → Finset (Fin m)) (hn : 0 < n) (hA : ∀ i, (A i).card ≤ 1) : ∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m → is_ejr_committee A k (Finset.univ.filter fun c => (σ c : ℕ) < k) := by classical set s : Fin m → ℕ := fun c => (Finset.univ.filter fun i => c ∈ A i).card with hs have hsum : ∑ c, s c ≤ n := ejr_chain_singleton_ballots_sum_support_le A hA obtain ⟨σ, hσ⟩ := ejr_chain_singleton_ballots_exists_perm s hn hsum refine (ejr_chain_iff_level_supporters A).mpr ⟨σ, ?_⟩ intro k hk T hT set W : Finset (Fin m) := Finset.univ.filter fun c => (σ c : ℕ) < k with hW rcases Nat.lt_or_ge T.card 2 with h2 | h2 · have hT1 : T.card = 1 := by have hpos : 0 < T.card := Finset.card_pos.mpr hT omega obtain ⟨c, rfl⟩ := Finset.card_eq_one.mp hT1 have hsupp : (Finset.univ.filter fun i => ({c} : Finset (Fin m)) ⊆ A i ∧ (A i ∩ W).card < 1) = Finset.univ.filter fun i => c ∈ A i ∧ c ∉ W := by apply Finset.filter_congr intro i _ constructor · rintro ⟨hsub, hlt⟩ refine ⟨hsub (Finset.mem_singleton_self c), ?_⟩ intro hcW have hpos : 0 < (A i ∩ W).card := Finset.card_pos.mpr ⟨c, Finset.mem_inter.mpr ⟨hsub (Finset.mem_singleton_self c), hcW⟩⟩ omega · rintro ⟨hc, hcW⟩ refine ⟨Finset.singleton_subset_iff.mpr hc, ?_⟩ have hempty : ¬ (A i ∩ W).Nonempty := by rintro ⟨x, hx⟩ obtain ⟨hxA, hxW⟩ := Finset.mem_inter.mp hx have hxc : x = c := Finset.card_le_one.mp (hA i) x hxA c hc exact hcW (hxc ▸ hxW) rw [Finset.card_eq_zero.mpr (Finset.not_nonempty_iff_eq_empty.mp hempty)] exact Nat.zero_lt_one rw [Finset.card_singleton, hsupp, Nat.one_mul] by_cases hcW : c ∈ W · have hempty : (Finset.univ.filter fun i : Fin n => c ∈ A i ∧ c ∉ W) = ∅ := by apply Finset.filter_false_of_mem intro i _ h exact h.2 hcW rw [hempty, Finset.card_empty, Nat.zero_mul] exact hn · have hksig : k ≤ (σ c : ℕ) := by rw [hW] at hcW simp only [Finset.mem_filter, Finset.mem_univ, true_and, not_lt] at hcW exact hcW have hcard : (Finset.univ.filter fun i : Fin n => c ∈ A i ∧ c ∉ W).card ≤ s c := by rw [hs] apply Finset.card_le_card intro i hi exact Finset.mem_filter.mpr ⟨Finset.mem_univ _, (Finset.mem_filter.mp hi).2.1⟩ calc (Finset.univ.filter fun i : Fin n => c ∈ A i ∧ c ∉ W).card * k ≤ s c * k := Nat.mul_le_mul_right k hcard _ ≤ s c * (σ c : ℕ) := Nat.mul_le_mul_left (s c) hksig _ < n := hσ c · have hempty : (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < T.card) = ∅ := by apply Finset.filter_false_of_mem intro i _ h have h1 : T.card ≤ (A i).card := Finset.card_le_card h.1 have h2 := hA i omega rw [hempty, Finset.card_empty, Nat.zero_mul] exact Nat.mul_pos (by omega) hn