ejr_two_voters_criterion
For 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 ∩ A 1 ⊆ W; and (3) for each voter i ∈ {0, 1}, if |A i ∩ W| < |A i| then k ≤ 2 * |A i ∩ W| + 1.
Statement
theorem ejr_two_voters_criterion {m : ℕ} (A : Fin 2 → Finset (Fin m))
(k : ℕ) (W : Finset (Fin m)) (hWcard : W.card = k)
(hA : k ≤ (A 0 ∩ A 1).card → W ⊆ A 0 ∩ A 1)
(hB : (A 0 ∩ A 1).card ≤ k → A 0 ∩ A 1 ⊆ W)
(hD : (A 0 ∩ W).card < (A 0).card → k ≤ 2 * (A 0 ∩ W).card + 1)
(hE : (A 1 ∩ W).card < (A 1).card → k ≤ 2 * (A 1 ∩ W).card + 1) :
is_ejr_committee A k W- Source
- step towards ejr_chain_two_voters
- 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_two_votersFor every approval profile with two voters and any number of candidates, there is an ordering of the candidates every prefix of which is…
The proof, explained
The proof characterizes Extended Justified Representation (EJR) using an equivalent candidate-subset condition: for any non-empty candidate set T, the set S of voters who approve all of T and have strictly fewer than |T| representatives in W must satisfy |S| * k < 2 * |T|. Since there are only two voters, |S| can only be 0, 1, or 2. If |S| = 0, the inequality is trivial; if |S| = 1, condition (3) on the single unsatisfied voter bounds k ≤ 2 * |A i ∩ W| + 1 < 2 * |T|; and if |S| = 2, both voters approve T, and assuming |T| ≤ k produces a contradiction using either condition (1) or (2) depending on how k compares to |A 0 ∩ A 1|.
To establish that W is an EJR committee, it suffices to show that |S| * k < 2 * |T| for every non-empty candidate set T, where S is the set of voters i ∈ {0, 1} who approve all of T and have |A i ∩ W| < |T|.
By is_ejr_committee_iff_candidate_subsets, a committee W satisfies EJR if and only if |W| = k and for every non-empty subset of candidates T, |S| * k < |T| * n, where n = 2 is the number of voters and S consists of voters approving T with strictly fewer than |T| representatives in W. The cardinality condition |W| = k is directly provided by hWcard, leaving only the inequality to verify for an arbitrary non-empty T.
uses
is_ejr_committee_iff_candidate_subsetsrw [is_ejr_committee_iff_candidate_subsets] refine ⟨hWcard, fun T hT => ?_⟩
|T| > 0, and the number of unsatisfied voters |S| is at most 2.
Since T is non-empty, its cardinality is strictly positive (Finset.Nonempty.card_pos). Defining S as the set of voters in Fin 2 who approve T and have |A i ∩ W| < |T|, S is a subset of the two-element type Fin 2, so |S| ≤ 2 by Finset.card_le_univ.
uses
Finset.Nonempty.card_pos,Finset.card_le_univhave hTpos : 0 < T.card := Finset.Nonempty.card_pos hT generalize hS : (Finset.univ.filter fun i : Fin 2 => T ⊆ A i ∧ (A i ∩ W).card < T.card) = S have hS_le : S.card ≤ 2 := by rw [← hS] have := Finset.card_le_univ (Finset.univ.filter fun i : Fin 2 => T ⊆ A i ∧ (A i ∩ W).card < T.card) simpa using this
The inequality |S| * k < 2 * |T| holds when |S| = 0.
We perform a case split on |S| ∈ {0, 1, 2}. When |S| = 0, the left-hand side reduces to 0 * k = 0 by zero_mul. Since |T| > 0 and 2 > 0, their product 2 * |T| is strictly positive by mul_pos, satisfying 0 < 2 * |T|.
uses
zero_mul,mul_posinterval_cases hSc : S.card · rw [zero_mul] exact mul_pos hTpos (by decide)
The inequality |S| * k < 2 * |T| holds when |S| = 1.
When |S| = 1, S consists of a unique voter i ∈ {0, 1} (Finset.card_eq_one.mp). In either case (i = 0 or i = 1), voter i satisfies T ⊆ A i and |A i ∩ W| < |T|. Since T ⊆ A i implies |T| ≤ |A i|, we have |A i ∩ W| < |A i|. The corresponding hypothesis (hD for voter 0, hE for voter 1) gives k ≤ 2 * |A i ∩ W| + 1. Since |A i ∩ W| ≤ |T| - 1, linear arithmetic over ℕ establishes k < 2 * |T|.
uses
Finset.card_eq_one.mp,Finset.mem_singleton_self,Finset.mem_filter,Finset.card_le_card,lt_of_lt_of_le· obtain ⟨i, hi⟩ := Finset.card_eq_one.mp hSc have hiS : i ∈ S := by rw [hi]; exact Finset.mem_singleton_self i rw [← hS, Finset.mem_filter] at hiS fin_cases i · dsimp at hiS obtain ⟨-, hsub, hlt⟩ := hiS have hTleA : T.card ≤ (A 0).card := Finset.card_le_card hsub have hltA : (A 0 ∩ W).card < (A 0).card := lt_of_lt_of_le hlt hTleA have hk := hD hltA linarith · dsimp at hiS obtain ⟨-, hsub, hlt⟩ := hiS have hTleA : T.card ≤ (A 1).card := Finset.card_le_card hsub have hltA : (A 1 ∩ W).card < (A 1).card := lt_of_lt_of_le hlt hTleA have hk := hE hltA linarith
When |S| = 2, both voters approve T (so T ⊆ A 0 ∩ A 1), and assuming for contradiction that 2 * k < 2 * |T| fails implies |T| ≤ k.
Since |S| = 2, S must be all of Fin 2 (Finset.eq_univ_of_card). Thus both 0 ∈ S and 1 ∈ S, which means T ⊆ A 0, T ⊆ A 1, and |A i ∩ W| < |T| for both voters. In particular, T ⊆ A 0 ∩ A 1 by Finset.subset_inter. Assuming for contradiction that ¬(2 * k < 2 * |T|), linear arithmetic gives |T| ≤ k.
uses
Finset.eq_univ_of_card,Finset.mem_univ,Finset.mem_filter,Finset.subset_inter· have hS_univ : S = Finset.univ := Finset.eq_univ_of_card S (by simpa using hSc) have h0S : (0 : Fin 2) ∈ S := by rw [hS_univ]; exact Finset.mem_univ 0 have h1S : (1 : Fin 2) ∈ S := by rw [hS_univ]; exact Finset.mem_univ 1 rw [← hS, Finset.mem_filter] at h0S h1S obtain ⟨-, hT0, hlt0⟩ := h0S obtain ⟨-, hT1, hlt1⟩ := h1S have hTsub : T ⊆ A 0 ∩ A 1 := Finset.subset_inter hT0 hT1 by_contra hnot have hTk : T.card ≤ k := by linarith
A contradiction arises in the subcase |A 0 ∩ A 1| ≤ k.
By le_total, either |A 0 ∩ A 1| ≤ k or k ≤ |A 0 ∩ A 1|. If |A 0 ∩ A 1| ≤ k, hypothesis hB implies A 0 ∩ A 1 ⊆ W. Since T ⊆ A 0 ∩ A 1, we get T ⊆ W by transitivity, and together with T ⊆ A 0 this yields T ⊆ A 0 ∩ W. Hence |T| ≤ |A 0 ∩ W|, contradicting the fact that 0 ∈ S requires |A 0 ∩ W| < |T|.
uses
le_total,Finset.Subset.trans,Finset.subset_inter,Finset.card_le_cardrcases le_total ((A 0 ∩ A 1).card) k with hle | hle · have hsubW : A 0 ∩ A 1 ⊆ W := hB hle have hTW : T ⊆ W := Finset.Subset.trans hTsub hsubW have hT0W : T ⊆ A 0 ∩ W := Finset.subset_inter hT0 hTW have hle_card : T.card ≤ (A 0 ∩ W).card := Finset.card_le_card hT0W linarith
A contradiction arises in the subcase k ≤ |A 0 ∩ A 1|.
If k ≤ |A 0 ∩ A 1|, hypothesis hA implies W ⊆ A 0 ∩ A 1. Since A 0 ∩ A 1 ⊆ A 0, transitivity gives W ⊆ A 0, which means A 0 ∩ W = W (Finset.inter_eq_right.mpr). Therefore |A 0 ∩ W| = |W| = k. But 0 ∈ S gives k = |A 0 ∩ W| < |T|, which contradicts |T| ≤ k.
uses
Finset.Subset.trans,Finset.inter_subset_left,Finset.inter_eq_right.mpr· have hWsub : W ⊆ A 0 ∩ A 1 := hA hle have hW0 : W ⊆ A 0 := Finset.Subset.trans hWsub Finset.inter_subset_left have hAW : A 0 ∩ W = W := Finset.inter_eq_right.mpr hW0 have hcard : (A 0 ∩ W).card = k := by rw [hAW, hWcard] linarith
is_ejr_committee_iff_candidate_subsets- A committee W of size k satisfies EJR for a profile of n voters if and only if for every non-empty candidate set T, the number of voters who approve T and have strictly fewer than |T| committee members in W, multiplied by k, is strictly less than |T| * n.
Finset.Nonempty.card_pos- A finite set is non-empty if and only if its cardinality is strictly positive.
Finset.card_le_univ- The cardinality of any finset of a finite type is at most the cardinality of the full type.
zero_mul- Zero multiplied by any element is zero: 0 * a = 0.
mul_pos- The product of two strictly positive elements in a preordered ring is strictly positive.
Finset.card_eq_one.mp- If a finset has cardinality 1, then it is a singleton {a} for some element a.
Finset.mem_singleton_self- Any element belongs to its own singleton set: a ∈ {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.card_le_card- If s ⊆ t, then |s| ≤ |t|.
lt_of_lt_of_le- Strict inequality is transitive with non-strict inequality: if a < b and b ≤ c, then a < c.
Finset.eq_univ_of_card- A subset of a finite type whose cardinality equals the cardinality of the whole type is the entire universe set.
Finset.mem_univ- Every element of a finite type belongs to the universal finset Finset.univ.
Finset.subset_inter- If s ⊆ u and s ⊆ v, then s ⊆ u ∩ v.
le_total- In any linear order, any two elements are comparable: a ≤ b ∨ b ≤ a.
Finset.Subset.trans- Subset inclusion is transitive: if s₁ ⊆ s₂ and s₂ ⊆ s₃, then s₁ ⊆ s₃.
Finset.inter_subset_left- The intersection of two sets is a subset of the first set: s₁ ∩ s₂ ⊆ s₁.
Finset.inter_eq_right.mpr- If t ⊆ s, then s ∩ t = t.
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 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 ∩ A 1 ⊆ W; and (3) for each voter i ∈ {0, 1}, if |A i ∩ W| < |A i| then k ≤ 2 * |A i ∩ W| + 1. -/theorem ejr_two_voters_criterion {m : ℕ} (A : Fin 2 → Finset (Fin m)) (k : ℕ) (W : Finset (Fin m)) (hWcard : W.card = k) (hA : k ≤ (A 0 ∩ A 1).card → W ⊆ A 0 ∩ A 1) (hB : (A 0 ∩ A 1).card ≤ k → A 0 ∩ A 1 ⊆ W) (hD : (A 0 ∩ W).card < (A 0).card → k ≤ 2 * (A 0 ∩ W).card + 1) (hE : (A 1 ∩ W).card < (A 1).card → k ≤ 2 * (A 1 ∩ W).card + 1) : is_ejr_committee A k W := by rw [is_ejr_committee_iff_candidate_subsets] refine ⟨hWcard, fun T hT => ?_⟩ have hTpos : 0 < T.card := Finset.Nonempty.card_pos hT generalize hS : (Finset.univ.filter fun i : Fin 2 => T ⊆ A i ∧ (A i ∩ W).card < T.card) = S have hS_le : S.card ≤ 2 := by rw [← hS] have := Finset.card_le_univ (Finset.univ.filter fun i : Fin 2 => T ⊆ A i ∧ (A i ∩ W).card < T.card) simpa using this interval_cases hSc : S.card · rw [zero_mul] exact mul_pos hTpos (by decide) · obtain ⟨i, hi⟩ := Finset.card_eq_one.mp hSc have hiS : i ∈ S := by rw [hi]; exact Finset.mem_singleton_self i rw [← hS, Finset.mem_filter] at hiS fin_cases i · dsimp at hiS obtain ⟨-, hsub, hlt⟩ := hiS have hTleA : T.card ≤ (A 0).card := Finset.card_le_card hsub have hltA : (A 0 ∩ W).card < (A 0).card := lt_of_lt_of_le hlt hTleA have hk := hD hltA linarith · dsimp at hiS obtain ⟨-, hsub, hlt⟩ := hiS have hTleA : T.card ≤ (A 1).card := Finset.card_le_card hsub have hltA : (A 1 ∩ W).card < (A 1).card := lt_of_lt_of_le hlt hTleA have hk := hE hltA linarith · have hS_univ : S = Finset.univ := Finset.eq_univ_of_card S (by simpa using hSc) have h0S : (0 : Fin 2) ∈ S := by rw [hS_univ]; exact Finset.mem_univ 0 have h1S : (1 : Fin 2) ∈ S := by rw [hS_univ]; exact Finset.mem_univ 1 rw [← hS, Finset.mem_filter] at h0S h1S obtain ⟨-, hT0, hlt0⟩ := h0S obtain ⟨-, hT1, hlt1⟩ := h1S have hTsub : T ⊆ A 0 ∩ A 1 := Finset.subset_inter hT0 hT1 by_contra hnot have hTk : T.card ≤ k := by linarith rcases le_total ((A 0 ∩ A 1).card) k with hle | hle · have hsubW : A 0 ∩ A 1 ⊆ W := hB hle have hTW : T ⊆ W := Finset.Subset.trans hTsub hsubW have hT0W : T ⊆ A 0 ∩ W := Finset.subset_inter hT0 hTW have hle_card : T.card ≤ (A 0 ∩ W).card := Finset.card_le_card hT0W linarith · have hWsub : W ⊆ A 0 ∩ A 1 := hA hle have hW0 : W ⊆ A 0 := Finset.Subset.trans hWsub Finset.inter_subset_left have hAW : A 0 ∩ W = W := Finset.inter_eq_right.mpr hW0 have hcard : (A 0 ∩ W).card = k := by rw [hAW, hWcard] linarith