# Sets and Models of

Stephen G. Simpson

Department of Mathematics

Draft: May 8, 2000

Pennsylvania State University

### Abstract:

We show that any two Medvedev complete subsets of are recursively homeomorphic. We obtain a set of countable coded -models of with a strong homogeneity property. We show that if is a generic element of , then the -model of coded by satisfies if is definable from , then is Turing reducible to . We use a result of Kucera to refute some plausible conjectures concerning -models of . We generalize our results to non--models of . We discuss the significance of our results for foundations of mathematics.

This research was partially supported by NSF grant DMS-0070718. For helpful discussions and correspondence, I thank F. Ferreira, A. M. Fernandes, K. Tanaka, and T. Yamazaki.

AMS Subject Classifications: 03F35, 03D30, 03D80, 03B30.

This paper has been accepted for publication in Reverse Mathematics 2001, to appear.

# Introduction

In this paper we apply recursion-theoretic methods to the study of -models of subsystems of second order arithmetic. Specifically, we present some results concerning subsets of , along with applications to countable -models of . These results and applications may be regarded as an addendum or supplement to Simpson [30, §VIII.2]. We also present generalizations to countable non--models of . These generalizations may be regarded as an addendum to Simpson [30, §IX.2].

For background on subsystems of second order arithmetic, see Simpson [30]. We recall here that is the subsystem consisting of comprehension and induction, and is the subsystem consisting of plus Weak König's Lemma, i.e., the statement that every infinite tree of finite sequences of 's and 's has a path. These two systems play an important role in Reverse Mathematics [30]. Their -models are easy to understand in recursion-theoretic terms. An -model of is a set such that (i) , (ii) for all , and (iii) if and then . An -model of has the additional property that if and is an infinite tree of finite sequences of 's and 's, then has a path in .

There is a large recursion-theoretic literature on subsets of and degrees of elements of such sets. An important paper in this area is Jockusch/Soare [16]. An extensive recent survey is Cenzer/Remmel [3]. This topic is well known to be closely related to -models of . The connection is as follows: is if and only if there exists a recursive tree of finite sequences of 's and 's such that is a path through .

In the model-theoretic literature, -models of are known as Scott systems, after Scott [25], who proved that is a countable -model of if and only if is the set of sets representable in some complete extension of Peano arithmetic. This idea is important in the study of models of arithmetic. See also Kaye [17].

Here is an outline of the rest of this paper.

In §2 we discuss the significance of some of our results, in terms of foundations of mathematics.

In §3 we study and characterize the nonempty subsets of which are Medvedev complete. We prove that any two such sets are recursively homeomorphic (Theorem 3.21). This is related to a result of Pour-El/Kripke [22] concerning effectively inseparable theories.

In §4 we relativize and iterate the result of §3 to obtain a nonempty set of codes for countable -models of , with a strong homogeneity property: any two nonempty subsets of are recursively homeomorphic, via a homeomorphism which preserves the -models (Theorem 4.11).

In §5 we combine the results of §§3,4 with Jockusch/Soare forcing, to obtain a countable -model of in which all definable elements are recursive (Theorem 5.11). This result is originally due to Friedman [10, unpublished]. In §6 we improve this result, to obtain a countable -model of satisfying if is definable from then (Theorem 6.9).

In §7 we generalize the results of §§3,4,5,6 to non--models. In this way we obtain a conservation result, showing that plus a strong relative non-definability scheme is conservative over - (Corollary 7.9).

In §8 we prove a recursion-theoretic result of Kucera [19]: There is a disjoint pair of recursively inseparable, recursively enumerable sets, such that any two separating sets which differ infinitely compute the complete recursively enumerable set (Theorem 8.3). In §9 we apply Kucera's result to the study of -models of . It is well known that the intersection of all such models consists of the recursive sets. We now show that the intersection of all such models which are submodels of a given one may contain nonrecursive sets (Theorem 9.1).

In §10 we generalize Kucera's result, and we apply the generalization to the study of non--models of . We refute several plausible conjectures concerning the relationship between and . See Remarks 10.4, 10.8, 10.9.

Throughout this paper, we use recursion-theoretic concepts and notation from Rogers [24] and Soare [33]. We use to denote the set of natural numbers. We identify points with functions . For and , we write to mean that the Turing machine with Gödel number and oracle and input halts in steps with output . For and , we write to mean that . Furthermore, means that is defined, i.e., , and means that is undefined, i.e., . For , means that is Turing reducible to , i.e., . The Turing degree of , written , is the set of all such that , i.e., and . A predicate is said to be recursive if if , and if . A set is said to be if there exists a recursive predicate such that . For sets , we shall consider recursive functionals given by for some and all , .

# Foundational Significance

In this section we explore the foundational significance of some of our results.

Foundations of mathematics is the study of the most basic concepts and logical structure of mathematics, with an eye to the unity of human knowledge. For general background in this area, the reader may turn to the van Heijenoort volume [37], where some of the most important modern papers have been carefully translated and reprinted. See also Gödel's collected works [12] and the Friedman volume [13].

As background for our work here, consider the well known foundational program of computable analysis, i.e., the development of mathematics in the computable world, is recursive. See Aberth [1] and Pour-El/Richards [23]. This program is obviously attractive from the viewpoint of Turing's analysis of computability. However, it is also known that the assumption all real numbers are computable'' conflicts with many basic, well known theorems of real analysis. For example, it is in conflict with the maximum principle for continuous real-valued functions on a closed bounded interval.

Clearly it would be desirable to strike a balance between these conflicting requirements. A fairly successful attempt in this direction is Theorem 5.11, below. In non-technical terms, the theorem asserts the existence of a world where the main theorems of real analysis hold, and the natural numbers are standard, yet each definable real number is computable. In technical terms, one obtains an -model of in which all definable reals are recursive. The identification of the recursive reals with the computable reals is an outcome of Turing's foundational work on computable functions. Thus the computable reals play a large and important role in , forming so to speak the definable core'' of . On the other hand, from recent foundational work in Reverse Mathematics, we know that is just strong enough to prove many basic theorems of real analysis. See Simpson [30, Chapter IV]. Thus contains just enough non-computable reals in order to satisfy the demands of real analysis.

