AFTD Auto-Formalizing Theoretical Domains

ejr_chain_of_deletable_voter

theoremverified

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 LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — 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.

  1. 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}|.

    lines 5–27

    uses if_pos, Finset.card_insert_of_notMem, if_neg, zero_add

      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
  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.

    lines 28–36

    uses Finset.card_map, Subtype.val_injective

      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
  3. 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.

    lines 37–44

    uses Finset.card_map

      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]
  4. 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.

    lines 55–61

    uses is_ejr_committee_iff_candidate_subsets

      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, ?_⟩
  5. 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.

    lines 62–75

    uses ejr_chain_of_deletable_voter_card_filter_split

      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
  6. 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|.

    lines 76–79

    uses Nat.sub_add_cancel, Nat.succ_le_of_lt

      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
  7. 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.

    lines 80–103

    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_union

      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
  8. 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.

    lines 104–108

    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

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

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
See it in the graphDiscuss this resultChallenge it