is_ultrametric_transition_of_eq_const
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 thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
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.
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})$.
intro i j k hij hjk hikThe 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`.
uses
le_max_leftrw [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
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.
/-- 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