Connected Choice and the Brouwer Fixed Point Theorem

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 upwards 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 upwards. 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 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.

36 pages

References in corpus (10)

• Closed Choice and a Uniform Low Basis Theorem
• The Bolzano-Weierstrass Theorem is the Jump of Weak König's Lemma
• Computational Problems in Metric Fixed Point Theory and their Weihrauch Degrees
• Finite choice, convex choice and finding roots
• On the Uniform Computational Content of Computability Theory
• Computable counter-examples to the Brouwer fixed-point theorem
• On the Uniform Computational Content of the Baire Category Theorem
• The Vitali Covering Theorem in the Weihrauch Lattice
• Computability of the Radon-Nikodym derivative
• Incomputability of Simply Connected Planar Continua

Cited by in corpus (9)

• Probabilistic Computability and Choice
• On the algebraic structure of Weihrauch degrees
• Computational Problems in Metric Fixed Point Theory and their Weihrauch Degrees
• Finite choice, convex choice and finding roots
• Completion of Choice
• The set of hyperbolic equilibria and of invertible zeros on the unit ball is computable
• Ramsey's theorem and products in the Weihrauch degrees
• Metaphysics in Mathematics
• Computability of Initial Value Problems