So-called “preservation theorems” relate the (possible) syntactic form of the axioms of a theory to certain closure conditions on its class of models. Such results are well known for the first-order predicate calculus, Lω, ω, and there are various expositions; e.g., Keisler [14], [15]. For the language , the first results were the theorems of Lopez-Escobar on sentences preserved under homomorphic images and of Malitz on formulas preserved under substructures. More recently, Feferman added a result on formulas preserved under (or persistent for) ∈-extensions. Some of these theorems will be considered in subsequent sections. A more thorough treatment may be found in Makkai [17]. The main new preservation result obtained here characterizes the sentences preserved under ω-unions. This notion and the statement of the theorem will be explained shortly.

It is a familiar experience in mathematical research that concepts which are equivalent in a special case diverge in general. In the case at hand, one must expect to consider different possible statements for , which generalize a known result for Lω, ω. Moreover, diverse proofs may yield the same result in the special case, not all of which can be extended to the general case. Again, since the compactness theorem fails for , one cannot expect to extend the arguments from Lω, ω which use this in an essential way.

Since 1933, when Kolmogorov laid the foundations for probability and statistics as we know them today [1], it has been recognized that propositions asserting that such and such an event occurred as a consequence of the execution of a particular random experiment tend to band together and form a Boolean algebra. In 1936, Birkhoff and von Neumann [2] suggested that the so-called logic of quantum mechanics should not be a Boolean algebra, but rather should form what is now called a modular ortholattice [3]. Presumably, the departure from Boolean algebras encountered in quantum mechanics can be attributed to the fact that in quantum mechanics, one must consider more than one physical experiment, e.g., an experiment measuring position, an experiment measuring charge, an experiment measuring momentum, etc., and, because of the uncertainty principle, these experiments need not admit a common refinement in terms of which the Kolmogorov theory is directly applicable.

Mackey's Axioms I–VI for quantum mechanics [4] imply that the logic of quantum mechanics should be a σ-orthocomplete orthomodular poset [5]. Most contemporary practitioners of quantum logic seem to agree that a quantum logic is (at least) an orthomodular poset [6], [7], [8], [9], [10] or some variation thereof [11]. P. D. Finch [12] has shown that every completely orthomodular poset is the logic arising from sets of Boolean logics, where these sets have a structure similar to the structures generally given to quantum logic. In all of these versions of quantum logic, a fundamental relation, the relation of compatibility or commutativity, plays a decisive role.

The usual formulations of combinatory logic, as in Church [1] or Curry and Feys [2], have no straightforward semantics. This lack complicates the proofs of basic metasystematic results, prevents the perspicuous formalization of combinatory logic as a deductive theory, and makes the combinators unnecessarily difficult to apply to recursion theory or to the foundations of mathematics. In the present paper we shall give a new formulation of combinatory logic, thought of as an abstract theory of rules. At each stage in the development we shall give a precise semantic interpretation for our axioms. We begin with an abstract treatment of the syntax and semantics of a theory of rules. We then specialize to the theory of the combinators and prove a completeness theorem connecting our axioms with our semantics. On this basis we treat functional abstraction, truth-functions, and the representation of partial recursive functions. In the spirit of Church [1, pp. 62–71], we conclude by extending our methods to the treatment of intensional identity.

The theories developed here are part of a simplification of the theory of constructions described in [3]. Their semantics are motivated by the intended interpretation of the theory of constructions. The present paper is selfcontained and can be read without any familiarity with the theory of constructions, although the motivation of several of the notions considered here is given in [3]. In a future publication we will use the results of the present paper as the basis for a detailed study of a simplified form of the theory in [3].

We prove here theorems of the form: if T has a model M in which P1(M) is κ1-like ordered, P2(M) is κ2-like ordered …, and Q1(M) is of power λ1, …, then T has a model N in which P1(M) is κ1′-like ordered …, Q1(N) is of power λ1′, …. (In this article κ is a strong-limit singular cardinal, and κ′ is a singular cardinal.)

We also sometimes add the condition that M, N omits some types. The results are seemingly the best possible, i.e. according to our knowledge about n-cardinal problems (or, more precisely, a certain variant of them).

