[FOM] Paris Harrington for two colors

[Andreas Weiermann]

Dear members of FOM,

during the Utrecht workshop on Ramsey numbers the unprovability
of the Paris Harrington theorem
for two colors has been discussed. In Ketonen and Solovay
it is proved that 7 is a sufficient number of
colors for unprovability. In Takeuti's book
a proof is given that 3 suffices (following Quinsey).
An inspection by a paper by Erdoes Mills shows that
already 2 is sufficient.
This might be well known today.

My vision why results of this type might be important to
a wider audience is as follows.

Let R^3_2(f)(m) be the least number r such that
for all P:[r]^3\to 2 there is a P homogeneous Y\subseteq r such that
card Y\geq \max\{f(\min Y),m\}
Then R^3_2(identity) is Ackermannian but R^3_2(constant) is
bounded by a double exponential function.
Now if for f(i)=\sqrt[3]{\log(i)} the function
R^3_2(f) would be Ackermannian then we would have
that R^3_2 is not bounded by n\mapsto 2^{n^3}.
[Remark: For f(i)=\log(i) the function 
R^3_2(f) is Ackermannian.]

Thus a result of a logical flavour would affect the asymptotic
of the standard Ramsey function (which is a classic in combinatorics).
To study R^3_2(f) one may employ e.g. non standard models
or any other means. 

Best regards,
A. Weiermann