AN INSIDE/OUTSIDE RAMSEY THEOREM AND RECURSION THEORY

Inspired by Ramsey's theorem for pairs, Rival and Sands proved what we refer to as an inside/outside Ramsey theorem: every infinite graph G contains an infinite subset H such that every vertex of G is adjacent to precisely none, one, or infinitely many vertices of H. 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 Konig'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.

Automated summary

Inspired by Ramsey's theorem, Rival and Sands proved the inside/outside Ramsey theorem which has strong computational strength and is equivalent to arithmetical comprehension. They also identified a weaker form that is equivalent to Ramsey's theorem for pairs. Combining their result with previous research, they showed that solving one instance of the Rival-Sands theorem corresponds to solving countably many instances of Ramsey's theorem for pairs simultaneously. They also analyzed the Weihrauch degrees and found that the Rival-Sands theorem has the same computational strength as the double jump of weak Konig's lemma.