AFTD Auto-Formalizing Theoretical Domains

ejr_chain_of_nested_committees

theoremverified

If 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 permutation of the candidates whose prefix of length k is exactly W_k, hence the target chain exists.

Statement

theorem ejr_chain_of_nested_committees {n m : ℕ} (A : Fin n → Finset (Fin m)) :
    (∃ W : ℕ → Finset (Fin m), W 0 = ∅ ∧
        (∀ k, k < m → W k ⊆ W (k + 1)) ∧
        (∀ k, k ≤ m → is_ejr_committee A k (W k))) →
      ∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m →
        is_ejr_committee A k (Finset.univ.filter fun c => (σ c : ℕ) < k)
Source
step towards ejr_committee_monotone_chain_exists
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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| ≥ ℓ.
  • exists_perm_with_prefix_eq_takeEvery duplicate-free list L of length m whose entries are the m candidates is the order of appearance of some permutation σ: for every k ≤…
  • is_ejr_cohesive_groupFor committee size k, a group G of the n voters is ℓ-cohesive if |G| ≥ ℓ·n/k and |∩_{i∈G} A_i| ≥ ℓ.
Used by 3

The proof, explained

Given a nested chain of EJR committees ∅ = W_0 ⊆ W_1 ⊆ ... ⊆ W_m, each committee W_k has cardinality k, meaning that each step adds exactly one candidate x(k) ∈ W_(k+1) \ W_k. Monotonicity of the sequence of committees ensures that these added candidates x(0), ..., x(m-1) are pairwise distinct. Ordering the candidates as a list and invoking exists_perm_with_prefix_eq_take produces a permutation σ whose prefixes of length k reconstruct each W_k, showing that the target chain of EJR committees exists.

  1. Unpack the nested EJR committee sequence and note that each committee W_k has cardinality k.

    We unpack the hypothesis into the committee sequence W, the base condition W_0 = ∅ (hW0), the one-step inclusion W_k ⊆ W_(k+1) (hmono), and the EJR property for each committee (hEJR). By definition of is_ejr_committee, an EJR committee of target size k must have cardinality k (hcard).

    lines 8–9

      rintro ⟨W, hW0, hmono, hEJR⟩
      have hcard : ∀ k, k ≤ m → (W k).card = k := fun k hk => (hEJR k hk).1
  2. Each step adds exactly one candidate: |W_(k+1) \ W_k| = 1 for every k < m.

    Because W_k ⊆ W_(k+1), the cardinality of the difference plus |W_k| equals |W_(k+1)| by Finset.card_sdiff_add_card_eq_card. Since |W_k| = k and |W_(k+1)| = k + 1, linear arithmetic forces the difference to have cardinality 1.

    lines 10–17

    uses Finset.card_sdiff_add_card_eq_card

      have hdiff_card : ∀ k : Fin m, (W (k.1 + 1) \ W k.1).card = 1 := by
        intro k
        have hklt : (k : ℕ) < m := k.2
        have hsub : W k.1 ⊆ W (k.1 + 1) := hmono k.1 hklt
        have h1 := Finset.card_sdiff_add_card_eq_card hsub
        have h2 : (W k.1).card = k.1 := hcard k.1 (by omega)
        have h3 : (W (k.1 + 1)).card = k.1 + 1 := hcard (k.1 + 1) (by omega)
        omega
  3. Define x(k) as the unique candidate added at step k, satisfying W_(k+1) \ W_k = {x(k)}, x(k) ∈ W_(k+1), and x(k) ∉ W_k.

    Because W_(k+1) \ W_k has cardinality 1, Finset.card_eq_one.mp yields a unique element x(k) such that W_(k+1) \ W_k = {x(k)}. From Finset.mem_sdiff.mp and Finset.mem_singleton_self, this element x(k) is in W_(k+1) and not in W_k.

    lines 18–26

    uses Finset.card_eq_one.mp, Finset.mem_sdiff.mp, Finset.mem_singleton_self

      let x : Fin m → Fin m := fun k => (Finset.card_eq_one.mp (hdiff_card k)).choose
      have hx : ∀ k : Fin m, W (k.1 + 1) \ W k.1 = {x k} :=
        fun k => (Finset.card_eq_one.mp (hdiff_card k)).choose_spec
      have hx_mem' : ∀ k : Fin m, x k ∈ W (k.1 + 1) := by
        intro k
        exact (Finset.mem_sdiff.mp (by rw [hx k]; exact Finset.mem_singleton_self (x k))).1
      have hx_not : ∀ k : Fin m, x k ∉ W k.1 := by
        intro k
        exact (Finset.mem_sdiff.mp (by rw [hx k]; exact Finset.mem_singleton_self (x k))).2
  4. The committee sequence is monotonic for all indices: W_a ⊆ W_b whenever a ≤ b ≤ m.

    We prove W_a ⊆ W_b by induction on b. In the base case b = 0, a ≤ 0 forces a = 0, and reflexivity (Finset.Subset.refl) gives W_0 ⊆ W_0. For the successor step b + 1, either a < b + 1 (so a ≤ b, and the result follows from the induction hypothesis W_a ⊆ W_b and one-step inclusion W_b ⊆ W_(b+1)) or a = b + 1 (which holds trivially by reflexivity).

    lines 27–37

    uses Finset.Subset.refl, lt_or_ge

      have hmono' : ∀ a b, a ≤ b → b ≤ m → W a ⊆ W b := by
        intro a b hab hbm
        induction b with
        | zero =>
          have : a = 0 := by omega
          subst this; exact Finset.Subset.refl _
        | succ b ih =>
          rcases lt_or_ge a (b + 1) with hlt | hge
          · exact (ih (by omega) (by omega)).trans (hmono b (by omega))
          · have : a = b + 1 := by omega
            subst this; exact Finset.Subset.refl _
  5. The assignment x : Fin m → Fin m of added candidates is injective.

    Suppose x(i) = x(j). By trichotomy (lt_trichotomy), either i < j, i = j, or j < i. If i < j, then i + 1 ≤ j, so x(i) ∈ W_(i+1) ⊆ W_j by monotonicity, which means x(j) ∈ W_j, contradicting x(j) ∉ W_j. The case j < i is symmetric. Thus i = j as natural numbers, which implies i = j in Fin m by Fin.ext.

    lines 38–53

    uses lt_trichotomy, le_of_lt, Fin.ext

      have hx_inj : Function.Injective x := by
        intro i j hij
        have hval : (i : ℕ) = (j : ℕ) := by
          rcases lt_trichotomy (i : ℕ) (j : ℕ) with hlt | heq | hgt
          · exfalso
            have h1 : x i ∈ W ((i:ℕ) + 1) := hx_mem' i
            have h2 : W ((i:ℕ) + 1) ⊆ W j.1 := hmono' _ _ (by omega) (le_of_lt j.2)
            have h3 : x j ∉ W j.1 := hx_not j
            exact h3 (hij ▸ h2 h1)
          · exact heq
          · exfalso
            have h1 : x j ∈ W ((j:ℕ) + 1) := hx_mem' j
            have h2 : W ((j:ℕ) + 1) ⊆ W i.1 := hmono' _ _ (by omega) (le_of_lt i.2)
            have h3 : x i ∉ W i.1 := hx_not i
            exact h3 (hij.symm ▸ h2 h1)
        exact Fin.ext hval
  6. Convert x into a duplicate-free list of candidates and obtain a permutation σ whose prefixes match the prefix sublists.

    We form the list L = List.ofFn x of length m. Because x is injective, L has no duplicate entries (List.nodup_ofFn). The auxiliary lemma exists_perm_with_prefix_eq_take then provides a permutation σ of Fin m whose prefix filters {c | σ(c) < k} equal the set of candidates in the first k elements of L for all k ≤ m.

    lines 54–60

    uses List.nodup_ofFn, exists_perm_with_prefix_eq_take

      let L : List (Fin m) := List.ofFn x
      have hlen : L.length = m := by simp [L]
      have hLnodup : L.Nodup := by
        show (List.ofFn x).Nodup
        rw [List.nodup_ofFn]
        exact hx_inj
      obtain ⟨σ, hσ⟩ := exists_perm_with_prefix_eq_take L hLnodup hlen
  7. For each k ≤ m, the set of candidates in the first k elements of L is precisely W_k.

    We proceed by induction on k. For k = 0, taking 0 elements gives ∅ = W_0. For k + 1 ≤ m, the prefix of length k + 1 appends L[k] = x(k) to the prefix of length k (using List.take_add_one, List.getElem?_eq_getElem, and Option.toList_some). Applying List.toFinset_append and the induction hypothesis, this set is W_k ∪ {x(k)}. Mutual inclusion (Finset.Subset.antisymm) shows W_k ∪ {x(k)} = W_(k+1): forward inclusion holds because W_k ⊆ W_(k+1) and x(k) ∈ W_(k+1), while reverse inclusion holds because any a ∈ W_(k+1) either lies in W_k (Finset.mem_union_left) or lies in W_(k+1) \ W_k = {x(k)} (Finset.mem_sdiff.mpr, Finset.mem_union_right).

    lines 61–95

    uses List.take_add_one, List.getElem?_eq_getElem, Option.toList_some, List.toFinset_append, Finset.Subset.antisymm, Finset.mem_union.mp, Finset.mem_singleton, Finset.mem_union_left, Finset.mem_union_right, Finset.mem_sdiff.mpr

      have hprefix : ∀ k, k ≤ m → (L.take k).toFinset = W k := by
        intro k
        induction k with
        | zero =>
          intro _
          simp [hW0]
        | succ k ih =>
          intro hk
          have hkm : k < m := hk
          have hk_le : k ≤ m := le_of_lt hkm
          have hk_lt_len : k < L.length := by rw [hlen]; exact hkm
          have hLk : L[k] = x ⟨k, hkm⟩ := by
            simp only [L, List.getElem_ofFn]
          have htake : (L.take (k + 1)).toFinset = (L.take k).toFinset ∪ {x ⟨k, hkm⟩} := by
            rw [List.take_add_one, List.getElem?_eq_getElem hk_lt_len, Option.toList_some,
              List.toFinset_append, hLk]
            simp
          have hunion : W k ∪ {x ⟨k, hkm⟩} = W (k + 1) := by
            apply Finset.Subset.antisymm
            · intro a ha
              rcases Finset.mem_union.mp ha with h | h
              · exact hmono k hkm h
              · rw [Finset.mem_singleton] at h
                rw [h]
                have := hx_mem' ⟨k, hkm⟩
                simpa using this
            · intro a ha
              by_cases h : a ∈ W k
              · exact Finset.mem_union_left _ h
              · apply Finset.mem_union_right
                have hmem : a ∈ W (k + 1) \ W k := Finset.mem_sdiff.mpr ⟨ha, h⟩
                have hset := hx ⟨k, hkm⟩
                rw [hset] at hmem
                exact hmem
          rw [htake, ih hk_le, hunion]
  8. The permutation σ satisfies the theorem: each prefix {c | σ(c) < k} is the EJR committee W_k.

    For each k ≤ m, rewriting with hσ and hprefix shows that {c | σ(c) < k} equals the set of elements in the first k entries of L, which equals W_k. Since each W_k was assumed to be an EJR committee (hEJR), σ witnesses the required permutation.

    line 96

      exact ⟨σ, fun k hk => by rw [hσ k hk, hprefix k hk]; exact hEJR k hk⟩
