Suppose M is a countable standard transitive model of set theory. P. J. Cohen [2] showed that if κ is an infinite cardinal of M then there is a one-to-one function Fκ from κ into the set of real numbers such that M[Fκ] is a model of set theory with the same cardinals as M.

If Tκ is the range of Fκ then Cohen also showed [2] that M[Tκ] fails to satisfy the axiom of choice. We will give an easy proof of this fact.

If κ, λ are infinite we will also show that M[Tκ] is elementarily equivalent to M[Tλ] and that (] in M[Fλ]) is elementarily equivalent to (] in M[FK]).

Finally we show that there may be an N ∈ M[GK] which is a standard model of set theory (without the axiom of choice) and which has, from the viewpoint of M[GK], more real numbers than ordinals.

We write ZFC and ZF for Zermelo-Fraenkel set theory, respectively with and without the axiom of choice (AC). GBC is Gödel-Bernays' set theory with AC. DC and ACℵo are respectively the axioms of dependent choice and of countable choice defined in [6].

Lower case Greek characters (other than ω) are used as variables over ordinals. When α is an ordinal, R(α) is the set of all sets with rank less than α.

In [1] we proved the following interpolation theorem for first-order (finitary) logic:

Theorem (Scott). Let A and B be sentences. There is an -sentence C such that A → C and C → B iff whenever and are -isomorphic structures and satisfies A then satisfies B.

We show here that the Theorem holds for A and B in Lω1, ω only if we permit the interpolant C to be in L(2ω)+, ω, where (2ω)+ is the successor of 2ω.

Our language contains the usual logical symbols and the relation symbols Ri, is i ∈ J. IfI ⊆ J define an I-sentence to be a sentence containing only relations with subscripts in I. If define an -sentence to be a boolean combination of I-sentences with , i.e., a sentence consisting of I-sentences, for various I's in , joined together by ∨, ∧ and ⌝; e.g., ∀xR1(x) ∨ ∀xR2(x)is a{{1}, {2}}-sentence but ∀x(R1(x) ∨ R2(x)) is not. If is a structure let , be the structure obtained by restricting to just the relations with subscripts in I. We say that is -isomorphic to if is isomorphic to for each .

The principal aim of this paper is to establish a theorem stating, roughly, that the addition of the fan theorem and the. continuity schema to an intuitionistic system of elementary analysis results in a conservative extension with respect to arithmetical statements.

The result implies that the consistency of first order arithmetic cannot be proved by use of the fan theorem, in addition to standard elementary methods—although it was the opposite assumption which led Gentzen to withdraw the first version of his consistency proof for arithmetic (see [B]).

We must presuppose acquaintance with notation and principal results of [K, T], and with §1.6, Chapter II, and Chapter III, §4-6 of [T1]. In one respect we shall deviate from the notation in [K, T]: We shall use (n)x (instead of g(n, x)) to indicate the xth component of the sequence coded by n, if x < lth(n), 0 otherwise.

We also introduce abbreviations n ≤* m, a ≤ b which will be used frequently below:

Let be the set of recursive functions computable by machines using at most t(x) computation steps on argument x, for all but finitely many inputs x. We call t a name for the complexity class . Suppose we allow our machines to run longer, say h(x, t(x)) steps on argument x, where h is some fixed recursive function. One might expect that, for large enough h, permitting our machines to run longer by an amount h will always allow us to compute new functions, i.e., is a proper subset of . This turns out not to be the case: The “gap theorem” ([2], [3]) implies that for every recursive h there exists a recursive t such that . However, if we restrict our attention to names from a certain subclass of the recursive functions, then we can indeed uniformly increase the size of our -classes. Informally, we call a recursive function t “honest” if some machine computes t(x) in roughly t(x) steps for each argument x. (A precise definition is given in Definition 1 below.) Then according to the “compression theorem” [1], there exists a single recursive function h such that, for every honest t, is a proper subset of . Thus the phenomenon of the gap theorem is avoided by restricting attention to honest functions. It is a surprising consequence of the “honesty theorem” of McCreight and Meyer ([4], [5]) that there is no loss of generality in this restriction. Namely, for any recursive function t there is an honest recursive function t′ such that .

H. Scholz [11] defined the spectrum of a formula φ of first-order logic with equality to be the set of all natural numbers n for which φ has a model of cardinality n. He then asked for a characterization of spectra. Only partial progress has been made. Computational aspects of this problem have been worked on by Gunter Asser [1], A. Mostowski [9], and J. H. Bennett [2]. It is known that spectra include the Grzegorczyk class and are properly included in . However, no progress has been made toward establishing whether spectra properly include , or whether spectra are closed under complementation.

A possible connection with automata theory arises from the fact that contains just those sets which are accepted by deterministic linear-bounded Turing machines (Ritchie [10]). Another resemblance lies in the fact that the same two problems (closure under complement, and proper inclusion of ) have remained open for the class of context sensitive languages for several years.

In this paper we show that these similarities are not accidental—that spectra and context sensitive languages are closely related, and that their open questions are merely special cases of a family of open questions which relate to the difference (if any) between deterministic and nondeterministic time or space bounded Turing machines.

In particular we show that spectra are just those sets which are acceptable by nondeterministic Turing machines in time 2cx, where c is constant and x is the length of the input. Combining this result with results of Bennett [2], Ritchie [10], Kuroda [7], and Cook [3], we obtain the “hierarchy” of classes of sets shown in Figure 1. It is of interest to note that in all of these cases the amount of unrestricted read/write memory appears to be too small to allow diagonalization within the larger classes.

There is an analogy between concepts such as end-extension types and minimal types in the model theory of Peano arithmetic and concepts such as P-points and selective ultrafilters in the theory of ultrafilters on N. Using the notion of conservative extensions of models, we prove some theorems clarifying the relation between these pairs of analogous concepts. We also use the analogy to obtain some model-theoretic results with techniques originally used in ultrafilter theory. These results assert that every countable nonstandard model of arithmetic has a bounded minimal extension and that some types in arithmetic are not 2-isolated.

We give a direct mathematical proof of the Mathias-Silver theorem that every analytic set is Ramsey.