Categoricity Without Equality

H. Jerome Keisler and Arnold W. Miller

Abstract

We study categoricity in power for reduced models of first order logic without equality.

1 Introduction

The object of this paper is to study categoricity in power for theories in first order logic without equality. Our results will reveal some surprising differences between the model theory for logic without equality and for logic with equality.

When we consider categoricity, it is natural to identify elements which are indistinguishable from each other. We will do this by confining our attention to reduced models, that is, models M such that any pair of elements which satisfy the same formulas with parameters in M are equal. We also confine our attention to complete theories T in a countable language such that all models of T are infinite. T is said to be κ-categorical if T has exactly one reduced model of cardinality κ up to isomorphism.

The classical result about ω-categoricity for logic with equality is the Ryll-Nardzewski theorem, which says that T is ω-categorical if and only if T has only finitely many complete n-types for each finite n. This result fails for logic without equality. Another relevant result which fails for logic without equality is the Löwenheim-Skolem-Tarski theorem, that T has at least one model of every infinite cardinality. Concerning uncountable categoricity, Łoś [Ł] conjectured that if T is λ-categorical for some uncountable λ, then T is κ-categorical for every uncountable κ. The Łoś conjecture was proved for logic with equality by Morley [M]. We will show that this result also holds for logic without equality.

Some basic facts about reduced models are stated in Section 2. Section 3 contains several examples of ω-categorical theories in logic without equality which have infinitely many complete 1-types or 2-types. The reason for this different behavior is clarified in Section 4, where we see what happens to the Omitting Types Theorem in logic without equality. In Section 5 we apply the Omitting Types Theorem to study ω-categoricity and the existence of prime models in logic without equality.

Section 3 also contains examples of bounded theories, i.e. theories for which the class of cardinalities of infinite models is bounded. In Section 6 we show that there are just three possibilities: All models of T are countable, the maximum cardinality of a model of T is the continuum, or T has models of all infinite cardinalities (i.e. T is unbounded). This shows that the Hanf number of first order logic without equality is (2^{ω})^{+}. In Section 7 we show that no bounded theory is categorical in an uncountable cardinal. Finally, the Łoś conjecture for logic without equality is proved in Section 8.

We thank the National Science Foundation and the Vilas Trust Fund for support of this research.

2 Preliminaries

Throughout this paper, L will be a countable first order predicate logic without equality. In considering isomorphisms between models of logic without equality, it is natural to identify elements which are indistinguishable from each other. That is, it is natural to restrict attention to models which are reduced in the following sense (see [BP],[CDJ], [D], [DJ]).

Definition 2.1 A model M for L is said to be reduced if for any pair of elements a, b ∈ M, we have a = b if and only if for every formula θ(x, y⃗) of L,

M ⊧ ∀u⃗[θ(a, u⃗) ⇔ θ(b, u⃗)].  (1)

In general, two elements a, b ∈ M are said to be Leibniz congruent, in symbols a ≡ b, if condition (1) holds for all formulas θ of L. Thus M is reduced if and only if its Leibniz congruence relation is the equality relation on M. It is well known that for every model M for L, the quotient structure M/≡ of M modulo its Leibniz congruence is a reduced model, and the mapping a ↦ a/≡ preserves the truth values of all formulas of L. Moreover, if condition (1) holds for all atomic formulas θ, then it holds for all formulas θ. We are primarily interested in the case that the Leibniz congruence relation is not definable in M.

It follows from the preceding remarks that the compactness and (downward) Löwenheim-Skolem theorems hold for reduced models. That is,

Proposition 2.2 If Γ is a set of sentences of L and every finite subset of Γ has a model, then Γ has a reduced model of cardinality at most ω. □

For each n, the set of all complete types in a theory T with at most n free variables (i.e. the Stone space of T in n variables) is denoted by S_{n}(T). It is a compact Hausdorff space whose clopen sets are determined by formulas in n free variables.

Given a set X ⊆ M, we let L_{X} be the expansion of L obtained by adding a new constant symbol for each a ∈ X, and let M_{X} be the corresponding expansion of M. As usual, we say that M is κ-saturated if for each X ⊆ M of cardinality less than κ, every 1-type in T h(M_{X}) is satisfiable in M_{X}. The following existence theorem is proved exactly as in the case of logic with equality.

Proposition 2.3 (i) For each infinite cardinal κ, every consistent theory in L has a κ^{+}-saturated reduced model of cardinality at most 2^{κ}.

(ii) A complete theory T has an at most countable ω-saturated reduced model if and only if S_{n}(T) is finite or countable for each n. □

We shall say that a theory T in L is κ-categorical if it has exactly one reduced model of cardinality κ up to isomorphism.

Reduced structures can also be viewed as structures which omit a certain set of formulas in logic with equality. Given a logic L without equality, we let L^{=} be the corresponding logic with equality, obtained by adding the equality symbol to L. Every structure for L, whether or not it is reduced, is also a structure for L^{=} with the natural interpretation of =. Thus a structure M is reduced if and only if it omits the following set Λ(x, y) of formulas of L^{=}:

Λ(x, y) = {¬x = y} ∪ {∀u⃗[θ(x, u⃗) ⇔ θ(y, u⃗)] : θ is in L}.

We remark that two reduced structures are isomorphic in the sense of L if and only if they are isomorphic in the sense of L^{=}. However, as we shall see in the next section, there are reduced structures which are elementarily equivalent in the sense of L but not in the sense of L^{=}.

Blanket Hypothesis: Hereafter it will be understood that all models mentioned are reduced. Also, T will always denote a complete theory of L with infinite models.

3 Examples

In this section we give some examples of categorical theories in logic without equality which behave oddly.

The theorem of Ryll-Nardzewski (see [V]) shows that for a complete theory T with infinite models in first order logic with equality, the following three conditions are equivalent:

(a) S_{n}(T) is finite for each n ∈ ω.

(b) T is ω-categorical.

(c) Every countable model of T is prime.

For logic without equality, it is easily seen that (a) implies (b) and (b) implies (c). But the following examples show that the reverse implications do not hold in logic without equality. In each example, we will describe a countable model M and let T be the complete theory of M without equality, T = T h(M).

