AFTD Auto-Formalizing Theoretical Domains

ejr_support_density_bound_empty

theoremverified

Every approval profile satisfies the initial density bound q=1 at the empty committee.

Statement

theorem ejr_support_density_bound_empty {n m : ℕ}
    (A : Fin n → Finset (Fin m)) : ejr_support_density_bound A 1 ∅
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 3
  • 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…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

The proof, explained

To verify that the empty committee satisfies the EJR support density bound with q = 1, we fix an arbitrary candidate set T and branch on whether T is non-empty. If T is non-empty, then |T| ≥ 1, and since the number of voters who approve T cannot exceed the total number of voters n, the inequality (count * 1 ≤ |T| * n) follows immediately. If T is empty, |T| = 0, which makes the required condition that a voter has strictly fewer than 0 approved candidates impossible, leaving the count at 0 and rendering the bound 0 ≤ 0 trivial.

  1. It suffices to verify the inequality for an arbitrary candidate set T, splitting into cases where T is non-empty or empty.

    After enabling classical reasoning, we introduce an arbitrary candidate set T and split into two cases based on whether T is non-empty.

    lines 3–5

      classical
      intro T
      by_cases hT : T.Nonempty
  2. The number of voters satisfying the condition is at most the total number of voters n.

    The set of voters who approve T and have fewer than |T| approved candidates in the empty committee is a filtered sub-finset of all n voters. By Finset.card_filter_le, its size is at most the cardinality of the universe Fin n, which is n.

    lines 6–9

    uses Finset.card_filter_le

      · have hsub : (Finset.univ.filter fun i => T ⊆ A i ∧
            (A i ∩ (∅ : Finset (Fin m))).card < T.card).card ≤ n := by
          simpa using Finset.card_filter_le (s := (Finset.univ : Finset (Fin n)))
            (p := fun i => T ⊆ A i ∧ (A i ∩ (∅ : Finset (Fin m))).card < T.card)
  3. When T is non-empty, the density bound holds.

    Since T is non-empty, its cardinality is at least 1 by Finset.card_pos.mpr. Simplifying the product by 1 using mul_one, the inequality reduces to checking that the voter count is at most |T| * n. Because the voter count is at most n and |T| ≥ 1, this follows by elementary arithmetic (nlinarith).

    lines 10–12

    uses Finset.card_pos.mpr, mul_one

        have hpos := Finset.card_pos.mpr hT
        simp only [mul_one]
        nlinarith
  4. When T is empty, the density bound holds.

    If T is not non-empty, then T = ∅ by Finset.not_nonempty_iff_eq_empty.mp. When T is empty, |T| = 0, so the condition (A i ∩ ∅).card < |T| requires a non-negative cardinality to be strictly less than 0. No voter satisfies this condition, so the filtered set is empty and the inequality trivializes to 0 ≤ 0.

    lines 13–14

    uses Finset.not_nonempty_iff_eq_empty.mp

      · have he : T = ∅ := Finset.not_nonempty_iff_eq_empty.mp hT
        simp [he]
Finset.card_filter_le
The cardinality of a filtered sub-finset of s is at most the cardinality of s.
Finset.card_pos.mpr
A finset is non-empty if and only if its cardinality is strictly greater than 0; the .mpr direction deduces positivity from non-emptiness.
mul_one
Multiplying by 1 on the right leaves an element unchanged: a * 1 = a.
Finset.not_nonempty_iff_eq_empty.mp
If a finset is not non-empty, it is the empty 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

theorem ejr_support_density_bound_empty {n m : ℕ}    (A : Fin n → Finset (Fin m)) : ejr_support_density_bound A 1 ∅ := by  classical  intro T  by_cases hT : T.Nonempty  · have hsub : (Finset.univ.filter fun i => T ⊆ A i ∧        (A i ∩ (∅ : Finset (Fin m))).card < T.card).card ≤ n := by      simpa using Finset.card_filter_le (s := (Finset.univ : Finset (Fin n)))        (p := fun i => T ⊆ A i ∧ (A i ∩ (∅ : Finset (Fin m))).card < T.card)    have hpos := Finset.card_pos.mpr hT    simp only [mul_one]    nlinarith  · have he : T = ∅ := Finset.not_nonempty_iff_eq_empty.mp hT    simp [he]
See it in the graphDiscuss this resultChallenge it