Hostname: page-component-78c5997874-s2hrs Total loading time: 0 Render date: 2024-11-08T13:26:24.329Z Has data issue: false hasContentIssue false
  • English
  • Français

A Q-WADGE HIERARCHY IN QUASI-POLISH SPACES

Part of: Partial differential equations on manifolds; differential operators Computability and recursion theory Partial differential equations, initial value and time-dependent initial-boundary value problems

Published online by Cambridge University Press:  05 October 2020

VICTOR SELIVANOV
VICTOR SELIVANOV*
Affiliation:
A.P. ERSHOV INSTITUTE OF INFORMATICS SYSTEMS SB RAS AC. LAVRENTYEV AVE. 6, NOVOSIBIRSK, 630090, RUSSIAE-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

The Wadge hierarchy was originally defined and studied only in the Baire space (and some other zero-dimensional spaces). Here we extend the Wadge hierarchy of Borel sets to arbitrary topological spaces by providing a set-theoretic definition of all its levels. We show that our extension behaves well in second countable spaces and especially in quasi-Polish spaces. In particular, all levels are preserved by continuous open surjections between second countable spaces which implies e.g., several Hausdorff–Kuratowski (HK)-type theorems in quasi-Polish spaces. In fact, many results hold not only for the Wadge hierarchy of sets but also for its extension to Borel functions from a space to a countable better quasiorder Q.

Keywords

Borel hierarchyWadge hierarchyfine hierarchyiterated labeled treeh-quasiorderbetter quasiorderQ-partition

MSC classification

Primary: 03D15: Complexity of computation (including implicit computational complexity)
Secondary: 03D78: Computation over the reals 58J45: Hyperbolic equations 65M06: Finite difference methods 65M25: Method of characteristics
Type
Article
Information
The Journal of Symbolic Logic , Volume 87 , Issue 2 , June 2022 , pp. 732 - 757
Check for updates
Copyright
© The Author(s), 2020. Published by Cambridge University Press on behalf of The Association for Symbolic Logic

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

