\chapter{Relations between structures}

\section{Definitions}

Let $\str A$ and $\str B$ be $\lang$-structures; we consider some
possible relations between them.

The two structures are called \defn{elementarily equivalent}, and we
write
\begin{equation*}
  \str A\equiv\str B,
\end{equation*}
if $\Th{\str A}=\Th{\str B}$.  Immediately, the relation $\equiv$, or
  \defn{elementary equivalence}, is an equivalence-relation.

All models of a complete theory are elementarily
  equivalent, and
first-order logic provides no means to distinguish between
  elementarily equivalent structures.  We shall see \emph{other}
  possible ways to distinguish between them.

Various functions between (universes of) structures are possible.  To
describe them, it is convenient to use the following convention.  If
$h$ is a function from $A$ to $B$, we also 
understand $h$ as the function from $A^n$ to $B^n$ given by
\begin{equation}\label{eqn:h}
  h(a_0,\dots,a_{n-1})=(h(a_0),\dots,h(a_{n-1})),
\end{equation}
for each $n$ in $\varN$.
In particular, as a function from $A^0$ to $B^0$, $h$ is $\{(0,0)\}$.

An \defn{embedding} of $\str A$ in $\str B$ is an \emph{injection} $h$
from $A$ to $B$ such that:
\begin{mylist}
  \item
$h(c^{\str A})=c^{\str B}$ for all constants $c$ in $\lang$;
\item
$h\setim(R^{\str A})=h\setim(A^n)\cap R^{\str B}$, that is,
  \begin{equation*}
      \tuple a\in R^{\str A}\Iff h(\tuple a)\in R^{\str B}
  \end{equation*}
 for all $\tuple
  a$ in $A^n$, for all
  $n$-ary predicates $R$ in $\lang$, for all $n$ in $\varN$;
\item
$h\circ f^{\str A}=f^{\str B}\circ h$, that is,
  \begin{equation*}
      h(f^{\str A}(\tuple a))=f^{\str B}(h(\tuple a))
  \end{equation*}
 for all $\tuple a$
  in $A^n$, for all $n$-ary function-symbols $f$ in $\lang$, for all
  $n$ in $\varN$.
\end{mylist}
To express that $h$ is an embedding of $\str A$ in $\str B$, we can
write
\begin{equation*}
  h:\str A\To\str B.
\end{equation*}
This then means, precisely,
\begin{align}\label{eqn:unnested-c}
  \str A\models c=a&\Iff \str B\models c=h(a),\\ \label{eqn:unnested-R}
\str A\models Ra_0\dotsb a_{n-1}&\Iff \str B\models Rh(a_0)\dotsb
h(a_{n-1}),\\ \label{eqn:unnested-f}
\str A\models fa_0\dotsb a_{n-1}=b&\Iff \str B\models fh(a_0)\dotsb
h(a_{n-1})=h(b), 
\end{align}
where $c$, $R$ and $f$ are symbols in $\lang$ as usual, and $a_k$ and
$b$ are in $A$.

\begin{example}
  The map $x\mapsto x/1$ is an embedding of the ring $\Z$ in the field
  $\Q$. 
\end{example}

Using the notions of elementary equivalence and embeddings, we can
define several useful derivative notions:
\begin{mylist}
  \item
$\str A$ is a \defn{substructure of $\str B$}, and $\str B$ is an
    \defn{extension of $\str A$}, if  $A\included B$ and
    $\id_A:\str A\to \str B$; in this case we write
    \begin{equation*}
      \str A\included\str B.
    \end{equation*}
\item
$\str A$ is an \defn{elementary substructure of $\str B$}, and $\str
  B$ is an \defn{elementary extension of $\str A$}, if $\str
  A\included\str B$ and $\str A_A\equiv\str B_A$; in this
  case we write
  \begin{equation*}
    \str A\elsub\str B.
  \end{equation*}
\item
If $h:\str A\to\str B$ and $h$ is a \emph{surjection} onto $B$, then
$h$ is called an \defn{isomorphism} from $\str A$ to $\str B$, and we
can write
\begin{equation*}
  h:\str A\overset{\cong}{\To}\str B.
\end{equation*}
\item
If an isomorphism from $\str A$ to $\str B$ exists, then $\str A$ is
\defn{isomorphic} to $\str B$, and we can write
\begin{equation*}
  \str A\cong\str B;
\end{equation*}
the relation $\cong$ can be called \defn{isomorphism}.

\end{mylist}

