A classification of rapidly growing Ramsey functions

Abstract:

Let $f$ be a number-theoretic function. A finite set $X$ of natural numbers is called $f$-large if $card(X)\geq f(min(X))$. Let $PH_f$ be the Paris Harrington statement where we replace the largeness condition by a corresponding $f$-largeness condition. We classify those functions $f$ for which the statement $PH_f$ is independent of first order (Peano) arithmetic $PA$. If $f$ is a fixed iteration of the binary length function, then $PH_f$ is independent. On the other hand $PH_{\log ^*}$ is provable in $PA$. More precisely let $f_\alpha (i):= {\lvert i \rvert }_{H_\alpha ^{-1}(i)}$ where $\mid i\mid _h$ denotes the $h$-times iterated binary length of $i$ and $H_\alpha ^{-1}$ denotes the inverse function of the $\alpha$-th member $H_\alpha$ of the Hardy hierarchy. Then $PH_{f_\alpha }$ is independent of $PA$ (for $\alpha \leq \varepsilon _0$) iff $\alpha =\varepsilon _0$.