Combinatorial characterization of pseudometrics

Abstract

Let $X$, $Y$ be sets and let $\Phi$, $\Psi$ be mappings with the domains $X^2$ and $Y^2$ respectively. We say that $\Phi$ is combinatorially similar to $\Psi$ if there are bijections $f:\Phi (X^2)\to \Psi (Y^2)$ and $g:Y\to X$ such that $\Psi (x,y)=f(\Phi (g(x),g(y)))$ for all $x$, $y\in Y$. It is shown that the semigroups of binary relations generated by sets $\{{\Phi }^{-1}(a):a\in \Phi (X^2)\}$ and $\{{\Psi }^{-1}(b):b\in \Psi (Y^2)\}$ are isomorphic for combinatorially similar $\Phi$ and $\Psi$. The necessary and sufficient conditions under which a given mapping is combinatorially similar to a pseudometric, or strongly rigid pseudometric, or discrete pseudometric are found. The algebraic structure of semigroups generated by $\{d^{-1}(r):r\in d(X^2)\}$ is completely described for nondiscrete, strongly rigid pseudometrics and, also, for discrete pseudometrics $d:X^2\to \mathbb{R}$.

35 pages, 2 figures

Cited by in corpus (1)

• Combinatorial properties of ultrametrics and generalized ultrametrics