# François G. Dorais

## Towsner's stable forcing


The actual size of the gaps between $\Ind{\Sigma^0_n}$ and $\Bnd{\Sigma^0_{n+1}}$ has recently been quantified by Towsner (2015), who used a beautiful forcing argument to show that $\Ind{\Sigma^0_n}$ gives absolutely no control whatsoever on $\Delta^0_{n+1}$-definable sets.

Theorem (Towsner 2015). 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 2015). 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$.


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 paper, I highly recommend reading it!

#### References

1. T. A. Slaman, 2004: $\Sigma_n$-bounding and $\Delta_n$-induction, Proc. Amer. Math. Soc. 132, no. 8, 2449–2456.

2. H. Towsner, 2015: On maximum conservative extensions, Computability 4, no. 1, 57–68.

Originally posted on by François G. Dorais. To the extent possible under law, François G. Dorais has waived all copyright and neigboring rights to this work.