##
On notions of computability theoretic reduction between
Π^{1}_{2} principles

Status: *Journal of Mathematical Logic* 16 (2016) 1650002

Availability: PDF

**Abstract.**
Several notions of computability theoretic reducibility between
Π^{1}_{2} 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
RT^{n}_{2} all of whose solutions have PA degree
over 0^{(n-2)}, and use this to show that König's
Lemma lies strictly between RT^{2}_{2} and
RT^{3}_{2} 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 RCA_{0}, 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].

drh@math.uchicago.edu