AFTD Auto-Formalizing Theoretical Domains

ejr_chain_singleton_ballots

theoremverified

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$.

  1. 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$.

    lines 5–20

    uses Finset.sum_congr, Finset.sum_boole, Finset.sum_comm, Finset.sum_le_sum

      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
  2. 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$.

    lines 27–32

    uses Tuple.sort, Tuple.monotone_sort, OrderDual.toDual_le_toDual.mp

      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)
  3. 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$.

    lines 33–64

    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_right

      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
  4. 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$.

    lines 65–71

    uses Nat.zero_mul, Nat.pos_of_ne_zero, Nat.mul_lt_mul_of_pos_left, Nat.lt_succ_self, lt_of_lt_of_le

        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⟩
  5. 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$.

    lines 78–84

    uses ejr_chain_singleton_ballots_sum_support_le, ejr_chain_singleton_ballots_exists_perm, ejr_chain_iff_level_supporters

      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
  6. 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$.

    lines 85–110

    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_mul

      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]
  7. 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$.

    lines 111–130

    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_left

        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
  8. 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$.

    lines 131–138

    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.

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

/-- 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
See it in the graphDiscuss this resultChallenge it