FOM: miniaturization

Soren Moller Riis smriis at brics.dk
Wed Sep 15 11:09:10 EDT 1999


--------------------------
FOM: miniaturization
--------------------------

Jan Mycielski wrote:

> > the statements of Paris and Harrington (for PA), and those of Friedman
> > which I saw, do not appear to me more appealing than S(T) ...

Steve Simpson replied:

> I propose that we try to get to the bottom of this issue right here on
> the FOM list, by simply comparing the corresponding statements side by
> side.
>
> First, let's look at finitary statements that imply Con(PA).
>
> The Paris-Harrington statement is:
>
>  For all k, l, m there exists n so large that, if you color the
>  k-element subsets of {1,...,n} with l colors, then there will be
>  subset X of cardinality at least m all of whose k-elements subsets
>  have the same color, and such that the cardinality of X is greater
>  than the smallest element of X.
>
> Let's call this statement P-H.  I think we can agree that P-H is
> reasonably natural and appealing from the mathematician's point of
> view.  (The kind of mathematician I have in mind is a finite

In my MA (from 1989) I considered ideas very similar to those of 
Mycielski. In the case of PA the sentence S(PA) is very similar 
to P-H. It can be phrased

For all k, l, m there exists n so large that, if you color the
k-element subsets of {1,...,n} with l colors, then there will be
a subset X of cardinality at least size m such that all (k+1)-element
subsets of {1,2,...,n} which have the k largest elements in X
have a color which only depend on the smallest element (which might
not be in X).

In my MA-thesis I stated and showed that this version is
independent of Peano's Arithmetic. I did it by developing a version
of finite model theory in which quantifiers do not have to range
over the same domains. The principle above falls out almost
automatically from this. All this is in Danish in my 156 page
MA-thesis! Later I discovered that Mycielski already did something 
similar and I never published my work even though it differs from 
Mycielskis work in various ways. 

In my opinion my MA-thesis version of PH is not quite as elegant 
as Paris and Harringtons version.
On the other hand I think it is more canonical
in the sense that it almost automatically appear as result of
an instance of a general method of producing independent
combinatorial principles. While doing my MA-thesis I tried to get nice
versions S(ZFC), but I did not succeed. 

Some might already pity Prof. Mycielski that he finally decided to
step into the boxing ring (read: the FOM-arena)  where Steve kindly 
offered a pair of Boxing gloves (read: offered a challenge). 

Personally I hope this discussion will turn into a constructive
and rational debate. I would really like to see an artistic and 
nice version of S(ZFC) rather than a new exfom list!!!
There is a general method to produce combinatorial finitistic
independence results. The consistency sentence itself can be viewed
as a combinatorial principle about strings. It is however
not a "natural" combinatorial principle. In my opinion
S(ZFC) is not a natural principle, but perhaps it is possible
to rephrase as a natural combinatorial principle?

Soren Riis










More information about the FOM mailing list