Abstract:
We study computable reducibility of computable metrics on $\mathbf R$ induced by reducibility of their respective Cauchy representations. It is proved that this ordering has a subordering isomorphic to an arbitrary countable tree. Also we introduce a weak version of computable reducibility and construct a countable antichain of computable metrics that are incomparable with respect to it. Informally, copies of the real line equipped with these metrics are pairwise homeomorphic but not computably homeomorphic.
Keywords:computable metric space, Cauchy representation, reducibility of representations.