AFTD Auto-Formalizing Theoretical Domains

is_ejr_committee_zero

theoremverified

For every approval profile with at least one voter, the empty committee is an EJR committee of size 0.

Statement

theorem is_ejr_committee_zero {n m : ℕ} (A : Fin n → Finset (Fin m)) (hn : 0 < n) :
    is_ejr_committee A 0 ∅
Source
step towards ejr_committee_monotone_chain_exists
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • is_ejr_committeeA committee W with |W| = k satisfies EJR if for every ℓ ≥ 1 and every ℓ-cohesive group G some voter i ∈ G has |A_i ∩ W| ≥ ℓ.
  • is_ejr_cohesive_groupFor committee size k, a group G of the n voters is ℓ-cohesive if |G| ≥ ℓ·n/k and |∩_{i∈G} A_i| ≥ ℓ.
Used by 1

The proof, explained

An Extended Justified Representation (EJR) committee of size $0$ must have cardinality $0$ and satisfy representation for all cohesive groups of voters. The empty committee trivially has cardinality $0$. For the representation condition, any group of voters cohesive for committee size $k = 0$ with threshold $\ell \ge 1$ would have to satisfy $\ell \cdot n \le |G| \cdot 0 = 0$, which contradicts $\ell \cdot n > 0$ since $\ell \ge 1$ and $n > 0$; thus no cohesive group exists and the condition holds vacuously.

  1. The empty committee satisfies the committee size requirement $|\emptyset| = 0$.

    Applying `constructor` splits the definition of an EJR committee into two conditions: the committee size requirement and the cohesive group representation requirement. The first condition is $|\emptyset| = 0$, which holds immediately by the definition of the empty set (`simp`).

    lines 4–5

      constructor
      · simp
  2. The representation condition for cohesive groups is vacuously satisfied because no group can be cohesive for committee size $0$.

    To prove the representation condition, we introduce a threshold $\ell \ge 1$, a voter group $G$, and the assumption that $G$ is $\ell$-cohesive (`is_ejr_cohesive_group`). Cohesiveness requires $\ell \cdot n \le |G| \cdot 0 = 0$, which in natural numbers simplifies to $\ell = 0$ or $n = 0$. However, since $\ell \ge 1$ (so $\ell > 0$) and the number of voters satisfies $n > 0$ by assumption (`hn`), the product $\ell \cdot n$ is strictly positive by `Nat.mul_pos`. This contradicts $\ell = 0 \lor n = 0$, meaning no cohesive group exists and the requirement holds vacuously (`omega`).

    lines 6–10

    uses is_ejr_cohesive_group, Nat.mul_pos

      · intro ℓ hℓ G hG
        simp only [is_ejr_cohesive_group] at hG
        simp at hG
        have : 0 < ℓ * n := Nat.mul_pos (by omega) hn
        omega
is_ejr_cohesive_group
The definition stating that a group of voters $G$ is $\ell$-cohesive for committee size $k$ if $\ell \cdot n \le |G| \cdot k$ and there are at least $\ell$ candidates approved by every voter in $G$.
Nat.mul_pos
If $a$ and $b$ are strictly positive natural numbers, then their product $a \cdot b$ is strictly positive.

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

/-- For every approval profile with at least one voter, the empty committee satisfies EJR at size 0. -/theorem is_ejr_committee_zero {n m : ℕ} (A : Fin n → Finset (Fin m)) (hn : 0 < n) :    is_ejr_committee A 0 ∅ := by  constructor  · simp  · intro ℓ hℓ G hG    simp only [is_ejr_cohesive_group] at hG    simp at hG    have : 0 < ℓ * n := Nat.mul_pos (by omega) hn    omega
See it in the graphDiscuss this resultChallenge it