Degree Spectra of Homeomorphism Types of Polish Spaces

Mathieu Hoyrup (1) , Takayuki Kihara (2) , Victor Selivanov (3)

1 MOCQUA - Designing the Future of Computational Models
2 Graduate School of Informatics, Nagoya University
3 A.P. Ershov Institute of Informatics Systems SB RAS

A Polish space is not always homeomorphic to a computably presented Polish space. In this article, we examine degrees of non-computability of presenting homeomorphic copies of Polish spaces. We show that there exists a 0'-computable low3 Polish space which is not homeomorphic to a computable one, and that, for any natural number n, there exists a Polish space Xn such that exactly the high2n+3-degrees are required to present the homeomorphism type of Xn. We also show that no compact Polish space has an easiest presentation with respect to Turing reducibility.

Mots clés: computable topology; computable presentation; computable Polish space; degree spectrum

Domaines: Logique en informatique [cs.LO]; Topologie générale [math.GN]

Mathieu Hoyrup, Takayuki Kihara, Victor Selivanov. Degree Spectra of Homeomorphism Types of Polish Spaces. 2020. ⟨hal-02555111v1⟩