ejr_chain_nested_committees_iff
An approval profile admits an EJR committee chain if and only if it admits an increasing sequence of EJR committees of sizes 0 through m.
Statement
theorem ejr_chain_nested_committees_iff {n m : ℕ} (A : Fin n → Finset (Fin m)) : (∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m → is_ejr_committee A k (Finset.univ.filter fun c => (σ c : ℕ) < k)) ↔ (∃ W : ℕ → Finset (Fin m), W 0 = ∅ ∧ (∀ k, k < m → W k ⊆ W (k + 1)) ∧ (∀ k, k ≤ m → is_ejr_committee A k (W k)))
- Source
- step towards ejr_committee_monotone_chain_exists
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- 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…
The proof, explained
The equivalence states that an EJR committee chain (a permutation whose initial segments of size k ≤ m are EJR committees) is equivalent to having a nested sequence of EJR committees W(0) ⊆ W(1) ⊆ ⋯ ⊆ W(m). In the forward direction, defining W(k) to be the first k candidates according to the permutation σ immediately yields an empty initial committee, nested sets by transitivity of inequality, and EJR committees by hypothesis. The backward direction is established directly by the helper theorem `ejr_chain_of_nested_committees`.
In the forward direction, given an EJR chain permutation σ, setting W(k) = {c | σ(c) < k} leaves three conditions to verify.
We split the equivalence into both directions. In the forward direction, we assume a permutation σ such that for each k ≤ m, the prefix committee {c | σ(c) < k} is an EJR committee of size k. We witness the existential by choosing the sequence W(k) = {c | σ(c) < k}, leaving three goals: W(0) = ∅, nesting of successive committees, and the EJR property for each k ≤ m.
constructor · rintro ⟨σ, hσ⟩ refine ⟨fun k => Finset.univ.filter fun c => (σ c : ℕ) < k, ?_, ?_, ?_⟩
W(0) = ∅.
By definition, W(0) = {c | σ(c) < 0}. Because no natural number is strictly less than 0, no candidate satisfies the condition, so the set simplifies to the empty set.
· simpW(k) ⊆ W(k + 1) for every k < m.
Let k < m and consider a candidate c ∈ W(k). Unfolding membership in the filtered universal set with `Finset.mem_filter`, `Finset.mem_univ`, and `true_and` reduces this to σ(c) < k. Since k < k + 1, linear arithmetic (`omega`) deduces σ(c) < k + 1, which means c ∈ W(k + 1).
uses
Finset.mem_filter,Finset.mem_univ,true_and· intro k _ c hc simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hc ⊢ omega
Each committee W(k) satisfies EJR for k ≤ m.
For any k ≤ m, W(k) is {c | σ(c) < k}, which is an EJR committee of size k by the assumption on σ.
· intro k hk exact hσ k hk
Conversely, any nested sequence of EJR committees yields an EJR committee chain.
The reverse implication follows directly from the previously proved theorem `ejr_chain_of_nested_committees` applied to the approval profile A.
uses
ejr_chain_of_nested_committees· exact ejr_chain_of_nested_committees A
Finset.mem_filter- An element belongs to a filtered finite set if and only if it belongs to the original set and satisfies the filtering predicate.
Finset.mem_univ- Every element of a finite type belongs to the universal finite set `Finset.univ`.
true_and- The conjunction `True ∧ p` is equivalent to `p`.
ejr_chain_of_nested_committees- If an approval profile admits a nested sequence of EJR committees of sizes 0 through m, then it admits an EJR committee chain given by a permutation.
- The reverse direction is delegated entirely to the lemma `ejr_chain_of_nested_committees`, which constructs the ordering permutation from a nested sequence of committees.
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.
/-- An approval profile admits an EJR committee chain if and only if it admits an increasing sequence of EJR committees of sizes 0 through m. -/theorem ejr_chain_nested_committees_iff {n m : ℕ} (A : Fin n → Finset (Fin m)) : (∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m → is_ejr_committee A k (Finset.univ.filter fun c => (σ c : ℕ) < k)) ↔ (∃ W : ℕ → Finset (Fin m), W 0 = ∅ ∧ (∀ k, k < m → W k ⊆ W (k + 1)) ∧ (∀ k, k ≤ m → is_ejr_committee A k (W k))) := by constructor · rintro ⟨σ, hσ⟩ refine ⟨fun k => Finset.univ.filter fun c => (σ c : ℕ) < k, ?_, ?_, ?_⟩ · simp · intro k _ c hc simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hc ⊢ omega · intro k hk exact hσ k hk · exact ejr_chain_of_nested_committees A