Note that if the vocabulary L is finite and has no function symbols, then there are essentially only finitely many atomic formulas, and the Leibniz equivalence relation is definable (take the conjunction of the formulas in condition (1) where θ is atomic). Thus in this case conditions (a)-(c) are still equivalent. For this reason, all of our examples must either have an infinite vocabulary or function symbols.

Example 3.1 (Binary nested equivalence relations). Let L have countably many binary relations E_{n}, n < ω. Let M be a countable model such that each E_{n} is an equivalence relation, E_{0} has finitely many classes, and for every n, each equivalence class for E_{n} is the union of two equivalence classes for E_{n+1}.

In this example, T is ω-categorical, but the Stone space S_{2}(T) is infinite, so (b) holds but (a) fails. Another interesting property of this example is that every model has cardinality at most continuum; the upward Löwenheim-Skolem-Tarski theorem fails for (reduced models of) logic without equality.

Example 3.2 (Infinite nested equivalence relations). Let M be as in the preceding example, except that each equivalence class for E_{n} is the union of countably many equivalence classes for E_{n+1}.

Again, T is ω-categorical, but the Stone space S_{2}(T) is infinite. But this time every model of T has elementary extensions of arbitrarily large cardinality.

Example 3.3 Let L have countably many binary relations E_{n}, n < ω, a unary relation U, and a unary function symbol f. Let M be a countable model such that (U, E_{n})_{n∈ω} is the structure from the first example, f is the identity on U, and for each n,

M ⊧ ∀y U(f(y)) ∧ ∀x[U(x) ⇒ ∃y[¬U(y) ∧ E_{n}(x, f(y))]].

That is, f maps the complement of U to a dense subset of U.

The theory T is not ω-categorical, because there are countable models M where range(f) = U and N where range(f) ≠ U. But every countable model of T is prime. Thus (c) holds but (b) fails. We also remark that the models M and N are elementarily equivalent in the sense of L but are not elementarily equivalent with respect to the corresponding equality logic L^{=}.

Example 3.4 (An example with finite vocabulary). Let L have a unary relation U, a unary function symbol f, and a constant symbol c. In the model M,

M = {c} ∪ {x_{n} : n ∈ ω}

with c and all the x_{n}’s distinct, U = {x_{0}}, and

f(c) = c, f(x_{0}) = x_{0}, f(x_{n+1}) = x_{n} for each n ∈ ω.

Here the theory T is ω-categorical but the Stone space S_{1}(T) is infinite. In fact, all models of T are countable, so M is the only model of T up to isomorphism.

Another celebrated result for logic with equality is Vaught’s theorem [V] that no complete theory can have exactly two countable models. This result fails in logic without equality. By removing the constant symbol c from the vocabulary in the preceding example, we get a complete theory in logic without equality which has exactly two countable models up to isomorphism (and no uncountable models). Hint: there is at most one element z such that ¬U(f^{n}(z)) for all n.

Example 3.5 Let M be a model with a unary relation V, a copy of the model from Example 3.4 on V, and an equivalence relation with infinitely many classes on the complement of V.

In this example, T is κ-categorical for every infinite κ, but the interpretation of V is countably infinite for every model of T. To see this, observe that the theory of equality with infinitely many elements is κ-categorical for every infinite κ. This example is an artifact of the failure of the upward Löwenheim-Skolem-Tarski theorem. In a κ-categorical theory in logic with equality, all infinite definable sets in a model of cardinality κ have cardinality κ.

4 Omitting Types

The culprit behind the odd examples of ω-categorical theories is the Omitting Types Theorem. The usual formulation of the theorem does not hold without equality; the problem is that in the proof, one must construct a model out of constant terms rather than constant symbols. We now give a version of the Omitting Types Theorem which holds for logic without equality.

Definition 4.1 We say that a set of formulas q(y⃗) with n free variables y⃗ is locally realized by a theory U if for some m, there is a formula θ(x⃗) with m free variables x⃗ and an n-tuple of terms σ⃗(x⃗) such that θ(x⃗) is consistent with U and

U ⊧ ∀x⃗[θ(x⃗) ⇒ ψ(σ⃗(x⃗))]

for all ψ ∈ q(y⃗). We also say that θ(x⃗) and σ⃗ witness the local realization.

Theorem 4.2 (Omitting Types without Equality) Let U be a consistent theory and let q(y⃗) be a set of formulas in finitely many free variables y⃗. Suppose that

(i) q(y⃗) is realized in every model of U. Then

(ii) U locally realizes q(y⃗).

Note that since L is countable, (i) holds if and only if q is realized in every countable model of U.

Here is a topological formulation of local realizing. An n-tuple of terms σ⃗(x⃗) in m free variables x⃗ induces the continuous mapping

σ̂ : S_{m}(U) → S_{n}(U)

defined by

σ̂(p) = {ψ(y⃗) : ψ(σ⃗(x⃗)) ∈ p}.

We shall call the mapping σ̂ a term mapping from S_{m}(U) into S_{n}(U). In logic with equality, each term mapping is open, but in logic without equality term mappings need not be open. Then U locally realizes q(y⃗) if and only if:

(iii) For some m, there is a term mapping

σ̂ : S_{m}(U) → S_{n}(U)

such that σ̂^{−1}(q) has a nonempty interior.

In the classical Omitting Types Theorem for logic with equality, σ⃗(x⃗) is just x⃗, and σ̂ is the identity mapping on S_{n}(U). The present statement is different even in the case that the vocabulary L has only relation symbols.

In Examples 3.1 and 3.2, n = 2 with y⃗ = (y_{1}, y_{2}), and m = 1 with σ⃗(x) = (x, x). In these examples, condition (iii) holds for the nonisolated 2-type q = {E_{n}(y_{1}, y_{2}) : n ∈ ω}, and σ̂ maps the one-point space S_{1}(T) to q.

In Example 3.4, n = 1, and m = 0 with the constant term σ = c. Condition (iii) holds for the nonisolated 1-type q = {¬U(f^{n}(y)) : n ∈ ω}, and σ̂ maps the one-point space S_{0}(T) to q.

