An inside/outside Ramsey theorem and recursion theory

DOI10.1090/tran/8561zbMath1505.03027arXiv2006.16969OpenAlexW3040572287MaRDI QIDQ5036108

Paul Shafer, Marta Fiori-Carones, Giovanni Soldà

Publication date: 23 February 2022

Published in: Transactions of the American Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

graph theoryRamsey theorycomputability theoryreverse mathematicsWeihrauch degreesRival-Sands theorem

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Ramsey theory (05D10) Second- and higher-order arithmetic and fragments (03F35) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items (3)

Primitive recursive reverse mathematics ⋮ Variations of statement, variations of strength. The case of the Rival-Sands theorems ⋮ (EXTRA)ORDINARY EQUIVALENCES WITH THE ASCENDING/DESCENDING SEQUENCE PRINCIPLE

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
• The proof-theoretic strength of Ramsey's theorem for pairs and two colors
• On the uniform computational content of computability theory
• On the strength of Ramsey's theorem
• \( \mathsf{SRT}_2^2\) does not imply \(\mathsf{RT}_2^2\) in \(\omega \)-models
• The uniform content of partial and linear orders
• On the strength of Ramsey's theorem for pairs
• Infinite chains and antichains in computable partial Orderings
• On uniform relationships between combinatorial problems
• RT₂² does not imply WKL₀
• STRONG REDUCTIONS BETWEEN COMBINATORIAL PRINCIPLES
• Weihrauch degrees, omniscience principles and weak computability
• On notions of computability-theoretic reduction between Π21 principles
• The metamathematics of Stable Ramsey’s Theorem for Pairs
• Slicing the Truth
• Combinatorial principles weaker than Ramsey's Theorem for pairs
• The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs
• Corrigendum to: “On the strength of Ramsey's Theorem for pairs”
• On the Adjacency of Vertices to the Vertices of an Infinite Subgraph
• A cohesive set which is not high
• On the algebraic structure of Weihrauch degrees
• ON THE UNIFORM COMPUTATIONAL CONTENT OF RAMSEY’S THEOREM
• Partial orders and immunity in reverse mathematics
• Weihrauch Complexity in Computable Analysis
• Computability and Randomness
• SEPARATING PRINCIPLES BELOW RAMSEY'S THEOREM FOR PAIRS
• Cone avoiding closed sets
• ∏ 0 1 Classes and Degrees of Theories
• Ramsey's theorem and recursion theory

This page was built for publication: An inside/outside Ramsey theorem and recursion theory