AFTD Auto-Formalizing Theoretical Domains

ejr_support_density_bound_supported_trap

theoremverified

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`.

  1. 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$.

    lines 7–8

    uses ejr_support_density_bound

      dsimp
      unfold ejr_support_density_bound
  2. 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.

    line 9

      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$.

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_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
See it in the graphDiscuss this resultChallenge it