Next: Bibliography Up: A Symmetric -Model Previous: Recursion-Theoretic Analogs

In this section we present some additional results and open questions.

Lemma 4.1   Let be a formula with no free set variables other than X. The following is provable in . If and , then is a perfect tree and if X is a path through P then .

Proof.This is a well known consequence of formalizing the Perfect Set Theorem within . See Simpson [5, §§V.4 and VIII.3]. See also Sacks [4, §III.6].

Lemma 4.2   Let be a formula with no free set variables other than X. The following is provable in all ordinals are recursive''. If and , then is a perfect tree and if X is a path through P then .

Proof.Since is , we can write where R is a primitive recursive predicate. Let TX,Y be the tree consisting of all such that . For put

is well founded of height .
Note that, for each , is . Reasoning in all ordinals are recursive'', we have if and only if . Thus Lemma 4.2 follows easily from Lemma 4.1.

Theorem 4.3   Let T be or - . Let be a formula with no free set variables other than X. If and , then is a perfect tree and if X is a path through P then .

Proof.From Friedman [1] or Simpson [5, §VII.2], we have that the disjunction (1) all ordinals are recursive, or (2) there exists a countable coded -model M satisfying all ordinals are recursive''. In case (1), the desired conclusion follows from Lemma 4.2. In case (2), we have and , so the proof of Lemma 4.2 within M gives such that and . It follows that and . We can then apply Lemma 4.1 to to obtain the desired conclusion.

Corollary 4.4   Let T and be as in Theorem 4.3. If and , then and .

Proof.This follows easily from Theorem 4.3.

Theorem 4.5   Let T and be as in Theorem 4.3. If exactly one , then and .

Proof.Consider cases (1) and (2) as in the proof of Theorem 4.3. In both cases it suffices to show that, for all , if exactly one then and . This follows from Lemma 4.1 applied to .

Remark 4.6   Theorems 4.3 and 4.5 appear to be new. Corollary 4.4 has been stated without proof by Friedman [3, Theorems 3.4 and 4.4]. A recursion-theoretic analog of Corollary 4.4 has been stated without proof by Friedman [3, Theorem 1.7], but this statement of Friedman is known to be false, in view of Simpson [6]. A recursion-theoretic analog of Theorem 4.5 has been proved by Simpson/Tanaka/Yamazaki [7].

Question 4.7   Suppose and where is , or even arithmetical, with no free set variables other than X. Does it follow that ? A similar question has been asked by Friedman [2, unpublished].

Question 4.8   Suppose exactly one where is with no free set variables other than X. Does it follow that and ? If is arithmetical or then the answer is yes, by Simpson/Tanaka/Yamazaki [7].

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