Proof of the Omitting Types Theorem. We assume that (ii) fails and prove that (i) fails. To do this we must construct a model M of U which omits (i.e. does not realize) q(y⃗). Let n = |y⃗|.

Let C be a countable set of constant symbols which are not in L. Then L_{C} is countable, and we may arrange all the sentences in a list

ψ_{m}, m < ω.

We also arrange all the n-tuples of variable-free terms in a list

σ⃗_{m}, m < ω.

We will form an increasing chain of theories U_{m} for L_{C} such that for each m:

(a) U_{m} is consistent and is a finite extension of U;

(b) If ψ_{m} is consistent with U_{m} then ψ_{m} ∈ U_{m+1};

(c) If ψ_{m} = ∃xθ(x) and ψ_{m} is consistent with U_{m}, then there exists c ∈ C such that θ(c) ∈ U_{m+1};

(d) There is a formula φ(y⃗) ∈ q(y⃗) such that (¬φ(σ⃗_{m})) ∈ U_{m+1}.

These conditions are the same as in the usual proof of the Omitting Types Theorem for logic with equality (e.g. see [CK], p.80) except that condition (d) has terms instead of a constant symbols from C. The construction of the chain U_{n} is routine and is left to the reader, with the hint that the hypothesis “U does not locally realize q(y⃗)” is used to get condition (d).

The union U_{ω} = ⋃_{m} U_{m} is a complete theory in L_{C}. In view of (c), U_{ω} has a model M′ = (M, c^{M})_{c∈C} such that each element of M is the interpretation of a variable-free term τ of L_{C}. By (d), the reduct M of M′ to L is a model of U which omits q(y⃗). □

Corollary 4.3 Let T be a complete theory and let q(y⃗) be a set of formulas with n free variables y⃗. Then conditions (i) and (ii) of the Omitting Types Theorem are equivalent. □

As in the case of logic with equality, a minor modification of the proof gives the following Extended Omitting Types Theorem.

Theorem 4.4 Let U be a consistent theory and for each m < ω let q_{m} be a set of formulas with finitely many free variables. Suppose that for each m, U does not locally realize q_{m}. Then U has a model which omits each q_{m}. □

5 ω-categorical Theories

In this section we will use the Omitting Types theorem to characterize ω-categorical theories. Let us say that U is a simple expansion of T if U = T h(M, a⃗) for some countable M ⊧ T and finite tuple a⃗ in M.

Corollary 5.1 The following are equivalent.

(i) T is ω-categorical.

(ii) Every countable model of T is ω-saturated.

(iii) For each simple expansion U of T, every type q ∈ S_{n}(U) is locally realized by U.

Proof. As in the case of logic with equality, (i) ⇒ (ii) is proved using the compactness theorem, and the converse is proved with a back and forth argument.

By the definition of ω-saturation, (ii) holds if and only if for every simple expansion U of T, every type q ∈ S_{n}(U) is realized in every countable model of U. By the Omitting Types Theorem, this is equivalent to condition (iii). □

We shall now give a nicer characterization in the case that the vocabulary L has no function symbols. L may still have infinitely many relation and/or constant symbols.

Theorem 5.2 Suppose the vocabulary L has no function symbols. The following are equivalent.

(i) T is ω-categorical.

(ii) Every countable model of T is prime.

(iii) For each n, every type in S_{n}(T) is realized in every model of T.

(iv) For each n, every type in S_{n}(T) is locally realized by T.

Proof. Even without the hypothesis that L has no function symbols, it is clear that (i) implies (ii) and (ii) implies (iii), and the equivalence of (iii) and (iv) follows from the Omitting Types Theorem.

To complete the proof we assume condition (iv) and prove (i). Let U = T h(M, a⃗) be a simple expansion of T, and let q ∈ S_{n}(U). By Corollary 5.1, it suffices to prove that q is locally realized by U. Let k = |a⃗|. Then q(y⃗) = r(a⃗, y⃗) for some type r(u⃗, y⃗) ∈ S_{k+n}(T). Let p(u⃗) be the projection of r to S_{k}(T). Then U = p(a⃗). We may assume without loss of generality that the tuple a⃗ contains no repeats or constants from L. By (iv), there is a tuple of terms (τ⃗(x⃗), σ⃗(x⃗)) and a formula θ(x⃗) such that

T ⊧ ∃x⃗θ(x⃗) ∧ ∀x⃗[θ(x⃗) ⇒ ⋀ r(τ⃗(x⃗), σ⃗(x⃗))].

Since L has no function symbols, τ⃗ is a sequence of variables from x⃗ and constant symbols. Since a⃗ contains no repeats or constants from L, τ⃗ must be a k-tuple of distinct variables, which we may take to be u⃗. Let v⃗ be the variables in x⃗ which do not occur in u⃗, so that x⃗ = (u⃗, v⃗).

We claim that the formula ∃v⃗ θ(u⃗, v⃗) belongs to the type p(u⃗). Proof of claim: Suppose not. Since p is complete, ¬∃v⃗ θ(u⃗, v⃗) belongs to p(u⃗). But then

T ⊧ θ(u⃗, v⃗) ⇒ ¬∃v⃗ θ(u⃗, v⃗),

and this contradicts the fact that

T ⊧ ∃u⃗∃v⃗θ(u⃗, v⃗).

Now replace the variables u⃗ with the constant symbols a⃗. The claim shows that

U ⊧ ∃v⃗ θ(a⃗, v⃗).

Since U contains T, we have

U ⊧ ∀v⃗[θ(a⃗, v⃗) ⇒ ⋀ q(σ⃗))].

This shows that U locally realizes q(y⃗) and completes the proof. □

In the general case that L has function symbols, we know from Example 3.3 that (ii) does not imply (i). However, we do not know whether (iii) implies (ii).

We now consider the existence of prime models. Using the same argument as for logic with equality, one can show that if S_{n}(T) is at most countable for each n, then every simple expansion of T has a prime model. Here is a necessary and sufficient condition for every simple expansion of T to have a prime model.

Proposition 5.3 The following are equivalent:

(i) Every simple expansion U of T has a prime model.

(ii) For every simple expansion U of T, every formula φ(y) which is consistent with U belongs to a 1-type q(y) which is locally realized by U.

