Variations on the Wadge Reducibility

V. L. Selivanov

Matematičeskie trudy, Tome 8 (2005) no. 1, pp. 135-175

Résumé

The Wadge reducibility in the Baire and Cantor spaces is very important in descriptive set theory. We consider the Wadge reducibility in some other topological spaces, in particular, in the $\varphi$-spaces which are topological counterparts of the algebraic directed-complete partial orderings. It turns out that the Wadge reducibility behaves worse in most spaces than in the classical case but there exist interesting examples of spaces with a better behavior as well.

Bibliographie

[1] Selivanov V. L., “O strukture stepenei nerazreshimosti indeksnykh mnozhestv”, Algebra i logika, 18:4 (1979), 463–480 | MR | Zbl

[2] Selivanov V. L., “O strukture stepenei obobschennykh indeksnykh mnozhestv”, Algebra i logika, 21:4 (1982), 472–491 | MR

[3] Selivanov V. L., “Ob indeksnykh mnozhestvakh v ierarkhii Klini — Mostovskogo”, Tr. IM SOAN SSSR, 2, Nauka, Novosibirsk, 1982, 135–158

[4] Selivanov V. L., “Indeksnye mnozhestva v giperarifmeticheskoi ierarkhii”, Sib. mat. zhurn., 25:3 (1984), 164–181 | MR | Zbl

[5] Selivanov V. L., “Bulevy ierarkhii razbienii nad redutsiruemoi bazoi”, Algebra i logika, 43:1 (2004), 77–109 | MR | Zbl

[6] Selivanov V. L., “Raznostnaya ierarkhiya v $\varphi$-prostranstvakh”, Algebra i logika, 43:4 (2004), 425–444 | MR | Zbl

[7] Selivanov V. L., “O klassifikatsii schetnykh bulevykh termov”, Algebra i logika, 44:2 (2005), 173–197 | MR | Zbl

[8] Bauer A., The Realizability Approach to Computable Analysis and Topology, Ph.D. Thesis, Carnegie Mellon University, Campus Printing, 2000

[9] Duparc J., “Wadge hierarchy and Veblen hierarchy: Part I: Borel sets of finite rank”, J. Symbol Logic, 66:1 (2001), 56–86 | DOI | MR | Zbl

[10] Ershov Yu. L., “Theory of domains and nearby”, Lecture Notes of Computer Science, 735 (1993), 1–7 | DOI | MR

[11] Giertz G., Hoffmann K. H., Keimel K., Lawson J. D., Mislove M. W., and Scott D. S., Continuous Lattices and Domains, Cambridge University Press, Cambridge, 2003 | MR

[12] Hemmerling A., Approximate Decidability in Euclidean Spaces, Preprint-Reihe Mathematik, N 17, Universitat Greifswald, Greifswald, 2001

[13] Hertling P., Unstetigkeitsgrade von Funktionen in der Effectiven Analysis, Ph.D. Thesis Informatik-Berichte208-11, Fern Universität Hagen, Hagen, 1996

[14] Kechris A. S., Classical Descriptive Set Theory, Springer-Verlag, Berlin, 1995 | MR

[15] Scott D., “Continuous lattices”, Lecture Notes in Math., 274, Springer-Verlag, Berlin, 1972, 97–136 | MR

[16] Selivanov V. L., “Fine hierarchies and Boolean terms”, J. Symbol. Logic, 60 (1995), 289–317 | DOI | MR | Zbl

[17] Tang A., “Chain properties in $P\omega$”, Theoret. Comput. Sci., 9 (1979), 153–172 | DOI | MR | Zbl

[18] Tang A., “Wadge reducibility and Hausdorff difference hierarchy in $P\omega$”, Continuous Lattices, Lecture Notes in Math., 871, Springer-Verlag, Berlin, 1981, 360–371

[19] Wadge W., “Degrees of complexity of subsets of the Baire space”, Notices Amer. Math. Soc., A 714 (1972)

[20] Wadge W., Reducibility and Determinateness in the Baire Space, Ph.D. Thesis, Univ. of California, Berkeley, 1984

[21] Weihrauch K., Computable Analysis, Springer-Verlag, Berlin, 2000 | MR | Zbl

[22] van Wesep R., “Wadge degrees and descriptive set theory”, Lecture Notes in Math., 689, Springer-Verlag, Berlin, 1978, 151–170 | MR