AFTD Auto-Formalizing Theoretical Domains

ejr_chain_exists_of_support_density_bound

theoremverified

A permutation whose every prefix satisfies the proposed density bound yields an EJR committee chain.

Statement

theorem ejr_chain_exists_of_support_density_bound (n m : ℕ)
    (A : Fin n → Finset (Fin m)) (hn : 0 < n)
    (h : ∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m →
      ejr_support_density_bound A (k + 1)
        (Finset.univ.filter fun c => (σ c : ℕ) < k)) :
    ∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m →
      is_ejr_committee A k (Finset.univ.filter fun c => (σ c : ℕ) < k)
Source
Supporting work for OP-22, arXiv:2007.01795, Q2, and the proposed max-group-density invariant in memory attempt 4342. These helpers neither settle full-chain existence nor refute the actual greedy rule. No research advance is claimed.
Verified
25 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • ejr_support_density_boundThe finite supporter-density bound: for every candidate subset T, its undersatisfied supporter count times q is at most |T| times the…
  • 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| ≥ ℓ.
  • ejr_of_support_density_boundFor a nonempty electorate, the density bound with q=k+1 implies EJR for any committee of size k.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

The proof, explained

To show that an EJR committee chain exists, we use the assumed permutation σ whose prefixes satisfy the support density bound at each size k ≤ m. An auxiliary lemma first proves that each prefix {c ∈ Fin m | σ c < k} has cardinality k by setting up a bijection to the initial interval of Fin m. The main theorem then applies the transfer lemma ejr_of_support_density_bound to each prefix to conclude that every prefix is an EJR committee.

  1. The prefix {c ∈ Fin m | σ c < k} has the same cardinality as the unpermuted prefix {c ∈ Fin m | c < k}.

    The permutation σ induces a bijection between {c | σ c < k} and {c | c < k}. By Finset.card_bij, σ maps elements of the former into the latter, σ is injective, and any b < k has preimage σ⁻¹(b) satisfying σ(σ⁻¹(b)) = b < k. Rewriting with this bijection reduces the goal to showing that the unpermuted prefix has size k.

    lines 4–15

    uses Finset.card_bij, Finset.mem_filter, Finset.mem_univ, true_and

      classical
      have he : (Finset.univ.filter fun c => (σ c : ℕ) < k).card =
          (Finset.univ.filter fun c : Fin m => (c : ℕ) < k).card := by
        apply Finset.card_bij (fun c _ => σ c)
        · intro c hc
          simpa only [Finset.mem_filter, Finset.mem_univ, true_and] using hc
        · intro a ha b hb hab
          exact σ.injective hab
        · intro b hb
          refine ⟨σ.symm b, ?_, by simp⟩
          simpa only [Finset.mem_filter, Finset.mem_univ, true_and, σ.apply_symm_apply] using hb
      rw [he]
  2. When k = m, the prefix {c ∈ Fin m | c < m} has cardinality m.

    If k = m, every element c ∈ Fin m satisfies c < m by definition of Fin m. The filtered subset is thus the entire universe Finset.univ of Fin m, whose cardinality is m.

    lines 16–18

      by_cases hkm : k = m
      · subst k
        simp
  3. When k < m, the prefix {c ∈ Fin m | c < k} is the open interval Finset.Iio ⟨k, hlt⟩, which has cardinality k.

    From k ≤ m and k ≠ m, linear arithmetic gives k < m, so k defines an element ⟨k, hlt⟩ ∈ Fin m. By extensionality and Finset.mem_Iio, the prefix equals Finset.Iio ⟨k, hlt⟩. Its cardinality is then evaluated as k using Fin.card_Iio.

    lines 19–25

    uses Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_Iio, Fin.card_Iio

      · have hlt : k < m := by omega
        have hI : (Finset.univ.filter fun c : Fin m => (c : ℕ) < k) =
            Finset.Iio (⟨k, hlt⟩ : Fin m) := by
          ext c
          simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_Iio]
          rfl
        rw [hI, Fin.card_Iio]
  4. The permutation σ produces an EJR committee of size k for each prefix size k ≤ m.

    We unpack the permutation σ and hypothesis hσ from the existential assumption. For each k ≤ m, the auxiliary lemma ejr_density_prefix_card_aux shows that the prefix W_k = {c | σ c < k} has cardinality k. Together with the density bound from hσ, ejr_of_support_density_bound concludes that W_k is an EJR committee of size k.

    lines 34–36

    uses ejr_of_support_density_bound, ejr_density_prefix_card_aux

      obtain ⟨σ, hσ⟩ := h
      exact ⟨σ, fun k hk => ejr_of_support_density_bound A k _ hn
        (ejr_density_prefix_card_aux σ k hk) (hσ k hk)⟩
Finset.card_bij
Two finite sets s and t have equal cardinality if there exists an injective and surjective map from s to t.
Finset.mem_filter
An element a belongs to Finset.filter p s if and only if a ∈ s and p a holds.
Finset.mem_univ
Every element of a finite type belongs to its universal Finset, Finset.univ.
true_and
The conjunction True ∧ p is equivalent to p.
Finset.mem_Iio
An element x belongs to the open interval Finset.Iio a if and only if x < a.
Fin.card_Iio
In Fin n, the cardinality of the strictly lower interval Finset.Iio b is equal to the numerical value of b.
ejr_of_support_density_bound
If a committee W has cardinality k and satisfies the support density bound with parameter k + 1 for an approval profile with n > 0 voters, then W is an EJR committee of size k.
ejr_density_prefix_card_aux
For any permutation σ of Fin m and any k ≤ m, the prefix Finset.univ.filter (fun c => σ c < k) has cardinality exactly k.

Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.

Lean source view module on GitHub

theorem ejr_density_prefix_card_aux {m : ℕ} (σ : Equiv.Perm (Fin m))    (k : ℕ) (hk : k ≤ m) :    (Finset.univ.filter fun c => (σ c : ℕ) < k).card = k := by  classical  have he : (Finset.univ.filter fun c => (σ c : ℕ) < k).card =      (Finset.univ.filter fun c : Fin m => (c : ℕ) < k).card := by    apply Finset.card_bij (fun c _ => σ c)    · intro c hc      simpa only [Finset.mem_filter, Finset.mem_univ, true_and] using hc    · intro a ha b hb hab      exact σ.injective hab    · intro b hb      refine ⟨σ.symm b, ?_, by simp⟩      simpa only [Finset.mem_filter, Finset.mem_univ, true_and, σ.apply_symm_apply] using hb  rw [he]  by_cases hkm : k = m  · subst k    simp  · have hlt : k < m := by omega    have hI : (Finset.univ.filter fun c : Fin m => (c : ℕ) < k) =        Finset.Iio (⟨k, hlt⟩ : Fin m) := by      ext c      simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_Iio]      rfl    rw [hI, Fin.card_Iio]theorem ejr_chain_exists_of_support_density_bound (n m : ℕ)    (A : Fin n → Finset (Fin m)) (hn : 0 < n)    (h : ∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m →      ejr_support_density_bound A (k + 1)        (Finset.univ.filter fun c => (σ c : ℕ) < k)) :    ∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m →      is_ejr_committee A k (Finset.univ.filter fun c => (σ c : ℕ) < k) := by  obtain ⟨σ, hσ⟩ := h  exact ⟨σ, fun k hk => ejr_of_support_density_bound A k _ hn    (ejr_density_prefix_card_aux σ k hk) (hσ k hk)⟩
See it in the graphDiscuss this resultChallenge it