The ordered algebraic structure of pseudometrics

The pointwise ordering of pseudometrics is mainly known as the order-theoretic setting of the category of metric spaces and short maps. It has additional features as well, including an onto monotone map to the order dual of the lattice of equivalence relations.

The associated monotone map:
Let $S$ be a set and let $M(S)$ denote the family of all pseudometric spaces on $S$. If we done the lattice of equivalence relations on $S$ by $Part(S)$ then its order dual is $Part(S)^d$. We can now construct a map $f : M(S) \to Part(S)^d$ defined by estabilshing an apartness relation $f(m)$ that has $(x,y) \in f(m)$ if $0 \lt d_m(x,y) $.

Theorem. $f : M(S) \to Part(S)^d$ is monotone

Proof. Let $m_1, m_2$ be pseudometrics on $S$ such that $m_1 \leq m_2$. Then $f(m_1)$ is the apartness relation $\{(x,y) : 0 \lt d_{m_1}(x,y) \}$. We have that $m_1 \leq m_2$ so it follows that $0 \lt d_{m_1}(x,y) \leq d_{m_2}(x,y)$ for all $x,y$. By the transitivity of $(\mathbb{R}_{\geq 0}, \leq)$ this implies $0 \lt d_{m_2}(x,y)$. Therefore, for all $x,y$ we have that $0 \lt d_{m_1}(x,y)$ implies $0 \lt d_{m_2}(x,y)$. In other words, $f(m_1) \leq f(m_2)$ which means that $f$ is monotone. $\square$

Representation of apartness relations:
Now that we have established a monotone map from the pointwise ordering of pseudometrics to the lattice $Part(S)^d$ we can now provide a construction of $Part(S)^d$ using pseudometrics. In doing so, we will constructively demonstrate that $f$ is onto.

Definition. the pseudometric representation of an apartness relation on $S$ is a function $d : S^2 \to \mathbb{R}_{\geq 0}$ defined by \[ d(x,y) = \begin{cases} 0 & (x,y) \not\in R \\ 1 & (x,y) \in R \end{cases} \] Dually, the pseudometric representation of an equivalence relation can by formed by setting the distance between two points to be zero when they are equal, and to one otherwise.

Example 1. {{0},{1,2,3}} \[ \begin{bmatrix} 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{bmatrix} \]

Example 2. {{0},{1,2},{3,4}} \[ \begin{bmatrix} 0 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 \end{bmatrix} \]

Example 3. {{0,1,2},{3,4,5}} \[ \begin{bmatrix} 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 \end{bmatrix} \]
If the family of all pseudometrics on a set is denoted $M(S)$ then we can denote the subset of $\{0,1\}$-pseudometrics by $M_{0,1}(S)$. It follows from this representation that the restriction map of $f$ to $M_{0,1}(S)$ is an isomorphism in the category of preorders and monotone maps. The minimal $\{0,1\}$-pseudometric is the pseudometric with distances of zero between each element, which is also the minimal pseudometric in general. The maximal $\{0,1\}$-pseudometric is the distance metric of the complete graph on $S$.

Properties:
The pointwise ordering has several properties in relations to other constructions such as graphs and topologies, described below.

1. The mapping from a connected graph to its pseudometric is antitone. Let $G$ and $H$ be graphs on a common set $S$ such that $G \subseteq H$ then $d_H \subseteq d_G$.
2. Let $m_1 \subseteq m_2$ be pseudometrics, $x$ be a point, and $r$ be a radius. Then $B_{m_2}(x,r) \subseteq B_{m_1}(x,r)$.
3. The mapping from a pseudometric to its radius or diameter is monotone. For any diameter $\delta$ the Vietoris-Rips complex is decreasing.
4. The mapping $g : M_{0,1}(S) \to T(S)$ from a $\{0,1\}$-pseudometric to its pseudometric topology is an order isomorphism.

To get (1) notice that the distance between points in a graph is the minimal path length between them. If we increase the graph by adding more edges, then we can only get a larger set of paths between two points. The mapping from a set to its minimal element is antitone, so the minimal path length can only be decreasing. Therefore, graph distances decrease as well. To get (2) notice that an open ball is the set of points less then a distance around a point, if the distances are increasing then the open ball can only get smaller.

