Journal of Mathematical Logic 19 (1):1950004 (2019)

Abstract
We study the computational content of the Brouwer Fixed Point Theorem in the Weihrauch lattice. Connected choice is the operation that finds a point in a non-empty connected closed set given by negative information. One of our main results is that for any fixed dimension the Brouwer Fixed Point Theorem of that dimension is computably equivalent to connected choice of the Euclidean unit cube of the same dimension. Another main result is that connected choice is complete for dimension greater than or equal to two in the sense that it is computably equivalent to Weak Kőnig’s Lemma. While we can present two independent proofs for dimension three and upward that are either based on a simple geometric construction or a combinatorial argument, the proof for dimension two is based on a more involved inverse limit construction. The connected choice operation in dimension one is known to be equivalent to the Intermediate Value Theorem; we prove that this problem is not idempotent in contrast to the case of dimension two and upward. We also prove that Lipschitz continuity with Lipschitz constants strictly larger than one does not simplify finding fixed points. Finally, we prove that finding a connectedness component of a closed subset of the Euclidean unit cube of any dimension greater than or equal to one is equivalent to Weak Kőnig’s Lemma. In order to describe these results, we introduce a representation of closed subsets of the unit cube by trees of rational complexes.
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1142/s0219061319500041
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 59,848
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
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.
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 references / Add more references

Citations of this work BETA

Completion of Choice.Vasco Brattka & Guido Gherardi - 2021 - Annals of Pure and Applied Logic 172 (3):102914.

Add more citations

Similar books and articles

A Fixed Point Theorem for o-Minimal Structures.Kam-Chau Wong - 2003 - Mathematical Logic Quarterly 49 (6):598.
Intersection Theory for o-Minimal Manifolds.Alessandro Berarducci & Margarita Otero - 2001 - Annals of Pure and Applied Logic 107 (1-3):87-119.
Book Review: Mark van Atten. On Brouwer. [REVIEW]O. Bradley Bassler - 2006 - Notre Dame Journal of Formal Logic 47 (4):581-599.
A Constructive Version of Sperner's Lemma and Brouwer's Fixed Point Theorem.A. K. Khalifa - 1990 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 36 (3):247-251.
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.
Yet Another Hierarchy Theorem.Max Kubierschky - 2000 - Journal of Symbolic Logic 65 (2):627-640.
Yet Another Hierarchy Theorem.Max Kubierschky - 2000 - Journal of Symbolic Logic 65 (2):627-640.
Brouwer's Equivalence Between Virtual and Inextensible Order.Enrico Martino - 1988 - History and Philosophy of Logic 9 (1):57-66.
Note on Some Fixed Point Constructions in Provability Logic.Per Lindström - 2006 - Journal of Philosophical Logic 35 (3):225-230.
Self-Defeating Predictions and the Fixed-Point Theorem: A Refutation.Audun Øfsti & Dag Østerberg - 1982 - Inquiry: An Interdisciplinary Journal of Philosophy 25 (3):331 – 352.

Analytics

Added to PP index
2018-11-29

Total views
10 ( #856,090 of 2,432,813 )

Recent downloads (6 months)
1 ( #464,144 of 2,432,813 )

How can I increase my downloads?

Downloads

My notes