Finding a reordering of the non-recursive sequence in computable metric space such that it is a recursive squence.

52 Views Asked by At

Let $(X, d, \alpha)$ be a computable metric space.

We say that $x \in X$ is a recursive point in $(X, d, \alpha)$ if there exists a recursive function $f : \mathbb{N} \rightarrow \mathbb{N}$ such that $d(x, \alpha_{f(k)}) < 2^{-k}$, for every $k \in \mathbb{N}$.

Let $(x_i)_{i \in \mathbb{N}}$ be a sequence in $X$. We say that $(x_i)_{i \in \mathbb{N}}$ is a recursive sequence in $(X, d, \alpha)$ if there exists a recursive function $F : \mathbb{N}^2 \rightarrow \mathbb{N}$ such that $d(x_i, \alpha_{F(i,k)}) < 2^{-k}$ for all $i,k \in \mathbb{N}$.

It is easy to see that if $(x_i)_{i \in \mathbb{N}}$ is a recursive sequence than $x_i$ is a recursive point for every $i \in \mathbb{N}$.

Im interested in the next question:

Suppose $(x_i)_{i \in \mathbb{N}}$ is a non-recurursive sequence in $(X, d, \alpha)$ such that $x_i$ is a recursive point in $(X, d, \alpha)$ for every $i \in \mathbb{N}$. Can we find a bijection $\sigma : \mathbb{N} \rightarrow \mathbb{N}$ such that $(x_{\sigma(i)})_{i \in \mathbb{N}}$ is a recursive sequence in $(X, d, \alpha)$? Also, can we find a recursive bijection $\sigma : \mathbb{N} \rightarrow \mathbb{N}$ such that $(x_{\sigma(i)})_{i \in \mathbb{N}}$ is a recursive sequence in $(X, d, \alpha)$?

1

There are 1 best solutions below

0
On BEST ANSWER

Assuming the computable metric space is infinite, the answer to both questions is no for cardinality reasons.

To make things simpler, let's consider a more restricted version of your first question where we only look at sequences whose elements are all of the form $\alpha_i$ for some $i$ and whose elements are all distinct. In other words, let's consider the following question: given an infinite subset $A \subseteq \mathbb{N}$, is there always an enumeration $f \colon \mathbb{N} \to A$ such that $(\alpha_{f(n)})_{n \in \mathbb{N}}$ is a recursive sequence in $(X, d, \alpha)$? Hopefully it is clear that if the answer to this question is no then the answer to your original two questions is no.

To see why the answer to this new question is "no," we simply compare cardinalities. There are only countably many recursive sequences in $(X, d, \alpha)$ but there are uncountably many infinite subsets of $\mathbb{N}$.