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].

This note shows that the inconsistency proof of the system of illative combinatory logic given in [1] can be simplified as well as extended to the absolute inconsistency of a more general system.

One extension of the result in [1] lies in the fact that the following weakened form of the deduction theorem for implication will lead to the inconsistency:

Also the inconsistency follows almost as easily for

as it does for ⊢ H2X for arbitrary X, so we will consider the more general case.

The only properties we require other than (DT), (1) and Rule Eq for equality are modus ponens,

and

Let G = [x] Hn−1x⊃: . … H2x⊃ :Hx⊃ . x ⊃ A, where A is arbitrary. Then if Y is the paradoxical combinator and X = YG, X = GX.

Now X ⊂ X, i.e.,

Roughly speaking partial degrees are equivalence classes of partial objects under a certain notion of relative recursiveness. To make this notion precise we have to state explicitly (1) what these partial objects are; (2) how to define a suitable reduction procedure. For example, when the type of these objects is restricted to one, we may include all possible partial functions from natural numbers to natural numbers as basic objects and the reduction procedure could be enumeration, weak Turing, or Turing reducibility as expounded in Sasso [4]. As we climb up the ladder of types, we see that the usual definitions of relative recursiveness, equivalent in the context of type-1 total objects and functions, may be extended to partial objects and functions in quite different ways. First such generalization was initiated by Kleene [2]. He considers partial functions with total objects as arguments. However his theory suffers the lack of transitivity, i.e. we may not obtain a recursive function when we substitute a recursive function into a recursive function. Although Kleene's theory provides a nice background for the study of total higher type objects, it would be unsatisfactory when partial higher type objects are being investigated. In this paper we choose the hierarchy of hereditarily consistent objects over ω as our universe of discourse so that Sasso's objects are exactly those at the type-1 level. Following Kleene's fashion we define relative recursiveness via schemes and indices. Yet in our theory, substitution will preserve recursiveness, which makes a degree theory of partial higher type objects possible. The final result will be a natural extension of Sasso's Turing reducibility. Due to the abstract nature of these objects we do not know much about their behaviour except at the very low types. Here we pay our attention mainly to type-2 objects. In §2 we formulate basic notions and give an outline of our recursion theory of partial higher type objects. In §3 we introduce the definitions of singular degrees and ω-consistent degrees which are two important classes of type-2 objects that we are most interested in.

Let Th be a formal theory extending number theory. Call an ordinal ξ provable in Th if there is a primitive recursive ordering which can be proved in Th to be a wellordering and whose order type is > ξ. One may define the ordinal ∣ Th ∣ of Th to be the least ordinal which is not provable in Th. By [3] and [12] we get , where IDN is the formal theory for N-times iterated inductive definitions. We will generalize this result not only to the case of transfinite iterations but also to a more general notion of ‘the ordinal of a theory’.

For an X-positive arithmetic formula [X,x] there is a natural norm ∣x∣: = μξ (x ∈ Iξ), where Iξ is defined as {x: [∪μ<ξIμ, x]} by recursion on ξ (cf. [7], [17]). By P we denote the least fixed point of [X,x]. Then P = ∪ξξ holds. If Th allows the formation of P, we get the canonical definitions ∥Th()∥ = sup{∣x∣ + 1: Th ⊢ x ∈ P} and ∥Th∥ = sup{∥Th()∥: P is definable in Th} (cf. [17]). If ≺ is any primitive recursive ordering define Q≺[X,x] as the formula ∀y(y ≺ x → y ∈ X) and ∣x∣≺:= ∣x∣O≺. Then ∣x∣≺ turns out to be the order type of the ≺ -predecessors of x and P is the accessible part of ≺. So Th ⊢ x ∈ P implies the provability of ∣x∣≺ in Th.

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.

One of the most significant by-products of the study of admissible sets with urelements is the emphasis it has given to recursively saturated models. As suggested in [Schlipf, 1977], countable recursively saturated models (for finite languages) possess many of the desirable properties of saturated and special models. The notion of resplendency was introduced to isolate some of these desirable properties. In §§1 and 2 of this paper we study these parallels, showing how they can be exploited to give new proofs of some traditional model theoretic theorems. This yields both pedagogical and philosophical advantages: pedagogical since countable recursively saturated models are easier to build and manipulate than saturated and special models; philosophical since it shows that uncountable models — which the downward Lowenheim–Skolem theorem tells us are in some sense not basic in the study of countable theories — are not needed in model theoretic proofs of these theorems. In §3 we apply our local results to get results about resplendent models of ZF set theory and PA (Peano arithmetic). In §4 we shall examine certain analogous results for admissible languages, most similar to, and seemingly generally slightly weaker than, already known results. (The Chang–Makkai sort of result, however, is new.)

