Let T be a (countable, complete, quantifier eliminable) ω-stable theory; an analysis of T, and consequently a classification of ω-stable theories, can be done by looking at the Boolean algebras B(M) of definable subsets of its countable models M (as usual, we often confuse a definable subset of M with the class of formulas defining it). If M ⊨ T, ∣M∣ = ℵ0, then, for every LM-formula ϕ(v) and for every ordinal α, we define a relation

(CB = Cantor-Bendixson, of course) by induction on α:

CB-rank ϕ(v) ≥ 0 if ϕ(M) ≠ ∅

CB-rank ϕ(v) ≥ λ for λ a limit ordinal, if CB-rank ϕ(v) ≥ for all v < λ;

CB-rank ϕ(v)≥ α + 1 if, for all n ∈ ω,

(*) there are LM-formulas ϕ0(v), …, ϕn − 1(v) such that

It is well known that the ω-stability of T implies that, for every consistent LM-formula ϕ(v), there is exactly one ordinal α < ω1 such that CB-rank ϕ(v) ≥ α and CB-rank ϕ(v)≱α + 1. Therefore we define:

CB-rank ϕ(v) = α

CB-degree ϕ(v) = d if d is the maximal n ∈ ω satisfying (*); and

CB-type ϕ(v) = (α, d).

The set Λ of isols was extensively studied by Dekker and Myhill in [1]. Subsequently, Nerode [3] developed the theory of Λ(A), the set of isols relative to some recursively closed set of functions A.

One of the main areas of interest of [1] was the natural partial order ≤ on Λ. In this paper we will examine some of the properties of ≤A on Λ(A). We use the following notations: ∣A∣ is the cardinality of the set A, ⊃ denotes strict inclusion, (a) is the power set of the set a, c is the cardinality of the continuum, and ω = {0, 1, 2, …}. The terms A-isol, A-immune, A-r.e., A-incomparable, etc. all refer to the usual meaning of these words, only taken in the context of the recursively closed set A. ReqA(a) is the A-r.e.t. of which a is a representative. By identifying a finite natural number with the A-r.e.t. consisting of sets of a given finite cardinality we see that ω ⊆ Λ(A); Λ(A) is said to be nontrivial iff ω ⊃ Λ(A). The three results proven in this paper are:

1. Theorem 1. If Λ(A) is nontrivial, then ∣Λ(A)∣ = c.

2. Theorem 2. If∣A∣ < c, then Λ(A) is nontrivial.

3. Theorem 3. If ∣A∣ < c and ∣⊿∣ < c and ⊿ ⊆ Λ(A) − ω, then there is aΓ ⊆ Λ(A) − ω such that:

• (a) ∣Γ∣ = c.

• (b) Every member of Γ is A-incomparable with every member of Δ.

• (c) Any two distinct members of Γ are A-incomparable.

Let S be the set of those α ∈ ω2 that have cofinality ω1. It is consistent relative to a measurable that the nonempty player wins the pressing down game of length ω1, but not the Banach-Mazur game of length ω + 1 (both games starting with S).

At the end of his paper [2], Silver shows how methods developed by Jensen and Solovay in order to prove results about the constructible universe L may be adapted to prove corresponding results for the universe L[μ], where μ is a normal measure on some uncountable cardinal ρ. In this paper we pursue this in greater depth. Jensen proved, in fact, much stronger results than those considered in [2], and we shall show that all of these carry over from L to L[μ], More precisely, we show that if V = L[μ] is assumed, then for any regular uncountable cardinal κ and any uncountable λ < κ, + (κ, λ) holds, and that + (κ, κ) holds just in the case κ is not ineffable. This result was proved to hold in L by Jensen, who first formulated the principles + (κ, λ).

Our proof differs in detail from Jensen's, and at one point (in choosing the set B of + ) differs fundamentally from his argument. However, the fact remains that our argument is modelled closely upon Jensen's, and it should be made clear that in many parts it is a straightforward adaption of his proof to the L[μ] situation. It is regrettable that, at the time of our writing this, Jensen's proof still only exists in the rough, handwritten form of [1]; so we shall give our argument in some detail, even those parts which are merely “translations” of Jensen's original arguments.

It is unprovable that every complete subalgebra of a countably closed complete Boolean algebra is countably closed.

