Geodesic
Computable metrics above the standard real metric
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 18 (2021) no. 1, pp. 377-392.

Voir la notice de l'article provenant de la source Math-Net.Ru

We construct a sequence of computable real metrics pairwise incomparable under weak reducibility $\leq_{ch}$ and located above the standard real metric w. r. t. computable reducibility $\leq_c$. Iterating the construction, we obtain that the ordering $(P(\omega),\subseteq)$ of subsets of $\omega$ is embeddable into the ordering of $ch$-degrees of real metrics above the standard metric. It is also proved that the countable atomless Boolean algebra is embeddable with preservation of joins and meets into the ordering of $c$-degrees of computable real metrics.
Keywords: computable metric space, representation of real numbers, Cauchy representation, reducibility of representations, computable analysis. 
@article{SEMR_2021_18_1_a6,
     author = {R. A. Kornev},
     title = {Computable metrics above the standard real metric},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {377--392},
     publisher = {mathdoc},
     volume = {18},
     number = {1},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a6/}
}
TY  - JOUR
AU  - R. A. Kornev
TI  - Computable metrics above the standard real metric
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2021
SP  - 377
EP  - 392
VL  - 18
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a6/
LA  - en
ID  - SEMR_2021_18_1_a6
ER  - 
%0 Journal Article
%A R. A. Kornev
%T Computable metrics above the standard real metric
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2021
%P 377-392
%V 18
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a6/
%G en
%F SEMR_2021_18_1_a6
R. A. Kornev. Computable metrics above the standard real metric. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 18 (2021) no. 1, pp. 377-392. http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a6/

[1] R. Kornev, “Reducibility of computable metrics on the real line”, Algebra Logic, 56:4 (2017), 302–317 | DOI | MR | Zbl

[2] H. Rogers, Theory of recursive functions and effective computability, McGraw-Hill, Maidenhead, Berksh., 1967 | MR | Zbl

[3] R. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets, Springer-Verlag, Berlin etc., 1987 | MR | Zbl

[4] K. Weihrauch, Computable analysis. An introduction, Texts Theoret. Comput. Sci.. An EATCS Ser., Springer, Berlin, 2000 | DOI | MR | Zbl

[5] R. Downey, D. Hirschfeldt, Algorithmic randomness and complexity, Springer, New York, 2010 | MR | Zbl

[6] Ch. Kreitz, K. Weihrauch, “Theory of representations”, Theor. Comput. Sci., 38 (1985), 35–53 | DOI | MR | Zbl

[7] Yu.L. Ershov, “Theory of numberings”, Handbook of computability theory, Stud. Logic Found. Math., 140, ed. E. R. Griffor, Elsevier, Amsterdam, 1999, 473–503 | DOI | MR | Zbl

[8] A.G. Melnikov, “Computably isometric spaces”, J. Symb. Log., 78:4 (2013), 1055–1085 | DOI | MR | Zbl

[9] J. Miller, “Degrees of unsolvability of continuous functions”, J. Symb. Log., 69:2 (2004), 555–584 | DOI | MR | Zbl

[10] K. Ko, H. Friedman, “Computational complexity of real functions”, Theor. Comput. Sci., 20:3 (1982), 323–352 | DOI | MR | Zbl

[11] K. Weihrauch, X. Zheng, “Effectiveness of the global modulus of continuity on metric spaces”, Theor. Comput. Sci., 219:1-2 (1999), 439–450 | DOI | MR | Zbl

[12] R. Shore, “The Turing degrees: An introduction”, Forcing, Iterated Ultrapowers, and Turing Degrees, World Scientific, 2015, 39–121 | DOI | MR

[13] S. Binns, S. Simpson, “Embeddings into the Medvedev and Muchnik lattices of $\Pi^0_1$ classes”, Arch. Math. Logic, 43:3 (2004), 399–414 | DOI | MR | Zbl

[14] S.S. Goncharov, Countable Boolean algebras and decidability, Siberian School of Algebra and Logic, Plenum, New York, 1997 | MR | Zbl