Metric Spaces | The Hitchhiker's Guide to Computable Mathematics

In Part 1 I posed the following question:

"Does there exist a metric space $(X,d)$ such that it has an infinite metric base $A$ with the following properties:

$A$ is not dense;
for all finite metric bases $B$ of $(X,d)$ we have $B \not \subseteq A$ ?"

Let $d:\mathbb{R}^2 \times \mathbb{R}^2 \rightarrow \mathbb{R}$ be defined as

$d((x_1,x_2), (y_1, y_2)) = \max(|x_1 - y_1|, |x_2-y_2|)$

for all $(x_1, x_2), (y_1, y_2) \in \mathbb{R}^2$ . Then $d$ is a metric on $\mathbb{R}^2$ , denoted by $d_\infty$ and $(\mathbb{R}^2, d_\infty)$ is a metric space.

After a brief chat with professor Zvonko Iljazović, he proposed the metric space $(\mathbb{R}^2,d_\infty)$ and the integer lattice $\mathbb{Z}^2$ as the candidate for such a set. Here I will explain why this set is a good candidate.

Let $A = \mathbb{Z}^2$ . Then $A$ is a countable set, which is not dense in $\mathbb{R}^2$ which can be seen by taking for example $x = (1/2,1/2)$ and $\epsilon = 1/4$ then $B(x,\epsilon) \cap A = \emptyset$ . By [1] the space $(\mathbb{R}^2, d_\infty)$ does not have a finite metric base, therefore $A$ itself can not contain a finite metric base. What is left to prove is that $\mathbb{Z}^2$ is a metric base for $(\mathbb{R}^2, d_\infty)$ . The rest of this blog post is concerned with proving this fact.

First, note that the following result was mentioned briefly in our CCA 2018 presentation.

Proposition 1. Let $\{a,b,c\} \in [0,1]\times[0,1]$ such that either $a=(0,0)$ , $b = (1,1)$ or $a=(0,1)$ , $b = (1,0).$ Let $c \not \in \overline{ab}$ . Then $\{a,b,c\}$ is a metric base for $([0,1]\times[0,1], d_\infty)$ .

Interestingly enough, the article [1] already gives a complete characterisation of finite metric bases for squares in the digital plane for a couple of metrics including $d_\infty$ . My conjecture is that this also gives a complete characterisation of finite metric bases for $([0,1]\times[0,1], d_\infty)$ however, this is a topic for another blog post. For now, it seems that the result stated in Proposition 1 coincides with some parts of results from [1] and as such will be sufficient for our needs.

We will also need the following claim, which is straightforward to establish.

Proposition 2. Let $(X,d_X)$ and $(Y,d_Y)$ be metric spaces. If $\{a_0,\dots,a_n\}$ is a metric base for $(X, d)$ and $\phi : X \rightarrow Y$ is an onto mapping such that there exists $\lambda > 0$ with the property

$d_Y(\phi(x), \phi(y)) = \lambda \cdot d_X(x, y),$

for all $x, y \in X$ , then $\{\phi(a_0),\dots,\phi(a_n)\}$ is a metric base for $(Y, d_Y)$ .

By using Proposition 2 we can now easily find a metric base for an arbitrary square $[\alpha,\beta]\times[\alpha,\beta]$ where $\alpha< \beta$ by using the known result of Proposition 1 and finding a suitable map $\phi : [0,1]\times[0,1]\rightarrow [\alpha,\beta]\times[\alpha,\beta]$ .

Proposition 3. Let $\{a,b,c\}$ be a metric base for $([0,1]\times[0,1], d_\infty)$ . Let $\phi :[0,1]\times[0,1] \rightarrow [\alpha,\beta]\times[\alpha,\beta]$ where $\alpha < \beta$ be defined as

$\phi(x_1,x_2) = ((1-x_1)\alpha + x_1 \beta, (1-x_2)\alpha + x_2 \beta))$

for all $(x_1,x_2) \in [0,1]\times[0,1]$ . Then $\{\phi(a), \phi(b), \phi(c)\}$ is a metric base for $([\alpha,\beta]\times[\alpha,\beta], d_\infty)$ .

Note that by setting $\lambda = \beta - \alpha$ it is easy to verify that $\phi$ defined in Proposition 3 satisfies the property of $\phi$ from Proposition 2.

Finally, we now have everything we need to prove that $\mathbb{Z}^2$ is indeed a metric base for $(\mathbb{R}^2, d_\infty)$ .

Proposition 4. $\mathbb{Z}^2$ is a metric base for $(\mathbb{R}^2, d_\infty)$ .

