It is well known that a decidable theory possesses a recursively presentable model. If a decidable theory also possesses a prime model, it is natural to ask if the prime model has a recursive presentation. This has been answered affirmatively for algebraically closed fields [5], and for real closed fields, Hensel fields and other fields [3]. This paper gives a positive answer for the theory of differentially closed fields, and for any decidable ℵ1-categorical theory.

The language of a theory T is denoted by L(T). All languages will be presumed countable. An x-type of T is a set of formulas with free variables x, which is consistent with T and which is maximal in this property. A formula with free variables x is complete if there is exactly one x-type containing it. A type is principal if it contains a complete formula. A countable model of T is prime if it realizes only principal types. Vaught has shown that a complete countable theory can have at most one prime model up to isomorphism.

If T is a decidable theory, then the decision procedure for T equips L(T) with an effective counting. Thus the formulas of L(T) correspond to integers. The integer a formula φ(x) corresponds to is generally called the Gödel number of φ(x) and is denoted by ⌜φ(x)⌝. The usual recursion theoretic notions defined on the set of integers can be transferred to L(T). In particular a type Γ is recursive with index e if {⌜φ⌝.; φ ∈ Γ} is a recursive set of integers with index e.

Shoenfield [6] constructed a hierarchy for any type two object F in which 2E is recursive by generalizing the hyperarithmetical hierarchy, using a jump operation jF defined by

(A similar hierarchy was constructed independently by Hinman [3].) In order to construct a hierarchy for an arbitrary type two F we must first associate with F an operator which, on one hand will always be recursive in F, and on the other hand will generate all the functions recursive in F when iterated over a simultaneously generated set of ordinal notations OF. Clearly the use of 2E in the above definition of jF(f) can be avoided if, instead of diagonalizing F over all functions recursive in f, we only diagonalize F over, say, the functions primitive recursive in f. If furthermore we code in a function which enumerates all functions primitive recursive in f then the resulting operation will certainly generate a primitive recursively expanding hierarchy of functions recursive in F. The problem that remains is whether this hierarchy will exhaust the 1-section of F. But this reduces to an effectiyized version of the following problem: If g is recursive in some level of the hierarchy, is g primitive recursive in some higher level ? An affirmative answer is suggested by the completeness results of Feferman [2], and our main theorem below will be proved by combining his ideas with those of Shoenfield [6]. The result is a hierarchy which applies to all type two objects, and which replaces the notion of recursion in F by the simpler notion of primitive recursion in certain functions generated by F. Unfortunately, in contrast with the Shoenfield hierarchy, the hierarchy developed here cannot always be expected to have the uniqueness property (even w.r.t. ≤T), and for this reason the proof of our main theorem is rather more complicated than the corresponding proof in [6].

§1. Let α be an admissible ordinal which is also a limit of admissible ordinals (e.g. take any α such that α = α*, its projectum [5]). For any admissible γ ≦ α, let [γ) denote the initial segment of ordinals less than γ. A very general question that one might ask is the following: What conditions should one put on γ so that a certain statement true in Lα is ‘reflected’ to be true in Lγ? We cite some examples: (a) If β < γ < α, then Lα ⊨ “β cardinal” is ‘reflected’ to Lγ ⊨ “ β cardinal” (⊨ is just the satisfaction relation). (b) If β < γ < α and γ is a cardinal in Lα (called α-cardinal for short), then Lα ⊨ “β is not a cardinal” is ‘reflected’ to Lγ ⊨ “β is not a cardinal” This fact is used in Gödel's proof that V = L implies the Generalized Continuum Hypothesis. Our objective in this paper is to study a ‘reflection’ property of the following sort: Let A ⊆ [α) be an α-recursively enumerable (α-r.e.), non-α-recursive set. Under what conditions will A restricted to a smaller admissible ordinal γ be γ-r.e. and not γ-recursive?

The notations used here are standard. Those that are not explained are adopted from the paper of Sacks and Simpson [5], to which we also refer the reader for background material.

