This paper gives some simple existence results on prime and atomic models over sets. It also contains an example in which there is no prime model over a certain set even though there is an atomic model over the set. The existence results are “local” in that they deal with just one set rather than all sets contained in models of some theory. For contrast, see the “global” results in [6] or [7, p. 200].

Throughout the paper, L is a countable language, and T is a complete L-theory with infinite models. There is a “large” model of T that contains the set X and any other sets and models to be used in a particular construction of a prime or atomic model over X.

A model is said to be prime over X if and every elementary monomorphism on X can be extended to an elementary embedding on all of . This notion is used in a variety of ways in model theory. It aids in distinguishing between models that are not isomorphic, as in Vaught [10]. It also aids in showing that certain models are isomorphic, as in Baldwin and Lachlan [1].

In recent years, the Axiom of Determinateness (AD) has yielded numerous results concerning the size and properties of the first ω-many uncountable cardinals. Briefly, these results began with Solovay's discovery that ℵ1 and ℵ2 are measurable [8], [3], continued with theorems of Solovay, Martin, and Kunen concerning infinite-exponent partition relations [6], [3], Martin's proof that ℵn has confinality ℵ2 for 1 < n < ω, and very recently, Kleinberg's proof that the ℵn are Jonsson cardinals [4].

This paper was inspired by a very recent result of Martin from AD that ℵ1 is ℵ2-super compact. It was known for some time that AD implies ℵ1 is α-strongly compact for all ℵ < θ (where θ is the least cardinal onto which 2ω cannot be mapped, quite a large cardinal under AD), and that ADR implies that ℵ1, is α-super compact for all α < θ. A key open question had been whether or not ℵ1 is super compact under AD alone.

This paper comments on the method of Martin in several different ways. In §2, we will prove that ℵ1 is ℵ2-super compact, and then generalize the method to show that ℵ2 is ℵ3-strongly compact. In addition, we will demonstrate a limitation in the method by showing that the possible measures obtained on are not normal, and that the method cannot be extended to show that ℵ2 is ℵ4-strongly compact.

A first-order theory is companionable if it is mutually model-consistent with a model-complete theory. The latter theory is then called a model-companion for the former theory. For example, the theory of formally real fields is a companionable theory; its model-companion is the theory of real closed fields. If a companionable, inductive theory has the amalgamation property, then its model-companion is actually a model-completion. For example, the theory of fields is a companionable, inductive theory with the amalgamation property; its model-completion is the theory of algebraically closed fields.

The goal of this paper is the characterization, by “algebraic” or “structural” properties, of the companionable, universal theories which satisfy a certain finiteness condition. A theory is companionable precisely when the theory consisting of its universal consequences is companionable. Both theories have the same model-companion if either has one. Accordingly, nought is lost by the restriction to universal theories. The finiteness condition, finite presentation decompositions, is an analogue for an arbitrary theory of the decomposition of a radical ideal in a Noetherian, commutative ring into a finite intersection of prime ideals for the theory of integral domains. The companionable theories with finite presentation decompositions are characterized by two properties: a coherence property for finitely generated submodels of finitely presented models and a homomorphism lifting property for homomorphisms from submodels of finitely presented models.

In [4], Metakides and Nerode define a recursively presented vector space V∞. over a (finite or infinite) recursive field F to consist of a recursive subset U of the natural numbers N and operations of vector addition and scalar multiplication which are partial recursive and under which V∞ becomes a vector space. Throughout this paper, we will identify V∞ with N, say via some fixed Gödel numbering, and assume V∞ is infinite dimensional and has a dependence algorithm, i.e., there is a uniform effective procedure which determines whether any given n-tuple v0, …, vn−1 from V∞ is linearly dependent. Given a subspace W of V∞, we write dim(W) for the dimension of W. Given subspaces V and W of V∞, V + W will denote the weak sum of V and W and if V ∩ W = {0) (where 0 is the zero vector of V∞), we write V ⊕ W instead of V + W. If W ⊇ V, we write W mod V for the quotient space. An independent set A ⊆ V∞ is extendible if there is a r.e. independent set I ⊇ A such that I − A is infinite and A is nonextendible if it is not the case that A is extendible.

We give two examples. T0 has nine countable models and a nonprincipal 1-type which contains infinitely many 2-types. T1, has four models and an inessential extension T2 having infinitely many models.

Martin [10] has computed the degrees of several classes of ω-r.e. sets. Lachlan [3] and Shoenfield [14] have obtained some additional results. For most of the examples, a class of r.e. sets is given by a property that is first-order definable over the lattice of ω-r.e. sets. Then the set of degrees of sets in this class is computed. The only sets of nonzero degrees which arise from the known examples are the following: ϕ, {a∣a is ω-r.e. and a ≠ 0}, {a∣a is ω-r.e. and a′ = 0″}, and {a∣a is ω-r.e. and a″ > 0″} (see [14]).

