7
$\begingroup$

Recall that the Paris-Harrington Principle, $\mathsf{PH}$, is the statement that for each $e, r, k < \omega$ there is an $N < \omega$ so that given any coloring $c:[N]^e \to r$ there is an $H \subseteq N$ so that $c \upharpoonright [H]^e$ is constant, and the cardinality of $H$ is larger than both $k$ and ${\rm min}(H)$. This last clause separates $\mathsf{PH}$ from finite Ramsey's theorem. Famously Paris and Harrington showed that $\mathsf{PH}$ is not provable in $\mathsf{PA}$ but it is true in the standard model. Of course in general the interest from a logical point of view is the non-provability result but in this question I want to focus on the fact that it's true in the standard model.

The standard proof of this fact mimics the proof of finite Ramsey's theorem as an application of Konig's Lemma and infinite Ramsey theorem noting that, in the infinite homogeneous set one gets, we can choose $H$ as big a finite segment as we like. If people are unclear what I mean, I can write this down. The same proof actually shows that for $any$ $f:\omega \to \omega$ we can actually arrange, in the definition of $\mathsf{PH}$ that not only $|H| > {\rm min}(H)$ but actually $|H| > f({\rm min}(H))$. Let us denote this (seemingly stronger) statement by $\mathsf{PH}_f$. So, for example, $\mathsf{PH}$ is $\mathsf{PH}_{identity}$. My question is:

When is it the case that for $f, g:\omega \to \omega$ do we have $\mathsf{PH}_f$ implies $\mathsf{PH}_g$ over $\mathsf{PA}$ as a base theory?

For example, one particular instance of this question that I'm interested in is:

Does $\mathsf{PH}$ imply $\mathsf{PH}_f$ for all computable $f$? What about all arithmetic $f$?

$\endgroup$
4
  • $\begingroup$ I guess I should clarify here $f:\omega \to \omega$ should really mean ``definable" in some model of $\mathsf{PA}$ (and $\omega$ really the universe of that model). $\endgroup$ – Corey Bacal Switzer Feb 7 at 21:47
  • $\begingroup$ Isn't that called some strong Ramsey principle? $\endgroup$ – Asaf Karagila Feb 8 at 1:07
  • 2
    $\begingroup$ Have you checked out the papers by my supervisor Andreas Weiermann? He has even discovered pretty tight 'phase transitions' for the (un)provability of principles like your PH$_f$, if memory serves. $\endgroup$ – Sam Sanders Feb 8 at 18:21
  • $\begingroup$ It is worth pointing out that, in their original paper, Paris and Harrington prove that provably in $\mathsf{PA}$, $\mathsf{PH}$ implies $\mathsf{PH}_f$ for all primitive recursive $f$. In light of their result, the first nontrivial instance of your question then is $\mathsf{PH}_f$, when $f$ is the Ackermann function. $\endgroup$ – Ali Enayat Apr 5 at 1:54
4
$\begingroup$

The following paper by my supervisor Andreas Weiermann studies the principle PH$_f$ you mention:

A. Weiermann, A classification of rapidly growing Ramsey functions Proc. Amer. Math. Soc. 132 (2004), no. 2, 553–561.

There are many follow-up papers with plenty of variations by Andreas and his collaborators.

As to your question, any answer here depends greatly on the exact technical details, so do consult the original paper if possible. Intuitively, the answer is two-fold as follows:

  1. PH$_f$ is not provable in PA for $f$ equal to log$^d$ for any fixed $d\in \mathbb{N}$.

  2. One can obtain sharper result as follows: $d$ can be replaced with an unbounded (provable say in ZFC) function that grows so slow that there are models of PA in which it is bounded above. An example of the latter is $H_{\epsilon_0}^{-1}$, i.e. the inverse of the Hardy function with ordinal $\epsilon_0$.

Note that $H_{\epsilon_0}^{-1}$ may seem weird, but PA actually proves that it is total.

$\endgroup$
3
  • 2
    $\begingroup$ Has Andreas Weiermann also worked on Paris-Harrington principles for large $f$? That seems to be the OP's main interest here. $\endgroup$ – Andreas Blass Feb 8 at 22:30
  • $\begingroup$ That I cannot recall immediately. I have sent Andreas an email to check out this thread. I believe his main interest was with these 'phase transitions'. Perhaps his (other) students have worked on this. $\endgroup$ – Sam Sanders Feb 9 at 8:47
  • $\begingroup$ @SamSanders This is very helpful, thanks! I would be very interested to hear what Andreas (Weiermann) says about it. The papers you link to are quite interesting but as Andreas (Blass) notes in the comment above they don't quite answer the question I asked so I'm going to wait to accept. $\endgroup$ – Corey Bacal Switzer Feb 9 at 19:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.