rankings_of_eq_biUnion
lemmaverified
For nonempty S, the rankings of S are obtained by choosing a top alternative a in S and then a ranking of S minus a.
Statement
lemma rankings_of_eq_biUnion (S : Finset ℕ) (hS : S.Nonempty) : rankings_of S = S.biUnion (fun a => (rankings_of (S.erase a)).image (List.cons a))
- Source
- step towards plackett_luce_geometric_entropy_linear (Preference Elicitation as Average-Case Sorting, AAAI 2021, Sec. 5 conjecture (entropy O(m) for every phi in (0,1)))
- Verified
- 06 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- rankings_ofThe rankings of a finite set S of alternatives: all orderings of S as duplicate-free lists.
- mem_rankings_of_iffA list is a ranking of S iff it has no duplicates and its set of entries is S.
- Used by 1
- sum_rankings_of_nonemptyFor nonempty S, a sum over rankings of S splits as a sum over the top alternative a and the rankings of S minus a.
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.
lemma rankings_of_eq_biUnion (S : Finset ℕ) (hS : S.Nonempty) : rankings_of S = S.biUnion (fun a => (rankings_of (S.erase a)).image (List.cons a)) := by ext l simp only [Finset.mem_biUnion, Finset.mem_image, mem_rankings_of_iff] constructor · rintro ⟨hn, hs⟩ cases l with | nil => simp at hs; exact absurd hs.symm hS.ne_empty | cons a t => rw [List.nodup_cons] at hn have ha : a ∈ S := by rw [← hs]; simp refine ⟨a, ha, t, ⟨hn.2, ?_⟩, rfl⟩ rw [← hs, List.toFinset_cons, Finset.erase_insert (by simpa using hn.1)] · rintro ⟨a, ha, t, ⟨hn, hs⟩, rfl⟩ have hat : a ∉ t := by intro h have : a ∈ t.toFinset := List.mem_toFinset.2 h rw [hs] at this; simp at this refine ⟨List.nodup_cons.2 ⟨hat, hn⟩, ?_⟩ rw [List.toFinset_cons, hs, Finset.insert_erase ha]