The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma

DOI10.1016/j.apal.2011.10.006zbMath1245.03097arXiv1101.0792OpenAlexW2018837422WikidataQ124965796 ScholiaQ124965796MaRDI QIDQ408156

Vasco Brattka, Guido Gherardi, Alberto Marcone

Publication date: 29 March 2012

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

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

zbMATH Keywords

reverse mathematicsweak König's lemmacomputable analysisBolzano-Weierstraß theoremconstructive analysiseffective descriptive set theoryjump in the Weihrauch lattice

Mathematics Subject Classification ID

Descriptive set theory (03E15) Constructive and recursive analysis (03F60) Foundations of classical theories (including reverse mathematics) (03B30) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (42)

An inside/outside Ramsey theorem and recursion theory ⋮ Effectivity and reducibility with ordinal Turing machines ⋮ On the uniform computational content of the Baire category theorem ⋮ Inside the Muchnik degrees. I: Discontinuity, learnability and constructivism ⋮ Computability and Analysis, a Historical Approach ⋮ The Brouwer Fixed Point Theorem Revisited ⋮ Generalized Effective Reducibility ⋮ Weihrauch Degrees of Finding Equilibria in Sequential Games ⋮ A semi-potential for finite and infinite games in extensive form ⋮ A topological view on algebraic computation models ⋮ Algebraic properties of the first-order part of a problem ⋮ On computability and disintegration ⋮ A comparison of concepts from computable analysis and effective descriptive set theory ⋮ On the uniform computational content of computability theory ⋮ Variations of statement, variations of strength. The case of the Rival-Sands theorems ⋮ On the complexity of learning programs ⋮ The complexity of finding supergraphs ⋮ ON THE UNIFORM COMPUTATIONAL CONTENT OF RAMSEY’S THEOREM ⋮ ON WEIHRAUCH REDUCIBILITY AND INTUITIONISTIC REVERSE MATHEMATICS ⋮ The Vitali Covering Theorem in the Weihrauch Lattice ⋮ Parallel and Serial Jumps of Weak Weak König’s Lemma ⋮ Many-one reductions and the category of multivalued functions ⋮ Unnamed Item ⋮ Borel-Piecewise Continuous Reducibility for Uniformization Problems ⋮ Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions ⋮ Completion of choice ⋮ Unnamed Item ⋮ Game characterizations and lower cones in the Weihrauch degrees ⋮ Embeddings between well-orderings: computability-theoretic reductions ⋮ FINDING DESCENDING SEQUENCES THROUGH ILL-FOUNDED LINEAR ORDERS ⋮ On the algebraic structure of Weihrauch degrees ⋮ Addendum to: ``The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma ⋮ From Bolzano‐Weierstraß to Arzelà‐Ascoli ⋮ Game characterizations and lower cones in the Weihrauch degrees ⋮ On uniform relationships between combinatorial problems ⋮ Unnamed Item ⋮ Connected choice and the Brouwer fixed point theorem ⋮ SEARCHING FOR AN ANALOGUE OF ATR₀ IN THE WEIHRAUCH LATTICE ⋮ WEIHRAUCH GOES BROUWERIAN ⋮ Probabilistic computability and choice ⋮ Weihrauch Complexity in Computable Analysis ⋮ Universality, optimality, and randomness deficiency

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Closed choice and a uniform low basis theorem
• Borel complexity and computability of the Hahn-Banach theorem
• How incomputable is the separable Hahn-Banach theorem?
• Classical recursion theory. The theory of functions and sets of natural numbers
• Computable invariance
• Computability on subsets of metric spaces.
• Constructive notions of equicontinuity
• A fan-theoretic equivalent of the antithesis of Specker's theorem
• How Discontinuous is Computing Nash Equilibria? (Extended Abstract)
• The cohesive principle and the Bolzano-Weierstraß principle
• On the (semi)lattices induced by continuous reducibilities
• On the computational content of the Bolzano-Weierstraß Principle
• Weihrauch degrees, omniscience principles and weak computability
• Effective Choice and Boundedness Principles in Computable Analysis
• Complexity Issues for Preorders on Finite Labeled Forests
• Effective Borel measurability and reducibility of functions
• Singular coverings and non‐uniform notions of closed set computability
• Undecidability in Weihrauch Degrees
• Borel Complexity of Topological Operations on Computable Metric Spaces
• Limited Omniscience and the Bolzano-Weierstrass Principle
• Computational complexity on computable metric spaces
• On the Strength of Weak Compactness
• Revising Type-2 Computation and Degrees of Discontinuity
• On Computable Compact Operators on Banach Spaces
• Applied Proof Theory: Proof Interpretations and Their Use in Mathematics
• Automata, Languages and Programming
• ∏ 0 1 Classes and Degrees of Theories

This page was built for publication: The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma