%% 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, nn\;\;
(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_mk$ such that
for every $n$-ary $f\in F$ and
$(r_i\in 2^k: ik_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}))\;\;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 $il_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\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,
00$. 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}