AFTD Auto-Formalizing Theoretical Domains

ejr_chain_two_voters

theoremverified

For every approval profile with two voters and any number of candidates, there is an ordering of the candidates every prefix of which is an EJR committee of the corresponding size.

Statement

theorem ejr_chain_two_voters {m : ℕ} (A : Fin 2 → Finset (Fin m)) :
    ∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m →
      is_ejr_committee A k (Finset.univ.filter fun c => (σ c : ℕ) < k)
Source
step towards ejr_committee_monotone_chain_exists
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • ejr_chain_iff_level_supportersA permutation whose every prefix of length k is an EJR committee exists if and only if there is a permutation such that for every k ≤ m…
  • exists_perm_with_prefix_eq_takeEvery duplicate-free list L of length m whose entries are the m candidates is the order of appearance of some permutation σ: for every k ≤…
  • ejr_two_voters_criterionFor 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…
  • 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| ≥ ℓ.

The proof, explained

The theorem establishes that for any two-voter approval profile, there is an ordering of candidates whose prefixes are all EJR committees of corresponding sizes. By a characterization lemma (ejr_chain_iff_level_supporters), this reduces to showing that for any nonempty set of candidates T and any prefix size k, the number of underrepresented voters |S_b| satisfies |S_b| · k < 2|T|. The key move is constructing a candidate ordering that places common approvals A 0 ∩ A 1 first and strictly alternates between voter 0's and voter 1's exclusive approvals, ensuring that every approved candidate appears with density at least 1/2 for that voter. When |S_b| = 1, this density condition forces k < 2|T|; when |S_b| = 2, placing common approvals first forces k < |T|, concluding the proof.

  1. For any natural numbers a and i, the number of elements in Fin a strictly less than i is min(i, a).

    We split into cases depending on whether i < a or i ≥ a. When i < a, the filtered set is the open interval Finset.Iio ⟨i, h⟩, which has cardinality i = min(i, a). When i ≥ a, every element of Fin a is strictly less than i, so the filtered set is all of Finset.univ, which has cardinality a = min(i, a).

    lines 1–10

    uses Fin.card_Iio, min_eq_left, le_of_lt, Finset.card_univ, Fintype.card_fin, min_eq_right

    private lemma ejr_chain_two_voters_card_fin_filter_lt {a i : ℕ} :
        (Finset.univ.filter fun j : Fin a => (j : ℕ) < i).card = min i a := by
      rcases Nat.lt_or_ge i a with h | h
      · have h1 : (Finset.univ.filter fun j : Fin a => (j : ℕ) < i) = Finset.Iio (⟨i, h⟩ : Fin a) := by
          ext j; simp [Finset.mem_Iio, Fin.lt_def]
        rw [h1, Fin.card_Iio, min_eq_left (le_of_lt h)]
      · have h1 : (Finset.univ.filter fun j : Fin a => (j : ℕ) < i) = Finset.univ := by
          ext j; simp only [Finset.mem_filter, Finset.mem_univ, true_and, iff_true]
          have := j.isLt; omega
        rw [h1, Finset.card_univ, Fintype.card_fin, min_eq_right h]
  2. Every prefix of length k ≤ m under any permutation σ of Fin m has cardinality k.

    We split into cases on whether k < m or k ≥ m. If k < m, the prefix {c | σ(c) < k} is the image under σ⁻¹ of the initial segment Finset.Iio ⟨k, h⟩, so its cardinality is k. If k ≥ m, then since k ≤ m we have k = m, and the prefix equals the entire universe of m candidates, so its cardinality is m = k.

    lines 12–34

    uses Finset.card_map, le_antisymm, Finset.card_univ, Fintype.card_fin

    private lemma ejr_chain_two_voters_prefix_card {m k : ℕ} (hk : k ≤ m) (σ : Equiv.Perm (Fin m)) :
        (Finset.univ.filter fun c => (σ c : ℕ) < k).card = k := by
      rcases Nat.lt_or_ge k m with h | h
      · have h1 : (Finset.univ.filter fun c : Fin m => (σ c : ℕ) < k)
            = Finset.map (σ.symm.toEmbedding) (Finset.Iio (⟨k, h⟩ : Fin m)) := by
          ext c
          simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_map,
            Equiv.coe_toEmbedding, Finset.mem_Iio, Fin.lt_def]
          constructor
          · intro hc
            exact ⟨σ c, hc, σ.symm_apply_apply c⟩
          · rintro ⟨i, hi, rfl⟩
            simp only [Equiv.apply_symm_apply]
            exact hi
        rw [h1, Finset.card_map]
        simp
      · have hkm : k = m := le_antisymm hk h
        have h2 : (Finset.univ.filter fun c : Fin m => (σ c : ℕ) < k) = Finset.univ := by
          ext c
          simp only [Finset.mem_filter, Finset.mem_univ, true_and, iff_true]
          rw [hkm]; exact (σ c).isLt
        rw [h2, Finset.card_univ, Fintype.card_fin, hkm]
    
  3. The cardinality of a disjoint union of two filtered sets is the sum of their individual filtered cardinalities.

    We first observe that filtering the universe for x ∈ s ∧ p(x) equals s.filter p. For disjoint sets s and t, the set of elements satisfying x ∈ s ∧ p(x) or x ∈ t ∧ q(x) is the union of two disjoint finsets, so its cardinality is the sum of their cardinalities by Finset.card_union_of_disjoint.

    lines 35–55

    uses Finset.card_union_of_disjoint, ejr_chain_two_voters_filter_mem_and, Finset.disjoint_left

    private lemma ejr_chain_two_voters_filter_mem_and {α : Type*} [Fintype α] [DecidableEq α]
        (s : Finset α) (p : α → Prop) [DecidablePred p] :
        (Finset.univ.filter fun x => x ∈ s ∧ p x).card = (s.filter p).card := by
      congr 1
      ext x
      simp
    
    private lemma ejr_chain_two_voters_filter_or_card {α : Type*} [Fintype α] [DecidableEq α]
        (s t : Finset α) (p q : α → Prop) [DecidablePred p] [DecidablePred q] (h : Disjoint s t) :
        (Finset.univ.filter fun x => (x ∈ s ∧ p x) ∨ (x ∈ t ∧ q x)).card
          = (s.filter p).card + (t.filter q).card := by
      have h1 : (Finset.univ.filter fun x => (x ∈ s ∧ p x) ∨ (x ∈ t ∧ q x))
          = (Finset.univ.filter fun x => x ∈ s ∧ p x) ∪ (Finset.univ.filter fun x => x ∈ t ∧ q x) := by
        ext x; simp
      rw [h1, Finset.card_union_of_disjoint]
      · rw [ejr_chain_two_voters_filter_mem_and, ejr_chain_two_voters_filter_mem_and]
      · rw [Finset.disjoint_left]
        intro x hx hx'
        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx hx'
        exact (Finset.disjoint_left.mp h hx.1 hx'.1)
    
  4. The number of elements in a finite set s having rank at most j under a bijection e : s ≃ Fin |s| is min(j + 1, |s|).

    We express the filtered set {x ∈ s | e(x) ≤ j} as the image under e⁻¹ of {k : Fin |s| | k < j + 1}. Because e⁻¹ is injective, this image has the same cardinality as the index set, which equals min(j + 1, |s|) by ejr_chain_two_voters_card_fin_filter_lt.

    lines 56–85

    uses ejr_chain_two_voters_card_fin_filter_lt, Finset.card_image_of_injective, Subtype.ext

    private lemma ejr_chain_two_voters_block_card {α : Type*} [Fintype α] [DecidableEq α]
        (s : Finset α) (e : ↥s ≃ Fin s.card) (kf : α → ℕ)
        (hk : kf = fun x => if h : x ∈ s then (e ⟨x, h⟩ : ℕ) else 0) (j : ℕ) :
        (Finset.univ.filter fun x => x ∈ s ∧ kf x ≤ j).card = min (j + 1) s.card := by
      rw [hk]
      have himg : (Finset.univ.filter fun x => x ∈ s ∧ (if h : x ∈ s then (e ⟨x, h⟩ : ℕ) else 0) ≤ j)
          = Finset.image (fun k : Fin s.card => ((e.symm k : ↥s) : α))
              (Finset.univ.filter fun k : Fin s.card => (k : ℕ) < j + 1) := by
        ext x
        constructor
        · intro hx
          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx
          obtain ⟨hxs, hkx⟩ := hx
          refine Finset.mem_image.mpr ⟨e ⟨x, hxs⟩, ?_, ?_⟩
          · simp only [Finset.mem_filter, Finset.mem_univ, true_and]
            rw [dif_pos hxs] at hkx; omega
          · simp
        · intro hx
          obtain ⟨k, hkm, rfl⟩ := Finset.mem_image.mp hx
          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hkm ⊢
          refine ⟨(e.symm k).2, ?_⟩
          rw [dif_pos (e.symm k).2]
          have h1 : (⟨↑(e.symm k), (e.symm k).2⟩ : ↥s) = e.symm k := rfl
          rw [h1, Equiv.apply_symm_apply]
          omega
      rw [himg, Finset.card_image_of_injective]
      · exact ejr_chain_two_voters_card_fin_filter_lt
      · intro k1 k2 h
        exact e.symm.injective (Subtype.ext h)
    
  5. Any injective ranking r : Fin m → ℕ induces an order-isomorphic permutation σ where σ(a) is the number of elements with smaller rank than a.

    We define f(a) = |{b | r(b) < r(a)}|. Because r(a) < r(a) cannot hold, the filtered set is a proper subset of Fin m, so f(a) < m. If r(a) < r(b), then {d | r(d) < r(a)} is a strict subset of {d | r(d) < r(b)}, so f is strictly monotone, hence injective. On a finite set, injectivity implies bijectivity, producing an equivalence σ that preserves the strict ordering of r.

    lines 86–144

    uses Finset.card_lt_card, Equiv.ofBijective, lt_trichotomy, Equiv.ofBijective_apply

    private lemma ejr_chain_two_voters_perm_of_rank {m : ℕ} (r : Fin m → ℕ) (hr : Function.Injective r) :
        ∃ σ : Equiv.Perm (Fin m), (∀ a b, r a < r b ↔ σ a < σ b) ∧
          (∀ a, (σ a : ℕ) = (Finset.univ.filter fun b => r b < r a).card) := by
      have key : ∀ a : Fin m, (Finset.univ.filter fun b : Fin m => r b < r a).card < m := by
        intro a
        have hne : (Finset.univ.filter fun b : Fin m => r b < r a) ≠ Finset.univ := by
          intro h
          have h2 : a ∈ Finset.univ.filter (fun b : Fin m => r b < r a) := by
            rw [h]; exact Finset.mem_univ a
          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at h2
          exact lt_irrefl _ h2
        have := Finset.card_lt_card (Finset.ssubset_iff_subset_ne.mpr ⟨Finset.filter_subset _ _, hne⟩)
        simpa using this
      set f : Fin m → Fin m := fun a => ⟨(Finset.univ.filter fun b => r b < r a).card, key a⟩ with hf
      have hmono : ∀ a b : Fin m, r a < r b →
          (Finset.univ.filter fun d => r d < r a).card < (Finset.univ.filter fun d => r d < r b).card := by
        intro a b hab
        have hne : (Finset.univ.filter fun d : Fin m => r d < r a) ≠
            (Finset.univ.filter fun d : Fin m => r d < r b) := by
          intro h
          have h2 : a ∈ Finset.univ.filter (fun d : Fin m => r d < r b) := by
            simp only [Finset.mem_filter, Finset.mem_univ, true_and]; exact hab
          rw [← h] at h2
          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at h2
          exact lt_irrefl _ h2
        have hss : (Finset.univ.filter fun d : Fin m => r d < r a) ⊂
            (Finset.univ.filter fun d : Fin m => r d < r b) := by
          refine Finset.ssubset_iff_subset_ne.mpr ⟨?_, hne⟩
          intro d
          simp only [Finset.mem_filter, Finset.mem_univ, true_and]
          omega
        exact Finset.card_lt_card hss
      have hfinj : Function.Injective f := by
        intro a b hab
        by_contra hne
        have hval : (Finset.univ.filter fun d => r d < r a).card =
            (Finset.univ.filter fun d => r d < r b).card := by
          simpa [hf] using hab
        rcases lt_or_gt_of_ne (fun h => hne (hr h)) with h | h
        · have := hmono a b h; omega
        · have := hmono b a h; omega
      have hfbij : Function.Bijective f := ⟨hfinj, Finite.injective_iff_surjective.mp hfinj⟩
      refine ⟨Equiv.ofBijective f hfbij, ?_, ?_⟩
      · intro a b
        constructor
        · intro h; exact hmono a b h
        · intro h
          have h' : f a < f b := by simpa using h
          rcases lt_trichotomy (r a) (r b) with h1 | h1 | h1
          · exact h1
          · have h2 : a = b := hr h1
            rw [h2] at h'
            exact absurd h' (lt_irrefl _)
          · exact absurd (hmono b a h1) (not_lt.mpr (le_of_lt h'))
      · intro a
        have h := Equiv.ofBijective_apply f hfbij a
        have h2 : ((Equiv.ofBijective f hfbij) a : ℕ) = (f a : ℕ) := by rw [h]
        rw [h2]
    
  6. Candidates are partitioned into C = A 0 ∩ A 1, R 0 = A 0 \ A 1, R 1 = A 1 \ A 0, and N, yielding an injective ranking function r.

    We partition candidates into common approvals C, exclusive approvals R 0 and R 1, and unapproved candidates N, indexing each block with Finset.equivFin. We define r(x) to be k_C(x) on C, |C| + 2 k_0(x) on R 0, |C| + 2 k_1(x) + 1 on R 1, and |C| + 2|R 0| + 2|R 1| + k_N(x) on N. Because the assigned values occupy mutually disjoint ranges (with R 0 receiving even offsets and R 1 receiving odd offsets above |C|), r is injective.

    lines 145–282

    uses Finset.mem_inter, Finset.mem_sdiff, Finset.equivFin, Fin.ext

    private lemma ejr_chain_two_voters_perm_exists {m : ℕ} (A : Fin 2 → Finset (Fin m)) :
        ∃ σ : Equiv.Perm (Fin m),
          (∀ c ∈ A 0 ∩ A 1, ∀ d, d ∉ A 0 ∩ A 1 → (σ c : ℕ) < (σ d : ℕ)) ∧
          (∀ (i : Fin 2) (c : Fin m), c ∈ A i →
            (σ c : ℕ) + 1 ≤ 2 * (Finset.univ.filter fun d => d ∈ A i ∧ (σ d : ℕ) ≤ (σ c : ℕ)).card) := by
      classical
      set C := A 0 ∩ A 1 with hC
      set R0 := A 0 \ A 1 with hR0
      set R1 := A 1 \ A 0 with hR1
      set N := Finset.univ \ (A 0 ∪ A 1) with hN
      have hCin : ∀ x : Fin m, x ∈ C ↔ x ∈ A 0 ∧ x ∈ A 1 := by
        intro x; rw [hC]; exact Finset.mem_inter
      have hR0in : ∀ x : Fin m, x ∈ R0 ↔ x ∈ A 0 ∧ x ∉ A 1 := by
        intro x; rw [hR0]; exact Finset.mem_sdiff
      have hR1in : ∀ x : Fin m, x ∈ R1 ↔ x ∈ A 1 ∧ x ∉ A 0 := by
        intro x; rw [hR1]; exact Finset.mem_sdiff
      have hcover : ∀ x : Fin m, x ∈ C ∨ x ∈ R0 ∨ x ∈ R1 ∨ x ∈ N := by
        intro x
        by_cases h0 : x ∈ A 0
        · by_cases h1 : x ∈ A 1
          · exact Or.inl ((hCin x).mpr ⟨h0, h1⟩)
          · exact Or.inr (Or.inl ((hR0in x).mpr ⟨h0, h1⟩))
        · by_cases h1 : x ∈ A 1
          · exact Or.inr (Or.inr (Or.inl ((hR1in x).mpr ⟨h1, h0⟩)))
          · refine Or.inr (Or.inr (Or.inr ?_))
            rw [hN]; simp [h0, h1]
      have dC0 : ∀ x, x ∈ C → x ∉ R0 := by
        intro x hx h; exact ((hR0in x).mp h).2 ((hCin x).mp hx).2
      have d0C : ∀ x, x ∈ R0 → x ∉ C := by
        intro x hx h; exact ((hR0in x).mp hx).2 ((hCin x).mp h).2
      have d1C : ∀ x, x ∈ R1 → x ∉ C := by
        intro x hx h; exact ((hR1in x).mp hx).2 ((hCin x).mp h).1
      have d01 : ∀ x, x ∈ R0 → x ∉ R1 := by
        intro x hx h; exact ((hR1in x).mp h).2 ((hR0in x).mp hx).1
      have memN : ∀ x, x ∉ C → x ∉ R0 → x ∉ R1 → x ∈ N := by
        intro x h1 h2 h3
        rcases hcover x with h | h | h | h
        · exact absurd h h1
        · exact absurd h h2
        · exact absurd h h3
        · exact h
      set kC : Fin m → ℕ := fun x => if h : x ∈ C then ((Finset.equivFin C ⟨x, h⟩ : Fin C.card) : ℕ) else 0 with hkC
      set k0 : Fin m → ℕ := fun x => if h : x ∈ R0 then ((Finset.equivFin R0 ⟨x, h⟩ : Fin R0.card) : ℕ) else 0 with hk0
      set k1 : Fin m → ℕ := fun x => if h : x ∈ R1 then ((Finset.equivFin R1 ⟨x, h⟩ : Fin R1.card) : ℕ) else 0 with hk1
      set kN : Fin m → ℕ := fun x => if h : x ∈ N then ((Finset.equivFin N ⟨x, h⟩ : Fin N.card) : ℕ) else 0 with hkN
      set r : Fin m → ℕ := fun x =>
        if x ∈ C then kC x
        else if x ∈ R0 then C.card + 2 * k0 x
        else if x ∈ R1 then C.card + 2 * k1 x + 1
        else C.card + 2 * R0.card + 2 * R1.card + kN x with hr
      have rC : ∀ x, x ∈ C → r x = kC x := by
        intro x h; rw [hr]; simp only [if_pos h]
      have rR0 : ∀ x, x ∉ C → x ∈ R0 → r x = C.card + 2 * k0 x := by
        intro x h h0; rw [hr]; simp only [if_neg h, if_pos h0]
      have rR1 : ∀ x, x ∉ C → x ∉ R0 → x ∈ R1 → r x = C.card + 2 * k1 x + 1 := by
        intro x h h0 h1; rw [hr]; simp only [if_neg h, if_neg h0, if_pos h1]
      have rN : ∀ x, x ∉ C → x ∉ R0 → x ∉ R1 → x ∈ N →
          r x = C.card + 2 * R0.card + 2 * R1.card + kN x := by
        intro x h h0 h1 hN'; rw [hr]; simp only [if_neg h, if_neg h0, if_neg h1]
      have kC_lt : ∀ x, x ∈ C → kC x < C.card := by
        intro x h; rw [hkC]; simp only [dif_pos h]; exact Fin.isLt _
      have k0_lt : ∀ x, x ∈ R0 → k0 x < R0.card := by
        intro x h; rw [hk0]; simp only [dif_pos h]; exact Fin.isLt _
      have k1_lt : ∀ x, x ∈ R1 → k1 x < R1.card := by
        intro x h; rw [hk1]; simp only [dif_pos h]; exact Fin.isLt _
      have kC_inj : ∀ x, x ∈ C → ∀ y, y ∈ C → kC x = kC y → x = y := by
        intro x hx y hy h
        rw [hkC] at h
        simp only [dif_pos hx, dif_pos hy] at h
        have h1 : (⟨x, hx⟩ : ↥C) = ⟨y, hy⟩ := (Finset.equivFin C).injective (Fin.ext h)
        exact Subtype.ext_iff.mp h1
      have k0_inj : ∀ x, x ∈ R0 → ∀ y, y ∈ R0 → k0 x = k0 y → x = y := by
        intro x hx y hy h
        rw [hk0] at h
        simp only [dif_pos hx, dif_pos hy] at h
        have h1 : (⟨x, hx⟩ : ↥R0) = ⟨y, hy⟩ := (Finset.equivFin R0).injective (Fin.ext h)
        exact Subtype.ext_iff.mp h1
      have k1_inj : ∀ x, x ∈ R1 → ∀ y, y ∈ R1 → k1 x = k1 y → x = y := by
        intro x hx y hy h
        rw [hk1] at h
        simp only [dif_pos hx, dif_pos hy] at h
        have h1 : (⟨x, hx⟩ : ↥R1) = ⟨y, hy⟩ := (Finset.equivFin R1).injective (Fin.ext h)
        exact Subtype.ext_iff.mp h1
      have kN_inj : ∀ x, x ∈ N → ∀ y, y ∈ N → kN x = kN y → x = y := by
        intro x hx y hy h
        rw [hkN] at h
        simp only [dif_pos hx, dif_pos hy] at h
        have h1 : (⟨x, hx⟩ : ↥N) = ⟨y, hy⟩ := (Finset.equivFin N).injective (Fin.ext h)
        exact Subtype.ext_iff.mp h1
      have hrinj : Function.Injective r := by
        intro x y hxy
        by_cases hxC : x ∈ C
        · have hxlt := kC_lt x hxC
          rw [rC x hxC] at hxy
          by_cases hyC : y ∈ C
          · rw [rC y hyC] at hxy; exact kC_inj x hxC y hyC hxy
          · by_cases hy0 : y ∈ R0
            · rw [rR0 y hyC hy0] at hxy; omega
            · by_cases hy1 : y ∈ R1
              · rw [rR1 y hyC hy0 hy1] at hxy; omega
              · rw [rN y hyC hy0 hy1 (memN y hyC hy0 hy1)] at hxy; omega
        · by_cases hx0 : x ∈ R0
          · have hxlt := k0_lt x hx0
            rw [rR0 x hxC hx0] at hxy
            by_cases hyC : y ∈ C
            · rw [rC y hyC] at hxy; have := kC_lt y hyC; omega
            · by_cases hy0 : y ∈ R0
              · rw [rR0 y hyC hy0] at hxy
                have hh : k0 x = k0 y := by omega
                exact k0_inj x hx0 y hy0 hh
              · by_cases hy1 : y ∈ R1
                · rw [rR1 y hyC hy0 hy1] at hxy; omega
                · rw [rN y hyC hy0 hy1 (memN y hyC hy0 hy1)] at hxy
                  have := k0_lt x hx0; omega
          · by_cases hx1 : x ∈ R1
            · have hxlt := k1_lt x hx1
              rw [rR1 x hxC hx0 hx1] at hxy
              by_cases hyC : y ∈ C
              · rw [rC y hyC] at hxy; have := kC_lt y hyC; omega
              · by_cases hy0 : y ∈ R0
                · rw [rR0 y hyC hy0] at hxy; omega
                · by_cases hy1 : y ∈ R1
                  · rw [rR1 y hyC hy0 hy1] at hxy
                    have hh : k1 x = k1 y := by omega
                    exact k1_inj x hx1 y hy1 hh
                  · rw [rN y hyC hy0 hy1 (memN y hyC hy0 hy1)] at hxy
                    have := k1_lt x hx1; omega
            · have hxN := memN x hxC hx0 hx1
              rw [rN x hxC hx0 hx1 hxN] at hxy
              by_cases hyC : y ∈ C
              · rw [rC y hyC] at hxy; have := kC_lt y hyC; omega
              · by_cases hy0 : y ∈ R0
                · rw [rR0 y hyC hy0] at hxy; have := k0_lt y hy0; omega
                · by_cases hy1 : y ∈ R1
                  · rw [rR1 y hyC hy0 hy1] at hxy; have := k1_lt y hy1; omega
                  · rw [rN y hyC hy0 hy1 (memN y hyC hy0 hy1)] at hxy
                    have hh : kN x = kN y := by omega
                    exact kN_inj x hxN y (memN y hyC hy0 hy1) hh
  7. The permutation σ induced by r places every candidate in A 0 ∩ A 1 before every candidate outside A 0 ∩ A 1.

    Every candidate c ∈ C = A 0 ∩ A 1 satisfies r(c) < |C|, whereas every candidate d ∉ C satisfies r(d) ≥ |C|. Because σ is order-isomorphic to r, σ(c) < σ(d) whenever c ∈ C and d ∉ C.

    lines 283–299

    uses ejr_chain_two_voters_perm_of_rank

      obtain ⟨σ, hσlt, hσpos⟩ := ejr_chain_two_voters_perm_of_rank r hrinj
      refine ⟨σ, ?_, ?_⟩
      · intro c hc d hd
        have hcc : c ∈ C := hc
        have hdd : d ∉ C := hd
        have hrd : C.card ≤ r d := by
          by_cases hd0 : d ∈ R0
          · rw [rR0 d hdd hd0]; omega
          · by_cases hd1 : d ∈ R1
            · rw [rR1 d hdd hd0 hd1]; omega
            · rw [rN d hdd hd0 hd1 (memN d hdd hd0 hd1)]; omega
        have hlt : r c < r d := by
          rw [rC c hcc]
          have := kC_lt c hcc
          omega
        exact Fin.lt_def.mp ((hσlt c d).mp hlt)
      · intro i c hc
  8. Every candidate c ∈ A 0 ∩ A 1 satisfies the 2-density condition σ(c) + 1 ≤ 2 · |{d ∈ A j | σ(d) ≤ σ(c)}| for both voters j ∈ {0, 1}.

    Since σ(c) ≤ r(c) and σ preserves the ordering of r, candidates in A j with σ(d) ≤ σ(c) are those with r(d) ≤ r(c). All of C is contained in A j, so this set contains all elements of C with index at most k_C(c), which has size k_C(c) + 1 by ejr_chain_two_voters_block_card. Since σ(c) ≤ r(c) = k_C(c), we obtain σ(c) + 1 ≤ 2(k_C(c) + 1).

    lines 300–353

    uses Finset.card_image_of_injective, Finset.card_le_card, ejr_chain_two_voters_block_card, min_eq_left

        have hσle : (σ c : ℕ) ≤ r c := by
          rw [hσpos c]
          have himg : (Finset.univ.filter fun d : Fin m => r d < r c).image r ⊆ Finset.range (r c) := by
            intro x hx
            obtain ⟨d, hd, rfl⟩ := Finset.mem_image.mp hx
            simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hd
            exact Finset.mem_range.mpr hd
          have h1 : (Finset.univ.filter fun d : Fin m => r d < r c).card
              = ((Finset.univ.filter fun d : Fin m => r d < r c).image r).card := by
            rw [Finset.card_image_of_injective _ hrinj]
          rw [h1]
          simpa using Finset.card_le_card himg
        have hiff : ∀ d : Fin m, ((σ d : ℕ) ≤ (σ c : ℕ)) ↔ (r d ≤ r c) := by
          intro d
          have h1 : ((σ d : ℕ) ≤ (σ c : ℕ)) ↔ (σ d ≤ σ c) := Fin.le_def.symm
          rw [h1]
          constructor
          · intro h
            rcases lt_or_eq_of_le h with h' | h'
            · exact le_of_lt ((hσlt d c).mpr h')
            · have hdc : d = c := σ.injective h'
              rw [hdc]
          · intro h
            rcases lt_or_eq_of_le h with h' | h'
            · exact le_of_lt (Fin.lt_def.mp ((hσlt d c).mp h'))
            · have hdc : d = c := hrinj h'
              rw [hdc]
        have hfilter : ∀ j : Fin 2, (Finset.univ.filter fun d => d ∈ A j ∧ (σ d : ℕ) ≤ (σ c : ℕ))
            = (Finset.univ.filter fun d => d ∈ A j ∧ r d ≤ r c) := by
          intro j
          apply Finset.filter_congr
          intro d _
          exact ⟨fun h => ⟨h.1, (hiff d).mp h.2⟩, fun h => ⟨h.1, (hiff d).mpr h.2⟩⟩
        have hCcase : ∀ (j : Fin 2), c ∈ C → c ∈ A j →
            (σ c : ℕ) + 1 ≤ 2 * (Finset.univ.filter fun d => d ∈ A j ∧ r d ≤ r c).card := by
          intro j hcc hcj
          have hmem : ∀ d, d ∈ C → d ∈ A j := by
            intro d hd
            fin_cases j
            · exact ((hCin d).mp hd).1
            · exact ((hCin d).mp hd).2
          have hsub : (Finset.univ.filter fun d => d ∈ C ∧ kC d ≤ kC c) ⊆
              (Finset.univ.filter fun d => d ∈ A j ∧ r d ≤ r c) := by
            intro d hd
            simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hd ⊢
            exact ⟨hmem d hd.1, by rw [rC d hd.1, rC c hcc]; exact hd.2⟩
          have hcard : (Finset.univ.filter fun d => d ∈ C ∧ kC d ≤ kC c).card = kC c + 1 := by
            rw [ejr_chain_two_voters_block_card C (Finset.equivFin C) kC hkC (kC c),
              min_eq_left (by have := kC_lt c hcc; omega)]
          have hlb : kC c + 1 ≤ (Finset.univ.filter fun d => d ∈ A j ∧ r d ≤ r c).card := by
            rw [← hcard]; exact Finset.card_le_card hsub
          have hrc : r c = kC c := rC c hcc
          omega
        have hi01 : i = 0 ∨ i = 1 := by fin_cases i <;> simp
  9. Every candidate in A 0 \ A 1 satisfies the 2-density condition for voter 0, and every candidate in A 1 \ A 0 satisfies it for voter 1.

    For c ∈ R 0 = A 0 \ A 1, r(c) = |C| + 2 k_0(c). The candidates in A 0 with rank at most r(c) include all |C| candidates in C together with the first k_0(c) + 1 candidates in R 0, totaling |C| + k_0(c) + 1 candidates by ejr_chain_two_voters_filter_or_card. Multiplying by 2 gives 2|C| + 2 k_0(c) + 2 > r(c) + 1 ≥ σ(c) + 1. The same reasoning applies to voter 1 and c ∈ R 1 with rank |C| + 2 k_1(c) + 1.

    lines 354–420

    uses ejr_chain_two_voters_filter_or_card, ejr_chain_two_voters_filter_mem_and, ejr_chain_two_voters_block_card, Finset.card_le_card

        by_cases hcc : c ∈ C
        · rw [hfilter i]; exact hCcase i hcc hc
        · rcases hi01 with h | h
          · rw [h] at hc ⊢
            rw [hfilter 0]
            have hc0 : c ∈ R0 := (hR0in c).mpr ⟨hc, fun h1 => hcc ((hCin c).mpr ⟨hc, h1⟩)⟩
            have hrc : r c = C.card + 2 * k0 c := rR0 c hcc hc0
            have hdisj : Disjoint C R0 := Finset.disjoint_left.mpr (fun x hx hy => dC0 x hx hy)
            have hcardU : (Finset.univ.filter fun d => (d ∈ C) ∨ (d ∈ R0 ∧ k0 d ≤ k0 c)).card
                = C.card + (k0 c + 1) := by
              have h2 := ejr_chain_two_voters_filter_or_card C R0 (fun _ => True)
                (fun d => k0 d ≤ k0 c) hdisj
              rw [show (Finset.univ.filter fun d => (d ∈ C ∧ True) ∨ (d ∈ R0 ∧ k0 d ≤ k0 c))
                    = (Finset.univ.filter fun d => (d ∈ C) ∨ (d ∈ R0 ∧ k0 d ≤ k0 c)) from by
                  congr 1; ext d; simp] at h2
              rw [h2, Finset.filter_true_of_mem (s := C) (p := fun _ => True) (fun x _ => trivial),
                  ← ejr_chain_two_voters_filter_mem_and R0 (fun d => k0 d ≤ k0 c),
                  ejr_chain_two_voters_block_card R0 (Finset.equivFin R0) k0 hk0 (k0 c),
                  min_eq_left (show k0 c + 1 ≤ R0.card by have := k0_lt c hc0; omega)]
            have hsub : (Finset.univ.filter fun d => (d ∈ C) ∨ (d ∈ R0 ∧ k0 d ≤ k0 c))
                ⊆ (Finset.univ.filter fun d => d ∈ A 0 ∧ r d ≤ r c) := by
              intro d hd
              simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hd ⊢
              rcases hd with hd | hd
              · refine ⟨((hCin d).mp hd).1, ?_⟩
                rw [rC d hd, hrc]
                have := kC_lt d hd; omega
              · refine ⟨((hR0in d).mp hd.1).1, ?_⟩
                rw [rR0 d (d0C d hd.1) hd.1, hrc]
                have := hd.2; omega
            have hlb : C.card + (k0 c + 1)
                ≤ (Finset.univ.filter fun d => d ∈ A 0 ∧ r d ≤ r c).card := by
              rw [← hcardU]; exact Finset.card_le_card hsub
            omega
          · rw [h] at hc ⊢
            rw [hfilter 1]
            have hc1 : c ∈ R1 := (hR1in c).mpr ⟨hc, fun h1 => hcc ((hCin c).mpr ⟨h1, hc⟩)⟩
            have hc1' : c ∉ R0 := fun hh => d01 c hh hc1
            have hrc : r c = C.card + 2 * k1 c + 1 := rR1 c hcc hc1' hc1
            have hdisj : Disjoint C R1 := Finset.disjoint_left.mpr (fun x hx hy => d1C x hy hx)
            have hcardU : (Finset.univ.filter fun d => (d ∈ C) ∨ (d ∈ R1 ∧ k1 d ≤ k1 c)).card
                = C.card + (k1 c + 1) := by
              have h2 := ejr_chain_two_voters_filter_or_card C R1 (fun _ => True)
                (fun d => k1 d ≤ k1 c) hdisj
              rw [show (Finset.univ.filter fun d => (d ∈ C ∧ True) ∨ (d ∈ R1 ∧ k1 d ≤ k1 c))
                    = (Finset.univ.filter fun d => (d ∈ C) ∨ (d ∈ R1 ∧ k1 d ≤ k1 c)) from by
                  congr 1; ext d; simp] at h2
              rw [h2, Finset.filter_true_of_mem (s := C) (p := fun _ => True) (fun x _ => trivial),
                  ← ejr_chain_two_voters_filter_mem_and R1 (fun d => k1 d ≤ k1 c),
                  ejr_chain_two_voters_block_card R1 (Finset.equivFin R1) k1 hk1 (k1 c),
                  min_eq_left (show k1 c + 1 ≤ R1.card by have := k1_lt c hc1; omega)]
            have hsub : (Finset.univ.filter fun d => (d ∈ C) ∨ (d ∈ R1 ∧ k1 d ≤ k1 c))
                ⊆ (Finset.univ.filter fun d => d ∈ A 1 ∧ r d ≤ r c) := by
              intro d hd
              simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hd ⊢
              rcases hd with hd | hd
              · refine ⟨((hCin d).mp hd).2, ?_⟩
                rw [rC d hd, hrc]
                have := kC_lt d hd; omega
              · refine ⟨((hR1in d).mp hd.1).1, ?_⟩
                rw [rR1 d (d1C d hd.1) (fun hh => d01 d hh hd.1) hd.1, hrc]
                have := hd.2; omega
            have hlb : C.card + (k1 c + 1)
                ≤ (Finset.univ.filter fun d => d ∈ A 1 ∧ r d ≤ r c).card := by
              rw [← hcardU]; exact Finset.card_le_card hsub
            omega
    
  10. The common approvals A 0 ∩ A 1 form the prefix of size |A 0 ∩ A 1| under σ, and their intersection with W_k has size min(k, |A 0 ∩ A 1|).

    Because every candidate in A 0 ∩ A 1 precedes every candidate outside it, A 0 ∩ A 1 is exactly the initial segment of size |A 0 ∩ A 1| under σ. Intersecting this initial segment with the prefix W_k = {c | σ(c) < k} produces the shorter of the two prefixes, which has size min(k, |A 0 ∩ A 1|) by ejr_chain_two_voters_prefix_card.

    lines 421–475

    uses ejr_chain_two_voters_perm_exists, ejr_chain_two_voters_prefix_card, Finset.card_lt_card, Finset.eq_of_subset_of_card_le

    private lemma ejr_chain_two_voters_level_supporters {m : ℕ} (A : Fin 2 → Finset (Fin m)) :
        ∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m → ∀ T : Finset (Fin m), T.Nonempty →
          (Finset.univ.filter fun i => T ⊆ A i ∧
            (A i ∩ Finset.univ.filter fun c => (σ c : ℕ) < k).card < T.card).card * k
          < T.card * 2 := by
      classical
      obtain ⟨σ, hseg, hspread⟩ := ejr_chain_two_voters_perm_exists A
      refine ⟨σ, ?_⟩
      have hcard : ∀ k ≤ m, (Finset.univ.filter fun c => (σ c : ℕ) < k).card = k :=
        fun k hk => ejr_chain_two_voters_prefix_card hk σ
      have hCeq : A 0 ∩ A 1 = Finset.univ.filter (fun c => (σ c : ℕ) < (A 0 ∩ A 1).card) := by
        set C := A 0 ∩ A 1 with hCdef
        have hCm : C.card ≤ m := by
          have h := Finset.card_le_univ C
          simpa using h
        have hsub : C ⊆ Finset.univ.filter (fun c => (σ c : ℕ) < C.card) := by
          intro c hc
          simp only [Finset.mem_filter, Finset.mem_univ, true_and]
          by_contra hge
          simp only [not_lt] at hge
          have hScard : (Finset.univ.filter (fun d => (σ d : ℕ) < (σ c : ℕ))).card = (σ c : ℕ) :=
            hcard (σ c) (le_of_lt (σ c).isLt)
          have hSC : (Finset.univ.filter (fun d => (σ d : ℕ) < (σ c : ℕ))) ⊆ C := by
            intro d hd
            simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hd
            by_contra hdC
            have := hseg c hc d hdC
            omega
          have hne : (Finset.univ.filter (fun d => (σ d : ℕ) < (σ c : ℕ))) ≠ C := by
            intro h
            have hmem : c ∈ Finset.univ.filter (fun d => (σ d : ℕ) < (σ c : ℕ)) := h ▸ hc
            simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hmem
            omega
          have hlt : (Finset.univ.filter (fun d => (σ d : ℕ) < (σ c : ℕ))).card < C.card :=
            Finset.card_lt_card (Finset.ssubset_iff_subset_ne.mpr ⟨hSC, hne⟩)
          omega
        refine Finset.eq_of_subset_of_card_le hsub ?_
        rw [hcard C.card hCm]
      have hCinter : ∀ k ≤ m, ((A 0 ∩ A 1) ∩ Finset.univ.filter (fun c => (σ c : ℕ) < k)).card
          = min k (A 0 ∩ A 1).card := by
        intro k hk
        rcases Nat.le_total k (A 0 ∩ A 1).card with h | h
        · have hsub : (Finset.univ.filter fun c => (σ c : ℕ) < k) ⊆ (A 0 ∩ A 1) := by
            rw [hCeq]
            intro c hc
            simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hc ⊢
            omega
          rw [Finset.inter_eq_right.mpr hsub, hcard k hk, min_eq_left h]
        · have hsub : (A 0 ∩ A 1) ⊆ (Finset.univ.filter fun c => (σ c : ℕ) < k) := by
            rw [hCeq]
            intro c hc
            simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hc ⊢
            omega
          rw [Finset.inter_eq_left.mpr hsub, min_eq_right h]
      intro k hk T hT
  11. If voter i approves all of T but has strictly fewer than |T| approved candidates in W_k, then k < 2|T|.

    Because |A i ∩ W_k| < |T| ≤ |A i|, the difference A i \ W_k is nonempty. Let c be its element minimizing σ, so σ(c) ≥ k. Any candidate d ∈ A i with σ(d) ≤ σ(c) must belong to W_k or equal c, so |{d ∈ A i | σ(d) ≤ σ(c)}| ≤ |A i ∩ W_k| + 1 ≤ |T|. Applying the 2-density condition to c gives k + 1 ≤ σ(c) + 1 ≤ 2|T|, hence k < 2|T|.

    lines 476–518

    uses Finset.exists_min_image, Finset.mem_sdiff, Finset.card_le_card, Finset.card_union_le, Finset.card_singleton

      set W := Finset.univ.filter (fun c => (σ c : ℕ) < k) with hW
      set Sb := Finset.univ.filter (fun i : Fin 2 => T ⊆ A i ∧ (A i ∩ W).card < T.card) with hSb
      have hℓ : 0 < T.card := Finset.card_pos.mpr hT
      have hSb2 : Sb.card ≤ 2 := by
        have h := Finset.card_le_univ Sb
        simpa using h
      have hfactA : ∀ i : Fin 2, i ∈ Sb → k < 2 * T.card := by
        intro i hi
        rw [hSb, Finset.mem_filter] at hi
        obtain ⟨-, hiT, hicard⟩ := hi
        have hEne : (A i \ W).Nonempty := by
          rw [← Finset.card_pos, Finset.card_sdiff, Finset.inter_comm]
          have h1 : T.card ≤ (A i).card := Finset.card_le_card hiT
          omega
        obtain ⟨c, hcE, hcmin⟩ := Finset.exists_min_image (A i \ W) (fun d => (σ d : ℕ)) hEne
        rw [Finset.mem_sdiff] at hcE
        obtain ⟨hcA, hcW⟩ := hcE
        have hck : k ≤ (σ c : ℕ) := by
          rw [hW] at hcW
          simp only [Finset.mem_filter, Finset.mem_univ, true_and, not_lt] at hcW
          exact hcW
        have hsub : (Finset.univ.filter fun d => d ∈ A i ∧ (σ d : ℕ) ≤ (σ c : ℕ))
            ⊆ (A i ∩ W) ∪ {c} := by
          intro d hd
          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hd
          obtain ⟨hdA, hdle⟩ := hd
          by_cases hdW : d ∈ W
          · exact Finset.mem_union_left _ (Finset.mem_inter.mpr ⟨hdA, hdW⟩)
          · have hdE : d ∈ A i \ W := Finset.mem_sdiff.mpr ⟨hdA, hdW⟩
            have h1 : (σ c : ℕ) ≤ (σ d : ℕ) := hcmin d hdE
            have h2 : (σ d : ℕ) = (σ c : ℕ) := le_antisymm hdle h1
            have h3 : d = c := σ.injective (Fin.ext h2)
            rw [h3]
            exact Finset.mem_union_right _ (Finset.mem_singleton_self c)
        have hcardle : (Finset.univ.filter fun d => d ∈ A i ∧ (σ d : ℕ) ≤ (σ c : ℕ)).card
            ≤ (A i ∩ W).card + 1 := by
          calc (Finset.univ.filter fun d => d ∈ A i ∧ (σ d : ℕ) ≤ (σ c : ℕ)).card
              ≤ ((A i ∩ W) ∪ {c}).card := Finset.card_le_card hsub
            _ ≤ (A i ∩ W).card + ({c} : Finset (Fin m)).card := Finset.card_union_le _ _
            _ = (A i ∩ W).card + 1 := by rw [Finset.card_singleton]
        have hsp := hspread i c hcA
        omega
      have hfactB : (0 : Fin 2) ∈ Sb → (1 : Fin 2) ∈ Sb → k < T.card := by
  12. If both voters approve T and each has strictly fewer than |T| approved candidates in W_k, then k < |T|.

    If both voters approve T, then T ⊆ A 0 ∩ A 1, so |T| ≤ |A 0 ∩ A 1|. If k ≥ |T|, then |(A 0 ∩ A 1) ∩ W_k| = min(k, |A 0 ∩ A 1|) ≥ |T|. Since A 0 ∩ A 1 ⊆ A 0, this would imply |A 0 ∩ W_k| ≥ |T|, contradicting the assumption that voter 0 has fewer than |T| approved candidates in W_k. Thus k < |T|.

    lines 519–532

    uses le_min, le_trans, Finset.card_le_card, Finset.inter_subset_left

        intro h0 h1
        rw [hSb, Finset.mem_filter] at h0 h1
        obtain ⟨-, hT0, hc0⟩ := h0
        obtain ⟨-, hT1, hc1⟩ := h1
        by_contra hcon
        simp only [not_lt] at hcon
        have hTC : T ⊆ A 0 ∩ A 1 := fun c hc => Finset.mem_inter.mpr ⟨hT0 hc, hT1 hc⟩
        have hCle : T.card ≤ (A 0 ∩ A 1).card := Finset.card_le_card hTC
        have h2 := hCinter k hk
        have hge : T.card ≤ (A 0 ∩ W).card := by
          have h3 : T.card ≤ ((A 0 ∩ A 1) ∩ W).card := by
            rw [h2]; exact le_min hcon hCle
          exact le_trans h3 (Finset.card_le_card (Finset.inter_subset_inter_right Finset.inter_subset_left))
        omega
  13. The number of underrepresented voters |S_b| satisfies |S_b| · k < 2|T| for all k and T, which implies every prefix of σ is an EJR committee.

    The number of voters in S_b can only be 0, 1, or 2. If |S_b| = 0, then 0 · k = 0 < 2|T|. If |S_b| = 1, then |S_b| · k = k < 2|T| by Fact A. If |S_b| = 2, then both voters are in S_b, so k < |T| by Fact B, which gives 2k < 2|T|. By the equivalence ejr_chain_iff_level_supporters, this inequality for all committee sizes k and cohesive sets T guarantees that every prefix committee satisfies extended justified representation.

    lines 533–559

    uses Finset.eq_empty_or_nonempty, Finset.card_empty, Finset.eq_univ_of_card, ejr_chain_iff_level_supporters

      rcases Nat.lt_or_ge Sb.card 2 with h2 | h2
      · rcases Finset.eq_empty_or_nonempty Sb with he | hne
        · rw [he, Finset.card_empty, Nat.zero_mul]
          omega
        · obtain ⟨i, hi⟩ := hne
          have hAk := hfactA i hi
          have hone : Sb.card = 1 := by
            have := Finset.card_pos.mpr ⟨i, hi⟩
            omega
          rw [hone, Nat.one_mul]
          omega
      · have huniv : Sb = Finset.univ := by
          apply Finset.eq_univ_of_card
          have h := Finset.card_le_univ Sb
          have hc2 : Fintype.card (Fin 2) = 2 := Fintype.card_fin 2
          omega
        have h0 : (0 : Fin 2) ∈ Sb := by rw [huniv]; exact Finset.mem_univ _
        have h1 : (1 : Fin 2) ∈ Sb := by rw [huniv]; exact Finset.mem_univ _
        have hkℓ := hfactB h0 h1
        have hSbc : Sb.card = 2 := by rw [huniv]; simp
        rw [hSbc]
        omega
    
    /-- The chain target holds for every profile with exactly two voters (verified by kernel decision for all profiles with m ≤ 4, and by exhaustive search for m ≤ 5; a general proof is not known). -/
    theorem ejr_chain_two_voters {m : ℕ} (A : Fin 2 → Finset (Fin m)) :
        ∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m →
          is_ejr_committee A k (Finset.univ.filter fun c => (σ c : ℕ) < k) := (ejr_chain_iff_level_supporters A).mpr (ejr_chain_two_voters_level_supporters A)
Fin.card_Iio
The number of elements in Fin n strictly less than b is b as a natural number.
min_eq_left
If a ≤ b, then min(a, b) = a.
le_of_lt
If a < b, then a ≤ b.
Finset.card_univ
The cardinality of the universal finset of a finite type is the cardinality of that type.
Fintype.card_fin
The cardinality of Fin n is n.
min_eq_right
If b ≤ a, then min(a, b) = b.
Finset.card_map
Mapping a finset under an embedding preserves its cardinality.
le_antisymm
If a ≤ b and b ≤ a, then a = b.
Finset.card_union_of_disjoint
The cardinality of the union of two disjoint finsets is the sum of their cardinalities.
ejr_chain_two_voters_filter_mem_and
Filtering the universe for x ∈ s ∧ p(x) has the same cardinality as filtering s directly by p.
Finset.disjoint_left
Two finsets are disjoint if and only if no element of the first belongs to the second.
ejr_chain_two_voters_card_fin_filter_lt
The number of elements in Fin a strictly less than i is min(i, a).
Finset.card_image_of_injective
The image of a finset under an injective map has the same cardinality as the finset.
Subtype.ext
Two subtype elements are equal if their underlying values are equal.
Finset.card_lt_card
A strict subset of a finset has strictly smaller cardinality.
Equiv.ofBijective
A bijective function between types can be promoted to an equivalence.
lt_trichotomy
For any two elements in a linear order, exactly one of a < b, a = b, or b < a holds.
Equiv.ofBijective_apply
Applying the equivalence built from a bijection yields the value of the underlying function.
Finset.mem_inter
An element belongs to the intersection of two finsets if and only if it belongs to both.
Finset.mem_sdiff
An element belongs to the set difference s \ t if and only if it belongs to s and not to t.
Finset.equivFin
Any finite set s is in bijection with Fin |s|.
Fin.ext
Two elements of Fin n are equal if their natural number coercions are equal.
ejr_chain_two_voters_perm_of_rank
Every injective ranking function r : Fin m → ℕ induces an order-isomorphic permutation whose values count elements with smaller rank.
Finset.card_le_card
If one finset is a subset of another, its cardinality is at most the other's cardinality.
ejr_chain_two_voters_block_card
Under a bijection e : s ≃ Fin |s|, the number of elements in s with index at most j is min(j+1, |s|).
ejr_chain_two_voters_filter_or_card
For disjoint finsets s and t, the number of elements satisfying (x ∈ s ∧ p(x)) ∨ (x ∈ t ∧ q(x)) is |s.filter p| + |t.filter q|.
ejr_chain_two_voters_perm_exists
There exists a permutation placing A 0 ∩ A 1 first and satisfying the 2-density condition σ(c) + 1 ≤ 2 · |{d ∈ A i | σ(d) ≤ σ(c)}| for all c ∈ A i.
ejr_chain_two_voters_prefix_card
Any prefix of size k ≤ m under a permutation of Fin m has cardinality k.
Finset.eq_of_subset_of_card_le
If s ⊆ t and |t| ≤ |s|, then s = t.
Finset.exists_min_image
Every nonempty finset contains an element minimizing a given function to a linear order.
Finset.card_union_le
The cardinality of the union of two finsets is at most the sum of their cardinalities.
Finset.card_singleton
A singleton finset has cardinality 1.
le_min
If c ≤ a and c ≤ b, then c ≤ min(a, b).
le_trans
If a ≤ b and b ≤ c, then a ≤ c.
Finset.inter_subset_left
The intersection s₁ ∩ s₂ is a subset of s₁.
Finset.eq_empty_or_nonempty
Every finset is either empty or nonempty.
Finset.card_empty
The empty finset has cardinality 0.
Finset.eq_univ_of_card
A subset of a finite type whose cardinality equals the type's cardinality is the universal set.
ejr_chain_iff_level_supporters
A candidate ordering gives an EJR committee prefix chain if and only if for every committee size k ≤ m and nonempty candidate subset T, the number of underrepresented voters |S_b| satisfies |S_b| · k < |T| · n.

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

Lean’s trace was cut to the first 400 of 573 tactics.

private lemma ejr_chain_two_voters_card_fin_filter_lt {a i : ℕ} :    (Finset.univ.filter fun j : Fin a => (j : ℕ) < i).card = min i a := by  rcases Nat.lt_or_ge i a with h | h  · have h1 : (Finset.univ.filter fun j : Fin a => (j : ℕ) < i) = Finset.Iio (⟨i, h⟩ : Fin a) := by      ext j; simp [Finset.mem_Iio, Fin.lt_def]    rw [h1, Fin.card_Iio, min_eq_left (le_of_lt h)]  · have h1 : (Finset.univ.filter fun j : Fin a => (j : ℕ) < i) = Finset.univ := by      ext j; simp only [Finset.mem_filter, Finset.mem_univ, true_and, iff_true]      have := j.isLt; omega    rw [h1, Finset.card_univ, Fintype.card_fin, min_eq_right h]private lemma ejr_chain_two_voters_prefix_card {m k : ℕ} (hk : k ≤ m) (σ : Equiv.Perm (Fin m)) :    (Finset.univ.filter fun c => (σ c : ℕ) < k).card = k := by  rcases Nat.lt_or_ge k m with h | h  · have h1 : (Finset.univ.filter fun c : Fin m => (σ c : ℕ) < k)        = Finset.map (σ.symm.toEmbedding) (Finset.Iio (⟨k, h⟩ : Fin m)) := by      ext c      simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_map,        Equiv.coe_toEmbedding, Finset.mem_Iio, Fin.lt_def]      constructor      · intro hc        exact ⟨σ c, hc, σ.symm_apply_apply c⟩      · rintro ⟨i, hi, rfl⟩        simp only [Equiv.apply_symm_apply]        exact hi    rw [h1, Finset.card_map]    simp  · have hkm : k = m := le_antisymm hk h    have h2 : (Finset.univ.filter fun c : Fin m => (σ c : ℕ) < k) = Finset.univ := by      ext c      simp only [Finset.mem_filter, Finset.mem_univ, true_and, iff_true]      rw [hkm]; exact (σ c).isLt    rw [h2, Finset.card_univ, Fintype.card_fin, hkm]private lemma ejr_chain_two_voters_filter_mem_and {α : Type*} [Fintype α] [DecidableEq α]    (s : Finset α) (p : α → Prop) [DecidablePred p] :    (Finset.univ.filter fun x => x ∈ s ∧ p x).card = (s.filter p).card := by  congr 1  ext x  simpprivate lemma ejr_chain_two_voters_filter_or_card {α : Type*} [Fintype α] [DecidableEq α]    (s t : Finset α) (p q : α → Prop) [DecidablePred p] [DecidablePred q] (h : Disjoint s t) :    (Finset.univ.filter fun x => (x ∈ s ∧ p x) ∨ (x ∈ t ∧ q x)).card      = (s.filter p).card + (t.filter q).card := by  have h1 : (Finset.univ.filter fun x => (x ∈ s ∧ p x) ∨ (x ∈ t ∧ q x))      = (Finset.univ.filter fun x => x ∈ s ∧ p x) ∪ (Finset.univ.filter fun x => x ∈ t ∧ q x) := by    ext x; simp  rw [h1, Finset.card_union_of_disjoint]  · rw [ejr_chain_two_voters_filter_mem_and, ejr_chain_two_voters_filter_mem_and]  · rw [Finset.disjoint_left]    intro x hx hx'    simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx hx'    exact (Finset.disjoint_left.mp h hx.1 hx'.1)private lemma ejr_chain_two_voters_block_card {α : Type*} [Fintype α] [DecidableEq α]    (s : Finset α) (e : ↥s ≃ Fin s.card) (kf : α → ℕ)    (hk : kf = fun x => if h : x ∈ s then (e ⟨x, h⟩ : ℕ) else 0) (j : ℕ) :    (Finset.univ.filter fun x => x ∈ s ∧ kf x ≤ j).card = min (j + 1) s.card := by  rw [hk]  have himg : (Finset.univ.filter fun x => x ∈ s ∧ (if h : x ∈ s then (e ⟨x, h⟩ : ℕ) else 0) ≤ j)      = Finset.image (fun k : Fin s.card => ((e.symm k : ↥s) : α))          (Finset.univ.filter fun k : Fin s.card => (k : ℕ) < j + 1) := by    ext x    constructor    · intro hx      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hx      obtain ⟨hxs, hkx⟩ := hx      refine Finset.mem_image.mpr ⟨e ⟨x, hxs⟩, ?_, ?_⟩      · simp only [Finset.mem_filter, Finset.mem_univ, true_and]        rw [dif_pos hxs] at hkx; omega      · simp    · intro hx      obtain ⟨k, hkm, rfl⟩ := Finset.mem_image.mp hx      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hkm ⊢      refine ⟨(e.symm k).2, ?_⟩      rw [dif_pos (e.symm k).2]      have h1 : (⟨↑(e.symm k), (e.symm k).2⟩ : ↥s) = e.symm k := rfl      rw [h1, Equiv.apply_symm_apply]      omega  rw [himg, Finset.card_image_of_injective]  · exact ejr_chain_two_voters_card_fin_filter_lt  · intro k1 k2 h    exact e.symm.injective (Subtype.ext h)private lemma ejr_chain_two_voters_perm_of_rank {m : ℕ} (r : Fin m → ℕ) (hr : Function.Injective r) :    ∃ σ : Equiv.Perm (Fin m), (∀ a b, r a < r b ↔ σ a < σ b) ∧      (∀ a, (σ a : ℕ) = (Finset.univ.filter fun b => r b < r a).card) := by  have key : ∀ a : Fin m, (Finset.univ.filter fun b : Fin m => r b < r a).card < m := by    intro a    have hne : (Finset.univ.filter fun b : Fin m => r b < r a) ≠ Finset.univ := by      intro h      have h2 : a ∈ Finset.univ.filter (fun b : Fin m => r b < r a) := by        rw [h]; exact Finset.mem_univ a      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at h2      exact lt_irrefl _ h2    have := Finset.card_lt_card (Finset.ssubset_iff_subset_ne.mpr ⟨Finset.filter_subset _ _, hne⟩)    simpa using this  set f : Fin m → Fin m := fun a => ⟨(Finset.univ.filter fun b => r b < r a).card, key a⟩ with hf  have hmono : ∀ a b : Fin m, r a < r b →      (Finset.univ.filter fun d => r d < r a).card < (Finset.univ.filter fun d => r d < r b).card := by    intro a b hab    have hne : (Finset.univ.filter fun d : Fin m => r d < r a) ≠        (Finset.univ.filter fun d : Fin m => r d < r b) := by      intro h      have h2 : a ∈ Finset.univ.filter (fun d : Fin m => r d < r b) := by        simp only [Finset.mem_filter, Finset.mem_univ, true_and]; exact hab      rw [← h] at h2      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at h2      exact lt_irrefl _ h2    have hss : (Finset.univ.filter fun d : Fin m => r d < r a) ⊂        (Finset.univ.filter fun d : Fin m => r d < r b) := by      refine Finset.ssubset_iff_subset_ne.mpr ⟨?_, hne⟩      intro d      simp only [Finset.mem_filter, Finset.mem_univ, true_and]      omega    exact Finset.card_lt_card hss  have hfinj : Function.Injective f := by    intro a b hab    by_contra hne    have hval : (Finset.univ.filter fun d => r d < r a).card =        (Finset.univ.filter fun d => r d < r b).card := by      simpa [hf] using hab    rcases lt_or_gt_of_ne (fun h => hne (hr h)) with h | h    · have := hmono a b h; omega    · have := hmono b a h; omega  have hfbij : Function.Bijective f := ⟨hfinj, Finite.injective_iff_surjective.mp hfinj⟩  refine ⟨Equiv.ofBijective f hfbij, ?_, ?_⟩  · intro a b    constructor    · intro h; exact hmono a b h    · intro h      have h' : f a < f b := by simpa using h      rcases lt_trichotomy (r a) (r b) with h1 | h1 | h1      · exact h1      · have h2 : a = b := hr h1        rw [h2] at h'        exact absurd h' (lt_irrefl _)      · exact absurd (hmono b a h1) (not_lt.mpr (le_of_lt h'))  · intro a    have h := Equiv.ofBijective_apply f hfbij a    have h2 : ((Equiv.ofBijective f hfbij) a : ℕ) = (f a : ℕ) := by rw [h]    rw [h2]private lemma ejr_chain_two_voters_perm_exists {m : ℕ} (A : Fin 2 → Finset (Fin m)) :    ∃ σ : Equiv.Perm (Fin m),      (∀ c ∈ A 0 ∩ A 1, ∀ d, d ∉ A 0 ∩ A 1 → (σ c : ℕ) < (σ d : ℕ)) ∧      (∀ (i : Fin 2) (c : Fin m), c ∈ A i →        (σ c : ℕ) + 1 ≤ 2 * (Finset.univ.filter fun d => d ∈ A i ∧ (σ d : ℕ) ≤ (σ c : ℕ)).card) := by  classical  set C := A 0 ∩ A 1 with hC  set R0 := A 0 \ A 1 with hR0  set R1 := A 1 \ A 0 with hR1  set N := Finset.univ \ (A 0 ∪ A 1) with hN  have hCin : ∀ x : Fin m, x ∈ C ↔ x ∈ A 0 ∧ x ∈ A 1 := by    intro x; rw [hC]; exact Finset.mem_inter  have hR0in : ∀ x : Fin m, x ∈ R0 ↔ x ∈ A 0 ∧ x ∉ A 1 := by    intro x; rw [hR0]; exact Finset.mem_sdiff  have hR1in : ∀ x : Fin m, x ∈ R1 ↔ x ∈ A 1 ∧ x ∉ A 0 := by    intro x; rw [hR1]; exact Finset.mem_sdiff  have hcover : ∀ x : Fin m, x ∈ C ∨ x ∈ R0 ∨ x ∈ R1 ∨ x ∈ N := by    intro x    by_cases h0 : x ∈ A 0    · by_cases h1 : x ∈ A 1      · exact Or.inl ((hCin x).mpr ⟨h0, h1⟩)      · exact Or.inr (Or.inl ((hR0in x).mpr ⟨h0, h1⟩))    · by_cases h1 : x ∈ A 1      · exact Or.inr (Or.inr (Or.inl ((hR1in x).mpr ⟨h1, h0⟩)))      · refine Or.inr (Or.inr (Or.inr ?_))        rw [hN]; simp [h0, h1]  have dC0 : ∀ x, x ∈ C → x ∉ R0 := by    intro x hx h; exact ((hR0in x).mp h).2 ((hCin x).mp hx).2  have d0C : ∀ x, x ∈ R0 → x ∉ C := by    intro x hx h; exact ((hR0in x).mp hx).2 ((hCin x).mp h).2  have d1C : ∀ x, x ∈ R1 → x ∉ C := by    intro x hx h; exact ((hR1in x).mp hx).2 ((hCin x).mp h).1  have d01 : ∀ x, x ∈ R0 → x ∉ R1 := by    intro x hx h; exact ((hR1in x).mp h).2 ((hR0in x).mp hx).1  have memN : ∀ x, x ∉ C → x ∉ R0 → x ∉ R1 → x ∈ N := by    intro x h1 h2 h3    rcases hcover x with h | h | h | h    · exact absurd h h1    · exact absurd h h2    · exact absurd h h3    · exact h  set kC : Fin m → ℕ := fun x => if h : x ∈ C then ((Finset.equivFin C ⟨x, h⟩ : Fin C.card) : ℕ) else 0 with hkC  set k0 : Fin m → ℕ := fun x => if h : x ∈ R0 then ((Finset.equivFin R0 ⟨x, h⟩ : Fin R0.card) : ℕ) else 0 with hk0  set k1 : Fin m → ℕ := fun x => if h : x ∈ R1 then ((Finset.equivFin R1 ⟨x, h⟩ : Fin R1.card) : ℕ) else 0 with hk1  set kN : Fin m → ℕ := fun x => if h : x ∈ N then ((Finset.equivFin N ⟨x, h⟩ : Fin N.card) : ℕ) else 0 with hkN  set r : Fin m → ℕ := fun x =>    if x ∈ C then kC x    else if x ∈ R0 then C.card + 2 * k0 x    else if x ∈ R1 then C.card + 2 * k1 x + 1    else C.card + 2 * R0.card + 2 * R1.card + kN x with hr  have rC : ∀ x, x ∈ C → r x = kC x := by    intro x h; rw [hr]; simp only [if_pos h]  have rR0 : ∀ x, x ∉ C → x ∈ R0 → r x = C.card + 2 * k0 x := by    intro x h h0; rw [hr]; simp only [if_neg h, if_pos h0]  have rR1 : ∀ x, x ∉ C → x ∉ R0 → x ∈ R1 → r x = C.card + 2 * k1 x + 1 := by    intro x h h0 h1; rw [hr]; simp only [if_neg h, if_neg h0, if_pos h1]  have rN : ∀ x, x ∉ C → x ∉ R0 → x ∉ R1 → x ∈ N →      r x = C.card + 2 * R0.card + 2 * R1.card + kN x := by    intro x h h0 h1 hN'; rw [hr]; simp only [if_neg h, if_neg h0, if_neg h1]  have kC_lt : ∀ x, x ∈ C → kC x < C.card := by    intro x h; rw [hkC]; simp only [dif_pos h]; exact Fin.isLt _  have k0_lt : ∀ x, x ∈ R0 → k0 x < R0.card := by    intro x h; rw [hk0]; simp only [dif_pos h]; exact Fin.isLt _  have k1_lt : ∀ x, x ∈ R1 → k1 x < R1.card := by    intro x h; rw [hk1]; simp only [dif_pos h]; exact Fin.isLt _  have kC_inj : ∀ x, x ∈ C → ∀ y, y ∈ C → kC x = kC y → x = y := by    intro x hx y hy h    rw [hkC] at h    simp only [dif_pos hx, dif_pos hy] at h    have h1 : (⟨x, hx⟩ : ↥C) = ⟨y, hy⟩ := (Finset.equivFin C).injective (Fin.ext h)    exact Subtype.ext_iff.mp h1  have k0_inj : ∀ x, x ∈ R0 → ∀ y, y ∈ R0 → k0 x = k0 y → x = y := by    intro x hx y hy h    rw [hk0] at h    simp only [dif_pos hx, dif_pos hy] at h    have h1 : (⟨x, hx⟩ : ↥R0) = ⟨y, hy⟩ := (Finset.equivFin R0).injective (Fin.ext h)    exact Subtype.ext_iff.mp h1  have k1_inj : ∀ x, x ∈ R1 → ∀ y, y ∈ R1 → k1 x = k1 y → x = y := by    intro x hx y hy h    rw [hk1] at h    simp only [dif_pos hx, dif_pos hy] at h    have h1 : (⟨x, hx⟩ : ↥R1) = ⟨y, hy⟩ := (Finset.equivFin R1).injective (Fin.ext h)    exact Subtype.ext_iff.mp h1  have kN_inj : ∀ x, x ∈ N → ∀ y, y ∈ N → kN x = kN y → x = y := by    intro x hx y hy h    rw [hkN] at h    simp only [dif_pos hx, dif_pos hy] at h    have h1 : (⟨x, hx⟩ : ↥N) = ⟨y, hy⟩ := (Finset.equivFin N).injective (Fin.ext h)    exact Subtype.ext_iff.mp h1  have hrinj : Function.Injective r := by    intro x y hxy    by_cases hxC : x ∈ C    · have hxlt := kC_lt x hxC      rw [rC x hxC] at hxy      by_cases hyC : y ∈ C      · rw [rC y hyC] at hxy; exact kC_inj x hxC y hyC hxy      · by_cases hy0 : y ∈ R0        · rw [rR0 y hyC hy0] at hxy; omega        · by_cases hy1 : y ∈ R1          · rw [rR1 y hyC hy0 hy1] at hxy; omega          · rw [rN y hyC hy0 hy1 (memN y hyC hy0 hy1)] at hxy; omega    · by_cases hx0 : x ∈ R0      · have hxlt := k0_lt x hx0        rw [rR0 x hxC hx0] at hxy        by_cases hyC : y ∈ C        · rw [rC y hyC] at hxy; have := kC_lt y hyC; omega        · by_cases hy0 : y ∈ R0          · rw [rR0 y hyC hy0] at hxy            have hh : k0 x = k0 y := by omega            exact k0_inj x hx0 y hy0 hh          · by_cases hy1 : y ∈ R1            · rw [rR1 y hyC hy0 hy1] at hxy; omega            · rw [rN y hyC hy0 hy1 (memN y hyC hy0 hy1)] at hxy              have := k0_lt x hx0; omega      · by_cases hx1 : x ∈ R1        · have hxlt := k1_lt x hx1          rw [rR1 x hxC hx0 hx1] at hxy          by_cases hyC : y ∈ C          · rw [rC y hyC] at hxy; have := kC_lt y hyC; omega          · by_cases hy0 : y ∈ R0            · rw [rR0 y hyC hy0] at hxy; omega            · by_cases hy1 : y ∈ R1              · rw [rR1 y hyC hy0 hy1] at hxy                have hh : k1 x = k1 y := by omega                exact k1_inj x hx1 y hy1 hh              · rw [rN y hyC hy0 hy1 (memN y hyC hy0 hy1)] at hxy                have := k1_lt x hx1; omega        · have hxN := memN x hxC hx0 hx1          rw [rN x hxC hx0 hx1 hxN] at hxy          by_cases hyC : y ∈ C          · rw [rC y hyC] at hxy; have := kC_lt y hyC; omega          · by_cases hy0 : y ∈ R0            · rw [rR0 y hyC hy0] at hxy; have := k0_lt y hy0; omega            · by_cases hy1 : y ∈ R1              · rw [rR1 y hyC hy0 hy1] at hxy; have := k1_lt y hy1; omega              · rw [rN y hyC hy0 hy1 (memN y hyC hy0 hy1)] at hxy                have hh : kN x = kN y := by omega                exact kN_inj x hxN y (memN y hyC hy0 hy1) hh  obtain ⟨σ, hσlt, hσpos⟩ := ejr_chain_two_voters_perm_of_rank r hrinj  refine ⟨σ, ?_, ?_⟩  · intro c hc d hd    have hcc : c ∈ C := hc    have hdd : d ∉ C := hd    have hrd : C.card ≤ r d := by      by_cases hd0 : d ∈ R0      · rw [rR0 d hdd hd0]; omega      · by_cases hd1 : d ∈ R1        · rw [rR1 d hdd hd0 hd1]; omega        · rw [rN d hdd hd0 hd1 (memN d hdd hd0 hd1)]; omega    have hlt : r c < r d := by      rw [rC c hcc]      have := kC_lt c hcc      omega    exact Fin.lt_def.mp ((hσlt c d).mp hlt)  · intro i c hc    have hσle : (σ c : ℕ) ≤ r c := by      rw [hσpos c]      have himg : (Finset.univ.filter fun d : Fin m => r d < r c).image r ⊆ Finset.range (r c) := by        intro x hx        obtain ⟨d, hd, rfl⟩ := Finset.mem_image.mp hx        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hd        exact Finset.mem_range.mpr hd      have h1 : (Finset.univ.filter fun d : Fin m => r d < r c).card          = ((Finset.univ.filter fun d : Fin m => r d < r c).image r).card := by        rw [Finset.card_image_of_injective _ hrinj]      rw [h1]      simpa using Finset.card_le_card himg    have hiff : ∀ d : Fin m, ((σ d : ℕ) ≤ (σ c : ℕ)) ↔ (r d ≤ r c) := by      intro d      have h1 : ((σ d : ℕ) ≤ (σ c : ℕ)) ↔ (σ d ≤ σ c) := Fin.le_def.symm      rw [h1]      constructor      · intro h        rcases lt_or_eq_of_le h with h' | h'        · exact le_of_lt ((hσlt d c).mpr h')        · have hdc : d = c := σ.injective h'          rw [hdc]      · intro h        rcases lt_or_eq_of_le h with h' | h'        · exact le_of_lt (Fin.lt_def.mp ((hσlt d c).mp h'))        · have hdc : d = c := hrinj h'          rw [hdc]    have hfilter : ∀ j : Fin 2, (Finset.univ.filter fun d => d ∈ A j ∧ (σ d : ℕ) ≤ (σ c : ℕ))        = (Finset.univ.filter fun d => d ∈ A j ∧ r d ≤ r c) := by      intro j      apply Finset.filter_congr      intro d _      exact ⟨fun h => ⟨h.1, (hiff d).mp h.2⟩, fun h => ⟨h.1, (hiff d).mpr h.2⟩⟩    have hCcase : ∀ (j : Fin 2), c ∈ C → c ∈ A j →        (σ c : ℕ) + 1 ≤ 2 * (Finset.univ.filter fun d => d ∈ A j ∧ r d ≤ r c).card := by      intro j hcc hcj      have hmem : ∀ d, d ∈ C → d ∈ A j := by        intro d hd        fin_cases j        · exact ((hCin d).mp hd).1        · exact ((hCin d).mp hd).2      have hsub : (Finset.univ.filter fun d => d ∈ C ∧ kC d ≤ kC c) ⊆          (Finset.univ.filter fun d => d ∈ A j ∧ r d ≤ r c) := by        intro d hd        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hd ⊢        exact ⟨hmem d hd.1, by rw [rC d hd.1, rC c hcc]; exact hd.2⟩      have hcard : (Finset.univ.filter fun d => d ∈ C ∧ kC d ≤ kC c).card = kC c + 1 := by        rw [ejr_chain_two_voters_block_card C (Finset.equivFin C) kC hkC (kC c),          min_eq_left (by have := kC_lt c hcc; omega)]      have hlb : kC c + 1 ≤ (Finset.univ.filter fun d => d ∈ A j ∧ r d ≤ r c).card := by        rw [← hcard]; exact Finset.card_le_card hsub      have hrc : r c = kC c := rC c hcc      omega    have hi01 : i = 0 ∨ i = 1 := by fin_cases i <;> simp    by_cases hcc : c ∈ C    · rw [hfilter i]; exact hCcase i hcc hc    · rcases hi01 with h | h      · rw [h] at hc ⊢        rw [hfilter 0]        have hc0 : c ∈ R0 := (hR0in c).mpr ⟨hc, fun h1 => hcc ((hCin c).mpr ⟨hc, h1⟩)⟩        have hrc : r c = C.card + 2 * k0 c := rR0 c hcc hc0        have hdisj : Disjoint C R0 := Finset.disjoint_left.mpr (fun x hx hy => dC0 x hx hy)        have hcardU : (Finset.univ.filter fun d => (d ∈ C) ∨ (d ∈ R0 ∧ k0 d ≤ k0 c)).card            = C.card + (k0 c + 1) := by          have h2 := ejr_chain_two_voters_filter_or_card C R0 (fun _ => True)            (fun d => k0 d ≤ k0 c) hdisj          rw [show (Finset.univ.filter fun d => (d ∈ C ∧ True) ∨ (d ∈ R0 ∧ k0 d ≤ k0 c))                = (Finset.univ.filter fun d => (d ∈ C) ∨ (d ∈ R0 ∧ k0 d ≤ k0 c)) from by              congr 1; ext d; simp] at h2          rw [h2, Finset.filter_true_of_mem (s := C) (p := fun _ => True) (fun x _ => trivial),              ← ejr_chain_two_voters_filter_mem_and R0 (fun d => k0 d ≤ k0 c),              ejr_chain_two_voters_block_card R0 (Finset.equivFin R0) k0 hk0 (k0 c),              min_eq_left (show k0 c + 1 ≤ R0.card by have := k0_lt c hc0; omega)]        have hsub : (Finset.univ.filter fun d => (d ∈ C) ∨ (d ∈ R0 ∧ k0 d ≤ k0 c))            ⊆ (Finset.univ.filter fun d => d ∈ A 0 ∧ r d ≤ r c) := by          intro d hd          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hd ⊢          rcases hd with hd | hd          · refine ⟨((hCin d).mp hd).1, ?_⟩            rw [rC d hd, hrc]            have := kC_lt d hd; omega          · refine ⟨((hR0in d).mp hd.1).1, ?_⟩            rw [rR0 d (d0C d hd.1) hd.1, hrc]            have := hd.2; omega        have hlb : C.card + (k0 c + 1)            ≤ (Finset.univ.filter fun d => d ∈ A 0 ∧ r d ≤ r c).card := by          rw [← hcardU]; exact Finset.card_le_card hsub        omega      · rw [h] at hc ⊢        rw [hfilter 1]        have hc1 : c ∈ R1 := (hR1in c).mpr ⟨hc, fun h1 => hcc ((hCin c).mpr ⟨h1, hc⟩)⟩        have hc1' : c ∉ R0 := fun hh => d01 c hh hc1        have hrc : r c = C.card + 2 * k1 c + 1 := rR1 c hcc hc1' hc1        have hdisj : Disjoint C R1 := Finset.disjoint_left.mpr (fun x hx hy => d1C x hy hx)        have hcardU : (Finset.univ.filter fun d => (d ∈ C) ∨ (d ∈ R1 ∧ k1 d ≤ k1 c)).card            = C.card + (k1 c + 1) := by          have h2 := ejr_chain_two_voters_filter_or_card C R1 (fun _ => True)            (fun d => k1 d ≤ k1 c) hdisj          rw [show (Finset.univ.filter fun d => (d ∈ C ∧ True) ∨ (d ∈ R1 ∧ k1 d ≤ k1 c))                = (Finset.univ.filter fun d => (d ∈ C) ∨ (d ∈ R1 ∧ k1 d ≤ k1 c)) from by              congr 1; ext d; simp] at h2          rw [h2, Finset.filter_true_of_mem (s := C) (p := fun _ => True) (fun x _ => trivial),              ← ejr_chain_two_voters_filter_mem_and R1 (fun d => k1 d ≤ k1 c),              ejr_chain_two_voters_block_card R1 (Finset.equivFin R1) k1 hk1 (k1 c),              min_eq_left (show k1 c + 1 ≤ R1.card by have := k1_lt c hc1; omega)]        have hsub : (Finset.univ.filter fun d => (d ∈ C) ∨ (d ∈ R1 ∧ k1 d ≤ k1 c))            ⊆ (Finset.univ.filter fun d => d ∈ A 1 ∧ r d ≤ r c) := by          intro d hd          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hd ⊢          rcases hd with hd | hd          · refine ⟨((hCin d).mp hd).2, ?_⟩            rw [rC d hd, hrc]            have := kC_lt d hd; omega          · refine ⟨((hR1in d).mp hd.1).1, ?_⟩            rw [rR1 d (d1C d hd.1) (fun hh => d01 d hh hd.1) hd.1, hrc]            have := hd.2; omega        have hlb : C.card + (k1 c + 1)            ≤ (Finset.univ.filter fun d => d ∈ A 1 ∧ r d ≤ r c).card := by          rw [← hcardU]; exact Finset.card_le_card hsub        omegaprivate lemma ejr_chain_two_voters_level_supporters {m : ℕ} (A : Fin 2 → Finset (Fin m)) :    ∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m → ∀ T : Finset (Fin m), T.Nonempty →      (Finset.univ.filter fun i => T ⊆ A i ∧        (A i ∩ Finset.univ.filter fun c => (σ c : ℕ) < k).card < T.card).card * k      < T.card * 2 := by  classical  obtain ⟨σ, hseg, hspread⟩ := ejr_chain_two_voters_perm_exists A  refine ⟨σ, ?_⟩  have hcard : ∀ k ≤ m, (Finset.univ.filter fun c => (σ c : ℕ) < k).card = k :=    fun k hk => ejr_chain_two_voters_prefix_card hk σ  have hCeq : A 0 ∩ A 1 = Finset.univ.filter (fun c => (σ c : ℕ) < (A 0 ∩ A 1).card) := by    set C := A 0 ∩ A 1 with hCdef    have hCm : C.card ≤ m := by      have h := Finset.card_le_univ C      simpa using h    have hsub : C ⊆ Finset.univ.filter (fun c => (σ c : ℕ) < C.card) := by      intro c hc      simp only [Finset.mem_filter, Finset.mem_univ, true_and]      by_contra hge      simp only [not_lt] at hge      have hScard : (Finset.univ.filter (fun d => (σ d : ℕ) < (σ c : ℕ))).card = (σ c : ℕ) :=        hcard (σ c) (le_of_lt (σ c).isLt)      have hSC : (Finset.univ.filter (fun d => (σ d : ℕ) < (σ c : ℕ))) ⊆ C := by        intro d hd        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hd        by_contra hdC        have := hseg c hc d hdC        omega      have hne : (Finset.univ.filter (fun d => (σ d : ℕ) < (σ c : ℕ))) ≠ C := by        intro h        have hmem : c ∈ Finset.univ.filter (fun d => (σ d : ℕ) < (σ c : ℕ)) := h ▸ hc        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hmem        omega      have hlt : (Finset.univ.filter (fun d => (σ d : ℕ) < (σ c : ℕ))).card < C.card :=        Finset.card_lt_card (Finset.ssubset_iff_subset_ne.mpr ⟨hSC, hne⟩)      omega    refine Finset.eq_of_subset_of_card_le hsub ?_    rw [hcard C.card hCm]  have hCinter : ∀ k ≤ m, ((A 0 ∩ A 1) ∩ Finset.univ.filter (fun c => (σ c : ℕ) < k)).card      = min k (A 0 ∩ A 1).card := by    intro k hk    rcases Nat.le_total k (A 0 ∩ A 1).card with h | h    · have hsub : (Finset.univ.filter fun c => (σ c : ℕ) < k) ⊆ (A 0 ∩ A 1) := by        rw [hCeq]        intro c hc        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hc ⊢        omega      rw [Finset.inter_eq_right.mpr hsub, hcard k hk, min_eq_left h]    · have hsub : (A 0 ∩ A 1) ⊆ (Finset.univ.filter fun c => (σ c : ℕ) < k) := by        rw [hCeq]        intro c hc        simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hc ⊢        omega      rw [Finset.inter_eq_left.mpr hsub, min_eq_right h]  intro k hk T hT  set W := Finset.univ.filter (fun c => (σ c : ℕ) < k) with hW  set Sb := Finset.univ.filter (fun i : Fin 2 => T ⊆ A i ∧ (A i ∩ W).card < T.card) with hSb  have hℓ : 0 < T.card := Finset.card_pos.mpr hT  have hSb2 : Sb.card ≤ 2 := by    have h := Finset.card_le_univ Sb    simpa using h  have hfactA : ∀ i : Fin 2, i ∈ Sb → k < 2 * T.card := by    intro i hi    rw [hSb, Finset.mem_filter] at hi    obtain ⟨-, hiT, hicard⟩ := hi    have hEne : (A i \ W).Nonempty := by      rw [← Finset.card_pos, Finset.card_sdiff, Finset.inter_comm]      have h1 : T.card ≤ (A i).card := Finset.card_le_card hiT      omega    obtain ⟨c, hcE, hcmin⟩ := Finset.exists_min_image (A i \ W) (fun d => (σ d : ℕ)) hEne    rw [Finset.mem_sdiff] at hcE    obtain ⟨hcA, hcW⟩ := hcE    have hck : k ≤ (σ c : ℕ) := by      rw [hW] at hcW      simp only [Finset.mem_filter, Finset.mem_univ, true_and, not_lt] at hcW      exact hcW    have hsub : (Finset.univ.filter fun d => d ∈ A i ∧ (σ d : ℕ) ≤ (σ c : ℕ))        ⊆ (A i ∩ W) ∪ {c} := by      intro d hd      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hd      obtain ⟨hdA, hdle⟩ := hd      by_cases hdW : d ∈ W      · exact Finset.mem_union_left _ (Finset.mem_inter.mpr ⟨hdA, hdW⟩)      · have hdE : d ∈ A i \ W := Finset.mem_sdiff.mpr ⟨hdA, hdW⟩        have h1 : (σ c : ℕ) ≤ (σ d : ℕ) := hcmin d hdE        have h2 : (σ d : ℕ) = (σ c : ℕ) := le_antisymm hdle h1        have h3 : d = c := σ.injective (Fin.ext h2)        rw [h3]        exact Finset.mem_union_right _ (Finset.mem_singleton_self c)    have hcardle : (Finset.univ.filter fun d => d ∈ A i ∧ (σ d : ℕ) ≤ (σ c : ℕ)).card        ≤ (A i ∩ W).card + 1 := by      calc (Finset.univ.filter fun d => d ∈ A i ∧ (σ d : ℕ) ≤ (σ c : ℕ)).card          ≤ ((A i ∩ W) ∪ {c}).card := Finset.card_le_card hsub        _ ≤ (A i ∩ W).card + ({c} : Finset (Fin m)).card := Finset.card_union_le _ _        _ = (A i ∩ W).card + 1 := by rw [Finset.card_singleton]    have hsp := hspread i c hcA    omega  have hfactB : (0 : Fin 2) ∈ Sb → (1 : Fin 2) ∈ Sb → k < T.card := by    intro h0 h1    rw [hSb, Finset.mem_filter] at h0 h1    obtain ⟨-, hT0, hc0⟩ := h0    obtain ⟨-, hT1, hc1⟩ := h1    by_contra hcon    simp only [not_lt] at hcon    have hTC : T ⊆ A 0 ∩ A 1 := fun c hc => Finset.mem_inter.mpr ⟨hT0 hc, hT1 hc⟩    have hCle : T.card ≤ (A 0 ∩ A 1).card := Finset.card_le_card hTC    have h2 := hCinter k hk    have hge : T.card ≤ (A 0 ∩ W).card := by      have h3 : T.card ≤ ((A 0 ∩ A 1) ∩ W).card := by        rw [h2]; exact le_min hcon hCle      exact le_trans h3 (Finset.card_le_card (Finset.inter_subset_inter_right Finset.inter_subset_left))    omega  rcases Nat.lt_or_ge Sb.card 2 with h2 | h2  · rcases Finset.eq_empty_or_nonempty Sb with he | hne    · rw [he, Finset.card_empty, Nat.zero_mul]      omega    · obtain ⟨i, hi⟩ := hne      have hAk := hfactA i hi      have hone : Sb.card = 1 := by        have := Finset.card_pos.mpr ⟨i, hi⟩        omega      rw [hone, Nat.one_mul]      omega  · have huniv : Sb = Finset.univ := by      apply Finset.eq_univ_of_card      have h := Finset.card_le_univ Sb      have hc2 : Fintype.card (Fin 2) = 2 := Fintype.card_fin 2      omega    have h0 : (0 : Fin 2) ∈ Sb := by rw [huniv]; exact Finset.mem_univ _    have h1 : (1 : Fin 2) ∈ Sb := by rw [huniv]; exact Finset.mem_univ _    have hkℓ := hfactB h0 h1    have hSbc : Sb.card = 2 := by rw [huniv]; simp    rw [hSbc]    omega/-- The chain target holds for every profile with exactly two voters (verified by kernel decision for all profiles with m ≤ 4, and by exhaustive search for m ≤ 5; a general proof is not known). -/theorem ejr_chain_two_voters {m : ℕ} (A : Fin 2 → Finset (Fin m)) :    ∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m →      is_ejr_committee A k (Finset.univ.filter fun c => (σ c : ℕ) < k) := (ejr_chain_iff_level_supporters A).mpr (ejr_chain_two_voters_level_supporters A)
See it in the graphDiscuss this resultChallenge it