Although this paper is an outgrowth of work with admissible sets with urelements, I have tried to keep it as accessible as possible to those with a background only in finitary model theory. Thus §§1,2, and 3 should not involve any work with admissible sets. §4, however, is concerned with some admissible analogues to results in §2 and necessarily uses certain technical results of §11 5 of [Schlipf, 1977].

Let Γ be a collection of relations on the reals and let M be a set of reals. We call M a perfect set basis for Γ if every set in Γ with parameters from M which is not totally included in M contains a perfect subset with code in M. A simple elementary proof is given of the following result (assuming mild regularity conditions on Γ and M): If M is a perfect set basis for Γ, the field of every wellordering in Γ is contained in M. An immediate corollary is Mansfield's Theorem that the existence of a Σ21 wellordering of the reals implies that every real is constructible. Other applications and extensions of the main result are also given.

In this paper we will do some model theory with respect to the models, defined in [7] and, as in [7], we will work again in intuitionistic metamathematics.

In this paper we will only consider models M = ‹S, TM›, where S is one fixed spreadlaw for all models M, namely the universal spreadlaw. That we can restrict ourselves to this class of models is a consequence of the completeness proof, which is sketched in [7, §3].

The main tools in this paper will be two model-constructions:

(i) In §1 we will consider, under a certain condition C(M0, M, s), the construction of a model R(M0, M, s) from two models M0 and M with respect to the finite sequence s.

(ii) In §2 we will construct from an infinite sequence M0, M1, M2, … of models a new model Σi∈INMi.

Syntactic proofs of the disjunction property and the explicit definability theorem are well known.

C. Smorynski [8] gave semantic proofs of these theorems with respect to Kripke models, however using classical metamathematics. In §1 we will give intuitionistically correct, semantic proofs with respect to the models, defined in [7] using Brouwer's continuity principle.

Let W be the fan of all models (see [7, Theorem 2.7]) and let Γ be a countably infinite sequence of sentences.

It has been shown that, for all rational numbers r such that 0≤ r ≤ 1, the ℵ0-valued Łukasiewicz propositional calculus whose designated truth-values are those truth-values x such that r ≤ x ≤ 1 may be formalised completely by means of finitely many axiom schemes and primitive rules of procedure. We shall consider now the case where r is rational, 0≥r≤1 and the designated truth-values are those truth-values x such that r≤x≤1.

We note that, in the subcase of the previous case where r = 1, a complete formalisation is given by the following four axiom schemes together with the rule of modus ponens (with respect to C),

the functor A being defined in the usual way. The functors B, K, L will also be considered to be defined in the usual way. Let us consider now the functor Dαβ such that if P, Dαβ take the truth-values x, dαβ(x) respectively, α, β are relatively prime integers and r = α/β then

It follows at once from a theorem of McNaughton that the functor Dαβ is definable in terms of C and N in an effective way. If r = 0 we make the definition

We note first that if x ≤ α/β then dαβ(x)≤(β + 1)α/β − α = α/β. Hence

Let us now define the functions dnαβ(x) (n = 0,1,…) by

Since

it follows easily that

and that

Thus, if x is designated, x − α/β > 0 and, if n > − log(x − α/β)/log(β + 1), then (β + 1)n(x−α/β) > 1.

Early work combining recursion theory and algebra had (at least) two different sets of motivations. First the precise setting of recursion theory offered a chance to make formal classical concerns as to the effective or algorithmic nature of algebraic constructions. As an added benefit the formalization gives one the opportunity of proving that certain constructions cannot be done effectively even when the original data is presented in a recursive way. One important example of this sort of approach is the work of Frohlich and Shepardson [1955] in field theory. Another motivation for the introduction of recursion theory to algebra is given by Rabin [1960]. One hopes to mathematically enrich algebra by the additional structure provided by the notion of computability much as topological structure enriches group theory. Another example of this sort is provided in Dekker [1969] and [1971] where the added structure is that of recursive equivalence types. (This particular structural view culminates in the monograph of Crossley and Nerode [1974].)