Proof. The implication from (i) to (ii) is an easy corollary of the Omitting Types Theorem.

Assume (ii). Let U be a simple expansion of T and let K be the vocabulary of U. Add a countable sequence c_{n}, n < ω of new constant symbols to K and let K′ = K∪{c_{n} : n < ω}. We can form a list φ_{k}(y), k < ω of all formulas of K′ with the property that for each k, at most the constants c_{n}, n < k occur in φ_{k}. Let U_{0} = U.

By recursion, choose a sequence of simple expansions U_{k} of U to K ∪ {c_{n} : n < k} and 1-types q_{k} over U_{k} such that:

(a) q_{k}(y) is locally realized by U_{k},

(b) q_{k}(y) contains the formula ∃zφ_{k}(z) ⇒ φ_{k}(y),

(c) U_{k+1} = q_{k}(c_{k}).

The sequence {U_{k}} is an increasing chain of complete theories, so their union has a model M′ with vocabulary K′. Let N′ be the submodel of M′ generated by the constants c_{n} : n < ω. By the criterion of Tarski and Vaught, N′ ≺ M′. Therefore the reduct N of N′ to K is a model of U. By Corollary 4.3, q_{k}(y) is realized in every model of U_{k}. It follows that every model O of U has a sequence of elements b_{n}, n < ω such that for each k,

(O, b_{0}, …, b_{k−1}) ⊧ U_{k}.

The mapping c_{n} ↦ b_{n} generates an elementary embedding of N into O, so N is prime. □

6 Bounded Theories

The usual proof of the downward Löwenheim-Skolem-Tarski theorem goes through for logic without equality; that is, if ω ≤ λ ≤ κ and T has a model of cardinality κ, then T has a model of cardinality λ. In fact, every model for L of cardinality κ has an elementary submodel of cardinality λ.

We have already seen from our examples that the corresponding upward theorem fails; there are complete theories which have models of cardinality ω but no larger, and complete theories which have models of cardinality 2^{ω} but no larger. In this section we shall see that ω and 2^{ω} are the only cardinals where this happens. This shows that (2^{ω})^{+} is the Hanf number of first order logic without equality. We will then show that any theory which is categorical in some uncountable cardinal must have models of arbitrarily large cardinality.

Definition 6.1 T will be called bounded if the class of cardinalities of models of T has an upper bound. Otherwise we say that T is unbounded.

By a fully saturated model we mean a model that is κ-saturated for all cardinals κ. It is clear that M is fully saturated if and only if it is |M|^{+}-saturated.

Lemma 6.2 (i) If M is a fully saturated model T, then every model of T is elementarily embeddable in M, and every fully saturated model of T is isomorphic to M.

(ii) T is bounded if and only if it has a fully saturated model.

Proof. (i) follows from the following two facts about a κ-saturated model M of T of cardinality at most κ (see [CK], Section 5.1). Any κ-saturated model of T of cardinality at most κ is isomorphic to M, and any model of T of cardinality at most κ is elementarily embeddable in M.

(ii) Suppose T is bounded. Then for some κ, all models of T have cardinality at most κ. But every T has a κ^{+}-saturated model M (of cardinality at most 2^{κ}). Then M is |M|^{+}-saturated and hence fully saturated.

Finally, suppose T has a fully saturated model M. By (i), every model of T is elementarily embeddable in M and hence has cardinality at most |M|, so T is bounded. □

Lemma 6.3 Let M be a model of T. The following are equivalent:

(i) T is bounded.

(ii) Every equivalence relation definable without parameters in M has finitely many equivalence classes.

(iii) Every equivalence relation definable with parameters in M has finitely many equivalence classes.

Proof. We first prove that (i) implies (iii). Suppose that (iii) fails, so that M has an equivalence relation with infinitely many classes defined by a formula θ(x, y, a⃗) with parameters a⃗. Using the compactness theorem, for each cardinal κ, M has an elementary extension N in which θ(x, y, a⃗) defines an equivalence relation with at least κ classes. Then |N| ≥ κ, so T is unbounded and (i) fails.

It is trivial that (iii) implies (ii).

We now assume (ii) and prove (i). The Leibniz congruence relation is an intersection of countably many equivalence relations E_{n}, n ∈ ω which are definable without parameters in M. By (ii), each E_{n} has finitely many classes. Since we are restricting attention to reduced models, two elements of M which are equivalent with respect to each E_{n} are equal. Therefore |M| ≤ 2^{ω}, and thus T is bounded. □

Our next theorem will give a concrete representation of the fully saturated model of a bounded theory T and all its elementary submodels, up to an isomorphism.

By a finitely branching tree we mean a tree T which has ω levels and finitely many nodes at each level. We denote the set of all branches of T by B(T ), and give B(T ) the usual topology where the set of all branches through a node is a basic clopen set. This topology is compact and Hausdorff.

For each n ∈ ω we give B(T )^{n} the product topology. By a clopen relation on B(T ) we mean a relation which is clopen on B(T )^{n} for some n. By a continuous function of n variables on B(T ) we mean a continuous function from B(T )^{n} into B(T ).

Proposition 6.4 Suppose T is bounded. Then there is a finitely branching tree T and a fully saturated model M of T such that:

(i) M has universe B(T ).

(ii) A relation is definable with parameters in M if and only if it is clopen in B(T ).

(iii) Each function of finitely many variables defined in M by a term is continuous on B(T ).

(iv) A subset M_{0} ⊆ M is the universe of an elementary substructure of M if and only if M_{0} is dense in B(T ) and closed under each function defined by a term.

Proof. Let E_{n}, 0 < n < ω be a list of all equivalence relations definable without parameters in M, and let D_{n} = E_{1} ∩ ⋯ ∩ E_{n}. By Lemma 6.3, each E_{n} has finitely many equivalence classes. Let D_{0} = E_{0} be the trivial equivalence relation with one class. Then each D_{n} has finitely many equivalence classes, and D_{n+1} is a refinement of D_{n}. Let T be the finitely branching tree such that the set of nodes of T at level n is equal to the set of equivalence classes of D_{n}, and whose order relation is reverse inclusion. Identify each element x ∈ M with the branch of T whose node at level n is the D_{n}-equivalence class of x. It follows from full saturation that each branch of T is realized in M. Thus M has universe B(T ), and (i) holds.

