Notre Dame Journal of Formal Logic 50 (4):393-425 (2009)

We determine the computational complexity of the Hahn-Banach Extension Theorem. To do so, we investigate some basic connections between reverse mathematics and computable analysis. In particular, we use Weak König's Lemma within the framework of computable analysis to classify incomputable functions of low complexity. By defining the multivalued function Sep and a natural notion of reducibility for multivalued functions, we obtain a computational counterpart of the subsystem of second-order arithmetic WKL0. We study analogies and differences between WKL0 and the class of Sep-computable multivalued functions. Extending work of Brattka, we show that a natural multivalued function associated with the Hahn-Banach Extension Theorem is Sep-complete
Keywords computable analysis   reverse mathematics   weak Konig's lemma   Hahn-Banach extension theorem   multivalued functions
Categories (categorize this paper)
DOI 10.1215/00294527-2009-018
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: 72,564
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.
Fixed Point Theory in Weak Second-Order Arithmetic.Naoki Shioji & Kazuyuki Tanaka - 1990 - Annals of Pure and Applied Logic 47 (2):167-188.
Borel Complexity and Computability of the Hahn–Banach Theorem.Vasco Brattka - 2008 - Archive for Mathematical Logic 46 (7-8):547-564.
Computable Metrization.Tanja Grubba, Matthias Schröder & Klaus Weihrauch - 2007 - Mathematical Logic Quarterly 53 (4‐5):381-395.

View all 7 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 13 citations / Add more citations

Similar books and articles

Separation and Weak König's Lemma.A. James Humphreys & Stephen G. Simpson - 1999 - Journal of Symbolic Logic 64 (1):268-278.
Banach Games.Chris Freiling - 1984 - Journal of Symbolic Logic 49 (2):343-375.
Semantics in Banach Spaces.Sławomir Bugajski - 1983 - Studia Logica 42 (1):81 - 88.
The Hahn Representation Theorem for ℓ-Groups in ZFA.D. Gluschankof - 2000 - Journal of Symbolic Logic 65 (2):519-524.
Actions of Non-Compact and Non-Locally Compact Polish Groups.Sławomir Solecki - 2000 - Journal of Symbolic Logic 65 (4):1881-1894.
The Morley Rank of a Banach Space.José Iovino - 1996 - Journal of Symbolic Logic 61 (3):928-941.
Fundamental Notions of Analysis in Subsystems of Second-Order Arithmetic.Jeremy Avigad - 2006 - Annals of Pure and Applied Logic 139 (1):138-184.
Stable Models and Reflexive Banach Spaces.José Iovino - 1999 - Journal of Symbolic Logic 64 (4):1595-1600.


Added to PP index

Total views
14 ( #737,924 of 2,533,482 )

Recent downloads (6 months)
1 ( #391,480 of 2,533,482 )

How can I increase my downloads?


My notes