FOM: logical status of pigeonhole principles, part 2
Stephen G Simpson
simpson at math.psu.edu
Sun Dec 17 17:30:45 EST 2000
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
More information about the FOM
mailing list