ejr_chain_of_deletable_voter
If a voter's ballot is empty or misses at most one candidate, deleting that voter preserves the existence of an EJR chain: the same ordering witnesses the chain for the original profile.
Statement
theorem ejr_chain_of_deletable_voter (n m : ℕ) (A : Fin n → Finset (Fin m)) (hn : 0 < n) (i : Fin n) (hi : A i = ∅ ∨ m - 1 ≤ (A i).card) (B : Fin (n - 1) → Finset (Fin m)) (e : Fin (n - 1) ≃ {j : Fin n // j ≠ i}) (hB : ∀ j, B j = A (e j).1) (hchain : ∃ σ' : Equiv.Perm (Fin m), ∀ k, k ≤ m → is_ejr_committee B k (Finset.univ.filter fun x => (σ' x : ℕ) < k)) : ∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m → is_ejr_committee A k (Finset.univ.filter fun x => (σ x : ℕ) < k)
- Source
- step towards ejr_committee_monotone_chain_exists
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- is_ejr_committee_iff_candidate_subsetsEJR is equivalent to the correct committee size together with the underrepresented-supporter inequality for every nonempty candidate…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - 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| ≥ ℓ.
The proof, explained
We show that any candidate permutation σ witnessing an EJR chain for the reduced profile B on n - 1 voters also witnesses an EJR chain for the original profile A on n voters. Using the candidate subset characterization of EJR, for any committee size k and nonempty candidate subset T, it suffices to bound the number c_A of voters in A approving all of T who have fewer than |T| committee members in W. A counting decomposition shows that c_A equals c_B plus an indicator for voter i, while the quota threshold increases by |T|. When voter i satisfies the condition, their ballot contains at least m - 1 candidates, so inclusion-exclusion forces them to share at least k - 1 candidates with the committee, implying k ≤ |T|. Combining this with the EJR bound on the reduced profile establishes the required inequality for A.
The number of voters in Fin n satisfying a predicate P is (1 if P i else 0) plus the number of voters other than i satisfying P.
We split into two cases based on whether voter i satisfies P. If P i holds, the set of satisfying voters is the disjoint union of {i} and {j | j ≠ i ∧ P j}, so its cardinality is 1 + |{j | j ≠ i ∧ P j}|. If P i fails, the set of satisfying voters is identically {j | j ≠ i ∧ P j}, so the count is 0 + |{j | j ≠ i ∧ P j}|.
uses
if_pos,Finset.card_insert_of_notMem,if_neg,zero_addhave h1 : (Finset.univ.filter P).card = (if P i then 1 else 0) + (Finset.univ.filter (fun j => j ≠ i ∧ P j)).card := by by_cases hi : P i · rw [if_pos hi] have h_eq : Finset.univ.filter P = insert i (Finset.univ.filter (fun j => j ≠ i ∧ P j)) := by ext x simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert] by_cases hx : x = i · subst hx; simp [hi] · simp [hx] rw [h_eq, Finset.card_insert_of_notMem] · omega · simp · rw [if_neg hi, zero_add] congr 1 ext x simp only [Finset.mem_filter, Finset.mem_univ, true_and] constructor · intro hx refine ⟨?_, hx⟩ rintro rfl exact hi hx · intro hx exact hx.2
The count of voters j ≠ i in Fin n satisfying P j equals the count of elements satisfying P in the subtype {j : Fin n // j ≠ i}.
The subtype inclusion Subtype.val is injective. Pushing forward the filtered subtype under this embedding produces the set {j | j ≠ i ∧ P j}, so by Finset.card_map their cardinalities are equal.
uses
Finset.card_map,Subtype.val_injectivehave h2 : (Finset.univ.filter (fun j => j ≠ i ∧ P j)).card = ((Finset.univ : Finset {j : Fin n // j ≠ i}).filter (fun j => P j.1)).card := by have h := (Finset.card_map ⟨Subtype.val, Subtype.val_injective⟩ (s := (Finset.univ : Finset {j : Fin n // j ≠ i}).filter (fun j => P j.1))).symm rw [h] congr 1 ext x simp tauto
The number of voters in Fin n satisfying P equals (1 if P i else 0) plus the number of voters in Fin (n - 1) satisfying P (e j).
The equivalence e : Fin (n - 1) ≃ {j : Fin n // j ≠ i} induces a bijection between the filtered set in Fin (n - 1) and the filtered subtype via e.symm, so by Finset.card_map their cardinalities are equal. Substituting this and the previous steps completes the proof of the splitting lemma.
uses
Finset.card_maphave h3 : (Finset.univ.filter (fun j => P (e j).1)).card = ((Finset.univ : Finset {j : Fin n // j ≠ i}).filter (fun j => P j.1)).card := by have : (Finset.univ.filter (fun j => P (e j).1)) = ((Finset.univ : Finset {j : Fin n // j ≠ i}).filter (fun j => P j.1)).map e.symm.toEmbedding := by ext a simp rw [this, Finset.card_map] rw [h1, h2, h3]
The same permutation σ witnesses an EJR chain for profile A, reducing the EJR requirement for each committee size k to the candidate subset condition.
Let σ be the permutation witnessing the EJR chain for the reduced profile B. For each k ≤ m, the committee W of the first k candidates under σ has size k. Using the candidate subset characterization is_ejr_committee_iff_candidate_subsets, verifying EJR for A reduces to showing that every nonempty candidate subset T satisfies c_A * k < |T| * n.
uses
is_ejr_committee_iff_candidate_subsetsrcases hchain with ⟨σ, hσ⟩ use σ intro k hk have hB_ejr := hσ k hk rw [is_ejr_committee_iff_candidate_subsets] at hB_ejr ⊢ rcases hB_ejr with ⟨hWcard, hB_subsets⟩ refine ⟨hWcard, ?_⟩
For any nonempty candidate set T, the count c_A of dissatisfied voters in A is related to the count c_B in B by c_A = (1 if T ⊆ A i ∧ |A i ∩ W| < |T| else 0) + c_B.
Fix a nonempty candidate set T and let W be the committee of size k. Applying the splitting lemma ejr_chain_of_deletable_voter_card_filter_split to the condition that a voter approves all of T but fewer than |T| candidates in W, and rewriting using B j = A (e j), expresses c_A as c_B plus an indicator for voter i.
uses
ejr_chain_of_deletable_voter_card_filter_splitintro T hT set W := Finset.univ.filter fun x : Fin m => (σ x : ℕ) < k have hB_bound := hB_subsets T hT have h_split := ejr_chain_of_deletable_voter_card_filter_split (n := n) i e (fun j => T ⊆ A j ∧ (A j ∩ W).card < T.card) have h_congr : (Finset.univ.filter (fun j => T ⊆ A (e j).1 ∧ (A (e j).1 ∩ W).card < T.card)).card = (Finset.univ.filter (fun j => T ⊆ B j ∧ (B j ∩ W).card < T.card)).card := by congr 1 ext j simp only [Finset.mem_filter, Finset.mem_univ, true_and] rw [hB j] rw [h_congr] at h_split set c_A := (Finset.univ.filter (fun j => T ⊆ A j ∧ (A j ∩ W).card < T.card)).card set c_B := (Finset.univ.filter (fun j => T ⊆ B j ∧ (B j ∩ W).card < T.card)).card
The quota threshold decomposes as |T| * n = |T| * (n - 1) + |T|.
Since n > 0, we have n = (n - 1) + 1 by Nat.sub_add_cancel and Nat.succ_le_of_lt. Multiplying through by |T| gives |T| * n = |T| * (n - 1) + |T|.
uses
Nat.sub_add_cancel,Nat.succ_le_of_lthave h_step : T.card * n = T.card * (n - 1) + T.card := by have : n = n - 1 + 1 := (Nat.sub_add_cancel (Nat.succ_le_of_lt hn)).symm conv_lhs => rw [this] ring
If voter i satisfies the dissatisfaction condition, then c_A = 1 + c_B and k ≤ |T|, which implies c_A * k < |T| * n.
Assume T ⊆ A i and |A i ∩ W| < |T|. Then c_A = 1 + c_B. Since T is nonempty and contained in A i, A i cannot be empty. By the deletability hypothesis, A i must approve at least m - 1 candidates. Since the union A i ∪ W has size at most m, inclusion-exclusion (Finset.card_inter_add_card_union) implies |A i ∩ W| ≥ |A i| + |W| - m ≥ (m - 1) + k - m = k - 1. Combined with |A i ∩ W| < |T|, this forces k ≤ |T|. Using the EJR bound on B (c_B * k < |T| * (n - 1)), linear arithmetic yields c_A * k = c_B * k + k < |T| * (n - 1) + |T| = |T| * n.
uses
if_pos,Finset.subset_empty.mp,Finset.nonempty_iff_ne_empty.mp,False.elim,le_trans,Finset.card_le_univ,Finset.card_inter_add_card_unionby_cases hPi : T ⊆ A i ∧ (A i ∩ W).card < T.card · rw [if_pos hPi] at h_split have hcA : c_A = 1 + c_B := h_split have hAi_nonempty : A i ≠ ∅ := by intro hAi_empty have hTempty : T ⊆ ∅ := by have h := hPi.1 rwa [hAi_empty] at h have : T = ∅ := Finset.subset_empty.mp hTempty exact Finset.nonempty_iff_ne_empty.mp hT this have hAi_card : m - 1 ≤ (A i).card := by cases hi with | inl h_empty => exact False.elim (hAi_nonempty h_empty) | inr h_ge => exact h_ge have h_union : (A i ∪ W).card ≤ m := by exact le_trans (Finset.card_le_univ (A i ∪ W)) (by simp) have h_inc_exc : (A i ∩ W).card + (A i ∪ W).card = (A i).card + W.card := Finset.card_inter_add_card_union (A i) W have h_inter : k - 1 ≤ (A i ∩ W).card := by omega have h_k_le_T : k ≤ T.card := by omega rw [hcA, h_step] linarith
If voter i does not satisfy the dissatisfaction condition, then c_A = c_B and c_A * k < |T| * n.
When voter i does not satisfy the condition, the indicator is 0, so c_A = c_B. Since T is nonempty, |T| > 0 by Finset.Nonempty.card_pos. Combining c_B * k < |T| * (n - 1) with |T| > 0 shows by linear arithmetic that c_A * k = c_B * k < |T| * (n - 1) < |T| * (n - 1) + |T| = |T| * n.
uses
if_neg,zero_add,Finset.Nonempty.card_pos· rw [if_neg hPi, zero_add] at h_split have hcA : c_A = c_B := h_split have hTpos : 0 < T.card := Finset.Nonempty.card_pos hT rw [hcA, h_step] linarith
False.elim- from False, any proposition follows (the principle of explosion)
Finset.card_insert_of_notMem- inserting an element not in a finite set increases its cardinality by 1
Finset.card_inter_add_card_union- inclusion-exclusion principle for two finite sets: the sum of the sizes of their intersection and union equals the sum of their sizes
Finset.card_le_univ- the cardinality of any finite subset of a finite type is at most the cardinality of the whole type
Finset.card_map- mapping a finite set along an injective function preserves its cardinality
Finset.nonempty_iff_ne_empty.mp- a nonempty finite set is not equal to the empty set
Finset.Nonempty.card_pos- a nonempty finite set has strictly positive cardinality
Finset.subset_empty.mp- if a finite set is a subset of the empty set, it must be the empty set
Nat.sub_add_cancel- for natural numbers, subtracting m and then adding m recovers n when m ≤ n
Nat.succ_le_of_lt- if n < m for natural numbers, then n + 1 ≤ m
Subtype.val_injective- the coercion from a subtype to the ambient type is injective
ejr_chain_of_deletable_voter_card_filter_split- the count of voters in Fin n satisfying a predicate P equals the indicator of P i plus the count of voters in Fin (n - 1) satisfying P ∘ e
if_neg- if a condition is false, the if-then-else evaluates to the else branch
if_pos- if a condition is true, the if-then-else evaluates to the then branch
is_ejr_committee_iff_candidate_subsets- a committee W of size k satisfies EJR if and only if every nonempty candidate subset T satisfies c(T) * k < |T| * n, where c(T) counts voters approving all of T but with fewer than |T| committee members
le_trans- the order relation ≤ is transitive
zero_add- adding zero on the left is the identity: 0 + a = a
- The helper lemma `ejr_chain_of_deletable_voter_card_filter_split` is a formal bookkeeping lemma that splits a count over `Fin n` into voter `i` and the remaining `n - 1` voters reindexed by the equivalence `e`. On paper, this is just partitioning a sum into the contribution of voter `i` and the other 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.
theorem ejr_chain_of_deletable_voter_card_filter_split {n : ℕ} (i : Fin n) (e : Fin (n - 1) ≃ {j : Fin n // j ≠ i}) (P : Fin n → Prop) [DecidablePred P] : (Finset.univ.filter P).card = (if P i then 1 else 0) + (Finset.univ.filter (fun j => P (e j).1)).card := by have h1 : (Finset.univ.filter P).card = (if P i then 1 else 0) + (Finset.univ.filter (fun j => j ≠ i ∧ P j)).card := by by_cases hi : P i · rw [if_pos hi] have h_eq : Finset.univ.filter P = insert i (Finset.univ.filter (fun j => j ≠ i ∧ P j)) := by ext x simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_insert] by_cases hx : x = i · subst hx; simp [hi] · simp [hx] rw [h_eq, Finset.card_insert_of_notMem] · omega · simp · rw [if_neg hi, zero_add] congr 1 ext x simp only [Finset.mem_filter, Finset.mem_univ, true_and] constructor · intro hx refine ⟨?_, hx⟩ rintro rfl exact hi hx · intro hx exact hx.2 have h2 : (Finset.univ.filter (fun j => j ≠ i ∧ P j)).card = ((Finset.univ : Finset {j : Fin n // j ≠ i}).filter (fun j => P j.1)).card := by have h := (Finset.card_map ⟨Subtype.val, Subtype.val_injective⟩ (s := (Finset.univ : Finset {j : Fin n // j ≠ i}).filter (fun j => P j.1))).symm rw [h] congr 1 ext x simp tauto have h3 : (Finset.univ.filter (fun j => P (e j).1)).card = ((Finset.univ : Finset {j : Fin n // j ≠ i}).filter (fun j => P j.1)).card := by have : (Finset.univ.filter (fun j => P (e j).1)) = ((Finset.univ : Finset {j : Fin n // j ≠ i}).filter (fun j => P j.1)).map e.symm.toEmbedding := by ext a simp rw [this, Finset.card_map] rw [h1, h2, h3]/-- Profile reduction deleting a voter with empty or nearly-full ballot, decreasing n with m fixed; the same permutation works. -/theorem ejr_chain_of_deletable_voter (n m : ℕ) (A : Fin n → Finset (Fin m)) (hn : 0 < n) (i : Fin n) (hi : A i = ∅ ∨ m - 1 ≤ (A i).card) (B : Fin (n - 1) → Finset (Fin m)) (e : Fin (n - 1) ≃ {j : Fin n // j ≠ i}) (hB : ∀ j, B j = A (e j).1) (hchain : ∃ σ' : Equiv.Perm (Fin m), ∀ k, k ≤ m → is_ejr_committee B k (Finset.univ.filter fun x => (σ' x : ℕ) < k)) : ∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m → is_ejr_committee A k (Finset.univ.filter fun x => (σ x : ℕ) < k) := by rcases hchain with ⟨σ, hσ⟩ use σ intro k hk have hB_ejr := hσ k hk rw [is_ejr_committee_iff_candidate_subsets] at hB_ejr ⊢ rcases hB_ejr with ⟨hWcard, hB_subsets⟩ refine ⟨hWcard, ?_⟩ intro T hT set W := Finset.univ.filter fun x : Fin m => (σ x : ℕ) < k have hB_bound := hB_subsets T hT have h_split := ejr_chain_of_deletable_voter_card_filter_split (n := n) i e (fun j => T ⊆ A j ∧ (A j ∩ W).card < T.card) have h_congr : (Finset.univ.filter (fun j => T ⊆ A (e j).1 ∧ (A (e j).1 ∩ W).card < T.card)).card = (Finset.univ.filter (fun j => T ⊆ B j ∧ (B j ∩ W).card < T.card)).card := by congr 1 ext j simp only [Finset.mem_filter, Finset.mem_univ, true_and] rw [hB j] rw [h_congr] at h_split set c_A := (Finset.univ.filter (fun j => T ⊆ A j ∧ (A j ∩ W).card < T.card)).card set c_B := (Finset.univ.filter (fun j => T ⊆ B j ∧ (B j ∩ W).card < T.card)).card have h_step : T.card * n = T.card * (n - 1) + T.card := by have : n = n - 1 + 1 := (Nat.sub_add_cancel (Nat.succ_le_of_lt hn)).symm conv_lhs => rw [this] ring by_cases hPi : T ⊆ A i ∧ (A i ∩ W).card < T.card · rw [if_pos hPi] at h_split have hcA : c_A = 1 + c_B := h_split have hAi_nonempty : A i ≠ ∅ := by intro hAi_empty have hTempty : T ⊆ ∅ := by have h := hPi.1 rwa [hAi_empty] at h have : T = ∅ := Finset.subset_empty.mp hTempty exact Finset.nonempty_iff_ne_empty.mp hT this have hAi_card : m - 1 ≤ (A i).card := by cases hi with | inl h_empty => exact False.elim (hAi_nonempty h_empty) | inr h_ge => exact h_ge have h_union : (A i ∪ W).card ≤ m := by exact le_trans (Finset.card_le_univ (A i ∪ W)) (by simp) have h_inc_exc : (A i ∩ W).card + (A i ∪ W).card = (A i).card + W.card := Finset.card_inter_add_card_union (A i) W have h_inter : k - 1 ≤ (A i ∩ W).card := by omega have h_k_le_T : k ≤ T.card := by omega rw [hcA, h_step] linarith · rw [if_neg hPi, zero_add] at h_split have hcA : c_A = c_B := h_split have hTpos : 0 < T.card := Finset.Nonempty.card_pos hT rw [hcA, h_step] linarith