ranking_kendall_tau_self
A ranking is at Kendall tau distance 0 from itself.
Statement
theorem ranking_kendall_tau_self {G : Type*} [Fintype G] [DecidableEq G] {m : ℕ} (r : Fin m ≃ G) : ranking_kendall_tau r r = 0
- Source
- Sanity lemma for ranking_kendall_tau.
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- ranking_kendall_tauThe Kendall tau distance between two strict rankings r and s of the goods: the number of ordered pairs (g, h) that r ranks g above h while…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
The proof, explained
The Kendall tau distance between two rankings measures the number of pairs whose relative order is inverted. When comparing a ranking to itself, any such pair would require the rank of the first element to be strictly less than the rank of the second, and simultaneously the rank of the second to be strictly less than the rank of the first. Since strict inequality is asymmetric, no pair can satisfy both conditions, so the set of inverted pairs is empty and the distance is 0.
To show that the Kendall tau distance of a ranking to itself is zero, it suffices to show that no pair of elements has its relative order inverted with respect to itself.
Unfolding the definition of `ranking_kendall_tau`, the distance is the cardinality of the set of pairs (x, y) satisfying r⁻¹(x) < r⁻¹(y) and r⁻¹(y) < r⁻¹(x). By `Finset.card_eq_zero` and `Finset.filter_eq_empty_iff`, this cardinality is 0 if and only if no pair in the universe satisfies this conjunction.
uses
ranking_kendall_tau,Finset.card_eq_zero,Finset.filter_eq_empty_iffsimp only [ranking_kendall_tau, Finset.card_eq_zero, Finset.filter_eq_empty_iff]No pair of elements can satisfy the inversion condition, completing the proof.
Suppose for contradiction that there exists a pair (x, y) satisfying the condition, meaning r⁻¹(x) < r⁻¹(y) and r⁻¹(y) < r⁻¹(x). From the second inequality, we obtain r⁻¹(y) ≤ r⁻¹(x), which by `not_lt.mpr` implies ¬(r⁻¹(x) < r⁻¹(y)). This directly contradicts the first inequality, deriving a contradiction via `absurd`.
uses
absurd,not_lt.mprintro p _ h exact absurd h.1 (not_lt.mpr h.2.le)
ranking_kendall_tau- The Kendall tau distance between rankings r and s is the number of pairs (x, y) such that r⁻¹(x) < r⁻¹(y) and s⁻¹(y) < s⁻¹(x).
Finset.card_eq_zero- A finite set has cardinality 0 if and only if it is empty.
Finset.filter_eq_empty_iff- Filtering a finite set by a predicate yields the empty set if and only if no element in the set satisfies the predicate.
absurd- From a proposition and its negation, a contradiction (or any statement) follows.
not_lt.mpr- If b ≤ a in a linear order, then ¬(a < b).
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
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.
theorem ranking_kendall_tau_self {G : Type*} [Fintype G] [DecidableEq G] {m : ℕ} (r : Fin m ≃ G) : ranking_kendall_tau r r = 0 := by simp only [ranking_kendall_tau, Finset.card_eq_zero, Finset.filter_eq_empty_iff] intro p _ h exact absurd h.1 (not_lt.mpr h.2.le)