mem_rankings_of_iff
lemmaverified
A list is a ranking of S iff it has no duplicates and its set of entries is S.
Statement
lemma mem_rankings_of_iff (S : Finset ℕ) (l : List ℕ) :
l ∈ rankings_of S ↔ l.Nodup ∧ l.toFinset = S- 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 1
- rankings_ofThe rankings of a finite set S of alternatives: all orderings of S as duplicate-free lists.
- Used by 3
- rankings_of_emptyThe empty set has exactly one ranking, the empty list.
- rankings_of_eq_biUnionFor nonempty S, the rankings of S are obtained by choosing a top alternative a in S and then a ranking of S minus a.
- map_sum_of_mem_rankings_ofThe total weight of the entries of a ranking of S is the total weight of S.
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 mem_rankings_of_iff (S : Finset ℕ) (l : List ℕ) : l ∈ rankings_of S ↔ l.Nodup ∧ l.toFinset = S := by unfold rankings_of rw [List.mem_toFinset, List.mem_permutations] constructor · intro h exact ⟨h.nodup_iff.2 S.nodup_toList, by rw [List.toFinset_eq_of_perm _ _ h, Finset.toList_toFinset]⟩ · rintro ⟨hn, hs⟩ exact List.perm_of_nodup_nodup_toFinset_eq hn S.nodup_toList (by rw [hs, Finset.toList_toFinset])