Becher, V. and Grigorieff, S., Wadge hardness in scott spaces and its effectivization . Mathematical Structures in Computer Science , vol. 25 (2015), no. 7, pp. 1520–1545.CrossRefGoogle Scholar
Brattka, V. and Hertling, P., Topological properties of real number representations . Theoretical Computer Science , vol. 284 (2002), pp. 241–257.CrossRefGoogle Scholar
Chen, R., Notes on quasi-polish spaces, preprint, 2019, arXiv 1809.07440.Google Scholar
de Brecht, M., Quasi-polish spaces . Annals of Pure and Applied Logic , vol. 164 (2013), pp. 356–381.CrossRefGoogle Scholar
Duparc, J. and Vuilleumier, L., The Wadge order on the scott domain is not a well-quasi-order , this Journal , vol. 85 (2020), no. 1, pp. 300–324.Google Scholar
Engelking, R., General Topology , Heldermann, Berlin, 1989.Google Scholar
Hertling, P., Topologische Komplexitätsgrade von Funktionen mit endlichem Bild, Technical report, vol. 152, Fernuniversität Hagen, Hagen, Germany, 1993.Google Scholar
Hertling, P., Unstetigkeitsgrade von Funktionen in der effektiven Analysis, Ph.D. thesis, Fachbereich Informatik, FernUniversität Hagen, 1996.Google Scholar
Kechris, A. S. , Classical Descriptive Set Theory , Springer, New York, 1995.CrossRefGoogle Scholar
Kechris, A. S., Löwe, B., and Steel, J. R. (eds.), Wadge Degrees and Projective Ordinals: The Cabal Seminar, Volume II , Lecture Notes in Logic, vol. 37,Cambridge University Press, Cambridge, 2012.Google Scholar
Kihara, T. and Montalbán, A., On the structure of the wadge degrees of bqo-valued borel functions . Transactions of the American Mathematical Society , vol. 371 (2019), no. 11, pp. 7885–7923.10.1090/tran/7621CrossRefGoogle Scholar
Kihara, T. and Selivanov, V., Wadge-like degrees of borel bqo-valued functions, submitted, 2019, Arxiv 1909.10835.Google Scholar
Kuratowski, K. and Mostowski, A., Set Theory , North Holland, Amsterdam, 1967.Google Scholar
Laver, R., Better-quasi-orderings and a class of trees , Studies in Foundations and Combinatorics (Rota, G.-C., editor), Advances in Mathematics Supplementary Series 1, vol. 37, Academic Press, New York, NY, 1978, pp. 31–48.Google Scholar
Louveau, A., Some results in the wadge hierarchy of borel sets , Wadge Degrees and Projective Ordinals: The Cabal Seminar, Volume II (Kechris, A.S., Lowe, B., and Steel, J.R., editors), Lecture Notes in Logic, vol. 37, Cambridge University Press, Cambridge, 2012, pp. 47–73.Google Scholar
Pequignot, Y., A Wadge hierarchy for second countable spaces . Archive for Mathematical Logic , vol. 54 (2015), no. 5-6, pp. 659–683.10.1007/s00153-015-0434-yCrossRefGoogle Scholar
Saint Raymond, J., Preservation of the Borel class under countable-compact-covering mappings . Topology and Its Applications , vol. 154 (2007), pp. 1714–1725.CrossRefGoogle Scholar
Selivanov, V. L., Fine hierarchies and boolean terms , this Journal , vol. 60 (1995), no. 1, pp. 289–317.Google Scholar
Selivanov, V. L., Variations on wadge reducibility . Siberian Advances in Mathematics , vol. 15 (2005), no. 3, pp. 44–80.Google Scholar
Selivanov, V. L., Towards a descriptive set theory for domain-like structures . Theoretical Computer Science , vol. 365 (2006), pp. 258–282.CrossRefGoogle Scholar
Selivanov, V. L., Hierarchies of ${\varDelta}_2^0$ -measurable $k$ -partitions . Mathematical Logic Quarterly , vol. 53 (2007), pp. 446–461.10.1002/malq.200710011CrossRefGoogle Scholar
Selivanov, V. L., The quotient algebra of labeled forests modulo h-equivalence . Algebra and Logic , vol. 46 (2007), no. 2, pp. 120–133.CrossRefGoogle Scholar
Selivanov, V. L., Fine hierarchies and $m$ -reducibilities in theoretical computer science . Theoretical Computer Science , vol. 405 (2008), pp. 116–163.CrossRefGoogle Scholar
Selivanov, V. L., Fine hierarchies via priestley duality . Annals of Pure and Applied Logic , vol. 163 (2012), pp. 1075–1107.10.1016/j.apal.2011.12.029CrossRefGoogle Scholar
Selivanov, V. L., Total representations . Logical Methods in Computer Science , vol. 9 (2013), no. 2, pp. 1–30.CrossRefGoogle Scholar
Selivanov, V. L., Extending wadge theory to k-partitions , Proceedings of Computability in Europe-2017 (Kari, Jarkko, Manea, Florin, and Petre, Ion, editors), Lecture Notes in Computer Science, vol. 10307, Springer, New York, 2017, pp. 389–399.Google Scholar
Selivanov, V. L., Towards a descriptive theory of cb0-spaces . Mathematical Structures in Computer Science , vol. 28 (2017), pp. 1553–1580, Earlier version: ArXiv 1406.3942v1, 2014.10.1017/S0960129516000177CrossRefGoogle Scholar
Selivanov, V. L., Effective wadge hierarchy in computable quasi-polish spaces, submitted, 2019, Arxiv 1910.13220.Google Scholar
Simpson, S. G., Bqo-theory and fraïssé conjecture , Recursive Aspects of Descriptive Set Theory (Mansfield, Richard and Weitkamp, Galen, editors), Oxford University Press, New York, 1985.Google Scholar
Steel, J., Determinateness and the separation property , this Journal , vol. 45 (1980), pp. 143–146.Google Scholar
van Engelen, A. J. M., Homogeneous Sero-Dimensional Absolute Borel Sets , Center for Mathematics and Computer Science, Amsterdam, 1986.Google Scholar
van Engelen, F., Miller, A., and Steel, J., Rigid Borel sets and better quasiorder theory . Contemporary Mathematics , vol. 65 (1987), pp. 199–222.10.1090/conm/065/891249CrossRefGoogle Scholar
Wadge, W., Degrees of complexity of subsets of the Baire space . Notices of the American Mathematical Society , vol. 19 (1972), pp. 714–715.Google Scholar
Wadge, W., Reducibility and determinateness in the baire space , Ph.D. thesis, University of California, Berkeley, CA, 1983.Google Scholar
Weihrauch, K., Computable Analysis , Springer, Berlin, 2000.CrossRefGoogle Scholar
van Wesep, R., Wadge Degrees and Descriptive Set Theory , Lecture Notes in Mathematics, vol. 689, Springer, Berlin, 1976, pp. 151–170.Google Scholar
van Wesep, R., Separation principles and the axiom of determinateness , this Journal , vol. 43 (1978), no. 1, pp. 77–81.Google Scholar