is_ejr_committee_zero
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
- ejr_chain_candidates_le_threeEvery approval profile on at most three candidates admits an EJR committee chain.
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.
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`).
constructor · simp
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`).
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.
- Because Lean's `omega` tactic solves linear integer arithmetic, it cannot reason directly about the non-linear multiplication $\ell \cdot n$; the proof explicitly invokes `Nat.mul_pos` on line 9 to deduce $0 < \ell \cdot n$, allowing `omega` to detect the linear contradiction on line 10.
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.
/-- 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