Next: Bibliography
Up: A Symmetric Model
Previous: RecursionTheoretic Analogs
Some Additional Results
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 T_{X,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.
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 recursiontheoretic 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
recursiontheoretic 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: RecursionTheoretic Analogs
Stephen G Simpson
20000523