Abstract
We study computable reducibility of computable metrics on 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.
Original language | English |
---|---|
Pages (from-to) | 302-317 |
Number of pages | 16 |
Journal | Algebra and Logic |
Volume | 56 |
Issue number | 4 |
DOIs | |
Publication status | Published - 1 Sep 2017 |
Keywords
- Cauchy representation
- computable metric space
- reducibility of representations