Furthermore, in Theorem 6.9 below, we show that the same -model satisfies a more general scheme:

For all reals and , if is definable from , then is Turing reducible to , i.e., computable using as an oracle.
We also show that plus the above scheme has the same first order part as alone. See Corollary 7.9, below.

The above scheme is foundationally interesting, for the following reason. Often in mathematics one has the situation that, under some assumptions on a real parameter , there exists a unique real having some property which is stated in terms of . In this kind of situation, our scheme allows us to conclude that is Turing reducible to .

# Medvedev Degrees of Subsets of

In this section we exposit the lattice of Medvedev degrees of nonempty subsets of . We prove an important result concerning nonempty subsets of which are Medvedev complete.

For background on Medvedev degrees of subsets of the Baire space, , see Rogers [24, §13.7] and Sorbi [34]. For background on subsets of the Cantor space, , and of the Baire space, see the survey by Cenzer/Remmel [3].

Definition 3.1   Let and be nonempty subsets of . We say that is Medvedev reducible to , written , if there exists a recursive functional . We say that is Medvedev complete if for all nonempty subsets of . We say that and are Medvedev equivalent, written , if and . The Medvedev degree of , written , is the set of all such that . The Medvedev degrees are partially ordered by writing if and only if . We write if and only if , i.e., and .

Theorem 3.2   The Medvedev degrees of nonempty subsets of form a distributive lattice with a bottom and a top element. The top element of consists of the nonempty subsets of which are Medvedev complete.

Proof.In this proof and throughout this paper, we use the following notation. For we have where and . We use to denote the set of strings, i.e., finite sequences of 's and 's. The length of is denoted . For and , we have and . For and , we have given by

We fix a primitive recursive, one-to-one, onto function . For and , we have where .

To prove our theorem, let and be nonempty subsets of . The supremum or least upper bound of and is where and . The infimum or greatest lower bound of and is where

The distributive laws and are easily verified. The bottom element of our lattice is , or equivalently where is any subset of with a recursive element. The top element of is where is any nonempty subset of which is Medvedev complete. See Lemma 3.3 and Remark 3.4 below.

Lemma 3.3   There exists a nonempty subset of which is Medvedev complete.

Proof.Let be a standard, recursive enumeration of the subsets of . (See Remark 3.9 below.) In particular, the predicate is . By the Normal Form Theorem for predicates, we have where is primitive recursive. As in Simpson [30, Lemmas VIII.2.5 and VIII.2.9], put

of length if then
Note that is again . Now for all such that is nonempty, we have . On the other hand, for all , is nonempty, by compactness of . Put
Obviously is a nonempty subset of . For all such that is nonempty, we have via the recursive functional . Thus is Medvedev complete.

Remark 3.4   Another construction of a Medvedev complete set is as follows. Let be the set of complete extensions of Peano arithmetic. It can be shown that is Medvedev complete; see Scott/Tennenbaum [26] and Jockusch/Soare [16]. Instead of Peano arithmetic, we may use any effectively inseparable theory; see Pour-El/Kripke [22]. Or, we may use any effectively essentially incomplete theory; see Remark 3.18 below. Yet another construction of a Medvedev complete set may be obtained from Lemmas 3.14 and 3.16 below.

We are going to show that any two Medvedev complete subsets of are recursively homeomorphic (Theorem 3.21). In order to prove this, we shall first consider the nature of Medvedev reducibility in more detail.

Lemma 3.5   Let . If the predicate is , then the predicate is also .

Proof.By the Normal Form Theorem for predicates, we have

where is primitive recursive. Thus holds if and only if . By compactness of , this is equivalent to of length , which is explicitly .

Lemma 3.6   Let be a subset of , and let be a recursive functional.
1.
The image is a subset of .
2.
For any subset of , the inverse image is a subset of .

Proof.To prove part 1, note that for all we have if and only if and . By Lemma 3.5, this is . For part 2 we have and and this is obviously .

Definition 3.7   We use to denote the free Boolean algebra on a countable set of generators . There is a well known isomorphism of onto the Boolean algebra of clopen subsets of , given by , , , , , . For we write .

Remark 3.8   The mapping is essentially just the usual semantics for propositional calculus. The Compactness Theorem for propositional calculus says: For all , if and only if for some finite . This is a consequence of the fact that is compact as a topological space.

Remark 3.9   If is recursively enumerable, then is . Conversely, if is , then where . Note that is recursively enumerable. A standard, recursive enumeration of the subsets of may be obtained by setting , where is a standard, recursive enumeration of the recursively enumerable subsets of .

Remark 3.10   The mapping gives a one-to-one correspondence between nonempty subsets of and Stone spaces of Boolean algebras of the form where is a recursively enumerable ideal. These are the so-called recursively enumerable Boolean algebras'' of Cenzer/Remmel [3, §5]. Recursively presented homomorphisms on the Boolean algebras correspond to recursive functionals on the Stone spaces.

Lemma 3.11   Let be a subset of , and let be a recursive functional. Then there is a recursive function such that for all .

Proof.The predicate and is , so by the Normal Form Theorem, let be a primitive recursive predicate such that

and
Trivially we have
or or
or in other words,
not or not or not
By compactness of , it follows that of length not or not or not . For let be the least such , and form such that
Clearly and are recursive, and .

Remark 3.12   In Lemma 3.11, we may replace by the unique recursive homomorphism given by for all . For and , we have if and only if . Thus is a truth-table reducibility operator. This is closely related to results of Nerode as presented in Rogers [24, pages 143 and 154].

We now introduce a property of nonempty subsets of , called productiveness, which will turn out to be equivalent to Medvedev completeness (Lemma 3.20).

Definition 3.13   Let be a nonempty subset of . A splitting function for is a recursive function such that for all , if and is nonempty, then and are nonempty. is said to be productive if there exists a splitting function for .

