AFTD Auto-Formalizing Theoretical Domains

ejr_two_voters_criterion

theoremverified

For two voters, a committee W of size k satisfies EJR whenever: (1) if k ≤ |A 0 ∩ A 1| then W ⊆ A 0 ∩ A 1; (2) if |A 0 ∩ A 1| ≤ k then A 0 ∩ A 1 ⊆ W; and (3) for each voter i ∈ {0, 1}, if |A i ∩ W| < |A i| then k ≤ 2 * |A i ∩ W| + 1.

Statement

theorem ejr_two_voters_criterion {m : ℕ} (A : Fin 2 → Finset (Fin m))
    (k : ℕ) (W : Finset (Fin m)) (hWcard : W.card = k)
    (hA : k ≤ (A 0 ∩ A 1).card → W ⊆ A 0 ∩ A 1)
    (hB : (A 0 ∩ A 1).card ≤ k → A 0 ∩ A 1 ⊆ W)
    (hD : (A 0 ∩ W).card < (A 0).card → k ≤ 2 * (A 0 ∩ W).card + 1)
    (hE : (A 1 ∩ W).card < (A 1).card → k ≤ 2 * (A 1 ∩ W).card + 1) :
    is_ejr_committee A k W
Source
step towards ejr_chain_two_voters
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • is_ejr_committee_iff_candidate_subsetsEJR is equivalent to the correct committee size together with the underrepresented-supporter inequality for every nonempty candidate…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • 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| ≥ ℓ.
Used by 1
  • ejr_chain_two_votersFor every approval profile with two voters and any number of candidates, there is an ordering of the candidates every prefix of which is…

The proof, explained

