Conservation Results

In this section we generalize the construction of §1 to a wider setting. We then use this idea to obtain some conservation results involving the scheme (*) of Theorem 1.3.

Two important subsystems of second order arithmetic are $\mathsf{ATR}_0$(arithmetical transfinite recursion with restricted induction) and $\Pi^1_\infty$- $\mathsf{TI}_0$ (the transfinite induction scheme). For general background, see Simpson [5]. It is known [5, § VII.2] that $\mathsf{ATR}_0\subseteq\Pi^1_\infty$- $\mathsf{TI}_0$, and that every $\beta$-model is a model of $\Pi^1_\infty$- $\mathsf{TI}_0$.

Let $(N,\mathcal{S})$ be a countable model of $\mathsf{ATR}_0$, where $\mathcal{S}\subseteq P(\vert N\vert)$. Define $\mathcal{P}_{(N,\mathcal{S})}=\{p:(N,\mathcal{S})\models(p$ is a finite subset of $\omega\times\omega^{<\omega}$ and there exists $\langle X_n\rangle_{n\in\omega}$ meeting $p)\}$. The notion of $\langle G_n\rangle_{n\in\vert N\vert}$ being generic over $(N,\mathcal{S})$ is defined in the obvious way. As in §1, the basic forcing lemmas can be proved. Let $\langle G_n\rangle_{n\in\vert N\vert}$ be generic over $(N,\mathcal{S})$. Put $\mathcal{S}'=\{G_n:n\in\vert N\vert\}$.

