AFTD Auto-Formalizing Theoretical Domains

ejr_committee_univ

theoremverified

For every approval profile with at least one voter, the committee consisting of all m candidates satisfies EJR at committee size m.

Statement

theorem ejr_committee_univ {n m : ℕ} (A : Fin n → Finset (Fin m)) (hn : 0 < n) :
    is_ejr_committee A m Finset.univ
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

The proof, explained

The proof uses the equivalent candidate-subset characterization of Extended Justified Representation (EJR), which requires that the committee has size m and that every non-empty candidate set T satisfies a representation inequality. The size condition holds immediately because the universal set on m candidates has cardinality m. For the representation inequality, because the committee contains all m candidates, any voter approving all candidates in T already has at least |T| approved candidates in the committee, so no voter qualifies and the set of dissatisfied voters is empty. The left-hand side therefore evaluates to zero, which is strictly less than |T| · n because both T and the electorate are non-empty.

  1. The theorem reduces to showing that the full committee has size m and that every non-empty candidate subset satisfies the candidate-subset representation inequality.

    By is_ejr_committee_iff_candidate_subsets, satisfying EJR at committee size m is equivalent to having cardinality m and satisfying, for every non-empty candidate subset T, that the number of voters approving all of T with fewer than |T| approved committee candidates, multiplied by m, is strictly less than |T| · n. The goal is split into these two conjuncts.

    lines 4–5

    uses is_ejr_committee_iff_candidate_subsets

      rw [is_ejr_committee_iff_candidate_subsets]
      constructor
  2. The full committee has size m. automation

    The committee consists of Finset.univ for candidates Fin m, whose cardinality is m by definition; the simplifier evaluates this directly.

    line 6

      · simp
  3. Fix an arbitrary non-empty candidate subset T.

    We introduce the candidate set T along with the hypothesis hT that T is non-empty.

    line 7

      · intro T hT
  4. No voter can approve all of T while approving strictly fewer than |T| candidates in the full committee; hence the set of such voters is empty.

    By Finset.filter_eq_empty_iff.mpr, it suffices to show no voter i satisfies both conditions. Because the committee is Finset.univ, voter i's approved committee candidates A(i) ∩ Finset.univ simplify to A(i) by Finset.inter_univ. If voter i approves all of T (T ⊆ A(i)), then |T| ≤ |A(i)| by Finset.card_le_card. This contradicts the condition |A(i)| < |T| via not_le.mpr.

    lines 8–14

    uses Finset.filter_eq_empty_iff.mpr, Finset.inter_univ, Finset.card_le_card, not_le.mpr

        have hfilter :
            (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ Finset.univ).card < T.card) = ∅ := by
          apply Finset.filter_eq_empty_iff.mpr
          intro i _
          rw [Finset.inter_univ]
          rintro ⟨hsub, hlt⟩
          exact absurd (Finset.card_le_card hsub) (not_le.mpr hlt)
  5. The candidate-subset inequality holds for T.

    Replacing the filtered voter set with ∅, its cardinality is 0 by Finset.card_empty, so the left-hand side reduces to 0 · m = 0 by Nat.zero_mul. On the right-hand side, |T| > 0 by Finset.card_pos.mpr because T is non-empty, and n > 0 by hypothesis hn, so their product |T| · n is strictly positive by Nat.mul_pos, completing the inequality 0 < |T| · n.

    lines 15–17

    uses Finset.card_empty, Nat.zero_mul, Nat.mul_pos, Finset.card_pos.mpr

        rw [hfilter]
        simp only [Finset.card_empty, Nat.zero_mul]
        exact Nat.mul_pos (Finset.card_pos.mpr hT) hn
is_ejr_committee_iff_candidate_subsets
A committee W of size k satisfies EJR if and only if |W| = k and, for every non-empty set of candidates T, the number of voters who approve all of T but have fewer than |T| committee members in their approval set, multiplied by k, is strictly less than |T| · n.
Finset.filter_eq_empty_iff.mpr
A filtered finite set is empty if no element of the ambient set satisfies the filtering condition.
Finset.inter_univ
The intersection of any finite set with the universal set of its type is the set itself.
Finset.card_le_card
If s ⊆ t for finite sets s and t, then |s| ≤ |t|.
not_le.mpr
If b < a, then ¬(a ≤ b).
Finset.card_empty
The empty set has cardinality 0.
Nat.zero_mul
0 · n = 0 for any natural number n.
Nat.mul_pos
The product of two strictly positive natural numbers is strictly positive.
Finset.card_pos.mpr
A finite set has strictly positive cardinality if and only if it is non-empty.

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

/-- For a nonempty electorate the full committee satisfies EJR at committee size m. -/theorem ejr_committee_univ {n m : ℕ} (A : Fin n → Finset (Fin m)) (hn : 0 < n) :    is_ejr_committee A m Finset.univ := by  rw [is_ejr_committee_iff_candidate_subsets]  constructor  · simp  · intro T hT    have hfilter :        (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ Finset.univ).card < T.card) = ∅ := by      apply Finset.filter_eq_empty_iff.mpr      intro i _      rw [Finset.inter_univ]      rintro ⟨hsub, hlt⟩      exact absurd (Finset.card_le_card hsub) (not_le.mpr hlt)    rw [hfilter]    simp only [Finset.card_empty, Nat.zero_mul]    exact Nat.mul_pos (Finset.card_pos.mpr hT) hn
See it in the graphDiscuss this resultChallenge it