This is a follow-up of sorts to an earlier question on mine in that it should be easier to construct a positive example of this, if it exists.

To be clear about definitions, a computable metric space is a metric space $(X,d)$ with a dense sequence $\{q_n\}_{n<\omega}$ such that $d(q_n,q_m)$ is a uniformly computable family of computable real numbers. The points $q_n$ are called rational points. Given a computable metric space $X$ and a point $x\in X$, a name of $x$ is any function $f:\omega\rightarrow \omega$ satisfying $d(q_{f(n)},q_{f(m)})\leq\frac{1}{n}+\frac{1}{m}$ for all $n,m<\omega$ and such that $q_{f(n)}\rightarrow x$ as $n\rightarrow \infty$. A point $x\in X$ is computable if it is a name that is a computable function. Given a computable metric space $X$, we'll denote the set of computable points in $X$ as $X_{c}$.

Given a pair of computable metric spaces $X$ and $Y$, a Turing functional $A \mapsto \Phi_e^A$ induces a partial function $F_e$ from $X$ to $Y$ by the rule $F_e(x)=y$ iff for any name $f$ of $x$, $\Phi_e^f$ is a name of $y$. One can check that any such function is automatically continuous on its domain. A computable homeomorphism between $X$ and $Y$ is a pair of Turing functionals $\Phi_e$ and $\Phi_i$ such that $F_e$ is a total bijection from $X$ to $Y$ and $F_i$ is its inverse from $Y$ to $X$. $X$ and $Y$ are said to be computably homeomorphic if there exists a computable homeomorphism between them.

Now we can state the question:

Does there exist a pair of complete computable metric spaces $X$ and $Y$ with no isolated points such that $X$ and $Y$ are not homeomorphic, but $X_c$ and $Y_c$ are computably homeomorphic?

The completeness stipulation is necessary because technically the definition of a computable metric space allows it to be any arbitrary subset of its completion that contains its rational points. The no isolated points stipulation is necessary because there is a relatively easy example, building off of the Kleene tree, of a compact computable metric space whose rational points are all isolated and with the property that the only computable points are rational. You can easily give a functional mapping the computable points in this space to a non-compact discrete space. On the other hand, since $X_c$ and $Y_c$ are countable metric spaces with no isolated points, they are both classically homeomorphic to $\mathbb{Q}$, so there is no obvious proof that a computable homeomorphism can't exist. The proof of this is effective if you actually have a list of the elements of the space, but you can show that in a complete computable metric space with no isolated points you can computably find a point not on any given list of points in the space.


1 Answer 1


I think that maybe I should have thought about this a little harder before posting, because it seems like there is a fairly easy positive answer:

Let $X=[0,1]$ with a standard enumeration of the rational numbers. Let $f:[0,1]_c \rightarrow \mathbb{R}$ be a computable function that is unbounded (an easy example is to let $f(x)=\frac{1}{g(x)}$ where $g:[0,1]\rightarrow [0,1]$ is a computable function whose zeroset contains no computable points). Then let $Y_0 = [0,1]_c$ with the metric $d(x,y)=|x-y|+|f(x)-f(y)|$ and let $Y$ be the metric completion of $Y_0$. $X$ and $Y$ are obviously not homeomorphic because $X$ is compact and $Y$ is not. On the other hand, the identity function is a computable homeomorphism between $X_c$ and $Y_c$.

  • $\begingroup$ Another example would be the real line and the unit circle, with the natural metrics. You can think of the circle as the one point compactification of the line, with the extra point being any noncomputable point. This induces a homeomorphism on their computable points. $\endgroup$ Feb 7, 2019 at 5:12
  • $\begingroup$ Are you sure that can be done with a computable homeomorphism? $\endgroup$ Feb 7, 2019 at 18:18
  • $\begingroup$ No, it can't. Sorry, I missed that part of the question. $\endgroup$ Feb 8, 2019 at 19:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.