[FOM] Erdoes probabilistic method

[Andreas Weiermann]

Dear all,

in December 2000 there was some discussion
on the probabilistic method in FOM.
Perhaps it is worth to remark the following
recent application to foundations of mathematics. 

Let A be the Ackermann function
and A^{-1}(i) be the corresponding slow
growing inverse function. Let A_n be the
n-th branch of A and A_n^{-1} its inverse.
Let PH^2_f be the Paris Harrington assertion
for coloring of pairs and f-largeness condition.

Then for any n PRA proves PH^2_f for
f(i)=log(i)/A_n^{-1}(i)
The probabilistic method yields that
for any epsilon>0 PRA does not prove 
PH^2_f for 
f(i)=epsilon log(i).
(The partition which has been used is not defined
explicitly. It exists by the prob. method.)
Presumably the same proof gives:
PRA does not prove 
PH^2_f for 
f(i)=log(i)/A^{-1}(i).

Using Ketonen Solovay methods the results
shall extend to ISigma_k.


Best regards,
Andreas Weiermann