How Incomputable Is the Separable Hahn-Banach Theorem?

Gherardi ,  Guido; Marcone ,  Alberto

Notre Dame J. Formal Logic, Tome 50 (2009) no. 1, p. 393 - 425 / Harvested from Project Euclid

Résumé

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 WKL₀. We study analogies and differences between WKL₀ 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.

Publié le : 2009-10-15
Classification: computable analysis, reverse mathematics, weak Konig's lemma, Hahn-Banach extension theorem, multivalued functions, 03F60, 03B30, 46A22, 46S30

@article{1265899122,
     author = {Gherardi ,  Guido and Marcone ,  Alberto},
     title = {How Incomputable Is the Separable Hahn-Banach Theorem?},
     journal = {Notre Dame J. Formal Logic},
     volume = {50},
     number = {1},
     year = {2009},
     pages = { 393 - 425},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1265899122}
}

Gherardi ,  Guido; Marcone ,  Alberto. How Incomputable Is the Separable Hahn-Banach Theorem?. Notre Dame J. Formal Logic, Tome 50 (2009) no. 1, pp.  393 - 425. http://gdmltest.u-ga.fr/item/1265899122/