AFTD Auto-Formalizing Theoretical Domains

is_ejr_committee_iff_undersatisfied_supporters

theoremverified

A committee W of size k satisfies EJR exactly when, for each positive ell and each ell-element candidate set T, fewer than ell*n/k voters both approve every member of T and approve fewer than ell members of W, stated without division as underrepresented-supporter count times k < ell*n.

Statement

theorem is_ejr_committee_iff_undersatisfied_supporters {n m : ℕ}
    (A : Fin n → Finset (Fin m)) (k : ℕ) (W : Finset (Fin m)) :
    is_ejr_committee A k W ↔ W.card = k ∧
      ∀ ℓ, 1 ≤ ℓ → ∀ T : Finset (Fin m), T.card = ℓ →
        (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < ℓ).card * k < ℓ * n
Source
Helper for ejr_committee_monotone_chain_exists (OP-22; arXiv:2007.01795, open problems Q2): finite witness criterion used in exact profile synthesis and committee-subset dynamic programming.
Verified
24 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| ≥ ℓ.
  • 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 1

The proof, explained

The theorem establishes that a committee W satisfies Extended Justified Representation (EJR) if and only if |W| = k and every ℓ-candidate set T has fewer than ℓ*n/k undersatisfied supporters (voters approving T who receive fewer than ℓ members of W). In the forward direction, if T had at least ℓ*n/k undersatisfied supporters, those voters would form an ℓ-cohesive group in which nobody receives ℓ committee members, contradicting EJR. In the backward direction, if an ℓ-cohesive group G were completely undersatisfied, choosing an ℓ-element subset T of their common approvals would make G a subset of the undersatisfied supporters of T, violating the assumed counting bound.

  1. The equivalence decomposes into two directions: showing that an EJR committee satisfies the undersatisfied supporter bound, and conversely that the bound implies the EJR property.

    We enable classical logic and split the `↔` statement into its forward (`→`) and backward (`←`) directions.

    lines 6–7

      classical
      constructor
  2. In the forward direction, |W| = k, and it suffices to show that for every ℓ ≥ 1 and every candidate set T of size ℓ, the number of undersatisfied supporters of T satisfies the strict upper bound.

    Assuming that W is an EJR committee, its size is k by definition. We then fix ℓ ≥ 1 and an arbitrary set T of ℓ candidates, aiming to establish the cardinality bound.

    lines 8–10

      · intro h
        refine ⟨h.1, ?_⟩
        intro ℓ hℓ T hT
  3. Assuming for contradiction that the bound fails for T, the set G of voters who approve T and have |A(i) ∩ W| < ℓ satisfies ℓ * n ≤ |G| * k.

    Suppose for contradiction that the strict inequality fails. Let G be the set of voters i who approve all of T and approve fewer than ℓ members of W. By Nat.le_of_not_gt, the negation of the strict inequality gives ℓ * n ≤ |G| * k.

    lines 11–13

    uses Nat.le_of_not_gt

        by_contra hbad
        let G := Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < ℓ
        have hsize : ℓ * n ≤ G.card * k := Nat.le_of_not_gt hbad
  4. The group G is an ℓ-cohesive group.

    Every voter in G approves every candidate in T by definition of G, so T is a subset of the candidates unanimously approved by G. Since |T| = ℓ, monotonicity of cardinality (Finset.card_le_card) implies that the set of unanimously approved candidates has size at least ℓ. Combined with ℓ * n ≤ |G| * k, this means G meets both requirements of an ℓ-cohesive group.

    lines 14–20

    uses Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_filter.mp, Finset.card_le_card

        have hsub : T ⊆ Finset.univ.filter fun c => ∀ i ∈ G, c ∈ A i := by
          intro c hc
          simp only [Finset.mem_filter, Finset.mem_univ, true_and]
          intro i hi
          exact (Finset.mem_filter.mp hi).2.1 hc
        have hcoh : is_ejr_cohesive_group A k ℓ G :=
          ⟨hsize, by rw [← hT]; exact Finset.card_le_card hsub⟩
  5. Applying the EJR property to G yields a contradiction, completing the forward direction.

    Because W satisfies EJR and G is an ℓ-cohesive group, there must exist some voter i ∈ G who approves at least ℓ members of W, so |A(i) ∩ W| ≥ ℓ. However, every voter in G approves strictly fewer than ℓ members of W by definition of G. These two inequalities contradict each other.

    lines 21–23

    uses Finset.mem_filter.mp

        obtain ⟨i, hi, hsat⟩ := h.2 ℓ hℓ G hcoh
        have hlt := (Finset.mem_filter.mp hi).2.2
        omega
  6. In the backward direction, assuming |W| = k and the bound on undersatisfied supporters, to prove W is an EJR committee it suffices to show that every ℓ-cohesive group G contains a voter who approves at least ℓ committee members.

    We assume |W| = k and that the bound holds for all ℓ and sets T of size ℓ. For an arbitrary ℓ ≥ 1 and ℓ-cohesive group G, we suppose for contradiction that no voter in G approves ℓ or more committee members; that is, every i ∈ G satisfies |A(i) ∩ W| < ℓ.

    lines 24–28

      · rintro ⟨hcard, h⟩
        refine ⟨hcard, ?_⟩
        intro ℓ hℓ G hcoh
        by_contra hnone
        push Not at hnone
  7. There exists an ℓ-element candidate set T such that G ⊆ H, where H is the set of undersatisfied supporters of T.

    Since G is ℓ-cohesive, the set of candidates approved by all voters in G has size at least ℓ. By Finset.exists_subset_card_eq, we can choose an exact subset T of ℓ such candidates. Letting H be the set of voters who approve T and have |A(i) ∩ W| < ℓ, every voter in G belongs to H because they approve all candidates in T and, by the contradiction hypothesis, have |A(i) ∩ W| < ℓ.

    lines 29–37

    uses Finset.exists_subset_card_eq, Finset.mem_filter.mpr, Finset.mem_univ, Finset.mem_filter.mp

        obtain ⟨T, hTsub, hTcard⟩ := Finset.exists_subset_card_eq hcoh.2
        let H := Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < ℓ
        have hGH : G ⊆ H := by
          intro i hi
          apply Finset.mem_filter.mpr
          refine ⟨Finset.mem_univ _, ?_, ?_⟩
          · intro c hc
            exact (Finset.mem_filter.mp (hTsub hc)).2 i hi
          · exact hnone i hi
  8. The inclusion G ⊆ H leads to a numerical contradiction, completing the proof.

    From G ⊆ H, we have |G| * k ≤ |H| * k by Nat.mul_le_mul_right and Finset.card_le_card. Applying the hypothesis to the ℓ-element set T gives |H| * k < ℓ * n. Meanwhile, cohesiveness of G gives ℓ * n ≤ |G| * k. Combining these yields ℓ * n ≤ |G| * k ≤ |H| * k < ℓ * n, an impossible chain of inequalities.

    lines 38–42

    uses Nat.mul_le_mul_right, Finset.card_le_card

        have hle := Nat.mul_le_mul_right k (Finset.card_le_card hGH)
        have hlt := h ℓ hℓ T hTcard
        have hsize := hcoh.1
        change H.card * k < ℓ * n at hlt
        omega
