Sage Journals: Discover world-class research

Abstract

The well known ideal presentations of countably based domains were recently extended to (effective) quasi-Polish spaces. Continuing these investigations, we explore some classes of effective quasi-Polish spaces. In particular, we prove an effective version of the domain-characterization of quasi-Polish spaces, describe effective extensions of quasi-Polish topologies, discover natural numberings of classes of effective quasi-Polish spaces, estimate the complexity of the (effective) homeomorphism relation and of some classes of spaces with respect to these numberings, and investigate degree spectra of continuous domains.

Keywords

Effective quasi-Polish space effective domain numbering index set degree spectrum

Get full access to this article

View all access options for this article.

References

Abramsky and

Jung, Domain theory, in: Handbook of Logic in Computer Science, Vol. 3, Oxford Univ. Press, New York, 1994, pp. 1–168.

C.J.

Ash and

Knight, Computable Structures and the Hyperarithmetical Hierarchy, Studies in Logic and the Foundations of Mathematics, Vol. 144, North-Holland Publishing Co., Amsterdam, 2000.

P.A.

Cholak,

D.D.

Dzhafarov,

Schweber and

R.A.

Shore, Computably enumerable partial orders, Computability1(2) (2012), 99–107. doi:10.3233/COM-12013.

de Brecht, Quasi-Polish spaces, Ann. Pure Appl. Logic164(3) (2013), 356–381. doi:10.1016/j.apal.2012.11.001.

de Brecht, Some notes on spaces of ideals and computable topology, in: Beyond the Horizon of Computability, Lecture Notes in Comput. Sci., Vol. 12098, Springer, Cham, 2020, pp. 26–37.

de Brecht,

Kihara and

Selivanov, Enumerating classes of effective quasi-Polish spaces, in: Revolutions and Revelations in Computability, Lecture Notes in Comput. Sci., Vol. 13359, Springer, Cham, 2022, pp. 88–102.

de Brecht,

Pauly and

Schröder, Overt choice, Computability9(3–4) (2020), 169–191. doi:10.3233/COM-190253.

R.G.

Downey and

A.G.

Melnikov, Computably compact metric spaces, Bull. Symb. Log.29(2) (2023), 170–263. doi:10.1017/bsl.2023.16.

Y.L.

Ershov, Theory of domains and nearby, in: Formal Methods in Programming and Their Applications (Academgorodok, 1993), Lecture Notes in Comput. Sci., Vol. 735, Springer, Berlin, 1993, pp. 1–7. doi:10.1007/BFb0039696.

10.

Y.L.

Ershov and

S.S.

Goncharov, Constructive Models, Siberian School of Algebra and Logic, Consultants Bureau, New York, 2000.

11.

Fokina,

Friedman and

Nies, Equivalence relations that are

Σ_{3}^{0}

complete for computable reducibility, in: Logic, Language, Information and Computation,

Ong and

de Queiroz, eds, Lecture Notes in Comput. Sci., Vol. 7456, Springer, Berlin, Heidelberg, 2012, pp. 26–33. doi:10.1007/978-3-642-32621-9_2.

12.

E.B.

Fokina,

S.-D.

Friedman,

Harizanov,

J.F.

Knight,

McCoy and

Montalbán, Isomorphism relations on computable structures, J. Symbolic Logic77(1) (2012), 122–132. doi:10.2178/jsl/1327068695.

13.

E.B.

Fokina,

Harizanov and

Melnikov, Computable model theory, in: Turing’s Legacy: Developments from Turing’s Ideas in Logic, Lect. Notes Log., Vol. 42, Assoc. Symbol. Logic, La Jolla, CA, 2014, pp. 124–194. doi:10.1017/CBO9781107338579.006.

14.

Gierz,

K.H.

Hofmann,

Keimel,

J.D.

Lawson,

M.W.

Mislove and

D.S.

Scott, A Compendium of Continuous Lattices, Springer-Verlag, Berlin–New York, 1980.

15.

S.S.

Goncharov and

Knight, Computable structure and antistructure theorems, Algebra Logika41(6) (2002), 639–681, 757. doi:10.1023/A:1021758312697.

16.

Harrison-Trainor,

Melnikov and

K.M.

Ng, Computability of Polish spaces up to homeomorphism, J. Symb. Log.85(4) (2020), 1664–1686. doi:10.1017/jsl.2020.67.

17.

Hoyrup,

Kihara and

Selivanov, Degree spectra of homeomorphism type of compact Polish spaces, The Journal of Symbolic Logic (2023), 1–32, to appear, first view. doi:10.1017/jsl.2023.93.

18.

Hoyrup,

Rojas,

Selivanov and

D.M.

Stull, Computability on quasi-Polish spaces, in: Descriptional Complexity of Formal Systems, Lecture Notes in Comput. Sci., Vol. 11612, Springer, Cham, 2019, pp. 171–183. doi:10.1007/978-3-030-23247-4_13.

19.

A.S.

Kechris, Classical Descriptive Set Theory, Graduate Texts in Mathematics, Vol. 156, Springer-Verlag, New York, 1995.

20.

Kihara,

K.M.

Ng and

Pauly, Enumeration degrees and nonmetrizable topology, submitted. arXiv:1904.04107.

21.

Korovina and

Kudinov, On higher effective descriptive set theory, in: Unveiling Dynamics and Complexity, Lecture Notes in Comput. Sci., Vol. 10307, Springer, Cham, 2017, pp. 282–291. doi:10.1007/978-3-319-58741-7_27.

22.

T.H.

McNicholl and

D.M.

Stull, The isometry degree of a computable copy of

ℓ^{p 1}

, Computability8(2) (2019), 179–189. doi:10.3233/COM-180214.

23.

A.G.

Melnikov, Computably isometric spaces, J. Symbolic Logic78(4) (2013), 1055–1085. doi:10.2178/jsl.7804030.

24.

RogersJr., Theory of Recursive Functions and Effective Computability, McGraw-Hill Book Co., New York–Toronto–London, 1967.

25.

Selivanov, Positive structures, in: Computability and Models, Univ. Ser. Math., Kluwer/Plenum, New York, 2003, pp. 321–350. doi:10.1007/978-1-4615-0755-0_14.

26.

Selivanov, Towards the effective descriptive set theory, in: Evolving Computability, Lecture Notes in Comput. Sci., Vol. 9136, Springer, Cham, 2015, pp. 324–333. doi:10.1007/978-3-319-20028-6_33.

27.

V.L.

Selivanov, On degree spectra of topological spaces, Lobachevskii J. Math.41(2) (2020), 252–259. doi:10.1134/S1995080220020146.

28.

L.A.

Steen and

J.A.

SeebachJr., Counterexamples in Topology, Holt, Rinehart and Winston, Inc., New York–Montreal, Que.–London, 1970.

Ideal presentations and numberings of some classes of effective quasi-Polish spaces

Abstract

Keywords

Get full access to this article

References