It is well known that the laws of logic governing the sentence connectives—“and”, “or”, “not”, etc.—can be expressed by means of equations in the theory of Boolean algebras. The task of providing a similar algebraic setting for the full first-order predicate logic is the primary concern of algebraic logicians. The best-known efforts in this direction are the polyadic algebras of Halmos (cf. [2]) and the cylindric algebras of Tarski (cf. [3]), both of which may be described as Boolean algebras with infinitely many additional operations. In particular, there is a primitive operator, cκ, corresponding to each quantification, ∃υκ. In this paper we explore a version of algebraic logic conceived by A. H. Copeland, Sr., and described in [1], which has this advantage: All operators are generated from a finite set of primitive operations.

Following the theory of cylindric algebras, we introduce, in the natural way, the classes of Copeland set algebras (SCpA), representable Copeland algebras (RCpA), and Copeland algebras of formulas. Playing a central role in the discussion is the set, Γ, of all equations holding in every set algebra. The reason for this is that the operations in a set algebra reflect the notion of satisfaction of a formula in a model, and hence an equation expresses the fact that two formulas are satisfied by the same sequences of objects in the model. Thus to say that an equation holds in every set algebra is to assert that a certain pair of formulas are logically equivalent.

The purpose of this work is to formulate a general theory of forcing with classes and to solve some of the consistency and independence problems for the impredicative theory of classes, that is, the set theory that uses the full schema of class construction, including formulas with quantification over proper classes. This theory is in principle due to A. Morse [9]. The version I am using is based on axioms by A. Tarski and is essentially the same as that presented in [6, pp. 250–281] and [10, pp. 2–11]. For a detailed exposition the reader is referred there. This theory will be referred to as .

The reflection principle (see [8]), valid for other forms of set theory, is not provable in . Some form of the reflection principle is essential for the proofs in the original version of forcing introduced by Cohen [2] and the version introduced by Mostowski [10]. The same seems to be true for the Boolean valued models methods due to Scott and Solovay [12]. The only suitable form of forcing for found in the literature is the version that appears in Shoenfield [14]. I believe Vopěnka's methods [15] would also be applicable. The definition of forcing given in the present paper is basically derived from Shoenfield's definition. Shoenfield, however, worked in Zermelo-Fraenkel set theory.

I do not know of any proof of the consistency of the continuum hypothesis with assuming only that is consistent. However, if one assumes the existence of an inaccessible cardinal, it is easy to extend Gödel's consistency proof [4] of the axiom of constructibility to .

In this paper we discuss subsystems of number theory based on restrictions on induction in terms of quantifiers, and we show that all the natural formulations of ‘n-quantifier induction’ are reducible to one of two (for n ≠ 0) nonequivalent normal forms: the axiom of induction restricted to (or, equivalently, ) formulae and the rule of induction restricted to formulae.

Let Z0 be classical elementary number theory with a symbol and defining equations for each Kalmar elementary function, and the rule of induction

restricted to quantifier-free formulae. Given the schema

let IAn be the restriction of IA to formulae of Z0 with ≤n nested quantifiers, IAn′ to formulae with ≤n nested quantifiers, disregarding bounded quantifiers, the restriction to formulae, the restriction to , formulae. IRn, IRn′, , are analogous.

Then, we show that, for every n, , , IAn, and IAn′, are all equivalent modulo Z0. The corresponding statement does not hold for IR. We show that, if n ≠ 0, is reducible to ; evidently IRn is reducible to . On the other hand, IRn′ is obviously equivalent to IAn′ [10, Lemma 2].

