AFTD Auto-Formalizing Theoretical Domains

exists_perm_with_prefix_eq_take

theoremverified

Every duplicate-free list L of length m whose entries are the m candidates is the order of appearance of some permutation σ: for every k ≤ m the set {c | σ c < k} of candidates occupying the first k positions is exactly the set of the first k entries of L.

Statement

theorem exists_perm_with_prefix_eq_take {m : ℕ} (L : List (Fin m)) (hnd : L.Nodup) (hlen : L.length = m) :
    ∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m →
      Finset.univ.filter (fun c => (σ c : ℕ) < k) = (L.take k).toFinset
Source
step towards ejr_committee_monotone_chain_exists
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 4
  • 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…
  • ejr_chain_singleton_ballotsIf every voter approves at most one candidate, then there is an ordering of the candidates every prefix of which is an EJR committee of…
  • ejr_chain_of_nested_committeesIf there are committees W_0 ⊆ W_1 ⊆ ... ⊆ W_m with W_0 empty and W_k an EJR committee of size k for every k ≤ m, then there is a…
  • ejr_chain_one_voterEvery approval profile with exactly one voter admits an EJR committee chain.

The proof, explained

Because L has length m and contains no duplicates, every candidate in Fin m appears in L exactly once. We define a map f from candidates to Fin m sending each candidate to its index in L. This map is injective, hence a permutation σ by finiteness of Fin m. Finally, the candidates satisfying σ(c) < k are precisely those whose index in L is strictly less than k, which characterizes the elements in the first k positions of L.

  1. Every candidate c ∈ Fin m appears in the list L.

    Because L has no duplicate entries, the cardinality of its set of elements equals its length m. The universe Fin m also has cardinality m, so the set of elements of L must be the entire universe Fin m. In particular, every candidate c belongs to this set and therefore appears in L.

    lines 5–15

    uses List.toFinset_card_of_nodup, Finset.eq_univ_of_card, Fintype.card_fin, Finset.mem_univ, List.mem_toFinset.mp

      have h_mem : ∀ c : Fin m, c ∈ L := by
        intro c
        have h1 : Finset.card L.toFinset = m := by
          rw [List.toFinset_card_of_nodup hnd, hlen]
        have h2 : L.toFinset = Finset.univ := by
          apply Finset.eq_univ_of_card
          rw [h1, Fintype.card_fin]
        have h3 : c ∈ L.toFinset := by
          rw [h2]
          exact Finset.mem_univ c
        exact List.mem_toFinset.mp h3
  2. For every candidate c, the index of c in L is strictly less than m.

    Since c appears in L, its index in L is strictly less than the length of L. Because L has length m, linear arithmetic yields that the index is strictly less than m.

    lines 16–19

    uses List.idxOf_lt_length_iff.mpr

      have h_idx_lt : ∀ c : Fin m, L.idxOf c < m := by
        intro c
        have h : L.idxOf c < L.length := List.idxOf_lt_length_iff.mpr (h_mem c)
        omega
  3. The map f : Fin m → Fin m sending each candidate c to its position in L is injective.

    We define f(c) by assigning to c its index in L as an element of Fin m. If f(c₁) = f(c₂), their underlying index values in ℕ are equal. Since c₁ occurs in L, having identical indices implies c₁ = c₂.

    lines 20–25

    uses congrArg, Fin.val, List.idxOf_inj

      let f : Fin m → Fin m := fun c => ⟨L.idxOf c, h_idx_lt c⟩
      have hf_inj : Function.Injective f := by
        intro c1 c2 h
        have h_eq : (f c1).1 = (f c2).1 := congrArg Fin.val h
        dsimp [f] at h_eq
        exact (List.idxOf_inj (h_mem c1) (y := c2)).mp h_eq
  4. The map f is a bijection, giving rise to a permutation σ of Fin m.

    Any injective map from a finite type to itself is bijective. We turn this bijection f into a permutation σ of Fin m and choose σ as the witness for the existential statement.

    lines 26–28

    uses Finite.injective_iff_bijective.mp, Equiv.ofBijective

      have hf_bij : Function.Bijective f := Finite.injective_iff_bijective.mp hf_inj
      let σ : Equiv.Perm (Fin m) := Equiv.ofBijective f hf_bij
      use σ
  5. For every k ≤ m, the prefix set {c | σ(c) < k} equals the set of elements in the first k positions of L.

    By set extensionality, a candidate c belongs to {c | σ(c) < k} if and only if σ(c) < k. By construction, σ(c) is the index of c in L. Since c appears in L, having index strictly less than k is equivalent to belonging to the prefix of length k of L, which completes the equality with (L.take k).toFinset.

    lines 29–35

    uses Finset.mem_filter, Finset.mem_univ, true_and, List.mem_toFinset, List.mem_take_iff_idxOf_lt

      intro k hk
      ext c
      simp only [Finset.mem_filter, Finset.mem_univ, true_and]
      have h_σ_val : (σ c : ℕ) = L.idxOf c := rfl
      rw [h_σ_val]
      rw [List.mem_toFinset]
      rw [List.mem_take_iff_idxOf_lt (h_mem c)]
