exists_perm_with_prefix_eq_take
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.
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.
uses
List.toFinset_card_of_nodup,Finset.eq_univ_of_card,Fintype.card_fin,Finset.mem_univ,List.mem_toFinset.mphave 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
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.
uses
List.idxOf_lt_length_iff.mprhave 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
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₂.
uses
congrArg,Fin.val,List.idxOf_injlet 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
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.
uses
Finite.injective_iff_bijective.mp,Equiv.ofBijectivehave hf_bij : Function.Bijective f := Finite.injective_iff_bijective.mp hf_inj let σ : Equiv.Perm (Fin m) := Equiv.ofBijective f hf_bij use σ
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.
uses
Finset.mem_filter,Finset.mem_univ,true_and,List.mem_toFinset,List.mem_take_iff_idxOf_ltintro 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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- 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)]