AFTD Auto-Formalizing Theoretical Domains

ejr_good_of_low_support_candidate

theoremverified

If candidate c is approved by fewer than n/m voters (m times its supporter count is below n), then for any k-committee P with c not in P, EJR holds as soon as it holds for all demand-sets T not containing c.

Statement

theorem ejr_good_of_low_support_candidate (n m : ℕ) (A : Fin n → Finset (Fin m)) (hn : 0 < n)
    (c : Fin m) (hc : m * (Finset.univ.filter fun i => c ∈ A i).card < n)
    (P : Finset (Fin m)) (hp : c ∉ P) (k : ℕ) (hkP : P.card = k)
    (h : ∀ T : Finset (Fin m), T.Nonempty → c ∉ T →
      (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ P).card < T.card).card * k < T.card * n) :
    is_ejr_committee A k P
Source
step towards ejr_committee_monotone_chain_exists
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • is_ejr_committee_iff_candidate_subsetsEJR is equivalent to the correct committee size together with the underrepresented-supporter inequality for every nonempty candidate…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • 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 1
  • ejr_chain_of_low_support_candidateIf candidate c is approved by fewer than n/m voters and the profile with c deleted (transported along e) admits an EJR chain, then so does…

The proof, explained

The theorem uses the demand-set characterization of Extended Justified Representation (EJR), where every non-empty candidate set T must have fewer than |T| * n / k under-represented supporters in committee P. By hypothesis, this condition is already known to hold for all candidate sets T that do not contain c. For any demand-set T that does contain c, any voter approving T must approve c, so the number of such voters is bounded by the total support of c. Since c has low support (m times its supporter count is strictly less than n), committee size satisfies k ≤ m, and |T| ≥ 1, this demand-set constraint is satisfied automatically.

  1. To show that P is an EJR committee of size k, it suffices to verify the demand-set condition for every non-empty candidate subset T.

    By the equivalence theorem `is_ejr_committee_iff_candidate_subsets`, P is an EJR committee if and only if |P| = k (which is given by hypothesis `hkP`) and every non-empty subset T of candidates satisfies the strict inequality |{i | T ⊆ A i ∧ |A i ∩ P| < |T|}| * k < |T| * n. We fix an arbitrary non-empty candidate subset T.

    lines 8–9

    uses is_ejr_committee_iff_candidate_subsets

      rw [is_ejr_committee_iff_candidate_subsets]
      refine ⟨hkP, fun T hT => ?_⟩
  2. When c ∈ T, the number of voters approving T with fewer than |T| committee members is at most the total number of voters approving candidate c.

    We split into cases on whether candidate c belongs to T. In the positive case c ∈ T, every voter i who approves all of T must approve c, because c ∈ T ⊆ A i. Using `Finset.mem_filter`, this containment implies that the set of voters approving T with fewer than |T| representatives in P is a subset of the voters approving c. By `Finset.card_le_card`, its cardinality is therefore bounded by the number of voters approving c.

    lines 10–18

    uses Finset.mem_filter, Finset.card_le_card

      by_cases hcT : c ∈ T
      · have hsub : (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ P).card < T.card) ⊆
            (Finset.univ.filter fun i => c ∈ A i) := by
          intro i hi
          rw [Finset.mem_filter] at hi ⊢
          refine ⟨hi.1, hi.2.1 hcT⟩
        have hcard : (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ P).card < T.card).card ≤
            (Finset.univ.filter fun i => c ∈ A i).card :=
          Finset.card_le_card hsub
  3. The committee size satisfies k ≤ m, and multiplying by the previous bound gives |{i | T ⊆ A i ∧ |A i ∩ P| < |T|}| * k ≤ |{i | c ∈ A i}| * m.

    Since P is a committee of candidates from the m-element universe Fin m, its size k = |P| cannot exceed m by `Finset.card_le_univ`. Multiplying this inequality with the voter-count bound from the previous step via `Nat.mul_le_mul` yields the scaled inequality.

    lines 19–25

    uses Finset.card_le_univ, Nat.mul_le_mul

        have hk_le_m : k ≤ m := by
          rw [← hkP]
          have : P.card ≤ (Finset.univ : Finset (Fin m)).card := Finset.card_le_univ P
          simpa using this
        have h1 : (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ P).card < T.card).card * k ≤
            (Finset.univ.filter fun i => c ∈ A i).card * m :=
          Nat.mul_le_mul hcard hk_le_m
  4. When c ∈ T, the demand-set inequality |{i | T ⊆ A i ∧ |A i ∩ P| < |T|}| * k < |T| * n holds.

    By the low-support hypothesis `hc`, candidate c satisfies m * |{i | c ∈ A i}| < n, which by commutativity of multiplication (`mul_comm`) becomes |{i | c ∈ A i}| * m < n. Since T is non-empty, |T| ≥ 1, so n = 1 * n ≤ |T| * n using `one_mul` and `Nat.mul_le_mul_right`. Combining |{i | T ⊆ A i ∧ |A i ∩ P| < |T|}| * k ≤ |{i | c ∈ A i}| * m < n ≤ |T| * n using linear arithmetic (`linarith`) completes the argument for this case.

    lines 26–33

    uses mul_comm, one_mul, Nat.mul_le_mul_right

        have h2 : (Finset.univ.filter fun i => c ∈ A i).card * m < n := by
          rw [mul_comm]
          exact hc
        have h3 : n ≤ T.card * n := by
          have : 1 ≤ T.card := hT.card_pos
          calc n = 1 * n := by rw [one_mul]
          _ ≤ T.card * n := Nat.mul_le_mul_right n this
        linarith
  5. When c ∉ T, the demand-set inequality holds directly from the hypothesis.

    In the remaining case where c ∉ T, the required inequality is precisely the assumption `h` applied to T, the non-emptiness proof `hT`, and the assumption `hcT` that c ∉ T.

    line 34

      · exact h T hT hcT
