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.
Theorem (Towsner). If $\MN$ is a model of $\RCA0$ and $X$ is any external set of numbers in $\MN$ then there is an $\omega$-extension $\MN’$ of $\MN$ that satisfies $\RCA0$ and such that $X$ is $\Delta^0_2$-definable in $\MN’$.
Theorem (Towsner). If $\MN$ is a model of $\RCA0+\Ind{\Sigma^0_n}$ and $X$ is any external set of numbers in $\MN$ then there is an $\omega$-extension $\MN’$ of $\MN$ that satisfies $\RCA0+\Ind{\Sigma^0_n}$ and such that $X$ is $\Delta^0_{n+1}$-definable in $\MN’$.
I will only outline the proof of the first result. The Limit Lemma gives a very combinatorial way to understand $\Delta^0_2$-definable sets over $\MN$. Namely, the external set $X$ is $\Delta^0_2$-definable in $\MN$ exactly when there is a function $c:\N^2\to\set{0,1}$ in $\MN$ such that $\lim_{y\to\infty} c(x,y)$ exists for every $x$ and $x \in X \IFF \lim_{y\to\infty} c(x,y) = 1$. In general, a function $f:\N^2\to\N$ such that $\lim_{y\to\infty} f(x,y)$ exists for every $x$ is called stable. Towsner’s strategy is to generically add a stable coloring $c:\N^2\to\set{0,1}$ such that $x \in X \IFF \lim_{y\to\infty} c(x,y) = 1$ and show that the forcing to add such a coloring preserves $\RCA0$.
Towsner doesn’t name this forcing, so I will take the liberty of coining a name for it — Towsner’s Stable Forcing and I will denote it $\newcommand{\ST}{\mathbb{ST}}\ST_X$ — at least for the purpose of this post. The forcing can be described as follows. Conditions of $\ST_X$ are pairs $p = (c_p,V_p)$ where $c_p$ is (a code for) an $\MN$-finite partial function $\N^2\to\set{0,1}$ and $V_p$ is a truly finite set of stability promises (discussed shortly); and the ordering of conditions is $q \leq p$ iff $c_q$ extends $c_p$ and $V_p \subseteq V_q$. The stability promises consist of pairs $(x,y) \in \N^2$ that promise that the values of the generic coloring with first coordinate $x$ stabilize from $y$ on to the correct value predicted by $X$. More precisely, if $(x,y) \in V_p$ then $(x,y) \in \dom(c_p)$, $c_p(x,y) = 1 \IFF x \in X$, and $c_p(x,y’) = c_p(x,y)$ for all $y’ \gt y$ such that $(x,y’) \in \dom(c_p)$. Since $X$ is not in $\MN$ and $\MN$ usually has no way of distinguishing truly finite sets from others, the forcing $\ST_X$ is not definable in $\MN$ though all conditions are in $\MN$. It is therefore hopeless try to internalize this forcing but we will see that if $G$ is a (sufficiently) generic filter over $\ST_X$, then $c(x,y) = i \IFF (\exists p \in G)(c_p(x,y) = i)$ defines a total coloring $c:\N^2\to\set{0,1}$ and that $\MN’ = \MN[c]$ is as required for the theorem.
The main difficulty is in showing that $\MN[c]$ still satisfies $\Ind{\Sigma^0_1}$. The trick is that if an extension $q \leq p$ forces a bounded statement, then only an $\MN$-finite amount of the information of the information that $q$ knows about $c$ is actually used to witness that fact. Though $V_q$ contains an infinite amount of promised information, we can trim down $V_q$ and throw all the information actually used into $c_q$ to get a new condition $q’ \leq p$ that still forces the bounded statement and has no more stability promises than $p$ had. Thus, if $p \Vdash \exists v\phi(v)$ where $\phi(v)$ is bounded, then there are an extension $q \leq p$ with $V_q = V_p$ and $x \in \N$ such that $q \Vdash \phi(x)$. Using this, given a condition $p$ and a $\Sigma^0_1$-formula $\phi(v)$ we can work in $\MN$ to find an extension $q \leq p$ with $V_q = V_p$ such that $$p \Vdash \forall v\lnot\phi(v) \quad\text{or}\quad p \Vdash \phi(x) \land (\forall v \lt x)\lnot\phi(v) \text{ for some $x$.}$$ Since $V_q = V_p$, we know that $q$ actual condition in $\ST_X$, provided that $p$ is one in the first place, without worrying about $X$, true finiteness, or anything that is not within reach of $\MN$.
Of course, this forcing construction is only a small part of Towsner’s excellent preprint, I highly recommend reading it!
References
- T. A. Slaman, $\Sigma_n$-bounding and $\Delta_n$-induction, Proceedings of the American Mathematical Society 132 (2004), 2449–2456. [doi:10.1090/S0002-9939-04-07294-6]
- H. Towsner, On maximal conservative extensions, preprint. [arχiv:1302.1488]
Edit: I redacted a claim that the second result follows from the first using arguments similar to those Jared Corduan and I used in On the indecomposability of $\omega^n$. That unfortunate claim was at best incomplete and possibly false. Since the claim was only tangential to the topic, early redaction was the best course of action.
Excellent piece of research blogging. You could generate a citation via mathblogging.org and add it.
How does one generate a citation?
Got to Mathblogging.org, hit the menu item “Generate Citation”, follow instructions?
The citations are MLA style, which I am not particularly fond of, and WordPress tends to strip some stuff out. What parts are necessary to make scanning work?
I’m not sure, but I’m guessing the title-tag of the span is the only crucial thing since it contains structured data.