December | 2018 | 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

The Hitchhiker's Guide to Computable Mathematics

Konrad Burnik

Monthly Archives: December 2018

Investigations into infinite metric bases (Part 2/2)

References