Lemma 3.14   There exists a nonempty set such that is productive.

Proof.Put . Clearly is nonempty and . By Lemma 3.5, the predicate

if then
is . By the Uniformization Principle and the S-m-n Theorem, let be a primitive recursive function such that, for all and , some such that holds, if such a exists. Define by . We claim that is a splitting function for . To see this, suppose and . If , then if then , hence , a contradiction. If , then if then , hence , a contradiction.

Lemma 3.15   Let and be nonempty subsets of . Given such that and , and given a splitting function for , we can effectively find with the following properties: , and if and then
1.
if and only if ,
2.
if and only if .

Proof.Because is productive, is nowhere dense in , so given we can effectively find such that and and and and and . Thus . Now let be a splitting function for . By the Recursion Theorem, we can effectively find such that

Put . Clearly . Now assume and . If , then we have , hence , hence (because is a splitting function for ), hence . Similarly, if , then . On the other hand, if and , then we have , hence and . This completes the proof.

Lemma 3.16   Let and be nonempty subsets of .
1.
If is productive, then there exists a recursive functional from onto .
2.
If and are productive, then and are recursively homeomorphic, i.e., there exists a recursive functional from one-to-one onto .

Proof.Let and be as in the hypothesis of our lemma. If is a subalgebra of and if is a monomorphism, let us call good if, for all , if and only if .

For part 1, to find a recursive functional from onto , it suffices to find a good recursive monomorphism . Assume inductively that we have already found a good finite monomorphism , where is a finite subalgebra of . (We start with .) Let be the th element of with respect to some fixed recursive enumeration of . Let be the finite subalgebra of generated by . We effectively extend to a good finite monomorphism , as follows. For each atom of , if or put , otherwise use Lemma 3.15 and a splitting function for to effectively find such that , and if and only if , and if and only if . Finally we obtain a good recursive monomorphism , and part 1 is proved.

For part 2 we proceed as above, except that we use a back-and-forth argument involving splitting functions for both and . The inductive hypothesis is that we have a good finite isomorphism , where and are finite subalgebras of . Let be the th element of with respect to some fixed recursive enumeration of . Let be the finite subalgebra of generated by . Use Lemma 3.15 and a splitting function for to effectively extend to a good finite isomorphism . Then let be the finite subalgebra of generated by . Use Lemma 3.15 and a splitting function for to effectively extend to a good finite isomorphism . Finally we obtain a good recursive automorphism , and part 2 is proved.

Remark 3.17   The ideas used in the proofs of Lemmas 3.15 and 3.16 can be traced to Myhill [20], Smullyan [32], and Pour-El/Kripke [22].

Remark 3.18   Pour-El and Kripke [22] have obtained some interesting results concerning deduction-preserving isomorphisms of theories. In the Pour-El/Kripke terminology, some of our results in this section can be reformulated as follows. Let denote consistent, recursively axiomatized theories in the predicate calculus, or in the propositional calculus. Note that the Lindenbaum sentence algebras of such theories correspond precisely to nonempty subsets of , via Stone duality. Let us say that is effectively essentially incomplete if, given extending , we can effectively find a sentence in the language of such that both and are consistent. Note that is effectively essentially incomplete if and only if the nonempty subset of corresponding to is productive, in the sense of Definition 3.13. Thus by Lemma 3.16 we have: (1) If is effectively essentially incomplete, then for all there exists a deduction-preserving recursive monomorphism of into . (2) If and are effectively essentially incomplete, then there exists a deduction-preserving recursive isomorphism of onto . Pour-El/Kripke [22] obtain similar results under the stronger hypothesis that is effectively inseparable. Our results (1) and (2) are best possible, in the sense that effective essential incompleteness is a necessary as well as sufficient condition for them to hold.

Lemma 3.19   Let and be nonempty subsets of . If and is productive, then is productive.

Proof.Since , there is a recursive functional . By Lemma 3.11, let be recursive such that for all . Let be a splitting function for . The predicate is (see the proof of part 1 of Lemma 3.6), so by the S-m-n Theorem, let be primitive recursive such that for all . Now if and , we have and , hence and , hence and . Thus is a splitting function for .

Lemma 3.20   Let be a nonempty subset of . is productive if and only if is Medvedev complete.

Proof.By Lemma 3.19, Medvedev completeness implies productiveness. By part 1 of Lemma 3.16, productiveness implies Medvedev completeness.

Theorem 3.21   Let and be nonempty subsets of .
1.
If is Medvedev complete, then there exists a recursive functional from onto .
2.
If and are Medvedev complete, then and are recursively homeomorphic, i.e., there exists a recursive functional from one-to-one onto .

Proof.This is immediate from Lemmas 3.16 and 3.20.

Remark 3.22   Let be the lattice of Medvedev degrees of nonempty subsets of , as in Theorem 3.2. There are many obvious structural questions to ask about . One may ask about embeddability, initial segments, final segments, definability, automorphisms, etc. There is reason to believe that a study of structural aspects of the distributive lattice could be more rewarding than the ongoing study of the structural aspects of , the upper semilattice of Turing degrees of recursively enumerable subsets of , as pursued for instance in Soare [33]. For one thing, there is a well known lack of natural examples of elements of , but there are some interesting natural examples of elements of . In particular, putting
, Jockusch [15] has shown that
, , and of course is Medvedev complete (see the proof of Lemma 3.14). See also Simpson [28,29] and other FOM postings in the same thread.

# Relativization, Iteration, -Models

In this section we relativize and iterate the results of §3. Our construction is inspired by the idea of iterated forcing in set theory, as exposited in Jech [14, page 458] and Kunen [18, page 273]. We show that our construction gives rise to a set of countable -models of with a strong homogeneity property (Theorem 4.11).

Definition 4.1   All of the concepts and results of §3 can be uniformly relativized (Rogers [24, pages 128-137]) to an arbitrary . Say that is if for some recursive predicate . We employ a uniform, standard, recursive enumeration of the subsets of . A nonempty set is said to be -productive if there exists an -recursive splitting function, i.e., an -recursive function such that for all , if then .

