Effective choice and boundedness principles in computable analysis

Bulletin of Symbolic Logic 17 (1):73-117 (2011)
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 such as co-finite choice, discrete choice, interval choice, compact choice and closed choice, 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, the Closed Graph Theorem and the Uniform Boundedness Theorem. We also explore how existing classifications of the Hahn—Banach Theorem and Weak Kőnig's Lemma fit into this picture. Well-known omniscience principles from constructive mathematics such as LPO and LLPO can also naturally be considered as Weihrauch degrees and they play an important role in our classification. Based on this 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. Our classification scheme does not require any particular logical framework or axiomatic setting, but it can be carried out in the framework of classical mathematics using tools of topology, computability theory and computable analysis. 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
Keywords Computable analysis   constructive analysis   reverse mathematics   effective descriptive set theory
Categories (categorize this paper)
DOI 10.2178/bsl/1294186663
Options
 Save to my reading list
Follow the author(s)
Edit this record
My bibliography
Export citation
Find it on Scholar
Mark as duplicate
Request removal from index
Revision history
Download options
Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 31,786
Through your library
References found in this work BETA
Effective Borel Measurability and Reducibility of Functions.Vasco Brattka - 2005 - Mathematical Logic Quarterly 51 (1):19-44.
On the (Semi)Lattices Induced by Continuous Reducibilities.Arno Pauly - 2010 - Mathematical Logic Quarterly 56 (5):488-502.
How Incomputable Is the Separable Hahn-Banach Theorem?Guido Gherardi & Alberto Marcone - 2009 - Notre Dame Journal of Formal Logic 50 (4):393-425.
Borel Complexity and Computability of the Hahn–Banach Theorem.Vasco Brattka - 2008 - Archive for Mathematical Logic 46 (7-8):547-564.

View all 20 references / Add more references

Citations of this work BETA
Closed Choice and a Uniform Low Basis Theorem.Vasco Brattka, Matthew de Brecht & Arno Pauly - 2012 - Annals of Pure and Applied Logic 163 (8):986-1008.

View all 10 citations / Add more citations

Similar books and articles
Developments in Constructive Nonstandard Analysis.Erik Palmgren - 1998 - Bulletin of Symbolic Logic 4 (3):233-272.
Degrees of Unsolvability of Continuous Functions.Joseph S. Miller - 2004 - Journal of Symbolic Logic 69 (2):555 - 584.
A Simple Proof and Some Difficult Examples for Hindman's Theorem.Henry Towsner - 2012 - Notre Dame Journal of Formal Logic 53 (1):53-65.
Hindman's Theorem, Ultrafilters, and Reverse Mathematics.Jeffry L. Hirst - 2004 - Journal of Symbolic Logic 69 (1):65-72.
Reverse Mathematics: The Playground of Logic.Richard A. Shore - 2010 - Bulletin of Symbolic Logic 16 (3):378-402.
Stable Ramsey's Theorem and Measure.Damir D. Dzhafarov - 2011 - Notre Dame Journal of Formal Logic 52 (1):95-112.
Some New Intuitionistic Equivalents of Zorn's Lemma.John Bell - 2003 - Archive for Mathematical Logic 42 (8):811-814.
Algebraic Aspects of Deduction Theorems.Janusz Czelakowski - 1985 - Studia Logica 44 (4):369 - 387.
On the Indecomposability of $\Omega^{N}$.Jared R. Corduan & François G. Dorais - 2012 - Notre Dame Journal of Formal Logic 53 (3):373-395.
Added to PP index
2011-01-05

Total downloads
32 ( #182,513 of 2,231,528 )

Recent downloads (6 months)
1 ( #445,507 of 2,231,528 )

How can I increase my downloads?

Monthly downloads
My notes
Sign in to use this feature