FOM: large cardinals and combinatorics

[Stephen G Simpson]

Joseph Shoenfield 30 Mar 1998 17:17:09 says:
 > Two replies to my recent message on the above subject state that I
 > failed to distinguish finite combinatorics from infinite
 > combinatorics.  I would be much more impressed with this reply if
 > it included a reasonable syntactic definition of "finite
 > combinatorial statement"

I wasn't trying to impress anyone.  My only purpose was to draw some
meaningful distinctions and advance the discussion.

Joe, I don't understand the thrust of your objection.  Are you saying
that there is no meaningful distinction here?  Don't mathematicians
working in this area always distinguish among finite, countable, and
uncountable combinatorics?  They don't need to replace this informal
distinction by a syntactic one.  You yourself used this distinction in
your original posting, when you said:

 > The combinatorial principles were infinite generalizations of
 > well-known results in finite combinatorics.

My impression is that these uncountable generalizations are not of
much interest to mathematicians working in this area.  For instance,
the book by Graham, Rothschild and Spencer on Ramsey theory covers the
finite case very thoroughly, the countably infinite case to some
extent, and the uncountable cases not at all.  The distinction is
according to whether the underlying set (in whatever Ramsey-type
theorem is being considered) is finite, countably infinite, or
uncountable.

 > which included Harvey's principles but not Erdos's.  

Harvey's principles are of the same general character as the original
Ramsey theorem: If you color the m-element subsets of N with n colors,
then there is an infinite set all of whose m-element subsets get the
same color.  Here N is the set of natural numbers, and m and n are
positive integers.  This can be expressed as omega -> (omega)^m_n,
where omega is aleph_0, the cardinality of N.  Erdos studied
propositions such as kappa -> (kappa)^m_n, where kappa is an
inaccessible cardinal.  Isn't that the Erdos work that you were
referring to?  There is a large and obvious difference between aleph_0
and inaccessible cardinals in terms of direct relevance to core
mathematics.

You are asking for a syntactical distinction.  How about "expressible
in the language of second order arithmetic", i.e. expressible in terms
of natural numbers and sets of natural numbers?  Joe, isn't that an
answer to your question?  Am I walking into some trap here?

 > I would be still more impressed if one could show that these finite
 > combinatorial statements had some absoluteness properties not
 > shared by Erdos's results.

Well, Ramsey's theorem and Harvey's statements are Pi^1_2, hence
absolute in the sense of G"odel, by the Shoenfield absoluteness
theorem.  The property of being an inaccessible cardinal (even an
uncountable one) is not absolute in this sense.  So far as I can see,
these simple observations answer and do justice to your question.
Actually, Harvey's statements are expressible in the language of first
order arithmetic, Pi^0_2 and even Pi^0_1, so that's even better.

 > (Please take this as a challenge, not a criticism.)

Joe, I'm thrashing here, giving several different and obvious answers
to your questions, simply because I don't understand the thrust of the
questions.  So far, the challenge for me is to understand what you are
getting at.  I'm genuinely somewhat mystified.

-- Steve