Archive for Mathematical Logic 46 (7-8):547-564 (2008)

Abstract
The classical Hahn–Banach Theorem states that any linear bounded functional defined on a linear subspace of a normed space admits a norm-preserving linear bounded extension to the whole space. The constructive and computational content of this theorem has been studied by Bishop, Bridges, Metakides, Nerode, Shore, Kalantari Downey, Ishihara and others and it is known that the theorem does not admit a general computable version. We prove a new computable version of this theorem without unrolling the classical proof of the theorem itself. More precisely, we study computability properties of the uniform extension operator which maps each functional and subspace to the set of corresponding extensions. It turns out that this operator is upper semi-computable in a well-defined sense. By applying a computable version of the Banach–Alaoglu Theorem we can show that computing a Hahn–Banach extension cannot be harder than finding a zero in a compact metric space. This allows us to conclude that the Hahn–Banach extension operator is ${\bf {\Sigma^{0}_{2}}}$ -computable while it is easy to see that it is not lower semi-computable in general. Moreover, we can derive computable versions of the Hahn–Banach Theorem for those functionals and subspaces which admit unique extensions
Keywords Computable analysis  Functional analysis  Effective descriptive set theory
Categories (categorize this paper)
DOI 10.1007/s00153-007-0057-z
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: 71,410
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

On Computable Numbers, with an Application to the N Tscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.
Subsystems of Second-Order Arithmetic.Stephen G. Simpson - 2004 - Studia Logica 77 (1):129-129.
Effective Borel Measurability and Reducibility of Functions.Vasco Brattka - 2005 - Mathematical Logic Quarterly 51 (1):19-44.
An Omniscience Principle, the König Lemma and the Hahn-Banach Theorem.Hajime Ishihara - 1990 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 36 (3):237-240.

View all 9 references / Add more references

Citations of this work BETA

How Incomputable Is the Separable Hahn-Banach Theorem?Guido Gherardi & Alberto Marcone - 2009 - Notre Dame Journal of Formal Logic 50 (4):393-425.
A Computable Version of Banach’s Inverse Mapping Theorem.Vasco Brattka - 2009 - Annals of Pure and Applied Logic 157 (2-3):85-96.

Add more citations

Similar books and articles

How Incomputable Is the Separable Hahn-Banach Theorem?Guido Gherardi & Alberto Marcone - 2009 - Notre Dame Journal of Formal Logic 50 (4):393-425.
A Computable Version of Banach’s Inverse Mapping Theorem.Vasco Brattka - 2009 - Annals of Pure and Applied Logic 157 (2-3):85-96.
Uniform Domain Representations of "Lp" -Spaces.Petter K. Køber - 2007 - Mathematical Logic Quarterly 53 (2):180-205.
A Uniformly Computable Implicit Function Theorem.Timothy H. McNicholl - 2008 - Mathematical Logic Quarterly 54 (3):272-279.
The Hahn-Banach Property and the Axiom of Choice.Juliette Dodu & Marianne Morillon - 1999 - Mathematical Logic Quarterly 45 (3):299-314.

Analytics

Added to PP index
2013-11-23

Total views
17 ( #639,163 of 2,519,856 )

Recent downloads (6 months)
1 ( #406,012 of 2,519,856 )

How can I increase my downloads?

Downloads

My notes