How incomputable is the separable Hahn-Banach theorem?

DOI10.1215/00294527-2009-018MaRDI QIDQ987935zbMATHOpenAlexFDO

Authors Guido Gherardi, Alberto Marcone

Publication date 2 September 2010

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

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

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)

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.

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?

Cited in

(30)

• On the uniform computational content of the Baire category theorem
• Borel complexity and computability of the Hahn-Banach theorem
• Many-one reductions and the category of multivalued functions
• The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
• Searching for an analogue of \(\text{ATR}_0\) in the Weihrauch lattice
• Minimal covers in the Weihrauch degrees
• FINDING DESCENDING SEQUENCES THROUGH ILL-FOUNDED LINEAR ORDERS
• A comparison of concepts from computable analysis and effective descriptive set theory
• Weihrauch degrees, omniscience principles and weak computability
• The Vitali Covering Theorem in the Weihrauch Lattice
• Universality, optimality, and randomness deficiency
• Game characterizations and lower cones in the Weihrauch degrees
• Open sets in computability theory and reverse mathematics
• Connected choice and the Brouwer fixed point theorem
• Computability on the countable ordinals and the Hausdorff-Kuratowski theorem (extended abstract)
• How incomputable is the separable Hahn-Banach theorem?
• The Brouwer fixed point theorem revisited
• Closed choice and a uniform low basis theorem
• Game characterizations and lower cones in the Weihrauch degrees
• THE OPEN AND CLOPEN RAMSEY THEOREMS IN THE WEIHRAUCH LATTICE
• On the uniform computational content of computability theory
• Probabilistic computability and choice
• Effective Choice and Boundedness Principles in Computable Analysis
• Computability and analysis, a historical approach
• COMPUTABLY COMPACT METRIC SPACES
• On the algebraic structure of Weihrauch degrees
• On the uniform computational content of Ramsey's theorem
• Searching problems above arithmetical transfinite recursion
• Primitive recursive reverse mathematics
• Weihrauch Complexity in Computable Analysis

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)