AFTD Auto-Formalizing Theoretical Domains

ejr_support_density_bound_iff_groups

theoremverified

The finite supporter bound is equivalent to the corresponding bound on every commonly approving group whose members all have utility below a positive demand.

Statement

theorem ejr_support_density_bound_iff_groups {n m : ℕ}
    (A : Fin n → Finset (Fin m)) (q : ℕ) (W : Finset (Fin m)) :
    ejr_support_density_bound A q W ↔
      ∀ ℓ, 1 ≤ ℓ → ∀ G : Finset (Fin n),
        ℓ ≤ (Finset.univ.filter fun c => ∀ i ∈ G, c ∈ A i).card →
        (∀ i ∈ G, (A i ∩ W).card < ℓ) → G.card * q ≤ ℓ * n
Source
Supporting work for OP-22, arXiv:2007.01795, Q2, and the proposed max-group-density invariant in memory attempt 4342. These helpers neither settle full-chain existence nor refute the actual greedy rule. No research advance is claimed.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • ejr_support_density_boundThe finite supporter-density bound: for every candidate subset T, its undersatisfied supporter count times q is at most |T| times the…

The proof, explained

The theorem establishes that the supporter density bound over all candidate sets T is equivalent to the corresponding density bound over cohesive voter groups demanding ℓ ≥ 1 candidates. In the forward direction, given a group G commonly approving at least ℓ candidates, selecting an ℓ-element subset T of these common approvals embeds G into the voters supporting T, so the density bound on T implies the bound on G. In the reverse direction, for any nonempty candidate set T, taking G to be the group of all voters who approve T and have utility below |T| allows one to apply the group bound with ℓ = |T|; the empty candidate set case holds vacuously since utility cannot be negative.

  1. The equivalence decomposes into two implications: the candidate-set density bound implies the voter-group bound, and conversely.

    Enable classical logic and split the biconditional into forward and backward implications.

    lines 7–8

      classical
      constructor
  2. Given a group G commonly approving at least ℓ candidates with utility below ℓ, we obtain a subset T of ℓ jointly approved candidates and define the group H of all voters supporting T.

    Assume the supporter density bound h, a positive demand ℓ ≥ 1, and a voter group G whose common approvals number at least ℓ and whose members each have utility < ℓ from the committee W. By Finset.exists_subset_card_eq, there exists an ℓ-element subset T of candidates approved by all of G. We then define H to be the set of all voters who approve every candidate in T and have utility < ℓ.

    lines 9–11

    uses Finset.exists_subset_card_eq

      · intro h ℓ hℓ G hcommon hunsat
        obtain ⟨T, hTsub, hTcard⟩ := Finset.exists_subset_card_eq hcommon
        let H := Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < ℓ
  3. The original group G is a subset of H.

    Take any voter i ∈ G. Voter i has utility < ℓ by assumption on G, and because every candidate c ∈ T is jointly approved by G, voter i approves every candidate in T. Hence i satisfies the defining condition of H.

    lines 12–17

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

        have hGH : G ⊆ H := by
          intro i hi
          apply Finset.mem_filter.mpr
          refine ⟨Finset.mem_univ _, ?_, hunsat i hi⟩
          intro c hc
          exact (Finset.mem_filter.mp (hTsub hc)).2 i hi
  4. The group density bound |G| * q ≤ ℓ * n holds.

    Since G ⊆ H, we have |G| * q ≤ |H| * q. Evaluating the supporter density bound hypothesis h at candidate set T (where |T| = ℓ) gives |H| * q ≤ ℓ * n. Composing these inequalities gives |G| * q ≤ ℓ * n.

    lines 18–21

    uses Nat.mul_le_mul_right, Finset.card_le_card

        have hle := Nat.mul_le_mul_right q (Finset.card_le_card hGH)
        have hb := h T
        rw [hTcard] at hb
        exact hle.trans hb
  5. To prove the supporter density bound for an arbitrary candidate set T, it suffices to consider whether T is nonempty, in which case we define G as the set of voters supporting T with low utility.

    Assume the voter-group bound holds for all ℓ ≥ 1 and all groups G. Given an arbitrary candidate set T, split into cases on whether T is nonempty. If T is nonempty, define G to be the set of all voters who approve all of T and have utility < |T| from W.

    lines 22–24

      · intro h T
        by_cases hT : T.Nonempty
        · let G := Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < T.card
  6. Every candidate in T is approved by all voters in G.

    For any candidate c ∈ T and voter i ∈ G, by definition of G the voter approves the entire set T, so c ∈ A(i). Thus T is a subset of the candidates jointly approved by all voters in G.

    lines 25–29

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

          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
  7. The supporter density bound holds for any nonempty candidate set T.

    Apply the group hypothesis with demand ℓ = |T| and group G. Because T is nonempty, |T| ≥ 1. The number of candidates commonly approved by G is at least |T| since T ⊆ {c | ∀ i ∈ G, c ∈ A(i)}, and every voter in G has utility < |T| by construction. The group bound gives |G| * q ≤ |T| * n, which is the density bound for T.

    lines 30–31

    uses Finset.card_pos.mpr, Finset.card_le_card, Finset.mem_filter.mp

          exact h T.card (by have := Finset.card_pos.mpr hT; omega) G
            (Finset.card_le_card hsub) (fun i hi => (Finset.mem_filter.mp hi).2.2)
  8. The supporter density bound holds when T is empty.

    When T is empty, |T| = 0. No voter can satisfy the condition of having utility < 0, so the filtered set of voters is empty. The inequality simplifies to 0 * q ≤ 0 * n, which holds trivially.

    lines 32–33

    uses Finset.not_nonempty_iff_eq_empty.mp

        · have he : T = ∅ := Finset.not_nonempty_iff_eq_empty.mp hT
          simp [he]
