AFTD Auto-Formalizing Theoretical Domains

ejr_chain_nested_committees_iff

theoremverified

An approval profile admits an EJR committee chain if and only if it admits an increasing sequence of EJR committees of sizes 0 through m.

Statement

theorem ejr_chain_nested_committees_iff {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)) ↔
      (∃ W : ℕ → Finset (Fin m), W 0 = ∅ ∧
        (∀ k, k < m → W k ⊆ W (k + 1)) ∧
        (∀ k, k ≤ m → is_ejr_committee A k (W k)))
Source
step towards ejr_committee_monotone_chain_exists
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • 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…

The proof, explained

The equivalence states that an EJR committee chain (a permutation whose initial segments of size k ≤ m are EJR committees) is equivalent to having a nested sequence of EJR committees W(0) ⊆ W(1) ⊆ ⋯ ⊆ W(m). In the forward direction, defining W(k) to be the first k candidates according to the permutation σ immediately yields an empty initial committee, nested sets by transitivity of inequality, and EJR committees by hypothesis. The backward direction is established directly by the helper theorem `ejr_chain_of_nested_committees`.

  1. In the forward direction, given an EJR chain permutation σ, setting W(k) = {c | σ(c) < k} leaves three conditions to verify.

    We split the equivalence into both directions. In the forward direction, we assume a permutation σ such that for each k ≤ m, the prefix committee {c | σ(c) < k} is an EJR committee of size k. We witness the existential by choosing the sequence W(k) = {c | σ(c) < k}, leaving three goals: W(0) = ∅, nesting of successive committees, and the EJR property for each k ≤ m.

    lines 8–10

      constructor
      · rintro ⟨σ, hσ⟩
        refine ⟨fun k => Finset.univ.filter fun c => (σ c : ℕ) < k, ?_, ?_, ?_⟩
  2. W(0) = ∅.

    By definition, W(0) = {c | σ(c) < 0}. Because no natural number is strictly less than 0, no candidate satisfies the condition, so the set simplifies to the empty set.

    line 11

        · simp
  3. W(k) ⊆ W(k + 1) for every k < m.

    Let k < m and consider a candidate c ∈ W(k). Unfolding membership in the filtered universal set with `Finset.mem_filter`, `Finset.mem_univ`, and `true_and` reduces this to σ(c) < k. Since k < k + 1, linear arithmetic (`omega`) deduces σ(c) < k + 1, which means c ∈ W(k + 1).

    lines 12–14

    uses Finset.mem_filter, Finset.mem_univ, true_and

        · intro k _ c hc
          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hc ⊢
          omega
  4. Each committee W(k) satisfies EJR for k ≤ m.

    For any k ≤ m, W(k) is {c | σ(c) < k}, which is an EJR committee of size k by the assumption on σ.

    lines 15–16

        · intro k hk
          exact hσ k hk
  5. Conversely, any nested sequence of EJR committees yields an EJR committee chain.

    The reverse implication follows directly from the previously proved theorem `ejr_chain_of_nested_committees` applied to the approval profile A.

    line 17

    uses ejr_chain_of_nested_committees

      · exact ejr_chain_of_nested_committees A
Finset.mem_filter
An element belongs to a filtered finite set if and only if it belongs to the original set and satisfies the filtering predicate.
Finset.mem_univ
Every element of a finite type belongs to the universal finite set `Finset.univ`.
true_and
The conjunction `True ∧ p` is equivalent to `p`.
ejr_chain_of_nested_committees
If an approval profile admits a nested sequence of EJR committees of sizes 0 through m, then it admits an EJR committee chain given by a permutation.

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

/-- An approval profile admits an EJR committee chain if and only if it admits an increasing sequence of EJR committees of sizes 0 through m. -/theorem ejr_chain_nested_committees_iff {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)) ↔      (∃ W : ℕ → Finset (Fin m), W 0 = ∅ ∧        (∀ k, k < m → W k ⊆ W (k + 1)) ∧        (∀ k, k ≤ m → is_ejr_committee A k (W k))) := by  constructor  · rintro ⟨σ, hσ⟩    refine ⟨fun k => Finset.univ.filter fun c => (σ c : ℕ) < k, ?_, ?_, ?_⟩    · simp    · intro k _ c hc      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hc ⊢      omega    · intro k hk      exact hσ k hk  · exact ejr_chain_of_nested_committees A
See it in the graphDiscuss this resultChallenge it