Recall that for and we have where . (See the proofs of Theorem 3.2 and Lemma 3.3.) For put .

Lemma 4.2   There is a predicate such that
if then
where .

Proof.This comes from a uniform relativization of the proof of Lemma 3.3. The predicate is , so by the Normal Form Theorem for predicates, let be primitive recursive such that . Put , where

of length if then .
It is straightforward to verify that has the desired property. The details are as in the proof of Lemma 3.3.

Lemma 4.3   With notation as in Lemma 4.2, for all , is -productive with a fixed primitive recursive splitting function .

Proof.This comes from a uniform relativization of Lemmas 3.14 and 3.19. Let be such that, for all , . The argument for Lemma 3.14 gives a primitive recursive function such that, for all , is -productive with splitting function . Note also that for all . Let be primitive recursive such that, for all and , if and only if . Let be primitive recursive such that, for all and all , . As in the proof of Lemma 3.19 we have that, for all , is -productive with splitting function .

Definition 4.4   Recall that . We also put

(Compare the dependent choice notation of Simpson [30, Definition VII.6.1 and Lemmas VIII.2.5 and VIII.2.9].) From now on, fix as in Lemma 4.2, and put . Clearly is a nonempty subset of .

Lemma 4.5   For all we have
and this is an -model of .

Proof.If then clearly for an appropriate , hence . This gives . The converse inclusion follows from . To see that this is an -model of , use Lemma 4.2 plus the following characterization: is an -model of if and only if (i) , (ii) for all , and (iii) for all and , if then .

Definition 4.6   Let and be nonempty subsets of . Let be a recursive functional from onto . A splitting functional for is a recursive functional such that for all , the -recursive function is a splitting function for the set . We say that is productive if there exists a splitting functional for .

Lemma 4.7   Let be nonempty subsets of . Suppose that is a recursive functional from onto , . If and are recursively homeomorphic and and are productive, then and are recursively homeomorphic. Indeed, given a recursive homeomorphism and splitting functionals for and , we can effectively find a recursive homeomorphism such that .

Proof.This is a uniform relativization of part 2 of Lemma 3.16.

Definition 4.8   For any and any nonempty set , put and . Note that and are again nonempty subsets of . In particular is a trivial set, namely where is defined by for all .

Lemma 4.9   Let and be nonempty subsets of . Then there are a recursive homeomorphism and a recursive sequence of recursive homeomorphisms , , such that for all .

Proof.By Lemma 4.3, the recursive functionals from onto given by are uniformly productive. Hence their restrictions, from onto and from onto , are uniformly productive. Begin with the trivial recursive homeomorphism . Repeatedly apply Lemma 4.7 to obtain a recursive sequence of recursive homeomorphisms , , ..., , ..., such that for all . Finally is given by .

Lemma 4.10   Let and be nonempty subsets of . Then there exists a recursive homeomorphism such that for all and , if then .

Proof.Let be as in Lemma 4.9. Let and be such that . By Lemma 4.9 we have , hence for all , hence . By Lemma 4.5 it follows that .

Theorem 4.11   There is a nonempty subset of , , with the following properties:
1.
For all , is an -model of .
2.
Any two nonempty subsets of are recursively homeomorphic.
3.
For all nonempty sets , there is a recursive homeomorphism such that for all and , if then .

Proof.This follows from Lemmas 4.5 and 4.10 if we let , where for all . (Note: is not the Turing jump of .)

# Jockusch/Soare Genericity

In this section we combine the previous theorem with so-called Jockusch/Soare forcing, to obtain an -model of in which all definable elements are recursive (Theorem 5.11).

Definition 5.1   A relation is said to be arithmetical if it is first order definable over the standard model of arithmetic . We write is recursive, and is arithmetical.

Definition 5.2   Let be the set of all nonempty subsets of . is said to be arithmetical if is arithmetical. is said to be dense if for all there exists such that . is said to meet if there exists such that . is said to be Jockusch/Soare generic (cf. Jockusch/Soare [16, proof of Theorem 2.4]), or simply, generic, if meets every dense arithmetical .

Lemma 5.3   Given , there exists such that is generic.

Proof.Let , be an enumeration of the dense arithmetical subsets of . Construct a sequence in as follows. Begin with . Given , let be such that . Finally let be the unique element of . Clearly and meets each , hence is generic.

Lemma 5.4   Let , be a sequence of nonrecursive elements of . Given , there exists such that is generic and .

Proof.For all we have if and only if . For , put . We claim that is dense in . To see this, let be given. If , then by Lemma 3.5 is recursive, contrary to assumption. So we have . Fix such an and put . Clearly and and . This proves our claim. Now let , be an enumeration of the dense arithmetical subsets of . As in the proof of Lemma 5.3, given there exists such that meets for all , and meets for all . This proves our lemma.

Lemma 5.5   Let . Suppose and is generic. Then is generic, and is truth-table reducible to .

Proof.We are assuming , so let be such that . Put either is undefined or is defined. We claim that is dense in . To see this, given , we have is undefined, so fix such an and put is undefined. Then clearly and . This proves our claim. Since is dense arithmetical, let be such that . It follows that is defined, so we have a recursive functional given by , and . Hence by Lemma 3.11 and Remark 3.12, is truth-table reducible to . To show that is generic, let be dense arithmetical. Put or . By Lemma 3.6, is dense arithmetical. Let be such that . Then , so . This completes the proof.

Definition 5.6   Let be the language of first order arithmetic with an extra function symbol denoting an element of , i.e., a function . Let be an -sentence. Let . We say that forces if holds for all generic such that .

Lemma 5.7
1. Let be an -sentence. If is generic, then holds if and only if there exists such that and forces .
2. Let be an -formula with free variables . Then
and forces
is arithmetical.

Proof.Parts 1 and 2 are proved together by a straightforward induction on the complexity of . If is atomic, then for all we have that forces if and only if holds for all , because and are elements of . For arbitrary and of , we have that forces if and only if if then and either forces or forces . For arbitrary of , we have that forces if and only if if then and forces . For arbitrary of , we have that forces if and only if if then does not force .