Finset.card_sdiff_add_card_eq_card
If s ⊆ t, then the cardinality of t \ s plus the cardinality of s equals the cardinality of t.
Finset.card_eq_one.mp
A finite set has cardinality 1 if and only if it is a singleton set {a} for some element a.
Finset.mem_sdiff.mp
An element belongs to s \ t if and only if it belongs to s and does not belong to t.
Finset.mem_singleton_self
Every element belongs to its own singleton set.
Finset.Subset.refl
Every set is a subset of itself.
lt_or_ge
In a linear order, either a < b or b ≤ a.
lt_trichotomy
For any two elements in a linear order, exactly one of a < b, a = b, or b < a holds.
le_of_lt
Strict inequality implies non-strict inequality.
Fin.ext
Two elements of Fin n are equal if their underlying natural numbers are equal.
List.nodup_ofFn
The list created by evaluating a function f on Fin n contains no duplicates if and only if f is injective.
exists_perm_with_prefix_eq_take
For any duplicate-free list L of all m elements, there exists a permutation σ whose prefix filters {c | σ(c) < k} match the set of elements in the first k entries of L.
List.take_add_one
The prefix of length i + 1 of a list equals the prefix of length i concatenated with the list containing the i-th element.
List.getElem?_eq_getElem
Accessing the i-th element of a list within its length returns some of that element.
Option.toList_some
Converting some a of an option to a list yields the singleton list [a].
List.toFinset_append
The set of elements in a concatenated list is the union of the sets of elements of each list.
Finset.Subset.antisymm
Two sets are equal if each is a subset of the other.
Finset.mem_union.mp
An element belongs to a union s ∪ t if and only if it belongs to s or to t.
Finset.mem_singleton
An element belongs to {a} if and only if it equals a.
Finset.mem_union_left
If an element belongs to s, it belongs to s ∪ t.
Finset.mem_union_right
If an element belongs to t, it belongs to s ∪ t.
Finset.mem_sdiff.mpr
If an element belongs to s and does not belong to t, it belongs to s \ t.

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

