Borel-piecewise continuous reducibility for uniformization problems

DOI10.2168/LMCS-12(4:4)2016MaRDI QIDQ2974788zbMATH OpenFDO

Authors Takayuki Kihara

Publication date 11 April 2017

Published in Logical Methods in Computer Science (Search for Journal in Brave)

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

zbMATH Keywords

Muchnik degreepiecewise continuitypriority argumentselectionWeihrauch degree

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30) Computation over the reals, computable analysis (03D78) Descriptive set theory (03E15) Constructive and recursive analysis (03F60)

Abstract: We study a fine hierarchy of Borel-piecewise continuous functions, especially, between closed-piecewise continuity and $G_{d}elta$-piecewise continuity. Our aim is to understand how a priority argument in computability theory is connected to the notion of $G_{d}elta$-piecewise continuity, and then we utilize this connection to obtain separation results on subclasses of $G_{d}elta$-piecewise continuous reductions for uniformization problems on set-valued functions with compact graphs. This method is also applicable for separating various non-constructive principles in the Weihrauch lattice.

Recommendations

• Three topological reducibilities for discontinuous functions
• On the (semi)lattices induced by continuous reducibilities
• Effective Borel measurability and reducibility of functions
• Effective Choice and Boundedness Principles in Computable Analysis
• Inside the Muchnik degrees. I: Discontinuity, learnability and constructivism

Cites work

• A hierarchy of immunity and density for sets of reals
• Approximately differentiable functions: The r-topology
• Bad Wadge-like reducibilities on the Baire space
• Baire reductions and good Borel reducibilities
• Borel isomorphisms at the first level—I
• Borel-amenable reducibilities for sets of reals
• Borel–Wadge degrees
• Cohesive avoidance and strong reductions
• Computability and randomness
• Decomposing Borel functions and structure at finite levels of the Baire hierarchy
• Decomposing Borel functions using the Shore-Slaman join theorem
• Decomposing Borel sets and functions and the structure of Baire class 1 functions
• Effective Choice and Boundedness Principles in Computable Analysis
• Effective decomposition of -continuous Borel functions
• First level Borel functions and isomorphisms
• Game characterizations and lower cones in the Weihrauch degrees
• Hierarchies of function classes defined by the first-value operator
• Hierarchies of Δ⁰₂‐measurable k ‐partitions
• scientific article; zbMATH DE number 4091484 (Why is no real title available?)
• scientific article; zbMATH DE number 4108753 (Why is no real title available?)
• scientific article; zbMATH DE number 3665285 (Why is no real title available?)
• Incomputability of Simply Connected Planar Continua
• Inside the Muchnik degrees. I: Discontinuity, learnability and constructivism
• Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions
• Levels of discontinuity, limit-computability, and jump operators
• Many-one reductions and the category of multivalued functions
• More on Wadge determinacy
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On notions of computability-theoretic reduction between Π21 principles
• On some class of functions intermediate between the class B^*_1 and the family of continuous functions
• On the (semi)lattices induced by continuous reducibilities
• On the algebraic structure of Weihrauch degrees
• On the role of procrastination in machine learning
• On the Structure of Finite Level and ω-Decomposable Borel Functions
• Probabilistic computability and choice
• Survey of Measurable Selection Theorems
• The axiom of determinateness and reduction principles in the analytical hierarchy
• The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
• The infinite-dimensional topology of function spaces
• Topological complexity with continuous operations
• Wadge-like reducibilities on arbitrary quasi-Polish spaces
• Weihrauch degrees, omniscience principles and weak computability

Cited in

(5)

• On the (semi)lattices induced by continuous reducibilities
• scientific article; zbMATH DE number 4023249 (Why is no real title available?)
• Computability of Subsets of Metric Spaces
• A syntactic approach to Borel functions: some extensions of Louveau's theorem
• Weihrauch problems as containers

This page was built for publication: Borel-piecewise continuous reducibility for uniformization problems

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