More recently there is the work of Metakides and Nerode [1975], [1977] which combines both approaches. Thus, for example, working with vector spaces they show in a very strong way that one cannot always effectively extend a given (even recursive) independent set to a basis for a (recursive) vector space.

We shall describe Boolean extensions of models of set theory with the axiom of choice in which cardinals are collapsed by mappings definable from parameters in the ground model. In particular, starting from the constructible universe, we get Boolean extensions in which constructible cardinals are collapsed by ordinal definable sets.

Let be a transitive model of set theory with the axiom of choice. Definability of sets in the generic extensions of is closely related to the automorphisms of the corresponding Boolean algebra. In particular, if G is an -generic ultrafilter on a rigid complete Boolean algebra C, then every set in [G] is definable from parameters in . Hence if B is a complete Boolean algebra containing a set of forcing conditions to collapse some cardinals in , it suffices to construct a rigid complete Boolean algebra C, in which B is completely embedded. If G is as above, then [G] satisfies “every set is -definable” and the inner model [G ∩ B] contains the collapsing mapping determined by B. To complete the result, it is necessary to give some conditions under which every cardinal from [G ∩ B] remains a cardinal in [G].

The absolutness is granted for every cardinal at least as large as the saturation of C. To keep the upper cardinals absolute, it often suffices to construct C with the same saturation as B. It was shown in [6] that this is always possible, namely, that every Boolean algebra can be completely embedded in a rigid complete Boolean algebra with the same saturation.

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 [1, §14E], a sequent calculus formulation (L.-formulation) of type assignment (theory of functionality) is given for a system based either on a system of combinators with strong reduction or on a system of λη-calculus provided that the rule for subject conversion (which says that if X has type α and X cnv Y then Y has type α) is postulated for the system. This sequent calculus formulation does not work for a system based on the λβ-calculus. In [2] I introduced a sequent calculus formulation for a system without the rule of subject conversion based on any of the three systems mentioned above. Further, in [2, §5] I pointed out that if proper inclusions of the form of the statement that λx·x is a function from α to β are postulated, then functions are identified with their restrictions in the λη-calculus but not in the λβ-calculus, and that therefore there is some interest in having a sequent calculus formulation of type assignment with the rule of subject conversion for systems based on the λβ-calculus. In this paper, such a system is presented, the elimination theorem (Gentzen's Hauptsatz) is proved for it, and it is proved equivalent to the natural deduction formulation of [1, §14D].

I shall assume familiarity with the λβ-calculus, and shall use (with minor modifications) the notational conventions of [1]. Hence, the theory of type assignment (theory of functionality) will be based on an atomic constant F such that if α and β are types then Fαβ represents roughly the type of functions from α to β (more exactly it represents the type of functions whose domain includes α and under which the image of α is included in β).

In this paper we introduce a new notion of realizability for intuitionistic arithmetic in all finite types. The notion seems to us to capture some of the intuition underlying both the recursive realizability of Kjeene [5] and the semantics of Kripke [7]. After some preliminaries of a syntactic and recursion-theoretic character in §1, we motivate and define our notion of realizability in §2. In §3 we prove a soundness theorem, and in §4 we apply that theorem to obtain new information about provability in some extensions of intuitionistic arithmetic in all finite types. In §5 we consider a special case of our general notion and prove a kind of reflection theorem for it. Finally, in §6, we consider a formalized version of our realizability notion and use it to give a new proof of the conservative extension theorem discussed in Goodman and Myhill [4] and proved in our [3]. (Apparently, a form of this result is also proved in Mine [13]. We have not seen this paper, but are relying on [12].) As a corollary, we obtain the following somewhat strengthened result: Let Σ be any extension of first-order intuitionistic arithmetic (HA) formalized in the language of HA. Let Σω be the theory obtained from Σ by adding functionals of finite type with intuitionistic logic, intensional identity, and axioms of choice and dependent choice at all types. Then Σω is a conservative extension of Σ. An interesting example of this theorem is obtained by taking Σ to be classical first-order arithmetic.

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.

Fine [1] and Thomason [4] have recently shown that the familiar relational semantics of Kripke [2] is inadequate for certain normal extensions of T and S4. It is here shown that the more general semantics developed by Kripke in [3] to handle nonnormal modal logics is likewise inadequate for certain of those logics.

The interest of incompleteness results, such as those of Fine and Thomason, is of course a function of one's expectations. Define a “normal” logic too broadly and it is not surprising that a given semantics is not adequate for all normal logics. In the case of relational semantics, for example, one would want to require at least that a normal logic contain T, the logic determined by the class of all normal frames, and that it be closed under certain (though perhaps not all) rules of inference which are validity preserving in such frames. The adequacy of that semantics will otherwise be ruled out at the outset.

For Kripke a logic is normal if it contains all tautologies, □p→p and □ (p → q)→(□p → □q), and is closed under the rules of substitution, modus ponens and necessitation (from A infer □A). T is the smallest normal logic, and this fact, together with the “naturalness” of the definition and the enormous number of normal logics which have been shown to be complete, made it plausible to suppose that Kripke's original semantics was adequate for all normal logics. That it is not is indeed surprising and would seem to reveal a genuine shortcoming.

A λ-theory T is a consistent set of equations between λ-terms closed under derivability. The degree of T is the degree of the set of Gödel numbers of its elements. is the λ-theory axiomatized by the set {M = N∣ M, N unsolvable}. A λ-theory is sensible iff T ⊃ ; for a motivation see [6] and [4].

In §1 it is proved that the theory is Σ20-complete. We present Wadsworth's proof that its unique maximal consistent extension * (= Th(D∞)) is Π20-complete. In §2 it is proved that η (= λη-calculus + ) is not closed under the ω-rule (see [1]). In §3 arguments are given to conjecture that is Π11-complete. This is done by representing recursive sets of sequence numbers as λ-terms and by connecting wellfoundedness of trees with provability in ω. In §4 an infinite set of equations independent over η will be constructed. From this it follows that there are 2ℵ0 sensible theories T such that and 2ℵ0 sensible hard models of arbitrarily high degrees. In §5 some nonprovability results needed in §§1 and 2 are established. For this purpose one uses the theory η extended with a reduction relation for which the Church–Rosser theorem holds. The concept of Gross reduction is used in order to show that certain terms have no common reduct.

Since A. Robinson introduced the classes of existentially complete and generic models, conditions which were interesting for elementary classes were considered for these classes. In [6] H. Simmons showed that with the natural definitions there are prime and saturated existentially complete models and these are very similar to their elementary counterparts which were introduced by Vaught [2, 2.3]. As Example 6 will show, there is a limit to the similarity—there are theories which have exactly two existentially complete models.

In [6] H. Simmons considers the following list of properties, shows that each property implies the next one and asks whether any of them implies the previous one:

1.1. T is ℵ0-categorical.

1.2. T has an ℵ0-categorical model companion.

1.3. ∣E∣ = 1.

1.4. ∣E∣ < .

1.5. T has a countable ∃-saturated model.

1.6. T has a ∃-prime model.

1.7. Each universal formula is implied by a ∃-atomic existential formula.

[The reader is referred to [1], [3], [4] and [6] for the definitions and background.

We only mention that T is always a countable theory. All the models under discussion are countable. Thus E is the class of countable existentially complete models and F and G, respectively, are the classes of countable finite and infinite generic models. For every class C,∣C∣ is the number of (countable) models in C.]

In 1930, A. Heyting first specified a formal system for part of intuitionistic mathematics. Although his rules were presumably motivated by the “intended interpretation” or meaning of the logical symbols, over the years a number of other possible interpretations have been discovered for which the rules are also valid. In particular, one might mention the realizablity interpretation of Kleene, the (Dialectica) interpretation of Gödel, and various semantic interpretations, such as Kripke models. (Each of these has several variants or close relatives.) Each such interpretation can be regarded as defining precisely a certain “notion of constructivity”, the study of which may illuminate the still rather vague notions which underlie the intended interpretation; or, if one doubts that there is a single interpretation “intended” by all constructivist mathematicians, the study of precisely defined interpretations may help to delineate and distinguish the possibilities.

In the last few years, Heyting's systems have been vastly extended, in order to encompass the large and growing body of constructive mathematics. Several kinds of new systems have been put forward and studied. The present author has extended the various realizability interpretations to several of these systems [B1], [B2] and drawn a number of interesting applications. The mathematical content of the present paper is an interpretation in the style of Godel's Dialectica interpretation, but applicable to the new systems put forward by Feferman [Fl]. The original motivation for this work was to obtain certain metamathematical applications: roughly speaking, Markov's rule and its variants.

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.