/-- A nested family of EJR committees of sizes 0, 1, ..., m yields a permutation whose every prefix is the corresponding EJR committee. -/theorem ejr_chain_of_nested_committees {n m : ℕ} (A : Fin n → Finset (Fin m)) :    (∃ W : ℕ → Finset (Fin m), W 0 = ∅ ∧        (∀ k, k < m → W k ⊆ W (k + 1)) ∧        (∀ k, k ≤ m → is_ejr_committee A k (W k))) →      ∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m →        is_ejr_committee A k (Finset.univ.filter fun c => (σ c : ℕ) < k) := by  rintro ⟨W, hW0, hmono, hEJR⟩  have hcard : ∀ k, k ≤ m → (W k).card = k := fun k hk => (hEJR k hk).1  have hdiff_card : ∀ k : Fin m, (W (k.1 + 1) \ W k.1).card = 1 := by    intro k    have hklt : (k : ℕ) < m := k.2    have hsub : W k.1 ⊆ W (k.1 + 1) := hmono k.1 hklt    have h1 := Finset.card_sdiff_add_card_eq_card hsub    have h2 : (W k.1).card = k.1 := hcard k.1 (by omega)    have h3 : (W (k.1 + 1)).card = k.1 + 1 := hcard (k.1 + 1) (by omega)    omega  let x : Fin m → Fin m := fun k => (Finset.card_eq_one.mp (hdiff_card k)).choose  have hx : ∀ k : Fin m, W (k.1 + 1) \ W k.1 = {x k} :=    fun k => (Finset.card_eq_one.mp (hdiff_card k)).choose_spec  have hx_mem' : ∀ k : Fin m, x k ∈ W (k.1 + 1) := by    intro k    exact (Finset.mem_sdiff.mp (by rw [hx k]; exact Finset.mem_singleton_self (x k))).1  have hx_not : ∀ k : Fin m, x k ∉ W k.1 := by    intro k    exact (Finset.mem_sdiff.mp (by rw [hx k]; exact Finset.mem_singleton_self (x k))).2  have hmono' : ∀ a b, a ≤ b → b ≤ m → W a ⊆ W b := by    intro a b hab hbm    induction b with    | zero =>      have : a = 0 := by omega      subst this; exact Finset.Subset.refl _    | succ b ih =>      rcases lt_or_ge a (b + 1) with hlt | hge      · exact (ih (by omega) (by omega)).trans (hmono b (by omega))      · have : a = b + 1 := by omega        subst this; exact Finset.Subset.refl _  have hx_inj : Function.Injective x := by    intro i j hij    have hval : (i : ℕ) = (j : ℕ) := by      rcases lt_trichotomy (i : ℕ) (j : ℕ) with hlt | heq | hgt      · exfalso        have h1 : x i ∈ W ((i:ℕ) + 1) := hx_mem' i        have h2 : W ((i:ℕ) + 1) ⊆ W j.1 := hmono' _ _ (by omega) (le_of_lt j.2)        have h3 : x j ∉ W j.1 := hx_not j        exact h3 (hij ▸ h2 h1)      · exact heq      · exfalso        have h1 : x j ∈ W ((j:ℕ) + 1) := hx_mem' j        have h2 : W ((j:ℕ) + 1) ⊆ W i.1 := hmono' _ _ (by omega) (le_of_lt i.2)        have h3 : x i ∉ W i.1 := hx_not i        exact h3 (hij.symm ▸ h2 h1)    exact Fin.ext hval  let L : List (Fin m) := List.ofFn x  have hlen : L.length = m := by simp [L]  have hLnodup : L.Nodup := by    show (List.ofFn x).Nodup    rw [List.nodup_ofFn]    exact hx_inj  obtain ⟨σ, hσ⟩ := exists_perm_with_prefix_eq_take L hLnodup hlen  have hprefix : ∀ k, k ≤ m → (L.take k).toFinset = W k := by    intro k    induction k with    | zero =>      intro _      simp [hW0]    | succ k ih =>      intro hk      have hkm : k < m := hk      have hk_le : k ≤ m := le_of_lt hkm      have hk_lt_len : k < L.length := by rw [hlen]; exact hkm      have hLk : L[k] = x ⟨k, hkm⟩ := by        simp only [L, List.getElem_ofFn]      have htake : (L.take (k + 1)).toFinset = (L.take k).toFinset ∪ {x ⟨k, hkm⟩} := by        rw [List.take_add_one, List.getElem?_eq_getElem hk_lt_len, Option.toList_some,          List.toFinset_append, hLk]        simp      have hunion : W k ∪ {x ⟨k, hkm⟩} = W (k + 1) := by        apply Finset.Subset.antisymm        · intro a ha          rcases Finset.mem_union.mp ha with h | h          · exact hmono k hkm h          · rw [Finset.mem_singleton] at h            rw [h]            have := hx_mem' ⟨k, hkm⟩            simpa using this        · intro a ha          by_cases h : a ∈ W k          · exact Finset.mem_union_left _ h          · apply Finset.mem_union_right            have hmem : a ∈ W (k + 1) \ W k := Finset.mem_sdiff.mpr ⟨ha, h⟩            have hset := hx ⟨k, hkm⟩            rw [hset] at hmem            exact hmem      rw [htake, ih hk_le, hunion]  exact ⟨σ, fun k hk => by rw [hσ k hk, hprefix k hk]; exact hEJR k hk⟩
See it in the graphDiscuss this resultChallenge it