##
Combinatorial Principles Weaker than Ramsey's Theorem for Pairs

Status: *Journal of Symbolic Logic* vol. 72 (2007), pp. 171 - 206

Availability: PostScript, DVI, and PDF

**Abstract.** We investigate the complexity of various
combinatorial theorems about linear and partial orders, from the
points of view of computability theory and reverse mathematics. We
focus in particular on the principles ADS (Ascending or Descending
Sequence), which states that every infinite linear order has either an
infinite descending sequence or an infinite ascending sequence, and
CAC (Chain-AntiChain), which states that every infinite partial order
has either an infinite chain or an infinite antichain. It is
well-known that Ramsey's Theorem for pairs
(RT^{2}_{2}) splits into a stable version
(SRT^{2}_{2}) and a cohesive principle (COH). We show
that the same is true of ADS and CAC, and that in their cases these
versions are strictly weaker (which is not known to be the case for
RT^{2}_{2} and SRT^{2}_{2}). We also
analyze the relationships between these principles and other systems
and principles previously studied by reverse mathematics, such as
WKL_{0}, DNR, and BSigma_{2}, showing for instance
that WKL_{0} is incomparable with all of the systems we study;
and prove computability-theoretic and conservation results for
them. Among these results are a strengthening of the fact, proved by
Cholak, Jockusch, and Slaman, that COH is
Pi^{1}_{1}-conservative over the base system
RCA_{0}. We also prove that CAC does not imply DNR which,
combined with a recent result of Hirschfeldt, Jockusch, Kjos-Hanssen,
Lempp, and Slaman, shows that CAC does not imply
SRT^{2}_{2} (and so does not imply
RT^{2}_{2}). This answers a question of Cholak,
Jockusch, and Slaman.

Our proofs suggest that the essential distinction between ADS and CAC
on the one hand and RT^{2}_{2} on the other is that
the colorings needed for our analysis are in some way transitive. We
formalize this intuition as the notions of transitive and
semitransitive multicolorings and show that the existence of
homogeneous sets for such colorings is equivalent to ADS and CAC,
respectively. We finish with several open questions.

drh@math.uchicago.edu