Lemma 5.8   Let be the language of second order arithmetic. Given an -sentence , we can find an -sentence such that for all , holds if and only if the -model satisfies .

Proof.The proof is straightforward. Set quantifiers in are translated as number quantifiers in .

Lemma 5.9   With as in Theorem 4.11, let be generic. Then the -models and satisfy the same -sentences.

Proof.Suppose and satisfy and respectively. Then and hold. By part 1 of Lemma 5.7, there exist such that and and forces and forces . Since , we may safely assume that . Let be a recursive homeomorphism as in part 3 of Theorem 4.11. By Lemma 5.5 we have that is generic. Since forces , it follows that holds, i.e., . But, by part 3 of Theorem 4.11, we have that . This contradiction proves our lemma.

Lemma 5.10   Consider an -model where and is generic.
1. For -sentences , we have that if and only if forces .
2. For relations , we have that is definable over without parameters if and only if is arithmetical.
3. For , we have that is definable over (without parameters) if and only if is recursive.

Proof.Parts 1 and 2 are immediate from Lemmas 5.7 and 5.9. For part 3, suppose that and is definable without parameters over . Let be an -formula with one free set variable, , such that is the unique such that . Letting be the -sentence unique , we have that . By part 1 we have that forces . By Lemma 5.4, let be generic such that if then . Consider the -model . Then . Since and is generic and forces , we have that holds, i.e., . Let be the unique such that . We claim that . This is clear from Lemma 5.9, because for all and , we have if and only if and , if and only if and , if and only if . Since , it follows that .

Theorem 5.11   There is a countable -model of such that every definable element of is recursive.

Proof.This follows immediately from Theorem 4.11 and Lemma 5.3 and part 3 of Lemma 5.10.

Remark 5.12   Theorem 5.11 is due to Friedman [10, unpublished, Theorem 1.10], announced in [11, Theorem 1.6]. Our proof here is different from Friedman's proof in [10].

# Relative Genericity and Definability

In this section we prove a key lemma concerning relativized Jockusch/
[0]Soare genericity (Lemma 6.2). We then use our lemma to obtain an improvement of Theorem 5.11, involving relative definability and relative recursiveness, i.e., Turing reducibility (Theorem 6.9).

Definition 6.1   All of the concepts and results of §5 can be straightforwardly relativized to an arbitrary . We use to denote the set of nonempty subsets of . (See Definition 4.1.) is said to be arithmetical in if is arithmetical in , i.e., definable over by a formula of . is said to be Jockusch/Soare generic over , or simply, generic over , if meets every dense subset of which is arithmetical in .

Lemma 6.2   Let . Suppose and is generic. Then is generic over .

Proof.Let be given such that is dense in and arithmetical in . We need to show that meets . By Lemma 5.5, there are a set and a recursive functional such that . It suffices to show that forces if is dense in then meets . Equivalently, we shall show if and forces is dense in , then and forces meets . To see this, let be given such that and forces is dense in . Put . Using as our forcing language, we have that forces is dense in . In particular, since forces , it follows that forces and . Let and be such that and forces and . Put and . Then , , and forces and , i.e., forces meets . This proves our lemma.

Lemma 6.3   Let be given. Suppose , and suppose is an -recursive homeomorphism of onto . If is generic over , then is generic over .

Proof.This follows from a straightforward relativization to of Lemma 5.5.

Definition 6.4   Let be as in Lemma 4.2. Relativizing Definition 4.4, put
for all . Clearly .

Lemma 6.5   Let be given. For all we have
and this is an -model of containing .

Proof.A straightforward relativization to of Lemma 4.5 shows that, for all , and this is an -model of . Clearly is , hence for an appropriate , hence .

Lemma 6.6   Consider an -model where and is generic. For all , if is definable over , then is recursive.

Proof.The proof of Theorem 4.11 shows that via a recursive homeomorphism such that, for all , . In particular, where . Furthermore, by Lemma 5.5, is generic. Part 3 of Lemma 5.10 now gives the desired conclusion.

Lemma 6.7   Let be given. Consider an -model where and is generic over . For all , if is definable over from , then .

Proof.This is a straightforward relativization to of Lemma 6.6.

Lemma 6.8   Let and be given. Put
.
If is nonempty, then there exists an -recursive homeomorphism such that for all , putting , we have .

Proof.As in the proof of Lemma 4.9, construct a recursive sequence of -recursive homeomorphisms , , such that for all . Define . Then is an -recursive homeomorphism. Furthermore, for and , we have for all . Hence . By Lemmas 4.5 and 6.5, it follows that .

Theorem 6.9   There is a countable -model of satisfying if is definable from then .

Proof.Let be generic, and put . By Lemma 4.5, is an -model of . Fix . Fix such that . As in Lemma 6.8, put , and let be an -recursive homeomorphism of onto . We have . Put . By Lemma 6.8, . By Lemma 6.2, is generic over . Hence, by Lemma 6.3, is generic over . It follows by Lemma 6.7 that, for all , if is definable over from , then . This completes the proof.

Remark 6.10   Our Theorem 6.9 above contradicts Friedman's Theorem 1.12 of [10, unpublished].

# Generalization to Non--Models

In this section we generalize the results of §§3,4,5,6 to countable non--models of .

As in [30, Remark I.7.6], let - be first order Peano arithmetic with the induction scheme restricted to formulas. The following theorem is well known.

Theorem 7.1   Let be a countable model of -. Then there exists a countable such that .

Proof.This result is originally due to Harrington (1977, unpublished). The proof is in Simpson [30, §IX.2].

Thus any countable model of - is the first order part of a countable model of . It follows by the Gödel Completeness Theorem that - is the first order part of . (See Simpson [30, §IX.2].) We shall strengthen these results below (Theorems 7.6 and 7.8, Corollary 7.9).

