ejr_good_of_low_support_candidate
If candidate c is approved by fewer than n/m voters (m times its supporter count is below n), then for any k-committee P with c not in P, EJR holds as soon as it holds for all demand-sets T not containing c.
Statement
theorem ejr_good_of_low_support_candidate (n m : ℕ) (A : Fin n → Finset (Fin m)) (hn : 0 < n) (c : Fin m) (hc : m * (Finset.univ.filter fun i => c ∈ A i).card < n) (P : Finset (Fin m)) (hp : c ∉ P) (k : ℕ) (hkP : P.card = k) (h : ∀ T : Finset (Fin m), T.Nonempty → c ∉ T → (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ P).card < T.card).card * k < T.card * n) : is_ejr_committee A k P
- Source
- step towards ejr_committee_monotone_chain_exists
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- is_ejr_committee_iff_candidate_subsetsEJR is equivalent to the correct committee size together with the underrepresented-supporter inequality for every nonempty candidate…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - 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| ≥ ℓ.
- Used by 1
- ejr_chain_of_low_support_candidateIf candidate c is approved by fewer than n/m voters and the profile with c deleted (transported along e) admits an EJR chain, then so does…
The proof, explained
The theorem uses the demand-set characterization of Extended Justified Representation (EJR), where every non-empty candidate set T must have fewer than |T| * n / k under-represented supporters in committee P. By hypothesis, this condition is already known to hold for all candidate sets T that do not contain c. For any demand-set T that does contain c, any voter approving T must approve c, so the number of such voters is bounded by the total support of c. Since c has low support (m times its supporter count is strictly less than n), committee size satisfies k ≤ m, and |T| ≥ 1, this demand-set constraint is satisfied automatically.
To show that P is an EJR committee of size k, it suffices to verify the demand-set condition for every non-empty candidate subset T.
By the equivalence theorem `is_ejr_committee_iff_candidate_subsets`, P is an EJR committee if and only if |P| = k (which is given by hypothesis `hkP`) and every non-empty subset T of candidates satisfies the strict inequality |{i | T ⊆ A i ∧ |A i ∩ P| < |T|}| * k < |T| * n. We fix an arbitrary non-empty candidate subset T.
uses
is_ejr_committee_iff_candidate_subsetsrw [is_ejr_committee_iff_candidate_subsets] refine ⟨hkP, fun T hT => ?_⟩
When c ∈ T, the number of voters approving T with fewer than |T| committee members is at most the total number of voters approving candidate c.
We split into cases on whether candidate c belongs to T. In the positive case c ∈ T, every voter i who approves all of T must approve c, because c ∈ T ⊆ A i. Using `Finset.mem_filter`, this containment implies that the set of voters approving T with fewer than |T| representatives in P is a subset of the voters approving c. By `Finset.card_le_card`, its cardinality is therefore bounded by the number of voters approving c.
uses
Finset.mem_filter,Finset.card_le_cardby_cases hcT : c ∈ T · have hsub : (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ P).card < T.card) ⊆ (Finset.univ.filter fun i => c ∈ A i) := by intro i hi rw [Finset.mem_filter] at hi ⊢ refine ⟨hi.1, hi.2.1 hcT⟩ have hcard : (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ P).card < T.card).card ≤ (Finset.univ.filter fun i => c ∈ A i).card := Finset.card_le_card hsub
The committee size satisfies k ≤ m, and multiplying by the previous bound gives |{i | T ⊆ A i ∧ |A i ∩ P| < |T|}| * k ≤ |{i | c ∈ A i}| * m.
Since P is a committee of candidates from the m-element universe Fin m, its size k = |P| cannot exceed m by `Finset.card_le_univ`. Multiplying this inequality with the voter-count bound from the previous step via `Nat.mul_le_mul` yields the scaled inequality.
uses
Finset.card_le_univ,Nat.mul_le_mulhave hk_le_m : k ≤ m := by rw [← hkP] have : P.card ≤ (Finset.univ : Finset (Fin m)).card := Finset.card_le_univ P simpa using this have h1 : (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ P).card < T.card).card * k ≤ (Finset.univ.filter fun i => c ∈ A i).card * m := Nat.mul_le_mul hcard hk_le_m
When c ∈ T, the demand-set inequality |{i | T ⊆ A i ∧ |A i ∩ P| < |T|}| * k < |T| * n holds.
By the low-support hypothesis `hc`, candidate c satisfies m * |{i | c ∈ A i}| < n, which by commutativity of multiplication (`mul_comm`) becomes |{i | c ∈ A i}| * m < n. Since T is non-empty, |T| ≥ 1, so n = 1 * n ≤ |T| * n using `one_mul` and `Nat.mul_le_mul_right`. Combining |{i | T ⊆ A i ∧ |A i ∩ P| < |T|}| * k ≤ |{i | c ∈ A i}| * m < n ≤ |T| * n using linear arithmetic (`linarith`) completes the argument for this case.
uses
mul_comm,one_mul,Nat.mul_le_mul_righthave h2 : (Finset.univ.filter fun i => c ∈ A i).card * m < n := by rw [mul_comm] exact hc have h3 : n ≤ T.card * n := by have : 1 ≤ T.card := hT.card_pos calc n = 1 * n := by rw [one_mul] _ ≤ T.card * n := Nat.mul_le_mul_right n this linarith
When c ∉ T, the demand-set inequality holds directly from the hypothesis.
In the remaining case where c ∉ T, the required inequality is precisely the assumption `h` applied to T, the non-emptiness proof `hT`, and the assumption `hcT` that c ∉ T.
· exact h T hT hcT
is_ejr_committee_iff_candidate_subsets- A committee W satisfies Extended Justified Representation (EJR) for committee size k if and only if |W| = k and, for every non-empty candidate subset T, the number of voters who approve all of T but have fewer than |T| committee members in their approval set is strictly less than |T| * n / k (expressed as |{i | T ⊆ A i ∧ |A i ∩ W| < |T|}| * k < |T| * n).
Finset.mem_filter- An element a belongs to a filtered finset Finset.filter p s if and only if a ∈ s and p a holds.
Finset.card_le_card- If s is a subset of t for finite sets s and t, then |s| ≤ |t|.
Finset.card_le_univ- The cardinality of any subset of a finite type α is at most the total number of elements in α (Fintype.card α).
Nat.mul_le_mul- If n₁ ≤ n₂ and m₁ ≤ m₂, then n₁ * m₁ ≤ n₂ * m₂ for natural numbers.
mul_comm- Multiplication is commutative: a * b = b * a.
one_mul- Multiplying by 1 on the left is the identity: 1 * a = a.
Nat.mul_le_mul_right- If n ≤ m, then n * k ≤ m * k for natural numbers.
- The hypothesis `hp : c ∉ P` is included in the theorem statement but is not used anywhere in the proof, as the low-support bound on candidate `c` suffices on its own.
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.
/-- A low-support candidate imposes no EJR constraint: subsets T containing it are automatically satisfied. -/theorem ejr_good_of_low_support_candidate (n m : ℕ) (A : Fin n → Finset (Fin m)) (hn : 0 < n) (c : Fin m) (hc : m * (Finset.univ.filter fun i => c ∈ A i).card < n) (P : Finset (Fin m)) (hp : c ∉ P) (k : ℕ) (hkP : P.card = k) (h : ∀ T : Finset (Fin m), T.Nonempty → c ∉ T → (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ P).card < T.card).card * k < T.card * n) : is_ejr_committee A k P := by rw [is_ejr_committee_iff_candidate_subsets] refine ⟨hkP, fun T hT => ?_⟩ by_cases hcT : c ∈ T · have hsub : (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ P).card < T.card) ⊆ (Finset.univ.filter fun i => c ∈ A i) := by intro i hi rw [Finset.mem_filter] at hi ⊢ refine ⟨hi.1, hi.2.1 hcT⟩ have hcard : (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ P).card < T.card).card ≤ (Finset.univ.filter fun i => c ∈ A i).card := Finset.card_le_card hsub have hk_le_m : k ≤ m := by rw [← hkP] have : P.card ≤ (Finset.univ : Finset (Fin m)).card := Finset.card_le_univ P simpa using this have h1 : (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ P).card < T.card).card * k ≤ (Finset.univ.filter fun i => c ∈ A i).card * m := Nat.mul_le_mul hcard hk_le_m have h2 : (Finset.univ.filter fun i => c ∈ A i).card * m < n := by rw [mul_comm] exact hc have h3 : n ≤ T.card * n := by have : 1 ≤ T.card := hT.card_pos calc n = 1 * n := by rw [one_mul] _ ≤ T.card * n := Nat.mul_le_mul_right n this linarith · exact h T hT hcT