AFTD Auto-Formalizing Theoretical Domains

ejr_chain_one_voter

theoremverified

Every approval profile with exactly one voter admits an EJR committee chain.

Statement

theorem ejr_chain_one_voter {m : ℕ} (A : Fin 1 → 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
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
  • 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| ≥ ℓ.
  • 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 ≤…
  • 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 construct an EJR committee chain for a single voter, order all candidates by placing the voter's approved candidates first, followed by the unapproved candidates. The prefix of length k in this ordering forms the committee of size k. Since there is only one voter, any cohesive group consists solely of this voter, requiring ℓ ≤ k and ℓ ≤ |A 0|. Because approved candidates are placed first, the committee of size k contains min(k, |A 0|) ≥ ℓ approved candidates, satisfying EJR.

  1. The candidate list L, formed by concatenating the voter's approved candidates A₀ with the remaining candidates B, is duplicate-free.

    Let A₀ = A 0 be the set of candidates approved by voter 0, and B = Finset.univ \ A₀ the remaining candidates. Since B consists of candidates not in A₀, their list representations are disjoint. Because finset listings are already duplicate-free, their concatenation L has no duplicates.

    lines 5–15

    uses List.disjoint_left, Finset.mem_toList.mp, Finset.mem_sdiff, Finset.mem_univ, true_and, List.Nodup.append

      let A0 := A 0
      let B := Finset.univ \ A0
      let L := A0.toList ++ B.toList
      have hdisj : (A0.toList).Disjoint (B.toList) := by
        rw [List.disjoint_left]
        intro a ha hb
        have ha' : a ∈ A0 := Finset.mem_toList.mp ha
        have hb' : a ∈ B := Finset.mem_toList.mp hb
        simp only [B, Finset.mem_sdiff, Finset.mem_univ, true_and] at hb'
        exact hb' ha'
      have hLnodup : L.Nodup := List.Nodup.append A0.nodup_toList B.nodup_toList hdisj
  2. The list L has total length m.

    The sum of the sizes of A₀ and its complement B equals the total number of candidates m. Since the length of L is the sum of the lengths of the two component lists, L has length m.

    lines 16–21

    uses Finset.card_sdiff_add_card_eq_card, Finset.subset_univ, Finset.card_univ, Fintype.card_fin, List.length_append, Finset.length_toList

      have hcardB : Finset.card B + Finset.card A0 = m := by
        have := Finset.card_sdiff_add_card_eq_card (Finset.subset_univ A0)
        simpa [B, Finset.card_univ, Fintype.card_fin] using this
      have hLlen : L.length = m := by
        simp only [L, List.length_append, Finset.length_toList]
        omega
  3. There exists a candidate permutation σ whose initial segments match the prefixes of L, reducing the goal to showing that the first k candidates of L form an EJR committee.

    Applying exists_perm_with_prefix_eq_take to the duplicate-free list L of length m yields a permutation σ such that for every k ≤ m, the set of candidates with ranking index below k is precisely the finset of the first k elements of L. Witnessing this permutation σ and fixing k ≤ m, the committee is rewritten as (L.take k).toFinset.

    lines 22–26

    uses exists_perm_with_prefix_eq_take

      obtain ⟨σ, hσ⟩ := exists_perm_with_prefix_eq_take L hLnodup hLlen
      refine ⟨σ, ?_⟩
      intro k hk
      have hW : Finset.univ.filter (fun c => (σ c : ℕ) < k) = (L.take k).toFinset := hσ k hk
      rw [hW]
  4. The committee (L.take k).toFinset has size k.

    The prefix of length k of the duplicate-free list L has no duplicates and has length min(k, m) = k. Converting a duplicate-free list of length k to a finset yields a set of cardinality k.

    lines 27–31

    uses List.take_sublist, List.length_take, min_eq_left, List.toFinset_card_of_nodup

      constructor
      · have htake_nodup : (L.take k).Nodup := (List.take_sublist k L).nodup hLnodup
        have htake_len : (L.take k).length = k := by
          rw [List.length_take, hLlen, min_eq_left hk]
        rw [List.toFinset_card_of_nodup htake_nodup, htake_len]
  5. Any EJR-cohesive group G with quota ℓ ≥ 1 is nonempty.

    Assume ℓ ≥ 1 and G is cohesive for committee size k and quota ℓ. By definition of cohesiveness, ℓ · 1 ≤ |G| · k. If G were empty, this would force ℓ ≤ 0, contradicting ℓ ≥ 1.

    lines 32–40

    uses Finset.eq_empty_or_nonempty, Finset.card_empty

      · intro ℓ hℓ G hGcoh
        obtain ⟨hGcard, hcomm⟩ := hGcoh
        have hGne : G.Nonempty := by
          rcases Finset.eq_empty_or_nonempty G with h | h
          · exfalso
            rw [h] at hGcard
            simp only [Finset.card_empty] at hGcard
            omega
          · exact h
  6. The cohesive group G has size 1, and the quota satisfies ℓ ≤ k.

    Because G is a nonempty subset of the singleton voter set Fin 1, its cardinality must be 1. Substituting |G| = 1 into the cohesiveness inequality ℓ · 1 ≤ |G| · k yields ℓ ≤ k.

    lines 41–49

    uses Finset.card_le_card, Finset.subset_univ, Finset.card_univ, Finset.card_pos.mpr

        have hGcard_le : Finset.card G ≤ 1 := by
          have := Finset.card_le_card (Finset.subset_univ G)
          simpa [Finset.card_univ] using this
        have hGpos : 0 < Finset.card G := Finset.card_pos.mpr hGne
        have hGc1 : Finset.card G = 1 := by omega
        have hℓk : ℓ ≤ k := by
          have := hGcard
          rw [hGc1] at this
          omega
  7. Voter 0 belongs to G, and the quota satisfies ℓ ≤ |A₀|.

    Since Fin 1 contains only the element 0, the unique voter in G is 0. The set of candidates unanimously approved by G is therefore contained in A₀ = A 0. Cohesiveness implies that ℓ is bounded by the size of this intersection, which by inclusion is at most |A₀|.

    lines 50–57

    uses Subsingleton.elim, Finset.mem_filter, Finset.mem_univ, true_and, le_trans, Finset.card_le_card

        obtain ⟨i, hi⟩ := hGne
        have hi0 : i = 0 := Subsingleton.elim i 0
        have h0mem : (0 : Fin 1) ∈ G := hi0 ▸ hi
        have hsub : (({c | ∀ i ∈ G, c ∈ A i}) : Finset (Fin m)) ⊆ A0 := by
          intro c hc
          simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hc
          exact hc 0 h0mem
        have hA0ge : ℓ ≤ Finset.card A0 := le_trans hcomm (Finset.card_le_card hsub)
  8. The set S of the first k elements of A₀ is a subset of A₀ ∩ (L.take k).toFinset.

    We choose voter 0 ∈ G as the voter whose representation will be guaranteed. Let S be the first k elements of A₀.toList. Every element of S belongs to A₀ by definition. Moreover, since A₀ appears first in the concatenation L, the first k elements of A₀ are contained in the first k elements of L, so S is contained in both A₀ and the committee.

    lines 58–67

    uses Finset.mem_inter, Finset.mem_toList.mp, List.mem_of_mem_take, List.mem_toFinset.mp, List.mem_toFinset, List.take_append, List.mem_append_left

        refine ⟨0, h0mem, ?_⟩
        let S := (A0.toList.take k).toFinset
        have hSsub : S ⊆ A0 ∩ (L.take k).toFinset := by
          intro c hc
          rw [Finset.mem_inter]
          constructor
          · exact Finset.mem_toList.mp (List.mem_of_mem_take (List.mem_toFinset.mp hc))
          · rw [List.mem_toFinset]
            rw [List.take_append]
            exact List.mem_append_left _ (List.mem_toFinset.mp hc)
  9. Voter 0 approves at least ℓ committee members, completing the proof of EJR.

    The size of S is min(k, |A₀|). Since ℓ ≤ k and ℓ ≤ |A₀|, we have ℓ ≤ min(k, |A₀|) = |S|. Because S is a subset of the committee members approved by voter 0, that intersection has size at least |S| ≥ ℓ.

    lines 68–74

    uses List.take_sublist, List.toFinset_card_of_nodup, List.length_take, Finset.length_toList, le_min, le_trans, Finset.card_le_card

        have hScard : Finset.card S = min k (Finset.card A0) := by
          have hnd : (A0.toList.take k).Nodup := (List.take_sublist k A0.toList).nodup A0.nodup_toList
          rw [List.toFinset_card_of_nodup hnd, List.length_take, Finset.length_toList]
        have hmin : ℓ ≤ Finset.card S := by
          rw [hScard]
          exact le_min hℓk hA0ge
        exact le_trans hmin (Finset.card_le_card hSsub)
List.disjoint_left
Two lists are disjoint if and only if no element of the first list belongs to the second.
Finset.mem_toList.mp
If an element belongs to the list of elements of a finset, then it belongs to the finset.
Finset.mem_sdiff
An element belongs to the set difference s \ t if and only if it is in s and not in t.
Finset.mem_univ
Every element of a finite type belongs to the universal finset.
true_and
The conjunction True ∧ p is equivalent to p.
List.Nodup.append
The concatenation of two duplicate-free lists is duplicate-free if the lists are disjoint.
Finset.card_sdiff_add_card_eq_card
For any subset s ⊆ t of a finset, the size of t \ s plus the size of s equals the size of t.
Finset.subset_univ
Every finset of elements of a finite type is a subset of the universal finset.
Finset.card_univ
The cardinality of the universal finset equals the cardinality of the underlying finite type.
Fintype.card_fin
The cardinality of Fin n is n.
List.length_append
The length of the concatenation of two lists is the sum of their lengths.
Finset.length_toList
The list of elements of a finset has length equal to the cardinality of the finset.
exists_perm_with_prefix_eq_take
For any duplicate-free list of length m, there exists a permutation whose first k elements coincide with the prefix of length k of the list for all k ≤ m.
List.take_sublist
The prefix of length k of a list is a sublist of the original list.
List.length_take
The length of the prefix of length k of a list is min(k, length).
min_eq_left
If a ≤ b, then min(a, b) = a.
List.toFinset_card_of_nodup
The finset converted from a duplicate-free list has cardinality equal to the length of the list.
Finset.eq_empty_or_nonempty
Every finset is either empty or nonempty.
Finset.card_empty
The empty finset has cardinality 0.
Finset.card_le_card
If s ⊆ t, then |s| ≤ |t|.
Finset.card_pos.mpr
A finset has strictly positive cardinality if and only if it is nonempty.
Subsingleton.elim
Any two elements of a subsingleton type are equal.
Finset.mem_filter
An element is in a filtered finset if and only if it belongs to the finset and satisfies the predicate.
le_trans
Inequality is transitive: if a ≤ b and b ≤ c, then a ≤ c.
Finset.mem_inter
An element is in the intersection of two finsets if and only if it is in both.
List.mem_of_mem_take
An element in a prefix of a list is also in the list.
List.mem_toFinset.mp
An element in the finset converted from a list is also an element of the list.
List.mem_toFinset
An element belongs to the finset converted from a list if and only if it belongs to the list.
List.take_append
Taking k elements of a concatenation takes from the first list and then from the second.
List.mem_append_left
An element belonging to a list also belongs to the list concatenated with another list.
le_min
If c ≤ a and c ≤ b, then c ≤ min(a, b).

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

/-- Every approval profile with exactly one voter admits an EJR committee chain. -/theorem ejr_chain_one_voter {m : ℕ} (A : Fin 1 → Finset (Fin m)) :    ∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m →      is_ejr_committee A k (Finset.univ.filter fun c => (σ c : ℕ) < k) := by  let A0 := A 0  let B := Finset.univ \ A0  let L := A0.toList ++ B.toList  have hdisj : (A0.toList).Disjoint (B.toList) := by    rw [List.disjoint_left]    intro a ha hb    have ha' : a ∈ A0 := Finset.mem_toList.mp ha    have hb' : a ∈ B := Finset.mem_toList.mp hb    simp only [B, Finset.mem_sdiff, Finset.mem_univ, true_and] at hb'    exact hb' ha'  have hLnodup : L.Nodup := List.Nodup.append A0.nodup_toList B.nodup_toList hdisj  have hcardB : Finset.card B + Finset.card A0 = m := by    have := Finset.card_sdiff_add_card_eq_card (Finset.subset_univ A0)    simpa [B, Finset.card_univ, Fintype.card_fin] using this  have hLlen : L.length = m := by    simp only [L, List.length_append, Finset.length_toList]    omega  obtain ⟨σ, hσ⟩ := exists_perm_with_prefix_eq_take L hLnodup hLlen  refine ⟨σ, ?_⟩  intro k hk  have hW : Finset.univ.filter (fun c => (σ c : ℕ) < k) = (L.take k).toFinset := hσ k hk  rw [hW]  constructor  · have htake_nodup : (L.take k).Nodup := (List.take_sublist k L).nodup hLnodup    have htake_len : (L.take k).length = k := by      rw [List.length_take, hLlen, min_eq_left hk]    rw [List.toFinset_card_of_nodup htake_nodup, htake_len]  · intro ℓ hℓ G hGcoh    obtain ⟨hGcard, hcomm⟩ := hGcoh    have hGne : G.Nonempty := by      rcases Finset.eq_empty_or_nonempty G with h | h      · exfalso        rw [h] at hGcard        simp only [Finset.card_empty] at hGcard        omega      · exact h    have hGcard_le : Finset.card G ≤ 1 := by      have := Finset.card_le_card (Finset.subset_univ G)      simpa [Finset.card_univ] using this    have hGpos : 0 < Finset.card G := Finset.card_pos.mpr hGne    have hGc1 : Finset.card G = 1 := by omega    have hℓk : ℓ ≤ k := by      have := hGcard      rw [hGc1] at this      omega    obtain ⟨i, hi⟩ := hGne    have hi0 : i = 0 := Subsingleton.elim i 0    have h0mem : (0 : Fin 1) ∈ G := hi0 ▸ hi    have hsub : (({c | ∀ i ∈ G, c ∈ A i}) : Finset (Fin m)) ⊆ A0 := by      intro c hc      simp only [Finset.mem_filter, Finset.mem_univ, true_and] at hc      exact hc 0 h0mem    have hA0ge : ℓ ≤ Finset.card A0 := le_trans hcomm (Finset.card_le_card hsub)    refine ⟨0, h0mem, ?_⟩    let S := (A0.toList.take k).toFinset    have hSsub : S ⊆ A0 ∩ (L.take k).toFinset := by      intro c hc      rw [Finset.mem_inter]      constructor      · exact Finset.mem_toList.mp (List.mem_of_mem_take (List.mem_toFinset.mp hc))      · rw [List.mem_toFinset]        rw [List.take_append]        exact List.mem_append_left _ (List.mem_toFinset.mp hc)    have hScard : Finset.card S = min k (Finset.card A0) := by      have hnd : (A0.toList.take k).Nodup := (List.take_sublist k A0.toList).nodup A0.nodup_toList      rw [List.toFinset_card_of_nodup hnd, List.length_take, Finset.length_toList]    have hmin : ℓ ≤ Finset.card S := by      rw [hScard]      exact le_min hℓk hA0ge    exact le_trans hmin (Finset.card_le_card hSsub)
See it in the graphDiscuss this resultChallenge it