A hierarchy of systems of quantifier-free elementary recursive arithmetics, based on the Grzegorczyk hierarchy of functions, was set up in [2] and some meta-mathematical properties of these systems were developed. The Grzegorczyk hierarchy has been extended recently, mainly by Löb and Wainer [5], and our metamathematical developments may be similarly extended; the αth member of this hierarchy of formal systems will be denoted -arithmetic throughout. The main result in [2] was: For α > 1, -arithmetic can be proved consistent in -arithmetic. In this paper we shall continue this work in particular, beginning with this consistency result, we shall find (for α > 1) the order type of the weakest simple transfinite induction scheme which is independent of -arithmetic, thus giving a ‘measure of the complexity of derivations’ of these systems. For example we shall show that transfinite induction on a sequence of type ωω is a nonderivable rule of primitive recursive arithmetic (-arithmetic). This particular result was proved by Guard in [4] by a specialisation of a version of Gentzen's proof that ∈0-transfinite induction is independent of some standard formal systems of arithmetic with quantifiers. These methods can be adapted to our hierarchy but require what we might term an ‘ωω-jump’—that is if β is the largest ordinal for which transfinite induction up to β is derivable in the system in question then a scheme of transfinite induction up to β·ωω is independent. The proof presented in this paper requires only an ‘ω-jump’ and allows more precise results to be obtained for the systems in the extended Grzegorczyk hierarchy; it is also more direct and less proof-theoretic in character. We show that the consistency of -arithmetic (for α > 1) can be proved in a system obtained by adding to -arithmetic a transfinite induction scheme up to ω2, and that this induction scheme can be adapted to obtain the required result by increasing the ordinal and simultaneously decreasing the complexity of the functions involved in the induction scheme (detailed definitions of these concepts will be given in the next section).

In [3] Kemeny made the following conjecture: Suppose *Z is a nonstandard model of the ring of integers Z. Let

and let F be the subgroup of those cosets ā which contain an element of infinite height in *Z. Kemeny then asked if the ring R = {a: ā ∈ F} is also a nonstandard model of Z. If so then Goldbach's conjecture is false because Kemeny also shows in [3] that Goldbach's conjecture fails in R.

The papers [1] and [5] by Gandy and Mendelson show that R is not a nonstandard model of Z but we give here a simpler proof based on Mendelson's paper. Suppose R is a nonstandard model of Z. Then each positive number in R is a sum of four squares. Choose a in R so that a is a positive element of R of infinite height in *Z. Then since a is infinite in *Z, a − 1 is positive. Thus , xi ∈ R for i = 1, …, 4. Now each xi must be of the form ai + ni, where ai has infinite height in *Z and ni, ∈ Z.

The notion of an almost strongly minimal theory was introduced in [1]. Such a theory is a particularly simple sort of ℵ1-categorical theory. In [1] we characterized this simplicity in terms of the Stone space of models of T. Here, we characterize almost strongly minimal theories which are not ℵ0-categorical in terms of D. M. R. Park's notion [4] of a theory with the strong elementary intersection property. In addition we prove a useful sufficient condition for an elementary theory to be an almost strongly minimal theory. Our notation is from [1] but this paper is independent of the results proved there. We do assume familiarity with §1 and §2 of [2].

In [4], Park defines a theory T to have the strong elementary intersection property (s.e.i.p.) if for each model C of T and each pair of elementary submodels of C either is an elementary submodel of C. T has the nontrivial strong elementary intersection property (n.s.e.i.p.) if for each triple C, as above Park proves the following two statements equivalent:

Let N be the set of natural numbers. If A ⊆ N, let [A]n denote the class of all n-element subsets of A. If P is a partition of [N]n into finitely many classes C1, …, Cp, let H(P) denote the class of those infinite sets A ⊆ N such that [A]n ⊆ Ci for some i. Ramsey's theorem [8, Theorem A] asserts that H(P) is nonempty for any such partition P. Our purpose here is to study what can be said about H(P) when P is recursive, i.e. each Ci, is recursive under a suitable coding of [N]n. We show that if P is such a recursive partition of [N]n, then H(P) contains a set which is Πn0 in the arithmetical hierarchy. In the other direction we prove that for each n ≥ 2 there is a recursive partition P of [N]n into two classes such that H(P) contains no Σn0 set. These results answer a question raised by Specker [12].

A basic partition is a partition of [N]2 into two classes. In §§2, 3, and 4 we concentrate on basic partitions and in so doing prepare the way for the general results mentioned above. These are proved in §5. Our “positive” results are obtained by effectivizing proofs of Ramsey's theorem which differ from the original proof in [8]. We present these proofs (of which one is a generalization of the other) in §§4 and 5 in order to clarify the motivation of the effective versions.

In this paper we show that in Zermelo-Fraenkel set theory (ZF) sets of reals are determinate.

Before proceeding to the proof it will be helpful to consider some previous work in this area. The first major result was obtained by Gale and Stewart [3] who showed that in ZF open games are determinate. This was then successively improved by Wolfe [4] to (and so of course ) and then by Morton Davis [1] to . The results of Morton Davis further showed that countable unions of sufficiently ‘simple’ determinate sets are also determinate. At this time, however, sets did not appear sufficiently simple for this method to be applied in order to get determinacy.

