ejr_support_density_bound_supported_trap
Even when every candidate has approval support, a committee satisfying the stronger density bound can have no next-size extension satisfying it. This blocks arbitrary-state induction on that predicate.
Statement
theorem ejr_support_density_bound_supported_trap : let A : Fin 3 → Finset (Fin 4) := ![{0}, {1}, {2, 3}] (∀ c : Fin 4, ∃ i : Fin 3, c ∈ A i) ∧ ejr_support_density_bound A 3 {2, 3} ∧ ¬ ∃ W : Finset (Fin 4), {2, 3} ⊆ W ∧ W.card = 3 ∧ ejr_support_density_bound A 4 W
- 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 proves the existence of a 'trap' committee by exhibiting an explicit 3-voter, 4-candidate approval profile: voter 0 approves $\{0\}$, voter 1 approves $\{1\}$, and voter 2 approves $\{2, 3\}$. Every candidate receives approval from at least one voter, and the committee $\{2, 3\}$ satisfies the density bound with quota $q = 3$. However, neither of the two possible size-3 extensions ($\{0, 2, 3\}$ and $\{1, 2, 3\}$) satisfies the density bound with quota $q = 4$, because whichever singleton candidate is omitted gives an under-represented voter violating $1 \cdot 4 \le 1 \cdot 3$. After simplifying the profile definition and unfolding the density bound, Lean completes the proof by exhaustive finite evaluation using `decide`.
The problem reduces to verifying explicit arithmetic inequalities on the subsets of candidates.
We simplify the local definition of the voter approval profile $A = (![\{0\}, \{1\}, \{2, 3\}])$ and unfold the definition of `ejr_support_density_bound`. This reformulates the three conjuncts—candidate approval support, the density bound for $\{2, 3\}$ with quota $q = 3$, and the nonexistence of an extension of size 3 satisfying the bound with quota $q = 4$—as explicit bounded quantifiers and arithmetic comparisons over the finite sets $\text{Fin } 3$ and $\text{Fin } 4$.
uses
ejr_support_density_bounddsimp unfold ejr_support_density_bound
All four candidates have approval support, the committee $\{2, 3\}$ satisfies the density bound at quota $q = 3$, and no size-3 extension of $\{2, 3\}$ satisfies the density bound at quota $q = 4$. automation
Because all candidate sets, voter sets, and committees are finite, the statement is a decidable boolean proposition. Lean's `decide` tactic evaluates it to `true` by exhaustive computation: 1. Every candidate $c \in \{0, 1, 2, 3\}$ is approved by some voter: voter 0 approves 0, voter 1 approves 1, and voter 2 approves both 2 and 3. 2. The committee $W = \{2, 3\}$ satisfies the density bound with $q = 3$: for every test set $T \subseteq \{0, 1, 2, 3\}$, the number of voters approving $T$ who have fewer than $|T|$ approved candidates in $W$, scaled by 3, is at most $3|T|$. 3. The only size-3 supersets of $\{2, 3\}$ are $\{0, 2, 3\}$ and $\{1, 2, 3\}$. For $W = \{0, 2, 3\}$, candidate 1 is omitted; testing the singleton $T = \{1\}$ gives 1 voter (voter 1), but the quota condition requires $1 \cdot 4 \le 1 \cdot 3$, which fails. Symmetrically, for $W = \{1, 2, 3\}$, candidate 0 is omitted and testing $T = \{0\}$ similarly fails ($4 \le 3$). Hence $\{2, 3\}$ cannot be extended to any valid size-3 committee.
decide
ejr_support_density_bound- Given an approval profile $A$ on $n$ voters, a quota $q$, and a committee $W$, the density bound asserts that for every candidate subset $T$, the number of voters who approve all of $T$ and have strictly fewer than $|T|$ candidates in $W$, multiplied by $q$, is at most $|T| \cdot n$.
- The verification of the finite combinatorial conditions is performed entirely by Lean's `decide` tactic via exhaustive computation over all subsets of candidates and voters.
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_supported_trap : let A : Fin 3 → Finset (Fin 4) := ![{0}, {1}, {2, 3}] (∀ c : Fin 4, ∃ i : Fin 3, c ∈ A i) ∧ ejr_support_density_bound A 3 {2, 3} ∧ ¬ ∃ W : Finset (Fin 4), {2, 3} ⊆ W ∧ W.card = 3 ∧ ejr_support_density_bound A 4 W := by dsimp unfold ejr_support_density_bound decide