AFTD Auto-Formalizing Theoretical Domains

ranking_kendall_tau_self

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

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.

  1. 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.

    line 3

    uses ranking_kendall_tau, Finset.card_eq_zero, Finset.filter_eq_empty_iff

      simp only [ranking_kendall_tau, Finset.card_eq_zero, Finset.filter_eq_empty_iff]
  2. 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`.

    lines 4–5

    uses absurd, not_lt.mpr

      intro 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

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