ejr_chain_of_nested_committees
If there are committees W_0 ⊆ W_1 ⊆ ... ⊆ W_m with W_0 empty and W_k an EJR committee of size k for every k ≤ m, then there is a permutation of the candidates whose prefix of length k is exactly W_k, hence the target chain exists.
Statement
theorem ejr_chain_of_nested_committees {n m : ℕ} (A : Fin n → Finset (Fin m)) : (∃ W : ℕ → Finset (Fin m), W 0 = ∅ ∧ (∀ k, k < m → W k ⊆ W (k + 1)) ∧ (∀ k, k ≤ m → is_ejr_committee A k (W k))) → ∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m → is_ejr_committee A k (Finset.univ.filter fun c => (σ c : ℕ) < k)
- Source
- step towards ejr_committee_monotone_chain_exists
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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| ≥ ℓ.
- exists_perm_with_prefix_eq_takeEvery duplicate-free list L of length m whose entries are the m candidates is the order of appearance of some permutation σ: for every k ≤…
- 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 3
- 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_nested_committees_iffAn approval profile admits an EJR committee chain if and only if it admits an increasing sequence of EJR committees of sizes 0 through m.
- ejr_chain_candidates_le_threeEvery approval profile on at most three candidates admits an EJR committee chain.
The proof, explained
Given a nested chain of EJR committees ∅ = W_0 ⊆ W_1 ⊆ ... ⊆ W_m, each committee W_k has cardinality k, meaning that each step adds exactly one candidate x(k) ∈ W_(k+1) \ W_k. Monotonicity of the sequence of committees ensures that these added candidates x(0), ..., x(m-1) are pairwise distinct. Ordering the candidates as a list and invoking exists_perm_with_prefix_eq_take produces a permutation σ whose prefixes of length k reconstruct each W_k, showing that the target chain of EJR committees exists.
Unpack the nested EJR committee sequence and note that each committee W_k has cardinality k.
We unpack the hypothesis into the committee sequence W, the base condition W_0 = ∅ (hW0), the one-step inclusion W_k ⊆ W_(k+1) (hmono), and the EJR property for each committee (hEJR). By definition of is_ejr_committee, an EJR committee of target size k must have cardinality k (hcard).
rintro ⟨W, hW0, hmono, hEJR⟩ have hcard : ∀ k, k ≤ m → (W k).card = k := fun k hk => (hEJR k hk).1
Each step adds exactly one candidate: |W_(k+1) \ W_k| = 1 for every k < m.
Because W_k ⊆ W_(k+1), the cardinality of the difference plus |W_k| equals |W_(k+1)| by Finset.card_sdiff_add_card_eq_card. Since |W_k| = k and |W_(k+1)| = k + 1, linear arithmetic forces the difference to have cardinality 1.
uses
Finset.card_sdiff_add_card_eq_cardhave hdiff_card : ∀ k : Fin m, (W (k.1 + 1) \ W k.1).card = 1 := by intro k have hklt : (k : ℕ) < m := k.2 have hsub : W k.1 ⊆ W (k.1 + 1) := hmono k.1 hklt have h1 := Finset.card_sdiff_add_card_eq_card hsub have h2 : (W k.1).card = k.1 := hcard k.1 (by omega) have h3 : (W (k.1 + 1)).card = k.1 + 1 := hcard (k.1 + 1) (by omega) omega
Define x(k) as the unique candidate added at step k, satisfying W_(k+1) \ W_k = {x(k)}, x(k) ∈ W_(k+1), and x(k) ∉ W_k.
Because W_(k+1) \ W_k has cardinality 1, Finset.card_eq_one.mp yields a unique element x(k) such that W_(k+1) \ W_k = {x(k)}. From Finset.mem_sdiff.mp and Finset.mem_singleton_self, this element x(k) is in W_(k+1) and not in W_k.
uses
Finset.card_eq_one.mp,Finset.mem_sdiff.mp,Finset.mem_singleton_selflet x : Fin m → Fin m := fun k => (Finset.card_eq_one.mp (hdiff_card k)).choose have hx : ∀ k : Fin m, W (k.1 + 1) \ W k.1 = {x k} := fun k => (Finset.card_eq_one.mp (hdiff_card k)).choose_spec have hx_mem' : ∀ k : Fin m, x k ∈ W (k.1 + 1) := by intro k exact (Finset.mem_sdiff.mp (by rw [hx k]; exact Finset.mem_singleton_self (x k))).1 have hx_not : ∀ k : Fin m, x k ∉ W k.1 := by intro k exact (Finset.mem_sdiff.mp (by rw [hx k]; exact Finset.mem_singleton_self (x k))).2
The committee sequence is monotonic for all indices: W_a ⊆ W_b whenever a ≤ b ≤ m.
We prove W_a ⊆ W_b by induction on b. In the base case b = 0, a ≤ 0 forces a = 0, and reflexivity (Finset.Subset.refl) gives W_0 ⊆ W_0. For the successor step b + 1, either a < b + 1 (so a ≤ b, and the result follows from the induction hypothesis W_a ⊆ W_b and one-step inclusion W_b ⊆ W_(b+1)) or a = b + 1 (which holds trivially by reflexivity).
uses
Finset.Subset.refl,lt_or_gehave hmono' : ∀ a b, a ≤ b → b ≤ m → W a ⊆ W b := by intro a b hab hbm induction b with | zero => have : a = 0 := by omega subst this; exact Finset.Subset.refl _ | succ b ih => rcases lt_or_ge a (b + 1) with hlt | hge · exact (ih (by omega) (by omega)).trans (hmono b (by omega)) · have : a = b + 1 := by omega subst this; exact Finset.Subset.refl _
The assignment x : Fin m → Fin m of added candidates is injective.
Suppose x(i) = x(j). By trichotomy (lt_trichotomy), either i < j, i = j, or j < i. If i < j, then i + 1 ≤ j, so x(i) ∈ W_(i+1) ⊆ W_j by monotonicity, which means x(j) ∈ W_j, contradicting x(j) ∉ W_j. The case j < i is symmetric. Thus i = j as natural numbers, which implies i = j in Fin m by Fin.ext.
uses
lt_trichotomy,le_of_lt,Fin.exthave hx_inj : Function.Injective x := by intro i j hij have hval : (i : ℕ) = (j : ℕ) := by rcases lt_trichotomy (i : ℕ) (j : ℕ) with hlt | heq | hgt · exfalso have h1 : x i ∈ W ((i:ℕ) + 1) := hx_mem' i have h2 : W ((i:ℕ) + 1) ⊆ W j.1 := hmono' _ _ (by omega) (le_of_lt j.2) have h3 : x j ∉ W j.1 := hx_not j exact h3 (hij ▸ h2 h1) · exact heq · exfalso have h1 : x j ∈ W ((j:ℕ) + 1) := hx_mem' j have h2 : W ((j:ℕ) + 1) ⊆ W i.1 := hmono' _ _ (by omega) (le_of_lt i.2) have h3 : x i ∉ W i.1 := hx_not i exact h3 (hij.symm ▸ h2 h1) exact Fin.ext hval
Convert x into a duplicate-free list of candidates and obtain a permutation σ whose prefixes match the prefix sublists.
We form the list L = List.ofFn x of length m. Because x is injective, L has no duplicate entries (List.nodup_ofFn). The auxiliary lemma exists_perm_with_prefix_eq_take then provides a permutation σ of Fin m whose prefix filters {c | σ(c) < k} equal the set of candidates in the first k elements of L for all k ≤ m.
uses
List.nodup_ofFn,exists_perm_with_prefix_eq_takelet L : List (Fin m) := List.ofFn x have hlen : L.length = m := by simp [L] have hLnodup : L.Nodup := by show (List.ofFn x).Nodup rw [List.nodup_ofFn] exact hx_inj obtain ⟨σ, hσ⟩ := exists_perm_with_prefix_eq_take L hLnodup hlen
For each k ≤ m, the set of candidates in the first k elements of L is precisely W_k.
We proceed by induction on k. For k = 0, taking 0 elements gives ∅ = W_0. For k + 1 ≤ m, the prefix of length k + 1 appends L[k] = x(k) to the prefix of length k (using List.take_add_one, List.getElem?_eq_getElem, and Option.toList_some). Applying List.toFinset_append and the induction hypothesis, this set is W_k ∪ {x(k)}. Mutual inclusion (Finset.Subset.antisymm) shows W_k ∪ {x(k)} = W_(k+1): forward inclusion holds because W_k ⊆ W_(k+1) and x(k) ∈ W_(k+1), while reverse inclusion holds because any a ∈ W_(k+1) either lies in W_k (Finset.mem_union_left) or lies in W_(k+1) \ W_k = {x(k)} (Finset.mem_sdiff.mpr, Finset.mem_union_right).
uses
List.take_add_one,List.getElem?_eq_getElem,Option.toList_some,List.toFinset_append,Finset.Subset.antisymm,Finset.mem_union.mp,Finset.mem_singleton,Finset.mem_union_left,Finset.mem_union_right,Finset.mem_sdiff.mprhave hprefix : ∀ k, k ≤ m → (L.take k).toFinset = W k := by intro k induction k with | zero => intro _ simp [hW0] | succ k ih => intro hk have hkm : k < m := hk have hk_le : k ≤ m := le_of_lt hkm have hk_lt_len : k < L.length := by rw [hlen]; exact hkm have hLk : L[k] = x ⟨k, hkm⟩ := by simp only [L, List.getElem_ofFn] have htake : (L.take (k + 1)).toFinset = (L.take k).toFinset ∪ {x ⟨k, hkm⟩} := by rw [List.take_add_one, List.getElem?_eq_getElem hk_lt_len, Option.toList_some, List.toFinset_append, hLk] simp have hunion : W k ∪ {x ⟨k, hkm⟩} = W (k + 1) := by apply Finset.Subset.antisymm · intro a ha rcases Finset.mem_union.mp ha with h | h · exact hmono k hkm h · rw [Finset.mem_singleton] at h rw [h] have := hx_mem' ⟨k, hkm⟩ simpa using this · intro a ha by_cases h : a ∈ W k · exact Finset.mem_union_left _ h · apply Finset.mem_union_right have hmem : a ∈ W (k + 1) \ W k := Finset.mem_sdiff.mpr ⟨ha, h⟩ have hset := hx ⟨k, hkm⟩ rw [hset] at hmem exact hmem rw [htake, ih hk_le, hunion]
The permutation σ satisfies the theorem: each prefix {c | σ(c) < k} is the EJR committee W_k.
For each k ≤ m, rewriting with hσ and hprefix shows that {c | σ(c) < k} equals the set of elements in the first k entries of L, which equals W_k. Since each W_k was assumed to be an EJR committee (hEJR), σ witnesses the required permutation.
exact ⟨σ, fun k hk => by rw [hσ k hk, hprefix k hk]; exact hEJR k hk⟩
Finset.card_sdiff_add_card_eq_card- If s ⊆ t, then the cardinality of t \ s plus the cardinality of s equals the cardinality of t.
Finset.card_eq_one.mp- A finite set has cardinality 1 if and only if it is a singleton set {a} for some element a.
Finset.mem_sdiff.mp- An element belongs to s \ t if and only if it belongs to s and does not belong to t.
Finset.mem_singleton_self- Every element belongs to its own singleton set.
Finset.Subset.refl- Every set is a subset of itself.
lt_or_ge- In a linear order, either a < b or b ≤ a.
lt_trichotomy- For any two elements in a linear order, exactly one of a < b, a = b, or b < a holds.
le_of_lt- Strict inequality implies non-strict inequality.
Fin.ext- Two elements of Fin n are equal if their underlying natural numbers are equal.
List.nodup_ofFn- The list created by evaluating a function f on Fin n contains no duplicates if and only if f is injective.
exists_perm_with_prefix_eq_take- For any duplicate-free list L of all m elements, there exists a permutation σ whose prefix filters {c | σ(c) < k} match the set of elements in the first k entries of L.
List.take_add_one- The prefix of length i + 1 of a list equals the prefix of length i concatenated with the list containing the i-th element.
List.getElem?_eq_getElem- Accessing the i-th element of a list within its length returns some of that element.
Option.toList_some- Converting some a of an option to a list yields the singleton list [a].
List.toFinset_append- The set of elements in a concatenated list is the union of the sets of elements of each list.
Finset.Subset.antisymm- Two sets are equal if each is a subset of the other.
Finset.mem_union.mp- An element belongs to a union s ∪ t if and only if it belongs to s or to t.
Finset.mem_singleton- An element belongs to {a} if and only if it equals a.
Finset.mem_union_left- If an element belongs to s, it belongs to s ∪ t.
Finset.mem_union_right- If an element belongs to t, it belongs to s ∪ t.
Finset.mem_sdiff.mpr- If an element belongs to s and does not belong to t, it belongs to s \ 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.
/-- A nested family of EJR committees of sizes 0, 1, ..., m yields a permutation whose every prefix is the corresponding EJR committee. -/theorem ejr_chain_of_nested_committees {n m : ℕ} (A : Fin n → Finset (Fin m)) : (∃ W : ℕ → Finset (Fin m), W 0 = ∅ ∧ (∀ k, k < m → W k ⊆ W (k + 1)) ∧ (∀ k, k ≤ m → is_ejr_committee A k (W k))) → ∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m → is_ejr_committee A k (Finset.univ.filter fun c => (σ c : ℕ) < k) := by rintro ⟨W, hW0, hmono, hEJR⟩ have hcard : ∀ k, k ≤ m → (W k).card = k := fun k hk => (hEJR k hk).1 have hdiff_card : ∀ k : Fin m, (W (k.1 + 1) \ W k.1).card = 1 := by intro k have hklt : (k : ℕ) < m := k.2 have hsub : W k.1 ⊆ W (k.1 + 1) := hmono k.1 hklt have h1 := Finset.card_sdiff_add_card_eq_card hsub have h2 : (W k.1).card = k.1 := hcard k.1 (by omega) have h3 : (W (k.1 + 1)).card = k.1 + 1 := hcard (k.1 + 1) (by omega) omega let x : Fin m → Fin m := fun k => (Finset.card_eq_one.mp (hdiff_card k)).choose have hx : ∀ k : Fin m, W (k.1 + 1) \ W k.1 = {x k} := fun k => (Finset.card_eq_one.mp (hdiff_card k)).choose_spec have hx_mem' : ∀ k : Fin m, x k ∈ W (k.1 + 1) := by intro k exact (Finset.mem_sdiff.mp (by rw [hx k]; exact Finset.mem_singleton_self (x k))).1 have hx_not : ∀ k : Fin m, x k ∉ W k.1 := by intro k exact (Finset.mem_sdiff.mp (by rw [hx k]; exact Finset.mem_singleton_self (x k))).2 have hmono' : ∀ a b, a ≤ b → b ≤ m → W a ⊆ W b := by intro a b hab hbm induction b with | zero => have : a = 0 := by omega subst this; exact Finset.Subset.refl _ | succ b ih => rcases lt_or_ge a (b + 1) with hlt | hge · exact (ih (by omega) (by omega)).trans (hmono b (by omega)) · have : a = b + 1 := by omega subst this; exact Finset.Subset.refl _ have hx_inj : Function.Injective x := by intro i j hij have hval : (i : ℕ) = (j : ℕ) := by rcases lt_trichotomy (i : ℕ) (j : ℕ) with hlt | heq | hgt · exfalso have h1 : x i ∈ W ((i:ℕ) + 1) := hx_mem' i have h2 : W ((i:ℕ) + 1) ⊆ W j.1 := hmono' _ _ (by omega) (le_of_lt j.2) have h3 : x j ∉ W j.1 := hx_not j exact h3 (hij ▸ h2 h1) · exact heq · exfalso have h1 : x j ∈ W ((j:ℕ) + 1) := hx_mem' j have h2 : W ((j:ℕ) + 1) ⊆ W i.1 := hmono' _ _ (by omega) (le_of_lt i.2) have h3 : x i ∉ W i.1 := hx_not i exact h3 (hij.symm ▸ h2 h1) exact Fin.ext hval let L : List (Fin m) := List.ofFn x have hlen : L.length = m := by simp [L] have hLnodup : L.Nodup := by show (List.ofFn x).Nodup rw [List.nodup_ofFn] exact hx_inj obtain ⟨σ, hσ⟩ := exists_perm_with_prefix_eq_take L hLnodup hlen have hprefix : ∀ k, k ≤ m → (L.take k).toFinset = W k := by intro k induction k with | zero => intro _ simp [hW0] | succ k ih => intro hk have hkm : k < m := hk have hk_le : k ≤ m := le_of_lt hkm have hk_lt_len : k < L.length := by rw [hlen]; exact hkm have hLk : L[k] = x ⟨k, hkm⟩ := by simp only [L, List.getElem_ofFn] have htake : (L.take (k + 1)).toFinset = (L.take k).toFinset ∪ {x ⟨k, hkm⟩} := by rw [List.take_add_one, List.getElem?_eq_getElem hk_lt_len, Option.toList_some, List.toFinset_append, hLk] simp have hunion : W k ∪ {x ⟨k, hkm⟩} = W (k + 1) := by apply Finset.Subset.antisymm · intro a ha rcases Finset.mem_union.mp ha with h | h · exact hmono k hkm h · rw [Finset.mem_singleton] at h rw [h] have := hx_mem' ⟨k, hkm⟩ simpa using this · intro a ha by_cases h : a ∈ W k · exact Finset.mem_union_left _ h · apply Finset.mem_union_right have hmem : a ∈ W (k + 1) \ W k := Finset.mem_sdiff.mpr ⟨ha, h⟩ have hset := hx ⟨k, hkm⟩ rw [hset] at hmem exact hmem rw [htake, ih hk_le, hunion] exact ⟨σ, fun k hk => by rw [hσ k hk, hprefix k hk]; exact hEJR k hk⟩