This is an announcement for the paper "How much incomputable is the separable Hahn-Banach theorem?" by Guido Gherardi and Alberto Marcone.
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 Konig's Lemma within the framework of computable analysis to classify incomputable functions of low complexity. By defining the multi-valued function Sep and a natural notion of reducibility for multi-valued functions, we obtain a computational counterpart of the subsystem of second order arithmetic WKL_0. We study analogies and differences between WKL_0 and the class of Sep-computable multi-valued functions. Extending work of Brattka, we show that a natural multi-valued function associated with the Hahn-Banach Extension Theorem is Sep-complete.
Archive classification: math.LO math.FA
Mathematics Subject Classification: 03F60 (Primary) 03B30, 46A22, 46S30 (Secondary)
The source file(s), HahnBanach.tex: 106451 bytes, is(are) stored in gzipped form as 0808.1663.gz with size 32kb. The corresponding postcript file has gzipped size 149kb.
Submitted from: alberto.marcone@dimi.uniud.it
The paper may be downloaded from the archive by web browser from URL
http://front.math.ucdavis.edu/0808.1663
or
http://arXiv.org/abs/0808.1663
or by email in unzipped form by transmitting an empty message with subject line
uget 0808.1663
or in gzipped form by using subject line
get 0808.1663
to: math@arXiv.org.