AFTD Auto-Formalizing Theoretical Domains

ejr_chain_candidates_le_three

theoremverified

Every approval profile on at most three candidates admits an EJR committee chain.

Statement

theorem ejr_chain_candidates_le_three (n m : ℕ) (A : Fin n → Finset (Fin m))
    (hn : 0 < n) (hm : m ≤ 3) :
    ∃ σ : 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 6
  • 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_chain_of_nested_committeesIf 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…
  • is_ejr_committee_zeroFor every approval profile with at least one voter, the empty committee is an EJR committee of size 0.
  • ejr_committee_univFor every approval profile with at least one voter, the committee consisting of all m candidates satisfies EJR at committee size m.
  • ejr_adjacent_committees_existsFor every approval profile with at least one voter and every k smaller than the candidate count, there exist nested committees W subset V…
  • ejr_committee_existsFor every approval profile with at least one voter and every committee size k ≤ m, some committee of size k satisfies EJR (for instance…

The proof, explained

By ejr_chain_of_nested_committees, constructing an EJR committee chain reduces to finding a nested family of committees ∅ = W₀ ⊆ W₁ ⊆ ⋯ ⊆ Wₘ where each Wₖ satisfies EJR for size k. Since m ≤ 3, the proof proceeds by case analysis on m ∈ {0, 1, 2, 3}. The boundary committees W₀ = ∅ and Wₘ = Finset.univ are always EJR, which directly settles m ≤ 1. For m = 2, any EJR committee of size 1 can be placed between ∅ and the universal set, and for m = 3, the existence of adjacent nested EJR committees W₁ ⊆ W₂ of sizes 1 and 2 completes the four-committee chain.

  1. It suffices to construct a nested sequence of EJR committees of sizes k = 0, …, m for each candidate count m ∈ {0, 1, 2, 3}.

    By ejr_chain_of_nested_committees, finding an EJR committee chain reduces to constructing a sequence of nested committees ∅ = W₀ ⊆ W₁ ⊆ ⋯ ⊆ Wₘ where each Wₖ satisfies EJR for size k. Since the total number of candidates satisfies m ≤ 3, we perform a case analysis on the four possible values m = 0, 1, 2, 3.

    lines 6–7

    uses ejr_chain_of_nested_committees

      apply ejr_chain_of_nested_committees
      interval_cases m
  2. When m = 0, the constant empty sequence forms an EJR committee chain.

    For m = 0, we set Wₖ = ∅ for all k. The base condition W₀ = ∅ holds by definition. The nesting condition is vacuous since there is no k < 0. Finally, the only size to check is k = 0, and the empty set is an EJR committee of size 0 by is_ejr_committee_zero.

    lines 8–14

    uses is_ejr_committee_zero

      · -- m = 0
        refine ⟨fun _ => ∅, rfl, ?_, ?_⟩
        · intro k hk; omega
        · intro k hk
          have hk0 : k = 0 := by omega
          subst hk0
          exact is_ejr_committee_zero A hn
  3. When m = 1, the sequence W₀ = ∅ and W₁ = Finset.univ forms an EJR committee chain.

    For m = 1, we define W₀ = ∅ and Wₖ = Finset.univ for k ≥ 1. For k = 0 < 1, the inclusion ∅ ⊆ Finset.univ is immediate. For EJR satisfaction, W₀ = ∅ is an EJR committee of size 0 by is_ejr_committee_zero, and W₁ = Finset.univ is an EJR committee of size 1 by ejr_committee_univ.

    lines 15–23

    uses is_ejr_committee_zero, ejr_committee_univ

      · -- m = 1
        refine ⟨fun k => if k = 0 then ∅ else Finset.univ, rfl, ?_, ?_⟩
        · intro k hk
          interval_cases k
          · simp
        · intro k hk
          interval_cases k
          · simpa using is_ejr_committee_zero A hn
          · simpa using ejr_committee_univ (m := 1) A hn
  4. When m = 2, extending an EJR committee of size 1 with ∅ and Finset.univ forms an EJR committee chain.

    For m = 2, we obtain an EJR committee W₁ of size 1 using ejr_committee_exists, and define W₀ = ∅, W₁ = W₁, and W₂ = Finset.univ. The nesting ∅ ⊆ W₁ ⊆ Finset.univ holds immediately from the properties of ∅ and the universal set. For each size k ≤ 2, W₀ is EJR by is_ejr_committee_zero, W₁ is EJR by construction, and W₂ = Finset.univ is EJR by ejr_committee_univ.

    lines 24–35

    uses ejr_committee_exists, is_ejr_committee_zero, ejr_committee_univ

      · -- m = 2
        obtain ⟨W1, hW1⟩ := ejr_committee_exists n 2 A hn 1 (by norm_num)
        refine ⟨fun k => if k = 0 then ∅ else if k = 1 then W1 else Finset.univ, rfl, ?_, ?_⟩
        · intro k hk
          interval_cases k
          · simp
          · simp
        · intro k hk
          interval_cases k
          · simpa using is_ejr_committee_zero A hn
          · simpa using hW1
          · simpa using ejr_committee_univ (m := 2) A hn
  5. When m = 3, sandwiching a pair of adjacent nested EJR committees between ∅ and Finset.univ forms an EJR committee chain.

    For m = 3, we invoke ejr_adjacent_committees_exists at k = 1 < 3 to obtain nested committees W₁ ⊆ W₂ of sizes 1 and 2, both satisfying EJR. We define the sequence W₀ = ∅, W₁, W₂, and W₃ = Finset.univ. The inclusions ∅ ⊆ W₁ and W₂ ⊆ Finset.univ are trivial, while W₁ ⊆ W₂ is guaranteed by the lemma. Each committee in the chain satisfies EJR: W₀ by is_ejr_committee_zero, W₁ and W₂ by construction, and W₃ = Finset.univ by ejr_committee_univ.

    lines 36–49

    uses ejr_adjacent_committees_exists, is_ejr_committee_zero, ejr_committee_univ

      · -- m = 3
        obtain ⟨W1, W2, h12, hW1, hW2⟩ := ejr_adjacent_committees_exists A hn 1 (by norm_num)
        refine ⟨fun k => if k = 0 then ∅ else if k = 1 then W1 else if k = 2 then W2 else Finset.univ, rfl, ?_, ?_⟩
        · intro k hk
          interval_cases k
          · simp
          · simpa using h12
          · simp
        · intro k hk
          interval_cases k
          · simpa using is_ejr_committee_zero A hn
          · simpa using hW1
          · simpa using hW2
          · simpa using ejr_committee_univ (m := 3) A hn
ejr_chain_of_nested_committees
A sequence of nested committees ∅ = W₀ ⊆ W₁ ⊆ ⋯ ⊆ Wₘ where each Wₖ is an EJR committee of size k can be reordered into an EJR committee chain (a permutation whose prefixes of length k satisfy EJR for every k ≤ m).
is_ejr_committee_zero
For any approval profile with at least one voter, the empty committee ∅ is an EJR committee of size 0.
ejr_committee_univ
For any approval profile with at least one voter, the universal set of all m candidates is an EJR committee of size m.
ejr_committee_exists
For any approval profile with at least one voter and any committee size k ≤ m, there exists an EJR committee of size k.
ejr_adjacent_committees_exists
For any approval profile with at least one voter and any k < m, there exists a pair of nested committees W ⊆ V of sizes k and k + 1, respectively, both satisfying EJR.

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

/-- Every approval profile on at most three candidates admits an EJR committee chain. -/theorem ejr_chain_candidates_le_three (n m : ℕ) (A : Fin n → Finset (Fin m))    (hn : 0 < n) (hm : m ≤ 3) :    ∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m →      is_ejr_committee A k (Finset.univ.filter fun c => (σ c : ℕ) < k) := by  apply ejr_chain_of_nested_committees  interval_cases m  · -- m = 0    refine ⟨fun _ => ∅, rfl, ?_, ?_⟩    · intro k hk; omega    · intro k hk      have hk0 : k = 0 := by omega      subst hk0      exact is_ejr_committee_zero A hn  · -- m = 1    refine ⟨fun k => if k = 0 then ∅ else Finset.univ, rfl, ?_, ?_⟩    · intro k hk      interval_cases k      · simp    · intro k hk      interval_cases k      · simpa using is_ejr_committee_zero A hn      · simpa using ejr_committee_univ (m := 1) A hn  · -- m = 2    obtain ⟨W1, hW1⟩ := ejr_committee_exists n 2 A hn 1 (by norm_num)    refine ⟨fun k => if k = 0 then ∅ else if k = 1 then W1 else Finset.univ, rfl, ?_, ?_⟩    · intro k hk      interval_cases k      · simp      · simp    · intro k hk      interval_cases k      · simpa using is_ejr_committee_zero A hn      · simpa using hW1      · simpa using ejr_committee_univ (m := 2) A hn  · -- m = 3    obtain ⟨W1, W2, h12, hW1, hW2⟩ := ejr_adjacent_committees_exists A hn 1 (by norm_num)    refine ⟨fun k => if k = 0 then ∅ else if k = 1 then W1 else if k = 2 then W2 else Finset.univ, rfl, ?_, ?_⟩    · intro k hk      interval_cases k      · simp      · simpa using h12      · simp    · intro k hk      interval_cases k      · simpa using is_ejr_committee_zero A hn      · simpa using hW1      · simpa using hW2      · simpa using ejr_committee_univ (m := 3) A hn
See it in the graphDiscuss this resultChallenge it