THE DISCONTINUITY PROBLEM

DOI10.1017/JSL.2021.106MaRDI QIDQ6095979zbMATH OpenOpenAlexFDO

Authors Vasco Brattka

Publication date 11 September 2023

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

axiom of determinacycomputability theorycomputable analysiseffective discontinuitygamesWeihrauch complexity

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) Axiom of choice and related propositions (03E25) Determinacy principles (03E60) 2-person games (91A05)

Abstract: Matthias Schr"oder has asked the question whether there is a weakest discontinuous problem in the continuous version of the Weihrauch lattice. Such a problem can be considered as the weakest unsolvable problem. We introduce the discontinuity problem, and we show that it is reducible exactly to the effectively discontinuous problems, defined in a suitable way. However, in which sense this answers Schr"oder's question sensitively depends on the axiomatic framework that is chosen, and it is a positive answer if we work in Zermelo-Fraenkel set theory with dependent choice and the axiom of determinacy AD. On the other hand, using the full axiom of choice, one can construct problems which are discontinuous, but not effectively so. Hence, the exact situation at the bottom of the Weihrauch lattice sensitively depends on the axiomatic setting that we choose. We prove our result using a variant of Wadge games for mathematical problems. While the existence of a winning strategy for player II characterizes continuity of the problem (as already shown by Nobrega and Pauly), the existence of a winning strategy for player I characterizes effective discontinuity of the problem. By Weihrauch determinacy we understand the condition that every problem is either continuous or effectively discontinuous. This notion of determinacy is a fairly strong notion, as it is not only implied by the axiom of determinacy AD, but it also implies Wadge determinacy. We close with a brief discussion of generalized notions of productivity.

Recommendations

• On the problem of discontinuity at fixed point
• The Continuum Problem
• The Continuumproblem
• Problems with free discontinuities
• On discontinuity problem at fixed point
• scientific article; zbMATH DE number 1785554
• Discontinuity and fixed points
• On discontinuity and fixed points

Cites work

• A topological view on algebraic computation models
• Completion of choice
• Creative sets
• Descriptive set theory
• Equivalence between Wadge and Lipschitz determinacy
• Game characterizations and lower cones in the Weihrauch degrees
• scientific article; zbMATH DE number 3172716 (Why is no real title available?)
• scientific article; zbMATH DE number 3987247 (Why is no real title available?)
• scientific article; zbMATH DE number 473381 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• scientific article; zbMATH DE number 1099350 (Why is no real title available?)
• scientific article; zbMATH DE number 1460545 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• More on Wadge determinacy
• On the (semi)lattices induced by continuous reducibilities
• On the axiom of determinateness
• Productive Sets
• Recursively enumerable sets of positive integers and their decision problems
• Stashing and parallelization pentagons
• Theory of representations
• Topological games: on the 50th anniversary of the Banach-Mazur game
• Turing computability. Theory and applications
• Type 2 recursion theory
• Weihrauch Complexity in Computable Analysis
• Weihrauch goes Brouwerian

Cited in

(7)

• The generalized problem of breakup of an arbitrary discontinuity
• Discontinuity of geometric expansions
• scientific article; zbMATH DE number 218120 (Why is no real title available?)
• The Continuumproblem
• On the complexity of learning programs
• Mathematical logic: proof theory, constructive mathematics. Abstracts from the workshop held November 12--17, 2023
• Sequential discontinuity and first-order problems

This page was built for publication: THE DISCONTINUITY PROBLEM

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