Let be a countable model of -. It is well known that the familiar concepts and results of classical recursion theory can be generalized to -recursion theory. See for instance Mytilinaios [21]. Let - be the set of all such that is definable over , i.e., both and definable over allowing parameters from . We describe sets - as being -recursive. It is known from Simpson [30, § IX.1] that - is the smallest such that . Thus - in -recursion theory plays the role of in classical recursion theory.

A set is said to be -finite if it is -recursive and bounded in , or equivalently, if there exists an -canonical index of . By an -canonical index of , we mean an such that , where is the usual formula asserting that occurs in the binary expansion of , i.e., . Compare Rogers [24, §5.6]. The -finite sets play the role of finite sets in classical recursion theory. A set is said to be -regular if is -finite for each -finite . By Bounded Comprehension [30, Theorem II.3.9], every -recursively enumerable set is -regular. In this paper we shall have no use for sets which are not -regular. If is such that , then every is necessarily -regular.

We denote by the set of all -regular functions . We denote by the set of -strings, i.e., (-canonical indices of) -finite sequences of 's and 's. Clearly and the length function are -recursive. For and , we have an -string of length . We denote by the set of nonempty sets of the form where is -recursive. The sets in -recursion theory play the role of nonempty subsets of in classical recursion theory.

We say that is complete if for every there exists an -recursive functional . Generalizing Theorem 3.21, we have:

Theorem 7.2   Let be a countable model of -, and let . If is complete, there exists an -recursive functional from onto . If and are complete, there exists an -recursive functional .

Proof.This is a straightforward generalization of the arguments of §3.

Generalizing Theorem 4.11, we have:

Theorem 7.3   Let be a countable model of -. We can find with the following properties:
1.
For all , if then .
2.
For all such that , there exists an -recursive functional such that for all and , if then .

Proof.This is a straightforward generalization of the arguments of §4.

For the notion of Jockusch/Soare genericity over is defined in the obvious way, in terms of dense subsets of which are definable over allowing parameters from . This notion is equivalent to genericity over - in the sense of Simpson [30, § IX.2]. Generalizing Lemma 5.3, we have:

Lemma 7.4   Let be a countable model of -. For any there exists such that is Jockusch/Soare generic over . For any such we have - .

Proof.See Simpson [30, §IX.2].

Generalizing Lemma 5.4, we have:

Lemma 7.5   Let be a countable model of -, and suppose
- .
Then for any there exists such that
- ,
and is Jockusch/Soare generic over .

Proof.Combine the proof of Lemma 7.4 with a straightforward generalization of the proof of Lemma 5.4.

Generalizing Theorem 5.11, we have:

Theorem 7.6   Let be a countable model of -. Then there exists a countable such that and furthermore, every element of which is definable over allowing parameters from is -recursive.

Proof.This is a straightforward generalization of the arguments of §5.

Remark 7.7   Theorems 7.2, 7.3 and 7.6 and Lemma 7.5 are originally due to Simpson/Tanaka/Yamazaki [31].

Generalizing Theorem 6.9, we have:

Theorem 7.8   Let be a countable model of -. Then there exists a countable such that and furthermore, for all , if is definable over allowing parameters from , then - .

Proof.This is a straightforward generalization of the arguments of §6.

Corollary 7.9   - is the first order part of the -theory consisting of plus the following scheme:
if exactly one then and ,
where is any -formula with no free set variables other than .

Proof.This follows from Theorem 7.8 plus Gödel's Completeness Theorem.

# A Result of Kucera

In this section we present a simplified proof of a recursion-theoretic result of Kucera [19]. Our proof is based on two easy, well-known lemmas. We present the proof in detail now, because later we shall need to generalize it to the context of -recursion theory where is a model of -.

Lemma 8.1   There exists a recursively enumerable set such that the complement is infinite and, for all , if then , where

Proof.We use a movable marker argument, as in Rogers [24, pages 235-236]. We shall have where is the position of marker at stage . Thus

Stage . Begin by defining for all . In other words, .

Stage . Let be the least such that and . If is undefined, let . Thus for all . If is defined, let . Thus

and in particular .

Finally put . Clearly is a recursively enumerable set. Note that takes on each possible value at most once. Hence as , and it is clear that the construction works.

The following lemma is a strengthening due to K. Ohashi of the well-known Splitting Theorem of R. Friedberg. See Rogers [24, Exercise 12.21].

Lemma 8.2   Let be a nonrecursive, recursively enumerable set. Then there exists a pair of disjoint, recursively inseparable, recursively enumerable sets such that .

Proof.Let be a one-to-one recursive function such that is the range of . Put . Let () be a standard, recursive enumeration of the recursively enumerable sets. Let be the finite set of elements enumerated into prior to stage .

To construct we use a no-injury priority argument. For each and there is a requirement to the effect that if possible''. The ordering of the requirements is .

Stage . Put .

Stage . Let be the least such that and either or . If does not exist, or if , put into , i.e., and . Otherwise put into , i.e., and .

Finally put and . Clearly and are recursively enumerable sets, and . It is also clear that takes on each possible value at most twice, hence as .

We claim that and are recursively inseparable. Assume for a contradiction that is a recursive set which separates and , i.e., and . Let and be such that and . Then and . For all sufficiently large we have , hence . Thus there is a finite set such that for all there exists such that . On the other hand, we also have that for all there exists such that . It follows that is recursive, a contradiction.

The following theorem and its corollaries are due to Kucera [19].

Theorem 8.3   There exists a disjoint, recursively inseparable pair of recursively enumerable sets with the following property. If and are separating sets, then for the symmetric difference we have that either is finite or . Here , the complete recursively enumerable set.

Proof.Let be a recursively enumerable set as in Lemma 8.1. Then clearly for any infinite set . By Lemma 8.2 let be a disjoint, recursively inseparable pair of recursively enumerable sets such that . Now let and be separating sets. Then and . Hence and we have our result.

The previous theorem is of interest with respect to subsets of . An extensive survey of this part of recursion theory is Cenzer/Remmel [3]. It is known that a nonempty subset of with no recursive elements necessarily has elements of distinct Turing degrees, among which are infinitely many pairwise incomparable Turing degrees . We now get:

