ejr_support_density_bound_empty
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
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.
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.
classical intro T by_cases hT : T.Nonempty
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.
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)
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).
uses
Finset.card_pos.mpr,mul_onehave hpos := Finset.card_pos.mpr hT simp only [mul_one] nlinarith
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.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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]