AFTD Auto-Formalizing Theoretical Domains

ejr_chain_iff_level_supporters

theoremverified

A permutation whose every prefix of length k is an EJR committee exists if and only if there is a permutation such that for every k ≤ m and every nonempty candidate subset T, the number of voters approving all of T who approve fewer than |T| candidates among the first k positions, times k, is strictly below |T| times the number of voters.

Statement

theorem ejr_chain_iff_level_supporters {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)) ↔
      (∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m → ∀ T : Finset (Fin m), T.Nonempty →
        (Finset.univ.filter fun i => T ⊆ A i ∧
          (A i ∩ Finset.univ.filter fun c => (σ c : ℕ) < k).card < T.card).card * k
        < T.card * n)
Source
step towards ejr_committee_monotone_chain_exists
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • is_ejr_committee_iff_candidate_subsetsEJR is equivalent to the correct committee size together with the underrepresented-supporter inequality for every nonempty candidate…
  • 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| ≥ ℓ.
Used by 2
  • ejr_chain_two_votersFor every approval profile with two voters and any number of candidates, there is an ordering of the candidates every prefix of which is…
  • ejr_chain_singleton_ballotsIf every voter approves at most one candidate, then there is an ordering of the candidates every prefix of which is an EJR committee of…

The proof, explained

The theorem characterizes the existence of an EJR chain—a permutation of candidates whose prefixes of all sizes k ≤ m are EJR committees—in terms of a level-by-level counting condition on candidate subsets. By is_ejr_committee_iff_candidate_subsets, a committee of size k satisfies EJR if and only if it satisfies this supporter bound for all nonempty candidate subsets T. Since any prefix of length k determined by a permutation has size exactly k (as established in a helper lemma), the two existential statements are equivalent level by level.

  1. The k-candidate prefix {c | σ(c) < k} equals the image under σ⁻¹ of the initial segment {x | x < k}.

    By set extensionality, a candidate c satisfies σ(c) < k if and only if c is the image under the inverse permutation σ⁻¹ of some candidate x with x < k, where the forward witness is simply x = σ(c).

    lines 3–11

      have hpre : (Finset.univ.filter fun c : Fin m => (σ c : ℕ) < k)
          = (Finset.univ.filter fun x : Fin m => (x : ℕ) < k).image σ.symm := by
        ext c
        simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_image]
        constructor
        · intro h
          exact ⟨σ c, h, by simp⟩
        · rintro ⟨x, hx, rfl⟩
          simpa using hx
  2. The initial segment {x ∈ Fin m | x < k} is the image of Fin k under the canonical inclusion.

    By set extensionality, an element of Fin m lies in the image of Fin.castLE hk if and only if its index as a natural number is strictly less than k.

    lines 12–20

      have himg : (Finset.univ : Finset (Fin k)).image (Fin.castLE hk)
          = Finset.univ.filter (fun x : Fin m => (x : ℕ) < k) := by
        ext x
        simp only [Finset.mem_image, Finset.mem_univ, true_and, Finset.mem_filter]
        constructor
        · rintro ⟨a, rfl⟩
          simp
        · intro hx
          exact ⟨⟨x, hx⟩, Fin.ext rfl⟩
  3. The k-candidate prefix has cardinality k.

    Because both the permutation inverse σ⁻¹ and the inclusion Fin.castLE hk are injective, the cardinality of the prefix equals the cardinality of Fin k, which is k.

    lines 21–22

    uses Finset.card_image_of_injective, Fin.castLE_injective, Finset.card_univ, Fintype.card_fin

      rw [hpre, Finset.card_image_of_injective _ σ.symm.injective, ← himg,
        Finset.card_image_of_injective _ (Fin.castLE_injective hk), Finset.card_univ, Fintype.card_fin]
  4. If a permutation forms an EJR chain, then its prefixes satisfy the level-by-level candidate-subset supporter condition.

    Splitting the bi-implication, suppose σ forms an EJR chain. Then for every k ≤ m, the prefix committee of length k is an EJR committee. Applying the forward direction of is_ejr_committee_iff_candidate_subsets immediately yields the desired inequality for every nonempty subset of candidates T.

    lines 32–35

    uses is_ejr_committee_iff_candidate_subsets

      constructor
      · rintro ⟨σ, hσ⟩
        exact ⟨σ, fun k hk T hT =>
          ((is_ejr_committee_iff_candidate_subsets A k _).mp (hσ k hk)).2 T hT⟩
  5. Conversely, if a permutation satisfies the candidate-subset supporter condition at every level k ≤ m, then its prefixes form an EJR chain.

    Given such a permutation σ, we show each prefix of length k ≤ m is an EJR committee by applying the characterization is_ejr_committee_iff_candidate_subsets. This requires that the prefix has size k (which holds by ejr_chain_iff_level_supporters_card_prefix) and that the candidate-subset inequality holds for all nonempty T (which is our hypothesis).

    lines 36–39

    uses is_ejr_committee_iff_candidate_subsets, ejr_chain_iff_level_supporters_card_prefix

      · rintro ⟨σ, hσ⟩
        refine ⟨σ, fun k hk => ?_⟩
        rw [is_ejr_committee_iff_candidate_subsets]
        exact ⟨ejr_chain_iff_level_supporters_card_prefix σ k hk, fun T hT => hσ k hk T hT⟩
