FOM: logical status of pigeonhole principles, part 2

[Stephen G Simpson]

This is a follow-up to recent postings by Matt Frank, Alasdair
Urquhart and myself concerning the logical status of pigeonhole
principles.

A well-known infinitary pigeonhole principle says: if you stuff
infinitely many pigeons into n pigeonholes, at least one of the
pigeonholes will get infinitely many pigeons.  This is
PHP(aleph_0,n,aleph_0) in the notation of my earlier posting, or
aleph_0->(aleph_0)^1_n in the Erdos notation.  It may be viewed as the
special case k = 1 of Ramsey's Theorem: if you color the k-element
subsets of an infinite set with n colors, there will be an infinite
subset all of whose k-element subsets get the same color.  In the
Erdos notation this is aleph_0->(aleph_0)^k_n, also sometimes written
as RT(k,n).  We abbreviate the statement "for all n, RT(k,n)" as
simply RT(k).

Thus RT(1) is just the infinitary pigeonhole principle mentioned
above.

[ I apologize for the profusion of notation. ]

What is the logical status of RT(1)?  Below I will try to organize
some of the history of this problem.

Jeffry L. Hirst in his Ph D thesis (Penn State, 1987) proved:

  RT(1) is equivalent over RCA_0 to Pi^0_1 bounding.

In particular, RT(1) is not provable in RCA_0.

A couple of months ago, Takeshi Yamazaki made the following
observation.  Let RCA_0^* be the weak variant of RCA_0 introduced by
Simpson/Smith (1986, APAL), obtained by removing Sigma^0_1 induction
and replacing it with exponentiation plus Sigma^0_0 induction.  [See
also Section X.4 of my book "Subsystems of Second Order Arithmetic"
(http://www.math.psu.edu/simpson/sosoa/).]  Then RT(1) implies
Sigma^0_1 induction over RCA_0^*.  The proof is not difficult.  I can
show it to anyone who is interested.

Thus we have the following improvement of Jeff Hirst's result:

  RT(1) is equivalent over RCA_0^* to Sigma^0_1 induction plus 
  Pi^0_1 bounding.

Combining this with results on Ramsey's Theorem that are in my book (a
relevant name here is Carl Jockusch), it follows that RT(3) (or RT(k)
for any k>3) is equivalent over RCA_0^* to arithmetical comprehension.
This answers a question that was stated in my book.

Of course RT(2) does not imply arithmetical comprehension, and there
is an omega-model for the independence, by Seetapun's Theorem.

A remaining open question is whether, for instance, RT(3,2) is
equivalent over RCA_0^* to arithmetical comprehension.

-- Steve