AFTD Auto-Formalizing Theoretical Domains

ejr_committee_exists

theoremverifiedformalization

For every approval profile with at least one voter and every committee size k ≤ m, some committee of size k satisfies EJR (for instance the PAV committee).

Statement

theorem ejr_committee_exists :
    ∀ (n m : ℕ) (A : Fin n → Finset (Fin m)), 0 < n → ∀ k, k ≤ m →
      ∃ W, is_ejr_committee A k W
Formalizes
Justified Representation in Approval-Based Committee Voting (arXiv:1407.8269), theorem that PAV satisfies EJR; recalled in arXiv:2007.01795; the one-size-at-a-time part of the committee-monotonicity question
Verified
29 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 is established using a greedy cohesive group argument by strong induction on the voter set. For any set of voters S, one selects a cohesive subgroup G with maximum cohesion parameter ℓ, awards it ℓ unanimously approved candidates, and recursively solves the remaining voters S \ G. Applying this construction to the entire electorate yields a candidate set of size at most k satisfying Extended Justified Representation, which is then extended to a committee of size exactly k.

  1. We set up strong induction on the voter set S with respect to strict inclusion.

    The proof of the greedy cohesive auxiliary lemma proceeds by strong induction on the finite set of voters S using `Finset.strongInduction`. In the induction step, we assume the claim holds for all strict subsets t ⊂ S.

    lines 8–10

    uses Finset.strongInduction

      classical
      induction S using Finset.strongInduction with
      | H S ih =>
  2. Every cohesive group has parameter ℓ ≤ m, and we define the finite set P of all valid cohesive pairs (ℓ, G) with G ⊆ S.

    Since candidates are elements of Fin m, the total candidate count is m, so any group unanimously approving ℓ candidates satisfies ℓ ≤ m by `Finset.card_le_univ`. We define P as the set of pairs (ℓ, G) in {1, ..., m} × 𝒫(S) such that G is an ℓ-cohesive group, and verify the membership condition `hmemP` for P.

    lines 11–20

    uses Finset.card_le_univ, Finset.mem_filter, Finset.mem_product, Finset.mem_Icc, Finset.mem_powerset

      have hle_m : ∀ ℓ G, is_ejr_cohesive_group A k ℓ G → ℓ ≤ m := fun ℓ G h =>
        h.2.trans ((Finset.card_le_univ _).trans (by simp))
      let P : Finset (ℕ × Finset (Fin n)) :=
        ((Finset.Icc 1 m) ×ˢ S.powerset).filter fun p => is_ejr_cohesive_group A k p.1 p.2
      have hmemP : ∀ ℓ G, (ℓ, G) ∈ P ↔ (1 ≤ ℓ ∧ G ⊆ S ∧ is_ejr_cohesive_group A k ℓ G) := by
        intro ℓ G
        simp only [P, Finset.mem_filter, Finset.mem_product, Finset.mem_Icc, Finset.mem_powerset]
        constructor
        · rintro ⟨⟨⟨h1, -⟩, h2⟩, h3⟩; exact ⟨h1, h2, h3⟩
        · rintro ⟨h1, h2, h3⟩; exact ⟨⟨⟨h1, hle_m ℓ G h3⟩, h2⟩, h3⟩
  3. Assuming P is non-empty, we choose a pair (ℓ, G) ∈ P maximizing ℓ, and establish that G is non-empty.

    We split on whether P is non-empty. When P is non-empty, we pick a pair (ℓ, G) ∈ P maximizing ℓ. The group G cannot be empty: if G were empty, the cohesion bound ℓ * n ≤ |G| * k would imply ℓ * n ≤ 0, which contradicts ℓ ≥ 1 and n > 0 by linear arithmetic.

    lines 21–30

    uses Finset.nonempty_iff_ne_empty, Finset.card_empty, zero_mul, Nat.mul_pos

      by_cases hP : P.Nonempty
      · obtain ⟨⟨ℓ, G⟩, hpP, hmax⟩ := P.exists_max_image Prod.fst hP
        obtain ⟨hℓ1, hGS, hcoh⟩ := (hmemP ℓ G).1 hpP
        have hGne : G.Nonempty := by
          rw [Finset.nonempty_iff_ne_empty]
          rintro rfl
          have h := hcoh.1
          simp only [Finset.card_empty, zero_mul] at h
          have : 0 < ℓ * n := Nat.mul_pos hℓ1 hn
          omega
  4. Applying the induction hypothesis to S \ G yields W', and choosing ℓ unanimously approved candidates C gives candidate set W' ∪ C for S.

    Since G is non-empty and G ⊆ S, the remainder S \ G is a strict subset of S by `Finset.sdiff_ssubset`. By the induction hypothesis, there is a candidate set W' satisfying the bound and cohesive groups for S \ G. Since G is ℓ-cohesive, there is a set C of ℓ candidates unanimously approved by G (`Finset.exists_subset_card_eq`). We propose W' ∪ C as the witness for S.

    lines 31–33

    uses Finset.sdiff_ssubset, Finset.exists_subset_card_eq

        obtain ⟨W', hW'card, hW'⟩ := ih (S \ G) (Finset.sdiff_ssubset hGS hGne)
        obtain ⟨C, hCsub, hCcard⟩ := Finset.exists_subset_card_eq hcoh.2
        refine ⟨W' ∪ C, ?_, ?_⟩
  5. The candidate set W' ∪ C satisfies the quota bound |W' ∪ C| * n ≤ |S| * k.

    By subadditivity of set size, |W' ∪ C| ≤ |W'| + ℓ. Multiplying by n and using the induction hypothesis |W'| * n ≤ |S \ G| * k together with the cohesion bound ℓ * n ≤ |G| * k, we obtain (|W'| + ℓ) * n ≤ (|S \ G| + |G|) * k. Since |S \ G| + |G| = |S|, this equals |S| * k.

    lines 34–40

    uses Finset.card_union_le, Finset.card_sdiff_add_card_eq_card, Nat.mul_le_mul_right, Nat.add_le_add, Nat.add_mul

        · have h1 : (W' ∪ C).card ≤ W'.card + ℓ := (Finset.card_union_le _ _).trans (by rw [hCcard])
          have h2 : (S \ G).card + G.card = S.card := Finset.card_sdiff_add_card_eq_card hGS
          have hc := hcoh.1
          calc (W' ∪ C).card * n ≤ (W'.card + ℓ) * n := Nat.mul_le_mul_right _ h1
            _ = W'.card * n + ℓ * n := by ring
            _ ≤ (S \ G).card * k + G.card * k := Nat.add_le_add hW'card hc
            _ = S.card * k := by rw [← Nat.add_mul, h2]
  6. Any ℓ'-cohesive group H ⊆ S disjoint from G has a member approving at least ℓ' candidates in W' ∪ C.

    If an ℓ'-cohesive group H ⊆ S is disjoint from G, then H ⊆ S \ G. By the induction hypothesis for W', some voter i ∈ H approves at least ℓ' candidates in W', and hence at least ℓ' candidates in W' ∪ C.

    lines 41–47

    uses Finset.card_le_card, Finset.inter_subset_inter_left, Finset.subset_union_left

        · intro ℓ' hℓ' H hHS hHcoh
          by_cases hHG : Disjoint H G
          · have hHsub : H ⊆ S \ G := fun x hx =>
              Finset.mem_sdiff.2 ⟨hHS hx, Finset.disjoint_left.1 hHG hx⟩
            obtain ⟨i, hi, hle⟩ := hW' ℓ' hℓ' H hHsub hHcoh
            exact ⟨i, hi, hle.trans (Finset.card_le_card
              (Finset.inter_subset_inter_left Finset.subset_union_left))⟩
  7. Any ℓ'-cohesive group H ⊆ S intersecting G has a member approving at least ℓ' candidates in W' ∪ C.

    If H intersects G, take any voter i ∈ H ∩ G. By maximality of ℓ among cohesive groups in P, ℓ' ≤ ℓ. Since i ∈ G and all candidates in C are approved by G, voter i approves every candidate in C, so C ⊆ A(i) ∩ (W' ∪ C). Thus |A(i) ∩ (W' ∪ C)| ≥ |C| = ℓ ≥ ℓ'.

    lines 48–55

    uses Finset.card_le_card, Finset.mem_union_right

          · obtain ⟨i, hiH, hiG⟩ := Finset.not_disjoint_iff.1 hHG
            have hℓ'le : ℓ' ≤ ℓ := hmax (ℓ', H) ((hmemP ℓ' H).2 ⟨hℓ', hHS, hHcoh⟩)
            refine ⟨i, hiH, hℓ'le.trans ?_⟩
            rw [← hCcard]
            apply Finset.card_le_card
            intro c hc
            exact Finset.mem_inter.2 ⟨(Finset.mem_filter.1 (hCsub hc)).2 i hiG,
              Finset.mem_union_right _ hc⟩
  8. When P is empty, the empty candidate set vacuously satisfies the auxiliary lemma.

    If P is empty, W = ∅ satisfies |W| * n = 0 ≤ |S| * k. Any ℓ-cohesive group G ⊆ S with ℓ ≥ 1 would give an element of P, so the condition holds vacuously by contradiction.

    lines 56–58

      · refine ⟨∅, by simp, ?_⟩
        intro ℓ hℓ G hGS hcoh
        exact absurd ⟨(ℓ, G), (hmemP ℓ G).2 ⟨hℓ, hGS, hcoh⟩⟩ hP
  9. Applying the auxiliary lemma to the universal voter set yields a candidate set W of size at most k satisfying EJR.

    Instantiating `ejr_greedy_cohesive_aux` with the universal set S = Finset.univ of all n voters gives a set W with |W| * n ≤ n * k. Because n > 0, this implies |W| ≤ k by `Nat.le_of_mul_le_mul_right`. Every cohesive group in the electorate is satisfied by W.

    lines 63–68

    uses ejr_greedy_cohesive_aux, Finset.univ, Finset.card_univ, Fintype.card_fin, Nat.le_of_mul_le_mul_right, mul_comm

      intro n m A hn k hk
      classical
      obtain ⟨W, hWc, hW⟩ := ejr_greedy_cohesive_aux A k hn Finset.univ
      have hWk : W.card ≤ k := by
        rw [Finset.card_univ, Fintype.card_fin] at hWc
        exact Nat.le_of_mul_le_mul_right (by rw [mul_comm k n]; exact hWc) hn
  10. Extending W to a superset W2 of size exactly k produces the desired EJR committee.

    Since |W| ≤ k ≤ m, `Finset.exists_superset_card_eq` yields a superset W2 ⊇ W of cardinality exactly k. Any voter approving at least ℓ candidates in W also approves at least ℓ candidates in W2, completing the proof that W2 is an EJR committee.

    lines 69–72

    uses Finset.exists_superset_card_eq, Finset.subset_univ, Finset.card_le_card, Finset.inter_subset_inter_left

      obtain ⟨W2, hsub, hcard⟩ := Finset.exists_superset_card_eq hWk (by simpa using hk)
      refine ⟨W2, hcard, fun ℓ hℓ G hG => ?_⟩
      obtain ⟨i, hi, hle⟩ := hW ℓ hℓ G (Finset.subset_univ _) hG
      exact ⟨i, hi, hle.trans (Finset.card_le_card (Finset.inter_subset_inter_left hsub))⟩
Finset.strongInduction
Strong induction on finite sets: to prove a statement for all finite sets, it suffices to prove it for any set assuming it holds for all its proper subsets.
Finset.card_le_univ
The cardinality of any subset of a finite type is at most the total number of elements in that type.
Finset.mem_filter
An element belongs to a filtered set if and only if it belongs to the original set and satisfies the predicate.
Finset.mem_product
An ordered pair belongs to the Cartesian product of two sets if and only if its first component is in the first set and its second component is in the second set.
Finset.mem_Icc
An element belongs to the closed interval [a, b] if and only if it is between a and b inclusive.
Finset.mem_powerset
A set belongs to the powerset of another set if and only if it is a subset of that set.
Finset.nonempty_iff_ne_empty
A finite set is non-empty if and only if it is not equal to the empty set.
Finset.card_empty
The empty set has cardinality 0.
zero_mul
Zero multiplied by any element is zero.
Nat.mul_pos
The product of two strictly positive natural numbers is strictly positive.
Finset.sdiff_ssubset
Removing a non-empty subset from a set leaves a strictly smaller subset.
Finset.exists_subset_card_eq
Any finite set has a subset of size n whenever n is at most the cardinality of the set.
Finset.card_union_le
The cardinality of the union of two finite sets is at most the sum of their cardinalities.
Finset.card_sdiff_add_card_eq_card
For a subset s ⊆ t of finite sets, the size of t \ s plus the size of s equals the size of t.
Nat.mul_le_mul_right
Multiplying both sides of an inequality of natural numbers on the right by a constant preserves the inequality.
Nat.add_le_add
Adding two inequalities of natural numbers preserves the inequality.
Nat.add_mul
Distributivity of multiplication over addition: (n + m) * k = n * k + m * k.
Finset.card_le_card
A subset has cardinality less than or equal to that of the ambient finite set.
Finset.inter_subset_inter_left
Intersection with a fixed set preserves inclusion: if t ⊆ u, then s ∩ t ⊆ s ∩ u.
Finset.subset_union_left
Every set is a subset of its union with another set.
Finset.mem_union_right
An element of t belongs to s ∪ t.
ejr_greedy_cohesive_aux
For every voter subset S, there exists a candidate set W with |W| * n ≤ |S| * k such that every ℓ-cohesive group in S has a member approving at least ℓ candidates in W.
Finset.univ
The set of all elements of a finite type.
Finset.card_univ
The cardinality of the universal set of a finite type equals the number of elements in the type.
Fintype.card_fin
The cardinality of Fin n is n.
Nat.le_of_mul_le_mul_right
If a * c ≤ b * c and c > 0 for natural numbers, then a ≤ b.
mul_comm
Multiplication of natural numbers is commutative: a * b = b * a.
Finset.exists_superset_card_eq
A finite subset can be extended to a superset of any size between its cardinality and the total number of elements.
Finset.subset_univ
Every subset of a finite type is contained in the universal set.

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

/-- The greedy cohesive argument: for every set `S` of voters there is a set `W` of at most`|S| k / n` candidates such that every `ℓ`-cohesive group inside `S` has a member approving atleast `ℓ` members of `W`. (Take a cohesive group `G ⊆ S` with the largest `ℓ`, give it `ℓ`commonly approved candidates and recurse on `S \ G`.) -/theorem ejr_greedy_cohesive_aux {n m : ℕ} (A : Fin n → Finset (Fin m)) (k : ℕ) (hn : 0 < n)    (S : Finset (Fin n)) : ∃ W : Finset (Fin m), W.card * n ≤ S.card * k ∧      ∀ ℓ, 1 ≤ ℓ → ∀ G ⊆ S, is_ejr_cohesive_group A k ℓ G → ∃ i ∈ G, ℓ ≤ (A i ∩ W).card := by  classical  induction S using Finset.strongInduction with  | H S ih =>  have hle_m : ∀ ℓ G, is_ejr_cohesive_group A k ℓ G → ℓ ≤ m := fun ℓ G h =>    h.2.trans ((Finset.card_le_univ _).trans (by simp))  let P : Finset (ℕ × Finset (Fin n)) :=    ((Finset.Icc 1 m) ×ˢ S.powerset).filter fun p => is_ejr_cohesive_group A k p.1 p.2  have hmemP : ∀ ℓ G, (ℓ, G) ∈ P ↔ (1 ≤ ℓ ∧ G ⊆ S ∧ is_ejr_cohesive_group A k ℓ G) := by    intro ℓ G    simp only [P, Finset.mem_filter, Finset.mem_product, Finset.mem_Icc, Finset.mem_powerset]    constructor    · rintro ⟨⟨⟨h1, -⟩, h2⟩, h3⟩; exact ⟨h1, h2, h3⟩    · rintro ⟨h1, h2, h3⟩; exact ⟨⟨⟨h1, hle_m ℓ G h3⟩, h2⟩, h3⟩  by_cases hP : P.Nonempty  · obtain ⟨⟨ℓ, G⟩, hpP, hmax⟩ := P.exists_max_image Prod.fst hP    obtain ⟨hℓ1, hGS, hcoh⟩ := (hmemP ℓ G).1 hpP    have hGne : G.Nonempty := by      rw [Finset.nonempty_iff_ne_empty]      rintro rfl      have h := hcoh.1      simp only [Finset.card_empty, zero_mul] at h      have : 0 < ℓ * n := Nat.mul_pos hℓ1 hn      omega    obtain ⟨W', hW'card, hW'⟩ := ih (S \ G) (Finset.sdiff_ssubset hGS hGne)    obtain ⟨C, hCsub, hCcard⟩ := Finset.exists_subset_card_eq hcoh.2    refine ⟨W' ∪ C, ?_, ?_⟩    · have h1 : (W' ∪ C).card ≤ W'.card + ℓ := (Finset.card_union_le _ _).trans (by rw [hCcard])      have h2 : (S \ G).card + G.card = S.card := Finset.card_sdiff_add_card_eq_card hGS      have hc := hcoh.1      calc (W' ∪ C).card * n ≤ (W'.card + ℓ) * n := Nat.mul_le_mul_right _ h1        _ = W'.card * n + ℓ * n := by ring        _ ≤ (S \ G).card * k + G.card * k := Nat.add_le_add hW'card hc        _ = S.card * k := by rw [← Nat.add_mul, h2]    · intro ℓ' hℓ' H hHS hHcoh      by_cases hHG : Disjoint H G      · have hHsub : H ⊆ S \ G := fun x hx =>          Finset.mem_sdiff.2 ⟨hHS hx, Finset.disjoint_left.1 hHG hx⟩        obtain ⟨i, hi, hle⟩ := hW' ℓ' hℓ' H hHsub hHcoh        exact ⟨i, hi, hle.trans (Finset.card_le_card          (Finset.inter_subset_inter_left Finset.subset_union_left))⟩      · obtain ⟨i, hiH, hiG⟩ := Finset.not_disjoint_iff.1 hHG        have hℓ'le : ℓ' ≤ ℓ := hmax (ℓ', H) ((hmemP ℓ' H).2 ⟨hℓ', hHS, hHcoh⟩)        refine ⟨i, hiH, hℓ'le.trans ?_⟩        rw [← hCcard]        apply Finset.card_le_card        intro c hc        exact Finset.mem_inter.2 ⟨(Finset.mem_filter.1 (hCsub hc)).2 i hiG,          Finset.mem_union_right _ hc⟩  · refine ⟨∅, by simp, ?_⟩    intro ℓ hℓ G hGS hcoh    exact absurd ⟨(ℓ, G), (hmemP ℓ G).2 ⟨hℓ, hGS, hcoh⟩⟩ hPtheorem ejr_committee_exists :    ∀ (n m : ℕ) (A : Fin n → Finset (Fin m)), 0 < n → ∀ k, k ≤ m →      ∃ W, is_ejr_committee A k W := by  intro n m A hn k hk  classical  obtain ⟨W, hWc, hW⟩ := ejr_greedy_cohesive_aux A k hn Finset.univ  have hWk : W.card ≤ k := by    rw [Finset.card_univ, Fintype.card_fin] at hWc    exact Nat.le_of_mul_le_mul_right (by rw [mul_comm k n]; exact hWc) hn  obtain ⟨W2, hsub, hcard⟩ := Finset.exists_superset_card_eq hWk (by simpa using hk)  refine ⟨W2, hcard, fun ℓ hℓ G hG => ?_⟩  obtain ⟨i, hi, hle⟩ := hW ℓ hℓ G (Finset.subset_univ _) hG  exact ⟨i, hi, hle.trans (Finset.card_le_card (Finset.inter_subset_inter_left hsub))⟩
See it in the graphDiscuss this resultChallenge it