How incomputable is the separable Hahn-Banach theorem?

DOI10.1215/00294527-2009-018zbMATH Open1223.03052arXiv0808.1663OpenAlexW1987187730MaRDI QIDQ987935FDOQ987935

Authors: Guido Gherardi, Alberto Marcone 

Publication date: 2 September 2010

Published in: Notre Dame Journal of Formal Logic (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/0808.1663

Recommendations

• How incomputable is the separable Hahn-Banach theorem?
• Separation and Weak König's Lemma
• Effective choice and boundedness principles in computable analysis
• Borel complexity and computability of the Hahn-Banach theorem
• Which set existence axioms are needed to prove the separable Hahn-Banach theorem?

zbMATH Keywords

Hahn-Banach extension theoremmultivalued functionscomputable analysis, reverse mathematicsweak König's lemma

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Theorems of Hahn-Banach type; extension and lifting of functionals and operators (46A22) Constructive and recursive analysis (03F60) Constructive functional analysis (46S30)

Cited In (30)

• Closed choice and a uniform low basis theorem
• Searching problems above arithmetical transfinite recursion
• Borel complexity and computability of the Hahn-Banach theorem
• Computability on the Countable Ordinals and the Hausdorff-Kuratowski Theorem (Extended Abstract)
• FINDING DESCENDING SEQUENCES THROUGH ILL-FOUNDED LINEAR ORDERS
• Game characterizations and lower cones in the Weihrauch degrees
• COMPUTABLY COMPACT METRIC SPACES
• Primitive recursive reverse mathematics
• On the uniform computational content of the Baire category theorem
• The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
• Game characterizations and lower cones in the Weihrauch degrees
• THE OPEN AND CLOPEN RAMSEY THEOREMS IN THE WEIHRAUCH LATTICE
• The Vitali Covering Theorem in the Weihrauch Lattice
• Universality, optimality, and randomness deficiency
• Many-one reductions and the category of multivalued functions
• Minimal covers in the Weihrauch degrees
• Probabilistic computability and choice
• A comparison of concepts from computable analysis and effective descriptive set theory
• Weihrauch degrees, omniscience principles and weak computability
• Open sets in computability theory and reverse mathematics
• ON THE UNIFORM COMPUTATIONAL CONTENT OF RAMSEY’S THEOREM
• Effective Choice and Boundedness Principles in Computable Analysis
• SEARCHING FOR AN ANALOGUE OF ATR₀ IN THE WEIHRAUCH LATTICE
• Weihrauch Complexity in Computable Analysis
• Connected choice and the Brouwer fixed point theorem
• On the uniform computational content of computability theory
• Computability of the Radon-Nikodym derivative
• Computability and Analysis, a Historical Approach
• On the algebraic structure of Weihrauch degrees
• The Brouwer Fixed Point Theorem Revisited

This page was built for publication: How incomputable is the separable Hahn-Banach theorem?

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q987935)