The next major advance was made by D. A. Martin who showed, using indiscernibles, that with large cardinal assumptions games are equivalent to certain open games (i.e., player I (II) has a winning strategy for the game iff I (II) has a winning strategy for the open game). Thus, by the Gale–Stewart result, games are determinate. Martin's result also showed that under these large cardinal assumptions sets are sufficiently simple for the Morton Davis method to be applied to them.

In [1] the notions of strongly minimal formula and algebraic closure were applied to the study of ℵ1-categorical theories. In this paper we study a particularly simple class of ℵ1-categorical theories. We characterize this class in terms of the analysis of the Stone space of models of T given by Morley [3].

We assume familiarity with [1] and [3], but for convenience we list the principal results and definitions from those papers which are used here. Our notation is the same as in [1] with the following exceptions.

We deal with a countable first order language L. We may extend the language L in several ways. If is an L-structure, there is a natural extension of L obtained by adjoining to L a constant a for each (the universe of ). For each sentence A(a1, …, an) ∈ L(A) we say satisfies A(a1, …, an) and write if in Shoenfield's notation If is an L-structure and X is a subset of , then L(X) is the language obtained by adjoining to L a name x for each is the natural expansion of to an L(X)-structure. A structure is an inessential expansion [4, p. 141] of an L-structure if for some .

It will be proven that a set of sentences of infinitary logic is satisfiable iff it is proof theoretically consistent. Since this theorem is known to be false, it must be quickly added that an extended notion of model is being used; truth values may be taken from an arbitrary complete Boolean algebra. We shall give a Henkin style proof of this result which generalizes easily to Boolean valued sets of sentences.

For each infinite candinal number κ the language Lκ is built up from a set of relation symbols together with a constant symbol cα and a variable υα for each α in κ. It contains atomic formulas and is closed under the following rules:

(1) If Γ is a set of formulas of power < κ ∧ Γ is a set of formulas.

(2) If φ is a formula, ¬ φ is also.

(3) If φ is a formula and A Is a subset of κ of power < κ then Aφ is a formula.

∧Γ is meant to be the conjunction of all the formulas in Γ, while Aφ is the universal quantification of all the variables υα for α in A. We let C denote the set of constant symbols in Lκ, the parameter κ must be discovered from the context.

A model is identified with its truth function. Thus a model is a function mapping the sentences of Lκ into a complete Boolean algebra which satisfies the following conditions:

It is well known that iteration of any number-theoretic function f, which grows at least exponentially, produces a new function f′ such that f is elementary-recursive in f′ (in the Csillag-Kalmar sense), but not conversely (since f′ majorizes every function elementary-recursive in f). This device was first used by Grzegorczyk [3] in the construction of a properly expanding hierarchy {ℰn: n = 0, 1, 2, …} which provided a classification of the primitive recursive functions. More recently it was shown in [7] how, by iterating at successor stages and diagonalizing over fundamental sequences at limit stages, the Grzegorczyk hierarchy can be extended through Cantor's second number-class. A problem which immediately arises is that of classifying all recursive functions, and an answer to this problem is to be found in the general results of Feferman [1]. These results show that although hierarchies of various types (including the above extensions of Grzegorczyk's hierarchy) can be produced, which range over initial segments of the constructive ordinals and which do provide complete classifications of the recursive functions, these cannot be regarded as classifications “from below”, since the method of assigning fundamental sequences at limit stages must be highly noneffective. We therefore adopt the more modest aim here (as in [7], [12], [14]) of characterising certain well-known (effectively generated) subclasses of the recursive functions, by means of hierarchies generated in a natural manner, “from below”.

This paper is devoted to a description of the way in which ultraproducts can be used in proofs of various well-known Σ1-compactness theorems for infinitary languages ℒA associated with admissible sets A; the method generalises the ultra-product proof of compactness for finitary languages.

The compactness theorems we consider are (§2) the Barwise Compactness Theorem for ℒA when A is countable admissible [1], and (§3) the Cofinality (ω) Compactness Theorem of Barwise and Karp [2] and [4]. Our proof of the Barwise theorem unfortunately has the defect that it relies heavily on the Completeness Theorem for ℒA. This defect has, however, been avoided in the case of the Cf(ω) Compactness Theorem, so we have a purely model-theoretic proof.

