ejr_chain_one_voter
Every approval profile with exactly one voter admits an EJR committee chain.
Statement
theorem ejr_chain_one_voter {m : ℕ} (A : Fin 1 → Finset (Fin m)) : ∃ σ : 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| ≥ ℓ.
The proof, explained
To construct an EJR committee chain for a single voter, order all candidates by placing the voter's approved candidates first, followed by the unapproved candidates. The prefix of length k in this ordering forms the committee of size k. Since there is only one voter, any cohesive group consists solely of this voter, requiring ℓ ≤ k and ℓ ≤ |A 0|. Because approved candidates are placed first, the committee of size k contains min(k, |A 0|) ≥ ℓ approved candidates, satisfying EJR.
The candidate list L, formed by concatenating the voter's approved candidates A₀ with the remaining candidates B, is duplicate-free.
Let A₀ = A 0 be the set of candidates approved by voter 0, and B = Finset.univ \ A₀ the remaining candidates. Since B consists of candidates not in A₀, their list representations are disjoint. Because finset listings are already duplicate-free, their concatenation L has no duplicates.
uses
List.disjoint_left,Finset.mem_toList.mp,Finset.mem_sdiff,Finset.mem_univ,true_and,List.Nodup.appendlet A0 := A 0 let B := Finset.univ \ A0 let L := A0.toList ++ B.toList have hdisj : (A0.toList).Disjoint (B.toList) := by rw [List.disjoint_left] intro a ha hb have ha' : a ∈ A0 := Finset.mem_toList.mp ha have hb' : a ∈ B := Finset.mem_toList.mp hb simp only [B, Finset.mem_sdiff, Finset.mem_univ, true_and] at hb' exact hb' ha' have hLnodup : L.Nodup := List.Nodup.append A0.nodup_toList B.nodup_toList hdisj
The list L has total length m.
The sum of the sizes of A₀ and its complement B equals the total number of candidates m. Since the length of L is the sum of the lengths of the two component lists, L has length m.
uses
Finset.card_sdiff_add_card_eq_card,Finset.subset_univ,Finset.card_univ,Fintype.card_fin,List.length_append,Finset.length_toListhave hcardB : Finset.card B + Finset.card A0 = m := by have := Finset.card_sdiff_add_card_eq_card (Finset.subset_univ A0) simpa [B, Finset.card_univ, Fintype.card_fin] using this have hLlen : L.length = m := by simp only [L, List.length_append, Finset.length_toList] omega
There exists a candidate permutation σ whose initial segments match the prefixes of L, reducing the goal to showing that the first k candidates of L form an EJR committee.
Applying exists_perm_with_prefix_eq_take to the duplicate-free list L of length m yields a permutation σ such that for every k ≤ m, the set of candidates with ranking index below k is precisely the finset of the first k elements of L. Witnessing this permutation σ and fixing k ≤ m, the committee is rewritten as (L.take k).toFinset.
uses
exists_perm_with_prefix_eq_takeobtain ⟨σ, hσ⟩ := exists_perm_with_prefix_eq_take L hLnodup hLlen refine ⟨σ, ?_⟩ intro k hk have hW : Finset.univ.filter (fun c => (σ c : ℕ) < k) = (L.take k).toFinset := hσ k hk rw [hW]
The committee (L.take k).toFinset has size k.
The prefix of length k of the duplicate-free list L has no duplicates and has length min(k, m) = k. Converting a duplicate-free list of length k to a finset yields a set of cardinality k.
uses
List.take_sublist,List.length_take,min_eq_left,List.toFinset_card_of_nodupconstructor · have htake_nodup : (L.take k).Nodup := (List.take_sublist k L).nodup hLnodup have htake_len : (L.take k).length = k := by rw [List.length_take, hLlen, min_eq_left hk] rw [List.toFinset_card_of_nodup htake_nodup, htake_len]
Any EJR-cohesive group G with quota ℓ ≥ 1 is nonempty.
Assume ℓ ≥ 1 and G is cohesive for committee size k and quota ℓ. By definition of cohesiveness, ℓ · 1 ≤ |G| · k. If G were empty, this would force ℓ ≤ 0, contradicting ℓ ≥ 1.
uses
Finset.eq_empty_or_nonempty,Finset.card_empty· intro ℓ hℓ G hGcoh obtain ⟨hGcard, hcomm⟩ := hGcoh have hGne : G.Nonempty := by rcases Finset.eq_empty_or_nonempty G with h | h · exfalso rw [h] at hGcard simp only [Finset.card_empty] at hGcard omega · exact h
The cohesive group G has size 1, and the quota satisfies ℓ ≤ k.
Because G is a nonempty subset of the singleton voter set Fin 1, its cardinality must be 1. Substituting |G| = 1 into the cohesiveness inequality ℓ · 1 ≤ |G| · k yields ℓ ≤ k.
uses
Finset.card_le_card,Finset.subset_univ,Finset.card_univ,Finset.card_pos.mprhave hGcard_le : Finset.card G ≤ 1 := by have := Finset.card_le_card (Finset.subset_univ G) simpa [Finset.card_univ] using this have hGpos : 0 < Finset.card G := Finset.card_pos.mpr hGne have hGc1 : Finset.card G = 1 := by omega have hℓk : ℓ ≤ k := by have := hGcard rw [hGc1] at this omega
Voter 0 belongs to G, and the quota satisfies ℓ ≤ |A₀|.
Since Fin 1 contains only the element 0, the unique voter in G is 0. The set of candidates unanimously approved by G is therefore contained in A₀ = A 0. Cohesiveness implies that ℓ is bounded by the size of this intersection, which by inclusion is at most |A₀|.
uses
Subsingleton.elim,Finset.mem_filter,Finset.mem_univ,true_and,le_trans,Finset.card_le_cardobtain ⟨i, hi⟩ := hGne have hi0 : i = 0 := Subsingleton.elim i 0 have h0mem : (0 : Fin 1) ∈ G := hi0 ▸ hi have hsub : (({c | ∀ i ∈ G, c ∈ A i}) : Finset (Fin m)) ⊆ A0 := by intro c hc simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hc exact hc 0 h0mem have hA0ge : ℓ ≤ Finset.card A0 := le_trans hcomm (Finset.card_le_card hsub)
The set S of the first k elements of A₀ is a subset of A₀ ∩ (L.take k).toFinset.
We choose voter 0 ∈ G as the voter whose representation will be guaranteed. Let S be the first k elements of A₀.toList. Every element of S belongs to A₀ by definition. Moreover, since A₀ appears first in the concatenation L, the first k elements of A₀ are contained in the first k elements of L, so S is contained in both A₀ and the committee.
uses
Finset.mem_inter,Finset.mem_toList.mp,List.mem_of_mem_take,List.mem_toFinset.mp,List.mem_toFinset,List.take_append,List.mem_append_leftrefine ⟨0, h0mem, ?_⟩ let S := (A0.toList.take k).toFinset have hSsub : S ⊆ A0 ∩ (L.take k).toFinset := by intro c hc rw [Finset.mem_inter] constructor · exact Finset.mem_toList.mp (List.mem_of_mem_take (List.mem_toFinset.mp hc)) · rw [List.mem_toFinset] rw [List.take_append] exact List.mem_append_left _ (List.mem_toFinset.mp hc)
Voter 0 approves at least ℓ committee members, completing the proof of EJR.
The size of S is min(k, |A₀|). Since ℓ ≤ k and ℓ ≤ |A₀|, we have ℓ ≤ min(k, |A₀|) = |S|. Because S is a subset of the committee members approved by voter 0, that intersection has size at least |S| ≥ ℓ.
uses
List.take_sublist,List.toFinset_card_of_nodup,List.length_take,Finset.length_toList,le_min,le_trans,Finset.card_le_cardhave hScard : Finset.card S = min k (Finset.card A0) := by have hnd : (A0.toList.take k).Nodup := (List.take_sublist k A0.toList).nodup A0.nodup_toList rw [List.toFinset_card_of_nodup hnd, List.length_take, Finset.length_toList] have hmin : ℓ ≤ Finset.card S := by rw [hScard] exact le_min hℓk hA0ge exact le_trans hmin (Finset.card_le_card hSsub)
List.disjoint_left- Two lists are disjoint if and only if no element of the first list belongs to the second.
Finset.mem_toList.mp- If an element belongs to the list of elements of a finset, then it belongs to the finset.
Finset.mem_sdiff- An element belongs to the set difference s \ t if and only if it is in s and not in t.
Finset.mem_univ- Every element of a finite type belongs to the universal finset.
true_and- The conjunction True ∧ p is equivalent to p.
List.Nodup.append- The concatenation of two duplicate-free lists is duplicate-free if the lists are disjoint.
Finset.card_sdiff_add_card_eq_card- For any subset s ⊆ t of a finset, the size of t \ s plus the size of s equals the size of t.
Finset.subset_univ- Every finset of elements of a finite type is a subset of the universal finset.
Finset.card_univ- The cardinality of the universal finset equals the cardinality of the underlying finite type.
Fintype.card_fin- The cardinality of Fin n is n.
List.length_append- The length of the concatenation of two lists is the sum of their lengths.
Finset.length_toList- The list of elements of a finset has length equal to the cardinality of the finset.
exists_perm_with_prefix_eq_take- For any duplicate-free list of length m, there exists a permutation whose first k elements coincide with the prefix of length k of the list for all k ≤ m.
List.take_sublist- The prefix of length k of a list is a sublist of the original list.
List.length_take- The length of the prefix of length k of a list is min(k, length).
min_eq_left- If a ≤ b, then min(a, b) = a.
List.toFinset_card_of_nodup- The finset converted from a duplicate-free list has cardinality equal to the length of the list.
Finset.eq_empty_or_nonempty- Every finset is either empty or nonempty.
Finset.card_empty- The empty finset has cardinality 0.
Finset.card_le_card- If s ⊆ t, then |s| ≤ |t|.
Finset.card_pos.mpr- A finset has strictly positive cardinality if and only if it is nonempty.
Subsingleton.elim- Any two elements of a subsingleton type are equal.
Finset.mem_filter- An element is in a filtered finset if and only if it belongs to the finset and satisfies the predicate.
le_trans- Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
Finset.mem_inter- An element is in the intersection of two finsets if and only if it is in both.
List.mem_of_mem_take- An element in a prefix of a list is also in the list.
List.mem_toFinset.mp- An element in the finset converted from a list is also an element of the list.
List.mem_toFinset- An element belongs to the finset converted from a list if and only if it belongs to the list.
List.take_append- Taking k elements of a concatenation takes from the first list and then from the second.
List.mem_append_left- An element belonging to a list also belongs to the list concatenated with another list.
le_min- If c ≤ a and c ≤ b, then c ≤ min(a, b).
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.
/-- Every approval profile with exactly one voter admits an EJR committee chain. -/theorem ejr_chain_one_voter {m : ℕ} (A : Fin 1 → Finset (Fin m)) : ∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m → is_ejr_committee A k (Finset.univ.filter fun c => (σ c : ℕ) < k) := by let A0 := A 0 let B := Finset.univ \ A0 let L := A0.toList ++ B.toList have hdisj : (A0.toList).Disjoint (B.toList) := by rw [List.disjoint_left] intro a ha hb have ha' : a ∈ A0 := Finset.mem_toList.mp ha have hb' : a ∈ B := Finset.mem_toList.mp hb simp only [B, Finset.mem_sdiff, Finset.mem_univ, true_and] at hb' exact hb' ha' have hLnodup : L.Nodup := List.Nodup.append A0.nodup_toList B.nodup_toList hdisj have hcardB : Finset.card B + Finset.card A0 = m := by have := Finset.card_sdiff_add_card_eq_card (Finset.subset_univ A0) simpa [B, Finset.card_univ, Fintype.card_fin] using this have hLlen : L.length = m := by simp only [L, List.length_append, Finset.length_toList] omega obtain ⟨σ, hσ⟩ := exists_perm_with_prefix_eq_take L hLnodup hLlen refine ⟨σ, ?_⟩ intro k hk have hW : Finset.univ.filter (fun c => (σ c : ℕ) < k) = (L.take k).toFinset := hσ k hk rw [hW] constructor · have htake_nodup : (L.take k).Nodup := (List.take_sublist k L).nodup hLnodup have htake_len : (L.take k).length = k := by rw [List.length_take, hLlen, min_eq_left hk] rw [List.toFinset_card_of_nodup htake_nodup, htake_len] · intro ℓ hℓ G hGcoh obtain ⟨hGcard, hcomm⟩ := hGcoh have hGne : G.Nonempty := by rcases Finset.eq_empty_or_nonempty G with h | h · exfalso rw [h] at hGcard simp only [Finset.card_empty] at hGcard omega · exact h have hGcard_le : Finset.card G ≤ 1 := by have := Finset.card_le_card (Finset.subset_univ G) simpa [Finset.card_univ] using this have hGpos : 0 < Finset.card G := Finset.card_pos.mpr hGne have hGc1 : Finset.card G = 1 := by omega have hℓk : ℓ ≤ k := by have := hGcard rw [hGc1] at this omega obtain ⟨i, hi⟩ := hGne have hi0 : i = 0 := Subsingleton.elim i 0 have h0mem : (0 : Fin 1) ∈ G := hi0 ▸ hi have hsub : (({c | ∀ i ∈ G, c ∈ A i}) : Finset (Fin m)) ⊆ A0 := by intro c hc simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hc exact hc 0 h0mem have hA0ge : ℓ ≤ Finset.card A0 := le_trans hcomm (Finset.card_le_card hsub) refine ⟨0, h0mem, ?_⟩ let S := (A0.toList.take k).toFinset have hSsub : S ⊆ A0 ∩ (L.take k).toFinset := by intro c hc rw [Finset.mem_inter] constructor · exact Finset.mem_toList.mp (List.mem_of_mem_take (List.mem_toFinset.mp hc)) · rw [List.mem_toFinset] rw [List.take_append] exact List.mem_append_left _ (List.mem_toFinset.mp hc) have hScard : Finset.card S = min k (Finset.card A0) := by have hnd : (A0.toList.take k).Nodup := (List.take_sublist k A0.toList).nodup A0.nodup_toList rw [List.toFinset_card_of_nodup hnd, List.length_take, Finset.length_toList] have hmin : ℓ ≤ Finset.card S := by rw [hScard] exact le_min hℓk hA0ge exact le_trans hmin (Finset.card_le_card hSsub)