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