Fin.castLE_injective
The canonical inclusion of Fin n into Fin m for n ≤ m is injective.
Finset.card_image_of_injective
The image of a finite set under an injective map has the same cardinality as the original set.
Finset.card_univ
The cardinality of the universal finset on a finite type equals the cardinality of the underlying type.
Fintype.card_fin
The cardinality of Fin n is n.
ejr_chain_iff_level_supporters_card_prefix
For any permutation σ on m elements and any k ≤ m, the set of elements mapped by σ to values strictly less than k has cardinality k.
is_ejr_committee_iff_candidate_subsets
A committee W satisfies extended justified representation (EJR) for approval profile A at target size k if and only if W has cardinality k and, for every nonempty subset of candidates T, the number of voters approving all of T who approve fewer than |T| candidates in W, multiplied by k, is strictly less than |T| times the total number of 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

private lemma ejr_chain_iff_level_supporters_card_prefix {m : ℕ} (σ : Equiv.Perm (Fin m)) (k : ℕ)    (hk : k ≤ m) : (Finset.univ.filter fun c => (σ c : ℕ) < k).card = k := by  have hpre : (Finset.univ.filter fun c : Fin m => (σ c : ℕ) < k)      = (Finset.univ.filter fun x : Fin m => (x : ℕ) < k).image σ.symm := by    ext c    simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_image]    constructor    · intro h      exact ⟨σ c, h, by simp⟩    · rintro ⟨x, hx, rfl⟩      simpa using hx  have himg : (Finset.univ : Finset (Fin k)).image (Fin.castLE hk)      = Finset.univ.filter (fun x : Fin m => (x : ℕ) < k) := by    ext x    simp only [Finset.mem_image, Finset.mem_univ, true_and, Finset.mem_filter]    constructor    · rintro ⟨a, rfl⟩      simp    · intro hx      exact ⟨⟨x, hx⟩, Fin.ext rfl⟩  rw [hpre, Finset.card_image_of_injective _ σ.symm.injective, ← himg,    Finset.card_image_of_injective _ (Fin.castLE_injective hk), Finset.card_univ, Fintype.card_fin]/-- The chain target is equivalent to a level-by-level counting condition on supporters of candidate subsets, with all cohesive-group machinery eliminated. -/theorem ejr_chain_iff_level_supporters {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)) ↔      (∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m → ∀ T : Finset (Fin m), T.Nonempty →        (Finset.univ.filter fun i => T ⊆ A i ∧          (A i ∩ Finset.univ.filter fun c => (σ c : ℕ) < k).card < T.card).card * k        < T.card * n) := by  constructor  · rintro ⟨σ, hσ⟩    exact ⟨σ, fun k hk T hT =>      ((is_ejr_committee_iff_candidate_subsets A k _).mp (hσ k hk)).2 T hT⟩  · rintro ⟨σ, hσ⟩    refine ⟨σ, fun k hk => ?_⟩    rw [is_ejr_committee_iff_candidate_subsets]    exact ⟨ejr_chain_iff_level_supporters_card_prefix σ k hk, fun T hT => hσ k hk T hT⟩
See it in the graphDiscuss this resultChallenge it