Proof.

Let $A =\mathbb{Z}^2$ . Let $x, y \in \mathbb{R}^2$ and assume that

$d_\infty(x,a) = d_\infty(y,a)$

for all $a \in A$ .

Note that we can always choose $\alpha<\beta$ such that $\alpha,\beta\in \mathbb{Z}^2$ and $x, y \in [\alpha,\beta]\times[\alpha,\beta]$ . Namely, we can take for example $M \in \mathbb{N}$ such that $M > \max(|x_1|,|x_2|,|y_1|,|y_2|)+1$ and set $S =\widehat{B}_\infty(0, M)$ . Now set $\alpha = -M$ and $\beta = M$ .

From Proposition 1, it follows that any three corners of the square $[0,1]\times[0,1]$ are a metric base for $([0,1]\times[0,1], d_\infty)$ . By Proposition 3 there is a map $\phi :[0,1]\times[0,1] \rightarrow [\alpha,\beta]\times[\alpha,\beta]$ such that $\{\phi(a), \phi(b), \phi(c)\}$ is a metric base for $[\alpha,\beta]\times[\alpha,\beta]$ . Since $\{\phi(a), \phi(b), \phi(c)\} \subset A$ , then $d_\infty(x,p) = d_\infty(y,p)$ for all $p\in \{\phi(a), \phi(b), \phi(c)\}$ implies $x = y$ .

Therefore, $A$ is a metric base for $(\mathbb{R}^2, d_\infty)$ .

Q.E.D.

References

Robert A. Melter and Ioan Tomescu "Metric Bases in Digital Geometry", Computer Vision, Graphics, and Image Processing Volume 25, Issue 1, January 1984, Pages 113-121 DOI: https://doi.org/10.1016/0734-189X(84)90051-3

Let $(X,d)$ be a metric space. Let $A \subseteq X$ be such that for all $x,y \in X$ the following implication holds:

$\left(\forall a \in A \ d(x,a) = d(a,y) \right) \implies x=y$

then we say $A$ is a metric base for $(X,d)$ . A sequence $\alpha$ in $X$ is called a dense sequence iff $\mathrm{Im}\ \alpha$ is a dense set. A metric base $A$ is a finite metric base iff $A$ is a finite set. Finding a finite metric base (if it exists) in a general metric space is already an interesting challenge and this will be explored in more detail in another post. Some information about how finite metric bases relate to computability can be found in another post. The question of existence of infinite metric bases however seems a bit less challenging due to the following easy result.

Proposition: Let $(X,d)$ be a metric space. Let $\alpha$ be a dense sequence in $X$ . Then $\mathrm{Im}\ \alpha$ is a metric base for $(X,d)$ .

Proof. Let $\alpha$ be a dense sequence and set $A = \mathrm{Im}\ \alpha$ . Let $x,y\in X$ . Suppose $d(x,a) = d(y,a)$ for all $a \in A$ . Since $\alpha$ is dense, there exists a sequence $(\beta_i)$ in $A$ such that $\lim_i \beta_i = x$ . This is equivalent to $\lim_i d(\beta_i, x) =0$ . Since $d(x,a) = d(y,a)$ for all $a \in A$ we have $\lim_i d(\beta_i, y) = 0$ .

Set $x_i=0$ , $y_i =d(x,y)$ and $z_i = d(x,\beta_i) + d(\beta_i, y)$ for all $i \in \mathbb{N}$ . From the triangle inequality and non-negativity of the metric we now have $x_i \leq y_i \leq z_i$ for all $i \in \mathbb{N}$ .

Since $\lim_i x_i = 0$ and $\lim_i z_i = 0$ , we have by the squeeze theorem $\lim_i y_i = \lim_i d(x,y) = 0$ , therefore $d(x,y) =0$ which implies $x=y$ . We conclude that $A$ is a metric base for $(X,d)$ .

Q.E.D.

Obviously, by set inclusion we have that every $A\subseteq X$ that contains a metric base is a metric base. What about metric bases which are not dense in $X$ and also do not contain a finite metric base? Formally, we have the following question:

Question: Does there exist a metric space $(X,d)$ such that it has an infinite metric base $A$ with the following properties:

$A$ is not dense;
for all finite metric bases $B$ of $(X,d)$ we have $B \not \subseteq A$ ?

The Hitchhiker's Guide to Computable Mathematics

Konrad Burnik

Category Archives: Metric Spaces

Investigations into infinite metric bases (Part 2/2)

References

Investigations into infinite metric bases (Part 1/2)