Effective Choice and Boundedness Principles in Computable Analysis
From MaRDI portal
Abstract: In this paper we study a new approach to classify mathematical theorems according to their computational content. Basically, we are asking the question which theorems can be continuously or computably transferred into each other? For this purpose theorems are considered via their realizers which are operations with certain input and output data. The technical tool to express continuous or computable relations between such operations is Weihrauch reducibility and the partially ordered degree structure induced by it. We have identified certain choice principles which are cornerstones among Weihrauch degrees and it turns out that certain core theorems in analysis can be classified naturally in this structure. In particular, we study theorems such as the Intermediate Value Theorem, the Baire Category Theorem, the Banach Inverse Mapping Theorem and others. We also explore how existing classifications of the Hahn-Banach Theorem and Weak K"onig's Lemma fit into this picture. We compare the results of our classification with existing classifications in constructive and reverse mathematics and we claim that in a certain sense our classification is finer and sheds some new light on the computational content of the respective theorems. We develop a number of separation techniques based on a new parallelization principle, on certain invariance properties of Weihrauch reducibility, on the Low Basis Theorem of Jockusch and Soare and based on the Baire Category Theorem. Finally, we present a number of metatheorems that allow to derive upper bounds for the classification of the Weihrauch degree of many theorems and we discuss the Brouwer Fixed Point Theorem as an example.
Recommendations
- Effective choice and boundedness principles in computable analysis
- On effectively computable realizations of choice functions
- Finitely bounded effective computability
- scientific article; zbMATH DE number 817189
- scientific article; zbMATH DE number 4101178
- The Effective Sequence of Uniformities and its Limit as a Methodology in Computable Analysis
- Effective domains and concrete computability: A survey
- Absolutely Non-effective Predicates and Functions in Computable Analysis
- Computability of measurable sets via effective metrics
- Computability of measurable sets via effective topologies
Cites work
- A computable version of Banach's inverse mapping theorem
- An omniscience principle, the König Lemma and the Hahn‐Banach theorem
- Berechenbare Reelle Funktionenfolgen
- Borel complexity and computability of the Hahn-Banach theorem
- Borel Complexity of Topological Operations on Computable Metric Spaces
- Computability on subsets of Euclidean space. I: Closed and compact subsets
- Computability on subsets of metric spaces.
- Computable invariance
- Constructively Complete Finite Sets
- Corrigendum to “Unique solutions”
- Degrees of members of \(\Pi_ 1^ 0\) classes
- Effective Borel degrees of some topological functions
- Effective Borel measurability and reducibility of functions
- Effective representations of the space of linear bounded operators
- How incomputable is the separable Hahn-Banach theorem?
- scientific article; zbMATH DE number 4070894 (Why is no real title available?)
- scientific article; zbMATH DE number 42077 (Why is no real title available?)
- scientific article; zbMATH DE number 1226875 (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?)
- scientific article; zbMATH DE number 2236640 (Why is no real title available?)
- Mathematics based on incremental learning -- excluded middle and inductive inference
- Omniscience principles and functions of bounded variation
- On a simple definition of computable function of a real variable‐with applications to functions of a complex variable
- On the (semi)lattices induced by continuous reducibilities
- On uniform weak König's lemma
- Plottable Real Number Functions and the Computable Graph Theorem
- Polynomials and linear transformations
- Some conservation results on weak König's lemma
- Uniform versions of some axioms of second order arithmetic
- Unique solutions
- Weihrauch degrees, omniscience principles and weak computability
Cited in
(63)- On the uniform computational content of the Baire category theorem
- Comparing representations for function spaces in computable analysis
- A topological view on algebraic computation models
- On the uniform computational content of computability theory
- Towards computable analysis on the generalised real line
- Game characterizations and lower cones in the Weihrauch degrees
- Parallelizations in Weihrauch reducibility and constructive reverse mathematics
- Completion of choice
- Using Ramsey's theorem once
- Pincherle's theorem in reverse mathematics and computability theory
- The strength of compactness in computability theory and nonstandard analysis
- Finite choice, convex choice and sorting
- Probabilistic computability and choice
- Universality, optimality, and randomness deficiency
- Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions
- Inside the Muchnik degrees. I: Discontinuity, learnability and constructivism
- A new closed graph theorem on product spaces
- On the computational content of the Brouwer fixed point theorem
- Weihrauch degrees, omniscience principles and weak computability
- Effective choice and boundedness principles in computable analysis
- Computability on the countable ordinals and the Hausdorff-Kuratowski theorem (extended abstract)
- Reverse mathematics of matroids
- The Vitali Covering Theorem in the Weihrauch Lattice
- Many-one reductions and the category of multivalued functions
- Borel-piecewise continuous reducibility for uniformization problems
- Weihrauch degrees, omniscience principles and weak computability
- Complexity issues for preorders on finite labeled forests
- Computability and analysis, a historical approach
- The Brouwer fixed point theorem revisited
- A candidate for the generalised real line
- On the existence of a connected component of a graph
- Intuitionistic provability versus uniform provability in \(\mathsf{RCA}\)
- Weihrauch degrees of finding equilibria in sequential games
- Finite choice, convex choice and finding roots
- The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
- Closed choice and a uniform low basis theorem
- Real computation with least discrete advice: a complexity theory of nonuniform computability with applications to effective linear algebra
- A Galois connection between Turing jumps and limits
- On computability and disintegration
- A comparison of concepts from computable analysis and effective descriptive set theory
- On the uniform computational content of Ramsey's theorem
- Effective Brenier Theorem
- Weihrauch-completeness for layerwise computability
- scientific article; zbMATH DE number 817189 (Why is no real title available?)
- Decomposing Borel functions using the Shore-Slaman join theorem
- Computable analysis and notions of continuity in \textsc{Coq}
- Weihrauch and constructive reducibility between existence statements
- A COMPARISON OF VARIOUS ANALYTIC CHOICE PRINCIPLES
- Bishop-Style Constructive Reverse Mathematics
- Weihrauch Complexity in Computable Analysis
- The axiom of choice in computability theory and reverse mathematics with a cameo for the continuum hypothesis
- Stashing and parallelization pentagons
- Connected choice and the Brouwer fixed point theorem
- Game characterizations and lower cones in the Weihrauch degrees
- On the strength of marriage theorems and uniformity
- From Bolzano‐Weierstraß to Arzelà‐Ascoli
- Representations of analytic functions and Weihrauch degrees
- Wadge-like reducibilities on arbitrary quasi-Polish spaces
- Searching for an analogue of \(\text{ATR}_0\) in the Weihrauch lattice
- Lawvere-Tierney topologies for computability theorists
- Algebraic properties of the first-order part of a problem
- On the complexity of learning programs
- Searching problems above arithmetical transfinite recursion
This page was built for publication: Effective Choice and Boundedness Principles in Computable Analysis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3083466)
