\chapter{Compactness}

We now aim to prove \tech{compactness} for first-order logic.
A subset $\Sigma$ of $\Sn$ is
\begin{mylist}
  \item
\defn{satisfiable} if it has a model;
  \item
\defn{finitely satisfiable} if every finite subset of $\Sigma$ has a model.
\end{mylist}
Compactness is that every finitely satisfiable set is satisfiable.

\begin{lemma}
  If $\Sigma$ is finitely satisfiable, but $\Sigma\cup\{\sigma\}$ is
  not, then $\Sigma\cup\{\lnot\sigma\}$ is.
\end{lemma}

\begin{proof}
  Say $\Sigma_0$ is a finite subset of $\Sigma$ such that
  $\Sigma_0\cup\{\sigma\}$ has no model.  Then
  $\Sigma_0\models\lnot\sigma$.  Say $\Sigma_1$ is another finite
  subset of $\Sigma$.   Then $\Sigma_0\cup\Sigma_1$ has a model in
  which $\lnot\sigma$ is true.
\end{proof}

In proving the Completeness Theorem for propositional logic, we
start from a set $\Sigma$ of propositional formulas from which a
formula $F$ cannot be derived.  Then $\Sigma\cup\{\lnot F\}$ is
consistent.  We find a \emph{maximal} consistent set $\Sigma^*$ that
includes $\Sigma\cup\{\lnot F\}$.  From $\Sigma^*$ we \emph{define} a
structure $A$ that is a model of $\Sigma$ in which $F$ is false.

We can try to do something similar to prove compactness for
first-order logic.  Suppose $\Sigma$ is a maximal finitely
satisfiable set of first-order formulas in some signature $\lang$.
(In particular then, $\sigma\in\Sigma\Iff\lnot\sigma\notin\Sigma$.)  We
can try to define an $\lang$-structure $\str A$ by letting:
\begin{mylist}
  \item
$A$ be the set of constants in $\lang$;
\item
$c^{\str A}=c$ for every constant $c$ in $\lang$;
\item
$f^{\str A}(c_0,\dots,c_{n-1})=d\Iff (fc_0\dotsb
  c_{n-1}=d)\in\Sigma$;
\item
$(c_0,\dots,c_{n-1})\in R^{\str A}\Iff Rc_0\dotsb c_{n-1}\in\Sigma$.
\end{mylist}
We want $\str A$ to be a model of $\Sigma$.
There are three problems:
\begin{mylist}
  \item
The signature $\lang$ might not contain any constants.
\item
Suppose $\lang$ does contain constants $c$ and $d$.
We have $\str A\models(c=d)\Iff c^{\str A}=d^{\str A}\Iff c=d$.  So
$\str A$ can't be a model of $\Sigma$ unless either $\Sigma$ does not
contain $(c=d)$, or $c$ and $d$ are the same symbol.
\item
If $\str A\models\lnot\phi_c^x$ for every constant $c$ in $\lang$, then $\str
A\models\lnot\Exists x\phi$.  However, possibly $\Sigma$ contains all
of the formulas $\lnot\phi_c^x$, but also $\Exists x\phi$.
\end{mylist}

The solution to these problems is as follows:
\begin{mylist}
  \item
We expand $\lang$ to a signature $\lang'$ that contains infinitely
many constants.  Then we enlarge $\Sigma$ to a maximal finitely
satisfiable subset $\Sigma'$ of $\Sn[\lang']$.
\item
Letting $C$ be the set of constants of $\lang'$, we define an
equivalence-relation $E$ on $C$ by
\begin{equation*}
  c\mathrel Ed\Iff (c=d)\in\Sigma'.
\end{equation*}
Then we let $A$ be, not $C$, but $C/E$.
\item
In enlarging $\Sigma$ to $\Sigma'$, we ensure that, if $\Exists
x\phi\in\Sigma'$, then $\phi_c^x\in\Sigma'$ for some $c$ in $C$.
\end{mylist}


\begin{theorem}[Compactness for first-order logic]
  Every finitely satisfiable set of formulas (in some signature) is
  satisfiable.
\end{theorem}

\begin{proof}
  Suppose $\Sigma$ is a finitely satisfiable subset of $\Sn$.  Let $C$ be
