We prove in this paper that the -system, an axiom system for set theory suggested for investigation by Takeuti in [2], is inconsistent. We also show that this system without the ω-rule is consistent if Zermelo-Fraenkel set theory with the axiom of choice and an axiom due to Reinhardt and Silver is consistent. The -system is an effort to strengthen Bernays-Gödel set theory by adding a reflection principle.

In addition to the standard notation of set theory, we write X″{x) to mean {y∣〈x, y〉 Є X}.

Omitting-types theorems have been useful in model theory to construct models with special characteristics. For instance, one method of proving the ω-completeness theorem of Henkin [10] and Orey [20] involves constructing a model that omits the type {x ≠ 0, x ≠ 1, x ≠ 2,···} (i.e., {x ≠ 0, x ≠ 1, x ≠ 2,···} is not satisfiable in the model). Our purpose in this paper is to illustrate uses of omitting-types theorems in recursion theory. The Gandy-Kreisel-Tait Theorem [7] is the most well-known example. This theorem characterizes the class of hyperarithmetical sets as the intersection of all ω-models of analysis (the so-called hard core of analysis). The usual way to prove that a nonhyperarithmetical set does not belong to the hard core is to construct an ω-model of analysis that omits the type representing the set (Application 1). We will find basis results for and s — sets that are stronger than results previously known (Applications 2 and 3). The question of how far the natural hierarchy of hyperjumps extends was first settled by a forcing argument (Sacks) and subsequently by a compactness argument (Kripke, Richter). Another problem solved by a forcing argument (Sacks) and then by a compactness argument (Friedman-Jensen) was the characterization of the countable admissible ordinals as the relativized ω1's. Using omitting-types technique, we will supply a third kind of proof of these results (Applications 4 and 5). S. Simpson made a significant contribution in simplifying the proof of the latter result, with the interesting side effect that Friedman's result on ordinals in models of set theory is immediate (Application 6). One approach to abstract recursiveness and hyperarithmeticity on a countable set is to tenuously identify the set with the natural numbers. This approach is equivalent to other approaches to abstract recursion (Application 7). This last result may also be proved by a forcing method.

Let Δ be a set of axioms of a theory Tc(Δ) of classical predicate calculus (CPC); Δ may also be considered as a set of axioms of a theory TH(Δ) of Heyting's predicate calculus (HPC). Our aim is to investigate the decision problem of TH(Δ) in HPC for various known theories Δ of CPC.

Theorem I(a) of §1 states that if Δ is a finitely axiomatizable and undecidable theory of CPC then TH(Δ) is undecidable in HPC. Furthermore, the relations between theorems of HPC are more complicated and so two CPC-equivalent axiomatizations of the same theory may give rise to two different HPC theories, in fact, one decidable and the other not.

Semantically, the Kripke models (for which HPC is complete) are partially ordered families of classical models. Thus a formula expresses a property of a family of classical models (i.e. of a Kripke model). A theory Θ expresses a set of such properties. It may happen that a class of Kripke models defined by a set of formulas Θ is also definable in CPC (in a possibly richer language) by a CPC-theory Θ′! This establishes a connection between the decision problem of Θ in HPC and that of Θ′ in CPC. In particular if Θ′ is undecidable, so is Θ. Theorems II and III of §1 give sufficient conditions on Θ to be such that the corresponding Θ′ is undecidable. Θ′ is shown undecidable by interpreting the CPC theory of a reflexive and symmetric relation in Θ′.

In this paper we deal with infinitary languages which allow arbitrary infinite disjunctions and conjunctions, but finite strings of quantifiers only. Furthermore, we shall assume that the primitive predicate symbols are finitary. (Cf. [K] and §2 for further information and unexplained notations.)

Our main result shows that every “reasonable” language of this type is, in a certain sense, reducible to one of the same type which allows countable disjunctions and conjunctions only. More precisely if we let θ be the first measurable cardinal and μ ≤ θ, we have the following result partially announced in [R1]:

Theorem. Every theory in a Lμω language is equivalent to some theory in a Lω1ω language in the sense that atomic formulas of one language can be mapped into formulas of the other in such a way that, for every set, these maps establish a bijective correspondence between their models having that set as a universe.

