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 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.
How incomputable is the separable Hahn-Banach theorem?
MARCONE, Alberto Giulio
2009-01-01
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 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
