It is well known that a model $\newcommand{\MN}{\mathfrak{N}}\MN$ of $\newcommand{\RCA}[1]{\mathsf{RCA}_{#1}}\RCA0$ satisfies $\Sigma^0_n$-induction ($\newcommand{\Ind}[1]{\mathsf{I}{#1}}\Ind{\Sigma^0_n}$) if and only if it satisfies bounded $\Sigma^0_n$-comprehension: if $\phi(x)$ is a $\Sigma^0_n$-formula (with parameters) then the set $\set{x \lt b: \phi(x)}$ exists for every number $b$ in $\MN$. Thus, it follows that $\Pi^0_n$-induction also holds and indeed induction holds for all boolean combinations of $\Sigma^0_n$ formulas. However, $\Ind{\Sigma^0_n}$ offers no control over sets of higher complexity than that. In particular, $\Delta^0_{n+1}$-induction may fail very badly in a model of $\Ind{\Sigma^0_n}$. Indeed, by a result of Slaman [1] $\Delta^0_{n+1}$-induction is equivalent to $\Sigma^0_{n+1}$-bounding ($\newcommand{\Bnd}[1]{\mathsf{B}{#1}}\Bnd{\Sigma^0_{n+1}}$) and it is known that we have a strict hierarchy: $$\Ind{\Sigma^0_1} \quad\WHEN\quad \Bnd{\Sigma^0_2} \quad\WHEN\quad \Ind{\Sigma^0_2} \quad\WHEN\quad \Bnd{\Sigma^0_3} \quad\WHEN \cdots$$ The actual size of the gaps between $\Ind{\Sigma^0_n}$ and $\Bnd{\Sigma^0_{n+1}}$ has recently been quantified by Henry Towsner, who included a beautiful forcing argument in his preprint [2] that shows that $\Ind{\Sigma^0_n}$ gives absolutely no control whatsoever on $\Delta^0_{n+1}$-definable sets.

In a recent paper [1], Jared Corduan and I considered various notions of combinatorial indecomposability for finite ordinal powers of $\omega.$ In this process, we uncovered two weak forms of Ramsey’s theorem for pairs ($\newcommand{\RT}[2]{\mathsf{RT}^{#1}_{#2}}\RT2k$):

• The Weak Ramsey Theorem ($\newcommand{\Wk}{\mathsf{W}}\Wk\RT2k$). For every coloring $c:\N^2\to\set{0,\dots,k-1}$ there are a color $d \lt k$ and an infinite set $H$ such that $\set{y \in \N : c(x,y) = d}$ is infinite for every $x \in H.$
• The Hyper-Weak Ramsey Theorem ($\newcommand{\HWk}{\mathsf{HW}}\HWk\RT2k$). For every coloring $c:\N^2\to\set{0,\dots,k-1}$ there are a color $d \lt k$ and an increasing function $h:\N\to\N$ such that $\bigcup_{x=h(i-1)}^{h(i)-1} \set{y \in \N : c(x,y) = d}$ is infinite for every $i \in \N.$

The first is equivalent to what we called the game indecomposability of the ordinal $\omega^2,$ and the second is related to the lexicographic indecomposability of $\omega^2.$ You can find out more about these notions of indecomposability in our paper, what I want to write about here is the forcing technique that we used to show that $\HWk\RT22$ is $\Pi^1_1$-conservative over $\mathsf{RCA}_0$ with $\Sigma^0_2$-induction and to separate the two principles $\Wk\RT22$ and $\HWk\RT22.$ I’ve been calling the method envelope forcing since the basic idea is to force over a larger model that envelops the original one rather than forcing over the ground model itself. In the following, I will give a brief tour of this method, skipping all the gory details (that can be found in our paper).

I just read an interesting paper by Thomas Forster: The Paris–Harrington Theorem in an NF context [1]. This paper is a progress report on the status of the Paris–Harrington Theorem in Quine’s New Foundations (NF). Forster shows that the Paris–Harrington Theorem is at least consistent with NF, but leaves open the question whether it is provable in NF. Recall that the Paris–Harrington Theorem is a variation on Ramsey’s Theorem, where the homogeneous set $x$ is required to be relatively large: $\min(x) < |x|$. This result is not provable in Peano Arithmetic (PA). In fact, it is logically equivalent to $\Sigma_1$-reflection for PA.

The main issue with the Paris–Harrington Theorem in NF is that the notion of relative largeness is ill-typed. In addition to Forster, Harvey Friedman had also observed this [2]:

In ‘relatively large’, an integer is used both as an element of a finite set and as a cardinality (of that same set).

This is a serious problem in NF where cardinal numbers are defined as equivalence classes of equinumerous sets. Thus, the relative largeness condition $\min(x) < |x|$ entails a direct comparison between an element of the finite set $x$ and the cardinal number $|x|$ to which $x$ belongs. Needless to say that this is difficult to formulate in a stratified manner, as required for set comprehension in NF. Forster manages to work around this, but the winding road has so many twists that he only manages to get a consistency result rather than an actual proof.

While Forster does not directly discuss the issue of the strength of the Paris–Harrington Theorem in the paper, he does raise an interesting question whether the added strength of the theorem has any link to this failure of typing. I used to believe that while the naturalness of the Paris–Harrington Theorem could honestly be questioned, there was one real advantage of this example over the non-provable statements of Gödel and Rosser in that the Paris–Harrington Theorem did not appear to directly depend on self-reference. This observation by Forster and Friedman casts some serious doubts on this…

• Is the notion of relative largeness really self-referential?
• Is the fact that relative largeness is ill-typed the key to the strength of the Paris–Harrington Theorem?

References

[1] T. E. Forster, “The Paris-Harrington theorem in an NF context,” in One hundred years of axiomatic set theory, Acad.-Bruylant, Louvain-la-Neuve, 2010, vol. 17, pp. 97-109.
[Bibtex]
@incollection{Forster10,
AUTHOR = {Forster, Thomas Edward},
TITLE = {The {P}aris-{H}arrington theorem in an {NF} context},
BOOKTITLE = {One hundred years of axiomatic set theory},
SERIES = {Cahiers Centre Logique},
VOLUME = {17},
PAGES = {97--109},
YEAR = {2010},
MRCLASS = {03E70 (03E35)},
MRNUMBER = {2796910},
}
[2] H. Friedman, [FOM] PA incompleteness, 2007.
[Bibtex]
@misc{Friedman07,
AUTHOR = {Friedman, Harvey},
TITLE = {{[FOM]} {PA} incompleteness},
HOWPUBLISHED = {FOM},
NOTE = {\url{http://www.cs.nyu.edu/pipermail/fom/2007-October/012046.html}},
YEAR = {2007},
URL = {http://www.cs.nyu.edu/pipermail/fom/2007-October/012046.html},
}