An inside/outside Ramsey theorem and recursion theory
From MaRDI portal
Abstract: Inspired by Ramsey's theorem for pairs, Rival and Sands proved what we refer to as an inside/outside Ramsey theorem: every infinite graph contains an infinite subset such that every vertex of is adjacent to precisely none, one, or infinitely many vertices of . We analyze the Rival-Sands theorem from the perspective of reverse mathematics and the Weihrauch degrees. In reverse mathematics, we find that the Rival-Sands theorem is equivalent to arithmetical comprehension and hence is stronger than Ramsey's theorem for pairs. We also identify a weak form of the Rival-Sands theorem that is equivalent to Ramsey's theorem for pairs. We turn to the Weihrauch degrees to give a finer analysis of the Rival-Sands theorem's computational strength. We find that the Rival-Sands theorem is Weihrauch equivalent to the double jump of weak K"{o}nig's lemma. We believe that the Rival-Sands theorem is the first natural theorem shown to exhibit exactly this strength. Furthermore, by combining our result with a result of Brattka and Rakotoniaina, we obtain that solving one instance of the Rival-Sands theorem exactly corresponds to simultaneously solving countably many instances of Ramsey's theorem for pairs. Finally, we show that the uniform computational strength of the weak Rival-Sands theorem is weaker than that of Ramsey's theorem for pairs by showing that a number of well-known consequences of Ramsey's theorem for pairs do not Weihrauch reduce to the weak Rival-Sands theorem. We also address an apparent gap in the literature concerning the relationship between Weihrauch degrees corresponding to the ascending/descending sequence principle and the infinite pigeonhole principle.
Recommendations
- On the existence of a connected component of a graph
- On Tao's “finitary” infinite pigeonhole principle
- Reverse mathematics and a Ramsey-type König's lemma
- Reverse Mathematics and Recursive Graph Theory
- Reverse mathematics and infinite traceable graphs
- Combinatorial principles between \(\text{RRT}_2^2\) and \(\text{RT}_2^2\)
- The weakness of the pigeonhole principle under hyperarithmetical reductions
- Carlson-Simpson's lemma and applications in reverse mathematics
- scientific article; zbMATH DE number 6766028
- Menger's theorem in \(\Pi^1_1 \mathrm {-CA}_0\)
Cites work
- \( \mathsf{SRT}_2^2\) does not imply \(\mathsf{RT}_2^2\) in \(\omega \)-models
- \(\mathsf{RT}_{2}^{2}\) does not imply \(\mathsf{WKL}_{0}\)
- A cohesive set which is not high
- Combinatorial principles weaker than Ramsey's Theorem for pairs
- Computability and Randomness
- Cone avoiding closed sets
- Corrigendum to: ``On the strength of Ramsey's theorem for pairs
- scientific article; zbMATH DE number 3717361 (Why is no real title available?)
- scientific article; zbMATH DE number 3767656 (Why is no real title available?)
- scientific article; zbMATH DE number 194103 (Why is no real title available?)
- scientific article; zbMATH DE number 3536056 (Why is no real title available?)
- scientific article; zbMATH DE number 1144041 (Why is no real title available?)
- scientific article; zbMATH DE number 3446873 (Why is no real title available?)
- Infinite chains and antichains in computable partial orderings
- On notions of computability-theoretic reduction between Π21 principles
- On the Adjacency of Vertices to the Vertices of an Infinite Subgraph
- On the algebraic structure of Weihrauch degrees
- On the strength of Ramsey's theorem
- On the strength of Ramsey's theorem for pairs
- On the uniform computational content of computability theory
- On the uniform computational content of Ramsey's theorem
- On uniform relationships between combinatorial problems
- Partial orders and immunity in reverse mathematics
- Ramsey's theorem and recursion theory
- Separating principles below Ramsey's theorem for pairs
- Slicing the truth. On the computable and reverse mathematics of combinatorial principles
- Strong reductions between combinatorial principles
- Subsystems of second order arithmetic
- The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma
- The metamathematics of Stable Ramsey’s Theorem for Pairs
- The proof-theoretic strength of Ramsey's theorem for pairs and two colors
- The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs
- The uniform content of partial and linear orders
- Weihrauch Complexity in Computable Analysis
- Weihrauch degrees, omniscience principles and weak computability
- ∏ 0 1 Classes and Degrees of Theories
Cited in
(13)- On the Dirac-Frenkel variational principle on tensor Banach spaces
- Tree-based tensor formats
- The computational strength of matchings in countable graphs
- Reverse mathematics and infinite traceable graphs
- A recursion theoretic analysis of the clopen Ramsey theorem
- The geometry of algorithms using hierarchical tensors
- On the uniform computational content of Ramsey's theorem
- THE OPEN AND CLOPEN RAMSEY THEOREMS IN THE WEIHRAUCH LATTICE
- Ramsey's theorem and products in the Weihrauch degrees
- 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
- The metamathematics of separated determinacy
This page was built for publication: An inside/outside Ramsey theorem and recursion theory
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5036108)
