%% Latex2e
\documentclass[12pt]{article}
\usepackage{latexsym}

\def\note{\footnote{This appears
in the {\L}os Memorial Volume, Fundamenta Mathematicae, 170(2001),
87-106.)}}


\title{Categoricity Without Equality}
\author{H. Jerome Keisler and Arnold W. Miller}
\date{}

\setlength{\textwidth}{15cm}
\setlength{\oddsidemargin}{1.0cm}
\setlength{\evensidemargin}{1.0cm}
\setlength{\topmargin}{1.0cm}
\setlength{\headheight}{0cm}
\setlength{\textheight}{20.0cm}
\setlength{\headsep}{0cm}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{question}[theorem]{Question}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{remark}[theorem]{Remark}
\newcommand{\CA}{\mathcal{A}}
\newcommand{\CB}{\mathcal{B}}
\newcommand{\CC}{\mathcal{C}}
\newcommand{\CM}{\mathcal{M}}
\newcommand{\CN}{\mathcal{N}}
\newcommand{\CO}{\mathcal{O}}
\newcommand{\CT}{\mathcal{T}}
\def\res{|_}           \def\cc{{2^\om}}
\def\pr{\prime}        \def\al{\alpha}    \def\be{\beta}     \def\ka{\kappa}
\def\de{\delta}        \def\om{\omega}    \def\sg{\sigma}    \def\cs{B(\tr)}
\def\tr{2^{<\om}}      \def\su{\subseteq} \def\sp{\supseteq}
\def\la{\left(}        \def\ra{\right)}   \def\ff{{\cal F}}
\def\imp{\;\;\Rightarrow\;\;}             \def\rmand{{\;\;\mbox{ and }\;\;}}
\def\zz#1{\langle #1 \rangle}
\def\pf{\par\noindent{\bf Proof. }}
\def\qed{\par\noindent$\Box$}

\begin{document}

\maketitle

\begin{abstract}
We study categoricity in power for reduced models of first
order logic without equality. \note
\end{abstract}

