Two questions related to computability structures on the unit square | The Hitchhiker's Guide to Computable Mathematics

The following questions were proposed to me by professor Zvonko Iljazović.

Let $I = [0,1]$ . We define the metric $d_\infty$ be the metric defined as

$d_\infty((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 I^2$ . Let $\mathcal{M} = (I^2, d_\infty)$ .

Let $a = (0,0)$ and $b = (0,1)$ . Suppose $(x_i)$ is a sequence in $\mathcal{M}$ such that the sequences $d(x_i, a)$ and $d(x_i,b)$ are computable sequences $\mathbb{N} \rightarrow \mathbb{R}$ ? Does the sequence $(x_i)$ need to be computable in the sense that its components are computable sequences $\mathbb{N} \rightarrow \mathbb{R}$ ?

Rendered by QuickLaTeX.com

Let $w = (1, \gamma)$ where $0 < \gamma < 1$ is an incomputable real. Then $d_\infty(x_i, a) = d_\infty(x_i, b)=1$ however, $(x_i)$ is not a computable sequence.

Now the second question. Let $a=(0,0)$ , $b=(0,1)$ and $c=(1,0)$ . Let $(x_i)$ be a sequence such that $d_\infty(x_i,a)$ , $d_\infty(x_i,b)$ and $d_\infty(x_i,c)$ are computable sequences $\mathbb{N} \rightarrow \mathbb{R}$ . Does the sequence $(x_i)$ need to be computable?

The answer is yes. The proof is available in our upcoming publication "Dense Computability Structures".

Proposition:
The metric space $\mathcal{M}$ has at least two maximal computability structures in which points $a=(0,0)$ and $b=(0,1)$ are computable.

Proof:
Let $(q_j)$ be a computable sequence in $\mathbb{R}^2$ such that $\mathrm{Im}\ q = \mathbb{Q}^2 \cap \mathcal{M}$ . Let $S_q$ be a computability structure induced by $q$ . Since $S_q$ is separable, it is also maximal.

Let $c = (1,\gamma)$ where $\gamma \in \langle 0,1 \rangle$ is an incomputable real. Then the finite sequence $(a,b,c)$ has the property $d_\infty(a,b) = d_\infty(a,c) = d_\infty(b,c) = 1$ hence by definition $(a,b,c)$ is an effective finite sequence.
Therefore,

$T = \{(a,a,a,\dots), (b,b,b,\dots), (c,c,c,\dots)\}$

is a computability structure and there exists a maximal computability structure $M$ such that $T \subseteq M$ and $a,b,c$ are computable points in $M$ .

On the other hand, the point $c$ is not computable in $S_q$ since that would contradict the fact that $w$ is a non-computable real. This is equivalent to the fact that $(c,c,c,\dots) \not \in S_q$ . Therefore, $M \not = S_q$ . From this we conclude that $M$ and $S_q$ are two maximal computability structures on $\mathcal{M}$ in which points $a$ and $b$ are computable.