ejr_committee_univ
For every approval profile with at least one voter, the committee consisting of all m candidates satisfies EJR at committee size m.
Statement
theorem ejr_committee_univ {n m : ℕ} (A : Fin n → Finset (Fin m)) (hn : 0 < n) :
is_ejr_committee A m Finset.univ- Source
- step towards ejr_committee_monotone_chain_exists
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- is_ejr_committee_iff_candidate_subsetsEJR is equivalent to the correct committee size together with the underrepresented-supporter inequality for every nonempty candidate…
- 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 2
- 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_chain_candidates_le_threeEvery approval profile on at most three candidates admits an EJR committee chain.
The proof, explained
The proof uses the equivalent candidate-subset characterization of Extended Justified Representation (EJR), which requires that the committee has size m and that every non-empty candidate set T satisfies a representation inequality. The size condition holds immediately because the universal set on m candidates has cardinality m. For the representation inequality, because the committee contains all m candidates, any voter approving all candidates in T already has at least |T| approved candidates in the committee, so no voter qualifies and the set of dissatisfied voters is empty. The left-hand side therefore evaluates to zero, which is strictly less than |T| · n because both T and the electorate are non-empty.
The theorem reduces to showing that the full committee has size m and that every non-empty candidate subset satisfies the candidate-subset representation inequality.
By is_ejr_committee_iff_candidate_subsets, satisfying EJR at committee size m is equivalent to having cardinality m and satisfying, for every non-empty candidate subset T, that the number of voters approving all of T with fewer than |T| approved committee candidates, multiplied by m, is strictly less than |T| · n. The goal is split into these two conjuncts.
uses
is_ejr_committee_iff_candidate_subsetsrw [is_ejr_committee_iff_candidate_subsets] constructor
The full committee has size m. automation
The committee consists of Finset.univ for candidates Fin m, whose cardinality is m by definition; the simplifier evaluates this directly.
· simpFix an arbitrary non-empty candidate subset T.
We introduce the candidate set T along with the hypothesis hT that T is non-empty.
· intro T hTNo voter can approve all of T while approving strictly fewer than |T| candidates in the full committee; hence the set of such voters is empty.
By Finset.filter_eq_empty_iff.mpr, it suffices to show no voter i satisfies both conditions. Because the committee is Finset.univ, voter i's approved committee candidates A(i) ∩ Finset.univ simplify to A(i) by Finset.inter_univ. If voter i approves all of T (T ⊆ A(i)), then |T| ≤ |A(i)| by Finset.card_le_card. This contradicts the condition |A(i)| < |T| via not_le.mpr.
uses
Finset.filter_eq_empty_iff.mpr,Finset.inter_univ,Finset.card_le_card,not_le.mprhave hfilter : (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ Finset.univ).card < T.card) = ∅ := by apply Finset.filter_eq_empty_iff.mpr intro i _ rw [Finset.inter_univ] rintro ⟨hsub, hlt⟩ exact absurd (Finset.card_le_card hsub) (not_le.mpr hlt)
The candidate-subset inequality holds for T.
Replacing the filtered voter set with ∅, its cardinality is 0 by Finset.card_empty, so the left-hand side reduces to 0 · m = 0 by Nat.zero_mul. On the right-hand side, |T| > 0 by Finset.card_pos.mpr because T is non-empty, and n > 0 by hypothesis hn, so their product |T| · n is strictly positive by Nat.mul_pos, completing the inequality 0 < |T| · n.
uses
Finset.card_empty,Nat.zero_mul,Nat.mul_pos,Finset.card_pos.mprrw [hfilter] simp only [Finset.card_empty, Nat.zero_mul] exact Nat.mul_pos (Finset.card_pos.mpr hT) hn
is_ejr_committee_iff_candidate_subsets- A committee W of size k satisfies EJR if and only if |W| = k and, for every non-empty set of candidates T, the number of voters who approve all of T but have fewer than |T| committee members in their approval set, multiplied by k, is strictly less than |T| · n.
Finset.filter_eq_empty_iff.mpr- A filtered finite set is empty if no element of the ambient set satisfies the filtering condition.
Finset.inter_univ- The intersection of any finite set with the universal set of its type is the set itself.
Finset.card_le_card- If s ⊆ t for finite sets s and t, then |s| ≤ |t|.
not_le.mpr- If b < a, then ¬(a ≤ b).
Finset.card_empty- The empty set has cardinality 0.
Nat.zero_mul- 0 · n = 0 for any natural number n.
Nat.mul_pos- The product of two strictly positive natural numbers is strictly positive.
Finset.card_pos.mpr- A finite set has strictly positive cardinality if and only if it is non-empty.
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.
/-- For a nonempty electorate the full committee satisfies EJR at committee size m. -/theorem ejr_committee_univ {n m : ℕ} (A : Fin n → Finset (Fin m)) (hn : 0 < n) : is_ejr_committee A m Finset.univ := by rw [is_ejr_committee_iff_candidate_subsets] constructor · simp · intro T hT have hfilter : (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ Finset.univ).card < T.card) = ∅ := by apply Finset.filter_eq_empty_iff.mpr intro i _ rw [Finset.inter_univ] rintro ⟨hsub, hlt⟩ exact absurd (Finset.card_le_card hsub) (not_le.mpr hlt) rw [hfilter] simp only [Finset.card_empty, Nat.zero_mul] exact Nat.mul_pos (Finset.card_pos.mpr hT) hn