A relational structure of cardinality ℵ0 is called homogeneous by Fraissé [1] if each isomorphism between finite substructures of can be extended to an automorphism of . In §1 of this paper it is shown that there are isomorphism types of such structures for the first order language L0 with a single (binary) relation symbol, answering a question raised by Fraissé. In fact, as is shown in §2, a family of nonisomorphic homogeneous structures for L0 can be constructed, each member of which satisfies the following conditions (where U is the homogeneous, ℵ0-universal graph, the structure of which is considered in [4]):

(i) The relation R of is asymmetric (R ∩ R−1 = ∅);

(ii) If A is the domain of and S is the symmetric relation R ∪ R−1, then (A, S) is isomorphic to U. That is, each may be regarded as the result of assigning a unique direction to each edge of the graph U.

Let T0 be the first order theory of all homogeneous structures for L0 which have cardinality ℵ0. In §3 (which can be read independently of §2) it is shown that T0 has complete extensions (in L0), each of which is ℵ0-categorical. Moreover, among the complete extensions of T0 are theories of arbitrary (preassigned) degree of unsolvability. In particular, there exists an undecidable, ℵ0-categorieal theory in L0, which answers a question raised by Grzegorczyk [2], [3].

It follows from Theorem 6 of [3] that there are ℵ0-categorical theories of partial orderings which have arbitrarily high degrees of unsolvability. This is in sharp contrast to the situation for linear orderings, which were the motivation for Fraissé's early work. Indeed, as is shown in [10], every ℵ0-categorical theory of a linear ordering is finitely axiomatizable. (W. Glassmire [12] has independently shown the existence of theories in L0 which are all ℵ0-categorical, and C. Ash [13] has independently shown that such theories exist with arbitrary degree of unsolvability.)

Bachmann, in [2] shows how certain ordinals <Ω(Ω = Ω1 where Ωξ is the (1 + ξ)th infinite initial ordinal) may be described from below using suitable descriptions of ordinals <Ω2. The aim of this paper is to consider another approach to describing ordinal <Ω and compare it with the Bachmann method. Our approach will use functionals of transfinite type based on Ω.

The Bachmann method consists in denning a hierarchy of normal functions ϕδ: Ω → Ω (i.e. continuous and strictly increasing) for δ ≤ η0 < Ω2, starting with ϕ0(λ) = ω1 + λ. The definition of depends on a suitable description of the ordinals ≤ η0. This is obtained by defining a hierarchy 〈Fδ ∣ δ ≤ Ω2〉 of normal functions Fδ: Ω2 → Ω2 analogously to the definition of the initial segment 〈ϕδ ∣ δ ≤ Ω〉 of . The ordinal η0 is .

Note. Our description of Bachmann's hierarchies will differ slightly from those in Bachmann's paper. Let and denote the hierarchies in [2]. Then as Bachmann's normal functions are not defined at 0 we let for λ, δ < Ω2. Bachmann defines for 0 < λ < Ω2 but it seems more natural to omit this so that we let . The situation is analogous for and leads to the following definitions:

where n < ω and ξ is a limit number of cofinality Ω, and

One of the major problems of model theory is the spectrum problem, i.e. the development of structure theorems for the spectrum of models of a given theory. I hope that this paper will make a (small) contribution to the solution of this problem.

Broadly speaking, in this paper we take a fixed (but arbitrary) theory T and consider a particular class ℰ of models of T. The structures in ℰ (which are known as existentially closed structures) are connected with the model complete extensions of T. These structures have already appeared several times in the literature.

In §1 we survey the notation and terminology that we use, as well as the well known facts that we require. We also consider several concepts which are not new here but which may not be well known.

In §2 we define, and give the basic results concerning existentially closed structures. For most theories, T, the class ℰ is not elementary and hence is not directly amenable to a model theoretic study. Because of this we consider a smaller class of structures—the uniformly existentially closed structures. These are discussed in §3.

In §4 we look at model complete theories via existentially closed structures. This section is essentially a refinement of parts of [6].

In §5 we look at model companions of theories via existentially closed structures.

Finally, in §6 we make some remarks on the relevance of existentially closed structures to the spectrum problem.