Lemma 2.1   $(N,\mathcal{S}')$ satisfies the scheme (*) of Theorem 1.3.

Proof.The proof is a straightforward generalization of the arguments of §1.$\Box$

Lemma 2.2   Let $\psi$ be a $\Pi^1_2$ sentence with parameters from |N|. If $(N,\mathcal{S})\models\psi$, then $(N,\mathcal{S}')\models\psi$.

Proof.Write $\psi$ as $\forall X\,(X\in S_e)$ for some fixed $e\in\vert N\vert$. If $(N,\mathcal{S})\models\psi$, then for each $n\in\vert N\vert$ we have that $\{p\in\mathcal{P}_{(N,\mathcal{S})}:(e,\langle n\rangle)\in p\}$ is dense in $\mathcal{P}_{(N,\mathcal{S})}$, hence $\emptyset\Vdash X_n\in S_e$. Thus $\emptyset\Vdash\forall X\,(X\in S_e)$, i.e., $\emptyset\Vdash\psi$, so $(N,\mathcal{S}')\models\psi$.$\Box$

Remark 2.3   Since $(N,\mathcal{S})\models\mathsf{ATR}_0$ and $\mathsf{ATR}_0$ is axiomatized by a $\Pi^1_2$ sentence, it follows by Lemma 2.2 that $(N,\mathcal{S}')\models\mathsf{ATR}_0$. Lemma 2.2 also implies that $(N,\mathcal{S})$ and $(N,\mathcal{S}')$ satisfy the same $\Pi^1_1$ sentences with parameters from |N|. From this it follows that the recursive well orderings of $(N,\mathcal{S})$ and $(N,\mathcal{S}')$ are the same, and that $\mathrm{HYP}_{(N,\mathcal{S})}=\mathrm{HYP}_{(N,\mathcal{S}')}$. It can also be shown that $\mathrm{HYP}_{(N,\mathcal{S})}=\mathcal{S}\cap\mathcal{S}'$.

We now have:

Theorem 2.4   $\mathsf{ATR}_0+(*)$ is conservative over $\mathsf{ATR}_0$ for $\Sigma^1_2$ sentences.

Proof.Let $\varphi$ be a $\Sigma^1_2$ sentence. Suppose $\mathsf{ATR}_0\not\vdash\varphi$. Let $(N,\mathcal{S})$ be a countable model of $\mathsf{ATR}_0+\lnot\,\varphi$. Let $\mathcal{S}'=\{G_n:n\in\vert N\vert\}$ as above. Since $\lnot\,\varphi$ is a $\Pi^1_2$ sentence, we have by Lemmas 2.1 and 2.2 that $(N,\mathcal{S}')\models\mathsf{ATR}_0+(*)+\lnot\,\varphi$. Thus $\mathsf{ATR}_0+(*)\not\vdash\varphi$.$\Box$

In order to obtain a similar result for $\Pi^1_\infty$- $\mathsf{TI}_0$, we first prove:

Lemma 2.5   $(N,\mathcal{S}')\models$ ``all ordinals are recursive'', i.e., ``every well ordering is isomorphic to a recursive well ordering''.

Proof.Recall from [5, §§VIII.3 and VIII.6] that all of the basic results of hyperarithmetical theory are provable in $\mathsf{ATR}_0$. In particular, by [5, Theorem VIII.6.7], the Gandy/Kreisel/Tait Theorem holds in $\mathsf{ATR}_0$. Thus for all $p\in\mathcal{P}_{(N,\mathcal{S})}$ we have

$(N,\mathcal{S})\models$ there exists $\langle X_n\rangle_{n\in\omega}$ meeting p such that $\forall n\,(\omega_1^{X_n}=\omega_1^{\mathrm{CK}})$.

Now, it is provable in $\mathsf{ATR}_0$ that the predicate $\omega_1^X=\omega_1^{\mathrm{CK}}$ is $\Sigma^1_1$. Thus we have $\emptyset\Vdash\forall X\,(\omega_1^X=\omega_1^{\mathrm{CK}})$, i.e., $\emptyset\Vdash$ ``all ordinals are recursive''. This proves our lemma.$\Box$

Remark 2.6   An alternative proof of Lemma 2.5 is to note that $\mathsf{ATR}_0+(*)\vdash$ ``O does not exist'', because O would be definable but not hyperarithmetical. And ``O does not exist'' is equivalent over $\mathsf{ATR}_0$ to ``all ordinals are recursive''. (Here O denotes the complete $\Pi^1_1$ set of integers. See [5, § VIII.3].)

Theorem 2.7   $\Pi^1_\infty$- $\mathsf{TI}_0+(*)$ is conservative over $\Pi^1_\infty$- $\mathsf{TI}_0$ for $\Sigma^1_2$ sentences.

Proof.By Lemma 2.5 it suffices to prove: if $(N,\mathcal{S})\models$ transfinite induction for recursive well orderings, then $(N,\mathcal{S}')\models$ transfinite induction for recursive well orderings. Let $e\in\vert N\vert$ be such that $(N,\mathcal{S})\models$ ``<<sub>e</sub> is a recursive well ordering''. Suppose $p\Vdash\exists n\,(n\in\mathrm{field}({<}_e)$ and $\varphi(n))$. Put $A=\{n\in\mathrm{field}({<}_e):p\not\Vdash\lnot\,\varphi(n)\}$. Clearly $A\ne\emptyset$. By definability of forcing, A is definable over $(N,\mathcal{S})$. Hence there exists $a\in A$ such that $(N,\mathcal{S})\models$ ``a is the <_e-least element of A''. For each n<_ea we have $p\Vdash\lnot\,\varphi(n)$, but $p\not\Vdash\lnot\,\varphi(a)$, so let $q\le p$ be such that $q\Vdash\varphi(a)$. Then $q\Vdash$ ``a is the <_e-least n such that $\varphi(n)$''. Thus $(N,\mathcal{S}')\models$ transfinite induction for recursive well orderings.$\Box$

Remark 2.8   Theorems 2.4 and 2.7 are best possible, in the sense that we cannot replace $\Sigma^1_2$ by $\Pi^1_2$. An example is the $\Pi^1_2$ sentence ``all ordinals are recursive'', which is provable in $\mathsf{ATR}_0+(*)$ but not in $\Pi^1_\infty$- $\mathsf{TI}_0$.