Finset.exists_subset_card_eq
If a natural number n is at most the cardinality of a finite set s, then s contains a subset of cardinality n.
Finset.mem_filter.mpr
An element belongs to the filtered subset {x ∈ s | p x} if it belongs to s and satisfies the predicate p.
Finset.mem_univ
Every element of a finite type belongs to the universal finite set Finset.univ.
Finset.mem_filter.mp
If an element belongs to the filtered subset {x ∈ s | p x}, then it belongs to s and satisfies the predicate p.
Nat.mul_le_mul_right
Multiplying both sides of an inequality of natural numbers n ≤ m on the right by k yields n * k ≤ m * k.
Finset.card_le_card
If a finite set s is a subset of t, then |s| ≤ |t|.
Finset.mem_filter
An element belongs to {x ∈ s | p x} if and only if it belongs to s and satisfies the predicate p.
true_and
The logical conjunction True ∧ p is equivalent to p.
Finset.card_pos.mpr
A finite set has strictly positive cardinality if it is nonempty.
Finset.not_nonempty_iff_eq_empty.mp
If a finite set is not nonempty, then it is 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

theorem ejr_support_density_bound_iff_groups {n m : ℕ}    (A : Fin n → Finset (Fin m)) (q : ℕ) (W : Finset (Fin m)) :    ejr_support_density_bound A q W ↔      ∀ ℓ, 1 ≤ ℓ → ∀ G : Finset (Fin n),        ℓ ≤ (Finset.univ.filter fun c => ∀ i ∈ G, c ∈ A i).card →        (∀ i ∈ G, (A i ∩ W).card < ℓ) → G.card * q ≤ ℓ * n := by  classical  constructor  · intro h ℓ hℓ G hcommon hunsat    obtain ⟨T, hTsub, hTcard⟩ := Finset.exists_subset_card_eq hcommon    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 _, ?_, hunsat i hi⟩      intro c hc      exact (Finset.mem_filter.mp (hTsub hc)).2 i hi    have hle := Nat.mul_le_mul_right q (Finset.card_le_card hGH)    have hb := h T    rw [hTcard] at hb    exact hle.trans hb  · intro h T    by_cases hT : T.Nonempty    · let G := Finset.univ.filter fun i => T ⊆ A i ∧ (A i ∩ W).card < T.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      exact h T.card (by have := Finset.card_pos.mpr hT; omega) G        (Finset.card_le_card hsub) (fun i hi => (Finset.mem_filter.mp hi).2.2)    · have he : T = ∅ := Finset.not_nonempty_iff_eq_empty.mp hT      simp [he]
See it in the graphDiscuss this resultChallenge it