AFTD Auto-Formalizing Theoretical Domains

map_sum_of_mem_rankings_of

lemmaverified

The total weight of the entries of a ranking of S is the total weight of S.

Statement

lemma map_sum_of_mem_rankings_of (w : ℕ → ℝ) (S : Finset ℕ) (t : List ℕ)
    (ht : t ∈ rankings_of S) : (t.map w).sum = ∑ b ∈ S, w b
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
  • plackett_luce_prob_consIf a is in S and t ranks S minus a, the Plackett-Luce probability of a followed by t is w(a)/w(S) times that of t.

Lean source view module on GitHub

lemma map_sum_of_mem_rankings_of (w : ℕ → ℝ) (S : Finset ℕ) (t : List ℕ)    (ht : t ∈ rankings_of S) : (t.map w).sum = ∑ b ∈ S, w b := by  rw [mem_rankings_of_iff] at ht  rw [← ht.2, List.sum_toFinset _ ht.1]
See it in the graphDiscuss this resultChallenge it