In classical first-order predicate logic CL1 (without equality) only tautologies and antitautologies satisfy nontautological schemas. I.e., if F[p, Q] is a nontautological formula (fl) in the predicate letters shown, with p prepositional, then ⊬ F[K, Q] for any sentence K not containing some Q ∈ Q, unless ⊢ K or ⊢ ¬K. This is an easy consequence of the Completeness Theorem. Clearly, the analogous statement fails for intuitionistic predicate logic IL1; already when Q is empty: (i) ¬¬ K for, e.g., K ≡ p ∨ ¬p; (ii) ¬¬K → K for, e.g., K ≡ ¬p.

We get consistency results on I(λ, T, T) under the assumption that D(T) has cardinality > ∣T∣. We get positive results and consistency results on IE(λ, T 1, T).

The interest is model-theoretic, but the content is mostly set-theoretic: in Theorems 1–3, combinatorial; in Theorems 4–7 and 11(2), to prove consistency of counterexamples we concentrate on forcing arguments; and in Theorems 8–10 and 11(1), combinatorics for counterexamples; the rest are discussion and problems. In particular:

(A) By Theorems 1 and 2, if T ⊆ T 1 are first order countable, T complete stable but ℵ0-unstable, λ > ℵ0, and ∣D(T)∣ > ℵ0, then IE(λ, T 1, T) > Min{2 λ , ℶ2}.

(B) By Theorems 4,5,6 of this paper, if e.g. V = L, then in some generic extension of V not collapsing cardinals, for some first order T ⊆ T 1, ∣T∣ = ℵ0, ∣T 1∣ = ℵ1, ∣D(T)∣ = ℵ2 and IE(ℵ2, T1, T) = 1.

This paper (specifically the ZFC results) is continued in the very interesting work of Baldwin on diversity classes [Bl]. Some more advances can be found in the new version of [Sh300] (see Chapter III, mainly §7); they confirm 0.1, 0.2 and 14(1), 14(2).

Let L0 be a language on ℕ consisting of 0, 1, +, ∸, ·, ⌊½a⌋, ∣a∣, #, ∧(a,b), ∨(a,b), ¬(a), ≤ (a,b), and μx ≤ ∣s∣t(x). Here μx ≤ ∣s∣t(x) is the smallest number x ≤ ∣s∣ satisfying t(x) > 0 and 0 if there exist no such x and we stipulate that if s and t(a) are terms in Lo, then μx ≤ ∣s∣t(x) is also a term in Lo. The defining axioms of functions ∧(a,b), ∨(a,b), ¬(a), ≤ (a,b) are as follows:

Let L a language on ℕ with only predicate constant = and L0 ⊆ L. Let f (b, a1,…,am) be a function for ℕm+1 into ℕ. We say “f is weakly expressed by terms t1(b, a1,…, am),…, tr(b, a1,…, am) in L” if for every b, a1,…, am ∈ ℕ, f (b, a1,…,am) is equal to one of ti(b, a1, …, am). The critical number of b in f with respect to L is the minimum number n such that whenever f(b, a1,…, an) is weakly expressed by terms t1(b, a1, …, an),…, the number of occurrences of b in some ti(b, a1,…, an) is at least n.

As is defined in [1], a function f is defined by a limited iteration from g and h with respect to L iff the following holds: Let τ be defined as

with the condition ; and is defined by

where and are terms in L. We say “f is defined by a short limited iteration from g and h” if is defined by

where τ, s, t are the same as above satisfying the condition .

Here we prove the following:

Theorem. For every N ≤ ω there is a complete theory Tn having exactly n nonisomorphic rigid models and no uncountable rigid models. Moreover, each non-rigid model admits a nontrivial automorphism.

The Tn are theories in the first-order predicate calculus and a rigid structure is a structure with no nontrivial endomorphisms, i.e., the only endomorphism of the structure into itself is the identity. The theorem answers a question of A. Ehrenfeucht.

For the most part we use standard model theoretic notation with Th denoting the set of sentences true in and meaning . A complete set of sentences is one of the form Th for some . The universe of a structure may be denoted by ∣∣. An n-ary relation on X is a set of n tuples (x0, …, xn−1) with each xi ∈ X. All the structures encounted here will be relational. If P is an n-ary relation then P ↾ Y, the restriction of P to Y, is {(x0, …, xn−1): (x0, …, xn−1) ∈ P and x0, …, xn−1Y}.

We show that it is not possible to construct a Fraenkel-Mostowski model in which the axiom of choice for well-ordered families of sets and the axiom of choice for sets of well-orderable sets are both true, but the axiom of choice is false.