AFTD Auto-Formalizing Theoretical Domains

not_ejr_committee_two_voters_ignored

theoremverified

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.

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

    line 2

      rintro ⟨-, h⟩
  2. 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\}$.

    line 3

    uses le_rfl

      obtain ⟨i, hi, hl⟩ := h 1 le_rfl {0, 1} (by unfold is_ejr_cohesive_group; decide)
  3. 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.

    line 4

      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

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