(ii) Since each equivalence relation D_{n} is definable in M, each equivalence class of D_{n} is definable with parameters in M. It follows that each clopen relation is definable with parameters in M.

For the converse, suppose for example that a ternary relation R is defined by the formula ψ(x, y, z, a⃗) with parameters a⃗ in M. Any definable equivalence relation in M is refined by some D_{n}. We may therefore choose n large enough so that D_{n}(b, c) implies

∀y∀z∀u⃗ [ψ(b, y, z, u⃗) ⇔ ψ(c, y, z, u⃗)],
∀x∀z∀u⃗ [ψ(x, b, z, u⃗) ⇔ ψ(x, c, z, u⃗)],
∀x∀y∀u⃗ [ψ(x, y, b, u⃗) ⇔ ψ(x, y, c, u⃗)].

Now suppose that

D_{n}(x, x′), D_{n}(y, y′), D_{n}(z, z′), and R(x, y, z).

It then follows in turn that ψ(x, y, z, a⃗), ψ(x′, y, z, a⃗), ψ(x′, y′, z, a⃗), ψ(x′, y′, z′, a⃗), and R(x′, y′, z′). This shows that the relation R is clopen with respect to the product topology in B(T ), and (ii) is proved.

(iii) Let S be a clopen set in B(T ) and σ(x, y, z) a term of L. By (ii), S is definable by a formula ψ(u, a⃗). Then σ^{−1}(S) is definable by the formula ψ(σ(x, y, z), a⃗), and is clopen in B(T ) by (ii).

(iv) Let M_{0} ≺ M. It is clear that the universe M_{0} is closed under functions defined by terms of L. Since each relation D_{n} has finitely many equivalence classes and is definable without parameters in M, M_{0} must meet each equivalence class of D_{n}. Therefore M_{0} is dense in B(T ).

For the converse, suppose M_{0} is dense in B(T ) and closed under each function defined by a term of L. Then M_{0} is a substructure of M. Suppose M ⊧ ∃x ψ(x, b⃗) where b⃗ is in M_{0}. Since M_{0} is dense and the set defined by ψ(x, b⃗) in M is nonempty and clopen, there exists a ∈ M_{0} such that M ⊧ ψ(a, b⃗). Thus M_{0} ≺ M by the criterion of Tarski and Vaught. □

Let us say that T is countably bounded if all models of T are countable, and uncountably bounded if T is bounded but has an uncountable model.

Corollary 6.5 (i) T is countably bounded if and only if T has a fully saturated model of cardinality ω.

(ii) T is uncountably bounded if and only if T has a fully saturated model of cardinality 2^{ω}.

(iii) T is unbounded if and only if every model of T has elementary extensions of arbitrarily large cardinality.

Proof. By Lemma 6.2, T is bounded if and only if it has a fully saturated model. By Proposition 6.4, if T is bounded then its fully saturated model can be identified with the set of branches of a finitely branching tree. But any finitely branching tree with uncountably many branches has 2^{ω} branches. We conclude that (i) and (ii) hold. Part (iii) follows easily from Lemma 6.3. □

Recall that the Hanf number of a logic is the least cardinal κ such that any theory which has a model of cardinality at least κ has models of arbitrarily large cardinality.

Corollary 6.6 The Hanf number of first order logic without equality is (2^{ω})^{+}. □

7 Uncountable Categoricity Implies Unbounded

In this section we will show that a bounded theory cannot be categorical in an uncountable cardinal. In fact, an uncountably bounded theory T has the maximum possible number 2^{λ} of nonisomorphic models in each uncountable cardinal λ ≤ 2^{ω}.

We first consider the case that λ ≤ 2^{ω} < 2^{λ}.

Theorem 7.1 Suppose T is uncountably bounded and λ ≤ 2^{ω} < 2^{λ}. Then T has 2^{λ} nonisomorphic models of cardinality λ.

Proof. Let M be a fully saturated model of T, and let A be a countable elementary submodel of M. By Theorem 6.4, distinct elements of M realize distinct 1-types over A.

We will use the result of Shelah [S], Theorem VIII 1.5 (4), which shows that in logic with equality, if there are uncountably many 1-types over a countable structure A, there is a set S of 1-types over A of cardinality 2^{ω} such that for each R ⊆ S there is a structure B(R) ≻ A which realizes each p ∈ R and omits each p ∈ S \ R. The proof of this result still works in logic without equality. It follows that there is a family K = {B(R) : R ∈ [S]^{λ}} of structures B(R) such that A ≺ B(R) ≺ M, |B(R)| = λ, and for all distinct Q, R ∈ [S]^{λ}, there is no isomorphism from B(Q) to B(R) which is the identity on A.

The family K has cardinality 2^{λ}, and the relation of being isomorphic partitions K into equivalence classes. To complete the proof it suffices to show that there are 2^{λ} different equivalence classes. Suppose not. Then there is an equivalence class K_{0} of cardinality 2^{λ}. Choose C ∈ K_{0}, and for each B(R) ∈ K_{0} choose an isomorphism f_{R} : B(R) ≅ C. There are only 2^{ω} different mappings from A into C, and since 2^{ω} < 2^{λ}, there are distinct B(Q), B(R) ∈ K_{0} such that the isomorphisms f_{Q} and f_{R} have the same restriction to A. But then by composing isomorphisms we see that B(Q), B(R) are isomorphic by a mapping which is the identity on A, and we have a contradiction. □

We now consider the case that ω < λ < 2^{λ} = 2^{ω}. Shelah in [S], Theorem VIII 1.8, proved that any theory T in logic with equality which is not ω-stable has at least 2^{ω} nonisomorphic models of cardinality λ. His argument can be applied to logic without equality to show that any uncountably bounded theory has at least 2^{ω} nonisomorphic models of cardinality λ. We will now prove a slightly stronger result in this direction.

Theorem 7.2 Suppose T is uncountably bounded. Then T has a family K of models such that K has cardinality 2^{ω}, each M ∈ K has cardinality 2^{ω}, and whenever M ∈ K, N ∈ K, and M ≠ N, no uncountable elementary submodel of M is elementarily embeddable in N.

