Research output: Contribution to journal › Article › peer-review
Reducibility of Computable Metrics on the Real Line. / Kornev, R. A.
In: Algebra and Logic, Vol. 56, No. 4, 01.09.2017, p. 302-317.Research output: Contribution to journal › Article › peer-review
}
TY - JOUR
T1 - Reducibility of Computable Metrics on the Real Line
AU - Kornev, R. A.
PY - 2017/9/1
Y1 - 2017/9/1
N2 - 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.
AB - 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.
KW - Cauchy representation
KW - computable metric space
KW - reducibility of representations
UR - http://www.scopus.com/inward/record.url?scp=85033371888&partnerID=8YFLogxK
U2 - 10.1007/s10469-017-9451-8
DO - 10.1007/s10469-017-9451-8
M3 - Article
AN - SCOPUS:85033371888
VL - 56
SP - 302
EP - 317
JO - Algebra and Logic
JF - Algebra and Logic
SN - 0002-5232
IS - 4
ER -
ID: 9700026