is_ejr_committee_iff_undersatisfied_supporters
A committee W of size k satisfies EJR exactly when, for each positive ell and each ell-element candidate set T, fewer than ell*n/k voters both approve every member of T and approve fewer than ell members of W, stated without division as underrepresented-supporter count times k < ell*n.
Statement
theorem is_ejr_committee_iff_undersatisfied_supporters {n m : ℕ} (A : Fin n → Finset (Fin m)) (k : ℕ) (W : Finset (Fin m)) : is_ejr_committee A k W ↔ W.card = k ∧ ∀ ℓ, 1 ≤ ℓ → ∀ T : Finset (Fin m), T.card = ℓ → (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < ℓ).card * k < ℓ * n
- Source
- Helper for ejr_committee_monotone_chain_exists (OP-22; arXiv:2007.01795, open problems Q2): finite witness criterion used in exact profile synthesis and committee-subset dynamic programming.
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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| ≥ ℓ.
- is_ejr_cohesive_groupFor committee size k, a group G of the n voters is ℓ-cohesive if |G| ≥ ℓ·n/k and |∩_{i∈G} A_i| ≥ ℓ.
- Used by 1
- is_ejr_committee_iff_candidate_subsetsEJR is equivalent to the correct committee size together with the underrepresented-supporter inequality for every nonempty candidate…
The proof, explained
The theorem establishes that a committee W satisfies Extended Justified Representation (EJR) if and only if |W| = k and every ℓ-candidate set T has fewer than ℓ*n/k undersatisfied supporters (voters approving T who receive fewer than ℓ members of W). In the forward direction, if T had at least ℓ*n/k undersatisfied supporters, those voters would form an ℓ-cohesive group in which nobody receives ℓ committee members, contradicting EJR. In the backward direction, if an ℓ-cohesive group G were completely undersatisfied, choosing an ℓ-element subset T of their common approvals would make G a subset of the undersatisfied supporters of T, violating the assumed counting bound.
The equivalence decomposes into two directions: showing that an EJR committee satisfies the undersatisfied supporter bound, and conversely that the bound implies the EJR property.
We enable classical logic and split the `↔` statement into its forward (`→`) and backward (`←`) directions.
classical constructorIn the forward direction, |W| = k, and it suffices to show that for every ℓ ≥ 1 and every candidate set T of size ℓ, the number of undersatisfied supporters of T satisfies the strict upper bound.
Assuming that W is an EJR committee, its size is k by definition. We then fix ℓ ≥ 1 and an arbitrary set T of ℓ candidates, aiming to establish the cardinality bound.
· intro h refine ⟨h.1, ?_⟩ intro ℓ hℓ T hT
Assuming for contradiction that the bound fails for T, the set G of voters who approve T and have |A(i) ∩ W| < ℓ satisfies ℓ * n ≤ |G| * k.
Suppose for contradiction that the strict inequality fails. Let G be the set of voters i who approve all of T and approve fewer than ℓ members of W. By Nat.le_of_not_gt, the negation of the strict inequality gives ℓ * n ≤ |G| * k.
uses
Nat.le_of_not_gtby_contra hbad let G := Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < ℓ have hsize : ℓ * n ≤ G.card * k := Nat.le_of_not_gt hbad
The group G is an ℓ-cohesive group.
Every voter in G approves every candidate in T by definition of G, so T is a subset of the candidates unanimously approved by G. Since |T| = ℓ, monotonicity of cardinality (Finset.card_le_card) implies that the set of unanimously approved candidates has size at least ℓ. Combined with ℓ * n ≤ |G| * k, this means G meets both requirements of an ℓ-cohesive group.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_filter.mp,Finset.card_le_cardhave hsub : T ⊆ Finset.univ.filter fun c => ∀ i ∈ G, c ∈ A i := by intro c hc simp only [Finset.mem_filter, Finset.mem_univ, true_and] intro i hi exact (Finset.mem_filter.mp hi).2.1 hc have hcoh : is_ejr_cohesive_group A k ℓ G := ⟨hsize, by rw [← hT]; exact Finset.card_le_card hsub⟩
Applying the EJR property to G yields a contradiction, completing the forward direction.
Because W satisfies EJR and G is an ℓ-cohesive group, there must exist some voter i ∈ G who approves at least ℓ members of W, so |A(i) ∩ W| ≥ ℓ. However, every voter in G approves strictly fewer than ℓ members of W by definition of G. These two inequalities contradict each other.
uses
Finset.mem_filter.mpobtain ⟨i, hi, hsat⟩ := h.2 ℓ hℓ G hcoh have hlt := (Finset.mem_filter.mp hi).2.2 omega
In the backward direction, assuming |W| = k and the bound on undersatisfied supporters, to prove W is an EJR committee it suffices to show that every ℓ-cohesive group G contains a voter who approves at least ℓ committee members.
We assume |W| = k and that the bound holds for all ℓ and sets T of size ℓ. For an arbitrary ℓ ≥ 1 and ℓ-cohesive group G, we suppose for contradiction that no voter in G approves ℓ or more committee members; that is, every i ∈ G satisfies |A(i) ∩ W| < ℓ.
· rintro ⟨hcard, h⟩ refine ⟨hcard, ?_⟩ intro ℓ hℓ G hcoh by_contra hnone push Not at hnoneThere exists an ℓ-element candidate set T such that G ⊆ H, where H is the set of undersatisfied supporters of T.
Since G is ℓ-cohesive, the set of candidates approved by all voters in G has size at least ℓ. By Finset.exists_subset_card_eq, we can choose an exact subset T of ℓ such candidates. Letting H be the set of voters who approve T and have |A(i) ∩ W| < ℓ, every voter in G belongs to H because they approve all candidates in T and, by the contradiction hypothesis, have |A(i) ∩ W| < ℓ.
uses
Finset.exists_subset_card_eq,Finset.mem_filter.mpr,Finset.mem_univ,Finset.mem_filter.mpobtain ⟨T, hTsub, hTcard⟩ := Finset.exists_subset_card_eq hcoh.2 let H := Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < ℓ have hGH : G ⊆ H := by intro i hi apply Finset.mem_filter.mpr refine ⟨Finset.mem_univ _, ?_, ?_⟩ · intro c hc exact (Finset.mem_filter.mp (hTsub hc)).2 i hi · exact hnone i hi
The inclusion G ⊆ H leads to a numerical contradiction, completing the proof.
From G ⊆ H, we have |G| * k ≤ |H| * k by Nat.mul_le_mul_right and Finset.card_le_card. Applying the hypothesis to the ℓ-element set T gives |H| * k < ℓ * n. Meanwhile, cohesiveness of G gives ℓ * n ≤ |G| * k. Combining these yields ℓ * n ≤ |G| * k ≤ |H| * k < ℓ * n, an impossible chain of inequalities.
uses
Nat.mul_le_mul_right,Finset.card_le_cardhave hle := Nat.mul_le_mul_right k (Finset.card_le_card hGH) have hlt := h ℓ hℓ T hTcard have hsize := hcoh.1 change H.card * k < ℓ * n at hlt omega
Nat.le_of_not_gt- For natural numbers, if b is not strictly greater than a, then b ≤ a.
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the base set and satisfies the filtering predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
true_and- The conjunction True ∧ p simplifies to p.
Finset.mem_filter.mp- Membership in a filtered finset implies membership in the base set and satisfaction of the predicate.
Finset.card_le_card- If s ⊆ t for finite sets s and t, then |s| ≤ |t|.
Finset.exists_subset_card_eq- If a finite set has cardinality at least n, it contains a subset of cardinality exactly n.
Finset.mem_filter.mpr- If an element belongs to the base set and satisfies the predicate, it belongs to the filtered finset.
Nat.mul_le_mul_right- Multiplying both sides of a natural number inequality n ≤ m on the right by k yields n * k ≤ m * k.
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.
theorem is_ejr_committee_iff_undersatisfied_supporters {n m : ℕ} (A : Fin n → Finset (Fin m)) (k : ℕ) (W : Finset (Fin m)) : is_ejr_committee A k W ↔ W.card = k ∧ ∀ ℓ, 1 ≤ ℓ → ∀ T : Finset (Fin m), T.card = ℓ → (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < ℓ).card * k < ℓ * n := by classical constructor · intro h refine ⟨h.1, ?_⟩ intro ℓ hℓ T hT by_contra hbad let G := Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < ℓ have hsize : ℓ * n ≤ G.card * k := Nat.le_of_not_gt hbad have hsub : T ⊆ Finset.univ.filter fun c => ∀ i ∈ G, c ∈ A i := by intro c hc simp only [Finset.mem_filter, Finset.mem_univ, true_and] intro i hi exact (Finset.mem_filter.mp hi).2.1 hc have hcoh : is_ejr_cohesive_group A k ℓ G := ⟨hsize, by rw [← hT]; exact Finset.card_le_card hsub⟩ obtain ⟨i, hi, hsat⟩ := h.2 ℓ hℓ G hcoh have hlt := (Finset.mem_filter.mp hi).2.2 omega · rintro ⟨hcard, h⟩ refine ⟨hcard, ?_⟩ intro ℓ hℓ G hcoh by_contra hnone push Not at hnone obtain ⟨T, hTsub, hTcard⟩ := Finset.exists_subset_card_eq hcoh.2 let H := Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < ℓ have hGH : G ⊆ H := by intro i hi apply Finset.mem_filter.mpr refine ⟨Finset.mem_univ _, ?_, ?_⟩ · intro c hc exact (Finset.mem_filter.mp (hTsub hc)).2 i hi · exact hnone i hi have hle := Nat.mul_le_mul_right k (Finset.card_le_card hGH) have hlt := h ℓ hℓ T hTcard have hsize := hcoh.1 change H.card * k < ℓ * n at hlt omega