The proof characterizes Extended Justified Representation (EJR) using an equivalent candidate-subset condition: for any non-empty candidate set T, the set S of voters who approve all of T and have strictly fewer than |T| representatives in W must satisfy |S| * k < 2 * |T|. Since there are only two voters, |S| can only be 0, 1, or 2. If |S| = 0, the inequality is trivial; if |S| = 1, condition (3) on the single unsatisfied voter bounds k ≤ 2 * |A i ∩ W| + 1 < 2 * |T|; and if |S| = 2, both voters approve T, and assuming |T| ≤ k produces a contradiction using either condition (1) or (2) depending on how k compares to |A 0 ∩ A 1|.

  1. To establish that W is an EJR committee, it suffices to show that |S| * k < 2 * |T| for every non-empty candidate set T, where S is the set of voters i ∈ {0, 1} who approve all of T and have |A i ∩ W| < |T|.

    By is_ejr_committee_iff_candidate_subsets, a committee W satisfies EJR if and only if |W| = k and for every non-empty subset of candidates T, |S| * k < |T| * n, where n = 2 is the number of voters and S consists of voters approving T with strictly fewer than |T| representatives in W. The cardinality condition |W| = k is directly provided by hWcard, leaving only the inequality to verify for an arbitrary non-empty T.

    lines 9–10

    uses is_ejr_committee_iff_candidate_subsets

      rw [is_ejr_committee_iff_candidate_subsets]
      refine ⟨hWcard, fun T hT => ?_⟩
  2. |T| > 0, and the number of unsatisfied voters |S| is at most 2.

    Since T is non-empty, its cardinality is strictly positive (Finset.Nonempty.card_pos). Defining S as the set of voters in Fin 2 who approve T and have |A i ∩ W| < |T|, S is a subset of the two-element type Fin 2, so |S| ≤ 2 by Finset.card_le_univ.

    lines 11–16

    uses Finset.Nonempty.card_pos, Finset.card_le_univ

      have hTpos : 0 < T.card := Finset.Nonempty.card_pos hT
      generalize hS : (Finset.univ.filter fun i : Fin 2 => T ⊆ A i ∧ (A i ∩ W).card < T.card) = S
      have hS_le : S.card ≤ 2 := by
        rw [← hS]
        have := Finset.card_le_univ (Finset.univ.filter fun i : Fin 2 => T ⊆ A i ∧ (A i ∩ W).card < T.card)
        simpa using this
  3. The inequality |S| * k < 2 * |T| holds when |S| = 0.

    We perform a case split on |S| ∈ {0, 1, 2}. When |S| = 0, the left-hand side reduces to 0 * k = 0 by zero_mul. Since |T| > 0 and 2 > 0, their product 2 * |T| is strictly positive by mul_pos, satisfying 0 < 2 * |T|.

    lines 17–19

    uses zero_mul, mul_pos

      interval_cases hSc : S.card
      · rw [zero_mul]
        exact mul_pos hTpos (by decide)
  4. The inequality |S| * k < 2 * |T| holds when |S| = 1.

    When |S| = 1, S consists of a unique voter i ∈ {0, 1} (Finset.card_eq_one.mp). In either case (i = 0 or i = 1), voter i satisfies T ⊆ A i and |A i ∩ W| < |T|. Since T ⊆ A i implies |T| ≤ |A i|, we have |A i ∩ W| < |A i|. The corresponding hypothesis (hD for voter 0, hE for voter 1) gives k ≤ 2 * |A i ∩ W| + 1. Since |A i ∩ W| ≤ |T| - 1, linear arithmetic over ℕ establishes k < 2 * |T|.

    lines 20–35

    uses Finset.card_eq_one.mp, Finset.mem_singleton_self, Finset.mem_filter, Finset.card_le_card, lt_of_lt_of_le

      · obtain ⟨i, hi⟩ := Finset.card_eq_one.mp hSc
        have hiS : i ∈ S := by rw [hi]; exact Finset.mem_singleton_self i
        rw [← hS, Finset.mem_filter] at hiS
        fin_cases i
        · dsimp at hiS
          obtain ⟨-, hsub, hlt⟩ := hiS
          have hTleA : T.card ≤ (A 0).card := Finset.card_le_card hsub
          have hltA : (A 0 ∩ W).card < (A 0).card := lt_of_lt_of_le hlt hTleA
          have hk := hD hltA
          linarith
        · dsimp at hiS
          obtain ⟨-, hsub, hlt⟩ := hiS
          have hTleA : T.card ≤ (A 1).card := Finset.card_le_card hsub
          have hltA : (A 1 ∩ W).card < (A 1).card := lt_of_lt_of_le hlt hTleA
          have hk := hE hltA
          linarith
  5. When |S| = 2, both voters approve T (so T ⊆ A 0 ∩ A 1), and assuming for contradiction that 2 * k < 2 * |T| fails implies |T| ≤ k.

    Since |S| = 2, S must be all of Fin 2 (Finset.eq_univ_of_card). Thus both 0 ∈ S and 1 ∈ S, which means T ⊆ A 0, T ⊆ A 1, and |A i ∩ W| < |T| for both voters. In particular, T ⊆ A 0 ∩ A 1 by Finset.subset_inter. Assuming for contradiction that ¬(2 * k < 2 * |T|), linear arithmetic gives |T| ≤ k.

    lines 36–44

    uses Finset.eq_univ_of_card, Finset.mem_univ, Finset.mem_filter, Finset.subset_inter

      · have hS_univ : S = Finset.univ := Finset.eq_univ_of_card S (by simpa using hSc)
        have h0S : (0 : Fin 2) ∈ S := by rw [hS_univ]; exact Finset.mem_univ 0
        have h1S : (1 : Fin 2) ∈ S := by rw [hS_univ]; exact Finset.mem_univ 1
        rw [← hS, Finset.mem_filter] at h0S h1S
        obtain ⟨-, hT0, hlt0⟩ := h0S
        obtain ⟨-, hT1, hlt1⟩ := h1S
        have hTsub : T ⊆ A 0 ∩ A 1 := Finset.subset_inter hT0 hT1
        by_contra hnot
        have hTk : T.card ≤ k := by linarith
  6. A contradiction arises in the subcase |A 0 ∩ A 1| ≤ k.

    By le_total, either |A 0 ∩ A 1| ≤ k or k ≤ |A 0 ∩ A 1|. If |A 0 ∩ A 1| ≤ k, hypothesis hB implies A 0 ∩ A 1 ⊆ W. Since T ⊆ A 0 ∩ A 1, we get T ⊆ W by transitivity, and together with T ⊆ A 0 this yields T ⊆ A 0 ∩ W. Hence |T| ≤ |A 0 ∩ W|, contradicting the fact that 0 ∈ S requires |A 0 ∩ W| < |T|.

    lines 45–50

    uses le_total, Finset.Subset.trans, Finset.subset_inter, Finset.card_le_card

        rcases le_total ((A 0 ∩ A 1).card) k with hle | hle
        · have hsubW : A 0 ∩ A 1 ⊆ W := hB hle
          have hTW : T ⊆ W := Finset.Subset.trans hTsub hsubW
          have hT0W : T ⊆ A 0 ∩ W := Finset.subset_inter hT0 hTW
          have hle_card : T.card ≤ (A 0 ∩ W).card := Finset.card_le_card hT0W
          linarith
  7. A contradiction arises in the subcase k ≤ |A 0 ∩ A 1|.

    If k ≤ |A 0 ∩ A 1|, hypothesis hA implies W ⊆ A 0 ∩ A 1. Since A 0 ∩ A 1 ⊆ A 0, transitivity gives W ⊆ A 0, which means A 0 ∩ W = W (Finset.inter_eq_right.mpr). Therefore |A 0 ∩ W| = |W| = k. But 0 ∈ S gives k = |A 0 ∩ W| < |T|, which contradicts |T| ≤ k.

    lines 51–55

    uses Finset.Subset.trans, Finset.inter_subset_left, Finset.inter_eq_right.mpr

        · have hWsub : W ⊆ A 0 ∩ A 1 := hA hle
          have hW0 : W ⊆ A 0 := Finset.Subset.trans hWsub Finset.inter_subset_left
          have hAW : A 0 ∩ W = W := Finset.inter_eq_right.mpr hW0
          have hcard : (A 0 ∩ W).card = k := by rw [hAW, hWcard]
          linarith
