On the Uniform Computational Content of Ramsey's Theorem

Abstract

We study the uniform computational content of Ramsey's theorem in the Weihrauch lattice. Our central results provide information on how Ramsey's theorem behaves under product, parallelization and jumps. From these results we can derive a number of important properties of Ramsey's theorem. For one, the parallelization of Ramsey's theorem for cardinality $n\ge 1$ and an arbitrary finite number of colors $k\ge 2$ is equivalent to the $n$--th jump of weak Kőnig's lemma. In particular, Ramsey's theorem for cardinality $n\ge 1$ is ${\Sigma }_{n+2}^0$--measurable in the effective Borel hierarchy, but not ${\Sigma }_{n+1}^0$--measurable. Secondly, we obtain interesting lower bounds, for instance the $n$--th jump of weak Kőnig's lemma is Weihrauch reducible to (the stable version of) Ramsey's theorem of cardinality $n+2$ for $n\ge 2$. We prove that with strictly increasing numbers of colors Ramsey's theorem forms a strictly increasing chain in the Weihrauch lattice. Our study of jumps also shows that certain uniform variants of Ramsey's theorem that are indistinguishable from a non-uniform perspective play an important role. For instance, the colored version of Ramsey's theorem explicitly includes the color of the homogeneous set as output information, and the jump of this problem (but not the uncolored variant) is equivalent to the stable version of Ramsey's theorem of the next greater cardinality. Finally, we briefly discuss the particular case of Ramsey's theorem for pairs, and we provide some new separation techniques for problems that involve jumps in this context. In particular, we study uniform results regarding the relation of boundedness and induction problems to Ramsey's theorem, and we show that there are some significant differences with the non-uniform situation in reverse mathematics.

36 pages

References in corpus (2)

• The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs
• On the Uniform Computational Content of Computability Theory

Cited by in corpus (7)

• Completion of Choice
• Finding descending sequences through ill-founded linear orders
• Algebraic properties of the first-order part of a problem
• Pi01 encodability and omniscient reductions
• (Extra)ordinary equivalences with the ascending/descending sequence principle
• The tree pigeonhole principle in the Weihrauch degrees
• Regressive versions of Hindman's Theorem