Finite metric bases and computability structures

Introduction

In July 2018 professor Zvonko Iljazović and myself have attended the CCA 2018 conference and presented our joint work titled "Effective compactness and uniqueness of maximal computability structures". The original presentation can be found here.

Computability structures

In the following I will mention the elements of the theory of computability structures needed to state our main result. These notions are already well known, the main contributing articles for this theory that were used for our work are listed in the references.

Let $(X,d)$ be a metric space and $(x_i)$ a sequence in $X$ . We say $(x_i)$ is an effective sequence in $(X, d)$ if the function $\mathbb{N}^2 \rightarrow \mathbb{R}$

$(i,j) \mapsto d(x_i, x_j)$

is recursive.

A finite sequence $x_0,\dots,x_n$ is an effective finite sequence if $d(x_i, x_j)$ is a recursive real number for each $i,j \in \{0, \dots, n\}$ .

If $(x_i)$ and $(y_j)$ are sequences in $X$ , we say $((x_i), (y_j))$ is an effective pair in $(X,d)$ and write $(x_i) \diamond (y_j)$ if the function $\mathbb{N}^2 \rightarrow \mathbb{R}$ ,

$(i,j) \mapsto d(x_i, y_j)$

is recursive.

Let $(X,d)$ be a metric space and $(x_i)$ a sequence in $X$ . A sequence $(y_i)$ is computable w.r.t $(x_i)$ in $(X,d)$ iff there exists a computable $F:\mathbb{N}^2\rightarrow \mathbb{N}$ such that

$d(y_i, x_{F(i, k)}) < 2^{-k}$

for all $i,k \in \mathbb{N}$ . We write $(x_i) \preceq (y_j)$ .

Let $(X, d)$ be a metric space. A set $\mathcal{S} \subseteq X^\mathbb{N}$ is a computability structure on $(X,d)$ if the following holds:

$(x_i), (y_j) \in \mathcal{S}$ , then $(x_i) \diamond (y_j)$
if $(x_i) \in \mathcal{S}$ and $(y_j) \preceq (x_i)$ , then $(y_j) \in \mathcal{S}$

We say $x$ is a computable point in $\mathcal{S}$ iff $(x,x,\dots) \in \mathcal{S}$ .

A computability structure $\mathcal{S}$ such that there exists a dense sequence $\alpha \in \mathcal{S}$ is called separable.

We say $\mathcal{S}$ is a maximal computability structure on $(X, d)$ if there exists no computability structure $\mathcal{T}$ such that $\mathcal{S} \subseteq \mathcal{T}$ and $\mathcal{S} \not = \mathcal{T}$ .

The main question

The main question we are asking and trying to answer is the following:

Question:Let $(X,d)$ be a metric space. Let $a_0,\dots,a_k \in X$ . Let $\mathcal{M}$ be a maximal computability structure in which $a_0,\dots,a_k$ are computable. Under which conditions is such $\mathcal{M}$ unique?

A known result for sub-spaces of the Euclidean space

Let $V$ be a real vector space. Let $a_0,\dots,a_k$ be vectors in $V$ . We say that $a_0,\dots, a_k$ are geometrically independent points if $a_1 - a_0, \dots, a_k - a_0$ are linearly independent vectors.

Let $X \subseteq V$ . The largest $k \in \mathbb{N}$ such that that there exist geometrically independent points $a_0,\dots, a_k \in X$ we call the affine dimension of $X$ , and write $\mathrm{dim}\ X = k$ .

The following result from [1] already answers the main question in the case where $(X,d)$ is a sub-space of the Euclidean space.

Theorem: Let $X \subseteq \mathbb{R}^n$ , $k = \mathrm{dim}\ X$ and $k \geq 1$ . If $a_0,\dots,a_{k-1}$ is a geometrically independent effective finite sequence on $X$ then there exists an unique maximal computability structure on $X$ in which $a_0,\dots,a_{k-1}$ are computable points.

Main result for more general metric spaces

We wanted to introduce for general metric spaces a notion which will be a sort of replacement to the notion of geometric independence.

In the original presentation we used the term nice sequence. It turns out that this notion is a special case of the well-known notion of a metric base.

Let $(X, d)$ be a metric space. A subset $S \subseteq X$ is called a metric base for $(X,d)$ iff for all $x,y \in X$ the following implication holds: $d(x,s) = d(y,s)$ for all $s \in S$ implies $x=y$ .

A metric space $(X,d)$ is said to be effectively compact if there exist an effective separating sequence $\alpha$ in $(X,d)$ and a computable function $f:\mathbb{N}\rightarrow \mathbb{N}$ such that

$X=B(\alpha _{0} ,2^{-k})\cup \dots \cup B(\alpha _{f(k)},2^{-k})$

for each $k\in \mathbb{N}$ . It is known that if $(X,d)$ is effectively compact, then for each effective separating sequence $\alpha$ in $(X,d)$ there exists such a computable function $f$ .

A metric base is exactly the notion we needed to obtain the following result, at least for effectively compact metric spaces.

Theorem: Let $(X,d)$ be an effectively compact metric space. Suppose $a_{0} ,\dots ,a_{n}$ is a metric base in $(X,d)$ and suppose that there exists a separable computability structure $\mathcal{S}$ on $(X,d)$ in which $a_{0} ,\dots ,a_{n}$ are computable points. Then $\mathcal{S}$ is a unique maximal computability structure on $(X,d)$ in which $a_{0} ,\dots ,a_{n}$ are computable points.

In fact, an even more general form of the theorem holds: the assumption of effective compactness of the space $(X,d)$ can be replaced with the assumption that $(X,d)$ has compact closed balls and there exists $\alpha$ such that the computable metric space $(X,d,\alpha)$ has the effective covering property.

Proofs will be presented in our future up-coming publication.

References

Zvonko Iljazović. Isometries and Computability Structures. Journal of Universal Computer Science, 16(18):2569--2596, 2010.
Zvonko Iljazović and Lucija Validžić. Maximal computability structures. Bulletin of Symbolic Logic, 22(4):445--468, 2016.
Alexander Melnikov. Computably isometric spaces. Journal of Symbolic Logic, 78:1055--1085, 2013.
Marian Pour-El and Ian Richards. Computability in Analysis and Physics. Springer-Verlag, Berlin-Heielberg-New York, 1989.
Klaus Weihrauch. Computable Analysis. Springer, Berlin, 2000.
M. Yasugi, T. Mori and Y. Tsujji. Effective properties of sets and functions in metric spaces with computability structure. Theoretical Computer Science}, 219:467--486, 1999.
M. Yasugi, T. Mori and Y. Tsujji. Computability structures on metric spaces. Combinatorics, Complexity and Logic Proc. DMTCS96 (D.S.~Bridges et al), Springer, Berlin}, 351--362, 1996.

The Hitchhiker's Guide to Computable Mathematics

Konrad Burnik