The basic setting of nonstandard analysis consists of a set-theoretical structure together with a map * from into another structure * of the same sort. The function * is taken to be an elementary embedding (in an appropriate sense) and is generally assumed to make * into an enlargement of [13]. The structures and * may be type-hierarchies as in [11] and [13] or they may be cumulative structures with ω levels as in [14]. The assumption that * is an enlargement of has been found to be the weakest hypothesis which allows for the familiar applications of nonstandard analysis in calculus, elementary topology, etc. Indeed, practice has shown that a smooth and useful theory can be achieved only by assuming also that * has some stronger properties such as the saturation properties first introduced in nonstandard analysis by Luxemburg [11].

This paper concerns an entirely new family of properties, stronger than the saturation properties. For each cardinal number κ, * satisfies the κ-isomorphism property (as an enlargement of ) if the following condition holds:

For each first order language L with fewer than κ nonlogical symbols, if and are elementarily equivalent structures for L whose domains, relations and functions are all internal (relative to * and ), then and are isomorphic.

Some of the theorems contained in the interesting and incisive paper [*] (D. J. Shoesmith and T. J. Smiley, Deducibility and many-valuedness, this Journal, vol. 36 (1970), pp. 610–622) are strongly connected with some earlier results, especially those presented in the paper of Łoś and Suszko [2]. The lack of appropriate bibliographical references in [*] shows that some results which have been obtained relatively long ago are, unfortunately, not so widely known as one might expect. The main task of this short note is to inform briefly on a few results and problems related to those examined in [*].

An operator Γ mapping P(ω) to itself is inductive if Γ(A) ⊇ A for all A. For such an inductive operator Γ we define {Γα : α ∈ ORD} by letting Γ = ⌀, Γα + 1 = Γ(Γα ) for all α, and Γβ = ⋃{Γα : α < β} for limit ordinals β. The closure ordinal ∣Γ∣ of Γ is the least ordinal α such that Γα+1 = Γα and the closure is Γ∣Γ∣.

Let be a class of operators over the natural numbers. The closure ordinal ∣∣ of is the supremum of {∣Γ∣: Γ is an inductive operator and }. The closure algebra generated by is {A ⊆ ω: A is 1-1 reducible to for some inductive operator }. The inductive algebra generated by is {Γα : Γ is an inductive operator in and α < ∣Γ∣}.

