ON THE UNIFORM COMPUTATIONAL CONTENT OF RAMSEY’S THEOREM

DOI10.1017/jsl.2017.43zbMath1422.03132arXiv1508.00471OpenAlexW3100726716MaRDI QIDQ4600456

Vasco Brattka, Tahina Rakotoniaina

Publication date: 11 January 2018

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

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

zbMATH Keywords

Ramsey's theoremcomputable analysisWeihrauch lattice

Mathematics Subject Classification ID

Constructive and recursive analysis (03F60) Ramsey theory (05D10) Other degrees and reducibilities in computability and recursion theory (03D30) Computation over the reals, computable analysis (03D78)

Related Items (20)

An inside/outside Ramsey theorem and recursion theory ⋮ Reduction games, provability and compactness ⋮ On notions of computability-theoretic reduction between Π21 principles ⋮ The uniform content of partial and linear orders ⋮ Algebraic properties of the first-order part of a problem ⋮ Ramsey’s theorem for singletons and strong computable reducibility ⋮ Variations of statement, variations of strength. The case of the Rival-Sands theorems ⋮ On the complexity of learning programs ⋮ ON THE UNIFORM COMPUTATIONAL CONTENT OF RAMSEY’S THEOREM ⋮ (EXTRA)ORDINARY EQUIVALENCES WITH THE ASCENDING/DESCENDING SEQUENCE PRINCIPLE ⋮ The Vitali Covering Theorem in the Weihrauch Lattice ⋮ Completion of choice ⋮ The weakness of being cohesive, thin or free in reverse mathematics ⋮ FINDING DESCENDING SEQUENCES THROUGH ILL-FOUNDED LINEAR ORDERS ⋮ Using Ramsey's theorem once ⋮ RAMSEY’S THEOREM FOR PAIRS ANDKCOLORS AS A SUB-CLASSICAL PRINCIPLE OF ARITHMETIC ⋮ COH, SRT 2 2 , and multiple functionals ⋮ WEIHRAUCH GOES BROUWERIAN ⋮ On the Weihrauch degree of the additive Ramsey theorem over the rationals ⋮ Weihrauch Complexity in Computable Analysis

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
• Closed choice and a uniform low basis theorem
• The weakness of being cohesive, thin or free in reverse mathematics
• How incomputable is the separable Hahn-Banach theorem?
• Ramsey's theorem for pairs and provably recursive functions
• Combinatorial set theory: Partition relations for cardinals
• On the uniform computational content of computability theory
• On the strength of Ramsey's theorem
• Probabilistic computability and choice
• On the strength of Ramsey's theorem for pairs
• On uniform relationships between combinatorial problems
• RT₂² does not imply WKL₀
• Term extraction and Ramsey's theorem for pairs
• Ramsey Theorem for Pairs As a Classical Principle in Intuitionistic Arithmetic
• STRONG REDUCTIONS BETWEEN COMBINATORIAL PRINCIPLES
• Weihrauch degrees, omniscience principles and weak computability
• Effective Choice and Boundedness Principles in Computable Analysis
• Effective Borel measurability and reducibility of functions
• On notions of computability-theoretic reduction between Π21 principles
• The metamathematics of Stable Ramsey’s Theorem for Pairs
• The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs
• On the role of the collection principle for Σ⁰₂-formulas in second-order reverse mathematics
• Corrigendum to: “On the strength of Ramsey's Theorem for pairs”
• On the algebraic structure of Weihrauch degrees
• ON THE UNIFORM COMPUTATIONAL CONTENT OF RAMSEY’S THEOREM
• Connected choice and the Brouwer fixed point theorem
• Cohesive avoidance and strong reductions
• Cone avoiding closed sets
• Ramsey's theorem and recursion theory

This page was built for publication: ON THE UNIFORM COMPUTATIONAL CONTENT OF RAMSEY’S THEOREM