is_ejr_committee_iff_candidate_subsets
A committee W satisfies Extended Justified Representation (EJR) for committee size k if and only if |W| = k and, for every non-empty candidate subset T, the number of voters who approve all of T but have fewer than |T| committee members in their approval set is strictly less than |T| * n / k (expressed as |{i | T ⊆ A i ∧ |A i ∩ W| < |T|}| * k < |T| * n).
Finset.mem_filter
An element a belongs to a filtered finset Finset.filter p s if and only if a ∈ s and p a holds.
Finset.card_le_card
If s is a subset of t for finite sets s and t, then |s| ≤ |t|.
Finset.card_le_univ
The cardinality of any subset of a finite type α is at most the total number of elements in α (Fintype.card α).
Nat.mul_le_mul
If n₁ ≤ n₂ and m₁ ≤ m₂, then n₁ * m₁ ≤ n₂ * m₂ for natural numbers.
mul_comm
Multiplication is commutative: a * b = b * a.
one_mul
Multiplying by 1 on the left is the identity: 1 * a = a.
Nat.mul_le_mul_right
If n ≤ m, then n * k ≤ m * k for natural numbers.

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

/-- A low-support candidate imposes no EJR constraint: subsets T containing it are automatically satisfied. -/theorem ejr_good_of_low_support_candidate (n m : ℕ) (A : Fin n → Finset (Fin m)) (hn : 0 < n)    (c : Fin m) (hc : m * (Finset.univ.filter fun i => c ∈ A i).card < n)    (P : Finset (Fin m)) (hp : c ∉ P) (k : ℕ) (hkP : P.card = k)    (h : ∀ T : Finset (Fin m), T.Nonempty → c ∉ T →      (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ P).card < T.card).card * k < T.card * n) :    is_ejr_committee A k P := by  rw [is_ejr_committee_iff_candidate_subsets]  refine ⟨hkP, fun T hT => ?_⟩  by_cases hcT : c ∈ T  · have hsub : (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ P).card < T.card) ⊆        (Finset.univ.filter fun i => c ∈ A i) := by      intro i hi      rw [Finset.mem_filter] at hi ⊢      refine ⟨hi.1, hi.2.1 hcT⟩    have hcard : (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ P).card < T.card).card ≤        (Finset.univ.filter fun i => c ∈ A i).card :=      Finset.card_le_card hsub    have hk_le_m : k ≤ m := by      rw [← hkP]      have : P.card ≤ (Finset.univ : Finset (Fin m)).card := Finset.card_le_univ P      simpa using this    have h1 : (Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ P).card < T.card).card * k ≤        (Finset.univ.filter fun i => c ∈ A i).card * m :=      Nat.mul_le_mul hcard hk_le_m    have h2 : (Finset.univ.filter fun i => c ∈ A i).card * m < n := by      rw [mul_comm]      exact hc    have h3 : n ≤ T.card * n := by      have : 1 ≤ T.card := hT.card_pos      calc n = 1 * n := by rw [one_mul]      _ ≤ T.card * n := Nat.mul_le_mul_right n this    linarith  · exact h T hT hcT
See it in the graphDiscuss this resultChallenge it