Wadge-like reducibilities on arbitrary quasi-Polish spaces

DOI10.1017/S0960129513000339zbMATH Open1362.03042arXiv1204.5338OpenAlexW3103691847MaRDI QIDQ5740679FDOQ5740679

Authors: Luca Motto Ros, Philipp Schlicht, Victor Selivanov 

Publication date: 27 July 2016

Published in: Mathematical Structures in Computer Science (Search for Journal in Brave)

Abstract: The structure of the Wadge degrees on zero-dimensional spaces is very simple (almost well-ordered), but for many other natural non-zero-dimensional spaces (including the space of reals) this structure is much more complicated. We consider weaker notions of reducibility, including the so-called Delta^0_alpha-reductions, and try to find for various natural topological spaces X the least ordinal alpha_X such that for every alpha_X leq �eta < omega_1 the degree-structure induced on X by the Delta^0_�eta-reductions is simple (i.e. similar to the Wadge hierarchy on the Baire space). We show that alpha_X leq {omega} for every quasi-Polish space X, that alpha_X leq 3 for quasi-Polish spaces of dimension different from infty, and that this last bound is in fact optimal for many (quasi-)Polish spaces, including the real line and its powers.

Full work available at URL: https://arxiv.org/abs/1204.5338

Recommendations

• A Wadge hierarchy for second countable spaces
• Continuous reducibility and dimension of metric spaces
• Reducibility by continuous functions and Wadge degrees
• Effective wadge hierarchy in computable quasi-Polish spaces
• Variations of Wadge reducibility

Mathematics Subject Classification ID

Descriptive set theory (03E15) Other degrees and reducibilities in computability and recursion theory (03D30)

Cites Work

• Title not available (Why is that?)
• Continuous Lattices and Domains
• Wadge reducibility and infinite computations
• Weihrauch degrees, omniscience principles and weak computability
• Effective Choice and Boundedness Principles in Computable Analysis
• Undecidability in Weihrauch degrees
• Hierarchies of Δ⁰₂‐measurable k ‐partitions
• Quasi-Polish spaces
• Baire reductions and good Borel reducibilities
• A Gandy theorem for abstract structures and applications to first-order definability
• Definability in the \(h\)-quasiorder of labeled forests
• Definability in the Homomorphic Quasiorder of Finite Labeled Forests
• Borel-amenable reducibilities for sets of reals
• Borel–Wadge degrees
• \(\sigma\)-homogeneity of Borel sets
• Beyond Borel-amenability: scales and superamenable reducibilities
• Game representations of classes of piecewise definable functions
• Decomposing Borel sets and functions and the structure of Baire class 1 functions
• On the Structure of Finite Level and ω-Decomposable Borel Functions
• Decomposing Borel functions and structure at finite levels of the Baire hierarchy
• A new proof of a theorem of Jayne and Rogers
• More on Wadge determinacy
• On the Wadge reducibility of \(k\)-partitions
• Borel isomorphisms at the first level—I
• On the difference hierarchy in countably based \(T_{0}\)-spaces
• Borel isomorphisms at the first level, II

Cited In (25)

• Continuous reducibility and dimension of metric spaces
• The Wadge order on the Scott domain is not a well-quasi-order
• Wadge-like degrees of Borel bqo-valued functions
• On the main scientific achievements of Victor Selivanov
• Towards a descriptive theory of cb\(_{0}\)-spaces
• Effective wadge hierarchy in computable quasi-Polish spaces
• Game characterizations and lower cones in the Weihrauch degrees
• Game characterizations and lower cones in the Weihrauch degrees
• Borel-piecewise continuous reducibility for uniformization problems
• Variations of Wadge reducibility
• A comparison of concepts from computable analysis and effective descriptive set theory
• Decomposing Borel functions using the Shore-Slaman join theorem
• Borel subsets of the real line and continuous reducibility
• The Wadge hierarchy on Zariski topologies
• Regular tree languages in low levels of the Wadge hierarchy
• Descriptive set theory, from Cantor to Wadge and beyond
• A Wadge hierarchy for second countable spaces
• Wadge hardness in Scott spaces and its effectivization
• Well-Quasi Orders and Hierarchy Theory
• On the widest class of completeness-preserving covering maps
• Point Degree Spectra of Represented Spaces
• Descriptive complexity of \(\mathsf{qc} \mathsf{b}_0\)-spaces
• Towards the Effective Descriptive Set Theory
• Bad Wadge-like reducibilities on the Baire space
• Input-driven pushdown automata on well-nested infinite strings

This page was built for publication: Wadge-like reducibilities on arbitrary quasi-Polish spaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5740679)