AFTD Auto-Formalizing Theoretical Domains

ranking_kendall_tau_le

theoremverified

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.

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

    lines 3–6

    uses Finset.card_le_card_of_injOn

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

    lines 7–9

    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⟩
  3. 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$.

    lines 10–13

    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)
  4. 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$.

    lines 14–17

    uses Fintype.card_product_filter_lt, Fintype.card_fin, Nat.choose_two_right

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

    line 18

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

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