RUS  ENG
Full version
JOURNALS // Algebra i logika // Archive

Algebra Logika, 2017 Volume 56, Number 4, Pages 453–476 (Mi al808)

This article is cited in 4 papers

Reducibility of computable metrics on the real line

R. A. Kornev

Novosibirsk State University, ul. Pirogova 1, Novosibirsk, 630090 Russia

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.

UDC: 510.5

Received: 13.10.2015
Revised: 16.10.2016

DOI: 10.17377/alglog.2017.56.405


 English version:
Algebra and Logic, 2017, 56:4, 302–317

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024