Geodesic
Effective Wadge hierarchy in computable quasi-Polish spaces
Sibirskie èlektronnye matematičeskie izvestiâ, Tome 18 (2021) no. 1, pp. 121-135.

Voir la notice de l'article provenant de la source Math-Net.Ru

We define and study an effective version of the Wadge hierarchy in computable quasi-Polish spaces which include most spaces of interest for computable analysis. Along with hierarchies of sets we study hierarchies of $k$-partitions which are interesting on their own. We show that levels of such hierarchies are preserved by the computable effectively open surjections, that if the effective Hausdorff-Kuratowski theorem holds in the Baire space then it holds in every computable quasi-Polish space, and we extend the effective Hausdorff theorem to $k$-partitions.
Keywords: computable quasi-Polish space, effective Wadge hierarchy, fine hierarchy, preservation property, effective Hausdorff theorem.
Mots-clés : $k$-partition 
@article{SEMR_2021_18_1_a2,
     author = {V. L. Selivanov},
     title = {Effective {Wadge} hierarchy in computable {quasi-Polish} spaces},
     journal = {Sibirskie \`elektronnye matemati\v{c}eskie izvesti\^a},
     pages = {121--135},
     publisher = {mathdoc},
     volume = {18},
     number = {1},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a2/}
}
TY  - JOUR
AU  - V. L. Selivanov
TI  - Effective Wadge hierarchy in computable quasi-Polish spaces
JO  - Sibirskie èlektronnye matematičeskie izvestiâ
PY  - 2021
SP  - 121
EP  - 135
VL  - 18
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a2/
LA  - en
ID  - SEMR_2021_18_1_a2
ER  - 
%0 Journal Article
%A V. L. Selivanov
%T Effective Wadge hierarchy in computable quasi-Polish spaces
%J Sibirskie èlektronnye matematičeskie izvestiâ
%D 2021
%P 121-135
%V 18
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a2/
%G en
%F SEMR_2021_18_1_a2
V. L. Selivanov. Effective Wadge hierarchy in computable quasi-Polish spaces. Sibirskie èlektronnye matematičeskie izvestiâ, Tome 18 (2021) no. 1, pp. 121-135. http://geodesic.mathdoc.fr/item/SEMR_2021_18_1_a2/

[1] A. Callard, M. Hoyrup, “Descriptive complexity on non-Polish spaces”, 37th International Symposium on Theoretical Aspects of Computer Science 2020, LIPIcs, 154, 2020, 8:1–8:16 | MR

[2] M. de Brecht, “Quasi-Polish spaces”, Ann. Pure Appl. Logic, 164:3 (2013), 356–381 | DOI | MR | Zbl

[3] M. de Brecht, A. Pauly, M. Schröder, “Overt choice”, Computability, 9:3-4 (2020), 169–191 | DOI | MR | Zbl

[4] P. Hertling, “An effective Riemann Mapping Theorem”, Theor. Comput. Sci., 219:1-2 (1999), 225–265 | DOI | MR | Zbl

[5] M. Hoyrup, C. Rojas, V. Selivanov, D. Stull, “Computability on quasi-Polish spaces”, Proc. of DCFS-2019, LNCS, 11612, Springer, Berlin, 2019, 171–183 | MR | Zbl

[6] A.S. Kechris, Classical descriptive set theory, Graduate Texts in Mathematics, 156, Springer, Berlin, 1995 | DOI | MR | Zbl

[7] M.V. Korovina, O.V. Kudinov, “On higher effective descriptive set theory”, CiE-2017, LNCS, 10307, Springer, Berlin, 2017, 282–291 | MR | Zbl

[8] T. Kihara, A. Montalbán, “On the structure of the Wadge degrees of bqo-valued Borel functions”, Trans. Am. Math. Soc., 371:11 (2019), 7885–7923 | DOI | MR | Zbl

[9] A. Louveau, “Recursivity and compactness”, Higher Set Theory, Proc. (Oberwolfach 1977), Lect. Notes Math., 669, 1978, 303–337 | DOI | MR | Zbl

[10] Y.N. Moschovakis, Descriptive set theory, Mathematical Surveys and Monographs, 155, AMS, Providence, 2009 | DOI | MR | Zbl

[11] A. Pauly, Computability on the space of countable ordinals, 2017, arXiv: 1501.00386v3

[12] H. Rogers, jun., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967 | MR | Zbl

[13] V.L. Selivanov, “Hierarchies of hyperarithmetical sets and functions”, Algebra Logika, 22:6 (1983), 666–692 | DOI | MR | Zbl

[14] V.L. Selivanov, “Fine hierarchy of regular $\omega$-languages”, Theor. Comput. Sci., 191:1-2 (1998), 37–59 | DOI | MR | Zbl

[15] V.L. Selivanov, “Wadge degrees of $\omega$-languages of deterministic Turing machines”, Theor. Inform. Appl., 37:1 (2003), 67–83 | DOI | MR | Zbl

[16] V.L. Selivanov, “Towards a descriptive set theory for domain-like structures”, Theor. Comput. Sci., 365:3 (2006), 258–282 | DOI | MR | Zbl

[17] V.L. Selivanov, “Fine hierarchies and $m$-reducibilities in theoretical computer science”, Theor. Comput. Sci., 405:1-2 (2008), 116–163 | DOI | MR | Zbl

[18] V.L. Selivanov, “Fine hierarchies via Priestley duality”, Ann. Pure Appl. Logic, 163:8 (2012), 1075–1107 | DOI | MR | Zbl

[19] V.L. Selivanov, “Total representations”, Log. Methods Comput. Sci., 9:2 (2013), 5 | DOI | MR | Zbl

[20] V.L. Selivanov, “Towards the effective descriptive set theory”, Proc. CiE 2015, LNCS, 9136, Springer, Berlin, 2015, 324–333 | MR | Zbl

[21] V.L. Selivanov, “Towards a descriptive theory of $cb_0$-spaces”, Math. Struct. Comput. Sci., 27:8 (2017), 1553–1580 | DOI | MR | Zbl

[22] V. Selivanov, “A $Q$-Wadge hierarchy in quasi-Polish spaces”, The Journal of Symbolic Logic, 2020, 1–27, arXiv: 1911.02758v1 | DOI

[23] J. Saint Raymond, “Preservation of the Borel class under countable-compact-covering mappings”, Topology Appl., 154:8 (2007), 1714–1725 | DOI | MR | Zbl

[24] K. Wagner, “On $\omega$-regular sets”, Inf. Control, 43 (1979), 123–177 | DOI | MR | Zbl

[25] K. Weihrauch, Computable Analysis, Springer, Berlin, 2000 | MR | Zbl

[26] M. Ziegler, “Effectively open real functions”, J. Complexity, 22:6 (2006), 827–849 | DOI | MR | Zbl