\begin{lemma}
Isomorphism is an equivalence-relation.  If $h:\str
  A\overset{\cong}{\to}\str B$, then $h\inv:\str
  B\overset{\cong}{\to}\str A$. 
\end{lemma}

\begin{proof}
  \textbf{Exercise.}
\end{proof}

\begin{lemma}
  If $h:\str A\to\str B$, then $h(A)$ is the universe of a structure
  $h(\str A)$ such that $h:\str A\overset{\cong}{\to} h(\str A)$ and
  $h(\str A)\included\str B$.
\end{lemma}

\begin{proof}
  \textbf{Exercise.}
\end{proof}

We can now define one more notion, letting $h(\str A)$ be as in the
last lemma: 

\begin{mylist}\setcounter{mylist}{4}
\item  
If $h:\str A\to\str B$ and $h(\str A)\elsub\str B$, then $h$ is an
\defn{elementary embedding} of $\str A$ in $\str B$, and we can write
\begin{equation*}
  \str A\overset{\equiv}{\To}\str B.
\end{equation*}
\end{mylist}

\section{Characterizations}

We can give the following characterization of the relations $\equiv$
and $\elsub$:
\begin{align*}
      \str A\equiv\str B&\Iff\str B\models\Th{\str A};\\
\str A\elsub\str B&\Iff\str A\included\str B\amp \str B_A\models
\Th{\str A_A}. 
\end{align*}
To characterize $\included$ in this style, we let the \defn{diagram of
  $\str A$} be the set of \emph{open} sentences of $\Th{\str A_A}$;
  this set can be denoted
  \begin{equation*}
    \diag\str A.
  \end{equation*}


\begin{theorem}\label{thm:isom}\label{thm:elsub}
Suppose $h:A\to B$, and $\str
B^*$ is the expansion of $\str B$ to $\lang(A)$ such that
\begin{equation}\label{eqn:B*}
  a^{\str B^*}=h(a)
\end{equation}
for all $a$ in $A$.
Then
\begin{gather}\label{eqn:diag}
  \str B^*\models\diag\str A\Iff h:\str A\to\str B;\\ \label{eqn:eldiag}
\str B^*\models\Th{\str A_A}\Iff h:\str A\overset{\equiv}{\to}\str B.
\end{gather} 
In particular, 
\begin{equation*}
  \str B\models\diag\str A\Iff\str A\included\str B.  
\end{equation*} 
Finally,
\begin{equation}\label{eqn:isom-to-equiv}
  \str A\cong\str B\implies\str A\equiv\str B.
\end{equation}
\end{theorem}

\begin{proof}
Under the assumptions on $h$ and $\str B^*$, we have
\begin{equation}\label{eqn:B*h}
  \str B^*\models\phi(\tuple a)\Iff \str B\models\phi(h(\tuple a))
\end{equation}
for all $\tuple a$ in $A^n$ and all $n$-ary formulas $\phi$ of
$\lang$, for all $n$ in $\varN$.
The characterization of embedding in~\eqref{eqn:unnested-c}, 
\eqref{eqn:unnested-R}, 
and~\eqref{eqn:unnested-f} establishes the forward direction
of~\eqref{eqn:diag}.  Hence we also get the forward direction
of~\eqref{eqn:eldiag}.  To establish the reverse direction
of~\eqref{eqn:diag},
suppose $h:\str A\to\str B$.  It will be enough to show
\begin{equation}%\label{eqn:isom}
  \str A\models\phi(\tuple a)\Iff\str B\models\phi(h(\tuple a)), \text{
  for all $n$-tuples $\tuple a$ from $A$,} 
\end{equation}
for all $n$-ary open formulas
$\phi$ of $\lang$, for all $n$ in $\varN$.  If $h$ is also surjective
onto $B$, then we shall show~\eqref{eqn:isom} for \emph{all} formulas
$\phi$; this will give~\eqref{eqn:isom-to-equiv} as a special case, as
well as the reverse direction of~\eqref{eqn:eldiag}.

Note that \eqref{eqn:isom} can be re-formulated in other ways,
according to taste:
\begin{equation}\label{eqn:isom}
  \tuple a\in\phi^{\str A}\Iff h(\tuple a)\in\phi^{\str B}, \text{
  for all $n$-tuples $\tuple a$ from $A$,} 
\end{equation}
or more simply
\begin{equation}\label{eqn:isom-alt}
  h\setim(\phi^{\str A})=h\setim(A^n)\cap\phi^{\str B}.
