Degree Spectra of Homeomorphism Types of Compact Polish Spaces

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

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
4 SPBU - Saint Petersburg State University

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 compact Polish spaces. We show that there exists a 0'-computable low_3 compact Polish space which is not homeomorphic to a computable one, and that, for any natural number n\geq 2, there exists a Polish space X_n such that exactly the high_n-degrees are required to present the homeomorphism type of X_n. We also show that no compact Polish space has a least presentation with respect to Turing reducibility. The first version of this article appeared in April 2020. This version is a major update from September 2023, with improved proofs and results.

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 Compact Polish Spaces. The Journal of Symbolic Logic, inPress, pp.1-32. ⟨10.1017/jsl.2023.93⟩. ⟨hal-02555111v2⟩