We show that \\) cannot be proved with one typical application of \\) in an intuitionistic extension of \ to higher types, but that this does not remain true when the law of the excluded middle is added. The argument uses Kohlenbach’s axiomatization of higher order reverse mathematics, results related to modified reducibility, and a formalization of Weihrauch reducibility.

Journal of Mathematical Logic, Volume 22, Issue 03, December 2022. Hirschfeldt and Jockusch (2016) introduced a two-player game in which winning strategies for one or the other player precisely correspond to implications and non-implications between [math] principles over [math]-models of [math]. They also introduced a version of this game that similarly captures provability over [math]. We generalize and extend this game-theoretic framework to other formal systems, and establish a certain compactness result that shows that if an implication [math] between two (...) principles holds, then there exists a winning strategy that achieves victory in a number of moves bounded by a number independent of the specific run of the game. This compactness result generalizes an old proof-theoretic fact noted by H. Wang (1981), and has applications to the reverse mathematics of combinatorial principles. We also demonstrate how this framework leads to a new kind of analysis of the logical strength of mathematical problems that refines both that of reverse mathematics and that of computability-theoretic notions such as Weihrauch reducibility, allowing for a kind of fine-structural comparison between [math] principles that has both computability-theoretic and proof-theoretic aspects, and can help us distinguish between these, for example by showing that a certain use of a principle in a proof is “purely proof-theoretic”, as opposed to relying on its computability-theoretic strength. We give examples of this analysis to a number of principles at the level of [math], uncovering new differences between their logical strengths. (shrink)

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 cardinalityn≥ 1 and an arbitrary finite number of colorsk≥ 2 is equivalent to then-th jump of weak Kőnig’s lemma. In particular, Ramsey’s theorem for cardinalityn≥ 1 is${\bf{\Sigma }}_{n + 2}^0$-measurable in (...) the effective Borel hierarchy, but not${\bf{\Sigma }}_{n + 1}^0$-measurable. Secondly, we obtain interesting lower bounds, for instance then-th jump of weak Kőnig’s lemma is Weihrauch reducible to Ramsey’s theorem of cardinalityn+ 2 forn≥ 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 nonuniform 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 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 nonuniform situation in reverse mathematics. (shrink)

Ramsey’s theorem asserts that every k-coloring of $[\omega ]^n$ admits an infinite monochromatic set. Whenever $n \geq 3$, there exists a computable k-coloring of $[\omega ]^n$ whose solutions compute the halting set. On the other hand, for every computable k-coloring of $[\omega ]^2$ and every noncomputable set C, there is an infinite monochromatic set H such that $C \not \leq _T H$. The latter property is known as cone avoidance.In this article, we design a natural class of Ramsey-like theorems encompassing (...) many statements studied in reverse mathematics. We prove that this class admits a maximal statement satisfying cone avoidance and use it as a criterion to re-obtain many existing proofs of cone avoidance. This maximal statement asserts the existence, for every k-coloring of $[\omega ]^n$, of an infinite subdomain $H \subseteq \omega $ over which the coloring depends only on the sparsity of its elements. This confirms the intuition that Ramsey-like theorems compute Turing degrees only through the sparsity of its solutions. (shrink)

A set of integers A is computably encodable if every infinite set of integers has an infinite subset computing A. By a result of Solovay, the computably encodable sets are exactly the hyperarithmetic ones. In this article, we extend this notion of computable encodability to subsets of the Baire space, and we characterize the Π10-encodable compact sets as those which admit a nonempty Σ11-subset. Thanks to this equivalence, we prove that weak weak König’s lemma is not strongly computably reducible to (...) Ramsey’s theorem. This answers a question of Hirschfeldt and Jockusch. (shrink)