AFTD Auto-Formalizing Theoretical Domains

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

Lean source view module on GitHub

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