Computable counter-examples to the Brouwer fixed-point theorem

2008/04/21 by Petrus H. Potgieter, Potgieter, Petrus H.
Computer Science · Mathematics · #03D10 #68Q25 #68W99 #Computability, Logic, AI Algorithms #FOS: Mathematics #General Mathematics (math.GM) #Logic, Reasoning, and Knowledge #Numerical Methods and Algorithms #math.GM #msc:03D10 #msc:68Q25 #msc:68W99

paper · pdf · doi:10.48550/arxiv.0804.3199

10 pages; to appear in local proceedings of Computability in Europe 2008: Logic and Theory of Algorithms

arxiv created 2008/04/21 · openalex publication_date 2008/04/21 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper is an overview of results that show the Brouwer fixed-point theorem (BFPT) to be essentially non-constructive and non-computable. The main results, the counter-examples of Orevkov and Baigger, imply that there is no procedure for finding the fixed point in general by giving an example of a computable function which does not fix any computable point. Research in reverse mathematics has shown the BFPT to be equivalent to the weak König lemma in RCA₀ (the system of recursive comprehension) and this result is illustrated by relating the weak König lemma directly to the Baigger example.

Related

• An easily verifiable proof of the Brouwer fixed point theorem
• The Brouwer fixed point theorem and the Borsuk--Ulam theorem
• Constructive proof of Brouwer's fixed point theorem for sequentially locally non-constant functions
• Kakutani's fixed point theorem in constructive mathematics
• Brouwer fixed point theorem as a corollary of Lawvere