Nat.le_of_not_gt
For natural numbers, if b is not strictly greater than a, then b ≤ a.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the base set and satisfies the filtering predicate.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
true_and
The conjunction True ∧ p simplifies to p.
Finset.mem_filter.mp
Membership in a filtered finset implies membership in the base set and satisfaction of the predicate.
Finset.card_le_card
If s ⊆ t for finite sets s and t, then |s| ≤ |t|.
Finset.exists_subset_card_eq
If a finite set has cardinality at least n, it contains a subset of cardinality exactly n.
Finset.mem_filter.mpr
If an element belongs to the base set and satisfies the predicate, it belongs to the filtered finset.
Nat.mul_le_mul_right
Multiplying both sides of a natural number inequality n ≤ m on the right by k yields n * k ≤ m * k.

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 is_ejr_committee_iff_undersatisfied_supporters {n m : ℕ}    (A : Fin n → Finset (Fin m)) (k : ℕ) (W : Finset (Fin m)) :    is_ejr_committee A k W ↔ W.card = k ∧      ∀ ℓ, 1 ≤ ℓ → ∀ T : Finset (Fin m), T.card = ℓ →        (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < ℓ).card * k < ℓ * n := by  classical  constructor  · intro h    refine ⟨h.1, ?_⟩    intro ℓ hℓ T hT    by_contra hbad    let G := Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < ℓ    have hsize : ℓ * n ≤ G.card * k := Nat.le_of_not_gt hbad    have hsub : T ⊆ Finset.univ.filter fun c => ∀ i ∈ G, c ∈ A i := by      intro c hc      simp only [Finset.mem_filter, Finset.mem_univ, true_and]      intro i hi      exact (Finset.mem_filter.mp hi).2.1 hc    have hcoh : is_ejr_cohesive_group A k ℓ G :=      ⟨hsize, by rw [← hT]; exact Finset.card_le_card hsub⟩    obtain ⟨i, hi, hsat⟩ := h.2 ℓ hℓ G hcoh    have hlt := (Finset.mem_filter.mp hi).2.2    omega  · rintro ⟨hcard, h⟩    refine ⟨hcard, ?_⟩    intro ℓ hℓ G hcoh    by_contra hnone    push Not at hnone    obtain ⟨T, hTsub, hTcard⟩ := Finset.exists_subset_card_eq hcoh.2    let H := Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < ℓ    have hGH : G ⊆ H := by      intro i hi      apply Finset.mem_filter.mpr      refine ⟨Finset.mem_univ _, ?_, ?_⟩      · intro c hc        exact (Finset.mem_filter.mp (hTsub hc)).2 i hi      · exact hnone i hi    have hle := Nat.mul_le_mul_right k (Finset.card_le_card hGH)    have hlt := h ℓ hℓ T hTcard    have hsize := hcoh.1    change H.card * k < ℓ * n at hlt    omega
See it in the graphDiscuss this resultChallenge it