ejr_chain_candidates_le_three
Every approval profile on at most three candidates admits an EJR committee chain.
Statement
theorem ejr_chain_candidates_le_three (n m : ℕ) (A : Fin n → Finset (Fin m)) (hn : 0 < n) (hm : m ≤ 3) : ∃ σ : 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 6
- 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| ≥ ℓ.
- ejr_chain_of_nested_committeesIf 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…
- is_ejr_committee_zeroFor every approval profile with at least one voter, the empty committee is an EJR committee of size 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_adjacent_committees_existsFor every approval profile with at least one voter and every k smaller than the candidate count, there exist nested committees W subset V…
- ejr_committee_existsFor every approval profile with at least one voter and every committee size k ≤ m, some committee of size k satisfies EJR (for instance…
The proof, explained
By ejr_chain_of_nested_committees, constructing an EJR committee chain reduces to finding a nested family of committees ∅ = W₀ ⊆ W₁ ⊆ ⋯ ⊆ Wₘ where each Wₖ satisfies EJR for size k. Since m ≤ 3, the proof proceeds by case analysis on m ∈ {0, 1, 2, 3}. The boundary committees W₀ = ∅ and Wₘ = Finset.univ are always EJR, which directly settles m ≤ 1. For m = 2, any EJR committee of size 1 can be placed between ∅ and the universal set, and for m = 3, the existence of adjacent nested EJR committees W₁ ⊆ W₂ of sizes 1 and 2 completes the four-committee chain.
It suffices to construct a nested sequence of EJR committees of sizes k = 0, …, m for each candidate count m ∈ {0, 1, 2, 3}.
By ejr_chain_of_nested_committees, finding an EJR committee chain reduces to constructing a sequence of nested committees ∅ = W₀ ⊆ W₁ ⊆ ⋯ ⊆ Wₘ where each Wₖ satisfies EJR for size k. Since the total number of candidates satisfies m ≤ 3, we perform a case analysis on the four possible values m = 0, 1, 2, 3.
uses
ejr_chain_of_nested_committeesapply ejr_chain_of_nested_committees interval_cases mWhen m = 0, the constant empty sequence forms an EJR committee chain.
For m = 0, we set Wₖ = ∅ for all k. The base condition W₀ = ∅ holds by definition. The nesting condition is vacuous since there is no k < 0. Finally, the only size to check is k = 0, and the empty set is an EJR committee of size 0 by is_ejr_committee_zero.
uses
is_ejr_committee_zero· -- m = 0 refine ⟨fun _ => ∅, rfl, ?_, ?_⟩ · intro k hk; omega · intro k hk have hk0 : k = 0 := by omega subst hk0 exact is_ejr_committee_zero A hn
When m = 1, the sequence W₀ = ∅ and W₁ = Finset.univ forms an EJR committee chain.
For m = 1, we define W₀ = ∅ and Wₖ = Finset.univ for k ≥ 1. For k = 0 < 1, the inclusion ∅ ⊆ Finset.univ is immediate. For EJR satisfaction, W₀ = ∅ is an EJR committee of size 0 by is_ejr_committee_zero, and W₁ = Finset.univ is an EJR committee of size 1 by ejr_committee_univ.
uses
is_ejr_committee_zero,ejr_committee_univ· -- m = 1 refine ⟨fun k => if k = 0 then ∅ else Finset.univ, rfl, ?_, ?_⟩ · intro k hk interval_cases k · simp · intro k hk interval_cases k · simpa using is_ejr_committee_zero A hn · simpa using ejr_committee_univ (m := 1) A hn
When m = 2, extending an EJR committee of size 1 with ∅ and Finset.univ forms an EJR committee chain.
For m = 2, we obtain an EJR committee W₁ of size 1 using ejr_committee_exists, and define W₀ = ∅, W₁ = W₁, and W₂ = Finset.univ. The nesting ∅ ⊆ W₁ ⊆ Finset.univ holds immediately from the properties of ∅ and the universal set. For each size k ≤ 2, W₀ is EJR by is_ejr_committee_zero, W₁ is EJR by construction, and W₂ = Finset.univ is EJR by ejr_committee_univ.
uses
ejr_committee_exists,is_ejr_committee_zero,ejr_committee_univ· -- m = 2 obtain ⟨W1, hW1⟩ := ejr_committee_exists n 2 A hn 1 (by norm_num) refine ⟨fun k => if k = 0 then ∅ else if k = 1 then W1 else Finset.univ, rfl, ?_, ?_⟩ · intro k hk interval_cases k · simp · simp · intro k hk interval_cases k · simpa using is_ejr_committee_zero A hn · simpa using hW1 · simpa using ejr_committee_univ (m := 2) A hn
When m = 3, sandwiching a pair of adjacent nested EJR committees between ∅ and Finset.univ forms an EJR committee chain.
For m = 3, we invoke ejr_adjacent_committees_exists at k = 1 < 3 to obtain nested committees W₁ ⊆ W₂ of sizes 1 and 2, both satisfying EJR. We define the sequence W₀ = ∅, W₁, W₂, and W₃ = Finset.univ. The inclusions ∅ ⊆ W₁ and W₂ ⊆ Finset.univ are trivial, while W₁ ⊆ W₂ is guaranteed by the lemma. Each committee in the chain satisfies EJR: W₀ by is_ejr_committee_zero, W₁ and W₂ by construction, and W₃ = Finset.univ by ejr_committee_univ.
uses
ejr_adjacent_committees_exists,is_ejr_committee_zero,ejr_committee_univ· -- m = 3 obtain ⟨W1, W2, h12, hW1, hW2⟩ := ejr_adjacent_committees_exists A hn 1 (by norm_num) refine ⟨fun k => if k = 0 then ∅ else if k = 1 then W1 else if k = 2 then W2 else Finset.univ, rfl, ?_, ?_⟩ · intro k hk interval_cases k · simp · simpa using h12 · simp · intro k hk interval_cases k · simpa using is_ejr_committee_zero A hn · simpa using hW1 · simpa using hW2 · simpa using ejr_committee_univ (m := 3) A hn
ejr_chain_of_nested_committees- A sequence of nested committees ∅ = W₀ ⊆ W₁ ⊆ ⋯ ⊆ Wₘ where each Wₖ is an EJR committee of size k can be reordered into an EJR committee chain (a permutation whose prefixes of length k satisfy EJR for every k ≤ m).
is_ejr_committee_zero- For any approval profile with at least one voter, the empty committee ∅ is an EJR committee of size 0.
ejr_committee_univ- For any approval profile with at least one voter, the universal set of all m candidates is an EJR committee of size m.
ejr_committee_exists- For any approval profile with at least one voter and any committee size k ≤ m, there exists an EJR committee of size k.
ejr_adjacent_committees_exists- For any approval profile with at least one voter and any k < m, there exists a pair of nested committees W ⊆ V of sizes k and k + 1, respectively, both satisfying EJR.
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 on at most three candidates admits an EJR committee chain. -/theorem ejr_chain_candidates_le_three (n m : ℕ) (A : Fin n → Finset (Fin m)) (hn : 0 < n) (hm : m ≤ 3) : ∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m → is_ejr_committee A k (Finset.univ.filter fun c => (σ c : ℕ) < k) := by apply ejr_chain_of_nested_committees interval_cases m · -- m = 0 refine ⟨fun _ => ∅, rfl, ?_, ?_⟩ · intro k hk; omega · intro k hk have hk0 : k = 0 := by omega subst hk0 exact is_ejr_committee_zero A hn · -- m = 1 refine ⟨fun k => if k = 0 then ∅ else Finset.univ, rfl, ?_, ?_⟩ · intro k hk interval_cases k · simp · intro k hk interval_cases k · simpa using is_ejr_committee_zero A hn · simpa using ejr_committee_univ (m := 1) A hn · -- m = 2 obtain ⟨W1, hW1⟩ := ejr_committee_exists n 2 A hn 1 (by norm_num) refine ⟨fun k => if k = 0 then ∅ else if k = 1 then W1 else Finset.univ, rfl, ?_, ?_⟩ · intro k hk interval_cases k · simp · simp · intro k hk interval_cases k · simpa using is_ejr_committee_zero A hn · simpa using hW1 · simpa using ejr_committee_univ (m := 2) A hn · -- m = 3 obtain ⟨W1, W2, h12, hW1, hW2⟩ := ejr_adjacent_committees_exists A hn 1 (by norm_num) refine ⟨fun k => if k = 0 then ∅ else if k = 1 then W1 else if k = 2 then W2 else Finset.univ, rfl, ?_, ?_⟩ · intro k hk interval_cases k · simp · simpa using h12 · simp · intro k hk interval_cases k · simpa using is_ejr_committee_zero A hn · simpa using hW1 · simpa using hW2 · simpa using ejr_committee_univ (m := 3) A hn