is_ejr_committee_iff_candidate_subsets
A committee W of size k satisfies EJR for a profile of n voters if and only if for every non-empty candidate set T, the number of voters who approve T and have strictly fewer than |T| committee members in W, multiplied by k, is strictly less than |T| * n.
Finset.Nonempty.card_pos
A finite set is non-empty if and only if its cardinality is strictly positive.
Finset.card_le_univ
The cardinality of any finset of a finite type is at most the cardinality of the full type.
zero_mul
Zero multiplied by any element is zero: 0 * a = 0.
mul_pos
The product of two strictly positive elements in a preordered ring is strictly positive.
Finset.card_eq_one.mp
If a finset has cardinality 1, then it is a singleton {a} for some element a.
Finset.mem_singleton_self
Any element belongs to its own singleton set: a ∈ {a}.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the base set and satisfies the filtering predicate.
Finset.card_le_card
If s ⊆ t, then |s| ≤ |t|.
lt_of_lt_of_le
Strict inequality is transitive with non-strict inequality: if a < b and b ≤ c, then a < c.
Finset.eq_univ_of_card
A subset of a finite type whose cardinality equals the cardinality of the whole type is the entire universe set.
Finset.mem_univ
Every element of a finite type belongs to the universal finset Finset.univ.
Finset.subset_inter
If s ⊆ u and s ⊆ v, then s ⊆ u ∩ v.
le_total
In any linear order, any two elements are comparable: a ≤ b ∨ b ≤ a.
Finset.Subset.trans
Subset inclusion is transitive: if s₁ ⊆ s₂ and s₂ ⊆ s₃, then s₁ ⊆ s₃.
Finset.inter_subset_left
The intersection of two sets is a subset of the first set: s₁ ∩ s₂ ⊆ s₁.
Finset.inter_eq_right.mpr
If t ⊆ s, then s ∩ t = t.

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 two voters, a committee W of size k satisfies EJR whenever: (1) if k ≤ |A 0 ∩ A 1| then W ⊆ A 0 ∩ A 1; (2) if |A 0 ∩ A 1| ≤ k then A 0 ∩ A 1 ⊆ W; and (3) for each voter i ∈ {0, 1}, if |A i ∩ W| < |A i| then k ≤ 2 * |A i ∩ W| + 1. -/theorem ejr_two_voters_criterion {m : ℕ} (A : Fin 2 → Finset (Fin m))    (k : ℕ) (W : Finset (Fin m)) (hWcard : W.card = k)    (hA : k ≤ (A 0 ∩ A 1).card → W ⊆ A 0 ∩ A 1)    (hB : (A 0 ∩ A 1).card ≤ k → A 0 ∩ A 1 ⊆ W)    (hD : (A 0 ∩ W).card < (A 0).card → k ≤ 2 * (A 0 ∩ W).card + 1)    (hE : (A 1 ∩ W).card < (A 1).card → k ≤ 2 * (A 1 ∩ W).card + 1) :    is_ejr_committee A k W := by  rw [is_ejr_committee_iff_candidate_subsets]  refine ⟨hWcard, fun T hT => ?_⟩  have hTpos : 0 < T.card := Finset.Nonempty.card_pos hT  generalize hS : (Finset.univ.filter fun i : Fin 2 => T ⊆ A i ∧ (A i ∩ W).card < T.card) = S  have hS_le : S.card ≤ 2 := by    rw [← hS]    have := Finset.card_le_univ (Finset.univ.filter fun i : Fin 2 => T ⊆ A i ∧ (A i ∩ W).card < T.card)    simpa using this  interval_cases hSc : S.card  · rw [zero_mul]    exact mul_pos hTpos (by decide)  · obtain ⟨i, hi⟩ := Finset.card_eq_one.mp hSc    have hiS : i ∈ S := by rw [hi]; exact Finset.mem_singleton_self i    rw [← hS, Finset.mem_filter] at hiS    fin_cases i    · dsimp at hiS      obtain ⟨-, hsub, hlt⟩ := hiS      have hTleA : T.card ≤ (A 0).card := Finset.card_le_card hsub      have hltA : (A 0 ∩ W).card < (A 0).card := lt_of_lt_of_le hlt hTleA      have hk := hD hltA      linarith    · dsimp at hiS      obtain ⟨-, hsub, hlt⟩ := hiS      have hTleA : T.card ≤ (A 1).card := Finset.card_le_card hsub      have hltA : (A 1 ∩ W).card < (A 1).card := lt_of_lt_of_le hlt hTleA      have hk := hE hltA      linarith  · have hS_univ : S = Finset.univ := Finset.eq_univ_of_card S (by simpa using hSc)    have h0S : (0 : Fin 2) ∈ S := by rw [hS_univ]; exact Finset.mem_univ 0    have h1S : (1 : Fin 2) ∈ S := by rw [hS_univ]; exact Finset.mem_univ 1    rw [← hS, Finset.mem_filter] at h0S h1S    obtain ⟨-, hT0, hlt0⟩ := h0S    obtain ⟨-, hT1, hlt1⟩ := h1S    have hTsub : T ⊆ A 0 ∩ A 1 := Finset.subset_inter hT0 hT1    by_contra hnot    have hTk : T.card ≤ k := by linarith    rcases le_total ((A 0 ∩ A 1).card) k with hle | hle    · have hsubW : A 0 ∩ A 1 ⊆ W := hB hle      have hTW : T ⊆ W := Finset.Subset.trans hTsub hsubW      have hT0W : T ⊆ A 0 ∩ W := Finset.subset_inter hT0 hTW      have hle_card : T.card ≤ (A 0 ∩ W).card := Finset.card_le_card hT0W      linarith    · have hWsub : W ⊆ A 0 ∩ A 1 := hA hle      have hW0 : W ⊆ A 0 := Finset.Subset.trans hWsub Finset.inter_subset_left      have hAW : A 0 ∩ W = W := Finset.inter_eq_right.mpr hW0      have hcard : (A 0 ∩ W).card = k := by rw [hAW, hWcard]      linarith
See it in the graphDiscuss this resultChallenge it