How Incomputable Is the Separable Hahn-Banach Theorem?

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


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



    Upload a copy of this work     Papers currently archived: 91,386

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

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

24 (#639,942)

6 months
9 (#290,637)

Historical graph of downloads
How can I increase my downloads?

References found in this work

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