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. 
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/
@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},
     year = {2021},
     volume = {18},
     number = {1},
     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
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
%U http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a6/
%G en
%F 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