There have been some results in this direction for α an arbitrary admissible ordinal. Sacks [13] has shown that every nonzero α-r.e. α-degree contains a regular α-r.e. set. Thus regularity does not separate the α-r.e. α-degrees. Simpson [18] has several theorems which give information about the kinds of α-r.e. sets a given α-degree can contain. The classes of α-r.e. sets considered do separate the α-r.e. α-degrees into two nonempty pieces for some α's, but they are not necessarily given by properties which are definable over the lattice of α-r.e. sets. Using some definability results of Lerman [6], we shall make some comments about the definability of these classes of sets.

Answering a problem of Fuhrken we prove that for every κ, 1 ≤ κ ≤ ℵ0, there is a (countable) complete theory T, with no prime model, and exactly κ minimal models (up to isomorphism).

Let T be a complete theory with infinite models in a countable language. The stability function gT(κ) is defined as the supremum of the number of types over models of T of power κ. It is proved that there are only six possible stability functions, namely κ, κ + 2ω, κω, ded κ, (ded κ)ω, 2κ.

In [5] S. S. Wainer introduces a hierarchy for arbitrary type-2-functionals. Given F, he defines a set of ordinal notations OF, and for each a ∈ OF, a function fa recursive in F and an ordinal ∣a∣F < For any f recursive in F there is an a ∈ OF such that f is primitive recursive in fa.

Let ρF be the least ordinal α such that for any f recursive in F there is an α ∈ OF with ∣a∣F ≤ α such that f is primitive recursive in fa. If ρF < the hierarchy breaks down. In Bergstra and Wainer [2] ρF is described as “the real ordinal of the 1-section of F”.

Using standard methods (originally due to Kleene) one may prove that if F is normal, then ρF = Feferman has proved that if F is recursive, then ρF = ω2.

Let 1-section (F) = l-sc(F) = {f; f is recursive in F} where f is a total object of type 1.

Grilliot [4] proved that F ↾ 1-sc(F) is continuous if and only if F is not normal.

Let h be an associate for a given functional F, and assume that h is recursive in the jump of an element of 1-sc(F).

We prove that a countable complete theory whose prime model has an infinite definable subset, all of whose elements are named, has at least four countable models up to isomorphism. The motivation for this is the conjecture that a countable theory with a minimal model has infinitely many countable models. In this connection we first prove that a minimal prime model A has an expansion by a finite number of constants A′ such that the set of algebraic elements of A′ contains an infinite definable subset.

We note that our main conjecture strengthens the Baldwin–Lachlan theorem. We also note that due to Vaught's result that a countable theory cannot have exactly two countable models, the weakest possible nontrivial result for a non-ℵ0-categorical theory is that it has at least four countable models.

§1. Notation and preliminaries. Our notation follows Chang and Keisler [1], except that we denote models by A, B, etc. We use the same symbol to refer to the universe of a model. Models we refer to are always in a countable language. For T a countable complete theory we let n(T) be the number of countable models of T up to isomorphism. ∃n means ‘there are exactly n’.

This note is concerned with the old topic, initiated by Kleene, of the connections between recursive function theory and provability in intuitionistic arithmetic. More specifically, we are interested in the relationship between the hierarchy of degrees of unsolvability and the interdeducibility of cases of excluded middle. The work described below was motivated by a counterexample, to be given presently, which shows that that relationship is more complicated than one might suppose.

Let HA be first-order intuitionistic arithmetic. Let the symbol ⊢ mean derivability in HA. For each natural number n, let n¯ be the corresponding numeral. Let Ω be the standard model of arithmetic. Say that a sentence ϕ is true iff Ω⊨ ϕ. Now suppose ϕ(x) and Ψ(x) are formulas with only the variable x free. Suppose

Then it is natural to conjecture that {n∣Ω⊨Ψ(n¯)} is recursive in {n∣Ω⊨ϕ(n¯)}.

However, this conjecture is false. Consider the formula is a formalization of Kleene's T-predicate.

It is proved here, assuming Projective Determinacy, that every ascending sequence of -degrees has a minimal strict upper bound but no least strict upper bound. This generalizes a result of Friedman for n = 1.

Our general notation and terminology will be that of [Ke1] and [Mo1]. Letters i,j, k,… denote members of ω and α, β, ϒ,… members of ωω i.e. reals. Projective Determinacy (PD) is the hypothesis that every projective set of reals in determined, while in general for a collection of sets of reals Γ, Determinacy (Γ) abbreviates the statement that every set in Γ is determined.

§1. -degrees. For each m ≥ 1 and α, β Є ωω let α ≤mβ ⇔ α Є (β), α <mβ ⇔ α ≤mβ ∧ β ≰mα, and α ≡mβ ⇔ α ≤mβ ∧ β ≤mα.Clearly ≡m is an equivalence relation on ωω. The ≡m -equivalence class of α Є ωω is called its -degree, in symbols

