ejr_chain_exists_of_support_density_bound
A permutation whose every prefix satisfies the proposed density bound yields an EJR committee chain.
Statement
theorem ejr_chain_exists_of_support_density_bound (n m : ℕ) (A : Fin n → Finset (Fin m)) (hn : 0 < n) (h : ∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m → ejr_support_density_bound A (k + 1) (Finset.univ.filter fun c => (σ c : ℕ) < k)) : ∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m → is_ejr_committee A k (Finset.univ.filter fun c => (σ c : ℕ) < k)
- Source
- Supporting work for OP-22, arXiv:2007.01795, Q2, and the proposed max-group-density invariant in memory attempt 4342. These helpers neither settle full-chain existence nor refute the actual greedy rule. No research advance is claimed.
- Verified
- 25 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- ejr_support_density_boundThe finite supporter-density bound: for every candidate subset T, its undersatisfied supporter count times q is at most |T| times the…
- 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_of_support_density_boundFor a nonempty electorate, the density bound with q=k+1 implies EJR for any committee of size k.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
The proof, explained
To show that an EJR committee chain exists, we use the assumed permutation σ whose prefixes satisfy the support density bound at each size k ≤ m. An auxiliary lemma first proves that each prefix {c ∈ Fin m | σ c < k} has cardinality k by setting up a bijection to the initial interval of Fin m. The main theorem then applies the transfer lemma ejr_of_support_density_bound to each prefix to conclude that every prefix is an EJR committee.
The prefix {c ∈ Fin m | σ c < k} has the same cardinality as the unpermuted prefix {c ∈ Fin m | c < k}.
The permutation σ induces a bijection between {c | σ c < k} and {c | c < k}. By Finset.card_bij, σ maps elements of the former into the latter, σ is injective, and any b < k has preimage σ⁻¹(b) satisfying σ(σ⁻¹(b)) = b < k. Rewriting with this bijection reduces the goal to showing that the unpermuted prefix has size k.
uses
Finset.card_bij,Finset.mem_filter,Finset.mem_univ,true_andclassical have he : (Finset.univ.filter fun c => (σ c : ℕ) < k).card = (Finset.univ.filter fun c : Fin m => (c : ℕ) < k).card := by apply Finset.card_bij (fun c _ => σ c) · intro c hc simpa only [Finset.mem_filter, Finset.mem_univ, true_and] using hc · intro a ha b hb hab exact σ.injective hab · intro b hb refine ⟨σ.symm b, ?_, by simp⟩ simpa only [Finset.mem_filter, Finset.mem_univ, true_and, σ.apply_symm_apply] using hb rw [he]
When k = m, the prefix {c ∈ Fin m | c < m} has cardinality m.
If k = m, every element c ∈ Fin m satisfies c < m by definition of Fin m. The filtered subset is thus the entire universe Finset.univ of Fin m, whose cardinality is m.
by_cases hkm : k = m · subst k simp
When k < m, the prefix {c ∈ Fin m | c < k} is the open interval Finset.Iio ⟨k, hlt⟩, which has cardinality k.
From k ≤ m and k ≠ m, linear arithmetic gives k < m, so k defines an element ⟨k, hlt⟩ ∈ Fin m. By extensionality and Finset.mem_Iio, the prefix equals Finset.Iio ⟨k, hlt⟩. Its cardinality is then evaluated as k using Fin.card_Iio.
uses
Finset.mem_filter,Finset.mem_univ,true_and,Finset.mem_Iio,Fin.card_Iio· have hlt : k < m := by omega have hI : (Finset.univ.filter fun c : Fin m => (c : ℕ) < k) = Finset.Iio (⟨k, hlt⟩ : Fin m) := by ext c simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_Iio] rfl rw [hI, Fin.card_Iio]
The permutation σ produces an EJR committee of size k for each prefix size k ≤ m.
We unpack the permutation σ and hypothesis hσ from the existential assumption. For each k ≤ m, the auxiliary lemma ejr_density_prefix_card_aux shows that the prefix W_k = {c | σ c < k} has cardinality k. Together with the density bound from hσ, ejr_of_support_density_bound concludes that W_k is an EJR committee of size k.
uses
ejr_of_support_density_bound,ejr_density_prefix_card_auxobtain ⟨σ, hσ⟩ := h exact ⟨σ, fun k hk => ejr_of_support_density_bound A k _ hn (ejr_density_prefix_card_aux σ k hk) (hσ k hk)⟩
Finset.card_bij- Two finite sets s and t have equal cardinality if there exists an injective and surjective map from s to t.
Finset.mem_filter- An element a belongs to Finset.filter p s if and only if a ∈ s and p a holds.
Finset.mem_univ- Every element of a finite type belongs to its universal Finset, Finset.univ.
true_and- The conjunction True ∧ p is equivalent to p.
Finset.mem_Iio- An element x belongs to the open interval Finset.Iio a if and only if x < a.
Fin.card_Iio- In Fin n, the cardinality of the strictly lower interval Finset.Iio b is equal to the numerical value of b.
ejr_of_support_density_bound- If a committee W has cardinality k and satisfies the support density bound with parameter k + 1 for an approval profile with n > 0 voters, then W is an EJR committee of size k.
ejr_density_prefix_card_aux- For any permutation σ of Fin m and any k ≤ m, the prefix Finset.univ.filter (fun c => σ c < k) has cardinality exactly k.
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.
theorem ejr_density_prefix_card_aux {m : ℕ} (σ : Equiv.Perm (Fin m)) (k : ℕ) (hk : k ≤ m) : (Finset.univ.filter fun c => (σ c : ℕ) < k).card = k := by classical have he : (Finset.univ.filter fun c => (σ c : ℕ) < k).card = (Finset.univ.filter fun c : Fin m => (c : ℕ) < k).card := by apply Finset.card_bij (fun c _ => σ c) · intro c hc simpa only [Finset.mem_filter, Finset.mem_univ, true_and] using hc · intro a ha b hb hab exact σ.injective hab · intro b hb refine ⟨σ.symm b, ?_, by simp⟩ simpa only [Finset.mem_filter, Finset.mem_univ, true_and, σ.apply_symm_apply] using hb rw [he] by_cases hkm : k = m · subst k simp · have hlt : k < m := by omega have hI : (Finset.univ.filter fun c : Fin m => (c : ℕ) < k) = Finset.Iio (⟨k, hlt⟩ : Fin m) := by ext c simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_Iio] rfl rw [hI, Fin.card_Iio]theorem ejr_chain_exists_of_support_density_bound (n m : ℕ) (A : Fin n → Finset (Fin m)) (hn : 0 < n) (h : ∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m → ejr_support_density_bound A (k + 1) (Finset.univ.filter fun c => (σ c : ℕ) < k)) : ∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m → is_ejr_committee A k (Finset.univ.filter fun c => (σ c : ℕ) < k) := by obtain ⟨σ, hσ⟩ := h exact ⟨σ, fun k hk => ejr_of_support_density_bound A k _ hn (ejr_density_prefix_card_aux σ k hk) (hσ k hk)⟩