AFTD Auto-Formalizing Theoretical Domains

is_ultrametric_transition_of_eq_const

theoremverified

For a natural number n, a linearly ordered type α, a matrix P : Matrix (Fin n) (Fin n) α, and an element c : α, if all off-diagonal entries of P satisfy P i j = c for all i ≠ j, then P satisfies is_ultrametric_transition P.

Statement

theorem is_ultrametric_transition_of_eq_const {n : ℕ} {α : Type*} [LinearOrder α]
    (P : Matrix (Fin n) (Fin n) α) (c : α)
    (hP : ∀ i j, i ≠ j → P i j = c) :
    is_ultrametric_transition P
Source
folklore
Verified
29 Oct 2026
Axioms
propext
Built on 3
  • is_ultrametric_transitionFor a natural number n and a linearly ordered type α, an n-by-n matrix P : Matrix (Fin n) (Fin n) α satisfies the ultrametric transition…
  • 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.

Read back from the Lean

For any natural number $n$, any linearly ordered type $\alpha$, any $n \times n$ matrix $P$ with entries in $\alpha$, and any element $c \in \alpha$: if all off-diagonal entries of $P$ are equal to $c$ (that is, $P_{i, j} = c$ whenever $i \ne j$), then $P$ satisfies is_ultrametric_transition P.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

To show that a matrix with constant off-diagonal entries satisfies the ultrametric transition property, we take any three pairwise distinct indices $i, j, k$. Because all three pairs of indices are distinct, the off-diagonal hypothesis implies that $P_{i j}$, $P_{i k}$, and $P_{j k}$ all equal the same constant $c$. The required inequality $P_{i j} \le \max(P_{i k}, P_{j k})$ then reduces to $c \le \max(c, c)$, which holds by the basic property of the maximum.

  1. Let $i, j, k$ be pairwise distinct indices.

    Unfolding the definition of `is_ultrametric_transition`, we introduce three arbitrary indices $i, j, k \in \mathrm{Fin}(n)$ along with the hypotheses that $i \neq j$, $j \neq k$, and $i \neq k$. The remaining goal is to show $P_{i j} \le \max(P_{i k}, P_{j k})$.

    line 6

      intro i j k hij hjk hik
  2. The ultrametric inequality $P_{i j} \le \max(P_{i k}, P_{j k})$ holds.

    Because the indices are pairwise distinct, the hypothesis `hP` guarantees that $P_{i j} = c$, $P_{i k} = c$, and $P_{j k} = c$. Substituting $c$ for each entry simplifies the inequality to $c \le \max(c, c)$, which holds immediately by `le_max_left`.

    lines 7–8

    uses le_max_left

      rw [hP i j hij, hP i k hik, hP j k hjk]
      exact le_max_left c c
le_max_left
Any element $a$ is less than or equal to $\max(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

/-- Any matrix with constant off-diagonal entries satisfies the ultrametric transition property. -/theorem is_ultrametric_transition_of_eq_const {n : ℕ} {α : Type*} [LinearOrder α]    (P : Matrix (Fin n) (Fin n) α) (c : α)    (hP : ∀ i j, i ≠ j → P i j = c) :    is_ultrametric_transition P := by  intro i j k hij hjk hik  rw [hP i j hij, hP i k hik, hP j k hjk]  exact le_max_left c c
See it in the graphDiscuss this resultChallenge it