a set of new constants (so $\lang\cap C=\emptyset$).
  For any
  $\lang$-structure $\str A$, there is some $a$ in $A$; so we can
  expand $\str A$ to an $\lang\cup C$-structure $\str A'$ by defining
  \begin{equation*}
    c^{\str A'}=a
  \end{equation*}
for all $c$ in $C$.  In particular, $\Sigma$ is still finitely
satisfiable \emph{as a set of sentences of $\lang'$}.

We'll assume that $\lang$ is countable (although the general case
would proceed similarly).  So we can enumerate $\Sn[\lang\cup C]$ as
$\{\sigma_n:n\in\varN\}$, and $C$ as $\{c_n:n\in\varN\}$.
We shall define a chain
\begin{equation*}
  \Sigma_0\included\Sigma_{1}\included\Sigma_2\included\dotsb,
\end{equation*}
where each $\Sigma_k$ is finitely satisfiable, and only finitely many constants
in $C$ appear in formulas in $\Sigma_k$.  The recursive
definition is the following:
\begin{mylist}
  \item
$\Sigma_0=\Sigma$.  (By assumption, $\Sigma_0$ is finitely
    satisfiable, and it contains no constants of $C$.)
\item
Assume $\Sigma_{2n}$ has been defined as required.  Then define
\begin{equation*}
  \Sigma_{2n+1}=
  \begin{cases}
    \Sigma_{2n}\cup\{\sigma_n\},&\text{ if this is finitely
    satisfiable;}\\
\Sigma_{2n},&\text{ if not.}
  \end{cases}
\end{equation*}
Then $\Sigma_{2n+1}$ is as required.
\item
Suppose $\Sigma_{2n+1}$ has been defined as required.
Suppose also $\sigma_n\in\Sigma_{2n+1}$, and
$\sigma_n$ is $\Exists x\phi$ for some $\phi$.  The set of $m$ such
that $c_m$ does \emph{not} appear 
    in a formula in $\Sigma_{2n+1}$ has a least element, $k$.  Then
    the set $\Sigma_{2n+1}\cup\{\phi_{c_k}^x\}$ is
    finitely satisfiable.  For, if $\Gamma$ is a finite subset of
    $\Sigma_{2n+1}$, then it has a model $\str A$.  Then $\str
    A\models\phi_a^x$ for some $a$ in 
$A$; so we can expand $\str A$ to a model of
    $\Sigma_{2n+1}\cup\{\phi_{c_k}^x\}$ by 
interpreting $c_k$ as $a$.  In this case we define
\begin{equation*}
  \Sigma_{2n+2}= \Sigma_{2n+1}\cup\{\phi_{c_k}^x\};
\end{equation*}
otherwise, let $\Sigma_{2n+2}=\Sigma_{2n+1}$.  In either case,
$\Sigma_{2n+2}$ is as desired.
\end{mylist}
Now we define
\begin{equation*}
  \Sigma^*=\bigcup_{n\in\varN}\Sigma_n.
\end{equation*}
This is finitely satisfiable, since each finite subset is a subset of
some $\Sigma_n$.  Suppose $\Sigma^*\cup\{\sigma\}$ is finitely
satisfiable.  But $\sigma$ is $\sigma_n$ for some $n$, and
$\Sigma_{2n}\cup\{\sigma\}$ is finitely satisfiable, so
$\sigma\in\Sigma_{2n+1}$, and $\sigma\in\Sigma^*$.  So $\Sigma^*$ is a
maximal finitely satisfiable set. 

We now define a structure $\str A$ of $\lang\cup C$ that will turn out
to be a model of $\Sigma$:

We first define
\begin{equation*}
  E=\{(c,d)\in C^2:(c=d)\in\Sigma^*\}.
\end{equation*}
Then $E$ is an equivalence-relation on $C$ (\textbf{exercise}).  So,
we can let
\begin{equation*}
  A=C/E.
\end{equation*}
Let the $E$-class of $c$ be denoted $[c]$.  We can define
\begin{equation*}
  c^{\str A}=[c].
\end{equation*}
If $R$ is an $n$-ary
predicate in $\lang$, we define 
\begin{equation*}
  R^{\str A}=\{([c_0],\dots,[c_{n-1}])\in A^n:(Rc_0\dotsb
  c_{n-1})\in\Sigma^*\}. 
\end{equation*}
This means
\begin{equation*}
  (Rc_0\dotsb
  c_{n-1})\in\Sigma^*\implies ([c_0],\dots,[c_{n-1}])\in R^{\str A}.
\end{equation*}
In fact the converse holds too; that is, 
\begin{equation*}
  c_0\mathrel Ed_0\amp\dots \amp c_{n-1}\mathrel Ed_{n-1}
\amp(Rc_0\dotsb c_{n-1})\in\Sigma^*\implies
(Rd_0\dotsb d_{n-1})\in\Sigma^*
\end{equation*}
(\textbf{exercise}).  If $f$ is an $n$-ary function-symbol in $\lang$,
then $(\Exists x fc_0\dotsb c_{n-1}=x)\in\Sigma^*$ (since the sentence
is true in every structure), so $(fc_0\dotsb c_{n-1}=d)\in\Sigma^*$
for some $d$ in $C$.  Moreover,
\begin{multline*}
  c_0\mathrel Ec_0'\amp\dots \amp c_{n-1}\mathrel Ec_{n-1}'\amp
(fc_0\dotsb c_{n-1}=d)\in\Sigma^*\amp\\
(fc_0'\dotsb c_{n-1}'=d')\in\Sigma^* \implies
d\mathrel Ed'
\end{multline*}
(\textbf{exercise}).  
Hence we can define
\begin{equation*}
  f^{\str A}=\{([c_0],\dots,[c_{n-1}],[d])\in A:(fc_0\dotsb
  c_{n-1}=d)\in\Sigma^*\}. 
\end{equation*}
Note then
\begin{equation*}
  f^{\str A}[c_0]\dotsb [c_{n-1}]=[d]\Iff (fc_0\dotsb c_{n-1}=d)\in\Sigma^*
\end{equation*}
(\textbf{exercise}).
Finally, if $c$ is a constant of $\lang$, we can consider it as a
nullary function-symbol, obtaining the interpretation
\begin{equation*}
  c^{\str A}=[d]\Iff (c=d)\in\Sigma^*.
\end{equation*}
So we have $\str A$.  It remains to show $\str A\models\Sigma^*$.  We
shall do this by showing
\begin{equation}\label{eqn:compactness}
  \str A\models\sigma\Iff\sigma\in\Sigma^*
\end{equation}
for all sentences $\sigma$ of $\lang\cup C$, by induction on the
length of $\sigma$.

We need a preliminary observation:  If $t$ is a term with no
variables, and $c\in C$, then
\begin{equation*}
  t^{\str A}=[c]\Iff (t=c)\in\Sigma^*
\end{equation*}
(\textbf{exercise}).
Now suppose $\sigma$ is the atomic sentence $Rt_0\dotsb t_{n-1}$, and
$t_i{}^{\str A}=[c_i]$ for each $i$ in $n$.  Then
\begin{align*}
  \str A\models \sigma&\Iff (t_0{}^{\str
  A},\dots,t_{n-1}{}^{\str A})\in R^{\str A}\\
&\Iff([c_0],\dots,[c_{n-1}])\in R^{\str A}\\
&\Iff (Rc_0\dotsb c_{n-1})\in\Sigma^*\\
&\Iff \sigma\in\Sigma^*.
\end{align*}
If instead $\sigma$ is the equation $t_0=t_1$, then
\begin{align*}
  \str A\models\sigma&\Iff t_0{}^{\str A}=t_1{}^{\str A}\\
&\Iff [c_0]=[c_1]\\
&\Iff (c_0=c_1)\in\Sigma^*\\
&\Iff \sigma\in\Sigma^*.
\end{align*}
Now suppose that \eqref{eqn:compactness} holds when $\sigma$ has the
length of $\tau$, $\theta$ or $\phi$:
\begin{mylist}
  \item
If $\sigma$ is $\lnot\tau$, then
\begin{equation*}
  \str A\models\sigma\Iff \str A\nmodels\tau\Iff
  \tau\notin\Sigma^*\Iff \sigma\in\Sigma^*
\end{equation*}
by maximality of $\Sigma$.
\item
If $\sigma$ is $(\tau\to\theta)$, then
\begin{align*}
\str A\nmodels\sigma&\Iff \str A\models\tau\amp\str
A\models\not\theta\\
&\Iff \tau\in\Sigma^*\amp\theta\notin\Sigma^*\\
&\Iff \sigma\in\Sigma^*
\end{align*}
by maximality of $\Sigma^*$.
\item
If $\sigma$ is $\Exists x\phi$, then
\begin{align*}
  \str A\models\sigma&\Iff \str A\models\phi_c^x\text{ for some $c$ in
  $C$}\\
&\Iff \phi_c^x\in\Sigma^* \text{ for some $c$ in
  $C$}\\
&\Iff\Exists x\phi\in\Sigma^*
\end{align*}
by definition of $\Sigma^*$.
\end{mylist}
By induction, \eqref{eqn:compactness} holds for all $\sigma$, so $\str
A\models\Sigma^*$.
\end{proof}

In the proof, we introduced a set $C$ of new constants such that
$\size C=\size{\Sn}$.  We can denote $\size{\Sn}$ by 
$\size{\lang}$.  For the model $\str A$ of $\Sigma$ produced, we have $\size
A\leq\size C=\size{\lang}$. 

\begin{theorem}
  If $T$ is a theory such that, for all $n$ in $\varN$, there is a
  model of $T$ of size greater than $n$, then $T$ has an infinite
  model. 
\end{theorem}

\begin{proof}
For each $n$ in $\varN$, introduce a new constant $c_n$.
  Every model of the theory $T\cup\{c_i\neq c_j:i<j<\varN\}$ is
  infinite.  Also this theory \emph{has} models, by Compactness, since
  the theory is finitely satisfiable.  Indeed, every finite subset of
  the theory is a subset of $T\cup\{c_i<c_j:i<j<n\}$ for some $n$.  We
  can expand a
  model of $T$ of size greater than $n$ to a model of
  the larger theory by interpreting each $c_i$ by a different element
  of the universe.
\end{proof}

\begin{example}
  Let $\class K$ be the class of finite fields (considered as
  structures in the signature $\{+,-,\cdot, 0,1\}$).  Then $\Th{\class
  K}$ has infinite models; these are called \defn{pseudo-finite}
  fields.  Every field $F$ has a \defn{characteristic}:  If
  \begin{equation*}
    F\models \underbrace {1+\dotsb+1}_p=0
  \end{equation*}
for some prime number $p$, then $p$ is the characteristic of $F$, or
$\Char F=p$; if
there is no such $p$, then $\Char F=0$.  The field $F$ is
\defn{perfect} if either:
\begin{mylist}
  \item
$\Char F=0$; or
\item
$\Char F=p$ and every element of $F$ has a $p$-th root.
\end{mylist}
Then perfect fields are precisely the fields that satisfy the axioms
\begin{equation*}
  \Forall x\Exists y(\underbrace{1+\dotsb+1}_p=0\to y^p=x).
\end{equation*}
Now, if $F$ is finite, then $\Char F=p$ for some prime $p$, and the
function $x\mapsto x^p$ is an \defn{automorphism} of $F$, that is, an
isomorphism from $F$ to itself.  This shows $F$ is perfect.  Therefore
the pseudo-finite fields are also perfect.  In fact, axioms can be
written for the theory of pseudo-finite fields (James Ax, 1968). 
\end{example}

Another field-theoretic application of Compactness is:

\begin{example}
  An \defn{ordered field} is a structure $\str F$ or $(F,+,-,\cdot,0,
  1, <)$ such that: 
  \begin{mylist}
    \item
$(F,+,-,\cdot,0,1)$ is a
      field;
\item
$(F,<)$ is a total order;
\item
$\str F\models\Forall x\Forall y(0<x\land 0<y\to 0<x+y\land 0<x\cdot
  y)$;
\item
$\str F\models\Forall x(x<0\to 0<-x)$.
  \end{mylist}
An ordered field must have characteristic $0$ (why?); hence $\Q$ can
be treated as a sub-field of it.
In an ordered field, the formula $0<x$ defines the set of
\defn{positive} elements.  
The ordered field $\str F$ is
\defn{Archimedean} if, for all positive $a$ and $b$ in $F$, there is a
natural number $n$ such that
\begin{equation*}
  \str F\models a<\underbrace{b+\dotsb+b}_n.
\end{equation*}
Then $\R$ is an Archimedean ordered field.  However, there is an ordered field
$\str F$ such that $\str F\equiv\R$, but $\str F$ is not Archimedean.
Indeed, let $c$ be a new constant.  Then the theory
\begin{equation*}
  \Th{\R}\cup\{n<c:n\in\varN\}
\end{equation*}
is finitely satisfiable, since for every finite subset $\Sigma$ of
this theory, $\R$ itself expands to a model of $\Sigma$.  So the
theory has a model $\str F$, by Compactness; but
\begin{equation*}
  \str F\models\underbrace{1+\dotsb+1}_n<c
\end{equation*}
for all $n$ in $\varN$.
\end{example}

\begin{theorem}[L\"owenheim--Skolem--Tarski]\label{thm:LST}
  Suppose $\str A$ is an infinite $\lang$-structure, and $\kappa$ is
  an infinite cardinal such that $\size{\lang}\leq\kappa$.
Then
  there is an $\lang$-structure
  $\str B$ such that $\size B=\kappa$ and $\str A\equiv\str B$. 
\end{theorem}

\begin{proof}
Introduce $\kappa$-many new constants $c_\alpha$ (where $\alpha<\kappa$).
  In the Compactness Theorem, let $\Sigma$
  be $\Th{\str A}\cup\{c_\alpha\neq c_\beta:\alpha<\beta<\kappa\}$.
  This set is finitely satisfiable.  Indeed, any finite subset is
  included in a subset $\Th{\str
  A}\cup\{c_{\alpha_i}\neq
  c_{\alpha_j}:i<j<n\}$ for some finite subset
  $\{\alpha_0,\dots,\alpha_{n-1}\}$ of $\kappa$.  Then $\str A$
  expands to a model of this set of sentences, once we interpret each
  constant $c_{\alpha_i}$ as a different element of $A$.  (Since $A$
  is infinite, we can do this.)  Therefore $\Sigma$ is finitely
  satisfiable. 
  The \emph{proof} of Compactness now produces a model of $\Sigma$
  of size $\kappa$.  
\end{proof}

\begin{theorem}[Vaught]\label{thm:Vaught}
  Suppose $T$ is a finitely satisfiable theory of $\lang$, and
  $\size{\lang}\leq\kappa$.  Then $T$ is complete, provided:
  \begin{mylist}
    \item
$T$ has no finite models;
\item
$T$ is $\kappa$-categorical.
  \end{mylist}
\end{theorem}

\begin{proof}
  Suppose $T$ is finitely satisfiable, but has no finite models, but
  is not complete.  By Compactness, $T$ does have models.  Then for 
  some sentence $\sigma$, neither $\sigma$ nor $\lnot\sigma$ is a
  consequence of $T$.  Hence, both $T\cup\{\lnot\sigma\}$ and
  $T\cup\{\sigma\}$ have models.  By L\"owenheim--Skolem--Tarski, they
  have models of size $\kappa$.  These models are not elementarily
  equivalent, so they are not isomorphic; this means $T$ is not
  $\kappa$-categorical. 
\end{proof}

\begin{examples}\mbox{}
  \begin{mylist}
    \item
  To prove that $\TO^*$ is complete, it is enough to show that every
  model is infinite, and that every countable model is isomorphic to
  $(\Q,<)$.
\item
If a real vector-space $V$ has positive dimension $\kappa$, then 
\begin{equation*}
  \size V=\kappa\cdot \size{2^{\varN}}=\max(\kappa,\size{2^{\varN}}).
\end{equation*}
A space of dimension $0$ is the the \defn{trivial} space, namely the
space containing only the $0$-vector; this space has size $1$.
Real vector-spaces
of the same dimension are isomorphic  Hence the theory of real
vector-spaces is $\kappa$-categorical if $\kappa>\size{2^{\varN}}$.
Therefore the theory of \emph{non-trivial} real vector-spaces is
complete. 
  \end{mylist}
\end{examples}


\section{Additional exercises}


\begin{myenum}
  \item
Show that every Archimedean ordered field is elementarily equivalent
to some \emph{countable, non-Archimedean} 
ordered field.  
\item
  Show that every non-Archimedean ordered field contains
  \defn{infinitesimal} elements, that is, positive elements $a$ that
  are less than every positive rational number.
\item
  Find an example of a non-Archimedean ordered field.
\item
The \defn{order} of an element $g$ of a group is the size of the
subgroup $\{g^n:n\in \Z\}$ that $g$ generates.  In a \defn{periodic}
group, all elements have finite order.  Suppose $G$ is a periodic
group in which there is no finite upper bound on the orders of
elements.  Show that $G\equiv H$ for some non-periodic group $H$.
\item
  Suppose $(X,<)$ is an infinite total order in which $X$ is
  \emph{well-ordered}
  by $<$.  Show that there is a total order $(X^*,<^*)$ such that
  \begin{equation*}
    (X,<)\equiv(X^*,<^*),
  \end{equation*}
but $X^*$ is \emph{not} well-ordered by $<^*$.
\end{myenum}