ranking_kendall_tau_le
The Kendall tau distance between two rankings of m goods is at most m(m-1)/2.
Statement
theorem ranking_kendall_tau_le {G : Type*} [Fintype G] [DecidableEq G] {m : ℕ} (r s : Fin m ≃ G) : ranking_kendall_tau r s ≤ m * (m - 1) / 2
- Source
- Helper for iterated_round_robin_two_agents_item_preserving_swaps_le (arXiv:2610.23040 Theorem 3.12): the initial distance is at most m(m-1)/2.
- Verified
- 19 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- 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…
The proof, explained
The proof bounds the Kendall tau distance by the number of strictly ordered pairs of indices in $\text{Fin } m$. Since any pair of goods discordant between $r$ and $s$ satisfies $r^{-1}(p_1) < r^{-1}(p_2)$, mapping each discordant pair to $(r^{-1}(p_1), r^{-1}(p_2))$ injectively embeds them into the set of pairs $(i, j)$ with $i < j$. The number of such ordered index pairs is $\binom{m}{2} = m(m - 1) / 2$, which immediately bounds the Kendall tau distance.
To bound the Kendall tau distance by the number of strictly ordered index pairs in $\text{Fin } m$, it suffices to construct an injective map from discordant pairs into this target set.
We introduce an intermediate bound $h_1$ asserting that the Kendall tau distance is at most the number of pairs in $\text{Fin } m \times \text{Fin } m$ whose first coordinate is strictly less than their second. Unfolding `ranking_kendall_tau` (line 5), the distance is the number of pairs of goods $p$ satisfying $r^{-1}(p.1) < r^{-1}(p.2)$ and $s^{-1}(p.2) < s^{-1}(p.1)$. By `Finset.card_le_card_of_injOn` (line 6), this cardinality is bounded by that of the target set if the mapping $p \mapsto (r^{-1}(p.1), r^{-1}(p.2))$ maps into the target set and is injective on the discordant pairs.
uses
Finset.card_le_card_of_injOnhave h1 : ranking_kendall_tau r s ≤ ((Finset.univ : Finset (Fin m × Fin m)).filter (fun x => x.1 < x.2)).card := by dsimp [ranking_kendall_tau] apply Finset.card_le_card_of_injOn (fun p => (r.symm p.1, r.symm p.2))
The mapping $p \mapsto (r^{-1}(p.1), r^{-1}(p.2))$ maps discordant pairs into pairs of indices with $i < j$.
For any discordant pair $p$, rewriting with `Finset.mem_coe` and `Finset.mem_filter` shows that $r^{-1}(p.1) < r^{-1}(p.2)$ and $s^{-1}(p.2) < s^{-1}(p.1)$ (line 8). In particular, the first component $r^{-1}(p.1)$ is strictly less than the second $r^{-1}(p.2)$, and the pair belongs to $\text{Finset.univ}$ by `Finset.mem_univ` (line 9), meeting the membership condition of the target set.
uses
Finset.mem_coe,Finset.mem_filter,Finset.mem_univ· intro p hp rw [Finset.mem_coe, Finset.mem_filter] at hp ⊢ exact ⟨Finset.mem_univ _, hp.2.1⟩
The mapping $p \mapsto (r^{-1}(p.1), r^{-1}(p.2))$ is injective, establishing that the Kendall tau distance is at most the number of strictly ordered index pairs ($h_1$).
Suppose two discordant pairs $p_1, p_2$ satisfy $(r^{-1}(p_1.1), r^{-1}(p_1.2)) = (r^{-1}(p_2.1), r^{-1}(p_2.2))$ (line 11). Equating coordinates gives $r^{-1}(p_1.1) = r^{-1}(p_2.1)$ and $r^{-1}(p_1.2) = r^{-1}(p_2.2)$ (line 12). Because $r^{-1}$ is an equivalence and therefore injective, $p_1.1 = p_2.1$ and $p_1.2 = p_2.2$, so $p_1 = p_2$ by `Prod.ext` (line 13). This completes the proof of $h_1$.
uses
Prod.ext· intro p1 _ p2 _ h have h' : (r.symm p1.1, r.symm p1.2) = (r.symm p2.1, r.symm p2.2) := h injection h' with h1 h2 exact Prod.ext (r.symm.injective h1) (r.symm.injective h2)
The number of strictly ordered pairs of indices in $\text{Fin } m$ is $m(m - 1) / 2$.
By `Fintype.card_product_filter_lt` (lines 14–16), the cardinality of $\{(i, j) \in \text{Fin } m \times \text{Fin } m \mid i < j\}$ is $\binom{|\text{Fin } m|}{2}$. Rewriting with `Fintype.card_fin` and `Nat.choose_two_right` simplifies this to $m(m - 1) / 2$ (line 17), establishing $h_2$.
uses
Fintype.card_product_filter_lt,Fintype.card_fin,Nat.choose_two_righthave h2 : ((Finset.univ : Finset (Fin m × Fin m)).filter (fun x => x.1 < x.2)).card = (Fintype.card (Fin m)).choose 2 := Fintype.card_product_filter_lt rw [Fintype.card_fin, Nat.choose_two_right] at h2
The Kendall tau distance between $r$ and $s$ is at most $m(m - 1) / 2$.
Linear integer arithmetic (`omega`) combines the upper bound $h_1$ with the cardinality formula $h_2$ to conclude the theorem.
omega
Finset.card_le_card_of_injOn- If a function maps a finite set $s$ into a finite set $t$ and is injective on $s$, then the cardinality of $s$ is at most the cardinality of $t$.
Finset.mem_coe- An element belongs to a finite set viewed as a set via coercion if and only if it belongs to the finite set.
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the original finset and satisfies the filtering predicate.
Finset.mem_univ- Every element of a finite type belongs to its universal finset.
Prod.ext- Two pairs are equal if and only if their first coordinates are equal and their second coordinates are equal.
Fintype.card_product_filter_lt- In any linearly ordered finite type $\alpha$, the number of pairs $(x_1, x_2)$ with $x_1 < x_2$ equals $\binom{|\alpha|}{2}$.
Fintype.card_fin- The cardinality of the standard finite type $\text{Fin } n$ is $n$.
Nat.choose_two_right- The binomial coefficient $\binom{n}{2}$ equals $n(n - 1) / 2$.
- The definition `ranking_kendall_tau` counts directed pairs $(p_1, p_2)$ of goods such that $r^{-1}(p_1) < r^{-1}(p_2)$ and $s^{-1}(p_2) < s^{-1}(p_1)$. Directing pairs by $r$ ensures that each discordant pair of goods is counted exactly once without needing to divide by 2.
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_le {G : Type*} [Fintype G] [DecidableEq G] {m : ℕ} (r s : Fin m ≃ G) : ranking_kendall_tau r s ≤ m * (m - 1) / 2 := by have h1 : ranking_kendall_tau r s ≤ ((Finset.univ : Finset (Fin m × Fin m)).filter (fun x => x.1 < x.2)).card := by dsimp [ranking_kendall_tau] apply Finset.card_le_card_of_injOn (fun p => (r.symm p.1, r.symm p.2)) · intro p hp rw [Finset.mem_coe, Finset.mem_filter] at hp ⊢ exact ⟨Finset.mem_univ _, hp.2.1⟩ · intro p1 _ p2 _ h have h' : (r.symm p1.1, r.symm p1.2) = (r.symm p2.1, r.symm p2.2) := h injection h' with h1 h2 exact Prod.ext (r.symm.injective h1) (r.symm.injective h2) have h2 : ((Finset.univ : Finset (Fin m × Fin m)).filter (fun x => x.1 < x.2)).card = (Fintype.card (Fin m)).choose 2 := Fintype.card_product_filter_lt rw [Fintype.card_fin, Nat.choose_two_right] at h2 omega