Finite ultrametric spaces and computer science (Q2752023)

A metric space \((X,d)\) is called ultrametric (or non-Archimedean, or isosceles) provided it satisfies the strong triangle inequality \(d(x,z)\leq\max\{d(x,y),d(y,z)\}\). This concept derives from the notion of non-Archimedean valuations in field theory, and arises in a wide variety of topics in mathematics. This paper is an interesting, eclectic survey with several apparently new results. Topic include finite ultrametric spaces, embedding theorems, Banach spaces, graduated lattices, categorical operations, and ultrametrizations. Concerning finite spaces, we mention Theorem 4: In a finite ultrametric space of cardinality \(n+1\), the set of values of its metric consists of at most \(n\) numbers. Concerning embeddings, there is a complete discussion of the known results about ultrametric spaces into which all ultrametric spaces of a given weight \(\tau\) can be isometrically embedded (\(\tau\)-universal spaces). These results revolve around the \(\tau\)-universal space \(LW_\tau\) constructed by the author and \textit{A. J. Lemin} [Topology Appl. 103, No. 3, 339-345 (2000; Zbl 0983.54031)]. For example, Theorem 6 states that for any ultrametric space \((X,d)\) there exists a family \(\{D_\alpha:\alpha< \kappa\}\) of two-point (ultra)metric spaces, where \(\kappa\) is the weight of \(X\), such that \((X,d)\) can be isometrically embedded into the metric product \(m\Pi_{\alpha} D_\alpha\). The metric product of a family of metric spaces \(\{(X_\alpha,d_\alpha):\alpha <\lambda\}\) is defined in two cases: If there is a number \(c>0\) such that \(\sup\{\text{diam}(X_\alpha):\alpha < \lambda\}<c\), the set of the metric product is the Cartesian product and the metric is defined by \(d((x_\alpha),(y_\alpha)) = \sup\{d_\alpha(x_\alpha,y_\alpha):\alpha<\lambda\}\); otherwise a base point \(x^*_\alpha\) of each \(X_\alpha\) is chosen and the set of the metric product is then defined to be the subset of the Cartesian product consisting of all points \((x_\alpha)\) that are at a finite distance from the base point of the product \(x^* =(x^*_\alpha)\). Proposition 9 states that the metric product of the two-point subspaces \(\{0,q\}\) of the real line, where \(q\) runs through the positive rational numbers, is isometric to \(LW_2\). There are five unsolved problems mentioned. \(\{\)Three preprints given in the references have appeared. One by \textit{Alex J. Lemin}, Isometric embedding of ultrametric (non-Archimedean) spaces in Hilbert space and Lebesgue space, in ``\(p\)-adic functional analysis'', Proc. 6th internat. conf., Ioannina, 2000, Lecture Notes in Pure and Appl. Math., 222, 203-218 (2001; Zbl 0993.46051); one by \textit{J. Lawson}, Math. Struct. Comput. Sci. 7, No. 5, 543-555 (1997; Zbl 0985.54025); and one by the reviewer, ``Universal ultrametric spaces of smallest weight,'' Topol. Proc. 24, 611-619 (1999)\}. For the entire collection see [Zbl 0966.00025].