Abstract
We investigate the effectivizations of several equivalent definitions of quasi-Polish spaces and study which characterizations hold effectively. Being a computable effectively open image of the Baire space is a robust notion that admits several characterizations. We show that some natural effectivizations of quasi-metric spaces are strictly stronger.
This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 731143
C. Rojas was supported by Marie Curie RISE project CID.
V. Selivanov was supported by Inria program Invited Researcher and the Regional Mathematical Center of Kazan Federal University (project 1.13556.2019/13.1 of the Ministry of Education and Science of Russian Federation).
D.M. Stull was supported by Inria post-doc program.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abramsky, S.: Domain theory. In: Abramsky, S., Gabbay, D., Maibaum, T.S.E. (eds.) Handbook of Logic in Computer Science. Clarendon Press, Oxford (1994)
Becher, V., Grigorieff, S.: Borel and Hausdorff hierarchies in topological spaces of choquet games and their effectivization. Math. Struct. Comput. Sci. 25(7), 1490–1519 (2015). https://doi.org/10.1017/S096012951300025X
de Brecht, M.: Quasi-polish spaces. Ann. Pure Appl. Logic 164(3), 356–381 (2013)
Brecht de, M., Pauly, A., Schröder, M.: Overt choice. CoRR abs/1902.05926 (2019). http://arxiv.org/abs/1902.05926
Chen, R.: Notes on quasi-Polish spaces. CoRR abs/1902.05926 (2018). http://arxiv.org/abs/1809.07440
Gao, S.: Invariant Descriptive Set Theory. CRC Press, New York (2009)
Gregoriades, V.: Classes of polish spaces under effective Borel isomorphism. Mem. Amer. Math. Soc. 240(1135) (2016). https://doi.org/10.1090/memo/1135
Gregoriades, V., Kispéter, T., Pauly, A.: A comparison of concepts from computable analysis and effective descriptive set theory. Math. Struct. Comput. Sci. 27(8), 1414–1436 (2017). https://doi.org/10.1017/S0960129516000128
Grubba, T., Schröder, M., Weihrauch, K.: Computable metrization. MLQ Math. Log. Q. 53(4–5), 381–395 (2007). https://doi.org/10.1002/malq.200710009
Hoyrup, M.: Genericity of weakly computable objects. Theory Comput. Syst.60(3), 396–420 (2017). https://doi.org/10.1007/s00224-016-9737-6
Kechris, A.S.: Classical Descriptive Set Theory, GTM, vol. 156. Springer, New York (1995). https://doi.org/10.1007/978-1-4612-4190-4
Korovina, M.V., Kudinov, O.V.: Towards computability over effectively enumerable topological spaces. Electron. Notes Theor. Comput. Sci. 221, 115–125 (2008). https://doi.org/10.1016/j.entcs.2008.12.011
Korovina, M., Kudinov, O.: On higher effective descriptive set theory. In: Kari, J., Manea, F., Petre, I. (eds.) CiE 2017. LNCS, vol. 10307, pp. 282–291. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-58741-7_27
Louveau, A.: Recursivity and compactness. In: Müller, G.H., Scott, D.S. (eds.) Higher Set Theory. LNM, vol. 669, pp. 303–337. Springer, Heidelberg (1978). https://doi.org/10.1007/BFb0103106
Moschovakis, Y.N.: Descriptive Set Theory. Mathematical Surveys and Monographs, Second edition. American Mathematical Society (2009). http://www.math.ucla.edu/~ynm/lectures/dst2009/dst2009.pdf
Rogers Jr., H.: Theory of Recursive Functions and Effective Computability. MIT Press, Cambridge (1987). https://mitpress.mit.edu/books/theory-recursive-functions-and-effective-computability. (Reprint from 1967)
Selivanov, V.: On index sets in the Kleene-Mostowski hierarchy. Trans. Inst. Math. 2, 135–158 (1982). in Russian
Selivanov, V.L.: Towards a descriptive set theory for domain-like structures. Theoret. Comput. Sci. 365(3), 258–282 (2006). https://doi.org/10.1016/j.tcs.2006.07.053
Selivanov, V.L.: On the difference hierarchy in countably based T\({}_{\text{0}}\)-spaces. Electron. Notes Theor. Comput. Sci. 221, 257–269 (2008). https://doi.org/10.1016/j.entcs.2008.12.022
Selivanov, V.: Towards the effective descriptive set theory. In: Beckmann, A., Mitrana, V., Soskova, M. (eds.) CiE 2015. LNCS, vol. 9136, pp. 324–333. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-20028-6_33
Weihrauch, K.: Computable Analysis. Springer, Heidelberg (2000). https://doi.org/10.1007/978-3-642-56999-9
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 IFIP International Federation for Information Processing
About this paper
Cite this paper
Hoyrup, M., Rojas, C., Selivanov, V., Stull, D.M. (2019). Computability on Quasi-Polish Spaces. In: Hospodár, M., Jirásková, G., Konstantinidis, S. (eds) Descriptional Complexity of Formal Systems. DCFS 2019. Lecture Notes in Computer Science(), vol 11612. Springer, Cham. https://doi.org/10.1007/978-3-030-23247-4_13
Download citation
DOI: https://doi.org/10.1007/978-3-030-23247-4_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-23246-7
Online ISBN: 978-3-030-23247-4
eBook Packages: Computer ScienceComputer Science (R0)