On point (3) the diameter is the largest distance between points, so if the distance between points increases then the diameter can only increase and likewise for the radius. It follows that Vietoris-Rips complexes are decreasing. Finally, for part (4) we know that $Part(S)^d$ is order isomorphic to the family of partition topologies, so it follows that $\{0,1\}$-pseudometrics are as well.

Addition of pseudometrics:
The basic algebraic operation on pseudometrics is addition. Like the ordering of pseudometrics, it is defined pointwise.

Theorem. the addition of pseudometrics is a pseudometric

Proof. Let $d_X$ and $d_Y$ be distance functions of pseudometrics. Then $d_{X + Y}$ is a commutative non-negative real valued function. It remains to show the triangle inequality is satisfied for $d_{X+Y}$. In other words, we want to show: \[d_X(x,z) + d_Y(y,z) \leq d_X(x,y) + d_Y(x,y) + d_X(y,z) + d_Y(y,z) \] These terms can be rewritten to get: \[d_X(x,z) + d_Y(y,z) \leq (d_X(x,y) + d_X(y,z)) + (d_Y(x,y) + d_Y(y,z)) \] By the triangle inequality we have that $d_X(x,z) \leq (d_X(x,y) + d_X(y,z))$ and that $d_Y(y,z) \leq (d_Y(x,y) + d_Y(y,z))$. By the biextensive property of addition we can add the two inequalities to get the above one. The triangle inequality follows, which means that the sum is a pseudometric. $\square$.

The addition operation on the non-negative real numbers is a commutative posetal monoid with biextensive action. This is inherited by pseudometrics, which means that they form a commutative posetal monoid. The biextensive action means that for any given pseudometric adding it to another pseudometric will only increase it. In other words, addition is an upper bound producing function for the pointwise ordering. It follows that the family of pseudometrics on a set $(M(S), \leq, +)$ forms an ordered algebraic structure.

Theorem. $f : (M(S),+) \to (Part(S)^d, \vee)$ is a semigroup homomorphism from distance sums to differenc joins

Proof. The equivalence relation of $d_{m_1 + m_2}$ is defined by $d_{m_1}(x,y) + d_{m_1}(x,y)$. Equating to zero yields $d_{m_1}(x,y) + d_{m_2}(x,y) = 0$. Distances in pseudo-metrics are non-negative. Therefore, in order for this to be the case it must be that $d_{m_1}(x,y) = 0$ and that $d_{m_2}(x,y) = 0$. In other words, $x,y$ must be in the intersection of the equivalence relations of $d_{m_1}$ and $d_{m_2}$. By duality, the intersection of equivalence relations is the join of difference relations. It follows that $f(d_{m_1+m_2}) = f(d_{m_1}) \vee f(d_{m_2})$.

The relationship between distance sums is an intuitive one, and it shows how pseudometrics establish themselves over apartness relations. Apartness relations, which are dual to equivalence relations, simply describe how two things are different or not equal. Pseudometrics establish degrees of difference between things.

Corollary. the sum pseudometrics whose equivalence relations meet at the minimal equivalence relation in the lattice of equivalence relations forms a metric.

This enables a natural means by which we can construction pseudometrics from independently changing variables. The difference between two elements is then the sum of the distances between their individual components.

Example 1.. the distance between sets is equal to the sum of membership distances (each of which form $\{0,1\}$-pseudometrics). Membership differences can only arise from elements in the union that are not in the intersection, which comes back to $|S \triangle T|$.

Example 2. the distance between multisets is equal to the sum of the multiplicity distances between individual members, where multiplicity distances are defined using distances between natural numbers.

Example 3. the taxicab metric is the sum of pseudometrics defined for each variable

Noting that adding more paths to a pseudometric is antitone, the euclidean metric can be formed from the taxicab metric by adding straight lines between points. It follows that euclidean distance is a submetric of the taxicab metric in the pointwise ordering.