Every Δ⁰₂ Polish space is computable topological

Bazhenov, Nikolay; Melnikov, Alexander; Ng, Keng Meng

doi:10.1090/proc/16797

Every $\Delta ^0_2$ Polish space is computable topological
HTML articles powered by AMS MathViewer

by Nikolay Bazhenov, Alexander Melnikov and Keng Meng Ng;

Proc. Amer. Math. Soc. 152 (2024), 3123-3136

DOI: https://doi.org/10.1090/proc/16797

Published electronically: May 7, 2024

HTML | PDF | Request permission

Abstract:

We show that every $\Delta ^0_2$ Polish space admits a computable topological presentation given by an effective indexing of some non-empty open sets in the space.

References

C. J. Ash and J. Knight, Computable structures and the hyperarithmetical hierarchy, Studies in Logic and the Foundations of Mathematics, vol. 144, North-Holland Publishing Co., Amsterdam, 2000. MR 1767842
G. Baumslag, E. Dyer, and C. F. Miller III, On the integral homology of finitely presented groups, Topology 22 (1983), no. 1, 27–46. MR 682058, DOI 10.1016/0040-9383(83)90044-7
Nikolay Bazhenov, Matthew Harrison-Trainor, and Alexander Melnikov, Computable Stone spaces, Ann. Pure Appl. Logic 174 (2023), no. 9, Paper No. 103304, 25. MR 4609470, DOI 10.1016/j.apal.2023.103304
G. S. Ceĭtin, Algorithmic operators in constructive complete separable metric spaces, Dokl. Akad. Nauk SSSR 128 (1959), 49–52 (Russian). MR 115910
Rodney G. Downey and Alexander G. Melnikov, Computably compact metric spaces, Bull. Symb. Log. 29 (2023), no. 2, 170–263. MR 4616053, DOI 10.1017/bsl.2023.16
Rod Downey and Carl G. Jockusch, Every low Boolean algebra is isomorphic to a recursive one, Proc. Amer. Math. Soc. 122 (1994), no. 3, 871–880. MR 1203984, DOI 10.1090/S0002-9939-1994-1203984-4
Yuri L. Ershov and Sergei S. Goncharov, Constructive models, Siberian School of Algebra and Logic, Consultants Bureau, New York, 2000. MR 1749622, DOI 10.1007/978-1-4615-4305-3
Lawrence Feiner, Hierarchies of Boolean algebras, J. Symbolic Logic 35 (1970), 365–374. MR 282805, DOI 10.2307/2270692
S. S. Goncharov and J. F. Knight, Computable structure and non-structure theorems, Algebra and Logic 41 (2002), no. 6, 351–373.
Vassilios Gregoriades, Tamás Kispéter, and Arno Pauly, A comparison of concepts from computable analysis and effective descriptive set theory, Math. Structures Comput. Sci. 27 (2017), no. 8, 1414–1436. MR 3724458, DOI 10.1017/S0960129516000128
Tanja Grubba and Klaus Weihrauch, On computable metrization, Proceedings of the Third International Conference on Computability and Complexity in Analysis (CCA 2006), Electron. Notes Theor. Comput. Sci., vol. 167, Elsevier Sci. B. V., Amsterdam, 2007, pp. 345–364. MR 2321793, DOI 10.1016/j.entcs.2006.08.020
M. Harrison-Trainor and A. Melnikov, An arithmetic analysis of closed surfaces, Trans. Amer. Math. Soc. (2023), published online, doi: 10.1090/tran/8915.
Matthew Harrison-Trainor, Alexander Melnikov, and Keng Meng Ng, Computability of Polish spaces up to homeomorphism, J. Symb. Log. 85 (2020), no. 4, 1664–1686. MR 4243758, DOI 10.1017/jsl.2020.67
G. Higman, Subgroups of finitely presented groups, Proc. Roy. Soc. London Ser. A 262 (1961), 455–475. MR 130286, DOI 10.1098/rspa.1961.0132
Mathieu Hoyrup, Takayuki Kihara, and Victor Selivanov, Degrees of non-computability of homeomorphism types of Polish spaces, Beyond the horizon of computability, Lecture Notes in Comput. Sci., vol. 12098, Springer, Cham, [2020] ©2020, pp. 189–192. MR 4139535, DOI 10.1007/978-0-387-68546-5
N. G. Khisamiev, The arithmetic hierarchy of abelian groups, Sibirsk. Mat. Zh. 29 (1988), no. 6, 144–159 (Russian); English transl., Siberian Math. J. 29 (1988), no. 6, 987–999 (1989). MR 985295, DOI 10.1007/BF00972425
N. G. Khisamiev, Constructive abelian groups, Handbook of recursive mathematics, Vol. 2, Stud. Logic Found. Math., vol. 139, North-Holland, Amsterdam, 1998, pp. 1177–1231. MR 1673602, DOI 10.1016/S0049-237X(98)80050-5
H. T. Koh, A. Melnikov, and K. M. Ng, Computable topological groups, J. Symb. Log. (2023), published online, doi: 10.1017/jsl.2023.67.
Margarita Korovina and Oleg Kudinov, The Rice-Shapiro theorem in computable topology, Log. Methods Comput. Sci. 13 (2017), no. 4, Paper No. 30, 13. MR 3744005
Martino Lupini, Alexander Melnikov, and Andre Nies, Computable topological abelian groups, J. Algebra 615 (2023), 278–327. MR 4511344, DOI 10.1016/j.jalgebra.2022.10.003
A. I. Mal′cev, Constructive algebras. I, Uspehi Mat. Nauk 16 (1961), no. 3(99), 3–60 (Russian). MR 151377
Alexander G. Melnikov and Keng Meng Ng, Separating notions in effective topology, Internat. J. Algebra Comput. 33 (2023), no. 8, 1687–1711. MR 4683224, DOI 10.1142/S0218196723500649
Alexander G. Melnikov, Computable abelian groups, Bull. Symb. Log. 20 (2014), no. 3, 315–356. MR 3271281, DOI 10.1017/bsl.2014.32
Antonio Montalbán, Computable structure theory—within the arithmetic, Perspectives in Logic, Cambridge University Press, Cambridge; Association for Symbolic Logic, Ithaca, NY, 2021. MR 4274028, DOI 10.1017/9781108525749
Y. N. Moschovakis, Recursive metric spaces, Fund. Math. 55 (1964), 215–238. MR 182562, DOI 10.4064/fm-55-3-215-238
Yiannis N. Moschovakis, Descriptive set theory, 2nd ed., Mathematical Surveys and Monographs, vol. 155, American Mathematical Society, Providence, RI, 2009. MR 2526093, DOI 10.1090/surv/155
E. Ju. Nogina, Effectively topological spaces, Dokl. Akad. Nauk SSSR 169 (1966), 28–31 (Russian). MR 207559
Michael O. Rabin, Computable algebra, general theory and theory of computable fields, Trans. Amer. Math. Soc. 95 (1960), 341–360. MR 113807, DOI 10.1090/S0002-9947-1960-0113807-4
Matthias Schröder, Effective metrization of regular spaces, Computability and Complexity in Analysis, Informatik Berichte 235 (1998), 63–80.
Dieter Spreen, A characterization of effective topological spaces, Recursion theory week (Oberwolfach, 1989) Lecture Notes in Math., vol. 1432, Springer, Berlin, 1990, pp. 363–387. MR 1071526, DOI 10.1007/BFb0086126
Klaus Weihrauch and Tanja Grubba, Elementary computable topology, J.UCS 15 (2009), no. 6, 1381–1422. MR 2534366