ejr_chain_iff_level_supporters
A permutation whose every prefix of length k is an EJR committee exists if and only if there is a permutation such that for every k ≤ m and every nonempty candidate subset T, the number of voters approving all of T who approve fewer than |T| candidates among the first k positions, times k, is strictly below |T| times the number of voters.
Statement
theorem ejr_chain_iff_level_supporters {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)) ↔ (∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m → ∀ T : Finset (Fin m), T.Nonempty → (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ Finset.univ.filter fun c => (σ c : ℕ) < k).card < T.card).card * k < T.card * n)
- Source
- step towards ejr_committee_monotone_chain_exists
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- is_ejr_committee_iff_candidate_subsetsEJR is equivalent to the correct committee size together with the underrepresented-supporter inequality for every nonempty candidate…
- 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| ≥ ℓ.
- Used by 2
- ejr_chain_two_votersFor every approval profile with two voters and any number of candidates, there is an ordering of the candidates every prefix of which is…
- ejr_chain_singleton_ballotsIf every voter approves at most one candidate, then there is an ordering of the candidates every prefix of which is an EJR committee of…
The proof, explained
The theorem characterizes the existence of an EJR chain—a permutation of candidates whose prefixes of all sizes k ≤ m are EJR committees—in terms of a level-by-level counting condition on candidate subsets. By is_ejr_committee_iff_candidate_subsets, a committee of size k satisfies EJR if and only if it satisfies this supporter bound for all nonempty candidate subsets T. Since any prefix of length k determined by a permutation has size exactly k (as established in a helper lemma), the two existential statements are equivalent level by level.
The k-candidate prefix {c | σ(c) < k} equals the image under σ⁻¹ of the initial segment {x | x < k}.
By set extensionality, a candidate c satisfies σ(c) < k if and only if c is the image under the inverse permutation σ⁻¹ of some candidate x with x < k, where the forward witness is simply x = σ(c).
have hpre : (Finset.univ.filter fun c : Fin m => (σ c : ℕ) < k) = (Finset.univ.filter fun x : Fin m => (x : ℕ) < k).image σ.symm := by ext c simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_image] constructor · intro h exact ⟨σ c, h, by simp⟩ · rintro ⟨x, hx, rfl⟩ simpa using hx
The initial segment {x ∈ Fin m | x < k} is the image of Fin k under the canonical inclusion.
By set extensionality, an element of Fin m lies in the image of Fin.castLE hk if and only if its index as a natural number is strictly less than k.
have himg : (Finset.univ : Finset (Fin k)).image (Fin.castLE hk) = Finset.univ.filter (fun x : Fin m => (x : ℕ) < k) := by ext x simp only [Finset.mem_image, Finset.mem_univ, true_and, Finset.mem_filter] constructor · rintro ⟨a, rfl⟩ simp · intro hx exact ⟨⟨x, hx⟩, Fin.ext rfl⟩
The k-candidate prefix has cardinality k.
Because both the permutation inverse σ⁻¹ and the inclusion Fin.castLE hk are injective, the cardinality of the prefix equals the cardinality of Fin k, which is k.
uses
Finset.card_image_of_injective,Fin.castLE_injective,Finset.card_univ,Fintype.card_finrw [hpre, Finset.card_image_of_injective _ σ.symm.injective, ← himg, Finset.card_image_of_injective _ (Fin.castLE_injective hk), Finset.card_univ, Fintype.card_fin]If a permutation forms an EJR chain, then its prefixes satisfy the level-by-level candidate-subset supporter condition.
Splitting the bi-implication, suppose σ forms an EJR chain. Then for every k ≤ m, the prefix committee of length k is an EJR committee. Applying the forward direction of is_ejr_committee_iff_candidate_subsets immediately yields the desired inequality for every nonempty subset of candidates T.
uses
is_ejr_committee_iff_candidate_subsetsconstructor · rintro ⟨σ, hσ⟩ exact ⟨σ, fun k hk T hT => ((is_ejr_committee_iff_candidate_subsets A k _).mp (hσ k hk)).2 T hT⟩
Conversely, if a permutation satisfies the candidate-subset supporter condition at every level k ≤ m, then its prefixes form an EJR chain.
Given such a permutation σ, we show each prefix of length k ≤ m is an EJR committee by applying the characterization is_ejr_committee_iff_candidate_subsets. This requires that the prefix has size k (which holds by ejr_chain_iff_level_supporters_card_prefix) and that the candidate-subset inequality holds for all nonempty T (which is our hypothesis).
uses
is_ejr_committee_iff_candidate_subsets,ejr_chain_iff_level_supporters_card_prefix· rintro ⟨σ, hσ⟩ refine ⟨σ, fun k hk => ?_⟩ rw [is_ejr_committee_iff_candidate_subsets] exact ⟨ejr_chain_iff_level_supporters_card_prefix σ k hk, fun T hT => hσ k hk T hT⟩
Fin.castLE_injective- The canonical inclusion of Fin n into Fin m for n ≤ m is injective.
Finset.card_image_of_injective- The image of a finite set under an injective map has the same cardinality as the original set.
Finset.card_univ- The cardinality of the universal finset on a finite type equals the cardinality of the underlying type.
Fintype.card_fin- The cardinality of Fin n is n.
ejr_chain_iff_level_supporters_card_prefix- For any permutation σ on m elements and any k ≤ m, the set of elements mapped by σ to values strictly less than k has cardinality k.
is_ejr_committee_iff_candidate_subsets- A committee W satisfies extended justified representation (EJR) for approval profile A at target size k if and only if W has cardinality k and, for every nonempty subset of candidates T, the number of voters approving all of T who approve fewer than |T| candidates in W, multiplied by k, is strictly less than |T| times the total number of voters.
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.
private lemma ejr_chain_iff_level_supporters_card_prefix {m : ℕ} (σ : Equiv.Perm (Fin m)) (k : ℕ) (hk : k ≤ m) : (Finset.univ.filter fun c => (σ c : ℕ) < k).card = k := by have hpre : (Finset.univ.filter fun c : Fin m => (σ c : ℕ) < k) = (Finset.univ.filter fun x : Fin m => (x : ℕ) < k).image σ.symm := by ext c simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_image] constructor · intro h exact ⟨σ c, h, by simp⟩ · rintro ⟨x, hx, rfl⟩ simpa using hx have himg : (Finset.univ : Finset (Fin k)).image (Fin.castLE hk) = Finset.univ.filter (fun x : Fin m => (x : ℕ) < k) := by ext x simp only [Finset.mem_image, Finset.mem_univ, true_and, Finset.mem_filter] constructor · rintro ⟨a, rfl⟩ simp · intro hx exact ⟨⟨x, hx⟩, Fin.ext rfl⟩ rw [hpre, Finset.card_image_of_injective _ σ.symm.injective, ← himg, Finset.card_image_of_injective _ (Fin.castLE_injective hk), Finset.card_univ, Fintype.card_fin]/-- The chain target is equivalent to a level-by-level counting condition on supporters of candidate subsets, with all cohesive-group machinery eliminated. -/theorem ejr_chain_iff_level_supporters {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)) ↔ (∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m → ∀ T : Finset (Fin m), T.Nonempty → (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ Finset.univ.filter fun c => (σ c : ℕ) < k).card < T.card).card * k < T.card * n) := by constructor · rintro ⟨σ, hσ⟩ exact ⟨σ, fun k hk T hT => ((is_ejr_committee_iff_candidate_subsets A k _).mp (hσ k hk)).2 T hT⟩ · rintro ⟨σ, hσ⟩ refine ⟨σ, fun k hk => ?_⟩ rw [is_ejr_committee_iff_candidate_subsets] exact ⟨ejr_chain_iff_level_supporters_card_prefix σ k hk, fun T hT => hσ k hk T hT⟩