%an older version is <elementary-old.tex>
\chapter{Relations between structures}

There are several binary relations on the class of structures
in a signature $\lang$.  Some relations involve universes of
structures; others do not.

Let $\str A$ and $\str B$ be $\lang$-structures.

\section{Fundamental definitions}

The structure $\str A$ is a \defn{substructure of $\str B$}, or $\str
B$ is an \defn{extension of $\str A$}, if $A\included B$ and
\begin{mylist}
  \item
$c^{\str A}=c^{\str B}$ for all constants $c$ of $\lang$;
\item
$R^{\str A}=A^n\cap R^{\str B}$ for all $n$-ary predicates $R$ of
  $\lang$, for all positive $n$ in~$\varN$;
\item
$f^{\str A}=f^{\str B}\circ\id_{A^n}$  for all $n$-ary
  function-symbols $f$ of
  $\lang$, for all positive $n$ in~$\varN$.
\end{mylist}
In this case, we write
\begin{equation*}
  \str A\included\str B.
\end{equation*}
Immediately, $\str A\included\str B$ if and only if $A\included B$ and
\begin{equation}\label{eqn:sigma-iff}
  \str A\models\sigma\Iff\str B\models\sigma
\end{equation}
for all atomic sentences $\sigma$ of $\lang(A)$ of one of the forms
\begin{gather*}
  a_0=c,\\
Ra_0\dotsb a_{n-1},\\
fa_0\dotsb a_{n-1}=a_n.
\end{gather*}

The two structures $\str A$ and $\str B$ are called \defn{elementarily
  equivalent} if~\eqref{eqn:sigma-iff} holds for \emph{all} sentences
  $\sigma$ of $\lang$ (not $\lang(A)$).
In this case, we 
write
\begin{equation*}
  \str A\equiv\str B.
\end{equation*}
Then the relation $\equiv$ of \defn{elementary equivalence} is in fact
the equivalence-relation induced on the class of 
$\lang$-structures by the function $\str M\mapsto\Th{\str M}$; that
is,
\begin{equation*}
  \str A\equiv\str B\Iff \Th{\str A}=\Th{\str B}.
\end{equation*}

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.

\section{Additional definitions}

The structure $\str A$ is an \defn{elementary substructure of $\str
  B$}, and $\str 
  B$ is an \defn{elementary extension of $\str A$}, if $A\included B$
  and $\str A_A\equiv\str B_A$.  Then 
  we write
  \begin{equation*}
    \str A\elsub\str B.
  \end{equation*}
(Some people prefer just to write $\str A\prec\str B$.)  Note here
 that  $\str A_A\equiv\str B_A$ if and only if~\eqref{eqn:sigma-iff}
 holds for all sentences $\sigma$ of $\lang(A)$.  In particular,
 elementary substructures \emph{are} substructures.









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(\tuple a)= 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)\}$.

The structure $\str A$ \defn{embeds} in $\str B$ if there 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}$ for all
  $n$-ary predicates $R$ in $\lang$, for all positive $n$ in~$\varN$;
\item
$h\circ f^{\str A}=f^{\str B}\circ h$ for all $n$-ary function-symbols
  $f$ in $\lang$, for all positive
  $n$ in~$\varN$.
\end{mylist}
Then $h$ is an \defn{embedding} of $\str A$ in $\str B$; 
to express this, we can write
\begin{equation*}
  h:\str A\To\str B.
\end{equation*}
Immediately, $h:\str A\to\str B$ if and only if $h:A\to B$ and
\begin{equation}\label{eqn:h-iff}
  \str A\models\phi(\tuple a)\Iff\str B\models\phi(h(\tuple a)),\quad \text{
  for all $\tuple a$ from $A$,}
\end{equation}
for all
atomic formulas $\phi$ of $\lang$ of one of the forms
\begin{gather*}
  x_0=x_1,\\
x_0=c,\\
Rx_0\dotsb x_{n-1},\\
fx_0\dotsb x_{n-1}=x_n.
\end{gather*}
If~\eqref{eqn:h-iff} holds for
\emph{all} formulas $\phi$ of $\lang$, then $h$ is an \defn{elementary
  embedding} of $\str A$ in $\str B$, and we can write
\begin{equation*}
  h:\str A\overset{\equiv}{\To}\str B.
\end{equation*}


\begin{example}
  The map $x\mapsto x/1$ is an embedding of the ring $\Z$ in the field
  $\Q$, but not an elementary embedding, since $\Z\models\phi(1)$, but
  $\Q\nmodels\phi(1/1)$, where $\phi$ is
$\lnot\Exists
  y y+y=x$.
\end{example}



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*}

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}.

\section{Implications}

\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}

Isomorphic structures are practically the same.  One way to make this
precise is by means of the following:

\begin{lemma}\label{lem:fundamental}
  Suppose $h:\str A\to\str B$.  Then~\eqref{eqn:h-iff} holds for all
  atomic formulas $\phi$ of $\lang$.  If also $h$ is \emph{onto} $B$,
  then~\eqref{eqn:h-iff} holds for \emph{all} formulas $\phi$ of
  $\lang$. 
\end{lemma}

\begin{proof}
Note that \eqref{eqn:h-iff} can be re-formulated in other ways,
according to taste:
\begin{equation}\label{eqn:isom-alt}
  \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*}
  h\setim(\phi^{\str A})=h\setim(A^n)\cap\phi^{\str B}.
\end{equation*}
To prove it, assuming $h:\str A\to\str B$, 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$:
\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}

As an immediate consequence, we have:

\begin{theorem}
  If $\str A\cong\str B$, then $\str A\equiv\str B$.
\end{theorem}

For other consequences, we first observe:

\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}

\begin{theorem}
Suppose $h:\str A\to\str B$.  Then $\str A\overset{\equiv}{\To}\str B$
if and only if $h(\str A)\elsub\str B$.
\end{theorem}

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*}
Then we can give the following characterization of the relations
$\included$ and $\elsub$:

\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, if $A\included B$, then
\begin{gather*}
  \str B\models\diag{\str A}\Iff \str A\included\str B;\\
\str B\models\Th{\str A_A}\Iff \str A\elsub\str B.
\end{gather*}
\end{theorem}

\begin{proof}
Note that $\str B^*\models\phi(\tuple a)\Iff\str B\models\phi(h(\tuple
a))$.  The points about elementary embeddings and substructures follow
from the definitions; about embeddings and substructures, from
Lemma~\ref{lem:fundamental}. 
\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}