Given two distinct branches b, c of a finitely branching tree T , let δ(b, c) be the level of the highest node on b∩c. We say that a mapping h from a subset Y ⊆ B(T ) into B(T ) is level-preserving if δ(h(b), h(c)) = δ(b, c) for all distinct b, c ∈ Y. In the fully saturated model M of Proposition 6.4, the relation δ(x, y) = n says that n is the least m for which ¬E_{m}(x, y), and hence is definable in M without parameters. It follows that every elementary embedding from an elementary submodel of M into M is level-preserving. Therefore Theorem 7.2 is a consequence of Proposition 6.4 and the following topological result on finitely branching trees.

Theorem 7.3 Let T be a finitely branching tree with uncountably many branches, and let F be a countable set of continuous functions of finitely many variables on B(T ). Then there is a family {X_{α} ⊆ B(T ) : α < 2^{ω}} such that each X_{α} is a dense subset of B(T ) of size continuum which is closed under all f ∈ F and for each distinct α, β, there is no level-preserving mapping from an uncountable subset of X_{α} into X_{β}.

Proof. For simplicity, we first consider the case that

T = 2^{<ω} and B(T ) = B(2^{<ω})

Later we indicate how to do the more general case.

In this case

Definition 7.4 For any x, y ∈ B(2^{<ω})

δ(x, y) = min{n ∈ ω : x(n) ≠ y(n)}

Definition 7.5 For any set X ⊆ B(2^{<ω}) define

δ(X) = {δ(x, y) : x, y ∈ X}

Clearly, δ(X) is infinite for any infinite X.

We will construct X_{α} and A_{α} ⊆ ω such that the A_{α} are pairwise almost disjoint, i.e.

A_{α} ∩ A_{β} is finite

whenever α ≠ β, and for any α we can decompose X_{α} into countable many sets

X_{α} = ⋃{X_{α}^{n} : n ∈ ω}

such that δ(X_{α}^{n}) ⊆ A_{α} for each n < ω. This implies that there can be no levelpreserving map from any uncountable subset of X_{α} into X_{β}. For suppose there were a level-preserving bijection h : Y → Z with Y ⊆ X_{α} and Z ⊆ X_{β}. By cutting down the uncountable set Y we may assume that there exists n and m such that Y ⊆ X_{α}^{n} and Z ⊆ X_{β}^{m}. Level preserving implies that δ(Y) = δ(Z), but then

δ(Y) = δ(Z) ⊆ A_{α} ∩ A_{β},

contradicting the fact that A_{α} and A_{β} are almost disjoint.

The general case is a little messy, but the ideas are fairly simple. For the convenience of the reader we do a simple case first.

We first do the case that F is empty. In this case we may take the family {A_{α} : α < 2^{ω}} to be any family of infinite pairwise almost disjoint subsets of ω. Then define

X_{α} = {x ∈ B(2^{<ω}) : ∀^{∞}l (x(l) = 1 ⇒ l ∈ A_{α})}

∀^{∞}l means “for all but finitely many l”. It is easy to see that X_{α} is dense. Also, for any n ∈ ω and any s ∈ 2^{n}, if we define

X_{α}(s) = {x ∈ B(2^{<ω}) : s ⊆ x and ∀l > n (x(l) = 1 ⇒ l ∈ A_{α})}

then

δ(X_{α}(s)) ⊆ {l ∈ A_{α} : l ≥ n} and X_{α} = ⋃_{s∈2^{<ω}} X_{α}(s).

Now we consider the general case. We may assume that F is a family of continuous operations which contains the identity function and is closed under composition. Also, we may as well assume that for each s ∈ 2^{<ω} there is an operation f ∈ F such that f maps B(2^{<ω}) one-to-one into [s], where

Definition 7.6 For s ∈ 2^{<ω} define [s] = {x ∈ B(2^{<ω}) : s ⊆ x}.

Thus it is unnecessary to guarantee that X_{α} is dense; we will only need to construct Y_{α} ⊆ B(2^{<ω}) of cardinality continuum and then let X_{α} be the closure of Y_{α} under the operations of F.

Before diving into the details we give the general idea. Our plan is to construct a sequence k_{m} < k_{m+1} so that roughly speaking for each n-ary operation f ∈ F and x⃗, y⃗ ∈ Y_{α}^{n}

If

k_{m} < δ(f(x⃗), f(y⃗)) < k_{m+1}

then k_{m} < δ(u, v) < k_{m+1} for some u, v from x⃗ ∪ y⃗.

Definition 7.7 For s ∈ 2^{l} and l < k, let ⟨s, k⟩ ∈ 2^{k} be the unique element of 2^{k} such that s ⊆ ⟨s, k⟩ and ⟨s, k⟩(i) = 0 for all i with l ≤ i < k. In other words, ⟨s, k⟩ is the sequence of length k gotten by extending s with zeros.

Lemma 7.8 Suppose F ⊆ F is finite and k < ω. Then there exists l > k such that for every n-ary f ∈ F and (r_{i} ∈ 2^{k} : i < n) there exists a t ∈ 2^{k} such that

f(∏_{i<n}[⟨r_{i}, l⟩]) ⊆ [t]

Proof. This is easy, just use the continuity of the f’s. □

Now write F = ∪{F_{n} : n < ω} as an increasing union of finite sets. By iteratively applying the last lemma we get:

There exist increasing sequences

(k_{m} ∈ ω : m < ω) and (l_{m} ∈ ω : m < ω)

with k_{m} < l_{m} < k_{m+1} satisfying the following conditions:

Let

L = {l_{m} : m < ω} and T = {s ∈ 2^{<ω} : ∀l (s(l) = 1 ⇒ l ∈ L)}.

Then for any m < ω,

1. For every n-ary f ∈ F_{m} and (s_{i} ∈ T ∩ 2^{l_{m}} : i < n) there exists t ∈ 2^{k_{m}} such

that

f(∏_{i<n}[s_{i}]) ⊆ [t].

2. For any n-ary f ∈ F_{m} and

