Next: Recursion-Theoretic Analogs Up: A Symmetric -Model Previous: The Main Results

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 (arithmetical transfinite recursion with restricted induction) and - (the transfinite induction scheme). For general background, see Simpson [5]. It is known [5, § VII.2] that - , and that every -model is a model of - .

Let be a countable model of , where . Define is a finite subset of and there exists meeting . The notion of being generic over is defined in the obvious way. As in §1, the basic forcing lemmas can be proved. Let be generic over . Put .

Lemma 2.1   satisfies the scheme (*) of Theorem 1.3.

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

Lemma 2.2   Let be a sentence with parameters from |N|. If , then .

Proof.Write as for some fixed . If , then for each we have that is dense in , hence . Thus , i.e., , so .

Remark 2.3   Since and is axiomatized by a sentence, it follows by Lemma 2.2 that . Lemma 2.2 also implies that and satisfy the same sentences with parameters from |N|. From this it follows that the recursive well orderings of and are the same, and that . It can also be shown that .

We now have:

Theorem 2.4   is conservative over for sentences.

Proof.Let be a sentence. Suppose . Let be a countable model of . Let as above. Since is a sentence, we have by Lemmas 2.1 and 2.2 that . Thus .

In order to obtain a similar result for - , we first prove:

Lemma 2.5   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 . In particular, by [5, Theorem VIII.6.7], the Gandy/Kreisel/Tait Theorem holds in . Thus for all we have

there exists meeting p such that .
Now, it is provable in that the predicate is . Thus we have , i.e., all ordinals are recursive''. This proves our lemma.

Remark 2.6   An alternative proof of Lemma 2.5 is to note that O does not exist'', because O would be definable but not hyperarithmetical. And O does not exist'' is equivalent over to all ordinals are recursive''. (Here O denotes the complete set of integers. See [5, § VIII.3].)

Theorem 2.7   - is conservative over - for sentences.

Proof.By Lemma 2.5 it suffices to prove: if transfinite induction for recursive well orderings, then transfinite induction for recursive well orderings. Let be such that <e is a recursive well ordering''. Suppose and . Put . Clearly . By definability of forcing, A is definable over . Hence there exists such that a is the <e-least element of A''. For each n<ea we have , but , so let be such that . Then a is the <e-least n such that ''. Thus transfinite induction for recursive well orderings.

Remark 2.8   Theorems 2.4 and 2.7 are best possible, in the sense that we cannot replace by . An example is the sentence all ordinals are recursive'', which is provable in but not in - .

Next: Recursion-Theoretic Analogs Up: A Symmetric -Model Previous: The Main Results
Stephen G Simpson
2000-05-23