not_ejr_committee_two_voters_ignored
If two voters both approve only candidate 0, the committee {1} of size 1 violates EJR.
Statement
theorem not_ejr_committee_two_voters_ignored : ¬ is_ejr_committee (n := 2) (m := 2) ![{0}, {0}] 1 {1}- Source
- sanity check of is_ejr_committee
- Verified
- 06 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| ≥ ℓ.
The proof, explained
To show that the committee $\{1\}$ of size 1 violates Extended Justified Representation (EJR) when both voters approve only candidate 0, we argue by contradiction. The set of all voters $G = \{0, 1\}$ forms an EJR cohesive group for $\ell = 1$ because the voters meet the quota requirement and mutually approve candidate 0. Under EJR, at least one voter in $G$ must approve a committee member, but neither voter approves candidate 1, yielding an immediate contradiction.
Assume for contradiction that the committee $\{1\}$ satisfies EJR.
We assume that $\{1\}$ is an EJR committee. Unfolding this assumption, we discard the committee size condition and retain the representation property $h$: for every quota level $\ell \ge 1$ and every cohesive group $G$, at least one voter in $G$ must approve at least $\ell$ committee members.
rintro ⟨-, h⟩
The group of all voters $G = \{0, 1\}$ is cohesive for $\ell = 1$, so EJR implies some voter $i \in G$ approves candidate 1.
We specialize the EJR hypothesis $h$ to $\ell = 1$ (using reflexivity `le_rfl` for $1 \le 1$) and group $G = \{0, 1\}$. To satisfy cohesiveness, the group must meet the quota threshold $1 \cdot 2 \le |G| \cdot 1$ and have at least 1 candidate approved by all members of $G$; both conditions hold since $|G| = 2$ and both voters approve candidate 0. Unfolding the definition of a cohesive group, Lean verifies this by finite evaluation (`decide`). This yields a voter $i \in \{0, 1\}$ who approves at least 1 candidate in $\{1\}$.
uses
le_rflobtain ⟨i, hi, hl⟩ := h 1 le_rfl {0, 1} (by unfold is_ejr_cohesive_group; decide)
Contradiction: neither voter approves candidate 1.
Reverting the voter $i$, the membership $i \in \{0, 1\}$, and the overlap inequality back into the goal transforms it into the statement that no voter $i \in \{0, 1\}$ has $|A_i \cap \{1\}| \ge 1$. Since both voters only approve $\{0\}$, their intersection with $\{1\}$ is empty (cardinality 0), which `decide` verifies by exhaustive evaluation on the two voters, completing the contradiction.
revert hl; revert hi; revert i; decide
le_rfl- Any element in a preorder is less than or equal to itself: $a \le a$.
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 not_ejr_committee_two_voters_ignored : ¬ is_ejr_committee (n := 2) (m := 2) ![{0}, {0}] 1 {1} := by rintro ⟨-, h⟩ obtain ⟨i, hi, hl⟩ := h 1 le_rfl {0, 1} (by unfold is_ejr_cohesive_group; decide) revert hl; revert hi; revert i; decide