On Notions of Computability-Theoretic Reduction between
Π12 Principles
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].
drh@math.uchicago.edu