is_ejr_committee_iff_candidate_subsets
EJR is equivalent to the correct committee size together with the underrepresented-supporter inequality for every nonempty candidate subset T, with demand |T|. All remaining quantifiers range over finite types.
Statement
theorem is_ejr_committee_iff_candidate_subsets {n m : ℕ} (A : Fin n → Finset (Fin m)) (k : ℕ) (W : Finset (Fin m)) : is_ejr_committee A k W ↔ W.card = k ∧ ∀ T : Finset (Fin m), T.Nonempty → (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < T.card).card * k < T.card * n
- Source
- Finite version of is_ejr_committee_iff_undersatisfied_supporters for OP-22 computational certificates: eliminate the unbounded demand quantifier by taking the demand to be the common candidate subset cardinality.
- Verified
- 24 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- is_ejr_committee_iff_undersatisfied_supportersA 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…
- 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 9
- 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…
- ejr_good_of_low_support_candidateIf 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_chain_of_deletable_voterIf a voter's ballot is empty or misses at most one candidate, deleting that voter preserves the existence of an EJR chain: the same…
- ejr_committee_nine_without_three_subsetThere is an approval profile with nine voters and eleven candidates and an EJR committee of size nine that contains no EJR committee of…
- 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…
- ejr_two_voters_criterionFor two voters, a committee W of size k satisfies EJR whenever: (1) if k ≤ |A 0 ∩ A 1| then W ⊆ A 0 ∩ A 1; (2) if |A 0 ∩ A 1| ≤ k then A 0…
- ejr_committee_univFor every approval profile with at least one voter, the committee consisting of all m candidates satisfies EJR at committee size m.
- ejr_of_support_density_boundFor a nonempty electorate, the density bound with q=k+1 implies EJR for any committee of size k.
- ejr_chain_singleton_ballotsIf 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 proof, explained
By a previous characterization (`is_ejr_committee_iff_undersatisfied_supporters`), a committee W satisfies EJR if and only if |W| = k and the underrepresented-supporter inequality holds for every integer ℓ ≥ 1 and candidate subset T of size ℓ. This theorem eliminates the explicit parameter ℓ in favor of setting the demand to |T| directly for every nonempty subset T. The two conditions are equivalent because any nonempty finite set has cardinality at least 1, and conversely any set of size ℓ ≥ 1 is nonempty.
The equivalence reduces to showing the equivalence between the condition with an explicit size parameter ℓ ≥ 1 and the condition quantified over nonempty subsets T.
We invoke classical logic and rewrite the definition of an EJR committee using `is_ejr_committee_iff_undersatisfied_supporters`, which characterizes EJR as having committee size |W| = k and satisfying the underrepresented-supporter bound for every integer ℓ ≥ 1 and candidate subset T of size ℓ. We then split the equivalence into forward and backward implications.
uses
is_ejr_committee_iff_undersatisfied_supportersclassical rw [is_ejr_committee_iff_undersatisfied_supporters] constructor
If the condition holds for all ℓ ≥ 1 and subsets of size ℓ, then it holds for every nonempty candidate subset T with demand |T|.
Assuming |W| = k and that the bound holds for all ℓ ≥ 1 and subsets of size ℓ, the committee size requirement |W| = k is immediate. For any nonempty candidate subset T, its cardinality is strictly positive by `Finset.card_pos.mpr`, so 1 ≤ |T|. We instantiate the hypothesis with ℓ = |T| and T itself, using |T| = |T| by reflexivity, which yields the desired inequality.
uses
Finset.card_pos.mpr· rintro ⟨hc, h⟩ refine ⟨hc, ?_⟩ intro T hT exact h T.card (by have := Finset.card_pos.mpr hT; omega) T rflConversely, if the condition holds for every nonempty subset T with demand |T|, then it holds for every ℓ ≥ 1 and subset T of size ℓ.
Assuming |W| = k and the bound holds for every nonempty subset with demand |T|, the committee size requirement again holds immediately. Given ℓ ≥ 1 and a candidate subset T with |T| = ℓ, linear arithmetic shows 0 < |T|, so T is nonempty by `Finset.card_pos.mp`. Applying the hypothesis to T with this nonemptiness witness gives the inequality with demand |T|, and substituting |T| = ℓ produces the bound for ℓ.
uses
Finset.card_pos.mp· rintro ⟨hc, h⟩ refine ⟨hc, ?_⟩ intro ℓ hℓ T hT have hne : T.Nonempty := Finset.card_pos.mp (by omega) simpa [hT] using h T hne
is_ejr_committee_iff_undersatisfied_supporters- A committee W of size k satisfies EJR if and only if for every integer ℓ ≥ 1 and every candidate subset T with |T| = ℓ, the number of voters approving T who have fewer than ℓ committee members in their approval set satisfies |{i | T ⊆ A(i) ∧ |A(i) ∩ W| < ℓ}| · k < ℓ · n.
Finset.card_pos.mpr- If a finite set is nonempty, then its cardinality is strictly positive (0 < |s|).
Finset.card_pos.mp- If a finite set has strictly positive cardinality (0 < |s|), then it is nonempty.
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_candidate_subsets {n m : ℕ} (A : Fin n → Finset (Fin m)) (k : ℕ) (W : Finset (Fin m)) : is_ejr_committee A k W ↔ W.card = k ∧ ∀ T : Finset (Fin m), T.Nonempty → (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < T.card).card * k < T.card * n := by classical rw [is_ejr_committee_iff_undersatisfied_supporters] constructor · rintro ⟨hc, h⟩ refine ⟨hc, ?_⟩ intro T hT exact h T.card (by have := Finset.card_pos.mpr hT; omega) T rfl · rintro ⟨hc, h⟩ refine ⟨hc, ?_⟩ intro ℓ hℓ T hT have hne : T.Nonempty := Finset.card_pos.mp (by omega) simpa [hT] using h T hne