Hostname: page-component-586b7cd67f-t8hqh Total loading time: 0 Render date: 2024-11-25T14:06:17.607Z Has data issue: false hasContentIssue false
  • English
  • Français

Towards a descriptive theory of cb0-spaces

Published online by Cambridge University Press:  09 June 2016

VICTOR SELIVANOV
VICTOR SELIVANOV*
Affiliation:
A.P. Ershov Institute of Informatics Systems SB RAS and Novosibirsk State University, Novosibirsk, Russia Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The paper tries to extend some results of the classical Descriptive Set Theory to as many countably based T0-spaces (cb0-spaces) as possible. Along with extending some central facts about Borel, Luzin and Hausdorff hierarchies of sets we also consider the more general case of k-partitions. In particular, we investigate the difference hierarchy of k-partitions and the fine hierarchy closely related to the Wadge hierarchy.

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 27 , Special Issue 8: Continuity, Computability, Constructivity: From Logic to Algorithms 2013 , December 2017 , pp. 1553 - 1580
Copyright
Copyright © Cambridge University Press 2016 

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–3) 2–32.CrossRefGoogle Scholar
Andretta, A. and Martin, D.A. (2003). Borel-Wadge degrees. Fundamenta Mathematicae 177 (2) 175–192.CrossRefGoogle Scholar
de Brecht, M. (2013). Quasi-Polish spaces. Annals of Pure and Applied Logic 164 (3) 356–381.CrossRefGoogle Scholar
de Brecht, M. and Yamamoto, A. (2009). Σ0 α-admissible representations (Extended Abstract). In: Bauer, A., Hertling, P. and Ko, K.-I. (eds.) Proceedings of 6th International Conference on Computability and Complexity in Analysis. OASICS 11, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik.Google Scholar
Duparc, J. (2001). Wadge hierarchy and Veblen hierarchy. Part I: Borel sets of finite rank. Journal of Symbolic Logic 66 (1) 56–86.CrossRefGoogle Scholar
Engelking, R. (1989). General Topology, Heldermann.Google Scholar
Friedman, S.D., Hyttinen, T. and Kulikov, V. (2014). Generalized descriptive set theory and classification theory. Memoirs of the American Mathematical Society 230 (1081) 1–80.Google Scholar
Gierz, G., Hofmann, K.H., Keimel, K., Lawson, J.D., Mislove, M.W. and Scott, D.W. (2003). Continuous Lattices and Domains, Cambridge University Press.CrossRefGoogle Scholar
Hertling, P. (1993). Topologische Komplexitätsgrade von Funktionen mit endlichem Bild. Informatik-Berichte 152, 34 pages, Fernuniversität Hagen, December.Google Scholar
Hertling, P. (1996). Unstetigkeitsgrade von Funktionen in der effektiven Analysis. Ph.D. Thesis, Fachbereich Informatik, FernUniversität Hagen, 1996.Google Scholar
Jayne, J.E. and Rogers, C.A. (1982). First level Borel functions and isomorphisms. Journal de Mathematiques Pures et Appliquees 61 (2) 177–205.Google Scholar
Kechris, A.S. (1983). Suslin cardinals, k-Suslin sets and the scale property in the hyperprojective hierarchy. In: Kechris, A.S., Löwe, B. and Steel, J.R. (eds.) The Cabal Seminar, v. 1: Games, Scales and Suslin Cardinals, Lecture Notes in Logic, volume 31, 2008, 314–332. (Reprinted from Lecture Notes in Mathematics, No 1019, Springer).Google Scholar
Kechris, A.S. (1995). Classical Descriptive Set Theory, Springer.Google Scholar
Kreitz, C. and Weihrauch, K. (1985). Theory of representations. Theoretical Computer Science 38 35–53.Google Scholar
Kruskal, J.B. (1972). The theory of well-quasi-ordering: A frequently discovered concept. Journal of Combinatorics Th.(A) 13 (3) 297–305.Google Scholar
Louveau, A. (1983). Some results in the Wadge hierarchy of Borel sets. Lecutre Notes in Mathematics 1019 28–55.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., Schlicht, P. and Selivanov, V. (2015). Wadge-like reducibilities on arbitrary quasi-Polish spaces. Mathematical Structures in Computer Science 25 (8) 1705–1754.CrossRefGoogle 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.CrossRefGoogle Scholar
Pauly, A. (2012). A new introduction to the theory of represented spaces, arXiv:1204.3763.Google Scholar
Pauly, A. and de Brecht, M. (2013). Towards synthetic descriptives set theory: An instantiation with represented spaces, arXiv:1307.1850.Google Scholar
Saint Raymond, J. (2007). Preservation of the Borel class under countable-compact-covering mappings. Topology and its Applications 154 (8) 1714–1725.Google Scholar
Schröder, M. (2002). Extended admissibility. Theoretical Computer Science 284 (2) 519–538.CrossRefGoogle Scholar
Schröder, M. (2003). Admissible Representations for Continuous Computations, Ph.D. Thesis, Fachbereich Informatik, FernUniversität Hagen, 2003.Google Scholar
Schröder, M. and Selivanov, V. (2015). Some hierarchies of qcb0-spaces. Mathematical Structures in Computer Science 25 (8) 1799–1823.Google Scholar
Schröder, M. and Selivanov, V. (2015). Hyperprojective hierarchy of qcb0-spaces. Computability 4 (1) 1–17.CrossRefGoogle Scholar
Selivanov, V.L. (1983). Hierarchies of hyperarithmetical sets and functions. Algebra and Logic 22 (6) 473–491.Google Scholar
Selivanov, V.L. (2004). Difference hierarchy in ϕ-spaces. Algebra and Logic 43 (4) 238–248.CrossRefGoogle Scholar
Selivanov, V.L. (2005a). Variations on the Wadge reducibility. Siberian Advances in Mathematics 15 (3) 44–80.Google Scholar
Selivanov, V.L. (2005b). Hierarchies in ϕ-spaces and applications. Mathematical Logic Quarterly 51 (1) 45–61.Google Scholar
Selivanov, V.L. (2006). Towards a descriptive set theory for domain-like structures. Theoretical Computer Science 365 (2) 258–282.CrossRefGoogle Scholar
Selivanov, V.L. (2007a). The quotient algebra of labeled forests modulo h-equivalence. Algebra and Logic 46 (2) 120–133.Google Scholar
Selivanov, V.L. (2007b). 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). Fine hierarchies and m-reducibilities in theoretical computer science. Theoretical Computer Science 405 (1–2) 116–163.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.L. (2011). A fine hierarchy of ω-regular k-partitions. In: Löwe, B. et al. (eds.) CiE 2011. Lecture Notes in Computer Science 6735 Springer, 260–269.Google Scholar
Selivanov, V.L. (2012). Fine hierarchies via Piestley duality. Annals of Pure and Applied Logic 163 (8) 1075–1107.CrossRefGoogle Scholar
Selivanov, V.L. (2013). Total representations. Logical Methods in Computer Science 9 (2) 1–30.Google Scholar
Steel, J. (1980). Determinateness and the separation property. Journal of Symbolic Logic 45 (1) 143–146.Google Scholar
Van Wesep, R. (1976). Wadge degrees and descriptive set theory. Lecture Notes in Mathematics 689 151–170.Google Scholar
Wadge, W. (1972). Degrees of complexity of subsets of the Baire space. Notices of the American Mathematical Society 19 714–715.Google Scholar
Wadge, W. (1984). Reducibility and Determinateness in the Baire Space, Ph.D. Thesis, University of California.Google Scholar
Weihrauch, K. (2000). Computable Analysis, Springer.Google Scholar