For A ∈ P(ω), is the supremum of the ordinals of well-orderings recursive in A. For , let be the supremum of . For example, it is well known that ω() = ω(∆1 0 = ω 1, ω(Π1 1) = ω 1 and ω(Δn 1) = δn 1 for n > 1 (the latter by definition).

Let be the collection of all sets which are finite Boolean combinations of recursively enumerable (r.e.) sets of numbers. Dale Myers asked [private correspondence] whether there exists a nonempty class of sets containing no member of . In this note we construct such a class. The motivation for Myers' question was his observation (reported in [1]) that the existence of such a class is equivalent to the assertion that there is a finite consistent set of tiles which has no m-trial tiling of the plane for any m (obeying the “origin constraint”). (For explanations of these terms and further results on tilings of the plane, cf. [1] and [5].) In addition to the application to tilings, the proof of our results gives some information on bi-immune sets and on complete extensions of first-order Peano arithmetic.

A class of sets may be roughly described as the class of infinite binary input tapes for which a fixed Turing machine fails to halt, or alternatively as the class of infinite branches of a recursive tree of finite binary sequences. (In these definitions, sets of numbers are identified with the corresponding binary sequences.) Precise definitions, as well as many results concerning such classes, may be found in [3] and [4].

In this paper we define by means of a partition property a decreasing sequence N = ‹Nα: α is an ordinal› of classes of ordinals. This property is a generalization of the nonexistence of special Aronszajn trees: the successor cardinal κ+ is in N0 iff there does not exist a special Aronszajn κ+-tree.

The interest in the classes Nα stems from their applicability in model theory, in particular to that aspect of model theory dealing with ordered and two-cardinal models. A model is κ-like iff < is a linear ordering of A of cardinality κ but such that every proper initial segment has cardinality < κ. is α-ordered iff ≼ is a reflexive, linear ordering of some subset of A with order type α. The sequence N can be characterized by a first-order sentence σ in the following manner: The sentence σ has a κ-like α-ordered model iff κ ∉ Nα. This characterization will allow us to translate various independence statements regarding the sequence N to statements about the independence of transfer properties. We say that the transfer property κ → λ holds iff every first-order sentence which has a κ-like model also has a λ-like model. κ ⇸ λ is the negation of κ → λ.

This work is an attempt to characterize the index sets of classes of recursively enumerable sets which are expressible in terms of open sets in the Baire topology on the power set of the set N of natural numbers, usual in recursion theory. Let be a class of subsets of N and be the set of indices of recursively enumerable sets Wх belonging to .

A well-known theorem of Rice and Myhill (cf. [5, p. 324, Rice-Shapiro Theorem]) states that is recursively enumerable if and only ifis a r.e. open set. In this case, note that if is not empty and does not contain all recursively enumerable sets, is a complete set. This theorem will be partially extended to classes which are boolean combinations of open sets by the following:

(i) There is a canonical boolean combination which represents, namely the shortest among boolean combinations which represent.

(ii) The recursive isomorphism type of depends on the length n of this canonical boolean combination (and trivial properties of ); for instance, is recursively isomorphic (in the particular case where is a boolean combination of recursive open sets) to an elementary set combination Yn or Un, constructed from {х ∣ х Wх) and depending on the length n. We can say also that is a complete set in the sense of Ershov's hierarchy [1] (in this particular case).

The ω-rule in the λ-calculus (or, more exactly, the λK-β, η calculus) is

In [1] it was shown that this rule is consistent with the other rules of the λ-calculus. We will show the rule cannot be derived from the other rules; that is, we will give closed terms M and N such that MZ = NZ can be proved without using the ω-rule, for each closed term Z, but M = N cannot be so proved. This strengthens a result in [4] and answers a question of Barendregt.

The language of the λ-calculus has an alphabet containing denumerably many variables a, b, c, … (which have a standard listing e 1, e 2, …), improper symbolsλ, ( , ) and a single predicate symbol = for equality.

Terms are defined inductively by the following:

(1) A variable is a term.

(2) If M and N are terms, so is (MN); it is called a combination.

(3) If M is a term and x is a variable, (λx M) is a term; it is called an abstraction.

We use ≡ for syntactic identity of terms.

If M and N are terms, M = N is a formula.

BV(M), the set of bound variables in M, and FV(M), its free variables, are defined inductively by

A term M is closed iff FV(M) = ∅.

The Kondo-Addison theorem says that every set A of reals contains a real which is implicit (for short, Imp). Any real which is Imp is constructible, and it is the main purpose of this note to show that a close examination of the usual Kondo-Addison argument allows us to compute (in terms of the ordinals associated with A by the classical representation theorem) where in the constructible hierarchy an element of A ∩ Imp must occur. This result is related to a basis theorem of Barwise and Fisher [1] and is accompanied by a strong counterexample which shows that certain tepid improvements of their theorem (and, a fortiori, of the main theorem in this note) are impossible. As a final flourish, the ‘classifying ordinals’ used to compute the locations of the singletons are themselves characterized using an idea from [1].

The least possible jump for a degree of unsolvability a is its join a ∪ 0′ with 0′. Friedberg [1] showed that each degree b ≥ 0′ is the jump of a degree a realizing least possible jump (i.e., satisfying the equation a′ = a ∪ 0′). Sacks (cf. Stillwell [8]) showed that most (in the sense of Lebesgue measure) degrees realize least possible jump. Nevertheless, degrees not realizing least possible jump are easily found (e.g., any degree b ≥ 0′) even among the degrees <0′ (cf. Shoenfield [5]) and the recursively enumerable (r.e.) degrees (cf. Sacks [3]).

A degree is called minimal if it is minimal in the natural partial ordering of degrees excluding least element 0. The existence of minimal degrees <0” was first shown by Spector [7]; Sacks [3] succeeded in replacing 0” by 0′ using a priority argument. Yates [9] asked whether all minimal degrees <0′ realize least possible jump after showing that some do by exhibiting minimal degrees below each r.e. degree. Cooper [2] subsequently showed that each degree b > 0′ is the jump of a minimal degree which, as corollary to his method of proof, realizes least possible jump. We show with the aid of a simple combinatorial device applied to a minimal degree construction in the manner of Spector [7] that not all minimal degrees realize least possible jump. We have observed in conjunction with S. B. Cooper and R. Epstein that the new combinatorial device may also be applied to minimal degree constructions in the manner of Sacks [3], Shoenfield [6] or [4] in order to construct minimal degrees <0′ not realizing least possible jump. This answers Yates' question in the negative. Yates [10], however, has been able to draw this as an immediate corollary of the weaker result by carrying out the proof in his new system of prioric games.

Let σ be any sequence B0, B1 …, Bn, … of transitive sets closed under pairs with for each n. In this paper we show that the smallest admissible set Aσ with σ ∈ Aσ is Σ1 compact. Thus we have an entirely new class of explicitly describable uncountable Σ1 compact sets.

The search for uncountable Σ1 compact languages goes back to Hanf's negative results on compact cardinals [7]. Barwise first showed that all countable admissible sets were Σ1 compact [1] and then went on to give a characterization of the Σ1 compact sets in terms of strict reflection [2]. While his characterization has been of interest in understanding the Σ1 compactness phenomenon it has led to the identification of only one class of uncountable Σ1 compact sets. In particular, Barwise showed [2], using the above notation, that if ⋃nBn is power set admissible it satisfies the strict reflection principle and hence is Σ1 compact. (This result was obtained independently by Karp using algebraic methods [9].)

In proving our compactness theorem we follow Makkai's approach to the Barwise Compactness Theorem [12] and use a modified version of Smullyan's abstract consistency property [14]. A direct generalization of Makkai's method to the cofinality ω case yields a proof of the Barwise-Karp result mentioned above [6]. In order to obtain our new result we depart from the usual definition of language and use instead the indexed languages of Karp [9] in which a conjunction is considered to operate on a function whose range is a set of formulas rather than on a set of formulas itself.

This paper refines some results of Barwise [1] as well as answering the open question posed at the end of [1] about the Hanf number of positively. We conclude by showing that the existence of a Hanf bound for cannot be proved in the natural formally intuitionistic set theories with bounded predicates decidable of [3], [4] and [5].

All notation not explained below is taken from [1]. In the Appendix, we give the axioms of ZF0, ZF1, and T in full. We remark that an important point about the axiom of foundation was not emphasized in [1]. This axiom was intended to be the axiom scheme (∀x)((∀y ∈ x)(A(y)) → A(x)) → (∀x)(A(x)), where y does not occur in A = A(x), instead of the more customary (∀x)(∀y)(y ∈ x → (∃z ∈ x)(∀w ∈ z) (w ∉ x)). This is of no consequence in the presence of full separation, but is vital when considering ZF0 and the T below, for with the customary form of foundation, these cannot even prove the existence of Rω+ω .

In [1], a proof of the following is sketched.

The Hanf number for sentences of a language L is defined to be the least cardinal κ with the property that for any sentence φ of L, if φ has a model of power ≥ κ then φ has models of arbitrarily large cardinality. We shall be interested in the language Lω1,ω (see [3]), which is obtained by adding to the formation rules for first-order logic the rule that the conjunction of countably many formulas is also a formula.

Lopez-Escobar proved [4] that the Hanf number for sentences of Lω1,ω is ⊐ω1, where the cardinals ⊐α are defined recursively by ⊐0 = ℵ0 and ⊐α = Σ{2⊐β: β < α} for all cardinals α > 0. Here ω1 denotes the least uncountable ordinal.

A sentence of Lω1,ω is complete if all its models satisfy the same Lω1,ω-sentences. In [5], Malitz proved that the Hanf number for complete sentences of Lω1,ω is also ⊐ω1, but his proof required the generalized continuum hypothesis (GCH). The purpose of this paper is to give a proof that does not require GCH.

More precisely, we will prove the following:

Theorem 1. For any countable ordinal α, there is a complete Lω1,ω-sentence σαwhich has models of power ⊐α but no models of higher cardinality.

Our basic approach is identical with Malitz's. We simply use a different combinatorial fact at the crucial point.

The concept of model completeness has been very useful in model theory. In this article we obtain a new model theoretic tool by “reversing the arrows.” Specifically, model completeness deals with the relations between a model of a theory and its extensions; in this paper we shall be concerned with the relation between a model of a theory and its homomorphic pre-images.

This work is based on the intuitive principle that metamathematical theorems about universal sentences of the lower predicate calculus and substructures can be translated in a truth-preserving way to theorems about positive sentences and homomorphic images. From model completeness and the completeness theorems which depend on it, this translation gives new criteria for completeness.

Special thanks are due to Professor A. Robinson whose encouragement and suggestions have contributed much to these results.