(r_{i} ∈ T ∩ 2^{k_{m+1}}) : i < n) and (t_{i} ∈ T ∩ 2^{k_{m+1}}) : i < n),

if there exists k ≥ k_{m+1} with the property that there are distinct r, t ∈ 2^{k} with

f(∏_{i<n}[⟨r_{i}, k⟩]) ⊆ [r] and f(∏_{i<n}[⟨t_{i}, k⟩]) ⊆ [t],

then k_{m+1} already has this property.

This follows from the previous lemma. First we get l_{m} > k_{m} by applying Lemma 7.8 with k = k_{m} and then we get k_{m+1} as the maximum of finitely many k’s.

Given (B_{α} : α < 2^{ω}) infinite pairwise almost disjoint subsets, define Y_{α} as follows:

Y_{α} = {x ∈ B(2^{<ω}) : ∀l < ω (x(l) = 1 ⇒ ∃m ∈ B_{α} l = l_{m} )}

and define

A_{α} = {i : ∃m ∈ B_{α} k_{m} ≤ i < k_{m+1}}.

Lemma 7.9 Suppose m_{0} ∈ B_{α}, f ∈ F_{m_{0}} is n-ary, and x⃗, y⃗ ∈ Y_{α}^{n}. Then

δ(f(x⃗), f(y⃗)) ∈ A_{α} ∪ k_{m_{0}+1}

Proof. Suppose for contradiction that

k_{m} ≤ δ(f(x⃗), f(y⃗)) < k_{m+1}

for some m > m_{0} such that m ∉ B_{α}. By our construction l_{m} has the following property:

Let r_{i} = x_{i}|_{l_{m}} and let s_{i} = y_{i}|_{l_{m}} for each i < n. Then there exists
r, s ∈ 2^{k_{m}} such that

f(∏_{i<n}[r_{i}]) ⊆ [r] and f(∏_{i<n}[s_{i}]) ⊆ [s]

Because k_{m} ≤ δ(f(x⃗), f(y⃗)), it must be that r = s.

Let m_{1} ≥ m_{0} be the largest element of B_{α} such that m_{1} ≤ m. So m_{0} ≤ m_{1} < m and note that there is there is no splitting going on in Y_{α} between l_{m_{1}} + 1 and k_{m+1}, i.e., if u, v ∈ Y_{α}, then δ(u, v) ≤ l_{m_{1}} or δ(u, v) ≥ l_{m+1}.

Since m ∉ B_{α} and x_{i}, y_{i} ∈ Y_{α} it must be they are identically zero on all l with l_{m_{1}} < l < l_{m+1}. But l_{m+1} has been chosen so that for some r′, s′ ∈ 2^{k_{m+1}}

f(∏_{i<n}[x_{i}|_{l_{m+1}}]) ⊆ [r′] and f(∏_{i<n}[y_{i}|_{l_{m+1}}]) ⊆ [s′]

Since we are assuming δ(f(x⃗), f(y⃗)) < k_{m+1} it must be that r′ ≠ s′, but then this contradicts the way we have choose k_{m_{1}+1}, i.e., it must be that m_{1} = m and therefore m ∈ B_{α}. □

It follows from Lemma 7.9 that for any t ∈ 2^{k_{m_{0}+1}} that

δ ([t] ∩ f(∏_{i<n}([s_{i}] ∩ Y_{α}))) ⊆ A_{α}

and since the closure of Y_{α} under the operations of F can be written as a countable union of such sets, Theorem 7.3 has been proven for the special case that B(T ) = B(2^{<ω}).

Now we indicate the modifications necessary to prove the Theorem in general. Let T′ be the subtree of T consisting of all those nodes of T which have uncountably many branches thru them. Clearly,

Q = B(T ) \ B(T′)

is countable. Without loss of generality, we may assume that F also contains all operations which can be obtained by substituting elements of Q, e.g., if f ∈ F is binary and a ∈ Q then the unary operation g(x) = f(x, a) would also be in F. Thus we may choose Y_{α} ⊆ B(T′) and then take

X_{α} = Q ∪ ⋃{f(Y_{α}^{n}) : f ∈ F, n-ary for some n ∈ ω}

and then X_{α} will be closed under the operations of F.

In the proof, we need to define ⟨s, k⟩ where s ∈ T′ is at level l and k ≥ l. Put a linear ordering on T′ and then take ⟨s, k⟩ to be the node of T′ at level k which extends s and which is obtained by always taking the leftmost immediate branch.

The only other place in the proof that needs fixing is that we can not necessarily assume that the tree branches between level l_{n} and l_{n} + 1. Hence, we would choose l′_{n} > l_{n} so that

• each s ∈ T′ at level l_{n} has at least two incompatible extension in T′ at level l′_{n} and

• k_{n} < l_{n} < l′_{n} < k_{n+1}

Then we would take Y_{α} = B(T_{α}), where T_{α} is the subtree of T′, where nodes can be extended arbitrarily between levels l_{n} and l′_{n} if n ∈ B_{α}, but otherwise must be extended by using ⟨s, k⟩, i.e, the leftmost path. The choice of k_{n} is exactly the same and so is the rest of the proof. □

Combining Theorems 7.1 and 7.2, we have

Theorem 7.10 Suppose T is uncountably bounded. Then for every uncountable cardinal λ ≤ 2^{ω}, T has 2^{λ} nonisomorphic models of cardinality λ.

Corollary 7.11 If T is uncountably bounded, then for every uncountable cardinal κ, T is not κ-categorical. □

8 The Łoś Conjecture

In this section we show that the Łoś Conjecture, which was proved for logic with equality by Morley [M], also holds for logic without equality. The proof follows the same outline as the proof in [CK], which uses a two-cardinal omitting type theorem. We will refer to arguments from [CK] when we can, and indicate the modifications that are needed for logic without equality.

Recall that T is κ-stable if for every model M of T and every subset X ⊆ M of cardinality κ, the theory T h(M_{X}) has κ 1-types.

Proposition 8.1 If T is λ-categorical in some uncountable cardinal λ, then T is ω-stable.