\section{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 $\CM$
such that any pair of elements which satisfy the same formulas
with parameters in $\CM$ 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
$\kappa$-categorical if $T$ has exactly one reduced model of
cardinality $\kappa$ up to isomorphism.

The classical result about $\omega$-categoricity for logic with
equality is the Ryll-Nardzewski theorem, which says that $T$ is
$\omega$-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{\"o}wenheim-Skolem-Tarski theorem,
that $T$ has at least one model of every infinite cardinality.
Concerning uncountable categoricity, {\L}o\'{s} \cite{L}
conjectured that if $T$ is $\lambda$-categorical for some
uncountable $\lambda$, then $T$ is $\kappa$-categorical for every
uncountable $\kappa$.  The {\L}o\'{s} conjecture was proved for
logic with equality by Morley \cite{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 $\omega$-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
$\omega$-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^\omega)^+$.  In Section 7 we show that no bounded theory is
categorical in an uncountable cardinal.  Finally, the {\L}o\'{s}
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.

\section{Preliminaries}  \label{prelim}

Throughout this paper, $L$ will be a countable first order
predicate logic {\it 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 \cite{BP},\cite{CDJ}, \cite{D}, \cite{DJ}).

\begin{definition}
A model $\CM$ for $L$ is said to be {\bf reduced} if
for any pair of elements $a,b\in M$, we have $a=b$ if and only if
for every formula $\theta(x,\vec y)$ of $L$,
\begin{equation} \label{leibniz}
\CM \models \forall\vec u[\theta(a,\vec u)\Leftrightarrow\theta(b,\vec u)].
\end{equation}
\end{definition}

In general, two elements $a,b\in M$ are said to be {\bf Leibniz
congruent}, in symbols $a\equiv b$, if condition (\ref{leibniz})
holds for all formulas $\theta$ of $L$. Thus $\CM$ is reduced if
and only if its Leibniz congruence relation is the equality
relation on $M$.  It is well known that for every model $\CM$ for
$L$, the quotient structure $\CM/\!\!\equiv$ of $\CM$ modulo its
Leibniz congruence is a reduced model, and the mapping $a\mapsto
a/\!\!\equiv$ preserves the truth values of all formulas of $L$.
Moreover, if condition (\ref{leibniz}) holds for all atomic
formulas $\theta$, then it holds for all formulas $\theta$. We are
primarily interested in the case that the Leibniz congruence
relation is not definable in $\CM$.

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

\begin{proposition} If $\Gamma$ is a set of sentences of
$L$ and every finite subset of $\Gamma$ has a model, then $\Gamma$
has a reduced model of cardinality at most $\omega$. \qed
\end{proposition}

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\subseteq M$, we let $L_X$ be the expansion of $L$
obtained by adding a new constant symbol for each $a\in X$, and let
$\CM_X$ be the corresponding expansion of $\CM$.
As usual, we say that $\CM$ is {\bf $\kappa$-saturated} if for each
$X\subseteq M$ of cardinality less than $\kappa$, every 1-type
in $Th(\CM_X)$ is satisfiable in $\CM_X$.  The following existence
theorem is proved exactly as in the case of logic with equality.

\begin{proposition} \label{saturated}
(i)  For each infinite cardinal  $\kappa$,  every consistent
theory in $L$ has a $\kappa^+$-saturated reduced model of
cardinality at most $2^\kappa$.

(ii)  A complete theory $T$ has an at most countable
$\omega$-saturated reduced model if and only if $S_n(T)$ is finite
or countable for each $n$.  \qed
\end{proposition}


We shall say that a theory $T$ in $L$ is {\bf $\kappa$-categorical} if
it has exactly one reduced model of cardinality $\kappa$ up to
isomorphism.
\bigskip

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 $\CM$ is reduced if and only if it omits the following
set $\Lambda(x,y)$ of formulas of $L^=$:
$$\Lambda(x,y)=
\{\neg x = y\}\cup\{\forall\vec u[\theta(x,\vec u)\Leftrightarrow
\theta(y,\vec u)]:\theta \mbox{ 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^=$.
\medskip

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


\section{Examples}

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

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

(a) {\it $S_n(T)$ is finite for each $n\in\omega$.}

(b) {\it $T$ is $\omega$-categorical.}

(c)  {\it Every countable model of $T$ is prime.}
\medskip

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 $\CM$ and
let $T$ be the complete theory of $\CM$ without equality, $T=Th(\CM)$.

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~(\ref{leibniz}) where
$\theta$ 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.

\begin{example} \label{ex1} (Binary nested equivalence relations).  Let $L$
have countably many binary relations $E_n, n<\omega$.  Let $\CM$
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}$.
\end{example}

In this example, $T$ is $\omega$-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{\"o}wenheim-Skolem-Tarski theorem fails for (reduced models of)
logic without equality.

\begin{example}  \label{ex2}
(Infinite nested equivalence relations).  Let $\CM$ 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}$.
\end{example}

Again, $T$ is $\omega$-categorical, but the Stone space $S_2(T)$ is
infinite.  But this time every model of $T$ has elementary extensions
of arbitrarily large cardinality.

\begin{example}  \label{allprime}
Let $L$ have countably many binary relations $E_n, n<\omega$,
a unary relation $U$, and a unary function symbol $f$.  Let $\CM$
be a countable model such that $(U,E_n)_{n\in\omega}$ is the
structure from the first example, $f$ is the identity on $U$,
and for each $n$,
$$\CM\models \forall y\, U(f(y)) \wedge
\forall x[U(x)\Rightarrow\exists y[\neg U(y)\wedge E_n(x,f(y))]].$$
That is, $f$ maps the complement of $U$ to a dense subset of $U$.
\end{example}

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

\begin{example} \label{fincat} (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 $\CM$,
$$M = \{c\}\cup\{ x_n :n\in\omega\}$$
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 \mbox{ for each } n\in\omega.$$
\end{example}

Here the theory $T$ is $\omega$-categorical but the Stone space
$S_1(T)$ is infinite.  In fact, all models of $T$ are countable, so
$\CM$ is the only model of $T$ up to isomorphism.

Another celebrated result for logic with equality is Vaught's theorem
\cite{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 $\neg U(f^n(z))$ for all $n$.


\begin{example}
Let $\CM$ be a model with a unary relation $V$, a copy of the
model from Example~\ref{fincat} on $V$, and an equivalence relation
with infinitely many classes on the complement of $V$.
\end{example}

In this example, $T$ is $\kappa$-categorical for every infinite
$\kappa$, 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 $\kappa$-categorical for
every infinite $\kappa$. This example is an artifact of the
failure of the upward L{\"o}wenheim-Skolem-Tarski theorem.  In a
$\kappa$-categorical theory in logic with equality, all infinite
definable sets in a model of cardinality $\kappa$ have cardinality
$\kappa$.

\section{Omitting Types}

The culprit behind the odd examples of $\omega$-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.

\begin{definition}  We say that
a set of formulas $q(\vec y)$ with $n$ free variables $\vec y$
is {\bf locally realized} by a theory $U$ if
for some $m$, there is a formula $\theta(\vec x)$ with $m$ free
variables $\vec x$ and an $n$-tuple of terms $\vec \sigma(\vec x)$
such that $\theta(\vec x)$ is consistent with $U$ and

$$U\models\forall\vec x[\theta(\vec x)
\Rightarrow\psi(\vec\sigma(\vec x))]$$
for all $\psi\in q(\vec y)$.  We also say that $\theta(\vec x)$ and
$\vec \sigma$ {\bf witness} the local realization.
\end{definition}

\begin{theorem} (Omitting Types without Equality)  Let $U$ be
a consistent theory and let $q(\vec y)$ be a set of formulas
in finitely many free variables $\vec y$.  Suppose that

(i)  $q(\vec y)$ is realized in every model of $U$.

\noindent Then

(ii) $U$ locally realizes $q(\vec y)$.
\end{theorem}

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 $\vec \sigma(\vec x)$ in $m$ free variables
$\vec x$ induces the continuous mapping
$$\hat\sigma : S_m(U)\rightarrow S_n(U)$$
defined by
$$\hat\sigma(p) = \{\psi(\vec y): \psi(\vec\sigma(\vec x))\in p\}.$$
We shall call the mapping $\hat\sigma$ a {\bf 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(\vec y)$ if and only if:
\medskip

{\it  (iii) For some $m$, there is a term mapping}
$$\hat\sigma : S_m(U)\rightarrow S_n(U)$$
{\it such that $\hat\sigma^{-1}(q)$ has a nonempty interior.}
\medskip

In the classical Omitting Types Theorem for logic with equality,
$\vec\sigma(\vec x)$ is just $\vec x$,
and $\hat\sigma$ 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~\ref{ex1} and \ref{ex2},
$n=2$ with $\vec y=(y_1,y_2)$, and $m=1$ with
$\vec\sigma(x)=(x,x)$.  In these examples, condition (iii) holds for
the nonisolated 2-type \\
$q=\{E_n(y_1,y_2):n\in\omega\}$, and $\hat\sigma$ maps the one-point space $S_1(T)$
to $q$.

In Example~\ref{fincat}, $n=1$, and $m=0$ with the constant term $\sigma=c$.
Condition (iii) holds for the nonisolated 1-type
$q=\{\neg U(f^n(y)):n\in\omega\}$,
and $\hat\sigma$ maps the one-point space $S_0(T)$ to $q$.
\medskip

{\bf 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(\vec y)$.  Let $n=|\vec 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
$$ \psi_m, m<\omega.$$
We also arrange all the $n$-tuples of variable-free terms in a
list
$$ \vec\sigma_m, m<\omega.$$

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 $\psi_m$ is consistent with $U_m$ then
$\psi_m\in U_{m+1}$;

(c)  If $\psi_m=\exists x\theta(x)$ and $\psi_m$ is consistent with $U_m$,
then there exists $c\in C$ such that $\theta(c)\in U_{m+1}$;

(d) There is a formula $\varphi(\vec y)\in q(\vec y)$ such that
$(\neg\varphi(\vec\sigma_m))\in 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 \cite{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(\vec y)$'' is used to get condition (d).

The union $U_\omega=\bigcup_m U_m$ is a complete theory in $L_C$.
In view of (c), $U_\omega$ has a model $\CM'=(\CM,c^\CM)_{c\in C}$
such that each element of $M$ is the interpretation of a
variable-free term $\tau$ of $L_C$.  By (d), the reduct $\CM$ of
$\CM'$ to $L$ is a model of $U$ which omits $q(\vec y)$.  \qed
\medskip

\begin{corollary} \label{converse} Let $T$ be
a complete theory and let $q(\vec y)$ be a set of formulas with
$n$ free variables $\vec y$.  Then conditions (i) and (ii) of the
Omitting Types Theorem are equivalent. \qed
\end{corollary}

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

\begin{theorem}   Let $U$ be
a consistent theory and for each $m<\omega$ 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$.  \qed
\end{theorem}




\section{$\omega$-categorical Theories}


In this section we will use the Omitting Types Theorem to
characterize $\omega$-categorical theories.
Let us say that $U$ is a {\bf simple expansion} of $T$ if
$U=Th(\CM,\vec a)$ for some countable $\CM\models T$ and finite tuple
$\vec a$ in $M$.

\begin{corollary} \label{general} The following are equivalent.

(i)  $T$ is $\omega$-categorical.

(ii)  Every countable model of $T$ is $\omega$-saturated.

(iii)  For each simple expansion $U$ of $T$, every type $q\in
S_n(U)$ is locally realized by $U$.
\end{corollary}

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

By the definition of $\omega$-saturation, (ii) holds if and only if
  for every simple expansion $U$ of $T$,
every type $q\in S_n(U)$ is realized in every countable model of
$U$. By the Omitting Types Theorem, this is equivalent to
condition (iii).  \qed
\medskip

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.

\begin{theorem}  Suppose the vocabulary $L$ has no function symbols.
The following are equivalent.

(i) $T$ is $\omega$-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$.
\end{theorem}

\pf 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=Th(\CM,\vec a)$
be a simple expansion of $T$, and let $q\in S_n(U)$.
By Corollary~\ref{general}, it suffices to prove that
$q$ is locally realized by $U$.  Let $k=|\vec a|$. Then
$q(\vec y)=r(\vec a,\vec y)$ for some type $r(\vec u,\vec y)\in S_{k+n}(T)$.
Let $p(\vec u)$ be the projection of $r$ to $S_k(T)$. Then $U=p(\vec a)$.
We may assume without loss of generality that the tuple $\vec a$
contains no repeats or constants from $L$.
By (iv), there is a tuple of terms $(\vec \tau(\vec x),\vec\sigma(\vec x))$
and a formula $\theta(\vec x)$ such that
$$T\models\exists\vec x\theta(\vec x)\wedge
\forall\vec x [\theta(\vec x)\Rightarrow
\bigwedge r(\vec\tau(\vec x),\vec\sigma(\vec x))].$$
Since $L$ has no function symbols, $\vec \tau$ is a sequence of variables
from $\vec x$ and constant symbols.   Since $\vec a$
contains no repeats or constants from $L$, $\vec \tau$ must be
a $k$-tuple of distinct variables, which we may take to be $\vec u$.
Let $\vec v$ be the variables in $\vec x$
which do not occur in $\vec u$, so that $\vec x=(\vec u,\vec v)$.

We claim that the formula $\exists \vec v\,\theta(\vec u,\vec v)$
belongs to the type $p(\vec u)$.  Proof of claim:  Suppose not.
Since $p$ is complete, $\neg\exists \vec v\,\theta(\vec u,\vec v)$
belongs to $p(\vec u)$. But then $$T\models\theta(\vec u,\vec
v)\Rightarrow \neg\exists \vec v\,\theta(\vec u,\vec v),$$ and
this contradicts the fact that $$T\models\exists\vec u\exists\vec
v\theta(\vec u,\vec v).$$

Now replace the variables $\vec u$ with the constant symbols $\vec a$.
The claim shows that
$$U\models\exists\vec v\,\theta(\vec a,\vec v).$$
Since $U$ contains $T$, we have
$$U\models\forall\vec v[\theta(\vec a,\vec v)\Rightarrow
\bigwedge q(\vec\sigma))].$$
This shows that $U$ locally realizes $q(\vec y)$
 and completes the proof.  \qed
\medskip

In the general case that $L$ has function symbols, we know
from Example~\ref{allprime} 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.

\begin{proposition} \label{prime}  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
$\varphi(y)$ which is consistent with $U$ belongs to a 1-type
$q(y)$ which is locally realized by $U$.
\end{proposition}

\pf  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<\omega$
of new constant symbols to $K$ and let $K'=K\cup\{c_n:n<\omega\}$.
We can form a list $\varphi_k(y), k<\omega$ of all formulas of
$K'$ with the property that for each $k$, at most the constants
$c_n, n<k$ occur in $\varphi_k$.  Let $U_0=U$. By recursion,
choose a sequence of simple expansions $U_k$ of $U$ to $K\cup\{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
 $\exists z\varphi_k(z)\Rightarrow\varphi_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 $\CM'$ with vocabulary $K'$.
Let $\CN'$ be the submodel of $\CM'$ generated by the constants
$c_n:n<\omega$.  By the criterion of Tarski and Vaught,
$\CN'\prec\CM'$.  Therefore the reduct $\CN$ of $\CN'$ to $K$ is a
model of $U$.  By Corollary~\ref{converse}, $q_k(y)$ is realized
in every model of $U_k$.  It follows that every model $\CO$ of $U$
has a sequence of elements $b_n, n<\omega$ such that for each $k$,
 $$(\CO,b_0,\ldots,b_{k-1})\models U_k.$$
 The mapping $c_n\mapsto b_n$ generates an elementary embedding
of $\CN$ into $\CO$, so $\CN$ is prime.  \qed


\section{Bounded Theories}

The usual proof of the downward L{\"o}wenheim-Skolem-Tarski
theorem goes through for logic without equality; that is, if
$\omega\leq\lambda\leq\kappa$ and $T$ has a model of cardinality
$\kappa$, then $T$ has a model of  cardinality $\lambda$. In fact,
every model for $L$ of cardinality $\kappa$ has an elementary
submodel of cardinality $\lambda$.

We have already seen from our examples that the corresponding
upward theorem fails; there are complete theories which have models of
cardinality $\omega$ but no larger, and complete theories which have models
of cardinality $2^\omega$ but no larger.  In this section we shall
see that $\omega$ and $2^\omega$ are the only cardinals where
this happens.  This shows that $(2^\omega)^+$ 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.

\begin{definition}  $T$ will be called {\bf bounded}
if the class of cardinalities of models of $T$ has an upper bound.
Otherwise we say that $T$ is {\bf unbounded}.
\end{definition}


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

\begin{lemma} \label{fullsat}
(i)  If $\CM$ is a fully saturated model $T$,
then every model of $T$ is elementarily embeddable in $\CM$, and
every fully saturated model of $T$ is isomorphic to $\CM$.

(ii)
$T$ is bounded if and only if it has a fully saturated model.
\end{lemma}

\pf (i) follows from the following two facts about a
$\kappa$-saturated model $\CM$ of $T$ of cardinality at most
$\kappa$ (see \cite{CK}, Section 5.1). Any $\kappa$-saturated
model of $T$ of cardinality at most $\kappa$ is isomorphic to
$\CM$, and any model of $T$ of cardinality at most $\kappa$ is
elementarily embeddable in $\CM$.

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

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


\begin{lemma}  \label{defeq}
Let $\CM$ be a model of $T$.  The following are equivalent:

(i) $T$ is bounded.

(ii) Every equivalence relation definable
without parameters in $\CM$ has finitely many equivalence classes.

(iii) Every equivalence relation definable
with parameters in $\CM$ has finitely many equivalence classes.
\end{lemma}

\pf  We first prove that (i) implies (iii). Suppose that (iii)
fails, so that
 $\CM$ has an equivalence relation with infinitely
many classes defined by a formula $\theta(x,y,\vec a)$ with parameters
$\vec a$.  Using the compactness theorem, for each cardinal $\kappa$,
$\CM$ has an elementary extension $\CN$ in which $\theta(x,y,\vec a)$
defines an equivalence relation with at least $\kappa$ classes.
Then $|N|\geq\kappa$, 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\in\omega$ which are definable without parameters in $\CM$.
By (ii), each $E_n$ has finitely many classes.
Since we are restricting attention to reduced models,
two elements of $\CM$ which are equivalent with respect to each $E_n$
are equal.  Therefore $|M|\leq 2^\omega$, and thus $T$ is bounded.
  \qed
\medskip

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 {\bf finitely branching tree} we mean a tree $\CT$
which has $\omega$ levels and finitely many nodes at each level.
We denote the set of all branches of $\CT$ by $B(\CT)$, and give $B(\CT)$
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\in\omega$ we give $B(\CT)^n$ the product topology.
By a {\bf clopen relation} on $B(\CT)$ we mean a relation which is clopen
on $B(\CT)^n$ for some $n$.
By a {continuous function of $n$ variables} on $B(\CT)$ we mean a
continuous function from $B(\CT)^n$ into $B(\CT)$.

\begin{proposition} \label{tree}  Suppose $T$ is bounded. Then
there is a finitely branching tree $\CT$ and
a fully saturated model $\CM$ of $T$ such that:

(i) $\CM$ has universe $B(\CT)$.

(ii)  A relation is definable with parameters in $\CM$ if and only
if it is clopen in $B(\CT)$.

(iii)  Each function of finitely many variables
defined in $\CM$ by a term is continuous on $B(\CT)$.

(iv)  A subset $M_0\subseteq M$ is the universe of an elementary substructure
of $\CM$ if and only if $M_0$ is dense in $B(\CT)$ and closed under each
function defined by a term.
\end{proposition}

\pf Let $E_n, 0<n<\omega$ be a list of all equivalence relations
definable without parameters in $\CM$, and let
$D_n=E_1\cap\cdots\cap E_n$.  By Lemma~\ref{defeq}, 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 $\CT$ be the finitely branching tree such that the set of
nodes of $\CT$ 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\in M$ with the branch of $\CT$ whose node
at level $n$ is the $D_n$-equivalence class of $x$.  It follows
from full saturation that each branch of $\CT$ is realized in
$\CM$. Thus $\CM$ has universe $B(\CT)$, and (i) holds.

(ii)  Since each equivalence relation $D_n$ is definable in $\CM$,
each equivalence class of $D_n$ is definable with parameters in $\CM$.
It follows that each clopen relation is definable with parameters
in $\CM$.

For the converse,
suppose for example that a ternary relation $R$ is defined by
the formula $\psi(x,y,z,\vec a)$ with parameters $\vec a$ in $\CM$.
Any definable equivalence relation in $\CM$ is refined by some $D_n$.
We may therefore choose $n$ large enough so that $D_n(b,c)$ implies
$$\forall y\forall z\forall\vec u\,[\psi(b,y,z,\vec u)\Leftrightarrow
\psi(c,y,z,\vec u)],$$
$$\forall x\forall z\forall\vec u\,[\psi(x,b,z,\vec u)\Leftrightarrow
\psi(x,c,z,\vec u)],$$
$$\forall x\forall y\forall\vec u\,[\psi(x,y,b,\vec u)\Leftrightarrow
\psi(x,y,c,\vec u)].$$
Now suppose that
$$D_n(x,x'), D_n(y,y'), D_n(z,z'), \mbox{ and } R(x,y,z).$$
It then follows in turn that $\psi(x,y,z,\vec a)$, $\psi(x',y,z,\vec a)$,
$\psi(x',y',z,\vec a)$,  $\psi(x',y',z',\vec a)$, and $R(x',y',z')$.
This shows that the relation $R$ is clopen with respect to the product
topology in $B(\CT)$, and (ii) is proved.

(iii)  Let $S$ be a clopen set in $B(\CT)$ and $\sigma(x,y,z)$ a term
of $L$.  By (ii), $S$ is definable by a formula $\psi(u,\vec a)$.
Then $\sigma^{-1}(S)$ is definable by the formula
$\psi(\sigma(x,y,z),\vec a)$, and is clopen in $B(\CT)$ by (ii).

(iv)  Let $\CM_0\prec\CM$.  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 $\CM$, $M_0$ must meet each equivalence class
of $D_n$.  Therefore $M_0$ is dense in $B(\CT)$.

For the converse, suppose $M_0$ is dense in $B(\CT)$ and closed
under each function defined by a term of $L$.  Then $\CM_0$ is a
substructure of $\CM$.  Suppose $\CM\models\exists x\,\psi(x,\vec
b)$ where $\vec b$ is in $M_0$.  Since $M_0$ is dense and the set
defined by $\psi(x,\vec b)$ in $\CM$ is nonempty and clopen, there
exists $a\in M_0$ such that $\CM\models\psi(a,\vec b)$.  Thus
$\CM_0\prec\CM$ by the criterion of Tarski and Vaught.  \qed
\medskip

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

\begin{corollary}  \label{3cases}

(i) $T$ is countably bounded if and only if
$T$ has a fully saturated model of cardinality $\omega$.

(ii) $T$ is uncountably bounded if and only if
 $T$ has a fully saturated model of cardinality $2^\omega$.

(iii)  $T$ is unbounded if and only if every model of $T$ has elementary
extensions of arbitrarily large cardinality.
\end{corollary}

\pf By Lemma~\ref{fullsat}, $T$ is bounded if and only if it has a
fully saturated model. By Proposition~\ref{tree}, 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^\omega$
branches.  We conclude that (i) and (ii) hold. Part (iii) follows
easily from Lemma~\ref{defeq}.  \qed


Recall that the {\bf Hanf number} of a logic is the least cardinal
$\kappa$ such that any theory which has a model of cardinality
at least $\kappa$ has models of arbitrarily large cardinality.

\begin{corollary}  The Hanf number of first order logic without
equality is $(2^\omega)^+$.  \qed
\end{corollary}

\section{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^\lambda$ of nonisomorphic models in each
uncountable cardinal $\lambda\leq 2^\omega$.

We first consider the case that $\lambda\leq 2^\omega<2^\lambda$.


\begin{theorem} \label{biglambda} Suppose $T$ is uncountably bounded and
$\lambda\leq 2^\omega<2^\lambda$.  Then
$T$ has $2^\lambda$ nonisomorphic models of cardinality $\lambda$.
\end{theorem}

\pf 
By Corollary~\ref{3cases}, $T$ has a fully saturated model $\CM$,
and $|\CM|=2^\omega$.  Let $\CA$ be a
countable elementary submodel of $\CM$.  
By Proposition~\ref{tree}, distinct elements of $M$ realize
distinct 1-types over $A$.
 
We will use the result of Shelah \cite{S}, Theorem VIII 1.5 (4).
It shows
that in logic with equality, if there are uncountably many 1-types over a
countable structure $\CA$, then there is a set $S$ of 1-types over $\CA$ 
such that $|S|=2^\omega$, and for each $R\subseteq S$ there is a
structure $\CB_R\succ\CA$  which realizes each $p\in R$ and omits each
$p\in S\setminus R$.  The proof of this result still works in logic without
equality.  It follows that there is a family of structures 
$K=\{\CB_R: R\in [S]^\lambda\}$ such that $\CA\prec\CB_R\prec\CM$,
$|\CB_R|=\lambda$, and for all distinct $Q,R\in[S]^\lambda$, there is no
isomorphism from $\CB_Q$ to $\CB_R$ which is the identity on $A$.

The family $K$ has cardinality $2^\lambda$, and the relation of being
isomorphic partitions $K$ into equivalence classes.  To complete the proof
it suffices to show that there are $2^\lambda$ different equivalence
classes.  Suppose not. Then there is an equivalence class $K_0$ of
cardinality $2^\lambda$.  Choose $\CC\in K_0$, and for each $\CB_R\in K_0$
choose an isomorphism $f_R:\CB_R\cong\CC$.  There are only $2^\omega$
different mappings from $A$ into $C$, and since $2^\omega < 2^\lambda$,
there are distinct $\CB_Q,\CB_R\in 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 $\CB_Q, \CB_R$ are isomorphic by a mapping which
is the identity on $A$, and we have a contradiction.
  \qed



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

\begin{theorem}  \label{manymodels}
Suppose $T$ is uncountably bounded.
Then $T$ has a family $K$ of models such that $K$ has
cardinality $2^\omega$, each $\CM\in K$ has cardinality $2^\omega$,
and whenever $\CM\in K, \CN\in K$, and $\CM\neq\CN$, no uncountable
elementary submodel of $\CM$ is elementarily embeddable in $\CN$.
\end{theorem}


 Given two distinct branches $b,c$ of a finitely branching
tree $\CT$, let $\delta(b,c)$ be the level of the highest node on $b\cap c$.
We say that a mapping $h$ from a subset $Y\subseteq B(\CT)$ into $B(\CT)$ is
{\bf level-preserving} if $\delta(h(b),h(c))=\delta(b,c)$ for all  distinct
$b,c\in Y$.  In the fully saturated model $\CM$ of Proposition~\ref{tree},
the relation
$\delta(x,y)=n$ says that $n$ is the least $m$ for which $\neg E_m(x,y)$,
and hence is definable in $\CM$ without parameters.  It follows that every
elementary embedding from an elementary submodel of $\CM$ into $\CM$
is level-preserving.  Therefore
Theorem~\ref{manymodels} is a consequence of
Proposition~\ref{tree} and the following topological result on finitely branching
trees.


\begin{theorem} \label{level}
Let $\CT$ be a finitely branching tree with uncountably
many branches, and let $\ff$ be a countable set of continuous functions of
finitely many variables on $B(\CT)$.  Then there is a family
$\{X_\al\su B(\CT):\; \al<\cc\}$ such that each $X_\al$ is
a dense subset of $B(\CT)$
of size continuum which is closed under all $f\in \ff$ and
for each distinct $\al, \be$, there is no
level-preserving mapping from an uncountable subset
of $X_\al$ into $X_\be$.
\end{theorem}


\pf
For simplicity, we first consider the case that
$$\CT=\tr \rmand B(\CT)=\cs$$
Later we indicate how to do the more general case.

In this case

\begin{definition}
For any $x,y\in \cs$
 $$\de(x,y)=\min\{n\in\omega:x(n)\not=y(n)\}$$
\end{definition}

\begin{definition}
For any set $X\su\cs$ define
$$\de(X)=\{\de(x,y):\;\; x,y\in X\}$$
Clearly, $\de(X)$ is infinite for any infinite $X$.
\end{definition}


We will construct $X_\al$ and $A_\al\su\om$ such that
the $A_\al$ are pairwise almost disjoint, i.e.
$$A_\al\cap A_\be \mbox{ is finite }$$
whenever $\al\not=\be$, and for any $\al$ we can decompose
$X_\al$ into countable many sets
$$X_\al=\bigcup\{X^n_\al:\;n\in\om\}$$
such
that $\de(X^n_\al)\su A_\al$ for each $n<\om$.  This implies that
there can be no level-preserving map from any uncountable subset
of $X_\al$ into $X_\be$.   For suppose there were a level-preserving
bijection $h:Y\to Z$ with $Y\su X_\al$ and $Z\su X_\be$.
By cutting down
the uncountable set $Y$ we may assume that there exists $n$ and $m$
such that $Y\su X_\al^n$ and $Z\su X_\be^m$.  Level preserving
implies that $\de(Y)=\de(Z)$, but then
$$\de(Y)=\de(Z)\su A_\al\cap A_\be,$$
contradicting the fact that $A_\al$ and $A_\be$ 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 $\ff$ is empty.  In this case
we may take the family $\{A_\al:\al<\cc\}$
to be any family
of infinite pairwise almost disjoint subsets of $\om$.  Then
define
$$X_\al=\{x\in\cs: \forall^\infty l\;\;
(x(l)=1 \imp l\in A_\al) \}$$
$\forall^\infty l$ means ``for all but finitely many $l$''.
It is easy to see that $X_\al$ is dense.  Also, for any
$n\in \om$ and any $s\in 2^n$, if we define
$$X_\al(s)=\{x\in\cs: s\su x \rmand \forall l>n\;\;
(x(l)=1\imp l\in A_\al)\}$$
then
$$\de(X_\al(s))\su\{l\in A_\al:\;\; l\geq n\} \rmand
X_\al =\bigcup_{s\in\tr}X_\al(s).$$


Now we consider the general case.
We may assume that
$\ff$
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\in\tr$ there is an operation $f\in\ff$ such that
$f$ maps $\cs$ one-to-one into $[s]$, where

\begin{definition}
For $s\in\tr$ define $[s]=\{x\in\cs:\;\; s\su x\}$.
\end{definition}

Thus it is unnecessary
to guarantee that $X_\al$ is dense; we will only need to
construct $Y_\al\su\cs$ of cardinality continuum and then
let $X_\al$ be the closure of $Y_\al$ under the operations
of $\ff$.

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\in \ff$
and $\vec{x},\vec{y}\in Y_\al^n$
\par \medskip If
$$k_m<\;\; \de(f(\vec{x}),f(\vec{y}))\;\; <k_{m+1}$$
\par then $k_m<\de(u,v)<k_{m+1}$ for some $u,v$ from
$\vec{x}\cup\vec{y}$.

\medskip

\begin{definition}
For $s\in 2^l$ and $l<k$, let $\zz{s,k}\in 2^k$ be the
unique element of $2^k$ such that $s\su \zz{s,k}$ and $\zz{s,k}(i)=0$
for all $i$ with $l\leq i<k$.  In other words, $\zz{s,k}$ is the
sequence of length $k$ gotten by extending $s$ with zeros.
\end{definition}
\bigskip

\begin{lemma} \label{step1}
Suppose $F\su \ff$ is finite and $k<\om$.
Then there exists $l>k$ such that
for every $n$-ary $f\in F$ and
$(r_i\in 2^k: i<n)$ there exists a $t\in 2^k$ such that
$$f(\prod_{i<n}[\zz{r_i,l}])\su [t]$$
\end{lemma}
\pf
This is easy, just use the continuity of the $f$'s.
\qed


Now write $\ff=\cup\{F_n : n<\om\}$ as an increasing union of finite
sets.  By iteratively
applying the last  lemma we get:

\medskip
There exist increasing sequences
$$\la k_m\in\om :\;\; m<\om\ra
\rmand \la l_m\in\om :\;\; m<\om\ra$$
with $k_m<l_m<k_{m+1}$ satisfying the following conditions:

Let $$L=\{l_m:m<\om\} \rmand
T=\{s\in\tr: \forall l \;\;\left(s(l)=1 \imp l\in L\right)\}.$$
Then for any $m<\om,$
 \begin{enumerate}
 \item For every $n$-ary $f\in F_m$
  and $\la s_i \in T\cap 2^{l_m}:\;i<n\ra $
  there exists $t\in 2^{k_m}$
  such that $$f(\prod_{i<n}[s_i])\su [t].$$
 \item For any $n$-ary $f \in F_m$ and 
    $$(r_i\in T\cap 2^{k_{m+1}}): i<n) \rmand
    (t_i\in T\cap 2^{k_{m+1}}): i<n),$$
  \par if there exists $k\geq k_{m+1}$ with the property that
 there are distinct
   $r,t\in 2^{k}$ with
   $$f(\prod_{i<n} [\zz{r_i,k}])\su [r] \rmand
   f(\prod_{i<n} [\zz{t_i,k}])\su [t],$$
   then $k_{m+1}$ already has this property.
\end{enumerate}
\medskip

This follows from the previous lemma.  First we get $l_m>k_m$ by
applying Lemma \ref{step1} with $k=k_m$ and then we get $k_{m+1}$
as the maximum of finitely many $k$'s.

Given $\la B_\al:\al<\cc\ra$ infinite pairwise almost disjoint subsets,
define $Y_\al$ as follows:
$$Y_\al=\{x\in\cs: \forall l<\om\;\;
(x(l)=1\imp\exists m\in B_\al \;\; l=l_m \;)\}$$
and define
$$A_\al=\{i:\; \exists m\in B_\al \;\; k_m\leq i< k_{m+1}\}.$$

\begin{lemma}\label{last}
Suppose $m_0\in B_\al$,     $f \in F_{m_0}$ is $n$-ary,
and $\vec{x},\vec{y}\in Y_\al^n$.
Then $$\de(f(\vec{x}),f(\vec{y})) \;\;\in  \;\;A_\al\cup k_{m_0+1}$$
\end{lemma}
\pf
Suppose for contradiction that
$$k_m\leq \;\;\de(f(\vec{x}),f(\vec{y}))\;\;<k_{m+1}$$
for some $m>m_0$ such that $m\notin B_\al$. By our construction $l_m$ has
the following property:

\begin{quote}
Let $r_i=x_i\res{l_m}$ and let $s_i=y_i\res{l_m}$ for each $i<n$.  Then
there exists $r,s\in 2^{k_m}$ such that
$$f(\prod_{i<n}[r_i])\su [r]  \rmand  f(\prod_{i<n}[s_i])\su [s]$$
\end{quote}



Because $k_m\leq \;\;\de(f(\vec{x}),f(\vec{y}))$, it must be that $r=s$.

Let $m_1\geq m_0$ be the largest element of $B_\al$
such that $m_1\leq m$.  So $m_0\leq m_1<m$ and note that there is
there is no splitting going on in
$Y_\al$ between $l_{m_1}+1$ and $k_{m+1}$, i.e., if $u,v\in Y_\al$, then
$\de(u,v)\leq l_{m_1}$ or $\de(u,v)\geq l_{m+1}$.

Since $m\notin B_\al$  and $x_i,y_i\in Y_\al$
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^\pr,s^\pr \in 2^{k_{m+1}}$

$$f(\prod_{i<n}[x_i\res{l_{m+1}}])\su [r^\pr]  \rmand
f(\prod_{i<n}[y_i\res{l_{m+1}}])\su [s^\pr]$$

Since we are assuming $\de(f(\vec{x}),f(\vec{y}))<k_{m+1}$ it
must be that $r^\pr\not= s^\pr$, 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\in B_\al$.
\qed

It follows from Lemma \ref{last} that for any
$t\in 2^{k_{m_0+1}}$ and $n$-ary $f\in F_{m_0}$ that
$$\de\left([t]\cap f(Y_\al^n))\right)\su A_\al$$
and since the closure of $Y_\al$ under the operations of $\ff$
can be written as a countable union of such sets, Theorem \ref{level}
has been proven for the special case that $B(\CT)=\cs$.

Now we indicate the modifications necessary to prove the Theorem in general.
Let $\CT^\pr$ be the subtree of $\CT$ consisting of all those nodes of
$\CT$ which have uncountably many branches thru them.  Clearly,
$$Q=B(\CT)\setminus B(\CT^\pr)$$
is countable.  Without loss of generality, we may assume that
$\ff$ also contains all operations which can be obtained by substituting
elements of $Q$, e.g., if $f\in \ff$ is binary and $a\in Q$ then
the unary operation $g(x)=f(x,a)$ would also be in $\ff$.  Thus
we may choose $Y_\al\su B(\CT^\pr)$ and then take
$$X_\al=Q \cup \bigcup\{f(Y_\al^n): f\in\ff, \;\; n\mbox{-ary for some }
n\in\om\}$$
and then $X_\al$ will be closed under the operations of $\ff$.

In the proof, we need to define $\zz{s,k}$ where
$s\in \CT^\pr$ is at level $l$ and $k\geq l$.
Put a linear ordering on $\CT^\pr$
and then take $\zz{s,k}$ to be the node of
$\CT^\pr$ 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^\pr>l_n$ so that
\begin{itemize}
 \item each $s\in \CT^\pr$ at level $l_n$ has at least two
 incompatible extension in $\CT^\pr$ at level $l_n^\pr$ and
 \item $k_n<l_n<l_n^\pr <k_{n+1}$
\end{itemize}
Then we would take $Y_\al=B(\CT_\al)$, where $\CT_\al$ is
the subtree of $\CT^\pr$, where nodes can be extended arbitrarily
between levels $l_n$ and $l_n^\pr$ if $n\in B_\al$, but otherwise
must be extended by using $\zz{s,k}$, i.e., the leftmost path.
The choice of $k_n$ is exactly the same and so is the rest of
the proof.
\qed

Combining Theorems \ref{biglambda} and \ref{manymodels}, we have

\begin{theorem}  Suppose $T$ is  uncountably bounded.  Then for
every uncountable cardinal $\lambda\leq 2^\omega$, $T$ has
$2^\lambda$ nonisomorphic models of cardinality $\lambda$.
\end{theorem}

\begin{corollary} \label{notcat} If $T$ is uncountably bounded,
then for every uncountable cardinal $\kappa$, $T$ is not
$\kappa$-categorical.  \qed
\end{corollary}


\section{The {\L}o\'{s} Conjecture}

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

Recall that $T$ is $\kappa$-stable if for every model $\CM$ of $T$
and every subset $X\subseteq M$ of cardinality $\kappa$, the
theory $Th(\CM_X)$ has $\kappa$ 1-types.

\begin{proposition} If $T$ is $\lambda$-categorical in some uncountable
cardinal $\lambda$, then $T$ is $\omega$-stable.
\end{proposition}

\pf By Corollary~\ref{notcat}, $T$ is unbounded, so by
Lemma~\ref{defeq}, 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 \cite{CK}) but replace
equality by $E(x,y)$.  \qed

\begin{lemma}  \label{almosteq} If $T$ is $\omega$-stable, then for
 every model
$\CM$ of $T$, regular cardinal $\lambda>\omega$, and set
$Y\subseteq M$ of cardinality $\lambda$, there is an equivalence
relation $E(x,y)$ which is definable in $T$ without parameters
 such that the
restriction of $E^\CM$ to $Y\times Y$ has $\lambda$ equivalence
classes.
\end{lemma}

\pf  Suppose the result fails for a model $\CM$ of $T$ and set
$Y\subseteq M$ of regular cardinality $\lambda>\omega$.  Let $E_n,
0<n<\omega$ be a list of all equivalence relations definable
without parameters in $T$, and let $D_n$ be the restriction of
$E_1\cap\cdots\cap E_n$ to $Y\times Y$. Let $\CT$ 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 $\CT$ {\bf
large} if there are at least $\lambda$ branches through $t$. Then
the root of $\CT$ is large, but at each level, $\CT$ has fewer
than $\lambda$ nodes. It follows that for each large node $t$ of
$\CT$ there are two disjoint large nodes above $t$.  But then
$\CT$ has a subtree with countably many nodes and uncountably many
branches. Therefore $\CM$ has a countable subset $X$ such that
there are uncountably many types over $\CM_X$, so $T$ is not
$\omega$-stable.  \qed

\begin{proposition}  If $T$ is $\omega$-stable, then $T$ is
$\kappa$-stable for every infinite cardinal $\kappa$.
\end{proposition}

\pf  Suppose $T$ is not $\kappa$-stable, so $T$ has a model $\CM$
which realizes $\kappa^+$ types over some set $X\subseteq M$ of
power $\kappa$.   By Lemma~\ref{almosteq}, there is an equivalence
relation $E(x,y)$ definable in $T$ and a subset $Y\subseteq M$
such that $|Y|=\kappa^+$, the restriction of $E^\CM$ to $Y\times
Y$ is the equality on $Y$, and any two distinct elements $a,b\in
Y$ realize different types in $\CM_X$. One can now repeat the
proof of the corresponding result for equality logic (Lemma 7.1.3
in \cite{CK}) but with the relation $E(x,y)$ in place of equality.
\qed

\begin{definition}  A model $\CM$ of $T$ is said to be {\bf
primary over} a subset $A\subseteq M$ if there is a sequence
 $\langle b_\beta :\beta <\alpha\rangle$
 of elements of $M$ such that

 (i)  $A\cup\{ b_\beta :\beta <\alpha\}$ generates $\CM$,

 (ii)  For each formula $\varphi(y)$ in
 $L_A\cup\{b_\beta:\beta <\alpha\}$
 there exists $\gamma <\alpha$ such that
 $$(\CM_A,b_\beta)_{\beta <\alpha}\models\exists y
 \varphi(y)\Rightarrow\varphi(b_\gamma).$$

 (iii)  For each $\beta <\alpha$, the 1-type of $b_\beta$ in
 $Th((\CM_A,b_\beta)_{\beta <\alpha})$
 is isolated, (i.e. $b_\beta$ satisfies a maximal consistent
 formula).
 \end{definition}

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

 \begin{lemma} \label{primary} Suppose $T$ is $\omega$-stable.  Then for
  every model $\CM$ of $T$ and every set $A\subseteq M$, $\CM$ has an
elementary  submodel which is primary over $A$.
 \end{lemma}

 \pf  Since $T$ is $\omega$-stable, a binary tree argument
 shows that for every $B\subseteq M$, every formula $\varphi(y)$
 which is consistent with $Th(\CM_B)$ is implied by a formula
 $\psi(y)$ which is maximal consistent with $Th(\CM_B)$.  By
 transfinite recursion, one can build a sequence
 $\langle b_\beta :\beta <\alpha\rangle$
 in $M$ such that conditions (ii) and (iii) in the above
 definition hold.  Condition (ii) implies that $\alpha >0$.  It follows
  that the set
  $A\cup\{b_\beta:\beta <\alpha\}$ is nonempty,  and generates a
  submodel $\CM_0$ of $\CM$ which is an elementary
  submodel and is  primary over $A$.
\qed

We need one more lemma, which is the analogue of Lemma 7.1.13 in
\cite{CK} for logic without equality.

\begin{lemma} \label{minimal} Suppose $T$ is $\omega$-stable and $\CM$ is an
uncountable model of $T$.  Then there is a proper elementary
extension $\CN\succ\CM$ such that every countable set of formulas
$\Gamma(y)$ which is realized in $\CN_M$ is realized in $\CM_M$.
\end{lemma}

\pf  By $\omega$-stability and a binary tree argument, there is a
definable set $D$ in $\CM_M$ such that $D$ is uncountable, but for
any definable subset $C\subseteq D$, either $C$ or $D\setminus C$
is countable.  By Lemma~\ref{almosteq}, 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~\ref{primary}, and the proof of Lemma 7.1.16 in
\cite{CK} with $E(x,y)$ in place of equality, to obtain the
required model $\CN\succ\CM$. \qed

\begin{theorem} ({\L}o\'{s} Conjecture)  If $T$ is
$\lambda$-categorical for some uncountable cardinal $\lambda$,
then $T$ is $\kappa$-categorical for every uncountable cardinal
$\kappa$.
\end{theorem}

\pf  We have shown that $T$ is unbounded and stable in every
infinite cardinal. Now the usual proof that $T$ has an
$\omega_1$-saturated model in every uncountable cardinal goes
through (see \cite{CK}, Lemma 7.1.6). Finally, one can use
Lemma~\ref{minimal} and the argument in \cite{CK}, p. 494, to show
that $T$ is $\kappa$-categorical.  \qed


\begin{thebibliography}{22}

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

\bibitem[CDJ]{CDJ}
E.Casanovas, P.Dellunde, R.Jansana,
{\it On elementary equivalence for equality-free logic},
Notre Dame Journal of Formal Logic, 37(1996), 506-522.

\bibitem[CK]{CK}
C.C.Chang, H.J.Keisler, {\bf Model theory}, North-Holland 1990.

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

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

\bibitem[K]{K}  H.J.Keisler, {\it Logic with the quantifier
``there exist uncountably many''}, Ann. Math. Logic 1 (1970),
1-93.

\bibitem[\L]{L} J. {\L}o\'{s}, {\it On the categoricity in power of
elementary deductive systems and some related problems}, Colloq.
Math 3 (1954), 58-62.

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

\bibitem[S]{S}  S. Shelah, {\it Classification Theory}, North-Holland
Elsevier.  First edition 1978, second edition 1990.

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

\end{thebibliography}

\newpage
\begin{center}
  Addresses
\end{center}

\begin{flushleft}
 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/$\sim$keisler         \\
 home page: http://www.math.wisc.edu/$\sim$miller         \\
\end{flushleft}

\end{document}