AFTD Auto-Formalizing Theoretical Domains

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

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]
See it in the graphDiscuss this resultChallenge it