Corollary 8.4   There exists a nonempty set with no recursive elements, such that if and are Turing degrees of elements of , then either or .

Proof.Let be as in Theorem 8.3. Let be the set of (characteristic functions of) separating sets for . If and are the Turing degrees of respectively, it follows from the conclusion of Theorem 8.3 that either or .

If is a Turing degree, we write to mean that every nonempty subset of contains at least one element of Turing degree . This is equivalent to being the degree of a complete extension of Peano arithmetic. See also Jockusch/Soare [16] and Simpson [27, §6]. It is known that there exist and such that . We now get:

Corollary 8.5   If and and , then .

# An Application to -Models

In this section we apply Kucera's result to the study of -models of . For background on this subject, see Simpson [30, §VIII.2].

It is known that minimal -models of do not exist, i.e., every -model of has a proper -submodel of . It is also known that the intersection of all -models of is , the set of recursive sets. We now have:

Theorem 9.1   There exists a countable -model of such that
is an -model of
Here is the set of recursive sets.

Proof.Let be as in Theorem 8.3. Since proves separation [30, Lemma IV.4.4], every -model of contains a separating set for . Let be an -model of such that , where is the complete recursively enumerable set. Let be a separating set for . Obviously is not recursive. We claim that . Given such that , let be a separating set for . Since but , the conclusion of Theorem 8.3 implies that the symmetric difference is finite. Since , it follows that . This gives our result.

Remark 9.2   For any -model of , it can be shown that is an -model of if and only if .

The above theorem concerning -models of is in contrast to the following theorem of Simpson [30, Corollary VIII.6.10] concerning -models of . This is one instance where the well-known analogy [30, pages 40 and 314] between -models of and -models of breaks down.

Theorem 9.3   If is a -model of , then
is a -model of
Here is the set of hyperarithmetical sets.

Actually Simpson [30, Corollary VIII.6.10] obtains not only Theorem 9.3 for -models of , but also an appropriate generalization for arbitrary models of .

# Applications to Non--Models

In this section we generalize Kucera's result and apply the generalization to the study of non--models of . For background on non--models of , see Simpson [30, § VIII.2].

Lemma 10.1   There exists a formula with the following properties. Let be the formula . Then
1.
proves .
2.
proves is not recursive.
3.
proves is finite or .
Here is the complete recursively enumerable set.

Proof.This follows from a straightforward formalization of our proof of Theorem 8.3 via Lemmas 8.1 and 8.2 above, with . The key point for the success of the priority argument for Lemma 8.2 is that as . This is provable in because of Bounded Comprehension [30, Theorem II.3.9].

Remark 10.2   For applications of Bounded Comprehension in formalization of more sophisticated priority arguments, see Mytilinaios [21].

Theorem 10.3   Let be a model of  does not exist''. Then with the formula of Lemma 10.1, we have that satisfies
1.
2.
is not recursive
3.
is finite.
Furthermore, - .

Proof.That satisfies 1, 2, 3 is immediate from Lemma 10.1. Let be such that . Then - , but for every such that we have . See also Theorem 9.1 and its proof.

Remark 10.4   Friedman [11, Theorem 1.7] states the following result: If is an arithmetical formula and proves is not recursive, then proves is not recursive . But this is refuted by our Theorem 10.3, taking to be the formula .

As in §7, let - be first order Peano arithmetic with the induction scheme restricted to formulas. For we define - similarly, with the induction scheme restricted to formulas.

Corollary 10.5   Any countable model of - is the first order part of a countable model of with the properties mentioned in Theorem 10.3.

Proof.Let be a countable model of -. By [30, Exercise IX.2.8], there exists a countable such that is a model of  does not exist''. Our result now follows from Theorem 10.3.

Corollary 10.6   Let be a model of - which is not a model of -. Then any model of having as its first order part has the properties mentioned in Theorem 10.3.

Proof.Any model of having as its first order part is of the form where . We claim that necessarily satisfies  does not exist''. Otherwise, let be such that  is the complete recursively enumerable set''. Clearly any formula without set parameters is equivalent over to a formula with parameter . Since includes induction for all formulas with set parameters, satisfies induction for all formulas with parameter . Hence satisfies induction for all formulas without set parameters. In other words, -, a contradiction. This proves the claim. Our result now follows from Theorem 10.3.

Theorem 10.7   There is a formula with no free variables other than , such that
1.
proves .
2.
proves is finite.
3.
does not prove recursive .
4.
does not prove .

Proof.Let be the formula of Lemma 10.1. Let be a sentence which is provable in - but not in -. (For instance, we may take to be the sentence expressing consistency of -.) We may assume that is . Let be the formula

if then , and
if least element of then and .
Reasoning in , suppose is such that holds. If then we have , hence . Now suppose . Then where holds and is the least such that . Since fails, - fails. Hence by Corollary 10.6 we have is finite. This implies is finite. The rest follows easily from Theorem 10.3.

Remark 10.8   For formulas with no free set variables other than , it is known that proves
exactly one recursive . (This follows from [30, Lemma VIII.2.4.2] using comprehension.) One might conjecture that this result would continue to hold with  exactly one '' weakened to  countably many ''. However, such a conjecture is refuted by Theorem 10.7, taking to be .

Remark 10.9   Tanaka [35] conjectured that is conservative over for sentences of the form countably many , where is arithmetical with no free set variables other than . This conjecture is refuted by Theorem 10.7, taking to be the formula .

## Bibliography

1
Oliver Aberth.
Computable Analysis.
McGraw-Hill, 1980.
XI + 187 pages.

2
J. Barwise, editor.
Handbook of Mathematical Logic.
Studies in Logic and the Foundations of Mathematics. North-Holland, 1977.
XI + 1165 pages.

3
Douglas Cenzer and Jeffrey B. Remmel.
classes in mathematics.
In [7], pages 623-821, 1998.