\end{equation}
%Let us work with this last formulation.
To prove it, we first establish by induction that
\begin{equation}\label{eqn:isom-terms}
h\circ t^{\str A}=t^{\str B}\circ h
\end{equation}
for all terms $t$ of $\lang$.
To do so, we note:
\begin{mylist}
\item
  \eqref{eqn:isom-terms} is true by definition if $t$ is a constant or
  variable;
\item
if \eqref{eqn:isom-terms} is true when $t\in\{u_0,\dots,u_{n-1}\}$,
and now $t$ is $fu_0\dotsb u_{n-1}$, then
\begin{align*}
  h\circ t^{\str A}
&=h\circ f^{\str A}\circ(u_0{}^{\str A},\dots,u_{n-1}{}^{\str
    A})&&\text{[by def'n of $t^{\str A}$]}\\
&=f^{\str B}\circ h\circ(u_0{}^{\str A},\dots,u_{n-1}{}^{\str
    A})&&\text{[by def'n of $\included$]}\\
&=f^{\str B}\circ (h\circ u_0{}^{\str A},\dots,h\circ u_{n-1}{}^{\str
    A})&&\text{[by \eqref{eqn:h}]}\\
&=f^{\str B}\circ (u_0{}^{\str B}\circ h,\dots,u_{n-1}{}^{\str B}\circ
  h)&&\text{[by inductive hyp.]}\\
&=f^{\str B}\circ (u_0{}^{\str B},\dots,u_{n-1}{}^{\str B})\circ h\\
&=t^{\str B}\circ h.&&\text{[by def'n of $t^{\str A}$]}
\end{align*}
\end{mylist}
Therefore \eqref{eqn:isom-terms} holds for all $t$.  Now we turn to
\eqref{eqn:isom-alt}.  To prove it for open formulas, we observe:
\begin{mylist}
  \item
If $\phi$ is $t_0=t_1$ for some terms $t_i$, then
\begin{align*}
  \tuple a\in\phi^{\str A}
&\Iff t_0{}^{\str A}(\tuple a)=t_1{}^{\str A}(\tuple a) && \text{ [by
      definition of $\phi^{\str A}$]}\\
&\Iff h(t_0{}^{\str A}(\tuple a))=h(t_1{}^{\str A}(\tuple a)) &&
  \text{ [since $h$ is injective]}\\
&\Iff t_0{}^{\str B}(h(\tuple a)))=t_1{}^{\str B}(h(\tuple a))) &&
  \text{ [by \eqref{eqn:isom-terms}]}\\
&\Iff
  h(\tuple a)\in\phi^{\str B}.&&\text{ [by definition of $\phi^{\str B}$]}
\end{align*}
\item
If $\phi$ is $Rt_0\dotsb t_{n-1}$ for some terms $t_i$ and predicate
$R$, then:
\begin{align*}
  \tuple a\in \phi^{\str A}
&\Iff (t_0{}^{\str A}(\tuple a),\dots,t_{n-1}{}^{\str A}(\tuple a))\in
  R^{\str A}&&\text{ [by def'n of $\phi^{\str A}$]}\\
&\Iff h(t_0{}^{\str A}(\tuple a),\dots,t_{n-1}{}^{\str A}(\tuple a))\in
  R^{\str B}&&\text{ [by def'n of isom.]}\\
&\Iff
(t_0{}^{\str B}(h(\tuple a)),\dots,t_{n-1}{}^{\str B}(h(\tuple a)))\in
  R^{\str B}&&\text{ [by \eqref{eqn:isom-terms}]}\\
&\Iff h(\tuple a)\in \phi^{\str B}.&&\text{ [by def'n of
      $\phi^{\str B}$]}
\end{align*}
\item
If \eqref{eqn:isom-alt} holds when $\phi$ is $\chi$, and now $\phi$ is
$\lnot\chi$, then:
\begin{align*}
  \tuple a\in\phi^{\str A}
&\Iff \tuple a\notin\chi^{\str A}&&\text{ [by def'n of $\phi^{\str
	A}$]}\\
&\Iff h(\tuple a)\notin\chi^{\str B}&&\text{ [by inductive
      hypothesis]}\\
&\Iff h(\tuple a)\in\phi^{\str B}.&&\text{ [by def'n of $\phi^{\str
	B}$]}\\
\end{align*}
\item
Similarly, if \eqref{eqn:isom-alt} holds when $\phi$ is $\chi$ or $\psi$,
and now $\phi$ is $(\chi\to\psi)$, then:
\begin{align*}
  \tuple a\notin\phi^{\str A}
&\Iff \tuple a\in\chi^{\str A}\amp \tuple a\notin\psi^{\str A}&&\text{
    [by def'n of $\phi^{\str 
	A}$]}\\
&\Iff h(\tuple a)\in\chi^{\str B}\amp h(\tuple a)\notin\psi^{\str
    B}&&\text{ [by inductive  hypothesis]}\\
&\Iff h(\tuple a)\notin\phi^{\str B}.&&\text{ [by def'n of $\phi^{\str
	B}$]}\\
\end{align*}
\end{mylist}
Finally, to establish~\eqref{eqn:isom-alt} in case $h$ is surjective,
suppose \eqref{eqn:isom-alt} holds when $\phi$ is an $(m+1)$-ary
formula $\chi$, 
and now $\phi$ is the $m$-ary 
$\Exists{\varble_m}\chi$.  We have
\begin{align*}
  \tuple a\in\phi^{\str A}
&\Iff (\tuple a,b)\in\chi^{\str A}\text{ for some $b$ in $A$}\\
&\Iff (h(\tuple a),h(b))\in\chi^{\str B}\text{ for some $b$ in $A$}\\
&\Iff (h(\tuple a),c)\in\chi^{\str B}\text{ for some $c$ in $A$}\\
&\Iff h(\tuple a)\in\phi^{\str B}
\end{align*}
(Note how the surjectivity of $h$ was used.)  This completes the
proof. 
\end{proof}

\begin{corollary}\label{cor:QE-MC}
  If $T$ is a theory admitting quantifier-elimination, then all
  embeddings of models of $T$ are elementary embeddings.
\end{corollary}

\begin{proof}
  If $T$ admits quantifier-elimination and $\str A\models T$, then
  $\diag\str A\models\Th{\str A_A}$.
\end{proof}

Model-theory is interesting because not all elementarily equivalent
structures are isomorphic:

\begin{example}
  We know that $\Th{\Q,<}=\TO^*$.  Since also $(\R,<)\models\TO^*$, we
  have $(\R,<)\equiv(\Q,<)$; however, $(\Q,<)\not\cong(\R,<)$, simply
  because $\R$ is uncountable, so there is no bijection at all between
  $\Q$ and $\R$.
\end{example}

\section{Categoricity}

The \defn{cardinality} of a structure $\str A$ is the cardinality
$\size A$ of its universe $A$.  Let $\kappa$ be an infinite
cardinality. 
A theory $T$ is called
\defn{$\kappa$-categorical} if
\begin{mylist}
  \item
$T$ has a model of cardinality $\kappa$;
\item
all models of $T$ of cardinality $\kappa$ are isomorphic (to each
other). 
\end{mylist}

\begin{example}\label{example:TO*}
  We shall prove later, in Theorem~\ref{thm:Cantor}, that $\TO^*$ is
  $\varN$-categorical. 
\end{example}

A theory is \defn{totally categorical} if it is $\kappa$-categorical
for each $\kappa$.

\begin{example}\label{example:empty}
In the empty signature, structures are pure sets, and isomorphisms are
just bijections.  Hence, if $\lang=\emptyset$, then
$\Cn{\emptyset}$ 
is totally categorical.
\end{example}


There are sentences $\sigma_n$ (where $n>0$) in the empty signature
such that, for all theories $T$ and structures $\str A$ of some common
signature,
\begin{equation*}
  \str A\models T\cup\{\sigma_n:n>0\}\Iff\str A\models T\amp\size
  A\geq\varN. 
\end{equation*}
Indeed, let $\sigma_n$ be
\begin{equation*}
  \Exists{x_0}\dotsb\Exists{x_{n-1}}\bigwedge_{i<j<n}x_i\neq x_j. 
\end{equation*}
Moreover, for any formula $\phi$ with at most one free variable, $x$,
if $n>1$, we can form the sentence
\begin{equation*}
  \Exists{x_0}\dotsb\Exists{x_{n-1}}(\bigwedge_{i<j<n}x_i\neq x_j\land
  \bigwedge_{i<n}\phi(x_i));
\end{equation*}
this sentence can be
abbreviated
\begin{equation*}
  \Existsgeqn x\;\phi.
\end{equation*}
Then
\begin{equation*}
  \str A\models\Existsgeqn x\phi\Iff\size{\phi^{\str A}}\geq n.
\end{equation*}

\begin{example}
Suppose $\lang=\{E\}$, where $E$ is a binary predicate, and let
$T$ be the theory of equivalence-relations with exactly two classes,
both infinite.
So $T$ has the axioms:
\begin{gather*}
 \Forall x x\mathrel E x;\\
\Forall x\Forall y(x \mathrel Ey\to y\mathrel Ex);\\
\Forall x\Forall y\Forall z(x\mathrel Ey\land y\mathrel Ez\to x\mathrel Ez);\\
\Exists x\Exists y\Forall z (\lnot(x\mathrel Ey)\land(x\mathrel Ez\lor
y\mathrel Ez))\\
  \Forall x\Existsgeqn yx\mathrel Ey
\end{gather*}
for each $n$ greater than $1$.  Then $T$ is $\omega$-categorical.
However, if $\kappa$ is an \emph{uncountable} cardinal, then $T$ is
not $\kappa$-categorical.  For example, there is a model
in which both $E$-classes have size $\omega_1$ (that is, $\aleph_1$),
and a model in which one class has size $\omega_1$, the other $\varN$.
\end{example}

In a countable signature, there are at most $\size{2^{\varN}}$---that
is, \defn{continuum-many}---structures with a given countable universe
$A$, because each symbol in the
signature will be interpreted as a subset of some $A^n$, and there are
at most continuum-many of these.

The \defn{spectrum-function} is
\begin{equation*}
  (T,\kappa)\longmapsto I(T,\kappa),
\end{equation*}
where $T$ is a theory,$\kappa$ is an infinite
cardinal, and $I(T,\kappa)$ is the number of non-isomorphic models of
$T$ of size $\kappa$.  A theory
in a countable signature is also called \defn{countable}.  If $T$ is
countable, then we have
\begin{equation}\label{eqn:IT}
  1\leq I(T,\varN)\leq\size{2^{\varN}}.
\end{equation}
We've seen in Examples~\ref{example:TO*} and~\ref{example:empty} that
the lower bound cannot be improved. 
\defn{Vaught's conjecture} is that
\begin{equation*}
  I(T,\varN)<\size{2^{\varN}}\implies I(T,\varN)\leq\omega.
\end{equation*}
If the Continuum Hypothesis is accepted, than this implication is
trivial; the Conjecture is that the implication holds even if the
Continuum Hypothesis is rejected.


The upper bound of \eqref{eqn:IT} cannot be improved:

\begin{example}\label{example:binary}
  Let $\lang$ be $\{P_n:n\in\varN\}$, where each $P_n$ is a
unary predicate.  Let $T$ have the following axioms, where $I$ and $J$
are finite disjoint subsets of $\varN$:
\begin{equation*}
  \Exists x(\bigwedge_{i\in I}P_ix\land\bigwedge_{j\in J}\lnot P_jx). 
\end{equation*}
In the same way that we proved $\TO^*$ admitted quantifier-elimination
and was complete, we can prove that $T$ admits QE and is complete.
But $T$ has continu\-um-many countably infinite models.
Indeed, $T$ has a model $\str A$, where $A=2^{\varN}$, and
\begin{equation*}
  P_n{}^{\str A}=\{\sigma\in A:s(n)=1\}.
\end{equation*}
We could replace $A$ with the set $A_0$ of $\sigma$ in $2^{\varN}$ such
that, for some $k$, if $n\geq k$, then $\sigma(n)=0$.  This $A_0$ is
countable.  In fact there is an injection from $A_0$ into
$2^{{}<\varN}$, where
\begin{equation*}
  2^{{}<\varN}=\bigcup_{n\in\varN}2^n.
\end{equation*}
This set is partially ordered by $\included$ and is a \tech{tree}.  A
\tech{branch} of this tree is a maximal totally ordered subset; the
union of a branch is an element of $2^{\varN}$.  If $\sigma$ and
$\tau$ are distinct elements of $2^{\varN}$, then
$\sigma(n)\neq\tau(n)$ for some $n$ in $\varN$, and then
\begin{equation*}
  \sigma\in P_n{}^{\str A}\Iff\tau\notin P_n{}^{\str A}.
\end{equation*}
Hence, if also $\sigma$ and $\tau$ are not in $A_0$, then
$A_0\cup\{\sigma\}$ and $\tau\cup\{\tau\}$ determine non-isomorphic
models of $T$.  Hence $T$ has at least (and therefore exactly)
continuum-many countable models, since $\size{2^{\varN}\setminus
  A_0}=\size{2^{\varN}}$. 
\end{example}



For those who know some algebra:

\begin{examples}
  As examples of complete $T$ where $I(T,\varN)=\varN$, we have:
\begin{mylist}
  \item
the theory of torsion-free divisible abelian groups;
\item
$\ACF_0$, the theory of algebraically closed fields of characteristic $0$.
\end{mylist}
\end{examples}