List.toFinset_card_of_nodup
A list with no duplicate entries has the same number of elements as its set of elements.
Finset.eq_univ_of_card
A subset of a finite type whose cardinality equals the cardinality of the whole type is the universal set.
Fintype.card_fin
The finite type Fin n of natural numbers strictly less than n has cardinality n.
Finset.mem_univ
Every element of a finite type belongs to its universal set.
List.mem_toFinset.mp
If an element belongs to the set of elements of a list, then it appears as an entry in that list.
List.idxOf_lt_length_iff.mpr
If an element appears in a list, its index in the list is strictly less than the length of the list.
congrArg
Applying a function to equal arguments yields equal values.
Fin.val
The canonical projection mapping a bounded index in Fin n to its underlying natural number.
List.idxOf_inj
For an element occurring in a list, two elements share the same index if and only if they are equal.
Finite.injective_iff_bijective.mp
An injective map from a finite type to itself is bijective.
Equiv.ofBijective
A bijective function between types can be packaged into an equivalence (a permutation when the source and target coincide).
Finset.mem_filter
An element belongs to a filtered set if and only if it belongs to the base set and satisfies the filtering predicate.
true_and
The conjunction of True with any proposition p is equivalent to p.
List.mem_toFinset
An element belongs to the set of entries of a list if and only if it appears in the list.
List.mem_take_iff_idxOf_lt
An element appearing in a list belongs to its prefix of length n if and only if its index in the list is strictly less than 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

/-- A duplicate-free list of all m candidates induces a permutation of the candidates whose every prefix set is the corresponding prefix of the list. -/theorem exists_perm_with_prefix_eq_take {m : ℕ} (L : List (Fin m)) (hnd : L.Nodup) (hlen : L.length = m) :    ∃ σ : Equiv.Perm (Fin m), ∀ k, k ≤ m →      Finset.univ.filter (fun c => (σ c : ℕ) < k) = (L.take k).toFinset := by  have h_mem : ∀ c : Fin m, c ∈ L := by    intro c    have h1 : Finset.card L.toFinset = m := by      rw [List.toFinset_card_of_nodup hnd, hlen]    have h2 : L.toFinset = Finset.univ := by      apply Finset.eq_univ_of_card      rw [h1, Fintype.card_fin]    have h3 : c ∈ L.toFinset := by      rw [h2]      exact Finset.mem_univ c    exact List.mem_toFinset.mp h3  have h_idx_lt : ∀ c : Fin m, L.idxOf c < m := by    intro c    have h : L.idxOf c < L.length := List.idxOf_lt_length_iff.mpr (h_mem c)    omega  let f : Fin m → Fin m := fun c => ⟨L.idxOf c, h_idx_lt c⟩  have hf_inj : Function.Injective f := by    intro c1 c2 h    have h_eq : (f c1).1 = (f c2).1 := congrArg Fin.val h    dsimp [f] at h_eq    exact (List.idxOf_inj (h_mem c1) (y := c2)).mp h_eq  have hf_bij : Function.Bijective f := Finite.injective_iff_bijective.mp hf_inj  let σ : Equiv.Perm (Fin m) := Equiv.ofBijective f hf_bij  use σ  intro k hk  ext c  simp only [Finset.mem_filter, Finset.mem_univ, true_and]  have h_σ_val : (σ c : ℕ) = L.idxOf c := rfl  rw [h_σ_val]  rw [List.mem_toFinset]  rw [List.mem_take_iff_idxOf_lt (h_mem c)]
See it in the graphDiscuss this resultChallenge it