The paper is divided into three sections. In the first, we derive the main result from a theorem of Sikorski on ω-homomorphisms of μ-complete boolean algebras. In the second, we give a refined version of Sikorski's theorem from which cardinality bounds can be given for the Lω1ω theories obtained by our reduction. In the last, we use a Skolem ultrapower construction to give examples for which these bounds are actually attained. As a corollary, we obtain the converse of our main result.

Let ⊥, →, and □ be primitive, and let us have a countable supply of propositional letters. By a (modal) logic we understand a proper subset of the set of all formulas containing every tautology and being closed under modus ponens and substitution. A logic is regular if it contains every instance of □A ∧ □B ↔ □(A ∧ B) and is closed under the rule

A regular logic is normal if it contains □⊤. The smallest regular logic we denote by C (the same as Lemmon's C2), the smallest normal one by K. If L and L' are logics and L ⊆ L′, then L is a sublogic of L', and L' is an extension of L; properly so if L ≠ L'. A logic is quasi-regular (respectively, quasi-normal) if it is an extension of C (respectively, K).

A logic is Post complete if it has no proper extension. The Post number, denoted by p(L), is the number of Post complete extensions of L. Thanks to Lindenbaum, we know that

There is an obvious upper bound, too:

Furthermore,

.

In this paper we show how nonrecursive combinatorial functions can be used to obtain another proof of the compactness Theorem 3.1 of [6]. Our method is closely related to the argument used to show that a countable ultraproduct is ℵ1-saturated. What we do is to diagonalize in the most obvious way. The main difficulty with this approach is that the resulting diagonal function need not be recursive. Just to give an idea of how bad nonrecursive combinatorial functions are, we mention that by using frames (cf. [5]) they do not extend to Λ, and that by using normal combinatorial operators (cf. [4]) they do extend to Λ, map Λ into Λ, but in general, composition of such functions does not commute with their extension. We take care of this problem by constructing a large class of isols with respect to which the diagonal function is well behaved. The advantage of our method is that it provides the investigator with a natural and intuitive way of constructing counterexamples in his own research area.

In [4] Alonzo Church introduced an elegant and expressive formulation of type theory with λ-conversion. In [8] Henkin introduced the concept of a general model for this system, such that a sentence A is a theorem if and only if it is true in all general models. The crucial clause in Henkin's definition of a general model ℳ is that for each assignment φ of values in ℳ to variables and for each wff A, there must be an appropriate value of A in ℳ. Hintikka points out in [10, p. 3] that this constitutes a rather strong requirement concerning the structure of a general model. Henkin draws attention to the problem of constructing nonstandard models for the theory of types in [9, p. 324].

We shall use a simple idea of combinatory logic to find a characterization of general models which does not directly refer to wffs, and which is easier to work with in certain contexts. This characterization can be applied, with appropriate minor and obvious modifications, to a variety of formulations of type theory with λ-conversion. We shall be concerned with a language ℒ with extensionality in which there is no description or selection operator, and in which (for convenience) the sole primitive logical constants are the equality symbols Qoαα for each type α.

In [2] “recursive frames” were introduced as a means of extending relations R on the nonnegative integers to relations RΛ on the isols. In [1], this extension procedure was generalized by the introduction of “partial recursive frames”; the resulting extended relation on the isols was called RΛ. It was shown in [1] that the two extension procedures agree for recursive relations R, while RΛ ⊇ RΛ if R is . The case when R is , nonrecursive was left open. We show in this note that the extension procedures in fact agree for all relations R.

In the following, the notation and terminology is that of [1] and [2].

Theorem. If R ⊆ XκQ is a recursively enumerable (r.e.) relation, then RΛ = RΛ.

Proof. Clearly RΛ ⊆ RΛ, since every recursive frame is partial recursive. To prove RΛ ⊆ RΛ, we give a uniform effective method for expanding any partial recursiveR-frame F to a recursiveR-frame G such that F ⊆ G, so that So let F be a (nonempty) partial recursive R-frame, with CF(α) generated by . Let Rn denote the result of performing n steps in a fixed recursive enumeration of R. If g(α) is a partial recursive function, “g(α) is defined in n steps” means that in whichever coding of recursive computations is being used, a terminating computation for g with argument α has length ≤ n.

If Σ is the class of all fields and Σ* is the class of all algebraically closed fields, then it is well known that Σ* is characterized by the following properties:

(i) Σ* is the class of models of some first order theory K*.

(ii) If m1m2 are in Σ* and m1 ⊆ m2 then m1 ≺ m2 (m1 is an elementary substructure of m2, i.e. any first order sentence true in m1 is true in m2).

(iii) If m1 is in Σ then there is a structure m2 in Σ* such that m1 ⊆ m2.

If Σ is some other class of models of a first order theory K and a subclass Σ* of Σ exists satisfying (i)–(iii) then Σ* is uniquely determined and K* (which is unique up to logical equivalence) is called the model-companion of K. This notion is a generalization of the fundamental notion of model-completion introduced and extensively studied by A. Robinson [6], When the model-companion exists it provides the basis for a satisfactory treatment of the notion of an algebraically closed model of K.

Recently A. Robinson has developed a more general formulation of the notion of “algebraically closed” structures in Σ, which is applicable to any inductive elementary class Σ of structures (by elementary we always mean ECΔ). Condition (i) must be weakened to

(i′) Σ* is closed under elementary substructure (i.e. if m1 is in Σ* and m2 ≺ m1 then m2 is in Σ*).

It is well known that equality is definable in type theory. Thus, in the language of [2], the equality relation between elements of type α is definable as , i.e., xα = yα iff every set which contains xα also contains yα. However, in a nonstandard model of type theory, the sets may be so sparse that the wff above does not denote the true equality relation. We shall use this observation to construct a general model in the sense of [2] in which the Axiom of Extensionality is not valid. Thus Theorem 2 of [2] is technically incorrect. However, it is easy to remedy the situation by slightly modifying the definition of general model.

Our construction will show that the Axiom Schema of Extensionality is independent even if one takes as an axiom schema.

We shall assume familiarity with, and use the notation of, [2] and §§2–3 of [1].

Let A2 be the axiomatic system of second order arithmetic as described in [2]. One of the models of A2 is the “principal model” Mpr consisting of all integers and all sets of integers. Obviously there exist many denumerable ω-models elementarily equivalent to Mpr and we shall deal in this paper with some questions pertaining to this family which we denote by .

In §1 we define a rather natural relation ε between two denumerable families of sets of integers. From the upward Skolem-Löwenheim theorem it follows easily that there exists a family ordered by ε in the type ω1, but it is not immediately obvious whether there exist a subfamily of not well-ordered by ε. In the present paper we construct such a family of type η. ω1 where η is the order type of rationals and indicate some applications to hyperdegrees.

We adopt the terminology and notation of [2], with the only change that we adjoin to the language of A2 the constants ν0, ν1, … for the consecutive numerals 0, 1, 2, … and axioms which characterise them:

Also we modify the axioms of A2 given in [2] by prefixing them by general quantifiers bounded either to S or to N.

We have come to believe that propositional modal logic (with the usual relational semantics) must be understood as a rather strong fragment of classical second-order predicate logic. (The interpretation of propositional modal logic in second-order predicate logic is well known; see e.g. [2, §1].) “Strong” refers of course to the expressive power of the languages, not to the deductive power of formal systems. By “rather strong” we mean sufficiently strong that theorems about first-order logic which fail for second-order logic usually fail even for propositional modal logic. Some evidence for this belief is contained in [2] and [3]. In the former is exhibited a finitely axiomatized consistent tense logic having no relational models, and the latter presents a finitely axiomatized modal logic between T and S4, such that □p → □2p is valid in all relational models of the logic but is not a thesis of the logic. The result of [2] is strong evidence that bimodal logic is essentially second-order, but that of [3] does not eliminate the possibility that unimodal logic only appears to be incomplete because we have not adopted sufficiently powerful rules of inference. In the present paper we present stronger evidence of the essentially second-order nature of unimodal logic.

Fraenkel-Mostowski models are a particularly simple and conceptual tool for proving consistency results involving the axiom of choice, AC. These models satisfy the theory, FM, of a well founded universe of sets built from a ground set of individuals. Zermelo-Fraenkel set theory, ZF, is the extension of FM in which the set of individuals is assumed to be empty. In this paper we show that there is a large class of statements whose consistency with ZF can be proven directly by means of a Fraenkel-Mostowski model.

A statement, Φ, of set theory is said to be transferable if there is a metatheorem: If Φ is true in a Fraenkel-Mostowski model then Φ is consistent with ZF. Jech and Sochor introduced, in [12], the class of boundable statements and proved them to be transferable. Most existential contradictions of AC are boundable. It remains to find criteria under which Ψ ∧ Φ is transferable where Ψ is a universal consequence of AC and Φ is an existential contradiction of AC. To this end we give two classes of statements. Each class is closed under conjunction, contains the boundable statements, and contains a number of universal consequences of AC. Nearly every Fraenkel-Mostowski consistency in the literature falls into one of these two classes.

In §2 we give two generalizations of the boundable statements. In §§3 and 4 the classes of transferable statements are discussed. In §5 we discuss the transfer problem and prove a metatheorem concerning nontransferable statements.

There is a fairly simple algebraic property that distinguishes isols from cosimple isols.

If two nonstandard models of complete arithmetic are elementarily embedded in a third, then their intersection may be considerably smaller than either of them; indeed, the intersection may be only the standard model. For example, if D and E are nonprincipal ultrafilters on ω, then the nonstandard models D-prod and E-prod (where is the standard model) have canonical elementary embeddings into D-prod (E-prod , and the intersection of their images is easily seen to be the (canonical image of the) standard model. In this paper, we shall prove that, under certain conditions, this phenomenon will not occur. Our main result (Theorem 3) is that the intersection of countably many pairwise cofinal models is itself cofinal with these models, provided that at least one of them is generated by a single element. (Precise definitions will be given below.)

The theorems in this paper were first formulated in terms of ultrafilters, then rephrased (using the methods of Chapter III of [1]) as statements about ultra-powers of , and finally generalized to their present form. Since the theorems and their proofs are now entirely model-theoretic, they are presented here separately from the study of ultrafilters in which they originated. That study, including applications of the present results, will appear in [2].

Let L be the first-order language whose n-place relation symbols are all the relations R ⊆; ωn and whose n-place function symbols are all the functions f: ωn → ω. Let be the standard model for L; its universe is ω and every nonlogical symbol of L denotes itself. Let be an elementary extension of . The relation (or function) denoted by R (or f) in will be called *R (or *f).

Consider the Löwenheim-Skolem theorem in the form: If a theory in a countable first-order language has a model, then it has a countable model. As is well known, this theorem becomes false if one omits the hypothesis that the language be countable, for one then has the following trivial counterexample.

Example 1. Let the language have uncountably many constants, and let the theory say that they are unequal.

To motivate some of our future definitions and to introduce some notation, we present another, less trivial, counterexample.

Example 2. Let L0 be the language whose n-place predicate (resp. function) symbols are all the n-place predicates (resp. functions) on the set ω of natural numbers. Let be the standard model for L0; we use the usual notation Th() for its complete theory. Add to L0 a new constant e, and add to Th() an axiom schema saying that e is infinite. By the compactness theorem, the resulting theory T has models. However, none of its models are countable. Although this fact is well known, we sketch a proof in order to refer to it later.

By [5, p. 81], there is a family {Aα ∣ < α < c} of infinite subsets of ω, the intersection of any two of which is finite.

If T is a complete first-order totally transcendental theory then over every T-structure A there is a prime model unique up to isomorphism over A. Moreover M is a prime model over A iff: (1) every finite sequence from M realizes an isolated type over A, and (2) there is no uncountable indiscernible set over A in M.

The existence of prime models was proved by Morley [3] and their uniqueness for countable A by Vaught [9]. Sacks asked (see Chang and Keisler [1, question 25]) whether the prime model is unique. After proving this I heard Ressayre had proved that every two strictly prime models over any T-structure A are isomorphic, by a strikingly simple proof. From this follows

If T is totally transcendental, M a strictly prime model over A then every elementary permutation of A can be extended to an automorphism of M. (The existence of M follows by [3].)

By our results this holds for any prime model. On the other hand Ressayre's result applies to more theories. For more information see [6, §0A]. A conclusion of our theorem is the uniqueness of the prime differentially closed field over a differential field. See Blum [8] for the total transcendency of the theory of differentially closed fields.

We can note that the prime model M over A is minimal over A iff in M there is no indiscernible set over A (which is infinite).