4
S. B. Cooper, T. A. Slaman, and S. S. Wainer, editors.
Computability, Enumerability, Unsolvability: Directions in Recursion Theory.
Number 224 in London Mathematical Society Lecture Notes. Cambridge University Press, 1996.
VII + 347 pages.

5
J. C. E. Dekker, editor.
Recursive Function Theory.
Proceedings of Symposia in Pure Mathematics. American Mathematical Society, 1962.
VII + 247 pages.

6
F. R. Drake and J. K. Truss, editors.
Logic Colloquium '86.
Studies in Logic and the Foundations of Mathematics. North-Holland, 1988.
X + 342 pages.

7
Y. L. Ershov, S. S. Goncharov, A. Nerode, and J. B. Remmel, editors.
Handbook of Recursive Mathematics.
Studies in Logic and the Foundations of Mathematics. North-Holland, 1998.
Volumes 1 and 2, XLVI + 1372 pages.

8
J.-E. Fenstad, I. T. Frolov, and R. Hilpinen, editors.
Logic, Methodology and Philosophy of Science VIII.
Studies in Logic and the Foundations of Mathematics. North-Holland, 1989.
XVII + 702 pages.

9
FOM e-mail list.
http://www.cs.nyu.edu/mailman/listinfo/fom/, September 1997 to the present.

10
Harvey Friedman.
Subsystems of second order arithmetic and their use in the formalization of mathematics.
19 pages, unpublished, March 1974.

11
Harvey Friedman.
Some systems of second order arithmetic and their use.
In Proceedings of the International Congress of Mathematicians, Vancouver 1974, volume 1, pages 235-242. Canadian Mathematical Congress, 1975.

12
Kurt Gödel.
Collected Works.
Oxford University Press, 1986-1995.
Volume I, XVIII + 474 pages, 1986, Volume II, XVI + 407 pages, 1990, Volume III, XX + 532 pages, 1995.

13
L. A. Harrington, M. Morley, A. Scedrov, and S. G. Simpson, editors.
Harvey Friedman's Research on the Foundations of Mathematics.
Studies in Logic and the Foundations of Mathematics. North-Holland, 1985.
XVI + 408 pages.

14
Thomas Jech.
Set Theory.
XI + 621 pages.

15
Carl G. Jockusch, Jr.
Degrees of functions with no fixed points.
In [8], pages 191-201, 1989.

16
Carl G. Jockusch, Jr. and Robert I. Soare.
classes and degrees of theories.
Transactions of the American Mathematical Society, 173:35-56, 1972.

17
Richard Kaye.
Models of Peano Arithmetic.
Oxford University Press, 1991.
X + 292 pages.

18
Kenneth Kunen.
Set Theory, an Introduction to Independence Proofs.
Studies in Logic and the Foundations of Mathematics. North-Holland, 1980.
XVI + 313 pages.

19
Antonín Kucera.
On the role of in recursion theory.
In [6], pages 133-141, 1988.

20
John Myhill.
Creative sets.
Zeitschrift für mathematische Logik und Grundlagen der Mathematik, 1:97-108, 1955.

21
Michael E. Mytilinaios.
Finite injury and induction.
Journal of Symbolic Logic, 54:38-49, 1989.

22
Marian B. Pour-El and Saul Kripke.
Deduction-preserving recursive isomorphisms'' between theories.
Fundamenta Mathematicae, 61:141-163, 1967.

23
Marian B. Pour-El and J. Ian Richards.
Computability in Analysis and Physics.
Perspectives in Mathematical Logic. Springer-Verlag, 1988.
XI + 206 pages.

24
Hartley Rogers, Jr.
Theory of Recursive Functions and Effective Computability.
McGraw-Hill, 1967.
XIX + 482 pages.

25
Dana S. Scott.
Algebras of sets binumerable in complete extensions of arithmetic.
In [5], pages 117-121, 1962.

26
Dana S. Scott and Stanley Tennenbaum.
On the degrees of complete extensions of arithmetic (abstract).
Notices of the American Mathematical Society, 7:242-243, 1960.

27
Stephen G. Simpson.
Degrees of unsolvability: a survey of results.
In [2], pages 631-652, 1977.

28
Stephen G. Simpson.
FOM: natural r.e. degrees; Pi01 classes.
FOM e-mail list [9], August 13, 1999.

29
Stephen G. Simpson.
FOM: priority arguments; Kleene-r.e. degrees; Pi01 classes.
FOM e-mail list [9], August 16, 1999.

30
Stephen G. Simpson.
Subsystems of Second Order Arithmetic.
Perspectives in Mathematical Logic. Springer-Verlag, 1999.
XIV + 445 pages.

31
Stephen G. Simpson, Kazuyuki Tanaka, and Takeshi Yamazaki.
Some conservation results on weak König's lemma.
Annals of Pure and Applied Logic, 118:87-114, 2002.

32
Raymond M. Smullyan.
Theory of Formal Systems.
Annals of Mathematics Studies. Princeton University Press, 1961.
XIII + 142 pages.

33
Robert I. Soare.
Recursively Enumerable Sets and Degrees.
Perspectives in Mathematical Logic. Springer-Verlag, 1987.
XVIII + 437 pages.

34
Andrea Sorbi.
The Medvedev lattice of degrees of difficulty.
In [4], pages 289-312, 1996.

35
Kazuyuki Tanaka.
4 pages, handwritten, 1995.

36
Kazuyuki Tanaka.
(in Japanese).
R.I.M.S. Kokyuroku, 976:77-85, 1997.

37
J. van Heijenoort, editor.
From Frege to Gödel: A Source Book in Mathematical Logic, 1879-1931.
Harvard University Press, 1967.
XII + 660 pages.

Sets and Models of

This document was generated using the LaTeX2HTML translator Version 2002-2-1 (1.71)

Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.
Copyright © 1997, 1998, 1999, Ross Moore, Mathematics Department, Macquarie University, Sydney.

The command line arguments were:
latex2html -split 0 pizowkl

The translation was initiated by Stephen G Simpson on 2004-11-01

Stephen G Simpson 2004-11-01