If d = [α]m, e = [β]m then we define

One of the main results of Barwise [2] (see also [7, Chapter VIII]) showed that the s – reflection principle for a set A is equivalent to Σ1-compactness of . Here A is any transitive p.r. closed set, and is the infinitary language on A which allows conjunction and disjunction over arbitrary sets Φ Є A, and finite quantification.

In this paper we consider languages , where B is a Δ0 subset of A, which is like but we allow quantifiers ∀x and ∃x where x is any set of variables indexed by an element of B. A treatment similar to that of [2] for establishes a sufficient, and in some cases necessary, condition for to be Σ1-compact. The use of infinitary Skolem functions is intrinsic to the method, so to avoid a separate development of the rudiments of the Skolem language we actually define to have b-ary relation and function symbols for every b Є B.

We show that several theorems on ordinal bounds in different parts of logic are simple consequences of a basic result in the theory of global inductive definitions.

Chang, in [1], proves an interpolation theorem (Theorem I, remark b)) for a first-order language. The proof of Chang's theorem uses essentially nonsimple devices, like special and ω1-saturated models.

In remark e) in [1], Chang asks if there is a simpler proof of his Theorem I.

In [1], Chang proves also another interpolation theorem (Theorem II), which is not an extension of his Theorem I, but extends Craig's interpolation theorem to Lα+,ω languages with interpolant in Lα+,α where α is a strong limit cardinal of cofinality ω.

In remark k) in [1], Chang asks if there is a generalization of both Theorems I and II in [1], or at least a generalization of both Theorem I in [1] and Lopez-Escobar's interpolation theorem in [7].

Maehara and Takeuti, in [8], show that there is a completely different proof of Chang's interpolation Theorem I as a consequence of their interpolation theorems. The proofs of these theorems of Maehara and Takeuti are proof theoretical in character, involving the notion of cut-free natural deduction, and it uses devices as simple as those needed for the usual Craig's interpolation theorem. Hence this can be considered as a positive answer to Chang's question in remark e) in [1].

We prove that every model of T = Th(ω, <,…) (T countable) has an end extension; and that every countable theory with an infinite order and Skolem functions has nonisomorphic countable models; and that if every model of T has an end extension, then every ∣T∣-universal model of T has an end extension definable with parameters.

We construct a model of Peano arithmetic in an uncountable language which has no elementary end extension. This answers a question of Gaifman and contrasts with the well-known theorem of MacDowell and Specker which states that every model of Peano arithmetic in a countable language has an elementary end extension. The construction employs forcing in a nonstandard model.

We show it is consistent with ZFC that the Hanf number of Ellentuck's Souslin logic should be exactly .

Given I, a reasonable countable set of Turing degrees, can we find some sort of canonical strict upper bound on I? If I = {a ∣ a ≤ b}, the upper bound on I which springs to mind is b′. But what if I is closed under jump? This question arises naturally out of the question which motivates a large part of hierarchy theory: Is there a canonical increasing function from a countable ordinal, preferably a large one, into D, the set of Turing degrees? If d is to be such a function, it is natural to require that d(α + 1) = d(α)′; but how should d(λ) depend on d ↾ λ, where λ is a limit ordinal?

For any I ⊆ D, let MI, = ⋃I. Towards making the above questions precise, we introduce ideals of Turing degrees.

Definition 1. I ⊆ D is an ideal iff I is closed under jump and join, and I is downward-closed, i.e., if a ≤ b & b ϵ I then a ϵ I.

The following definition reflects the hierarchy-theoretic motivation for this paper.

Definition 2. For I ⊆ D and A ⊆ ω, I is an A-hierarchy ideal iff for some countable ordinal α, MI = Lα[A]∩ ωω.

All hierarchy ideals are ideals, but not conversely.

Early in the game Spector knocked out the best sort of canonicity for upper bounds on ideals, proving that no set of degrees closed under jump has a least upper bound.

Gödel has called to my attention that p. 773 is misleading in regard to the discovery of the finite axiomatization and its place in his proof of the consistency of GCH. For the version in [1940], as he says on p. 1, “The system Σ of axioms for set theory which we adopt [a finite one] … is essentially due to P. Bernays …”. However, it is not at all necessary to use a finite axiom system. Gödel considers the more suggestive proof to be the one in [1939], which uses infinitely many axioms.

His main achievement regarding the consistency of GCH, he says, really is that he first introduced the concept of constructible sets into set theory defining it as in [1939], proved that the axioms of set theory (including the axiom of choice) hold for it, and conjectured that the continuum hypothesis also will hold. He told these things to von Neumann during his stay at Princeton in 1935. The discovery of the proof of this conjecture On the basis of his definition is not too difficult. Gödel gave the proof (also for GCH) not until three years later because he had fallen ill in the meantime. This proof was using a submodel of the constructible sets in the lowest case countable, similar to the one commonly given today.