On Notions of Computability-Theoretic Reduction between Π12 Principles

by Denis R. Hirschfeldt and Carl G. Jockusch, Jr.

Status: published in the Journal of Mathematical Logic 16 (2016) 1650002.

Availability: journal version and preprint

Abstract. Several notions of computability theoretic reducibility between Π12 principles have been studied. This paper contributes to the program of analyzing the behavior of versions of Ramsey's Theorem and related principles under these notions. Among other results, we show that for each n ≥ 3, there is an instance of RTn2 all of whose solutions have PA degree over 0(n-2), and use this to show that König's Lemma lies strictly between RT22 and RT32 under one of these notions. We also answer two questions raised by Dorais, Dzhafarov, Hirst, Mileti, and Shafer [ta] on comparing versions of Ramsey's Theorem and of the Thin Set Theorem with the same exponent but different numbers of colors. Still on the topic of the effect of the number of colors on the computable aspects of Ramsey theoretic properties, we show that for each m ≥ 2, there is an (m+1)-coloring c of the natural numbers such that every m-coloring of the natural numbers has an infinite homogeneous set that does not compute any infinite homogeneous set for c, and connect this result with the notion of infinite information reducibility introduced by Dzhafarov and Igusa [ta]. Next, we introduce and study a new notion that provides a uniform version of the idea of implication with respect to ω-models of RCA0, and related notions that allow us to count how many applications of a principle P are needed to reduce another principle to P. Finally, we fill in a gap in the proof of Theorem 12.2 in Cholak, Jockusch, and Slaman [2001].