Proof. By Corollary 7.11, T is unbounded, so by Lemma 6.3, there is a formula E(x, y) which defines an equivalence relation with infinitely many classes in every model of T. One can now follow the proof of the corresponding result for logic with equality (Lemma 7.1.4 in [CK]) but replace equality by E(x, y). □

Lemma 8.2 If T is ω-stable, then for every model M of T, regular cardinal λ > ω, and set Y ⊆ M of cardinality λ, there is an equivalence relation E(x, y) which is definable in T without parameters such that the restriction of E^{M} to Y × Y has λ equivalence classes.

Proof. Suppose the result fails for a model M of T and set Y ⊆ M of regular cardinality λ > ω. Let E_{n}, 0 < n < ω be a list of all equivalence relations definable without parameters in T, and let D_{n} be the restriction of E_{1} ∩ ⋯ ∩ E_{n} to Y × Y. Let T be the tree whose nodes at level n are the D_{n}-equivalence classes and whose ordering is reverse inclusion. Call a node t of T large if there are at least λ branches through t. Then the root of T is large, but at each level, T has fewer than λ nodes. It follows that for each large node t of T there are two disjoint large nodes above t. But then T has a subtree with countably many nodes and uncountably many branches. Therefore M has a countable subset X such that there are uncountably many types over M_{X}, so T is not ω-stable. □

Proposition 8.3 If T is ω-stable, then T is κ-stable for every infinite cardinal κ.

Proof. Suppose T is not κ-stable, so T has a model M which realizes κ^{+} types over some set X ⊆ M of power κ. By Lemma 8.2, there is an equivalence relation E(x, y) definable in T and a subset Y ⊆ M such that |Y | = κ^{+}, the restriction of E^{M} to Y × Y is the equality on Y, and any two distinct elements a, b ∈ Y realize different types in M_{X}. One can now repeat the proof of the corresponding result for equality logic (Lemma 7.1.3 in [CK]) but with the relation E(x, y) in place of equality. □

Definition 8.4 A model M of T is said to be primary over a subset A ⊆ M if there is a sequence ⟨b_{β} : β < α⟩ of elements of M such that

(i) A ∪ {b_{β} : β < α} generates M,

(ii) For each formula φ(y) in L_{A} ∪ {b_{β} : β < α} there exists γ < α such that

(M_{A}, b_{β})_{β<α} ⊧ ∃yφ(y) ⇒ φ(b_{γ}).

(iii) For each β < α, the 1-type of b_{β} in T h((M_{A}, b_{β})_{β<α}) is isolated, (i.e. b_{β} satisfies a maximal consistent formula).

It is clear that every primary model over A is prime over A.

Lemma 8.5 Suppose T is ω-stable. Then for every model M of T and every set A ⊆ M, M has an elementary submodel which is primary over A.

Proof. Since T is ω-stable, a binary tree argument shows that for every B ⊆ M, every formula φ(y) which is consistent with T h(M_{B}) is implied by a formula ψ(y) which is maximal consistent with T h(M_{B}). By transfinite recursion, one can build a sequence ⟨b_{β} : β < α⟩ in M such that conditions (ii) and (iii) in the above definition hold. Condition (ii) implies that α > 0. It follows that the set A ∪ {b_{β} : β < α} is nonempty, and generates a submodel M_{0} of M which is an elementary submodel and is primary over A. □

We need one more lemma, which is the analogue of Lemma 7.1.13 in [CK] for logic without equality.

Lemma 8.6 Suppose T is ω-stable and M is an uncountable model of T. Then there is a proper elementary extension N ≻ M such that every countable set of formulas Γ(y) which is realized in N_{M} is realized in M_{M}.

Proof. By ω-stability and a binary tree argument, there is a definable set D in M_{M} such that D is uncountable, but for any definable subset C ⊆ D, either C or D \C is countable. By Lemma 8.2, there is an equivalence relation E(x, y) definable without parameters in T whose restriction to D has uncountably many equivalence classes. One can now use Lemma 8.5, and the proof of Lemma 7.1.16 in [CK] with E(x, y) in place of equality, to obtain the required model N ≻ M. □

Theorem 8.7 (Łoś Conjecture) If T is λ-categorical for some uncountable cardinal λ, then T is κ-categorical for every uncountable cardinal κ.

Proof. We have shown that T is unbounded and stable in every infinite cardinal. Now the usual proof that T has an ω_{1}-saturated model in every uncountable cardinal goes through (see [CK], Lemma 7.1.6). Finally, one can use Lemma 8.6 and the argument in [CK], p. 494, to show that T is κ-categorical. □

References

[BP] W.J.Blok and D. Pigozzi, Algebraizable logics, Memoirs of the A.M.S. no. 396 (1989).

[CDJ] E.Casanovas, P.Dellunde, R.Jansana, On elementary equivalence for equalityfree logic, Notre Dame Journal of Formal Logic, 37(1996), 506-522.

[CK] C.C.Chang, H.J.Keisler, Model theory, North-Holland 1990.

[D] P.Dellunde, Equality-free logic: the method of diagrams and preservation theorems, to appear.

[DJ] P.Dellunde, R.Jansana, Some characterization theorems for infinitary universal Horn logic without equality, Journal of Symbolic Logic, 61 (1996), 1242-1260.

[K] H.J.Keisler, Logic with the quantifier “there exist uncountably many”, Ann. Math. Logic 1 (1970), 1-93.

[Ł] J. Łoś, On the categoricity in power of elementary deductive systems and some related problems, Colloq. Math 3 (1954), 58-62.

[M] M.D.Morley, Categoricity in power, Trans. A.M.S. 114 (1965), 514-538.

[S] S. Shelah, Classification Theory, North-Holland Elsevier. First edition 1978, second edition 1990.

[V] R.L.Vaught, Denumerable models of complete theories, in Infinitistic Methods Proc. Sympos. Foundations of Math., Warsaw, 1959, Pergamon 1961, 303-321.

Addresses

University of Wisconsin-Madison Department of Mathematics Van Vleck Hall 480 Lincoln Drive Madison, Wisconsin 53706-1388, USA e-mail: keisler@math.wisc.edu e-mail: miller@math.wisc.edu home page: http://www.math.wisc.edu/∼keisler home page: http://www.math.wisc.edu/∼miller