[FOM] Erdoes probabilistic method

Andreas Weiermann weiermann at math.uu.nl
Tue Apr 20 11:48:31 EDT 2004

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
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 

Using Ketonen Solovay methods the results
shall extend to ISigma_k.

Best regards,
Andreas Weiermann

More information about the FOM mailing list