Hostname: page-component-78c5997874-lj6df Total loading time: 0 Render date: 2024-11-12T20:30:22.277Z Has data issue: false hasContentIssue false
  • English
  • Français

Wadge-like reducibilities on arbitrary quasi-Polish spaces

Published online by Cambridge University Press:  10 November 2014

LUCA MOTTO ROS ,
PHILIPP SCHLICHT  and
VICTOR SELIVANOV
LUCA MOTTO ROS
Affiliation:
Abteilung für Mathematische Logik, Mathematisches Institut, Albert-Ludwigs-Universität Freiburg, Eckerstraße 1, D-79104 Freiburg im Breisgau, Germany Email: [email protected]
PHILIPP SCHLICHT
Affiliation:
Mathematisches Institut, Universität Bonn, Endenicher Allee 60, 53115 Bonn, Germany Email: [email protected]
VICTOR SELIVANOV
Affiliation:
A. P. Ershov Institute of Informatics Systems, Siberian Division Russian Academy of Sciences, Novosibirsk, Russia Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The structure of the Wadge degrees on zero-dimensional spaces is very simple (almost well ordered), but for many other natural nonzero-dimensional spaces (including the space of reals) this structure is much more complicated. We consider weaker notions of reducibility, including the so-called Δ0α-reductions, and try to find for various natural topological spaces X the least ordinal αX such that for every αX ⩽ β < ω1 the degree-structure induced on X by the Δ0β-reductions is simple (i.e. similar to the Wadge hierarchy on the Baire space). We show that αX ⩽ ω for every quasi-Polish space X, that αX ⩽ 3 for quasi-Polish spaces of dimension ≠ ∞, and that this last bound is in fact optimal for many (quasi-)Polish spaces, including the real line and its powers.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 25 , Special Issue 8: Computing with Infinite Data: Topological and Logical Foundations Part 2 , December 2015 , pp. 1705 - 1754
Copyright
Copyright © Cambridge University Press 2014 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Andretta, A. (2006) More on Wadge determinacy. Annals of Pure and Applied Logic 144 (1) 2–32.Google Scholar
Andretta, A. (2007) The SLO principle and the Wadge hierarchy. In: Foundations of the Formal Sciences V, volume 11, College Publication, London 1–38.Google Scholar
Andretta, A. and Martin, D. A. (2003) Borel-Wadge degrees. Fundamenta Mathematicae 177 (2) 175–192.Google Scholar
Brattka, V. and Gherardi, G. (2011a) Weihrauch degrees, omniscience principles and weak computability. Journal of Symbolic Logic 76 (1) 143–176.Google Scholar
Brattka, V. and Gherardi, G. (2011b) Effective choice and boundedness principles in computable analysis. Bulletin of Symbolic Logic 17 (1) 73–117.Google Scholar
Cook, H. (1967) Continua which admit only the identity mapping onto non-degenerate subcontinua. Fundamenta Mathematicae 60 241–249.Google Scholar
de Brecht, M. (2013) Quasi-Polish spaces. Annals of Pure and applied Logic 164 356–381.Google Scholar
Giertz, G., Hoffmann, K. H., Keimel, K., Lawson, J. D., Mislove, M. W. and Scott, D. S. (2003) Continuous Lattices and Domains, Cambridge.Google Scholar
Hertling, P. (1993) Topologische Komplexitätsgrade von Funktionen mit endlichem Bild. Informatik-Berichte 152, Fernuniversität Hagen.Google Scholar
Hertling, P. (1996) Unstetigkeitsgrade von Funktionen in der effektiven Analysis, Ph.D. thesis, Fachbereich Informatik, FernUniversität Hagen.Google Scholar
Hurewicz, W. and Wallman, H. (1948) Dimension theory. Princeton Mathematical Series, volume 4, Princeton University Press, Princeton, NJ.Google Scholar
Ikegami, D. (2010) Games in Set Theory and Logic, Ph.D. Thesis, University of Amsterdam.Google Scholar
Ikegami, D., Schlicht, P. and Tanaka, H. (2014) Continuous reducibility for the real line. Fundamenta Mathematicae. In press.Google Scholar
Jayne, J. E. and Rogers, C. A. (1979a) Borel isomorphisms at the first level I. Mathematika 26 (1) 125–156.Google Scholar
Jayne, J. E. and Rogers, C. A. (1979b) Borel isomorphisms at the first level II. Mathematika 26 (2) 157–179.Google Scholar
Jayne, J. E. and Rogers, C. A. (1982) First level Borel functions and isomorphisms. Journal de Mathématiques Pures et Appliquées 61 (2) 177–205.Google Scholar
Kačena, M., Motto Ros, L. and Semmes, B. (2012/2013) Some observations on ‘A new proof of a theorem of Jayne and Rogers’. Real Analysis Exchange 38 (1) 121–132.Google Scholar
Kechris, A. S. (1995) Classical descriptive set theory. Graduate Texts in Mathematics, volume 156, Springer, New York.Google Scholar
Kudinov, O. V. and Selivanov, V. L. (2007) Definability in the homomorphic quasiorder of finite labelled forests. In: Computation and Logic in the Real World, Springer Lecture Notes in Computer Science 4497 436–445.Google Scholar
Kudinov, O. V. and Selivanov, V. L. (2009) A Gandy theorem for abstract structures and applications to first-order definability. In: Mathematical Theory and Computational Practice, Springer Lecture Notes in Computer Science 5635 290–299.Google Scholar
Kudinov, O. V., Selivanov, V. L. and Zhukov, A. V. (2009) Definability in the h-quasiorder of labelled forests. Annals of Pure and Applied Logic 159 (3) 318–332.Google Scholar
Kudinov, O. V., Selivanov, V. L. and Zhukov, A. V. (2010) Undecidability in Weihrauch degrees. In: Programs, Proofs, Processes. Springer Lecture Notes in Computer Science 6158 256–265.Google Scholar
Kuratowski, K. (1934) Sur une généraliation de la notion d'homéomorphie. Fundamenta Mathematicae 22 206–220.Google Scholar
Motto Ros, L. (2009) Borel-amenable reducibilities for sets of reals. Journal of Symbolic Logic 74 (1) 27–49.Google Scholar
Motto Ros, L. (2010a) Baire reductions and good Borel reducibilities. Journal of Symbolic Logic 75 (1) 323–345.Google Scholar
Motto Ros, L. (2010b) Beyond Borel-amenability: Scales and superamenable reducibilities. Annals of Pure and Applied Logic 161 (7) 829–836.Google Scholar
Motto Ros, L. (2011) Game representations of classes of piecewise definable functions. Mathematical Logic Quarterly 57 (1) 95–112.Google Scholar
Motto Ros, L. (2013) On the structure of finite level and omega-decomposable Borel functions. Journal of Symbolic Logic 78 (4) 1257–1287.Google Scholar
Motto Ros, L. and Semmes, B. (2010) A new proof of a theorem of Jayne and Rogers. Real Analysis Exchange 35 (1) 195–203.Google Scholar
Ostrovsky, A. (2011) σ-homogeneity of Borel sets. Archive for Mathematical Logic 50 (5–6) 661–664.CrossRefGoogle Scholar
Parovičenko, I. I. (1963) A universal bicompact of weight ℵ. Doklady Akademii Nauk SSSR 150 36–39.Google Scholar
Pawlikowski, J. and Sabok, M. (2012) Decomposing Borel functions and structure at finite levels of the Baire hierarchy. Annals of Pure and Applied Logic 163 (12) 1748–1764.Google Scholar
Perrin, D. and Pin, J.-E. (2004) Infinite words. Pure and Applied Mathematics, volume 141, Elsevier.Google Scholar
Saint Raymond, J. (1976) Fonctions Boréliennes sur un quotient. Bulletin de la Société Mathématique de France 100 141–147.Google Scholar
Schlicht, P. (2014) Continuous reducibility and dimension. Archive for Mathematical Logic. In press.Google Scholar
Selivanov, V. L. (2004) Difference hierarchy in ϕ-spaces. Algebra Logika 43 (4) 425–444 (Engl. Trans.: Algebra Logic 43 (4) 238–248).Google Scholar
Selivanov, V. L. (2005) Variations on the Wadge reducibility [Translation of Mat. Tr. 8 (1), 135–175]. Siberian Advances in Mathematics 15 (3) 44–80.Google Scholar
Selivanov, V. L. (2007) Hierarchies of Δ0 2-measurable k-partitions. Mathematical Logic Quarterly 53 (4–5) 446–461.Google Scholar
Selivanov, V. L. (2008a) On the difference hierarchy in countably based T 0-spaces. Electronic Notes in Theoretical Computer Science 221 257–269.Google Scholar
Selivanov, V. L. (2008b) Wadge reducibility and infinite computations. Mathematics in Computer Science 2 5–36.Google Scholar
Selivanov, V. L. (2010) On the Wadge reducibility of k-partitions. Journal of Logic and Algebraic Programming 79 (1) 92–102.Google Scholar
Selivanov, V. (2013) Total representations. Logical Methods in Computer Science 9 (2) 1–30.Google Scholar
Semmes, B. (2009) A Game for the Borel Functions, Ph.D. Thesis, ILLC, University of Amsterdam, Holland.Google Scholar
Solecki, S. (1998) Decomposing Borel sets and functions and the structure of Baire class 1 functions. Journal of the American Mathematical Society 11 (3) 521–550.Google Scholar
van Engelen, F., Miller, A. W. and Steel, J. (1987) Rigid Borel sets and better quasi-order theory. In: Logic and Combinatorics (Arcata, California, 1985), Contemporary Mathematics 65 199–222. (American Mathematical Society, Providence, RI.)Google Scholar
Wadge, W. (1984) Reducibility and Determinateness in the Baire Space, Ph.D. thesis, University of California, Berkeley.Google Scholar
Weihrauch, K. (2000) Computable analysis, An introduction. Texts in Theoretical Computer Science. An EATCS Series, Springer, Berlin.Google Scholar