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

Abstract
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
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: 51,447
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

No references found.

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

Analytics

Added to PP index
2010-09-13

Total views
14 ( #647,042 of 2,330,441 )

Recent downloads (6 months)
2 ( #393,610 of 2,330,441 )

How can I increase my downloads?

Downloads

My notes