Model_theory.tex

 % Typeset with LaTeX format
\documentclass[titlepage, oneside]{amsbook}

\usepackage{amsmath,amssymb}
\makeindex

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem*{proposition}{Proposition}

\newtheorem{corollary}{Corollary}
\newtheorem*{claim}{Claim}
\newtheorem*{subclaim}{subclaim}

\theoremstyle{definition}
\newtheorem*{notation}{Notation}
\newtheorem{exercise}{Exercise}
\newtheorem{examples}{Example}
\newtheorem{definition}{Definition}

\theoremstyle{remark}
\newtheorem*{note}{Remark}
\newtheorem*{abuse}{Abuse of Notation}
\newtheorem*{rem}{Remark}
\newtheorem*{pro}{PROBLEMS}

\newcommand{\amt}{\ensuremath{\mathfrak A \models \mathcal T }}
\newcommand{\bmt}{\ensuremath{\mathfrak B \models \mathcal T }}
\newcommand{\cmt}{\ensuremath{\mathfrak C \models \mathcal T }}
\newcommand{\dmt}{\ensuremath{\mathfrak D \models \mathcal T }}

\newcommand{\ax}{\ensuremath{\mathfrak{A}_X}}
\newcommand{\Th}{\ensuremath{\mbox{Th}}}
\newcommand{\sv}[1][v_0]{\ensuremath{\Sigma ( #1) }}
\newcommand{\tria}[1]{\ensuremath{\triangle_{\mathfrak{#1}}}}
\newcommand{\theory}{\ensuremath{\mathcal{T}}}
\newcommand{\tee}{\ensuremath{\mathcal{T}}}
\newcommand{\tst}{\ensuremath{\mathcal{T}^{\ast}}}
\newcommand{\tstar}{\ensuremath{\mathcal{T}^{\ast}}}
\newcommand{\Rstar}{\ensuremath{{}^{\ast}  \mathfrak R}}
\newcommand{\rstar}{\ensuremath{{}^{\ast}  \mathbb R}}
\newcommand{\lan}{\ensuremath{\mathcal{L}}}
\newcommand{\seq}{\ensuremath{\subseteq}}


\newcommand{\ma}{\ensuremath{\mathfrak{A}}}
\newcommand{\mb}{\ensuremath{\mathfrak{B}}}
\newcommand{\mc}{\ensuremath{\mathfrak{C}}}
\newcommand{\md}{\ensuremath{\mathfrak{D}}}
\newcommand{\me}{\ensuremath{\mathfrak{E}}}
\newcommand{\mf}{\ensuremath{\mathfrak{F}}}
\newcommand{\mg}{\ensuremath{\mathfrak{G}}}
\newcommand{\mh}{\ensuremath{\mathfrak{H}}}
\newcommand{\mj}{\ensuremath{\mathfrak{J}}}
\newcommand{\mq}{\ensuremath{\mathfrak{Q}}}
\newcommand{\mr}{\ensuremath{\mathfrak{R}}}
\newcommand{\mm}{\ensuremath{\mathfrak{M}}}

\newcommand{\masb}{\ensuremath{\mathfrak{A} \subseteq \mathfrak{B}}}
\newcommand{\mapb}{\ensuremath{\mathfrak{A} \prec \mathfrak{B}}}
\newcommand{\asb}{\ensuremath{\bf A \subseteq \bf B}}


\newcommand{\reduct}{\ensuremath{\mathfrak{A}' | \mathcal{L}'}}
\newcommand{\real}{\ensuremath{\mathfrak{R}}}
\newcommand{\rational}{\ensuremath{\mathfrak{Q}}}
\newcommand{\reals}{\ensuremath{\mathfrak{R}_{\mathbb{R}}}}
\newcommand{\ba}{\ensuremath{\mathbf{A}}}
\newcommand{\bb}{\ensuremath{\mathbf{B}}}
\newcommand{\bc}{\ensuremath{\mathbf{C}}}
\newcommand{\bd}{\ensuremath{\mathbf{D}}}
\newcommand{\be}{\ensuremath{\mathbf{E}}}
\newcommand{\bg}{\ensuremath{\mathbf{G}}}

\newcommand{\rat}{\ensuremath{\mathbb{Q}}}
\newcommand{\rea}{\ensuremath{\mathbb{R}}}
\newcommand{\nat}{\ensuremath{\mathbb{N}}}

\newcommand{\allforu}[2]{\ensuremath{\forall #1_{0}  \dots  \forall 
#1_{#2}}} 
\newcommand{\existsu}[2]{\ensuremath{\exists #1_{0}  \dots  \exists 
#1_{#2}}} 
\newcommand{\fru}[2][0]{\ensuremath{\forall u_{#1}  \dots  \forall
u_{#2}}}
\newcommand{\frv}[2][0]{\ensuremath{\forall v_{#1} \dots  \forall   
v_{#2}}}
\newcommand{\frw}[2][0]{\ensuremath{\forall w_{#1}  \dots  \forall   
w_{#2}}}
\newcommand{\frx}[2][0]{\ensuremath{\forall x_{#1}  \dots  \forall
x_{#2}}}
\newcommand{\exu}[2][0]{\ensuremath{\exists u_{#1}  \dots  \exists   
u_{#2}}}
\newcommand{\exv}[2][0]{\ensuremath{\exists v_{#1}  \dots  \exists
v_{#2}}} 
\newcommand{\exw}[2][0]{\ensuremath{\exists w_{#1}  \dots  \exists
w_{#2}}} 
\newcommand{\exx}[2][0]{\ensuremath{\exists x_{#1}  \dots  \exists
x_{#2}}} 
\newcommand{\cnot}[2][0]{\ensuremath{ c_{#1} , \dots , c_{#2}}}
\newcommand{\anot}[2][0]{\ensuremath{ a_{#1} , \dots , a_{#2}}}
\newcommand{\dnot}[2][0]{\ensuremath{ d_{#1} , \dots , d_{#2}}}
\newcommand{\bnot}[2][0]{\ensuremath{ b_{#1} , \dots , b_{#2}}}
\newcommand{\rnot}[2][0]{\ensuremath{ r_{#1} , \dots , r_{#2}}}
\newcommand{\tnot}[2][0]{\ensuremath{ t_{#1} , \dots , t_{#2}}}
\newcommand{\tnt}[2][0]{\ensuremath{ t_{#1}  \dots  t_{#2}}}
\newcommand{\unot}[2][0]{\ensuremath{ u_{#1} , \dots , u_{#2}}}
\newcommand{\vnot}[2][0]{\ensuremath{ v_{#1} , \dots , v_{#2}}}
\newcommand{\wnot}[2][0]{\ensuremath{ w_{#1} , \dots , w_{#2}}}
\newcommand{\xnot}[2][0]{\ensuremath{ x_{#1} , \dots , x_{#2}}}
\newcommand{\ynot}[2][0]{\ensuremath{ y_{#1} , \dots , y_{#2}}}

\newcommand{\hphi}{\ensuremath{\Hat{\varphi}}}
\newcommand{\ta}{\ensuremath{\theta}}
\newcommand{\vp}{\ensuremath{\varphi}}
\newcommand{\lra}{\ensuremath{\leftrightarrow}}

\newcommand{\amodphi}{\ensuremath{\mathfrak A \models \varphi}}
\newcommand{\amodpsi}{\ensuremath{\mathfrak A \models \psi}}
\newcommand{\bmodphi}{\ensuremath{\mathfrak B \models \varphi}}
\newcommand{\bmodpsi}{\ensuremath{\mathfrak B \models \psi}}
\newcommand{\cmodphi}{\ensuremath{\mathfrak C \models \varphi}}
\newcommand{\cmodpsi}{\ensuremath{\mathfrak C \models \psi}}
\renewcommand{\abstractname}{Introduction}

\begin{document}

\thispagestyle{empty}
\vglue 1truein
\centerline{\bf \Huge  Fundamentals of Model Theory}
\vglue .5truein
\centerline{\LARGE William Weiss and Cherie D'Mello} 
\vglue .2truein
\centerline{Department of Mathematics}
\centerline{University of Toronto}
\vglue 4.25truein
\centerline{\footnotesize\copyright 2015 W.Weiss and C. D'Mello}
\vfill
\eject
\vglue .25truein
\thispagestyle{empty}
\newpage
\begin{center}
\bf Introduction
\end{center}
\vglue .25truein
\setcounter{page}{1}
Model Theory is the part of mathematics which shows how to apply logic
to the study of structures in pure mathematics.  On the one hand it is
the ultimate abstraction; on the other, it has immediate applications
to every-day mathematics.  The fundamental tenet of Model Theory is
that mathematical truth, like all truth, is relative.  A statement may
be true or false, depending on how and where it is interpreted.  This
isn't necessarily due to mathematics itself, but is a consequence of
the language that we use to express mathematical ideas.  

What at first seems like a deficiency in our language, can
actually be shaped into a powerful tool for understanding mathematics.
This book provides an introduction to Model Theory which can be used
as a text for a reading course or a summer project at the senior
undergraduate or graduate level.  It is also a primer which will give
someone a self contained overview of the subject, before diving into
one of the more encyclopedic standard graduate texts.  

Any reader who is familiar with the cardinality of a set and the
algebraic closure of a field can proceed without worry.  Many readers
will have some acquaintance with elementary logic, but this is not
absolutely required, since all necessary concepts from logic are
reviewed in Chapter~0.  Chapter~1 gives the  motivating
examples; it is short and we recommend that you peruse it first, before studying 
the more technical aspects of Chapter~0. Chapters~2~and~3 are
selections of some of the most
important techniques in Model Theory. The remaining chapters
investigate
the relationship between Model Theory and the algebra of the real and
complex numbers.  Thirty exercises develop familiarity with the
definitions and consolidate understanding of the main proof techniques. 


Throughout the book we present applications which cannot easily be
found elsewhere in such detail.  Some are chosen for their value in
other areas of mathematics:  Ramsey's Theorem, the Tarski-Seidenberg
Theorem.  Some are chosen for their immediate appeal to every
mathematician: existence of infinitesimals for calculus, graph
colouring on the plane.  And some, like Hilbert's Seventeenth Problem,
are chosen because of how amazing it is that logic can play an
important role in the solution of a problem from high school algebra. 
In each case, the derivation  is shorter than any 
which tries to avoid logic. More importantly, the methods of Model
Theory display clearly the structure of the main ideas of the proofs,
showing how theorems of logic combine with theorems from other areas of
mathematics to produce stunning results.

The theorems here are all are more than thirty years old and due in
great part to the cofounders of the subject, Abraham Robinson and
Alfred Tarski.  However, we have not attempted to give a history.  When
we attach a name to a theorem, it is simply because that is what
mathematical logicians popularly call it.




The bibliography contains a number of texts that were helpful in the
preparation of this manuscript.  They could serve as avenues of further
study and in addition, they contain many other references and
historical notes.  The more recent titles were added to show the reader
where the subject is moving today.  All are worth a look. 

This book began life as notes for William Weiss's graduate course at
the University of Toronto. The notes were revised and expanded by
Cherie D'Mello and William Weiss, based upon suggestions from several
graduate students.  The electronic version of this book may be
downloaded and further modified by anyone for the purpose of learning,
provided this paragraph is included in its entirety and so long as no
part of this book is sold for profit.


\tableofcontents%
\setcounter{chapter}{-1}
\chapter{Models, Truth and Satisfaction}
We will use the following symbols:
\begin{itemize}
\item logical symbols:

\begin{itemize}
 \item the connectives $\wedge$ ,$\vee$ , $\neg$ , $\to$ ,
$\leftrightarrow$  called ``and'', ``or'', ``not'', ``implies'' and
``iff'' respectively
 \item the quantifiers $\forall$ , $\exists$ called ``for all'' and
``there exists''
\item an infinite
collection of variables
\index{variable}%
 indexed by the natural numbers $\mathbb{N}$ $v_{0}$ ,$v_{1}$
, $v_{2}$ , \dots

\item the two  parentheses  $)$, $($
 \item the symbol $=$ which is the usual ``equal sign''
 \end{itemize}

\item constant symbols : often denoted by the letter $c$ with
subscripts
\item function symbols : often denoted by the letter $F$ with
subscripts;
each function symbol is an m-placed func\-tion sym\-bol for some
natural 
number $m  \geq  1$
\item relation symbols : often denoted by the letter $R$ with
subscripts;  each relational symbol is an n-placed relation symbol for some natural 
number $n \geq 1$.

\end{itemize}

\addcontentsline{toc}{section}{Formulas, Sentences, Theories and
Axioms}
    We now define terms and formulas.

\begin{definition}\label{D:term}
\index{term}%
   A \emph{term} is defined as follows:
\begin{itemize}
\item [(1)] a variable is a term
\item[(2)] a constant symbol is a term
\item[(3)] if $F$ is an m-placed function symbol and
$t_{1},\dots,t_{m}$  are terms, then \\
 $F(t_{1} \dots t_{m})$ is a term.
\item[(4)] a string of symbols is a term if and only if it can be shown 
to be a term by a finite number of applications of (1), (2) and (3).

\end{itemize}
\end{definition}
\begin{note} This is a recursive definition.
\end{note}

\begin{definition}
\index{formula}%
   A  \emph{formula} is defined as follows :

\begin{itemize}
\item[(1)] if $t_1$ and $t_2$ are terms, then $(t_1 = t_2 )$ is a
formula.
\item[(2)] if $R$ is an n-placed relation symbol and 
$t_1 , \dots , t_n$ are terms, then  \\
$(R( t_1 \dots t_n))$ is a formula.
\item[(3)] if $\varphi$ is a formula, then $( \neg \varphi )$ is a
formula
\item[(4)] if $\varphi$ and $\psi$ are formulas then so are $( \varphi
\wedge \psi )$, $ ( \varphi \vee \psi )$, $( \varphi \to \psi )$ and
 $ ( \varphi \leftrightarrow \psi )$
\item[(5)] if $v_{i}$ is a variable and $\varphi$ is a formula, then 
$( \exists v_{i}) \varphi$ and $( \forall v_{i}) \varphi$ are formulas
\item[(6)] a string of symbols is a formula if and only if it can be
shown
to be a formula by a finite number of applications of (1), (2), (3),
(4) and (5).


\end{itemize}
\end{definition}

\begin{rem} This is another recursive definition. $\neg \varphi$ is
called the negation of $\varphi$;  $\varphi \wedge \psi$ is called the
conjunction of $\varphi$ and $\psi$; and  $\varphi \vee \psi$ is called the
disjunction of $\varphi $ and $\psi$.
\end{rem}

\begin{definition}\label{D:subform}
\index{subformula}%
A \emph{subformula} of a formula $ \varphi$ is defined as follows:

\begin{itemize}
\item[(1)] $\varphi$ is a subformula of $ \varphi$
\item[(2)] if $ (\neg \psi )$ is a subformula of $ \varphi$ then so is
$\psi$
\item[(3)] if any one of $ (\theta \wedge \psi)$, $(\theta \vee \psi)$,
$(\theta \to \psi)$ or $(\theta \leftrightarrow \psi )$ is a subformula of $
\varphi$,
then so are both $\theta$ and $ \psi $
\item[(4)] if either $( \exists v_{i} ) \psi$ or $( \forall v_{i} ) \psi$ 
is a subformula of $\varphi$ for some natural number $i$, then $\psi$ is 
also a subformula of $\varphi$
\item[(5)] A string of symbols is a subformula of $\varphi$, if and only 
if it can be shown to be such by a finite number of applications of (1), (2),
(3) and (4).

\end{itemize}
\end{definition}


\begin{definition}\label{D:bound}
\index{free variable}%
\index{bound variable}%
A variable $v_{i}$  is said to occur \emph{bound} in a formula $\varphi$ 
iff for some subformula $\psi$ of $\varphi$ either $(\exists v_{i}) \psi$ 
or $(\forall v_{i}) \psi $ is a subformula of $\varphi$.
In this case each occurrence of $v_{i}$  in $(\exists v_{i}) \psi$ or 
$(\forall v_{i}) \psi$ is said to be a 
\emph{bound occurrence} of $v_{i}$.
Other occurrences of $v_{i}$ which do not occur bound  in $\varphi$  are
said to be
\emph{free}.
\end{definition}

\begin{examples}\label{X:term} 
\[ F(v_3) \mbox{ is a term, where $F$ is a unary function symbol.} \]
\[ ((\exists v_3 ) ( v_0 = v_3 ) \wedge (\forall v_0 ) (v_0 = v_0 )) \] 
is a formula.  In this formula the variable $v_3$ only occurs bound but the variable $v_0$ occurs both bound and free.
\end{examples}



\begin{exercise}\label{E:recon}
Using the previous definitions as a guide, define the substitution of a
term $t$ for a variable $v_{i}$ in a formula $\varphi$.
In particular, demonstrate how to substitute the term for the variable $v_0$ 
in the formula of the example above.
\end{exercise}


\begin{definition}
\index{language}%
 A \emph{language} $\mathcal{L}$ is a set consisting of
all 
the logical symbols with perhaps some constant, function 
and/or   relational symbols included. It is understood that 
the formulas of 
$\mathcal{L}$ are     made up from this set in the manner prescribed above.  
Note that all the formulas of  $\mathcal{L}$ are uniquely described
by listing only the 
constant, function and relation symbols of $\lan$. 

\end{definition}

We use $t(v_{0}, \dots , v_{k} ) $ to denote a term $t$ all of whose 
variables occur among $v_{0}, \dots , v_{k}$.

We use $\varphi (v_{0}, \dots , v_{k}) $ to denote a formula $\varphi$ 
all of whose free variables occur among $v_{0}, \dots , v_{k}$.



\begin{examples}\label{X:form}
These would be formulas of any language :

\begin{itemize}
\item For any variable $v_i$: $(v_i = v_i )$
\item for any term $t(v_{0}, \dots , v_{k})$ and other terms $t_1$ and 
$t_2$: \[ ((t_1 = t_2 ) \to (t(v_{0},
\dots , v_{i-1} , t_1 , v_{i+1} , \dots , 
v_{k} ) = t (v_{0}, \dots , v_{i-1}, t_2 , v_{i+1}, \dots , v_{k})))\]   
\item for any  formula $\varphi(v_{0}, \dots ,v_{k})$ and terms
$t_1$ and $t_2$:             
 \[ ((t_1 = t_2 ) \to (\varphi ( v_{0}, \dots , v_{i-1} , t_1 , v_{i+1} , 
\dots , v_{k} )  \leftrightarrow  \varphi (v_{0}, \dots , v_{i-1}, t_2
, v_{i+1},
\dots ,
 v_{k}))) \] 
\end{itemize} 
Note the simple way we denote the substitution of $t_1$ for $v_i$.
\end{examples}

\begin{definition}
\index{model}%
 A \emph{model} (or structure) $\mathfrak{A}$ for a 
language $\mathcal{L}$ is an ordered pair $\langle \mathbf{A} 
,\mathcal{I} \rangle$
where $\mathbf{A}$ is a nonempty set and $\mathcal{I}$ is an \emph{interpretation 
function} with domain the set of all constant, function and relation 
symbols of $\mathcal{L}$ such that:

\begin{enumerate}

\item if $c$ is a constant symbol, then $\mathcal{I} (c) \in 
\mathbf{A}$; $\mathcal{I}(c)$ is called a 
constant 

\item if $F$ is an m-placed  function symbol, then 
$\mathcal{I}(F)$ is an m-placed function on $\mathbf{A}$

\item if $R$ is an n-placed relation symbol, then $\mathcal{I}(R)$ is an 
n-placed relation on $\mathbf{A}$.

\end{enumerate}

$\ba$ is called the \emph{universe} of the model $\mathfrak{A}$.  We
generally denote models with Gothic letters and their universes with
the
corresponding Latin letters in boldface.  One set
may be involved as a universe with many diff\-erent interpretation
functions of the 
language $\mathcal{L}$. The model is \emph{both} the universe
\emph{and} the interpretation function.          

\end{definition}

\begin{rem}  The importance of Model Theory lies in the observation that
mathematical objects can be cast as models for a language.  For instance,
the real numbers with the usual ordering $\pmb{<}$ and the usual
arithmetic operations, addition $\pmb{+}$ and multiplication $\pmb{\cdot}$
along with the special numbers $\bf{0}$ and $\bf{1}$ can be described
as a
model.  Let $\lan$ contain one two-placed (i.e. binary) relation symbol
$R_0$, two two-placed function symbols $F_1$ and $F_2$ and two constant
symbols $c_0$ and $c_1$.  We build a model by letting the universe $\ba$
be the set of real numbers.  The interpretation function $\mathcal I$ will
map $R_0$ to $\pmb{<}$, i.e. $R_0$ will be interpreted as $\pmb{<}$.
Similarly, $\mathcal I (F_1)$ will be $\pmb{+}$, $\mathcal I (F_2)$ will
be $\pmb{\cdot}$, $\mathcal I (c_0)$ will be $\bf{0}$ and $\mathcal
I(c_1)$ will be $\bf 1$.  So $\langle \ba , \mathcal I \rangle$ is an
example of a model for the language described by 
$\{ R_0 , F_1 , F_2 , c_0 ,c_1 \}$.

\end{rem}

We now wish to show how to use formulas to express mathematical statements
about elements of a model.  We first need to see how to interpret a term
in a model.  


\begin{definition}
\index{$t[x_{0}, \dots ,x_{q}]$}%
The value $t[x_{0}, \dots ,x_{q}]$ of a term 
$t(v_{0}, \dots , v_{q})$ at $x_{0}, \dots , x_{q}$ in the 
universe $\ba$ of the model 
$\mathfrak{A}$ is defined as follows:


\begin{enumerate}
\item if $t$ is $v_{i}$ then $t[x_{0}, \cdots , x_{q}]$ is $x_{i}$,
\item if t is the constant symbol c, then $t[x_{0}, \dots , x_{q}] $ is
$\mathcal{I}(c)$,
  the interpretation of $c$ in $\mathbf{A}$,
\item if $t$ is $F(t_{1} \dots  t_{m})$ where $F$ is an m-placed 
function symbol and $t_{1}, \dots ,t_{m}$ are terms, then $t[x_{0}, \dots 
, x_{q}]$ is $G(t_{1}[x_{0}, \dots ,x_{q}], \dots , t_{m}[x_{0}, \dots
,x_{q}])$
where $G $ is the m-placed function $ \mathcal{I}(F)$, the
interpretation 
of $F$ in $\mathbf{A}$.
 

\end{enumerate}

\end{definition}


\begin{definition}
\index{model!satisfies}% 
Suppose $\mathfrak{A}$ is a model for a language 
$\mathcal{L}$. The sequence \\
 $x_{0}, \dots ,x_{q}$ of elements of $\ba$ \emph{satisfies} the 
formula $\varphi (v_{0} , \dots ,v_{q})$ all of whose free and bound 
variables are among $v_{0}, \dots , v_{q}$, in the model $\mathfrak{A}$, 
written $\mathfrak{A} \models \varphi [x_{0} , \dots ,x_{q}] $ provided 
we have:
\begin{enumerate}
\item if $\varphi(v_{0}, \dots ,v_{q})$ is the  formula 
$(t_{1} = t_{2})$, then 
\[
\mathfrak{A} \models (t_{1} = t_{2})[x_{0}, \dots , x_{q}] \mbox{ 
means that } t_{1}[x_{0}, \dots ,x_{q}] \mbox{ equals } t_{2}[x_{0},
\dots ,x_{q}] \mbox{,}
\]

\item if $\varphi (v_{0}, \dots ,v_{q})$ is the  formula 
$(R(t_{1} \dots t_{n}))$ where $R$ is an n-placed relation symbol, then 
\[ \mathfrak{A} \models (R(t_{1} \dots  t_{n}))[x_{0} , \dots , x_{q}] 
\mbox{ means } 
S(t_{1}[x_{0}, \dots ,x_{q}], \dots , t_{n}[x_{0}, \dots ,x_{q}]) \]
where $S$ is the n-placed relation $\mathcal{I}(R)$,  the
interpretation of $R$ in $\mathbf{A}$,

\item if $\varphi$ is $( \neg \theta ) $, then 
\[
\mathfrak{A} \models \varphi [x_{0}, \dots ,x_{q}]
 \mbox{ means not } \mathfrak{A} \models \theta[x_{0}, \dots ,x_{q}]
\mbox{,}
\]

\item if $\varphi$ is $( \theta \wedge \psi)$, then 
\[
 \mathfrak{A} \models \varphi [x_{0}, \dots ,x_{q} ] \mbox{ means both } 
\mathfrak{A} \models \theta [x_{0} , \dots , x_{q}] \mbox{ and }
\mathfrak{A} \models \psi [x_{0}, \dots x_{q}] \mbox{,} \]

\item if $\varphi$ is $(\theta \vee \psi)$ then 
\[
\mathfrak{A} \models \varphi [x_{0} ,\dots ,x_{q}] \mbox{ means either } 
\mathfrak{A} \models \theta [x_{0}, \dots , x_{q}] \mbox{ or } 
\mathfrak{A} \models \psi [x_{0}, \dots , x_{q}] \mbox{,} \]

%6
\item if $\varphi $ is $( \theta  \to \psi) $ then
\[
\mathfrak{A} \models \varphi [x_{0} ,\dots ,x_{q}] \mbox{ means  that } 
\mathfrak{A} \models \theta [x_{0}, \dots , x_{q}] \mbox{ implies } 
\mathfrak{A} \models \psi [x_{0}, \dots , x_{q}] \mbox{,} \]




\item if $\varphi $ is $( \theta  \leftrightarrow \psi) $ then
\[
\mathfrak{A} \models \varphi [x_{0} ,\dots ,x_{q}] \mbox{ means that  } 
\mathfrak{A} \models \theta [x_{0}, \dots , x_{q}] \mbox{ iff } 
\mathfrak{A} \models \psi [x_{0}, \dots , x_{q}] \mbox{,} \]

%8
\item if $\varphi$ is $\forall v_{i} \theta$, then
\[ \mathfrak{A} \models \varphi [x_{0} , \dots , x_{q}] \mbox{ means for 
every } x \in \mathbf{A}, \mathfrak{A} \models \theta [x_{0}, \dots , 
x_{i-1}, x, x_{i+1} , \dots , x_{q}] \mbox{,} \]



%9
\item if $\varphi$ is $\exists v_{i} \theta$, then
\[ \mathfrak{A} \models \varphi [x_{0} , \dots , x_{q}] \mbox{ means for 
some } x \in \mathbf{A}, \mathfrak{A} \models \theta [x_{0}, \dots , 
x_{i-1}, x, x_{i+1} , \dots , x_{q}]. \]

\end{enumerate}
\end{definition}

\begin{exercise} Each of the formulas of Example \ref{X:form} is
satisfied in any model $\ma$ for any language $\lan$ by any (long
enough) sequence $ x_0 , x_1 , \dots , x_q $
of $\ba$. This is where you test your solution to
Exercise~\ref{E:recon}, especially with respect to the term and formula from Example \ref{X:term}.
\end{exercise}

We now prove two lemmas which show that the preceding concepts are
well-defined. In the first one, we see that the value of a term only 
depends upon the values of the variables which actually occur in the
term.  In this  lemma the equal sign $=$ is used, not as a logical
symbol in the formal sense, but in its usual sense to denote equality
of mathematical objects --- in this case, the values of terms, which
are elements of the universe of a model.

\begin{lemma}\label{L:zippy} 

Let $\mathfrak{A}$ be a model for $\mathcal{L}$ and let 
$t(v_{0}, \dots ,v_{p})$ be a term of $\mathcal{L}$. Let $x_{0} , \dots , 
x_{q}$ and $y_{0} , \dots, y_{r}$ be sequences from $\mathbf{A}$
such that $p \leq q$ and $p \leq r$, and let $x_{i}= y_{i}$ whenever 
$v_{i}$ actually occurs in $t(\vnot{p})$. Then \[ t[x_{0}, \dots ,x_{q}] =
t[y_{0}, 
\dots , y_{r}] \].

\end{lemma}

\begin{proof} We use induction on the complexity of the term $t$.
\begin{enumerate}
\item If $t$ is $v_i$ then $x_i=y_i$ and so we have 
\[t[\xnot{q}]=x_i=y_i=t[\ynot{r}] \mbox{ since } p\leq q \mbox{ and } p 
\leq r. \]

\item If $t$ is the constant symbol $c$, then 
\[t[\xnot{q}] = \mathcal I (c) = t[\ynot{r}] \]
where $\mathcal I (c) $ is the interpretation of $c$ in $\ba$.

\item If $t$ is $F(t_{1} \dots t_{m})$ where $F$ is an m-placed  
function symbol,  $t_{1}, \dots ,t_{m}$ are terms and $\mathcal I (F) 
= G$, then \\
  $t[x_{0}, \dots 
, x_{q}]=G(t_{1}[x_{0}, \dots ,x_{q}], \dots , t_{m}[x_{0}, \dots
,x_{q}])$ and \\ 
$t[y_{0}, \dots
, y_{r}]=G(t_{1}[y_{0}, \dots ,y_{r}], \dots , t_{m}[y_{0}, \dots
,y_{r}])$. \\
By the induction hypothesis we have that $t_i [\xnot{q}] = t_i [
\ynot{r}] $  for $ 1
\leq i 
\leq m$  since $t_1, \dots , t_m$ have all their variables among $\{ 
\vnot{p} \} $. So  we have $t[ \xnot{q} ] = t [ \ynot{r} ] $.

\end{enumerate}
\end{proof}


In the next lemma the equal sign $=$ is used in both senses --- as a
formal logical symbol in the formal language $\lan$ and also to denote
the usual equality of mathematical objects.  This is common practice
where the context allows the reader to distinguish the two usages of
the same symbol. The lemma confirms that satisfaction of a formula
depends only upon the values of its free variables.



\begin{lemma}\label{L:sat}  Let $\ma$ be a model for $\lan$ and $\varphi$
a formula of
$\lan$, all of whose free and bound variables occur among $\vnot{p}$.
Let $\xnot{q}$ and $\ynot{r}$ ($q,r \geq p $) be two sequences such
that
$x_i$ and $y_i$  are equal for all $i$ such that $v_i$ occurs
free in $\varphi$. Then \[ \amodphi [ \xnot{q}] \mbox{ iff } \ma \models
\varphi [ \ynot{r} ] \]

\end{lemma}

\begin{proof} Let $\ma$ and $\lan$ be as above.  We prove the lemma by
induction on the complexity of $\varphi$.

\begin{enumerate}
\item If $\varphi(v_{0}, \dots ,v_{p})$ is the  formula $(t_{1} = t_{2})$, then we use Lemma \ref{L:zippy} to get:
\[ \begin{aligned}
\mathfrak{A} \models (t_{1} = t_{2})[x_{0}, \dots , x_{q}]  &
\mbox{ iff  } t_{1}[x_{0}, \dots ,x_{q}] = t_{2}[x_{0}, \dots ,x_{q}]\\
%
& \mbox{ iff }
t_{1}[y_{0}, \dots ,y_{r}] = t_{2}[y_{0}, \dots ,y_{r}]\\
%
& \mbox{ iff } \mathfrak{A} \models (t_{1} = t_{2})[y_{0}, \dots
, y_{r}].
\end{aligned} \]

\item If $\varphi (v_{0}, \dots ,v_{p})$ is the  formula 
$(R(t_{1} \dots t_{n})) $ where $R$ is an n-placed relation symbol
with interpretation $S$, then
again by Lemma \ref{L:zippy}, we get:
\[ \begin{aligned}
\mathfrak{A} \models (R(t_{1} \dots  t_{n}))[x_{0} , \dots , x_{q}] 
& \mbox{ iff } S(t_{1}[x_{0}, \dots ,x_{q}], \dots , t_{n}[x_{0}, \dots 
,x_{q}]) \\
& \mbox{ iff } S(t_{1}[y_{0}, \dots ,y_{r}], \dots , t_{n}[y_{0}, \dots
,y_{r}]) \\
& \mbox{ iff } \ma \models R ( t_1  \dots  t_n ) [ \ynot{r} ].
\end{aligned} \]


\item If $\varphi$ is $( \neg \theta ) $, the inductive hypothesis
gives that the lemma is true for $\theta$. So,  
\[ \begin{aligned}
\mathfrak{A} \models \varphi [x_{0}, \dots ,x_{q}]
&  \mbox{ iff not } \mathfrak{A} \models \theta[x_{0}, \dots ,x_{q}] \\
&  \mbox{ iff not } \mathfrak{A} \models \theta[y_{0}, \dots ,y_{r}] \\
& \mbox{ iff } \mathfrak{A} \models \varphi [y_{0}, \dots ,y_{r}].
\end{aligned} \]

\item If $\varphi$ is $( \theta \wedge \psi)$, then using the inductive
hypothesis on $\theta$ and $\psi$ we get 
\[ \begin{aligned}
 \mathfrak{A} \models \varphi [x_{0}, \dots ,x_{q} ]
 &\mbox{ iff both } 
\mathfrak{A} \models \theta [x_{0} , \dots , x_{q}] \mbox{ and }
\mathfrak{A} \models \psi [x_{0}, \dots x_{q}] \\
 &\mbox{ iff both }
\mathfrak{A} \models \theta [y_{0} , \dots , y_{r}] \mbox{ and }
\mathfrak{A} \models \psi [y_{0}, \dots y_{r}] \\ 
& \mbox{ iff } \mathfrak{A} \models \varphi [y_{0}, \dots ,y_{r} ].
\end{aligned} \]

\item If $\varphi$ is $(\theta \vee \psi)$ then 
\[ \begin{aligned}
\mathfrak{A} \models \varphi [x_{0} ,\dots ,x_{q}] & \mbox{ iff either } 
\mathfrak{A} \models \theta [x_{0}, \dots , x_{q}] \mbox{ or } 
\mathfrak{A} \models \psi [x_{0}, \dots , x_{q}] \\
& \mbox{ iff either }
\mathfrak{A} \models \theta [y_{0}, \dots , y_{r}] \mbox{ or }
\mathfrak{A} \models \psi [y_{0}, \dots , y_{r}] \\
& \mbox{ iff } \mathfrak{A} \models \varphi [y_{0} ,\dots ,y_{r}].
\end{aligned} \]
%6
\item If $\varphi $ is $( \theta  \to \psi) $ then
\[ \begin{aligned}
\mathfrak{A} \models \varphi [x_{0} ,\dots ,x_{q}] & \mbox{ iff  } 
\mathfrak{A} \models \theta [x_{0}, \dots , x_{q}] \mbox{ implies } 
\mathfrak{A} \models \psi [x_{0}, \dots , x_{q}] \\
& \mbox{ iff  }
\mathfrak{A} \models \theta [y_{0}, \dots , y_{r}] \mbox{ implies }
\mathfrak{A} \models \psi [y_{0}, \dots , y_{r}] \\
& \mbox{ iff } \mathfrak{A} \models \varphi [y_{0} ,\dots ,y_{r}]  .
\end{aligned} \]

\item If $\varphi $ is $( \theta  \leftrightarrow \psi) $ then
\[ \begin{aligned}
\mathfrak{A} \models \varphi [x_{0} ,\dots ,x_{q}] & \mbox{ iff we have  } 
\mathfrak{A} \models \theta [x_{0}, \dots , x_{q}] \mbox{ iff } 
\mathfrak{A} \models \psi [x_{0}, \dots , x_{q}] \\
& \mbox{ iff we have }
\mathfrak{A} \models \theta [y_{0}, \dots , y_{r}] \mbox{ iff }
\mathfrak{A} \models \psi [y_{0}, \dots , y_{r}] \\
& \mbox{ iff } \mathfrak{A} \models \varphi [y_{0} ,\dots ,y_{r}].
\end{aligned} \]
%8

\item If $\varphi$ is $(\forall v_{i}) \theta$, then  
\[\begin{aligned} \mathfrak{A} \models \varphi [x_{0} , \dots , x_{q}]
&\mbox{ iff for 
every } z \in \mathbf{A}, \mathfrak{A} \models \theta [x_{0}, \dots , 
x_{i-1}, z, x_{i+1} , \dots , x_{q}]\\
&\mbox{ iff for every } z \in \ba, \ma \models \theta [\ynot{i-1}, z ,
y_{i+1}, \dots , y_r] \\
&\mbox{ iff } \ma \models \varphi [\ynot{r}] .\\
\end{aligned} \]
The inductive hypothesis uses the sequences $ x_0, \dots ,
x_{i-1}, z, x_{i+1}, \dots , x_{q}$ and $ y_0 , \dots , y_{i-1} , z,
y_{i+1} , \dots , y_r $ with the formula $\theta$.

%9
\item If $\varphi$ is $(\exists v_{i}) \theta$, then
\[ \begin{aligned}\mathfrak{A}  \models \varphi [x_{0} , \dots ,
x_{q}] &\mbox{ iff for some } z \in \mathbf{A}, \mathfrak{A} \models
\theta
[x_{0}, \dots ,x_{i-1}, z, x_{i+1} , \dots , x_{q}] \\
&\mbox{ iff for some } z \in \ba, \ma \models \theta
[\ynot{i-1},z,y_{i+1}, \dots , y_r]\\
&\mbox{ iff } \ma \models \varphi [\ynot{r}]. \\
\end{aligned} \]
The inductive hypothesis uses the sequences $ x_0, \dots ,
x_{i-1}, z, x_{i+1} , \dots , x_{q}$ and $ y_0 , \dots , y_{i-1} , z,
y_{i+1} , \dots , y_r $ with the formula $\theta$.


\end{enumerate}

\end{proof}


\begin{definition}
\index{sentence}%
  A \emph{sentence} is a formula with no free
variables.
\end{definition}




If $\varphi$ is a sentence, we can write
$\mathfrak{A} \models \varphi$ 
without any mention of a sequence from $\mathbf{A}$ since by the
previous lemma, it doesn't matter which sequence from $\ba$ we use. In
this case we say: \begin{itemize}
\item $\mathfrak{A}$ \emph{satisfies} $\varphi$
\item or $\mathfrak{A}$ is a \emph{model} of $\varphi$
\item or $\varphi$ \emph{holds} in $\mathfrak{A}$
\item or $\varphi$ is \emph{true} in $\mathfrak{A}$
\end{itemize}

If $\varphi$ is a sentence of $\lan$, we write
$\models \varphi$ to mean that $\ma \models \varphi$ for every model
$\ma$ for $\lan$. Intuitively then, $\models \varphi$ means that
$\varphi$ is true under any relevant interpretation (model for $\lan$).
Alternatively, no relevant example (model for $\lan$) is a
counterexample to $\varphi$ --- so  $\varphi $ is true.



\begin{lemma}\label{L:altform} Let $\varphi(v_{0}, \dots ,v_{q})$ be a
formula
of the 
language $\mathcal{L}$. There is another formula $\varphi' (v_{0}, 
\dots ,v_{q})$ of $\mathcal{L}$ such that

\begin{enumerate}

\item $\varphi'$ has exactly the same free and bound occurrences of 
variables as $\varphi$.


\item $\varphi'$ can possibly contain $\neg$, 
$\wedge$ and 
$\exists$ but no other connective or quantifier.

\item $\models ( \forall v_{0}) \dots  (\forall
v_{q}) (\varphi
\leftrightarrow \varphi' )$
\end{enumerate}

\end{lemma}


\begin{exercise} Prove the above lemma by induction on the complexity
of $\varphi$. As a reward, note that this lemma can be used to shorten future proofs by induction on complexity of formulas.
\end{exercise}

\addcontentsline{toc}{section}{Prenex Normal Form}

\begin{definition}
\index{prenex normal form}%
 A formula $\varphi $ is said to be in
\emph{prenex
normal form} whenever 
\begin{itemize}
\item[(1)] there are no quantifiers occurring in $\varphi $, or 
\item[(2)] $\varphi $ is $(\exists v_{i}) \psi$ where $\psi$ is in prenex normal 
form and $v_{i}$ does not occur bound in $\psi$, or
\item[(3)] $\varphi $ is $(\forall v_{i}) \psi$ where $\psi$ is in prenex normal 
form and $v_{i}$ does not occur bound in $\psi$.
\end{itemize}
\end{definition}

\begin{rem}
If $\varphi $ is in prenex normal form, then no variable occurring in $\varphi $ occurs both free and bound and no bound variable occurring in $\varphi $ is bound by more than one quantifier.
In the written order, all of the quantifiers precede all of the connectives.
\end{rem}

\begin{lemma}\label{L:prenex} Let $\varphi (v_{0} , \dots , v_{p}) $
be any formula
of a language $\mathcal{L} $. There is a 
formula $\varphi^*  $ of $\mathcal{L} $  which has the following
properties:

\begin{enumerate}
\item $\varphi^* $ is in prenex normal form
\item $\varphi $ and $\varphi^* $ have the same free occurrences of 
variables, and 
\item $\models (\forall v_{0}) \dots (\forall v_{p})(\varphi
\leftrightarrow \varphi^* )$

\end{enumerate}

\end{lemma}

\begin{exercise} Prove this lemma by induction on the complexity of
$\varphi$.
\end{exercise}

There is a notion of rank on prenex formulas --- the number of
alternations  of quantifiers. The usual formulas of elementary
mathematics have
prenex rank $0$, i.e. no alternations of quantifiers.  For example: \[
(\forall x) ( \forall y) ( 2 xy \leq x^2 + y^2) . \]
However, the $\epsilon - \delta$ definition of a limit of a function
has prenex rank 2 and is much more difficult for students to comprehend
at first sight: \[ (\forall \epsilon ) (\exists \delta ) (\forall x ) ( ( 0 <
\epsilon \wedge 0 < | x-a| < \delta) \to | F (x) - L | < \epsilon). \] 
A formula of prenex rank 4 would make any mathematician look twice.














\chapter{Notation and Examples}

 Although the formal notation for
formulas is precise, it can become cumbersome and difficult to read.
Confident that the
reader would be able, if necessary,  to put formulas into their formal
form, we will
relax our formal behaviour.  In particular,
 we will write formulas any way we want using appropriate symbols
for variables, constant symbols, function and relation symbols.  We
will omit 
parentheses or add them for clarity.  We will use
binary
function and relation symbols  between the arguments rather than in
front as is the usual case
for ``plus'', ``times'' and ``less than''.

Whenever a language $\lan$ has only finitely many relation, function and
constant symbols we often write, for example: \[ \lan = \{ < , R_0 , + ,
F_1 , c_0 , c_1 \} \] omitting explicit mention of the logical symbols
(including the infinitely many variables) which are always in $\lan$.
Correspondingly we may denote a model $\ma$ for $\lan$ as: \[ \ma =
\langle \ba , \pmb{<}, \bf{S}_{0} , \pmb{+}, \bf{G}_{1} ,
\bf{a}_{0} ,\bf{a}_{1} \rangle \]
where the interpretations of the symbols in the language $\lan$ are
given by 
 $\mathcal I (<) = \; \pmb{<}$, $\mathcal I (R_0) = \bf{S_0}$,
  $\mathcal
I (+) = \; \pmb{+}$ , $ \mathcal I (F_1) = \bf{G}_{1}$, $ \mathcal{I}
(c_0)
= \bf{a}_{0} $ and $ \mathcal I (c_1) = \bf{a_1} $.



\begin{examples}\label{X:real}
\index{ $\langle \mathbb R ,\pmb{<} , \pmb{+} ,\mathbf{\cdot}
, \mathbf{0}, \mathbf{1} \rangle $}%
\index{ $\langle \mathbb Q ,\pmb{<} , \pmb{+} ,\mathbf{\cdot}
, \mathbf{0}, \mathbf{1} \rangle $}%
\index{ $\langle \mathbb C , \pmb{+} ,\mathbf{\cdot}
, \mathbf{0}, \mathbf{1} \rangle $}%
\index{real numbers}%
\index{rational numbers}%
\index{complex}%
 $\mathfrak R = \langle \mathbb R , \pmb{<} , \pmb{+} , \mathbf{\cdot}
,\mathbf{0}, \mathbf{1} \rangle $ and
 $\mathfrak Q = \langle \mathbb Q ,\pmb{<} ,\pmb{ +} ,
\mathbf{\cdot},\mathbf{0}, \mathbf{ 1} \rangle $,  where $\mathbb R$
is the reals,
$\mathbb Q$ the
rationals ,
are models for the language $\lan = \{ <, + , \cdot , 0,1 \}$. Here 
${<}$ is a binary relation symbol, ${ +}$  and ${\cdot}$
are binary function symbols, ${0}$ and 
${ 1}$ are constant symbols whereas $\pmb{<}$, $\pmb{+} $,
$\mathbf{\cdot}$, $\mathbf{0}$, $\mathbf{1}$  are the well
known
relations, arithmetic functions and
constants.

Similarly, $\mathfrak C = \langle \mathbb C , \pmb{+} ,\mathbf{\cdot} ,
\mathbf{0} ,
\mathbf{1} \rangle $, where
$\mathbb C$ is the complex numbers, is a model for the language $\lan =
\{ +, \cdot, 0 , 1 \} $.  Note the exceptions to the boldface
convention for these popular sets.

 \end{examples}

\begin{examples}\label{X:theory} Here $\mathcal{L} = \{ < , + ,
\cdot ,
0 , 1 \}$, where $<$ is a binary relation symbol, $+$ and $\cdot$ are
binary function symbols
and $0$ and $1$ are constant symbols.  The following  
formulas are sentences.

\begin{enumerate}
%1
\item $(\forall x) \neg (x < x)$
%2

\item $(\forall x)( \forall y ) \neg (x <y \wedge y < x  )$

%3
\item $(\forall x)(\forall y)(\forall z ) ( x < y \wedge y < z \to x
< z)$

%4
\item  $(\forall x )(\forall y  ) (x < y \vee y < x \vee x = y)$

%5
\item  $(\forall x)(\forall y ) ( x < y  \to ( 
\exists z) (x < z  \wedge z < y))$

%6
\item $(\forall x ) (\exists y) ( x < y)$

%7
\item $(\forall x) (\exists y) (y < x)$
%8
\item $ (\forall x)(\forall y)(\forall z)( x+(y+z) = (x+y)+z
) $
\item $(\forall x) (x+0 =x)$
%10
\item $(\forall x) (\exists y) (x+y = 0 )$

%11
\item $ (\forall x) (\forall y) (x+y = y+x)$


\item $(\forall x)(\forall y)(\forall z) (x \cdot (y \cdot z)
= (x 
\cdot y) \cdot z)$

\item $(\forall x) (x \cdot 1 = x )$


%17
\item $(\forall x ) ( x = 0 \vee (\exists y) (y 
\cdot x  = 1 ))$


%14
\item $(\forall x)(\forall y) (x \cdot y = y \cdot x)$

%15
\item $(\forall x)(\forall y)(\forall z ) ( x \cdot (y+z) = (x
\cdot y) + (y 
\cdot z) )$


%18
\item $0  \neq 1$



%23
\item $( \forall x)(\forall y)(\forall z) (x < y \to x +z < y+z)$


\item $(\forall x)(\forall y)(\forall z) (x < y \wedge 0 < z \to x
\cdot z < y 
\cdot z)$



%20
\item for each $n \geq 1$ we have the formula
\[ (\forall x_{0})(\forall x_{1}) \cdots (\forall x_{n})(\exists y)
(x_{n} \cdot y^{n} + 
x_{n-1} \cdot y^{n-1} + \cdots + x_{1} \cdot y +x_{0} = 0 
\vee x_{n} =0)
\]

where, as usual, $y^{k}$ abbreviates $\overbrace{y \cdot y \cdot
\cdots \cdot y}^{k}$ 
 
\end{enumerate}

The latter formulas express that each polynomial of degree $n$ has a
root.  The following formulas express the intermediate value property
for polynomials of degree $n$: if the polynomial changes sign from $w$
to $z$, then it is zero at some $y$ between $w$ and $z$.



%21

(21) for each $n \geq 1$ we have  \begin{multline*}
 (\forall x_0) \dots (\forall x_n) 
(\forall w ) (\forall z) [ (x_n \cdot w^n + x_{n-1} \cdot w^{n-1} +
\cdots + x_1 \cdot w + x_0 )\cdot \\
 (x_n \cdot z^n + x_{n-1} \cdot z^{n-1} + \cdots + x_1 \cdot z + x_0)
<0 \\
\to (\exists y)((( w< y \wedge y < z ) \vee (z < y \wedge y < w ))\\
\wedge (x_n \cdot y^n + x_{n-1}
\cdot y^{n-1} + \cdots + x_1 \cdot y + x_0 = 0 ))] 
\end{multline*} 



\end{examples}

The most fundamental concept is that of a sentence $\sigma$ being true
when interpreted in a model $\ma$.  We write this as $\ma \models
\sigma$, and we extend this concept in the following definitions.


\begin{definition}
\index{$\models$}%
\index{satisfaction!$\mathfrak{A} \models \Sigma$}%
 If $\Sigma$ is a set of
sentences, $\mathfrak{A}$ is
said to be a 
\emph{model} of $\Sigma$, written $\mathfrak{A} \models \Sigma$, 
whenever 
$\mathfrak{A} \models \sigma $ for each $\sigma \in \Sigma$.
 $\Sigma $ is said to be \emph{satisfiable} iff there
is some 
$\mathfrak{A}$ such that $\mathfrak{A} \models \Sigma$.

\end{definition}


\begin{definition}\label{D:theory}
\index{theory}%
A \emph{theory} $\mathcal{T}$ is a set of sentences. If $\mathcal{T} $
is a theory and $\sigma$ is a sentence, we write 
$\mathcal{T} \models \sigma$ whenever we have that for all $\mathfrak{A}$ 
if $\mathfrak{A} \models \mathcal{T} \mbox{ then } \mathfrak{A} \models 
\sigma$. We say that $\sigma$ is a \emph{consequence} of $\mathcal{T}$. A 
theory is said to be \emph{closed} whenever it contains all of its 
consequences.

\end{definition}

\begin{definition}
\index{$\mbox{Th} \mathfrak{A}$}%
\index{theory of $\mathfrak{A}$}%
  If $\ma$ is a model for the language
$\lan$, the
\emph{theory of} $\ma$, denoted by $\Th \ma$, is defined to be the set
of all sentences of $\lan$ which are true in $\ma$, \[ \{ \sigma
\mbox{ of } \lan : \ma \models \sigma \}. \]

This is one way that a theory can arise.  Another way is through
axioms.

\end{definition}


\begin{definition}
\index{axioms}%
 $\Sigma \subseteq \mathcal{T}$ is said to be a set of
\emph{axioms} for 
$\mathcal{T}$ 
whenever $\Sigma  \models \sigma$ for every $\sigma$ in $\mathcal{T}$;
in this case we write $ \Sigma \models \mathcal{T}$.

\end{definition}


\begin{rem} We will generally assume our theories are closed and we
will often describe theories by specifying a set of axioms $\Sigma$.
The theory will then be all consequences $\sigma$ of $\Sigma$.
\end{rem}

\begin{examples}\label{X:axioms}
\index{DLO}%
\index{dense linear orders without endpoints!axioms,theory of}%
\index{LOR}%
\index{linear orders!axioms,theory of}%
\index{ACF}%
\index{algebraically closed fields!axioms,theory of}%
\index{RCF}%
\index{real closed ordered fields!axioms,theory of}%
\index{FLD}%
\index{fields!axioms,theory of}%
\index{ORF}%
\index{ordered fields!axioms,theory of}%
  We will consider the following theories and their axioms.
\begin{enumerate} 



%1
\item The theory of Linear Orderings (LOR) is a theory in the language 
$\{ < \}$ which has as axioms sentences~1-4 from
Example~\ref{X:theory}.

%2
\item The theory of Dense Linear Orders (DLO) is a theory in the language 
$\{ < \}$ which has as axioms all the axioms of LOR, and sentences~5, 6 and 7 of Example~\ref{X:theory}.

%3
\item The theory of Fields (FLD) is a theory in the language 
$\{0, 1, +, \cdot \}$  which has as  axioms sentences~8-17 from Example \ref{X:theory}.

%4
\item The theory of Ordered Fields (ORF) is a theory in the language given by  
$\{<,0,1,+,\cdot \}$ which has as axioms all the axioms of FLD, LOR and  sentences~18 and 19 from Example~\ref{X:theory}.

%5
\item The theory of Algebraically Closed Fields (ACF) is a theory in the language 
$\{0,1, +, \cdot \}$ which has as axioms all the axioms of FLD  and all sentences from 20 of Example~\ref{X:theory}, i.e. infinitely many sentences, one for each 
$n \geq 1$.


%6
\item The theory of Real Closed Ordered Fields (RCF) is a theory in the language 
$\{ < ,0 ,1, +, \cdot \}$ which has as axioms all the axioms of ORF, and all sentences from 21 of Example~\ref{X:theory}, i.e. infinitely many sentences, one for each $n \geq 1$.


\end{enumerate}

\end{examples}

\begin{exercise}\label{X:dloivt} Show that :
\begin{enumerate}
\item $\mathfrak Q \models \mbox{ DLO}$
\item $\mathfrak R \models \mbox{ RCF}$ using the Intermediate Value
theorem
\item $\mathfrak C \models \mbox{ ACF}$ using the Fundamental Theorem of
Algebra
\end{enumerate}
where $\mathfrak Q$, $\mathfrak R$ and $\mathfrak C$ are as in Example
\ref{X:real}.
\end{exercise}

\begin{rem}
\index{real closed ordered fields!axioms, theory}%
\index{real closed ordered fields!Intermediate Value Property}%
 The theory of Real Closed Ordered Fields is sometimes
axiomatised differently.  All the axioms of ORF are retained, but the
sentences from 21 of Example~\ref{X:theory}, which amount to an
Intermediate Value Property, are replaced by the sentences from 20 for
odd $n$ and the sentence \[ ( \forall x)( 0< x \to ( \exists y ) y^2 =
x ) \] which states that every positive element has a square root.  A
significant amount of algebra would then be used to verify the
Intermediate Value Property from these axioms.

\end{rem}

\chapter{Compactness and Elementary Submodels}
\addcontentsline{toc}{section}{The Compactness Theorem}
\begin{theorem}\label{T:Malcev}
\index{Compactness Theorem}%
The Compactness Theorem (Malcev)\\
A set of sentences is satisfiable iff every finite subset is
satisfiable.
\end{theorem}

\begin{proof}
There are several proofs. We only point out here that it is an easy 
consequence  of the following theorem which appears in all
elementary logic texts:

\begin{proposition}\label{P:Malcev}
\index{Completeness Theorem}%
The Completeness Theorem (G\"{o}del, Malcev)\\
A set of sentences is consistent if and only if it is satisfiable.
\end{proposition}

 Although we do not here formally define ``consistent'', it
does mean what you think it does.  In particular, a set of sentences is
consistent if and only if each finite subset is consistent.

\end{proof}

\begin{rem}  The Compactness Theorem is the only one for which we do
not give a complete proof. For the reader who has not previously seen the
Completeness Theorem, there are other proofs of the Compactness Theorem  
which may be more easily
absorbed: set theoretic (using ultraproducts), topological (using
compact spaces, hence the name) or Boolean algebraic.  However these
topics are too far afield to enter into the proofs here.  We will use
the Compactness Theorem as a
starting point ---  in fact, all that follows can be seen as its
corollaries.
\end{rem} 

\begin{exercise}  Suppose $\tee$ is a theory for the language $\lan$
and $\sigma$ is a sentence of $\lan$ such that $\tee \models \sigma$.
Prove that there is some finite $\tee' \seq \tee$ such that $\tee'
\models \sigma$. Recall that $\tee \models \sigma$ iff $\tee \cup \{
\neg \sigma \}$ is not satisfiable.
\end{exercise}


\begin{definition}
\index{$\subseteq$}%
\index{expansion!language}%
\index{reduction!language}%
 If $\mathcal{L}$, and $\mathcal{L}'$ are two
languages 
such that $\mathcal{L} \subseteq \mathcal{L}'$ we say that $\mathcal{L}'$ 
is an \emph{expansion} of $\mathcal{L} \mbox{ and } \mathcal{L}$ is a 
\emph{reduction} of $\mathcal{L}'$. Of course when we say that
$\mathcal{L} \subseteq \mathcal{L}'$ we also mean that the constant, function and relation symbols of $\mathcal{L}$ remain (respectively) constant, function and relation symbols of the same type in $\mathcal{L}'$.
\end{definition}

\begin{definition}
\index{reduction!model, $\reduct$}%
\index{expansion!model}% 
\index{$\reduct$}%
Given a model $\mathfrak{A}$ for the language $\mathcal{L}$, we can 
expand it to a model $\mathfrak{A}'$ of $\mathcal{L}'$, where $\mathcal{L}'$ 
is an expansion of $\mathcal{L}$, by giving 
appropriate interpretations to the symbols in $\mathcal{L}'\setminus 
\mathcal{L}$. We say that $\mathfrak{A}'$ is an \emph{expansion} of 
$\mathfrak{A}$ to $\mathcal{L}'$ and that $\mathfrak{A}$ is a 
\emph{reduct} of $\mathfrak{A}' $ to $ \mathcal{L}$. We also use the
notation $\ma' | \lan $ for the reduct of $\ma'$ to $\lan$.
\end{definition}

\begin{theorem}\label{T:compact} If a theory $\mathcal{T}$ has arbitrarily 
large finite models, then it has an infinite model.
\end{theorem}

\begin{proof} Consider new constant symbols $c_{i} \mbox{ for } i \in 
\mathbb{N}$, the usual natural numbers,  and expand from $\mathcal{L}$,
the language of $\mathcal{T}$, to 
$\mathcal{L}' = \mathcal{L} \cup \{ c_{i} : i \in \mathbb{N} \}$.

Let \[ \Sigma = \mathcal{T} \cup \{ \neg c_{i} = c_{j} : i \neq j, i,j 
\in \mathbb{N} \}. \]

We first show that  every finite subset of $\Sigma$ has a model by
interpreting the finitely many relevant constant symbols as different
elements in an expansion of some finite model of $\theory$.
 Then we use 
compactness to get a model $\ma'$ of $\Sigma$.

The model that we require is for the language $\lan$, so we take $\ma$ to
be the reduct of $\ma'$ to $\lan$.

\end{proof}

\addcontentsline{toc}{section}{Isomorphisms, elementary equivalence and
complete theories}

\begin{definition}
\index{isomorphic models}%
 Two models $\mathfrak{A} $ and
$\mathfrak{A}'$ for 
$\mathcal{L}$ are said to be \emph{isomorphic} whenever there is a
bijection $f: \mathbf{A} \to \mathbf{A}'$ such that 

\begin{enumerate}
\item for each n-placed relation symbol $R$ of $\mathcal{L}$ and 
corresponding interpretations $S$ of $\mathfrak{A}$ and $S'$ of 
$\mathfrak{A}'$ we have \[ S(x_{1} , \dots ,x_{n}) \mbox{ iff } 
S'(f(x_{1}), \dots ,f(x_{n})) \mbox{ for all } \xnot[1]{n} \mbox{ in } 
\mathbf{A} \]


\item for each n-placed function symbol $F$ of $\mathcal{L}$ and 
corresponding interpretations $G$ of $\mathfrak{A}$ and $G'$ of 
$\mathfrak{A}'$ we have \[ f(G(x_{1} , \dots ,x_{n})) = 
G'(f(x_{1}), \dots ,f(x_{n})) \mbox{ for all } \xnot[1]{n} \mbox{ in } 
\mathbf{A} \]



\item for each constant symbol $c$ of $\mathcal{L}$ and corresponding 
constant elements $a$ of $\mathfrak{A}$ and $a'$ of $\mathfrak{A}'$ we 
have $f(a)=a'$.

\end{enumerate}
We write $\mathfrak{A} \cong \mathfrak{A}'$. This is an equivalence relation.

\end{definition}

\begin{examples}\label{X:standard}
\index{Number Theory}%
\index{ $\langle \mathbb{N},\pmb{ +}, \pmb{\cdot} , \pmb{<} ,\pmb{ 0},
\pmb{1} \rangle$}%
 Number theory is Th$\langle \mathbb{N}, \pmb{+} , 
\pmb{\cdot} , \pmb{< }, \pmb{0} ,\pmb{ 1} \rangle$,  the set of all
sentences of $\mathcal{L} = \{ + , \cdot , < , 0 , 1 \}$
which are true in
 $\langle \mathbb{N},\pmb{ +}, 
\pmb{\cdot} , \pmb{<} ,\pmb{ 0}, \pmb{1} \rangle$,  the standard model
which we all learned in
school. Any model not isomorphic to the standard model of number theory is said to be a non-standard model of number theory.
\end{examples}

\begin{theorem}\label{T:nonstd} (T. Skolem) \\
\index{T. Skolem}%
\index{number theory!non-standard models}%
 There exist non-standard
models of 
number theory.
\end{theorem}

\begin{proof} Add a new constant symbol $c$ to $\lan$. 
Consider \[ \Th\langle \mathbb{N}, + , \cdot ,<,0,1 \rangle  
\cup \{ \overbrace{1+1+\dots +1}^{n} <c  : n \in \mathbb{N} \} \] and
use
the Compactness Theorem.  The interpretation of the constant symbol $c$
will not be a natural number. 
\end{proof}
 

\begin{definition}
\index{elementarily equivalent models}%
 Two models $\ma$ and $\ma'$ for $\lan$
are said to be  
\emph{elementarily equivalent} 
whenever we have that for each sentence $\sigma$ of $\mathcal{L}$ \[\ 
\mathfrak{A} \models \sigma \mbox{ iff } \mathfrak{A}' \models \sigma \]

We write $\ma \equiv \ma'$. This is another equivalence relation.
 
\end{definition}


\begin{exercise}\label{X:iso} Suppose $f: \ma \to \ma'$ is an
isomorphism and
$\varphi$ is a formula such that $\ma \models \varphi [ \anot k ] $ for
some $\anot k$ from $\ba$; prove $\ma' \models \varphi [ f(a_0) , \dots ,
f(a_k)]$.


Use this to show that $\ma \cong \ma'$ implies $\ma \equiv \ma'$.
\end{exercise}


\begin{definition}
\index{submodel}%
\index{$\mathfrak{A} \subseteq \mathfrak{B}$}%
 A model $\mathfrak{A}'$ is called a \emph{submodel} of $\mathfrak{A}$, and we
 write $\mathfrak{A}' \subseteq \mathfrak{A}$ whenever  $\phi \neq \mathbf{A}' \subseteq \mathbf{A}$ and 

\begin{enumerate}
\item each n-placed relation $S'$ of $\mathfrak{A}'$ is the restriction 
to $\mathbf{A}'$ of the corresponding relation $S$ of $\mathfrak{A}$, 
i.~e.\ $S'=S \cap (\mathbf{A}')^{n} $



\item each m-placed function $G'$ of $\mathfrak{A}'$ is the restriction 
to $\mathbf{A}'$ of the corresponding function $G$ of $\mathfrak{A}$, 
i.~e.\ $G' =G \! \upharpoonright \! (\mathbf{A}')^{m} $


\item each constant of $\mathfrak{A}'$ is the corresponding constant of 
$\mathfrak{A}$.\\

\end{enumerate}

\end{definition}

\begin{definition}
\index{elementary submodel}%
\index{elementary extension}%
\index{$\prec$}%
 Let $\mathfrak{A}$ and $\mathfrak{B}$ be
two models 
for $\mathcal{L}$. We say $\mathfrak{A}$ is an \emph{elementary 
submodel} of $\mathfrak{B}$ and $\mathfrak{B}$ is an \emph{elementary 
extension} of $\mathfrak{A}$ and we write $\mathfrak{A} \prec 
\mathfrak{B}$ whenever
\begin{enumerate}
\item $\ba \subseteq \bb$ and
\item for all formulas $\varphi (v_{0}, \dots, v_{k}) $ of $\mathcal{L}$ 
and all $a_{0}, \dots , a_{k} \in \mathbf{A}$ \[ \mathfrak{A} \models 
\varphi [a_{0}, \dots, a_{k}] \mbox{ iff } \mathfrak{B} \models \varphi 
[a_{0}, \dots ,a_{k}]. \]
\end{enumerate}
 \end{definition}

\begin{exercise} Prove that: 
\begin{itemize} 
\item  if $\ma \seq \mb$ and $\mb \seq \mc$ then $\ma \seq \mc $, 
\item if  $\ma \prec \mb$ and $\mb \prec \mc$ then $\ma \prec \mc$,
\item if $\ma \prec \mb$ then $\ma \seq \mb$ and $\ma \equiv \mb$.
\end{itemize}
\end{exercise}

\begin{examples}
 Let $\mathbb N$ be the usual natural numbers with
$\pmb{<}$ as
the usual ordering.  Let $\mb = \langle \mathbb N ,\pmb{ <} \rangle$
and $\ma
= \langle \mathbb N \setminus \{ 0 \} ,\pmb{ <} \rangle$ be models for
the
language with one binary relation symbol $<$.  Then $\ma \seq \mb$ and
$\ma \equiv \mb$; in fact $\ma \cong \mb$.  But we do not have $\ma
\prec \mb$; $1$ satisfies the formula describing the least element of the ordering in $\ma$ but in $\mb$. So we see that being an elementary submodel is a very strong
condition indeed.  Nevertheless, later in the chapter we will obtain
many examples of elementary submodels. \end{examples}


\begin{definition}
\index{chain of models}%
\index{$\mathfrak{A}=  \cup \{ \mathfrak{A}_{n} :n \in \mathbb N\}$}%
 A \emph{chain of models} for a language
$\mathcal{L}$ 
is an increasing sequence of models \[ \mathfrak{A}_{0} \subseteq 
\mathfrak{A}_{1} \subseteq \dots \subseteq \mathfrak{A}_{n} \subseteq 
\cdots \quad n \in \nat . \]

 The \emph{union} of the chain is defined to be the model 
$\mathfrak{A}=  \cup \{ \mathfrak{A}_{n} :n \in \nat\} $ where
the universe of 
$\mathfrak{A}$ is $ \ba = \cup \{  \ba_{n} :n \in \nat\}$
and: 
\begin{enumerate}
\item each relation $S$ on $\mathfrak{A}$ is the union of the
corresponding relations $S_{n}$ of $\mathfrak{A}_{n}$; $S =
\cup \{  S_{n}:n \in \nat \} $, i.e. the relation
extending each $S_n$

\item each function $G$ on $\mathfrak{A}$ is the union of the
corresponding functions $G_{n}$ of $\mathfrak{A}_{n}$; $G =
\cup \{  G_{n} :n \in \nat \} $, i.e. the function
extending each $G_n$

\item all the models $\mathfrak{A}_{n}$ and $ \mathfrak{A}$ have the
same constant elements.

\end{enumerate} Note that each $\mathfrak{A}_{n} \subseteq
\mathfrak{A}$.  

\end{definition}

\begin{rem}
 To be sure, what is defined here is a chain of models
indexed by the natural numbers $\nat$.  More generally, a chain of
models could be indexed by any ordinal. However we will not need the
concept of an ordinal at this point.
\end{rem}

\begin{examples} For each $n \in \mathbb{N}$, let \[\ba _{n} = \{ -n , -n+1,
-n+2, \dots , 0,1,2,3, \dots \} \subseteq \mathbb{Z}.\] 

Let $\mathfrak{A}_{n} = \langle \mathbf{A}_{n}, \leq \rangle $. Each
$\mathfrak{A}_{n} \equiv \mathfrak{A}_{0} $, but we don't have
$\mathfrak{A}_{0} \equiv \cup \{\mathfrak{A}_{n} : n \in
\mathbb{N} \} $. 

\end{examples}

\addcontentsline{toc}{section}{The Elementary Chain Theorem}
\begin{definition}
\index{chain of models!elementary}%
 An \emph{elementary chain} is a chain
of models $\{
\mathfrak{A}_{n} : n \in \nat \}$ such that for each $m < n $ we have
$\mathfrak{A}_{m} \prec \mathfrak{A}_{n}$.
\end{definition}

\begin{theorem}\label{T:tec} (Tarski's Elementary Chain Theorem) \\
\index{Tarski's Elementary Chain Theorem}%
\index{Elementary Chain Theorem}%
Let $\{ \mathfrak{A}_{n} : n \in \nat \}$ be an elementary chain.
For all $n \in \nat$ we have \[\mathfrak{A}_{n} \prec
\cup \{ \mathfrak{A}_{n} :n \in \nat \}.\]

\end{theorem}

\begin{proof}  Denote the union of the chain by $\ma$.  We have $\ma_k
\seq \ma$ for each $k \in \mathbb N$.

\begin{claim}  If $t$ is a term of the language $\lan$ and $\anot p$ are
in $\ba_k$, then the value of the term $t [ \anot p ]$ in $\ma$ is equal
to the value in $\ma_k$.
\end{claim}

\begin{proof}[Proof of  Claim] We prove this by induction on the
complexity of the term.

\begin{enumerate} 
\item  If $t$ is the variable $v_i$ then both values are just
$a_i$.
\item If $t$ is the constant symbol $c$ then the values are equal because
$c$ has the same interpretation in $\ma$ and in $\ma_k$.
\item If $t$ is $F( \tnt[1]{m}) $ where $F$ is a function symbol and
$\tnot[1]{m}$ are terms such that each value $t_i [ \anot p ]$ is the same
in both $\ma$ and $\ma_k $, then the value \[ F( \tnt[1]{m})[\anot p ] \]
in
$\ma$ is \[G(t_1 [ \anot p], \dots , t_m [ \anot p])\] where $G$ is the
interpretation of $F$ in $\ma$ and the value of \[F( \tnt[1]{m}) [\anot
p]\] in $\ma_k$ is \[G_k ( t_1 [\anot p ], \dots , t_m [ \anot p ])\] 
where
$G_k$ is the interpretation of $F$ in $\ma_k$.  But $G_k$ is the
restriction of $G$ to $\ba_k$ so these values are equal.
\end{enumerate}
\renewcommand{\qedsymbol}{}
\end{proof}

In order to show that each $\ma_k \prec \ma$ it will suffice to prove
the following statement  for each formula $\varphi ( \vnot p )$ of
$\lan$. 
 \begin{quote} `` For all $k \in \mathbb N$ and all $\anot p$
in $\ba_k$:  \[ \ma \models \varphi [ \anot p ] \mbox{ iff } \ma_k
\models \varphi [ \anot p ] . \mbox{''} \]
 \end{quote}


\begin{claim}  The statement is true whenever $\varphi$ is $t_1 = t_2$
where $t_1$ and $t_2$ are terms.
\end{claim}

\begin{proof}[Proof of Claim] Fix $k \in \nat$ and $\anot p$ in
$\ba_k$.  \[ \begin{aligned} \ma \models (t_1 = t_2)[ \anot p ] &\mbox{
iff } t_1 [\anot p] = t_2 [ \anot p ]  \mbox{ in } \ma \\
&\mbox{ iff } t_1 [\anot p ] = t_2 [ \anot p ] \mbox{ in } \ma_k \\
&\mbox{ iff } \ma_k \models (t_1 = t_2 ) [\anot p ]. \end{aligned}\]
\renewcommand{\qedsymbol}{}
\end{proof}

\begin{claim}  The statement is true whenever $\varphi$ is $R(
\tnt[1]{n} ) $ where $R$ is a relation symbol and $\tnot[1]{n}$ are
terms.
\end{claim}

\begin{proof}[Proof of Claim]  Fix $k \in \nat$ and $\anot p$ in
$\ba_k$.  Let $S$ be the interpretation of $R$ in $\ma$ and $S_k$ be
the interpretation in $\ma_k$; $S_k$ is the restriction of $S$ to
$\ba_k$.  \[ \begin{aligned}  \ma \models R ( \tnt[1]{n} ) [\anot p ]
&\mbox{ iff } S (t_1 [ \anot p ] , \dots , t_n [\anot p ] ) \\
&\mbox{ iff } S_k (t_1 [ \anot p ] , \dots , t_n [\anot p ] )\\
&\mbox{ iff } \ma_k \models R ( \tnt[1]{n} ) [\anot p ]
\end{aligned} \]

\renewcommand{\qedsymbol}{}
\end{proof}


\begin{claim}  If the statement is true when $\varphi $ is $\theta$,
then the statement is true when $\varphi$ is $\neg \theta$.
\end{claim}

\begin{proof}[Proof of Claim]  Fix $k \in \nat$ and $\anot p$ in
$\ba_k$.  \[ \begin{aligned} \ma \models ( \neg \theta ) [ \anot p ]
&\mbox{ iff not } \ma \models \theta [ \anot p ] \\
&\mbox{ iff not } \ma_k \models \theta [ \anot p ] \\
&\mbox{ iff } \ma_k \models ( \neg \theta ) [ \anot p ]. \end{aligned}
\]
\renewcommand{\qedsymbol}{}
\end{proof}


\begin{claim}  If the statement is true when $\varphi$ is $\theta_1$
and when $\varphi$ is $\theta_2$ then the statement is true when
$\varphi$
is $\theta_1 \wedge \theta_2$.
\end{claim}

\begin{proof}[Proof of Claim]  Fix $k \in \nat$ and $\anot p$ in $\ba_k
$.  \[ \begin{aligned} \ma \models ( \ta_1 \wedge \ta_2 ) [ \anot p ]
&\mbox{ iff } \ma \models \ta_1 [ \anot p ] \mbox{ and } \ma \models
\ta_2 [ \anot p ] \\
&\mbox{ iff }  \ma_k  \models \ta_1 [ \anot p ] \mbox{ and } \ma_k
\models \ta_2 [ \anot p ] \\
&\mbox{ iff }  \ma_k \models ( \ta_1 \wedge \ta_2 ) [ \anot p ] .
\end{aligned}
\]

\renewcommand{\qedsymbol}{}
\end{proof}


\begin{claim} If the statement is true when $\varphi$ is $\ta$ then the
statement is true when $\vp$ is $\exists v_i \ta$.
\end{claim}

\begin{proof}[Proof of Claim] Fix $k \in \nat$ and $\anot p$ in
$\ba_k$.  Note that \\
$\ba = \cup \{ \ba_j : j \in \nat \}$.
\[  \ma \models \exists v_i \ta [ \anot p ]  
 \mbox{ iff }
 \ma \models \exists v_i \ta [ \anot q ] \]
\begin{center} where $ q $ is the maximum of $ i$  and $ p$ (by Lemma 
\ref{L:sat}), \end{center}
\[\mbox{ iff } \ma \models \ta [ \anot{i - 1 } , a , \anot[i+1]{q} ] 
\mbox{ for some } a \in \ba, \]
\[\mbox{ iff } \ma \models \ta [ \anot{i-1}, a , \anot[i+1]{q} ] \]
\begin{center}  for some $ a \in \ba_l $ for some $ l \geq k $
\end{center}
\[\mbox{ iff } \ma_l \models \ta [ \anot{i-1}, a , \anot[ i+1]{q} ] \]
\begin{center} since the statement is true for $ \theta$, \end{center}
\[\mbox{ iff } \ma_l \models \exists v_i \ta [ \anot q ] \]
\[\mbox{ iff } \ma_k \models \exists v_i \theta [ \anot q ] 
 \mbox{ since } \ma_k \prec \ma_l  \]
\[ \mbox{ iff } \ma_k \models \exists v_i \ta [ \anot p ] \mbox{ (by
Lemma~\ref{L:sat})}. \]
\renewcommand{\qedsymbol}{}
\end{proof}

By induction on the complexity of $\vp$, we have proven the statement
for all formulas $\vp$ which do not contain the connectives $\vee $,
$\to$ and $\lra$ or the quantifier $\forall$.  To verify the statement
for all $\vp$ we use Lemma \ref{L:altform}.    Let $\vp$ be any formula
of $\lan$.  By Lemma \ref{L:altform}  there is a formula $\psi$ which
does not use $\vee$, $\to$, $\lra$ nor $\forall$ such that \[ \models
(\forall v_0 ) \dots (\forall v_p ) (\vp \lra \psi ) . \]
Now fix $k \in \nat$ and $\anot p$ in $\ba_k$.  We have 
\[ \ma \models (\vp  \lra \psi ) [ \anot p ] \mbox{ and } \ma_k \models
(\vp  \lra \psi ) [ \anot p ]. \]
\[\begin{aligned}  \ma \models \varphi [ \anot p ]  &\mbox{ iff } \ma
\models \psi [ \anot p ] \\
&\mbox{ iff }  \ma_k  \models \psi [ \anot p ] \\
&\mbox{ iff } \ma_k \models \vp [ \anot p ] \end{aligned} \]
which completes the proof of the theorem.


\end{proof}




\begin{lemma} (The Tarski-Vaught Condition) \\
\index{Tarski-Vaught Condition}%
Let $\mathfrak{A}$ and $\mathfrak{B}$ be  models for $\mathcal{L}$ with 
$\mathfrak{A} \subseteq \mathfrak{B}$. The following are equivalent:

\begin{itemize}
\item[(1)] $\mathfrak{A} \prec \mathfrak{B}$
\item[(2)] for any formula $\psi (v_{0}, \dots , v_{q})$ and any $i
\leq q$ 
and any $a_{0}, \dots , a_{q}$ from $\mathbf{A}$:

if there is some $b \in \bb$ such that 
\[ 
\mathfrak{B} \models  \psi [a_{0}, \dots ,a_{i-1},b, a_{i+1} , \dots ,
a_q ] \] then 
we have  some  $a \in \mathbf{A}$ such that \[ \mathfrak{B} \models \psi 
[a_{0}, \dots , a_{i-1}, a , a_{i+1}, \dots ,a_{q}]. \]

\end{itemize}
\end{lemma}
\begin{proof} Only the implication (2) $\Rightarrow$ (1) requires a lot 
of proof. We will prove that for each formula $\varphi (v_{0}, \dots , 
v_{p})$ and all $a_{0}, \dots , a_{p}$ from $\mathbf{A}$ we will have:
\[ \mathfrak{A} \models \varphi [a_{0} , \dots , a_{p}] \mbox{ iff } 
\mathfrak{B} \models \varphi [a_{0}, \dots , a_{p}] \] 
by induction on 
the complexity of $\varphi$ using only the negation symbol $\neg$, the 
connective $\wedge$ and the quantifier $\exists$ (recall Lemma
\ref{L:altform}).

\begin{enumerate} 
\item The cases of formulas of the form $t_1 = t_2$ and $R ( t_1 \dots
t_n)$  come immediately from the fact that
$\ma \seq \mb$.
\item For negation: suppose $\varphi$ is $\neg \psi$ and we have it for 
$\psi$, then 
\[ \mathfrak{A} \models \varphi [a_{0}, \dots , a_{p}] \mbox{  iff not } 
\mathfrak{A} \models \psi [a_{0}, \dots, a_{p}] \]           
\[ \mbox{ iff not }  \mathfrak{B} \models \psi [a_{0} , \dots , a_{p}]
\mbox{ iff } \mathfrak{B} \models \varphi [a_{0} ,\dots ,a_{p}]. \]

\item The $\wedge$ case proceeds similarly.

\item For the $\exists$ case we consider $\varphi$ as $\exists v_i \psi$.
If $\ma \models \exists v_i \psi [ \anot{p} ]$, then the inductive
hypothesis for $\psi$ and the fact that $\ba \seq \bb$ ensure that \\
$\mb \models \exists v_i \psi [ \anot p ]$.  It remains to show that if 
$\mb \models \varphi [\anot p ] $ then $\ma \models \varphi [\anot p
]$.

Assume $\mb \models \exists v_i \psi [\anot p ] $.  By Lemma
\ref{L:sat}, $\mb \models \exists v_i \psi [\anot q ] $ where q is the
maximum of $i$ and $p$.  By the definition of satisfaction, there is
some $b \in \bb$ such that \[\mb \models \psi [ \anot{i-1} , b ,
\anot[i+1]{q} ].\]  By (2), there is some $a \in \ba$ such that \[\mb
\models \psi [ \anot{i-1}, a , \anot[i+1]{q} ].\]  By the inductive
hypothesis on $\psi$, for that same $a \in \ba$, \[ \ma \models \psi [
\anot{i-1}, a , \anot[i+1]{q} ]. \]
By the definition of satisfaction, \[ \ma \models \exists v_i \psi [
\anot{q} ] .\]  Finally, by Lemma \ref{L:sat}, $\ma \models \phi [
\anot{p}] $.

\end{enumerate}
\end{proof}



Recall that $|\bb|$ is used to represent the cardinality, or size, of
the set $\bb$.  Note that since any language $\lan$ contains
infinitely many variables, $|\lan|$ is always infinite, but may be
countable or uncountable depending on the number of other symbols.
We often denote an arbitrary infinite cardinal by the lower case Greek
letter $\kappa$.

\addcontentsline{toc}{section}{The L\"{o}wenheim-Skolem Theorem}
\begin{theorem} (L\"{o}wenheim-Skolem Theorem) \\
\index{Lowenheim-Skolem Theorem}%
Let $\mathfrak{B}$ be a model for $\mathcal{L}$ and let $\kappa$ be any 
cardinal such that $\left| \mathcal{L} \right| \leq \kappa < \left|
\bb \right|$. 
Then $\mathfrak{B}$ has an elementary submodel $\mathfrak{A}$ of 
cardinality $\kappa$.

Furthermore if $ X \subseteq \mathbf{B} $ and $ |X | \leq \kappa$, then 
we can also have $ X \subseteq \mathbf{A}$. 

\end{theorem}

\begin{proof} Without loss of generosity assume $|X| = \kappa$.
We recursively define sets $X_{n}$ for $n \in \mathbb{N}$ such that $ X =
X_{0} \subseteq X_{1} \subseteq \dots \subseteq X_{n} \subseteq \cdots $ 
and such that for each formula $\varphi (v_{0} , \dots , v_{p})$ of 
$\mathcal{L}$ and each $i \leq p$ and each $a_{0}, \dots , a_{p}$ from $X_{n}
$ such that \[ \mathfrak{B} \models \exists v_{i} \varphi [a_{0} ,
\dots 
, a_{p}] \] we have  $x \in X_{n+1}$  such that 
\[ \mathfrak{B} 
\models \varphi [ a_{0}, \dots , a_{i-1} , x , a_{i+1} , \dots , a_{p} ] 
.\]
Since $| \mathcal{L} | \leq \kappa $ and each formula of $\lan$ is a
finite string of symbols from $\lan$, there are at most $\kappa$ many
formulas of $\lan$.  So there are at most $\kappa$ elements of $\bb$ that
need to be added to each $X_n$ and so,  without loss of generosity
each $|X_{n} | = \kappa $. Let $\mathbf{A} =  \cup \{ X_{n}: n \in
\mathbb{N} \}$; then $| \mathbf{A}| = \kappa $.
 Since $\mathbf{A}$ is closed under functions from 
$\mathfrak{B}$ and  contains all constants from $\mathfrak{B}$, 
$\mathbf{A}$ gives rise to a submodel $\mathfrak{A} \subseteq \mathfrak{B}$.

The Tarski-Vaught Condition is used to show that $\mathfrak{A} \prec 
\mathfrak{B}$.
\end{proof}

\begin{definition}
\index{complete theory}%
A theory $\mathcal{T}$ for a language $\mathcal{L}$ is said to be 
\emph{complete} whenever for each sentence $\sigma$ of $\mathcal{L}$ 
either $\mathcal{T} \models \sigma \mbox{ or } \mathcal{T} \models \neg 
\sigma$.
\end{definition}

\begin{lemma}\label{L:com}  A theory $\mathcal{T}$ for $\mathcal{L}$ is
complete iff any 
two models of $\mathcal{T}$ are elementarily equivalent.
\end{lemma}
\begin{proof}
$( \Rightarrow )$ easy.  $(\Leftarrow)$ easy. 
\end{proof}

\begin{definition}
\index{categorical!$\kappa$-categorical theory}%
 A theory $\mathcal{T}$ is said to be
\emph{categorical } in cardinality $\kappa$ whenever any two models of
$\mathcal{T}$ of 
cardinality $\kappa $ are isomorphic.  We also say that $\theory$ is
\emph{$\kappa$-~categorical}.
\end{definition}


The most interesting cardinalities in the context of categorical
theories are $\aleph_0$, the cardinality of countably infinite sets,
and $\aleph_1$, the first uncountable cardinal.


\begin{exercise}\label{X:cat} Show that DLO is $\aleph_0$-categorical.
There are two
well-known proofs.  One uses a back-and-forth construction of an
isomorphism.  The other constructs, by recursion, an isomorphism from the
set of dyadic rational numbers between $0$ and $1$: \[ \{ \frac{n}{2^m}
:
m \mbox{ is a positive integer and } n \mbox{ is an integer } 0 < n < 2^m
\}, \] onto a countable dense linear order without endpoints.

Now use the following theorem to show that DLO is complete.
\end{exercise}

\addcontentsline{toc}{section}{The {\L}o\'{s}-Vaught Test}
\begin{theorem} (The {\L}o\'{s}-Vaught Test) \\
\index{los-vaught Test@{\L}o\'{s}-Vaught Test}%
Suppose that a theory $\mathcal{T}$ has only infinite models for a
language $\lan$
and that $\mathcal{T}$ is $\kappa$-categorical for some cardinal $\kappa 
\geq | \mathcal{L} |$. Then $\mathcal{T}$ is complete.

\end{theorem}
%checked3

\begin{proof} We will show that any two models of $\mathcal{T}$ are 
elementarily equivalent.
Let $\mathfrak{A}$  of cardinality $\lambda_{1}$, and $\mathfrak{B}$ 
of cardinality $\lambda_{2}$, be two models of $\mathcal{T}$.

If $\lambda_{1} > \kappa $ use the L{\"{o}}wenheim-Skolem Theorem to get $\mathfrak{A}'$ such that $| \mathbf{A}'| = \kappa$ and $\mathfrak{A}' \prec \mathfrak{A}$.

If $\lambda_{1} < \kappa $ use the Compactness Theorem on the set of sentences
\[
   \Th \ma \cup \{ c_{\alpha} \neq c_{\beta} : \alpha \neq \beta \}
\]
where $\{ c_{\alpha} : \alpha \in \kappa \}$ is a set of new constant symbols of size $\kappa$, to obtain a model $ \mc $ for this expanded language such that 
$| \bc | \geq \kappa$. The reduct $\mc '$ to the language $\lan$ has the property that $\mc ' \models \Th \ma $ and hence $ \ma \equiv \mc '$. Now use the L{\"{o}}wenheim-Skolem Theorem to get $\mathfrak{A}'$ such that $| \mathbf{A}'| = \kappa$ and $\mathfrak{A}' \prec \mathfrak{C} '$.

Either way, we can get $\mathfrak{A}'$ such that $|\mathbf{A}'| = \kappa$ 
and $\mathfrak{A}' \equiv \mathfrak{A}$. \       
Similarly, we can get $\mathfrak{B}'$ such that $| \mathbf{B}' | = \kappa 
$ and $\mathfrak{B}' \equiv \mathfrak{B}$. \                   
Since $\mathcal{T}$ is $\kappa$~-categorical, $\mathfrak{A}' \cong 
\mathfrak{B}' $. Hence $\mathfrak{A} \equiv \mathfrak{B}$.
\end{proof}

Recall that the characteristic of a field is the prime number $p$ such
that \[ \overbrace{ 1 + 1 + \dots + 1}^p = 0 \] provided that such a
$p$
exists, and, if no such $p$ exists the field has characteristic 0.  All
of our best-loved fields: $\mathbb{Q}$, $\mathbb{R}$ and $\mathbb{C}$
have characteristic 0.  On the other hand, fields of characteristic
$p$ include the finite field of size $p$ (the prime Galois field).


\begin{theorem}\label{T:acf0}  The theory of algebraically closed 
fields of characteristic 0 is complete.
\end{theorem}

\begin{proof} We use the {\L}o\'{s}-Vaught Test and the following Lemma.
\end{proof}


\begin{lemma}\label{L:closed} Any two algebraically closed fields of
characteristic 0 and cardinality $\aleph_{1}$ are isomorphic.
\end{lemma}

\begin{proof}  Let $\ma$ be such a field containing the rationals $\mq
= \langle \rat , \pmb{+}, \pmb{\cdot}, \bf{0}, \bf{1} \rangle$ as a
prime subfield.  In a manner completely analogous to finding a basis
for a vector space, we can find a transcendence basis for $\ma$, that
is,  an indexed subset \\
$\{ a_\alpha : \alpha \in I \} \seq \ba$ such
that $\ma$ is the algebraic closure of the subfield $\ma'$ generated by
$\{ a_\alpha : \alpha \in I \}$ but no $a_\beta$ is in the algebraic
closure of the subfield generated by the rest: $\{ a_\alpha : \alpha
\in I \mbox{ and } \alpha \neq \beta \}$.

Since the subfield generated by a countable subset would be countable
and the algebraic closure of a countable subfield would also be
countable, we must have that the transcendence base is uncountable.
Since $|\ba| = \aleph_1$, the \emph{least} uncountable cardinal, we
must have in fact that $|I| = \aleph_1$.

Now let $\mb$ be any other algebraically closed field of characteristic
$0$ and size $\aleph_1$.  As above, obtain a transcendence basis $\{
b_\beta : \beta \in J \}$ with $|J| = \aleph_1$ and its generated
subfield $\mb'$.  Since $|I|=|J|$, there is a bijection $g: I \to
J$ which we can use to build an isomorphism from $\ma$ to $\mb$.

Since $\mb$ has characteristic $0$, a standard theorem of algebra gives
that the rationals are isomorphically
embedded into $\mb$.  Let this embedding be: \[ f : \mq
\hookrightarrow \mb .\]
We extend $f$ as follows:  for each $\alpha \in I$, let $f(a_\alpha) =
b_{g(\alpha)}$, which maps the transcendence basis of $\ma$ into the
transcendence basis of $\mb$.

We now extend $f$ to map $\ma'$ onto $\mb'$ as follows:  Each element
of $\ma'$ is given by \[
\frac{p(\anot[\alpha_1]{\alpha_m})}{q(\anot[\alpha_1]{\alpha_m})} ,\]
where $p$ and $q$ are polynomials with rational coefficients and the
$a$'s come, of course, from the transcendence basis.

Let $f$ map such an element to \[ \frac{  \bar{p} (
\bnot[g(\alpha_1)]{g (\alpha_m )})}{\bar{q}(\bnot[g (\alpha_1)]{g
(\alpha_m )})} \] where $\bar p$ and $\bar q$ are polynomials whose
coefficients are the images under $f$ of the rational coefficients of
$p$ and $q$.  


The final extension of $f$ to all of $\ma$ and $\mb$ comes from the
uniqueness of algebraic closures.

\end{proof}

\begin{rem}  Lemma \ref{L:closed} is also true when $0$ is replaced by
any
fixed characteristic and $\aleph_1$ by any uncountable cardinal.
\end{rem}



\begin{theorem}\label{T:fields} Let $\mathcal H$ be a set of sentences in
the 
language of 
field theory which are true in algebraically closed fields of 
arbitrarily high characteristic. Then $\mathcal H$ holds in some
algebraically closed field of characteristic 0.
\end{theorem}
\begin{proof} A field is a model in the language $\{ + , \cdot , 0 , 
1 \} $ of the axioms of field theory. Let ACF be the set of 
axioms for
 the theory of algebraically closed fields; see Example \ref{X:axioms}.
For each
$n \geq 2$, let 
$\tau_{n}$ denote the sentence \[ \neg (\overbrace{1+1+\dots+1}^{n}) 
= 0 \]

Let $\Sigma = \mbox{ACF} \cup \mathcal H \cup \{ \tau_{n} : n\geq 2 \}$

Let $\Sigma'$ be any finite subset of $\Sigma$ and let $m$ be the
largest 
natural number such that $\tau_{m} \in \Sigma'$ or let $m=1$ by default.

Let $\mathfrak{A}$ be an algebraically closed field of characteristic $p 
> m$ such that $\mathfrak{A} \models \mathcal H$; then in fact
$\mathfrak{A} 
\models \Sigma'$. 

So by compactness there is $\mathfrak{B}$ such that $\mathfrak{B} \models 
\Sigma$. $\mathfrak{B}$ is the required field.

\end{proof} \addcontentsline{toc}{section}{Every complex one-to-one
polynomial map is onto} \begin{corollary}\label{C:ACF} Let $\mathbb{C}$
denote, as usual, the complex numbers.  Every one-to-one polynomial map
$f:\mathbb{C}^{m} \to \mathbb{C}^{m}$ is onto.  \end{corollary}
\begin{proof} A \emph{polynomial map} is a function of the form \[
f(x_{1}, \dots , x_{m}) =\langle p_{1} (x_{1}, \dots, x_{m}), \dots,
p_{m}(x_{1}, \dots, x_{m}) \rangle \] where each $p_{i}$ is a
polynomial in the variables $x_{1}, \dots , x_{m}$.

We call max $\{ \mbox{ degree of } p_{i} : i \leq m\} $ the \emph{degree} 
of $f$.

Let $\mathcal{L}$ be the language of field theory and let $\theta_{m,n}$ 
be the sentence of $\mathcal{L}$ which expresses that
``each polynomial map of m variables of degree $<$ n which is
one-to-one 
is also onto''. 

We wish to show that there are algebraically closed fields of arbitrarily 
high characteristic which satisfy $\mathcal H = \{ \theta_{m,n} : m,n \in 
\mathbb{N} \}$. We will then apply Theorem \ref{T:fields},
Theorem~\ref{T:acf0}, Lemma~\ref{L:com} and Exercise~\ref{X:dloivt}
and be 
finished.

Let $p$ be any prime and let $F_{p}$ be the prime Galois field of size 
$p$. The algebraic closure $\tilde{F_{p}}$ is the countable union of a 
chain of finite fields 
\[F_{p}=A_{0}  \subseteq A_{1 } 
\subseteq A_{2 } \subseteq \cdots  \subseteq A_{ k} 
\subseteq A_{ k+1} \subseteq \cdots \]
obtained by recursively adding roots of polynomials.

We finish the proof by showing that each $\langle \tilde{F_{p}},
\pmb{+}, \bf{\cdot}, \bf{0}, \bf{1} \rangle$ satisfies $\mathcal H$.

Given any polynomial  map $f:(\tilde{F_{p}}^{m}) \to 
(\tilde{F_{p}}^{m})$ which is one-to-one, we show that $f$ is also
onto.  Given  any elements $b_{1}, \dots 
,b_{m} \in \tilde{F_{p}} $, there is some $A_{k}$ containing $b_{1}
, 
\dots , b_{m} $ as well as all the coefficients of f.

Since $f$ is one-to-one, $f \! \upharpoonright \! A_{k}^{m}  :A_{k}^{m}  \to 
A_{k}^{m} $ is a one-to-one polynomial map.

Hence, since $A_{k}^{m}$ is finite, $f \! \upharpoonright \! A_{k}^{m}$ is onto 
and so there are $a_{1}, \dots ,a_{m} \in A_{k}$ such that $f(a_{1}, 
\dots, a_{m}) =\langle b_{1}, \dots ,b_{m} \rangle$. Therefore $f$ is
onto.

Thus, for each prime number p and each $m,n \in \mathbb{N}$,
$\theta_{m,n}$ holds in a field of characteristic $p$,  i.e.
$\langle \tilde{F}_{p} , \pmb{+} , \pmb{\cdot} , \pmb{0} , \pmb{1}
\rangle$ satisfies
$\mathcal H$.



\end{proof}


It is a significant  problem to replace ``one-to-one'' with ``locally
one-to-one''.


\chapter{Diagrams and Embeddings}



Let $\ma = \langle \ba ,\mathcal I \rangle $ be a model for a
language $\lan$.  Expand $\lan$ to the language 
$\lan_\ba = \lan \cup \{ c_a : a \in \ba \}$ by adding new constant symbols to $\lan$. We can expand $\ma$ to a model 
$\ma_\ba = \langle \ba , \mathcal{I}' \rangle$ for $\lan_\ba$ by
choosing $\mathcal{I}'$ extending $\mathcal{I}$ such that
$\mathcal{I}'(c_a)=a$ for each $a \in \ba$. 


More generally, if $f \colon X \rightarrow \ba$, we can expand $\lan$ to 
$\lan_{X} = \lan \cup \{ c_x : x \in X \}$ and expand 
$\ma = \langle \ba ,\mathcal{I} \rangle $ to $\langle \ba ,\mathcal{I}' \rangle$ 
where $\mathcal{I}'$ extends $\mathcal{I}$ with each $\mathcal{I}' (c_x) = f(x)$. We denote the resulting model as $\langle \ma , f(x)\rangle _{x \in X}$ or 
$\ma_X = \langle \ma , x \rangle _{x \in X}$ if $f$ is the identity function.

\begin{definition}\label{D:diagram}
\index{$\mbox{Th}\mathfrak{A}_{\mathbf{A}}$}% 
\index{elementary diagram}%
Let $\ma$ be a model
for $\lan$. 
\begin{enumerate}
\item The \emph{elementary
diagram} of $\ma$ is $\Th(\ma_\ba)$, the set of all sentences of
$\lan_\ba$ which hold in $\ma_\ba$.  

\item The \emph{diagram} of $\ma$, denoted by $\tria{A}$, is the set of
all those sentences in $\Th(\ma_\ba)$ without quantifiers.
\end{enumerate}
\end{definition}


\begin{rem}  There is a notion of \emph{atomic formula}, which is a
formula of the form $(t_1 = t_2)$ or $(R(t_1 \dots t_n))$ where $t_1 ,
\dots , t_n$ are terms.  Sometimes $\tria A$ is defined to be the set
of all atomic formulas and negations of atomic formulas which occur in
$\Th (\ma_\ba)$.  However this is not substantially different from
Definition~\ref{D:diagram}, since the reader can quickly show that for
any model $\mb$, $\mb \models \tria A$ in one sense iff $\mb \models
\tria A$ in the other sense.

\end{rem}

\begin{exercise}\label{X:expand} 
Let $\ma $ and $\mb$ be models for $\lan$ with $X \seq \ba \seq \bb$.  Prove:
\begin{itemize}
\item[(i)]   $\ma \seq \mb$ iff $\ma_X \seq \mb_X$ iff $\mb_\ba \models \tria A$.
\item[(ii)]  $\ma \prec \mb$ iff $\ma_X \prec \mb_X$ iff 
$ \mb_\ba \models \Th (\ma_\ba)$.
\end{itemize}

Hint: $\ma \models \varphi [ a_1 , \dots, a_p ] \mbox{ iff } \ma_\ba
\models \varphi^*$ where $\varphi^*$ is the sentence of $\lan_\ba$
formed
by replacing each free occurrence of $v_i$ with $c_{a_i}$.

 \end{exercise}




\begin{definition}\label{D:iso}
\index{isomorphically embedded model}%
 $\mathfrak{A}$ is said to be
\emph{isomorphically embedded} into $\mathfrak{B}$ whenever 
\begin{enumerate} 
\item there is a model $\mathfrak{C}$ such that 
$\mathfrak{A} \cong \mathfrak{C}$ and 
$\mathfrak{C} \subseteq \mathfrak{B}$

\begin{flushleft} or
\end{flushleft}

\item there is a model $\mathfrak{D}$ such that 
$\mathfrak{A} \subseteq \mathfrak{D}$ and 
$\mathfrak{D} \cong \mathfrak{B}$.

\end{enumerate}
\end{definition}

\begin{exercise}\label{X:eeek} 
Prove that, in fact, (1) and (2) are equivalent conditions.
\end{exercise}

\begin{definition}
\index{elementarily embedded model}%
 $\ma$ is said to be \emph{elementarily embedded} into $\mb$ whenever 
\begin{enumerate}
\item there is a model $\mc$  such that $\ma \cong \mc $ and $\mc \prec \mb $

\begin{flushleft} or
\end{flushleft}

\item there is a model $\md$ such that $\ma \prec \md $ and $\md \cong \mb $.

\end{enumerate}

\end{definition}

\begin{exercise} Again, prove that, in fact, (1) and (2) are equivalent.
\end{exercise}

\addcontentsline{toc}{section}{Diagram Lemmas}


The next result is extremely useful; the first part is called the Diagram Lemma and the second part is called the Elementary Diagram Lemma.

\begin{theorem}
\index{diagram lemmas}%
Let $\ma$ and $\mb$ be models for $\lan$.
\begin{enumerate}
\item $\ma$ is isomorphically embedded into $\mb$ if and only if $\mb$ can be
expanded to a model of $\tria A$.
\item $\ma$ is elementarily embedded into $\mb$ if and only if $\mb$ can be expanded to
a model of $\mbox{Th}(\ma_\ba)$.
\end{enumerate}

\end{theorem}

\begin{proof}  We sketch the proof of (1).

($\Rightarrow$) If $f$ is the isomorphism as in 1 of Definition \ref{D:iso} above, then 
\[
        \langle \mb , f(a) \rangle_{a \in \ba} \models \tria A. 
\]

($\Leftarrow$) If $\langle \mb , b_a \rangle_{a \in \ba } \models \tria A$, then $\mathbf{C} = \{ b_a : a \in \mathbf{A} \}$ generates $\mc \subseteq \mb$ with 
$\mc \cong \ma$.

\end{proof}

\begin{exercise}
Give a complete proof of (2).
\end{exercise}

\begin{exercise} \label{X:diagram} 
Show that if $\ma$ is a model for the language $\lan$ and $\mc$ is a model for the language $\lan _{\mathbf{A}}$ such that $\mc \models \tria A $ then there is a model $\mb$ such that $\ma \subseteq \mb$ and $\mb _{\mathbf{A}} \cong \mc$.
\end{exercise}

\index{Downward L\"{o}wenheim-Skolem Theorem}%
\index{Upward L\"{o}wenheim-Skolem Theorem}%
\begin{exercise} The  L\"{o}wenheim-Skolem Theorem is sometimes called the Downward
L\"{o}wenheim-Skolem Theorem. It's partner is the Upward L\"{o}wenheim-Skolem Theorem: if $\mathfrak{A}$ is an infinite model for $\mathcal{L}$ and $\kappa$
is any cardinal such that $ |\mathcal{L} |\leq \kappa $ and 
$|\mathbf{A} | < \kappa $, then $\ma$ has an elementary extension of cardinality $\kappa$. Prove it.
\end{exercise}



We now apply these notions to graph theory and to calculus.  The natural
language for graph theory has one binary relation symbol which we call $E$
(to suggest the word ``edge''). Graph Theory has the following two axioms:
\begin{itemize}
\item $(\forall x ) (\forall y) E (x,y) \leftrightarrow E(y,x)$
\item $(\forall x) \neg E(x,x)$.
\end{itemize}

A graph is, of course, a model of graph theory.

\addcontentsline{toc}{section}{ Every planar graph can be four
coloured}


\begin{corollary} Every planar graph can be four coloured.
\end{corollary}

\begin{proof} We will have to use the famous result of Appel and Haken
that every \emph{finite} planar graph can be four coloured. Model
Theory will take us from the finite to the infinite.  We recall
that a planar graph is one that can be embedded, or drawn, in the usual
Euclidean plane and to be four coloured means that each vertex of the
graph
can be assigned one of four colours in such a way that no edge has the
same colour for both endpoints.

Let $\ma$ be an infinite planar graph.  Introduce four new unary relation
symbols: $R, G , B,Y$ (for red, green, blue and yellow). We wish to
prove
that there is some expansion $\ma'$ of $\ma$ such that $\ma' \models
\sigma$ where $\sigma$ is the sentence in the expanded language:
\begin{multline*} 
 (\forall x) [R(x) \vee G(x) \vee B(x) \vee Y(x) ] \\
\wedge (\forall x) [R(x) \to \neg (G(x) \vee B(x) \vee Y(x))] \wedge
\dots \\
\wedge (\forall x)
(\forall y) \neg (R(x) 
\wedge R(y) \wedge E(x,y)) \wedge \cdots 
\end{multline*} 
which will ensure that the interpretations of $R,G,B$ and $Y$ will four
colour the graph.

Let $\Sigma = \tria A \cup \{ \sigma \}$.  Any finite subset of $\Sigma$
has a model, based upon the appropriate finite subset of $\ma$.  By the
compactness theorem, we get $\mb \models \Sigma$.  Since $\mb \models
\sigma$, the interpretations of $R,G,B $ and $Y$ four colour it.  By the
diagram lemma $\ma$ is isomorphically embedded in the reduct of $\mb$, and
this isomorphism delivers the four-colouring of $\ma$.

\end{proof}

A graph with the property that every pair of vertices is connected with
an edge is called \emph{complete}.  At the other extreme, a graph with
no edges is called \emph{discrete}.  A very important theorem in finite
combinatorics says that most graphs contain an example of one or the
other as a subgraph.  A subgraph of a graph is, of course, a submodel
of a model of graph theory.

\begin{corollary} (Ramsey's Theorem)\\
 For each $n \in \nat$ there is an
$r \in \nat$ such
that if $\mg$ is any graph with $r$ vertices, then either $\mg$
contains a
complete subgraph with $n$ vertices or a discrete subgraph with $n$
vertices.

\end{corollary}

\addcontentsline{toc}{section}{Ramsey's Theorem}

\begin{proof}  We follow F.~Ramsey who began by proving an infinite
version of the theorem (also called Ramsey's Theorem).

\begin{claim}  Each infinite graph $\mg$  contains either an infinite
complete
subgraph or an infinite discrete subgraph.

\end{claim}

\begin{proof}[Proof of Claim]  By force of logical necessity, there are
two possiblities: 
\begin{itemize}
\item[(1)] there is an infinite $X \seq \bg$ such that for all $x \in
X$
there
is a finite $F_x \seq X$ such that $E(x, y)$ for all $y \in X \setminus
F_x$,
\item[(2)] for all infinite $X \seq \bg$ there is a $x \in X$ and an
infinite
$Y \seq X$ such that $\neg E ( x, y )$ for all $y \in Y$.
\end{itemize}

If (1) occurs, we recursively pick $x_1 \in X$, $x_2 \in X \setminus
F_{x_1}$, $x_3 \in X \setminus ( F_{x_1} \cup F_{x_2})$, etc, to obtain
an infinite complete subgraph.  If (2) occurs we pick $x_0 \in \bg$ and
$Y_0 \seq \bg$ with the property and then recursively choose $x_1 \in
Y_0$ and $Y_1 \seq Y_0$ , $x_2 \in Y_1$ and $Y_2 \seq Y_1$ and so on,
to obtain an infinite discrete subgraph.

\renewcommand{\qedsymbol}{}
\end{proof}

We now use Model Theory to go from the infinite to the finite.  Let
$\sigma$ be the sentence,  of the language of graph theory, asserting
that there is no complete subgraph of size $n$.
\[ (\frx[1]{n})[\neg E(x_1, x_2) \vee \neg E(x_1 , x_3 ) \vee \dots
\vee \neg E(x_{n-1}, x_n) ] . \]
Let $\tau$ be the sentence asserting that there is no discrete subgraph
of size $n$. \[ (\frx[1]{n})[ E(x_1, x_2) \vee  E(x_1 , x_3 )
\vee \dots \vee E(x_{n-1}, x_n) ] . \]
Let $\tee$ be the set consisting of $\sigma$, $\tau$ and the axioms of
graph theory.  


If there is no $r$ as Ramsey's Theorem states, then $\tee$ has
arbitrarily large finite models.  By Theorem \ref{T:compact}, $\tee$
has an infinite model, contradicting the claim.

\end{proof}

Ramsey's Theorem says that for each $n$ there is some $r$. The proof does not, however, let us know exactly which $r$ corresponds to any given $n$. There has been considerable efforts made to find a more constructive proof. In particular we would like to know, for each $n$, the smallest value of $r$ which would satisfy Ramsey's Theorem, called the Ramsey Number of $n$.

The Ramsey number of $3$ is $6$; the Ramsey number of $4$ is $18$; the Ramsey number of $5$ is \dots unknown; but it's somewhere between $40$ and $50$.  Even  less is known about the Ramsey numbers for higher values of $n$. Determining the Ramsey numbers may be the most mysterious problem in all of mathematics. 

\


\addcontentsline{toc}{section}{The Leibniz Principle and infinitesimals}

The following theorem of A. Robinson finally solved the centuries old
problem of infinitesimals in the foundations of calculus.
 
\begin{theorem}\label{T:Leibniz}  (The Leibniz Principle)\\
\index{Leibniz Principle}%
There is an ordered field $\rstar$ called the hyperreals, containing the
reals $\mathbb R$ and a number larger than any real number such that any statement
about the reals which holds in $\mathbb R$  also holds in $\rstar$.

\end{theorem}

\begin{proof} 
Let $\mr$ be $\langle \mathbb{R} ,\pmb{+}, \pmb{\cdot}, \pmb{<} , \pmb{0} , \pmb{1} \rangle $.
We will make the statement of the theorem precise by proving that there
is some model $\mh$, in the same language $\lan$ as $\mr$ and with the
universe called $\rstar$ , such that $\mr \prec \mh$ and
there is $b \in \rstar$ such that $a < b$ for each $a \in \mathbb R$.

For each real number $a$, we introduce a new constant symbol $c_a$. In addition, another new constant symbol $d$ is introduced. Let $\Sigma$ be the set of
sentences in the expanded language given by:
\[ 
\mbox{Th}\mr_{\mathbb{R}} \cup \{c_a < d : a \mbox{ is a real} \} 
\]
We can obtain a model $\mc \models \Sigma$ by the compactness theorem.
Let $\mc'$ be the reduct of $\mc$ to $\lan$.  By the elementary diagram
lemma $\mr$ is elementarily embedded in $\mc'$, and so there is a model
$\mh$ for $\lan$ such that $\mc' \cong \mh$ and $\mr \prec \mh$. Take $b$ to be the interpretation of $d$ in $\mh$.

\end{proof}


\begin{rem} The element $b \in \rstar$ gives rise to an infinitesimal $1/b \in \rstar$. An element $x \in \rstar $ is said to be \emph{infinitesimal} whenever $-1/n<x<1/n$ for each $n \in \mathbb{N}$. $0$ is infinitesimal. Two elements $x,y \in \mathbb{R}$ are 
said to be \emph{infinitely close}, written $x \approx y$ whenever $x-y$ 
is infinitesimal, so that $x$ is infinitesimal iff $x \approx 0$. 
An element $x \in \rstar$ is said to be \emph{finite} 
whenever $-r<x<r$ for some positive $r \in \mathbb{R}$. Else it is 
\emph{infinite}.

Each finite $x \in \rstar$ is infinitely close to some real 
number, called the \emph{standard part} of $x$, written $st(x)$.

This idea is extremely useful in understanding calculus. To differentiate $f$, for each $\vartriangle \negmedspace x \in \rstar$ generate 
$\vartriangle \negmedspace y = f(x \ + \vartriangle \negmedspace x) - f(x)$. 
Then $f'(x) = st  \left( \frac{\vartriangle y }{\vartriangle x} \right)$
whenever this exists and is the same for each infinitesimal 
$\vartriangle \negmedspace x \neq 0$.

This legitimises the intuition of the founders of the differential calculus and allows us to use that intuition to move from the (finitely) small to the 
infinitely small. Proofs of the usual theorems of calculus are now much easier.
More importantly, refinements of these ideas, now called non-standard analysis, 
form a powerful tool for applying calculus, just as its founders envisaged.	
\end{rem}

The following theorem is considered one of the most fundamental results
of mathematical logic.  We give a detailed proof.

\addcontentsline{toc}{section}{The Robinson Consistency Theorem}
\begin{theorem}\label{T:rob} (Robinson Consistency Theorem) \\
\index{Robinson Consistency Theorem}%
Let $\mathcal{L}_{1}$  and $\mathcal{L}_{2}$ be two languages with 
$\mathcal{L} = \mathcal{L}_{1} \cap \mathcal{L}_{2}$. Suppose 
$\mathcal{T}_{1}$ and $\mathcal{T}_{2}$
are satisfiable theories in $\mathcal{L}_{1}$ and $\mathcal{L}_{2}$ 
respectively. Then $\mathcal{T}_{1} \cup \mathcal{T}_{2}$ is satisfiable 
iff there is no sentence $\sigma$ of $\mathcal{L}$ such that 
$\mathcal{T}_{1} \models \sigma$ and $\mathcal{T}_{2} \models \neg \sigma$.

\end{theorem}

\begin{proof} The direction $\Rightarrow$ is easy and motivates the whole 
theorem. 

We begin the proof in the $\Leftarrow$ direction. Our goal is to show
that $\theory_1 \cup \theory_2$ is satisfiable.
The following claim is a first step.
\begin{claim}  $\theory_1 \cup \{ \mbox{ sentences } \sigma \mbox{ of }
\lan
: \theory_2 \models \sigma \} $ is satisfiable.
\end{claim}
\begin{proof}[Proof of Claim] Using the compactness theorem and
considering
conjunctions, it suffices to show that if $\theory_1 \models \sigma_1$ and
$\theory_2 \models \sigma_2$ with $\sigma_2$ a sentence of $\lan$, then
$\{ \sigma_1 , \sigma _2 \}$ is satisfiable.  But this is true, since
otherwise we would have $\sigma_1 \models \neg \sigma_2$ and hence
$\theory_1 \models \neg \sigma_2$ and
so $\neg \sigma_2$ would be a sentence of
$\lan$ contradicting our hypothesis. This proves the claim.
\renewcommand{\qedsymbol}{}
\end{proof}

The basic idea of the proof from now on is as follows.  In order to
construct a model of $\theory_1 \cup \theory_2$ we construct models $\ma
\models \theory_1$ and $\mb \models \theory_2$
and an isomorphism \\
$f: \ma |\lan \to \mb |\lan$ between the reducts of $\ma$ and 
$\mb$ to the language $\lan$, witnessing that $\ma
|\lan \cong \mb |\lan $. We then use
$f$ to carry over
interpretations of
symbols in $\lan_1 \setminus \lan$ from $\ma $ to $\mb$ , giving an
expansion
$ \mb^{\ast} $ of $\mb$ to the language
$\lan_1 \cup \lan_2$.  Then, since $\mb^{\ast} | {\lan_1} \cong \ma$
and
$\mb^{\ast} |{\lan_2} = \mb$ we get $\mb^{\ast} \models \theory_1
\cup \theory_2$.

\

The remainder of the proof will be devoted to constructing such an
$\ma$, $\mb$ and $f$. $\ma $ and $\mb$ will be constructed as unions of
elementary chains
of $\ma_n$'s  and $\mb_n$'s while $f$ will be the union of $f_n : \ma_n
\hookrightarrow \mb_n$.
We begin with $n=0$, the first link in the elementary chain.

\begin{claim}  There are models $\ma_0 \models \theory_1$ and $\mb_0
\models \theory_2$ with an elementary embedding $f_0 : \ma_0 |\lan
\hookrightarrow \mb_0 |\lan$. \end{claim}

\begin{proof}[Proof of Claim] Using the previous claim, let 
\[\ma_0 \models \theory_1 \cup \{ \mbox{ sentences } \sigma \mbox{ of }
\lan :\theory_2 \models \sigma \} \]

We first wish to show that $\Th (\ma_0 |\lan)_{\ba_0} \cup
\theory_2$ is satisfiable. Using the compactness
theorem, it suffices to prove that if $\sigma \in \Th (\ma_0 |\lan
)_{\ba_0}$ then $\theory_2 \cup \{ \sigma \} $ is satisfiable. For such
a $\sigma$ let $c_{a_0},\dots , c_{a_n}$ be all the constant symbols from
$\lan_{\ba_0} \setminus \lan$ which appear in $\sigma$.
Let $\varphi$
be the formula of $\lan$ obtained by replacing each constant symbol
$c_{a_i}$ by a new variable $u_i$.  We have \[\ma_0 |\lan \models \varphi [
\anot{n} ] \]
\[ \mbox{ and so } \ma_0 |\lan \models \exu{n} \varphi \]

By the definition of $\ma_0$, it cannot happen that $\theory_2 \models
\neg \exu{n} \varphi$ and so there is some
model $\md$ for $\lan_2$ such that $\md \models \theory_2$ and $\md
\models 
\exu{n} \varphi$. So there are elements $d_0, \dots ,d_n$ of $\bd$
such that $\md \models \varphi [ d_o , \dots , d_n ]$.  Expand $\md$ to a model
$\md^{\ast}$
for $\lan_2 \cup \lan_{\ba_0}$, making sure to interpret each $c_{a_i}$
as $d_i$. Then $\md^{\ast} \models \sigma$, and so $\md^{\ast} \models
\theory_2 \cup \{ \sigma \}$.

Let $\mb_{0}^{\ast} \models \Th (\ma_0 |\lan )_{\ba_0} \cup
\theory_2$. 
Let $\mb_0$ be the reduct of $\mb_{0}^{\ast}$ to $\lan_2$; clearly $\mb_0
\models \theory_2$.  Since $\mb_0 |\lan$ can be expanded to a model  of
$\Th (\ma_0 |\lan )_{\ba_0}$, the Elementary Diagram Lemma gives an
elementary embedding \[ f_0 : \ma_0 |\lan \hookrightarrow \mb_0
|\lan \] and
finishes the proof of the claim.

\renewcommand{\qedsymbol}{}
\end{proof}

The other links  in the elementary chain are  provided by the following
result.

\begin{claim} For each $n \geq 0$ there are models $\ma_{n+1} \models
\theory_1$ and $\mb_{n+1} \models \theory_2$ with an elementary
embedding 
\[ f_{n+1} : \ma_{n+1} | \lan \hookrightarrow \mb_{n+1} 
| {\lan} \]  such that 
\[ \ma_n \prec \ma_{n+1} , \, \mb_n \prec \mb_{n+1}, \, f_{n+1}
\mbox{ extends } f_n \mbox{ and } \bb_n \seq \mbox{ range of }
f_{n+1}.\]
\[
\begin{array}{ccccccccccc}
\ma_0 &\prec &\ma_1 &\prec &\cdots &\prec &\ma_n &\prec &\ma_{n+1}
&\prec &\cdots \\
\downarrow_{f_0} &{} &\downarrow_{f_1} &{} &{} &{} &\downarrow_{f_n}
&{} &\downarrow_{f_{n+1}} &{} &{} \\
\mb_0 &\prec &\mb_1 &\prec &\cdots &\prec &\mb_n &\prec &\mb_{n+1}
&\prec &\cdots 
\end{array}
\]

\end{claim}
 
\par
The proof of this claim will be discussed shortly. Assuming the
claim, let $\ma = \bigcup_{n \in \mathbb N} \ma_n$,
$\mb = \bigcup_{n \in \mathbb N} \mb_n$ and $f = \bigcup_{n \in \mathbb
N} f_n$.
The Elementary Chain Theorem gives that $\ma \models \theory_1$ and
$\mb
\models \theory_2$.  The proof of the theorem is concluded by simply
verifying that  $f: \ma | \lan \to \mb | \lan$ is an
isomorphism.

\

The proof of the claim is long and quite technical; it would not be
inappropriate to omit it on a first reading.  The proof, of course,
must proceed by induction on $n$.  The case of a general n is no
different from the case $n=0$ which we state and prove in some detail.

\begin{claim}  There are models $\ma_1 \models \theory_1 $ and $\mb_1
\models \theory_2 $ with an
elementary embedding $f_1 : \ma_1 |\lan \hookrightarrow \mb_1
|\lan $
such that $\ma_0 \prec \ma_1 $, $\mb_0 \prec \mb_1 $,$\; f_1 $ extends
$f_0$ 
and\\
$\bb_0 \seq \mbox{range of } f_1$.
\[ \begin{array}{ccc}
\ma_0  &\prec &\ma_1 \\
\downarrow_{f_0}  &{}  &\downarrow_{f_1} \\
\mb_0 &\prec &\mb_1
\end{array}
\]

\end{claim}

\begin{proof}[Proof of Claim] Let $\ma_0^+ $ be the expansion of $\ma_0 $
to
the
language $\lan_1^+ = \lan_1 \cup \{ c_a : a \in \ba_0 \} $ formed by
interpreting each $c_a  $ as $a \in \ba_0 $; $\ma_0^+ $ is just another
notation for $\left( \ma_0 \right)_{\ba_0} $.  The elementary diagram
of $\ma_0^+ $ is $\Th \left( \ma_0^+ \right)_{\ba_0^+} $. Let
$\mb_0^{\ast} $ be the
expansion of $\mb_0 |\lan $ to the language \[\lan^{\ast} = \lan \cup
\{ c_a : a \in \ba_0 \} \cup \{ c_b : b \in \bb_0 \} \] formed by
interpreting each $c_a $ as $f_0 (a) \in \bb_0 $
and each $c_b $ as $ b \in \bb_0$.

$  $\par
We wish to prove that $\Th \left( \ma_0^+ \right)_{\ba_0^+} \cup \Th
\mb_0^{\ast} $ is satisfiable. By the compactness theorem it
suffices to prove that $\Th \left( \ma_0^+ \right)_{\ba_0^+} \cup \{
\sigma \} $ is
satisfiable for each $\sigma $ in $\Th \mb_0^{\ast}$. For such a
sentence
$\sigma $, let $c_{a_0}, \dots , c_{a_m} , c_{b_0} , \dots , c_{b_n} $ be
all those constant symbols occuring in $\sigma $ but not
in $\lan $.
Let $\varphi ( u_0 , \dots , u_m , w_0 , \dots , w_m ) $ be the formula of
$\lan $ obtained from $\sigma $ by replacing each constant
symbol $c_{a_i} $ by a new variable $u_i $ and each constant symbol
$c_{b_i} $ by
a
new
variable $w_i $.  We have $\mb_0^{\ast} \models \sigma $ so 
\[\mb_0 |\lan \models \varphi [ f_0 (a_0) ,\dots , f_0 ( a_m ), b_0
,
\dots , b_n ] \]
\[\mbox{So }\mb_0 |\lan \models \exw{n} \varphi [ f_0 (a_0) , \dots ,
f_0 ( a_m ) ] \]
Since $f_0 $ is an elementary embedding we have :
\[ \ma_0 |\lan \models \exw{n} \varphi [ \anot m ] \]

\newcommand{\crap}{\ensuremath{\left( \ma_{0}^{+} \right)_{\ba_{0}^{+}}
}}

Let $\hphi ( \wnot{n})$ be the formula of $\lan_{1}^{+}$ obtained by
replacing occurrences of $u_i$ in $\varphi ( \unot m , \wnot n ) $ by
$c_{a_i}$; then $\ma_{0}^{+} \models \exw{n} \hphi$. So, of course, \[
\left( \ma_{0}^{+} \right)_{\ba_{0}^{+}} \models \exw{n} \hphi \]  and 
this means that there are $\dnot n$ in $\ba_0^+ = \ba_0$ such that 
\[ (\ma_0^+ )_{\ba_0^+} \models \hphi [ \dnot n ] .\] We
can now expand $\crap$ to a model $\md$ by interpreting each
$c_{b_i}$ as $d_i$ to obtain $\md \models \sigma$ and so $\Th \crap \cup
\{ \sigma \} $ is satisfiable.


Let $\me \models \Th \crap \cup \Th \mb_{0}^{\ast}$.  By the elementary
diagram lemma $\ma_0^+$ is elementarily embedded into $\me
|{\lan_{1}^{+}}$.  So there is a model $\ma_1^+$ for $\lan_1^+$
with
$\ma_0^+ \prec \ma_1^+$ and an isomorphism $g: \ma_1^+ \to \me
| {\lan_1^+}$.  Using $g$ we expand $\ma_1^+$ to a model $\ma_1'$
isomorphic to $\me$.  Let $\ma_1^{\ast}$ denote $\ma_1'
| {\lan^{\ast}}$; we have $\ma_1^{\ast} \models \Th \mb_0^{\ast}$.

\newcommand{\sucks}{\ensuremath{\left( \ma_1^{\ast}
\right)_{\ba_1^{\ast}}}}
\newcommand{\bobo}{\ensuremath{ \left( \mb_0^+ \right)_{\bb^+_0 }  }}
\newcommand{\bo}{\ensuremath{ \mb_0}}
\newcommand{\bostar}{\ensuremath{ \mb_0^{\ast}}}
\newcommand{\bop}{\ensuremath{ \mb_0^+}}

$  $\par

We now wish to prove that $\Th \sucks \cup \Th \bobo $ is satisfiable,
where $\bop$ is the common expansion of $\bo$ and $\bostar$ to the
language \[\lan_2^+ = \lan_2 \cup \{ c_a : a \in \ba_0 \} \cup \{ c_b : b
\in \bo \} . \]
By the compactness theorem, it suffices to show that \[ \Th \bobo \cup \{
\sigma \} \] is satisfiable for each $\sigma$ in $\Th \sucks$.  Let
$c_{x_0} , \dots , c_{x_n}$ be all those constant symbols which occur in
$\sigma$ but are not in $\lan^{\ast}$.  Let $\psi ( \unot{n})$ be the
formula of $\lan^{\ast}$ obtained from $\sigma$ by replacing each
$c_{x_i}$ with a new variable $u_i$.  Since $\sucks \models \sigma$ we
have \[\ma_1^{\ast} \models \psi [ \xnot n ] \mbox{,} \]  and so
\[\ma_1^{\ast} \models
\exu n \psi .\]
 Also $\ma_1^{\ast} \models \Th \bostar$ and $\Th
\bostar$
is a complete theory in the language $\lan^{\ast}$; hence $\exu n \psi$ is
in $\Th \bostar$.  Thus \[ \bostar \models \exu n \psi\] and so \[\bobo
\models \exu n \psi\] and therefore there are $\bnot n$ in $\bb_0^+ =
\bb_0$ such that \[\bobo \models \psi [ \bnot n ].\]  
We can now expand $\bobo$ to a model $\mf$ by interpreting each $c_{x_i}$
as $b_i$; then $\mf \models \sigma$ and $\Th \bobo \cup \{ \sigma \}$ is
satisfiable.

Let $\mg \models \Th \sucks \cup \Th \bobo$.  By the elementary diagram
lemma $\bop$ is elementarily embedded into $\mg | {\lan_2^+}$.  So
there is a model $\mb_1^+$ for $\lan_2^+$ with $\bop \prec \mb_1^+$ and an
isomorphism $h: \mb_1^+ \to \mg | {\lan_2^+}$.  Using $h$ we expand
$\mb_1^+$ to a model $\mb_1'$ isomorphic to $\mg$. Let $\mb_1^{\ast}$
denote $\mb_1' | {\lan^{\ast}}$. Again by the elementary diagram lemma
$\ma_1^{\ast}$ is elementarily
embedded into $\mb_1^{\ast}$.  Let this be denoted by \[f_1 : \ma_1^{\ast}
\hookrightarrow \mb_1^{\ast} . \]

\newcommand{\veqc}{\ensuremath{ \models (v_0 = c_a  )[f_0(a)] }}
\newcommand{\ceqv}{\ensuremath{ \models c_a = v_1 [ a ] }}
\newcommand{\veqcb}{\ensuremath{ \models v_0 = c_b [ b ] }}

Let $a \in \ba_0$; we will show that $f_0 (a) = f_1 (a)$.  By
definition we have \\
$ \bostar \models  ( v_0 = c_a ) [ f_0 (a ) ]$
and so $\bop \models (v_0 = c_a ) [f_0 (a) ] . $
Since $ \bop \prec \mb_1^+$, \\
 $ \mb_1^+  \models ( v_0 = c_a ) [ f_0 (a )]$ and so $ \mb_1^{\ast}
\models  (v_0 = c_a ) [ f_0 (a )] .$ Now  $ \ma_0^+ \models (c_a =
v_1)[a]$ and $ \ma_0^+ \prec \ma_1^+ $ so $\ma_1^+ \models (c_a = v_1 )
[a] $
so $ \ma_1^{\ast} \models  (c_a = v_1 ) [a]. $ Since $ f_1 $ is
elementary, 
$\mb_1^{\ast} \models (c_a = v_1) [ f_1 (a) ] $
so $\mb_1^{\ast} \models (v_0 = v_1) [ f_0 (a ), f_1 (a ) ] $
and so $ f_0 (a) = f_1 (a) $. 

Thus  $f_1 $ extends $f_0$.


Let $b \in \bb_0$; we will prove that $b = f_1 (a)$ for some $a \in
\ba_1$.  By definition we have: $ \bostar \models  (v_0 = c_b )[b]$
so $ \bop  \models (v_0 = c_b ) [b] $.
Since $ \bop \prec \mb_1^+, \mb_1^+ \models (v_0 = c_b ) [b]  $
so  $\mb_1^{\ast} \models (v_0 = c_b ) [b]$.
On the other hand, since $(\exists v_1)(v_1 = c_b)$ is always
satisfied,
we have:
$ \ma_1^{\ast} \models (\exists v_1) (v_1 = c_b) $
so there is $a \in \ba_1$ such that $ \ma_1^{\ast} \models (v_1
= c_b)[a]. $
Since $ f_1 $ is elementary, $ \mb_1^{\ast} \models ( v_1
= c_b) [f_1 (a) ] $
so $ \mb_1^{\ast} \models (v_0 = v_1 )[ b, f_1 (a) ] $
so $ b=f_1(a)$.

Thus  $  \mb_0 \seq \mbox{ range of } f_1$.

We now let $\ma_1$ be $\ma_1^+ | \lan_1 $ and
let $\mb_1$ be $\mb_1^+ |\lan_2$.  We get
$\ma_0 \prec \ma_1$ and $\mb_0 \prec \mb_1$ and $f_1 : \ma_1 | \lan
\to \mb_1 | \lan$ remains an elementary embedding.

This completes the proof of the claim and the theorem.
\renewcommand{\qedsymbol}{}
\end{proof}

\end{proof}


\begin{exercise}\label{E:rcthm}  
The Robinson Consistency Theorem was originally stated as: 
\begin{quotation} Let $\tee_1$ and $\tee_2$ be satisfiable theories in
languages $\lan_1$ and $\lan_2$ respectively and let $\tee \seq \tee_1
\cap \tee_2$ be a complete theory in the language $\lan_1 \cap \lan_2$.
Then $\tee_1 \cup \tee_2$ is satisfiable in the language $\lan_1 \cup
\lan_2$.
\end{quotation}

Show that this is essentially equivalent to our version in
Theorem~\ref{T:rob} by first proving that this statement follows from
Theorem~\ref{T:rob} and then also proving that this statement implies
Theorem~\ref{T:rob}.  Of course, for this latter argument you are
looking for a proof much shorter than our proof of Theorem~\ref{T:rob};
however it will help to use the first claim of our proof in your own
proof.

\end{exercise}


\addcontentsline{toc}{section}{The Craig Interpolation Theorem}
\begin{theorem} (Craig Interpolation Theorem)\label{T:cit}\\
\index{Craig Interpolation Theorem}%
%end of page 16.  page 17 begins
Let $\varphi $ and $\psi $ be sentences such that $\varphi \models \psi 
$.
Then there exists a sentence $\theta $, called the interpolant, such
that $\varphi \models \theta  $ and $\theta \models \psi$ and every
relation, function or constant symbol occuring in $\theta$ also occurs
in both $\varphi$ and $\psi$. 

\end{theorem}

\begin{exercise} Show that the Craig Interpolation Theorem follows quickly
from the Robinson Consistency Theorem. Also, use the Compactness
Theorem
to show that
Theorem~\ref{T:rob} follows quickly from Theorem~\ref{T:cit}.
\end{exercise}

\chapter{Model Completeness}


The quantifier $\forall$ is said to be the \emph{universal
quantifier} and the quantifier $\exists$ to be the \emph{existential
quantifier}.



A formula $\varphi $ is said to be \emph{ quantifier free } whenever no 
quantifiers occur in $\varphi $.

A formula $\varphi$ is said to be \emph{universal} whenever it is of
the form $\forall x_{0} \dots \forall x_{k} \theta$ where
$\theta$ is
quantifier free.

A formula $\varphi$ is said to be \emph{existential} whenever it is of
the form $\exists x_0 \dots \exists x_k \theta$ where $\theta$ is
quantifier free.  



A formula  $\varphi $ is said to be \emph{ universal-existensial}
whenever it is 
of the form $\forall x_{0} \dots \forall x_{k} \exists y_{0} \dots
\exists y_{k} \theta $ where $\theta $ is quantifier free.

We extend these notions to theories $\mathcal{T} $ whenever each axiom
$\sigma$ of $\mathcal{T} $ has the property.

\begin{rem} Note that each quantifier free formula $\varphi$ is 
trivially
equialent to the existential formula $\exists v_i \varphi$ where $v_i$
does not occur in $\varphi$.
\end{rem}

\begin{exercise}\label{X:verify}
 
Let $\ma$ and $\mb$ be models for $\lan$ with $\asb$. Verify the
following three statements:
\begin{itemize}
\item[(i)] $\ma \prec \mb \mbox{ iff }\mb_\ba \models \Th (\ma_\ba)
\mbox{ iff } \ma_\ba \models \Th (\mb_\ba).$

\item[(ii)] $\masb$ iff $\mb_\ba \models \sigma$ for each existential
$\sigma$ of $\Th (\ma_\ba).$

\item[(iii)] $\masb$ iff $\ma_\ba \models \sigma$ for each universal
$\sigma$ of $\Th ( \mb_\ba).$

\end{itemize}

\end{exercise}


\begin{definition}
\index{existentially closed}%
 A model $\mathfrak{A}$ of a theory
$\mathcal{T}$ is 
said to be \emph{existentially closed} if  whenever $\mathfrak{A}
\subseteq \mathfrak{B}$ and $\mb \models \mathcal{T}$, we have  
$\mathfrak{A}_{\mathbf{A}} \models \sigma$ for each existential
sentence $\sigma$ of $\Th (\mb_\ba).$
\end{definition}

\begin{rem} If $\ma$ is existentially closed and $\ma' \cong \ma$ then  
$\ma'$ is also  existentially  closed.
\end{rem} 

\begin{definition}
\index{model complete theory}%
 A theory $\mathcal{T} $ is said to be
\emph{ model complete } 
whenever $\theory \cup \tria A$ is complete in the language $\lan_\ba$
for each model $\ma$ of $\theory$.
\end{definition}

\addcontentsline{toc}{section}{Robinson's Theorem on existentially
complete theories}
\begin{theorem}\label{T:robinson} ( A. Robinson )\\
\index{A.~Robinson}%
Let $\mathcal{T} $ be a theory in the language $\mathcal{L} $. The
following are equivalent:
\begin{itemize}
\item[(1)] $\mathcal{T} $ is model complete,
\item[(2)] $\mathcal{T} $ is existentially complete, i.e. each 
model of $\mathcal{T} $ is existentially closed.
\item[(3)] for each formula $\varphi ( v_{0} , \dots , v_{p}) $ of
$\mathcal{L} $ 
there is some universal formula \\ $\psi (v_{0} , \dots , v_{p}) $ such that 
$\mathcal{T} \models ( \forall v_{0} \dots \forall v_{p} ) ( \varphi 
\leftrightarrow \psi ) $ 
\item[(4)] for all models $\ma$ and $\mb$ of $\theory$, $\ma \seq \mb$
implies $\ma \prec \mb$.
\end{itemize}
\end{theorem}

\begin{rem} Equivalently, in part (3) of this theorem the phrase ``universal formula" could be replaced by ``existential formula". We chose the version which makes the proof smoother.
\end{rem} 


\begin{proof}

(1) $\Rightarrow$ (2): \\
Let $\ma \models \theory$ and $\mb \models \theory$ with $\ma \seq
\mb$.  Clearly $\ma_\ba \models \tria A$ and by Exercise \ref{X:expand} we 
$\mb_\ba \models \tria A$.  Now by (1), $\theory \cup \tria A$ is
complete and both $\ma_\ba $ and $\mb_\ba$ are models of this theory so
they are elementarily equivalent.
For any sentence $\sigma$ of $\lan_\ba$ (existential or
otherwise), if $\mb_\ba \models \sigma$ then $\ma_\ba \models \sigma$
and (2) follows.

(2) $\Rightarrow$ (3): \\
Lemma \ref{L:prenex}  shows that it suffices to prove it for formulas
 $\varphi$ in
prenex normal form.  We do this by induction on the prenex rank of
$\varphi$ which is the number of alternations of quantifiers in
$\varphi$.  The first step is prenex rank $0$.  Where only universal
quantifiers are present the result is trivial.  
The existential formula case is non-trivial; it is the following claim:

\begin{claim}  For each existential formula $\varphi ( \vnot p )$ of
$\lan$ there is a universal formula $\psi (\vnot p )$ such that \[
\theory \models ( \forall v_{0}) \dots ( \forall
v_{p} ) ( \varphi
\leftrightarrow \psi ) \]

\end{claim}

\begin{proof}[Proof of Claim]  Add new constant symbols $\cnot p $ to
$\lan$ to form \[ \lan^{\ast} = \lan \cup \{ \cnot p \} \] and to form
a
sentence $\varphi^{\ast}$ of $\lan^{\ast}$ obtained by replacing each
free occurrence of
$v_i$ in $\varphi$ with the corresponding $c_i$; $\varphi^{\ast}$ is an
existential sentence.  It suffices to prove that there is a universal
sentence $\gamma$ of $\lan^{\ast}$ such that $\theory \models \varphi^{\ast}
\leftrightarrow \gamma$.

\[ \mbox{Let } \Gamma = \{ \mbox{universal sentences } \gamma \mbox{ of
} \lan^{\ast} \mbox{ such that } \theory \models \varphi^{\ast} \to \gamma \}
\]
We hope to prove that there is some $\gamma \in \Gamma $ such that
$\theory \models \gamma \to \varphi^{\ast}$.  Note, however, that any
finite
conjunction $\gamma_1 \wedge \gamma_2 \wedge \cdots \wedge \gamma_n $
of sentences from $\Gamma$ is equivalent to a sentence $\gamma$ in
$\Gamma$ which is simply obtained from $\gamma_1 \wedge \gamma_2 \wedge
\cdots \wedge \gamma_n $ by moving all the quantifiers to the front.
Thus it suffices to prove that there are finitely many sentences
$\gamma_1 , \gamma_2,  \dots , \gamma_n $ from $\Gamma$ such that 
\[ \theory \models \gamma_1 \wedge \gamma_2 \wedge \cdots \wedge
\gamma_n \to \varphi^{\ast}.\]  If no such finite set of sentences
existed,
then each \[ \theory \cup \{ \gamma_1 , \gamma_2 , \dots ,\gamma_n \}
\cup \{ \neg \varphi^{\ast} \} \] would be satisfiable. By the compactness
theorem, $\theory \cup \Gamma \cup \{ \neg \varphi^{\ast} \}$ would be
satisfiable.  Therefore it just suffices to prove that $\theory \cup
\Gamma \models \varphi^{\ast}$.

$  $ \par

In order to prove that $\theory \cup \Gamma \models \varphi^{\ast}$, let
$\ma$
be any model of $\theory \cup \Gamma$ for the language $\lan^{\ast}$. Let 
\[
\Sigma = \theory \cup \{ \varphi^{\ast} \} \cup \triangle _{\ma}.
\]  
be a set of sentences for the language $\lan ^{\ast}_{\ba}$; we wish to show that
$\Sigma$ is satisfiable.  

By the compactness theorem it suffices to consider
$\theory \cup \{ \varphi^{\ast} , \tau \}$ where $\tau$ is a conjunction of
finitely many sentences of, and hence in fact a single sentence of, 
$\triangle _{\ma}$.  
Let $\theta$ be the formula obtained from $\tau$ by exchanging each constant symbol from $\lan ^{\ast} _\ba \setminus \lan ^{\ast} $ occurring in $\tau$ for a new variable $u_a$. So 
\[ 
\ma \models \exu[a_0]{a_m} \theta ( \unot[a_0]{a_m} ). 
\]
But then $\ma$ is not a model of the universal sentence
$\fru[a_0]{a_m} \neg \theta ( \unot[a_0]{a_m})$. Recalling that $\ma
\models \Gamma$, we are forced to conclude that this universal sentence
is not in
$\Gamma$ and so not a consequence of $\theory \cup \{ \varphi^{\ast} \}$.
Therefore 
\[ 
\theory \cup \{ \varphi^{\ast} \} \cup \{ \exu[a_0]{a_m} \theta (
\unot[a_0]{a_m} ) \} 
\] 
must be satisfiable, and any model of this can
be expanded to a model of $\theory \cup \{ \varphi^{\ast} , \tau \}$ and so 
$\Sigma$ is satisfiable.

Let $\mc \models \Sigma$.  By the Exercise \ref{X:diagram}, there is a model $\mb$ for $\lan ^{\ast}$ such that $\ma \seq \mb$ and $\mb_\ba \cong \mc$ ; in particular: $\mb_\ba \models \Sigma$.

Since $\ma \seq \mb$ the interpretation of each of $c_{0},\dots,c_{p}$ in $\mb$ is the same as the interpretation in $\ma$; let's denote these by $a_{0},\dots,a_{p}$. Let $\sigma$ denote this sentence:
\[
   ( \exv[0]{p} )(\varphi \wedge v_{0} = c_{a_{0}} \wedge v_{1} = c_{a_{1}}
\wedge \dots \wedge v_{p} = c_{a_{p}})
\] 
which is equivalent to an existential sentence of $\lan_{\ba}$. 
Since $(\mb|\lan)_{\ba} \models \sigma$ we can apply (2) to $\ma |\lan$ and $\mb |\lan$ to get that $(\ma |\lan)_{\ba} \models \sigma$. 
By our choice of $a_{0},\dots,a_{p}$ we get that $\ma \models \varphi ^{\ast}$.

This means $\theory \cup \Gamma \models \varphi^{\ast}$ and finishes the proof of
the claim.

\renewcommand{\qedsymbol}{}
\end{proof}

We will now do the general cases for the proof of the induction on
prenex rank.  There are two cases, corresponding to the two methods
available for increasing the number of alternations of quantifiers:
\begin{itemize}
\item[(a)] the addition of universal quantifiers
\item[(b)] the addition of existential quantifiers.
\end{itemize}

For the case (a), suppose $\varphi ( \vnot p )$ is $\frw m \chi
(\vnot{p} , \wnot m )$ and $\chi$ has prenex rank lower than $\varphi$
so that we have by the inductive hypothesis that there is a quantifier
free formula $\theta ( \vnot p , \wnot m , \xnot n )$ with new
variables $\xnot n $ such that \[\theory \models ( \frv p \frw m )
(\chi \leftrightarrow \frx n \theta )\]
Therefore, case (a) is concluded by noticing that this gives us 
 \[\theory \models ( \frv p )(\frw m \chi \leftrightarrow \frw m  \frx
n
\theta ).\]


\begin{exercise}  Check this step using the definition of satisfaction.
\end{exercise}

For case (b), suppose $\varphi ( \vnot p )$ is $\exists w_0 \dots
\exists
w_n \chi ( \vnot p , \wnot m )$ and $\chi$ has prenex rank less than
$\varphi$.  Here we will use the inductive hypothesis on $\neg \chi$
which of course also has prenex rank less than $\varphi$.  We obtain a
quantifier free formula $\theta ( \vnot p , \wnot m , \xnot n )$ with
new variables $\xnot n$ such that 
\[ \theory \models (\frv p \frw m ) ( \neg \chi \leftrightarrow \frx n
\theta ) \]
\[\mbox{So } \theory \models (\frv p )(\frw m  \neg \chi
\leftrightarrow \frw m \frx n
\theta ) \]
\[\mbox{And } \theory \models (\frv p ) ( \exists w_0 \dots \exists 
w_m \chi \leftrightarrow \exists w_0 \dots \exists w_m \exists x_0
\dots \exists x_n \neg \theta ) \]
Now $\exists w_0 \dots \exists w_m \exists x_0 \dots \exists x_n \neg
\theta $ is an existential formula, so by the claim there is a
universal formula $\psi$ such that 
\[\theory \models (\frv p ) ( \exists w_0 \dots \exists w_m \exists x_0
\dots \exists x_n \neg \theta \leftrightarrow \psi ). \]
\[\mbox{Hence } \theory \models (\frv p ) ( \exists w_0 \dots \exists
w_n \chi \leftrightarrow \psi ) \]
which is the final result that we needed.


(3) $\Rightarrow$ (4)\\
 Let $\mathfrak{A} \models \mathcal T$ and
$\mathfrak B \models \mathcal T $ with $\mathfrak A \subseteq \mathfrak B$. 
Let $\varphi$ be a formula of $\mathcal L$ and let $a_0 , \dots , a_p $ be in
$\mathbf A$ such that $ \bmodphi [\anot{p}] $.
Obtain a universal formula $\psi$ such that
 \[ \theory \models (\allforu{v}{p})(\varphi \leftrightarrow \psi) . \]
Hence $\bmodpsi [ \anot{p} ] $. Since $\ma  \subseteq \mb $ by an argument similar to  Exercise \ref{X:verify} we have 
$ \amodpsi    [\anot{p} ] $. So $\amodphi  [ \anot{p} ] $. Therefore  $\ma  \prec \mb $.

 (4) $\Rightarrow$ (1) \\
Let $\ma \models \theory$. We will show that $\theory \cup \tria A$ is
complete by showing that 
\[
        \theory \cup \tria A \models \Th (\ma_\ba).
\]
Let $\mc \models \theory \cup \tria A$. By Exercise \ref{X:diagram} there is a model $\mb$ such that $\ma \subseteq \mb$ and $\mb_\ba \cong \mc$. By (4) we have that $\ma \prec \mb$. 
By Exercise \ref{X:expand} we get that $\mb_\ba \models \Th (\ma_\ba)$. Thus 
$\mc \models \Th (\ma_\ba)$.
\end{proof}

\begin{examples} We will see later that the theory ACF is model complete. 
But ACF is not complete because the characteristic of the algebraically
closed field can vary among models of ACF and the assertion that ``I
have characteristic $p$'' can easily be expressed as a sentence of the
language of ACF. 
\end{examples}

\begin{exercise}\label{E:m.c.impliesc.} Suppose that $\theory$ is a 
model complete theory in $\lan$ and that either 
\begin{enumerate}
\item any two models of $\theory$ are isomorphically embedded into a
third or
\item there is a model of $\theory$ which is isomorphically embedded in
any other.
\end{enumerate}
Then prove that $\theory$ is complete.

\end{exercise}


\begin{examples}  Let $\mathbb N$ be the natural numbers and $<$ the
usual ordering.  Let $\mb = \langle \mathbb N , < \rangle$ and $\ma =
\langle \mathbb N \setminus \{ 0 \} , <\rangle$ be models for the language
with one binary relation symbol $<$.  $\Th \ma$ is, of course,
complete, but it is not model complete because it is not existentially
complete.
In fact the model $\ma$ is not existentially closed because $\mb \models
\Th \ma$ and $\ma \seq \mb$ and $\mb_\ba \models ( \exists v_0 ) (v_0 <
c_1 )$ where $c_1$ is the constant symbol with interpretation $1$.  But
$\ma_\ba$ does not satisfy this existential sentence.
\end{examples}


\addcontentsline{toc}{section}{Lindstr\"{o}m's Test}
\begin{theorem} (Lindstr\"{o}m's Test)\\
\index{Lindstr\"{o}m's Test}%
Let $\theory$ be a theory in a countable language $\lan$ such that 
\begin{itemize}
\item[(1)] all models of $\theory$ are infinite,
\item[(2)] the union of any chain of models of $\theory$ is a model of
$\theory$, and 
\item[(3)] $\theory$ is $\kappa$-categorical for some infinite cardinal
$\kappa$.
\end{itemize}
Then $\theory$ is model complete.
\end{theorem}

\begin{proof} W.L.O.G. we assume that $\theory$ is satisfiable.
We use conditions (1) and (2) to prove the following:

\begin{claim} $\theory$ has  existentially closed models of each
infinite size $\kappa$.
\end{claim}

\begin{proof}[Proof of Claim]   By the L\"{o}wenheim-Skolem Theorems we
get $\ma_0 \models \theory$ with $|\ba_0| = \kappa$.  We recursively
construct a chain of models of $\tee$ of size $\kappa$ \[ \ma_0 \seq
\ma_1 \seq \dots \seq \ma_n \seq \ma_{n+1} \seq \cdots \]
with the property that 
\begin{center} if $\mb \models \tee$ and $\ma_{n+1} \seq \mb$
and $\sigma$ is an existential sentence of $\Th (\mb_{\ba_n})$, then
 $\left(\ma_{n+1} \right)_{\ba_n} \models \sigma$. \end{center}

Suppose $\ma_n$ is already constructed; we will construct $\ma_{n+1}$.
Let $\Sigma_n$ be a maximally large set of existential sentences of
$\lan_{\ba_n}$
such that for each finite  $\Sigma' \seq \Sigma_n$ there is a
model
$\mc$ for $\lan_{\ba_n}$ such that
\[\mc \models 
\Sigma' \cup \tee \cup \triangle_{\ma_n} \] 

 By compactness $\tee \cup \Sigma_n \cup
\triangle_{\ma_n}$ has a model $\md$ and without loss of generosity
$\ma_n
\seq \md$.  By the Downward L\"{o}wenheim-Skolem Theorem we get $\me$
such that 
$\ma_{n} \seq \me$, $|\me| = \kappa$ and $\me \prec \md$. 

Let $\ma_{n+1} = \me |\lan$; we will show that $\ma_{n+1}$ has the
required properties.  Since $\me \equiv \md$, $\me \models \tee \cup
\triangle_{\ma_n}$ and so $\ma_{n} \seq \ma_{n+1}$ (See
Exercise~\ref{X:verify}). 

Let $\bmt$ with $\ma_{n+1} \seq \mb$ and $\sigma$ be an existential
sentence of $\Th (\mb_{\ba_n})$; we will show that $(\ma_{n+1})_{\ba_n}  
\models \sigma$. Since $\Sigma_n$ consists of existential sentences and
$\md \equiv \me \equiv (\ma_{n+1})_{\ba_n} \seq \mb_{\ba_n}$ we have 
(see Exercise~\ref{X:verify}) that $\mb_{A_n} \models \Sigma_n$.
The maximal property
of $\Sigma_n$ then forces $\sigma$ to be in $\Sigma_n$ because if
$\sigma \notin \Sigma_n$ then there must be some finite $\Sigma' \seq
\Sigma_n$ for which there is no $\mc$ such that $\mc \models \Sigma'
\cup \{ \sigma \} \cup \tee \cup \triangle_{\ma_n}$; but $\mb_{\ba_n}$
is such a $\mc$!  Now since $\sigma \in \Sigma_n$ and $\me \equiv \md
\models \Sigma_n$ we must have $\me = (\ma_{n+1})_{\ba_n} \models
\sigma.$

Now let $\ma$ be the union of the chain. By hypothesis $\amt$.  It is
easy to check that
$|\ba| = \kappa$.  To check that $\ma$ is existentially closed, let
$\bmt$ with $\masb$ and let $\sigma$ be an existential sentence of 
$\Th(\mb_\ba)$.  Since $\sigma$ can involve only finitely
many constant symbols, $\sigma$ is a sentence of $\lan_{\ba_n}$ for
some $n \in \nat$.  Thus $\ma_{n+1} \seq \ma \seq \mb$ gives that
$(\ma_{n+1})_{\ba_n}
\models \sigma$.  Since $\sigma$ is existential (see
Exercise~\ref{X:verify} again) we get that $\ma_{\ba} \models \sigma$.  This
completes the proof of the claim.
\renewcommand{\qedsymbol}{}
\end{proof}

We now claim that $\theory$ is model complete using Theorem
\ref{T:robinson}  by showing that every model 
$\ma$ of $\theory$ is existentially closed. There are three cases to 
consider:
\begin{enumerate}
\item $|\mathbf A | = \kappa $
\item $|\mathbf A | > \kappa $
\item $|\mathbf A | < \kappa $
\end{enumerate}
where $\theory$ is $\kappa$-categorical.

\begin{proof}[Case (1)] 
Let $\ma^{\ast}$ be an existentially  closed model of $\theory$ of size 
$\kappa$. Then there is an isomorphism $f: \ma \to \ma^{\ast}$. Hence
$\ma$ is existentially closed.
\renewcommand{\qedsymbol}{}
\end{proof}

\begin{proof}[Case (2)] Let $\sigma$ be an existential sentence of
$\lan_\ba$ and $\mb \models \theory$ such that $\ma \seq \mb$ and $\mb_\ba
\models \sigma$.
%end of page 22 page 23 begins
Let $X= \{ a \in \mathbf A : c_a \mbox{ occurs  in } \sigma \} $.
By the Downward L\"{o}wenheim-Skolem Theorem we can find $\ma'$ 
such that $\ma' \prec \ma $, $ X \subseteq \mathbf{A}'$ and 
$|\mathbf{A}'|=\kappa$.
Now by Case (1) $\ma'$ is existentially closed and we have $\ma' 
\subseteq \mb$ and $\sigma$ in $\lan_{\ba'}$ so $\ma_{\ba'}' \models
\sigma $.
But since $\sigma \in  \mbox{Th}(\ma_{\ba'}') $ and $\ma' \prec \ma $ we 
have $\ma_\ba \models \sigma $.
\renewcommand{\qedsymbol}{}
\end{proof}

\begin{proof}[Case (3)] Let $\sigma$ and $\mb$ be as in case (2).
By the Upward L\"{o}wenheim-Skolem Theorem we can find $\ma'$
such 
that $\ma \prec \ma'$ and $|\ma'| = \kappa $.
By case (1) $\ma'$ is existentially  closed.
\renewcommand{\qedsymbol}{}
\end{proof}

\begin{claim} There is a model $\mb'$ such that $\ma' \subseteq \mb' $ and
$\mb_\ba \equiv \mb_\ba' $.
\end{claim}

Assuming this claim, we have 
$\mb' \models \theory$ and 
$\mb_{\ba}' \models \sigma$ and by the fact that $\ma'$ is
existentially 
closed we have $\ma_{\ba'}' \models \sigma$. Since $\ma 
\prec \ma'$ we have $\ma_\ba  \models \sigma$.

The following lemma implies the claim and completes the proof of the 
theorem.

\end{proof}


\begin{lemma} Let $\ma$, $\mb$ and $\ma'$ be models for $\lan$ such that
$\ma \seq \mb$ and $\ma \prec \ma'$. Then there is a model $\mb'$ for
$\lan$ such that $\ma' \seq \mb'$ and $\mb_\ba \equiv
\mb_\ba'$.
\end{lemma}


\begin{proof} Let \ma, \mb, $\ma'$ and $\lan$ be as above.

Let $\tau$ be a  sentence from $\triangle_{\ma'}$.
%
Let $\{ d_j : 0 \leq j \leq m \}$ be the constant symbols from
$\lan_{\ba'} \setminus \lan_\ba $ appearing in $\tau$. Obtain a quantifier
free formula $\varphi ( \unot{m} ) $
of $\lan_\ba$ by exchanging each $d_j$ in $\tau$ with a new variable
$u_i$.
Since $\ma_{\ba'}' \models \tau$ we have $\ma_\ba' \models \existsu{u}{m}
\varphi $.
%
Since $\ma \prec \ma'$, Exercise \ref{X:expand} gives us $\ma_\ba \prec \ma_\ba'$ and so $\ma_\ba \models \existsu{u}{m} \varphi $.
%

Also by Exercise \ref{X:expand} we have $\ma_\ba \seq \mb_\ba$, so  $ \mb_\ba \models \existsu{u}{m} \varphi $.
%
Hence for some $\bnot{m}$ in $\mathbf{B}$, $\mb_\ba \models \varphi [ 
\bnot{m} ]$.
%
Expand $\mb_\ba$ to be a model $\mb_{\ba}^{\ast}$ for the language 
$\lan_\ba \cup \{d_j : 0 \leq j \leq m \}$ by interpreting each $d_j$ as $b_j$.
%
Then $\mb_{\ba}^{\ast} \models \tau$ and so $\mbox{Th}(\mb_\ba) \cup \{
\tau \} $ is satisfiable.
%

This shows that $\Th (\mb_\ba) \cup \Sigma$ is satisfiable for each
finite subset $\Sigma \seq \triangle_{\ma'}$.  
By the Compactness Theorem there is a model 
$\mc \models \Th (\mb_\ba)  \cup \triangle_{\ma'}$.  
Using the Diagram Lemma for the language $\lan_\ba$ we
obtain a model $\mb'$ for $\lan$ such that $\ma_{\ba}' \seq \mb_{\ba}'$
and $\mb_{\ba}' \cong \mc | \lan_\ba$.  
Hence $\mb_{\ba}' \models \Th(\mb_\ba)$ and so $\mb_{\ba}' \equiv \mb_\ba$.



\end{proof}



\begin{exercise}  Suppose $\ma \prec \ma'$ are models for $\lan$.
Prove that for each sentence $\sigma$ of $\lan_\ba$, if
$\triangle_{\ma'} \models \sigma$ then $\triangle_\ma \models \sigma$.
\end{exercise}

\begin{exercise}\label{X:uni-exi} Prove that if $\theory$ has a
universal-existential set
of axioms, then the union of a chain of models of $\theory$ is also a
model of $\theory$.
\end{exercise}

\begin{rem} The converse of this last exercise is also true; it is usually 
called the Chang - ~{\L}o{\'s} -~Suszko Theorem.
\end{rem}

\begin{theorem}\label{T:mcomp} The following theories are model complete:
\begin{enumerate}
\item dense linear orders without endpoints. (DLO)
\item algebraically closed fields. (ACF)
\end{enumerate}
\end{theorem}

\begin{proof} (DLO): This theory has a universal existential set of axioms 
so that it is closed under unions of chains.  It is 
$\aleph_0$-categorical (by Exercise \ref{X:cat}) so Lindstr\"{o}m's
test applies.

(ACF): We first prove that for any fixed characteristic $p$, the theory 
of algebraically closed fields of characteristic $p$ is model complete. 
The proof is similar to that for DLO, with $\aleph_1$-categoricity
(Lemma \ref{L:closed} ).


Let $\ma \seq \mb $ be algebraically closed fields. They must have
the 
same characteristic $p$. Therefore $\ma \prec \mb$.

\end{proof}

\begin{corollary}  Any true statement about the rationals involving
only the usual ordering is also true about the reals.
\end{corollary}

\begin{proof}  Let $\ma = \langle \bf{\rat}, \pmb{<_1} \rangle$ and 
$\mb = \langle \bf{\rea}, \pmb{<_2} \rangle$ where $\pmb{<_1}$ and
$\pmb{<_2}$ are the usual orderings.  The precise version of this
corollary is: $\ma \prec \mb$.  This follows from
Theorem~\ref{T:robinson}
and Theorem~\ref{T:mcomp} and the easy facts that $\ma \models
\mbox{\bf{DLO}}$, $\mb \models \mbox{\bf{DLO}}$  and $\masb$.  The
reader will appreciate the power of these theorems by trying to prove
$\mapb$ directly, without using them.
\end{proof}


\addcontentsline{toc}{section}{Hilbert's Nullstellensatz}
The model completeness of ACF can be used to prove Hilbert's Nullstellensatz. The result below is the heart of the matter.
\begin{corollary}

Let $\Sigma$ be a finite system of polynomial equations and inequations 
in several variables with coefficients in the field $\ma$. If $\Sigma$ 
has a solution in some field extending $\ma$ then $\Sigma$ has a solution 
in the algebraic closure of $\ma$.
\end{corollary}

\begin{proof} Let $\sigma$ be the existential sentence of the language 
$\lan_\ba$ which asserts the fact that there is a solution of $\Sigma$.  
Suppose $\Sigma$ has a solution in a field $\mb$ with $\ma \seq \mb$. 
Then $\mb_\ba \models \sigma$.
So $\mb_{\ba}' \models \sigma$ where $\mb'$ is the algebraic closure of 
\mb. Let $\ma'$ be the algebraic closure of \ma. Since $\ma \seq \mb$, we 
have $\ma' \seq \mb'$.

By Theorem \ref{T:mcomp}, ACF is model complete, so $\ma' \prec \mb'$. 
Hence $\ma_\ba' \equiv \mb_\ba'$ and $\ma_\ba' \models \sigma$. 
\end{proof}

The usual form of the (weak) Nullstellensatz can now be obtained from the algebraic fact that the ideal $\mathcal{I}$ of the polynomial ring $\ma [x_{1}, \dots , x_{n} ]$ generated by $\Sigma$ is proper exactly when $\mathcal{I}$ has a solution in the field $\ma [x_{1}, \dots , x_{n} ] / \mathcal{I'}$ for some maximal ideal $\mathcal{I'}$ containing $\mathcal{I}$.


\begin{rem} 
We cannot apply Lindstr\"{o}m's Test to the theory of real closed ordered fields 
(RCF) because RCF is not categorical in any infinite cardinal. This is because, as 
demonstrated in Theorem \ref{T:Leibniz}, RCF neither implies nor denies the existence of infinitesimals. Nevertheless, as we shall later prove, RCF is indeed model complete.
\end{rem}
\begin{exercise}\label{E:m.c.RCF}
Use Exercise \ref{E:m.c.impliesc.} and the fact that RCF is model complete to show that  RCF is complete.
Step 0: the integers, step 1: the rationals, step 2: the real algebraic numbers, step 3: ${\dots}$
\end{exercise}













\chapter{The Seventeenth Problem}
\addcontentsline{toc}{section}{Positive definite rational functions are
the sums of squares}

We will give a complete proof later that RCF, the theory of real closed
ordered fields, is model complete.  However, by assuming this result
now, we can give a solution to the seventeenth problem of the list of
twenty-three problems of  David Hilbert's famous address to the 1900
International Congress of Mathematicians in Paris.



\begin{corollary}\label{C:Artin} (E. Artin)\\
Let $q ( \xnot[1]{n} )$ be a rational function with real coefficients, 
which is positive definite. i.e. \[ q( \anot[1]{n}) \geq 0 \mbox{ for
all } 
\anot[1]{n} \in \mathbb{R} \]

Then there are finitely many rational functions with real coefficients \\
$f_1(\xnot[1]{n} )$, $\dots$, $f_m ( \xnot[1]{n})$ such that \[
q(x_1, 
\dots , x_n ) = \sum_{j=1}^{m} (f_j ( \xnot[1]{n}))^2 \]
\end{corollary}

We give a proof of this theorem after a sequence of lemmas.  The first
lemma just uses calculus to prove the special case of the theorem in which
$q$ is a polynomial in only one variable.  This result probably motivated
the original question.

\begin{lemma}    A positive definite real polynomial is the sum of
squares of real polynomials.
\end{lemma}

\begin{proof} We prove this by induction on the degree of the
polynomial. Let $p(x) \in \mathbb R [x]$ with degree $deg(p)
\geq 2$ and $p(x) \geq 0 $ for all real $x$. Let $p(a) =
\mbox{ min} \{ p(x) : x \in \mathbb R \}$, so \[p(x) = (x -a) q(x) + p(a)
\mbox{ and  } p'(a) =0 \] for some polynomial $q$. But
\[  p'(a) =[(x-a)q'(x) +q(x)] \bigr|_{x=a} =q(a) \]
so $q(a) =0$ and $q(x) = r(x) (x-a)$ for some polynomial $r(x)$. So
\[  p(x) = p(a) + (x-a)^2 r(x) .\]  For all real $x$ we have 
\[ (x -a)^2 r(x) = p(x) - p(a) \geq 0. \]
Since $r$ is continuous, $r(x) \geq 0$ for all real $x$, and 
$deg(r) = deg(p) -2 $.
So, by induction $ r(x) = \sum_{i=1}^{n} \left( r_i (x) \right)^2$
where each $r_i (x) \in \mathbb R [x]$.
\[\mbox{So } p(x) = p(a) + \sum_{i=1}^{n} (x-a)^2 \left( r_i (x)
\right)^2. \]
\[\mbox{i.e. } p(x) =  \left[ \sqrt{ p(a) } \right]^2 + \sum_{i=1}^{n}
\left[ (x-a)r_i(x) \right]^2 .\]

\end{proof}


The following lemma shows why we deal with sums of rational functions
rather than sums of polynomials.

\begin{lemma}  $x^4 y^2 + x^2 y^4 - x^2 y^2 +1$ is positive definite,
but  not the sum of squares of polynomials.
\end{lemma}

\begin{proof}  Let the polynomial be $p ( x, y)$.  A little calculus
shows that the minimum value of $p$ is $\frac{26}{27}$ and confirms
that $p$ is positive definite.  

Suppose \[ p( x, y) = \sum_{i = 1}^{l} \left( q_i ( x, y ) \right)^2 \]
where $q_i ( x, y)$ are polynomials, each of which is the sum of terms
of the form $a x^m y^n$.  First consider powers of $x$ and the largest
exponent $m$ which can occur in any of the $q_i$.  Since no term of $p$
contains $x^6$ or higher powers of $x$, we see that we must have $m
\leq 2$.  Considering powers of $y$ similarly gives that each $n \leq
2$.  So each $q_i ( x, y) $ is of the form: 
\[ a_i x^2y^2 + b_i x^2 y + c_i x y^2 + d_i x^2 + e_i y^2 + f_i xy +
g_i x + h_i y +k _i \]
for some coefficients $a_i , b_i , c_i , d_i , e_i , f_i , g_i , h_i$
and $k_i$.  Comparing coefficients of $x^4 y^4$ in $p$ and the sum of
the $q_i^2$ gives \[0 = \sum_{i =1}^l a_i^2\] so each $a_i =0$.
Comparing
the
coefficients of $x^4$ and $y^4$ gives that each $d_i = 0 = e_i$.  Now
comparing the coefficients of $x^2$ and $y^2$ gives that each $g_i = 0
= h_i$.  Now comparing the coefficients of $x^2 y^2$ gives \[ -1 =
\sum_{i =1}^l f_i^2 \] which is impossible.

\end{proof}

The next lemma is easy but useful.

\begin{lemma}\label{L:Art}  The reciprocal of a sum of squares is a sum
of squares. 
\end{lemma}
\begin{proof} 
For example \[ \frac{1}{A^2 + B^2} = \frac{A^2 + B^2}{(A^2 + B^2)^2} = 
\left[ \frac{A}{A^2 + B^2 } \right]^2 + \left[ \frac{B}{A^2 + B^2} 
\right]^2 \]


\end{proof}

The following lemma is an algebraic result of E. Artin and O. Schreier,
who invented the theory of real closed fields.

\begin{lemma}\label{L:sum} Let $\ma = \langle \ba, \pmb{+}, \pmb{\cdot}
, \pmb{<}\negthickspace_\ba ,\pmb{ 0}, \pmb{1 }
\rangle$ be an ordered field such that each positive element of $\ba$
is the sum of squares of elements of $\ba$. Let $\mb$ be a field
containing the reduct of 
$\ma$ to $\{ + , \cdot , 0, 1 \}$ as a subfield and such that zero is not 
the sum of non-zero squares in $\mb$.

Let $b \in \bb \setminus \ba $ be such that $b$ is not the sum of
squares of elements of $\bb$. Then there is an ordering 
$\pmb{<}\negthickspace_ \bb$  on $\bb$ with $b \pmb{<}\negthickspace_\bb \:0$
such that $\ma $ is an ordered subfield of $ \langle \bb, \pmb{+}, \pmb{\cdot}
, \pmb{<}\negthickspace_\bb ,\pmb{ 0}, \pmb{1 } \rangle$ .
\end{lemma}

\begin{proof} It suffices to find a set $P \seq \bb$ of ``positive 
elements'' of $\bb$ such that 
\begin{itemize}
\item[(1)] $-b \in P$
\item[(2)] $0 \notin P$
\item[(3)] $c^2 \in P$ for each $c \in \bb \setminus \{ 0 \} $
\item[(4)] $P$ is closed under $+$ and $\cdot$
\item[(5)] for any $c \in \bb \setminus \{ 0 \} $ either $c \in P $ or $-c
\in P$.
\end{itemize}

Once $P$ has been obtained, we define $\pmb{<}\negthickspace_\bb$ as
follows: \[ c_1
\pmb{<}\negthickspace_\bb \,
c_2 \mbox{ iff } c_2 - c_1 \in P.\]
For each $a \in \ba$, if $0 \pmb{<}\negthickspace_\ba \,  a$ then $a$
is a
sum of squares
and
so by (3) and (4)  $a \in P$.  Thus $\pmb{<}\negthickspace_\bb$ extends
$\pmb{<}\negthickspace_\ba$.



So that all that remains to do is to construct such a $P$.
The first approximation to $P$ is $P_0$.
\[ \mbox{Let } P_0 = \left\{ \sum_{i=1}^{l} c_{i}^{2} 
- \sum_{j=1}^{m} 
d_{j}^{2}b : l,m \in \mathbb{N} , c_i \in \bb, d_j \in \bb \mbox{ not all 
zero} \right\} \]

We claim that (1), (2), (3) and (4) hold for $P_0$.
(1) and (3) are obvious. In order to verify 
(2),  note that if $\sum_{j=1}^{m} d_{j}^{2}b = \sum_{i=1}^{l}
c_{i}^{2}$, then
by 
the previous lemma about reciprocals of sums of squares, b would be a sum 
of squares.
Now (4)  holds by definition of $P_0$, noting
that $c_{i}^{2}(-d_j^2b) =
- (c_i d_j )^2b$ and \\
 $(-d_j^2b)(-d_k^2b)=(d_jd_kb)^2$.


We now  construct  larger and larger versions of $P_0$ to take care of
requirement (5).  We  do this in the following way.  Suppose $P_0 \seq
P_1$, $P_1$ satisfies (1), (2), (3) and (4), and $c \notin P_1 \cup \{ 0 \} $.  We
define $P_2$ to be: \[ \{ p ( - c) : p \mbox{ is a polynomial with
coefficients in } P_1 \}. \]
It is easy to see that $-c \in P_2$, $P_1 \seq P_2$ and that (1), (3)
and (4) hold for $P_2$.

To show that (2) holds for $P_2$ we suppose that $p(-c) = 0$ and bring
forth a contradiction.  Considering even and odd exponents we obtain:
\[ p(x) = q(x^2) + x r(x^2) \] for some polynomials $q$ and $r$ with
coefficients in $P_1$ and so \[ 0 = p (-c) = q( c^2) - c r (c^2). \]  

By (3) and (4) both $q(c^{2})$ and $r(c^{2})$ are in $P_1$; in particular $r(c^{2}) \neq 0$. But then 
\[ c = q (c^2) \cdot r ( c^2) \cdot \left( \frac{1}{r (c^2)} \right)^2 \] and since each of the factors on the right hand side is in $P_1$ we get a contradiction.

 \end{proof}

Now we need:

\begin{lemma}\label{L:ofrcf}
\index{ordered field}%
\index{real closed ordered field}%
 Every ordered field can be embedded as a 
submodel of a real closed ordered field.
\end{lemma}


\begin{proof} It suffices to prove that for every ordered field $\ma$
there is an ordered field $\mb$ such that $\ma \seq \mb$ and for each
natural number $n \geq 1$, $\mb \models \sigma_n$ where $\sigma_n$ is
the sentence in the language of field theory which formally states: 
\begin{quotation} If $p$ is a polynomial of degree at most $n$ and $w <
y$ such that $p(w) < 0 < p(y)$ then there is an $x$ such that $w < x <
y$ and $p(x) =0$.
\end{quotation}

Consider the statement called IH(n):
\begin{quotation} For any ordered field $\me$ there is an ordered field
$\mf$ such that $\me \seq \mf$ and $\mf \models \sigma_n$.
\end{quotation}

IH(1) is true since any ordered field $\me \models \sigma_1$.  We will
prove below that for each $n$, IH(n) implies IH($n+1$).

 Given our model
$\ma \models \mbox{ORF}$, we will then be able to construct a chain of
models: 
\[ \ma \seq \mb_1 \seq \mb_2 \seq \dots \seq \mb_n \seq \mb_{n+1} \seq
\cdots \] such that each $\mb_n \models \mbox{ORF} \cup \{ \sigma_n
\}$.  Let $\mb$ be the union of the chain.  Since the theory ORF is
preserved under unions of chains (see Exercise~\ref{X:uni-exi}), $\mb
\models \mbox{ORF}$. Furthermore, the nature of the sentences
$\sigma_n$ allows us to conclude that for each $n$, $\mb \models
\sigma_n$ and so $\mb \models \mbox{RCF}$.  All that remains is to
prove that for each n, IH(n) implies IH($n+1$).  We first make a claim:

\begin{claim}  If $\me \models \mbox{ORF} \cup \{ \sigma_n \}$ and $p$
is a polynomial of degree at most $n+1$ with coefficients from $\be$
and $a < d$ are in $\be$ such that $p(a) < 0 < p (d)$ then there is a
model $\mf$ such that $\me \seq \mf$, $\mf \models \mbox{ORF}$ and
there is $b \in \bf{F}$ such that $a < b < d$ and $p(b) =0$.
\end{claim}

Let us first see how this claim helps us to prove that IH(n) implies
IH(n+1). Let $\me \models ORF$; we will use the claim to build a model
$\mf$ such that $\me \seq \mf$ and $\mf \models \sigma_{n+1}$.

We first construct a chain of models of ORF \[ \me = \me_0 \seq \me_1
\seq \dots \seq \me_m \seq \me_{m+1} \seq \cdots \] such that for each
$m$ and each polynomial $p$ of degree at most $n+1$ with coefficients
from $\be_m$ and each pair of $a$, $d$ of elements of $\be_m$ such that
$p(a) < 0 < p(d)$ there is a $b \in \be_{m+1}$ such that $a < b < d $
and $p(b) = 0$.


Suppose $\me_m$ has been constructed; we construct $\me_{m+1}$ as
follows:  let $\Sigma_m$ be the set of all existential sentences of
$\lan_{\be_m}$ of the form \[ (\exists x ) ( c_a < x \wedge x < c_d
\wedge p (x ) = 0 ) \] where $p$ is a polynomial of degree at most
$n+1$ and such that  $c_a$, $c_d$ and the coefficients of the
polynomial $p$ are constant symbols from $\lan_{\be_m}$ and
\[(\me_m)_{\be_m} \models p (c_a) < 0 \wedge 0 < p(c_d)\] We claim that
\[ \mbox{ORF} \cup \triangle_{\me_m} \cup \Sigma_m \] is satisfiable.

Using the Compactness Theorem, it suffices to find, for each finite
subset $\{ \tau_1 , \dots , \tau_k \}$ of $\Sigma_m$, a model $\mc$
such that $\me_m \seq \mc$ and \[ \mc \models \mbox{ORF} \cup \{ \tau_1
, \dots , \tau_k \} . \]
By IH(n), obtain a model $\mf_1$ such that $\me_m \seq \mf_1$ and
$\mf_1 \models \mbox{ORF} \cup \{ \sigma_n \} $.  By the claim, obtain
a model $\mf_2$ such that $\mf_1 \seq \mf_2$ and $\mf_2 \models
\mbox{ORF} \cup \{ \tau_1 \} $.  Again by IH(n), obtain $\mf_3$ such
that $\mf_2 \seq \mf_3$ and $\mf_3 \models \mbox{ORF} \cup \{ \sigma_n
\}$.  Again by the claim, obtain $\mf_4$ such that $\mf_3 \seq \mf_4$
and $\mf_4 \models \mbox{ORF} \cup \{ \tau_2 \}$.  Continue in this
manner, getting models of ORF \[ \me_m \seq \mf_1 \seq \dots \seq
\mf_{2k} \] with each $\mf_{2j} \models \tau_j$.  Since each $\tau_j$
is existential, we get that $\mf_{2k}$ is a model of each $\tau_j$ (see
Exercise \ref{X:verify}).
 \[\mbox{Let } \md \models \mbox{ORF} \cup \triangle_{\me_m} \cup
\Sigma_m \]
and then use the Diagram Lemma to get $\me_{m+1}$ such that $\me_m \seq
\me_{m+1}$, $\me_{m+1} \models \mbox{ORF}$ and $\me_{m+1} \models
\Sigma_m$, thus satisfying the required property concerning polynomials
from $\be_m$.

Let $\mf$ be the union of the chain.  Since ORF is a
universal-existential theory, $\mf \models \mbox{ORF}$ (see
Exercise~\ref{X:uni-exi}) and $\mf \models \sigma_{n+1}$ by
construction.
So IH($n+1$) is proved.

We now finish the entire proof by proving the claim.

\begin{proof}[Proof of Claim]  Suppose that $p(x) = q(x) \cdot s(x)$ with the degree of $q$ at most $n$. Since $\me \models \sigma_n$ we are guaranteed $c \in \bf{E}$ with $ a < c < d$ and $q(c) = 0$. Hence $p(c) = 0$ and we can let $\mf = \me$.

So we can assume that $p$ is irreducible over $\be$. Introduce a new
element $b$ to $\be$ where the place of $b$ in the ordering is given
by:
 \[ b < x \mbox{  iff  } p (y) > 0 \mbox{ for all $y$ with }x \leq y \leq d. \]
Note that $b < d$ since $p(d) > 0$.

The fact that $p$ is irreducible over $\be$ means that we can extend
$\langle \be ,\pmb{ +} , \pmb{\cdot} , \pmb{0} ,\pmb{ 1} \rangle$ by
quotients of polynomials in $b$ of degree $\leq n$ in the usual way to form a field 
$\langle \bf{F}, \pmb{+} ,\pmb{\cdot} , \pmb{0} , \pmb{1} \rangle$ in which 
$p(b) = 0$.  We leave the details to the reader, but point out that
the construction cannot force $q(b) = 0$ for any polynomial $q(x)$ with
coefficients from $\be$  of degree $\leq n$.  
This is because we could take such a $q(x)$ of lowest
degree and divide $p(x)$ by  it to get \[ p(x) = q(x) \cdot s(x) +
r(x) \] where $\mbox{degree of } r  \mbox{ is less than the degree of } q$.  This means
that $r(x) =0$ constantly and so $p$ could have been factored over $\be$.  

Now we must expand $\langle \bf{F}, \pmb{ +} , \pmb{\cdot}, \pmb{ 0}
,\pmb{1} \rangle$ to an ordered field
$\mf$ while preserving the order of $\me$.  We are aided in this by the
fact that if $q$ is a polynomial of degree at most $n$ with
coefficients from $\be$ then there are $a_1$ and $a_2$ in $\be$ such
that $a_1 < b < a_2$ and $q$ doesn't change sign between $a_1$ and
$a_2$; this comes from the fact that $\me \models \sigma_n$. 
\renewcommand{\qedsymbol}{}
\end{proof}
\end{proof}



\begin{proof}[Proof of the Corollary]
Using Lemma \ref{L:Art} we see that it suffices to  prove the corollary
for a polynomial $p( x_1 , \dots , x_n)$ such 
that $p(a_1, \dots , a_n) \geq 0$ for all $a_1 , \dots , a_n \in \mathbb{R}$.

Let $\mb = \langle \mathbb{R} ( x_1, \dots , x_n ), \pmb{+}, \cdot,
\bf{0}, \bf{1} \rangle$ be the field of ``rational 
functions''. Note that $\mb$ contains the reduct of $\mathfrak R$ to
$\{ +,
\cdot, 0 , 1 \}$ as a subfield, where $\mr$ is defined as in  
Example~\ref{X:real} as the usual real numbers.

By Lemma \ref{L:sum}, if $p$ is not the sum of squares in $\mb$, then 
we can find an ordering $<_\bb$ on $\mb$, extending the ordering on
the reals, such that the expansion $\mb'$ 
of $\mb$ is an ordered field and $p(x_1, \dots , x_n) <_ \bb 0 $.

We now use Lemma \ref{L:ofrcf} to embed $\mb'$ as a submodel of a real 
closed field $\mathfrak M$, $\mb' \seq \mathfrak M$. 

Let $\varphi ( \vnot[1]{n} )$ be the quantifier free formula which we
informally write as 
$p( \vnot[1]{n} ) < 0$ where $\varphi$ involves constant symbols 
$c_{r_i}$ for the real coefficients $r_i$ of $p$.
Let $\psi$ be the formula of the language of field theory,  obtained
from $\varphi$ by substituting a new 
variable $u_i$ for each $c_{r_i}$. We have \[ \mb' \models \exv[1]{n}
\psi
[ \rnot[1]{k} ] \]  \[\mbox{and so } \mathfrak M
\models \exists v_1 \dots \exists v_n \psi [ r_1 , \dots , r_k] \]

Since RCF is model complete and $\mr \seq \mb' \seq \mm$,
Theorem~\ref{T:robinson} gives $\mathfrak R \prec \mathfrak M$ and so
\[\mathfrak R  \models \exists v_1 \dots \exists v_n \psi [ r_1 , \dots
, r_k] \]
i.e. there exist $a_1, \dots , a_n$ in $\mathbb R$ such that $p(a_1,
\dots , 
a_n) < 0 $.



\end{proof}


Hilbert also asked: \begin{quotation} If the coefficients of a positive
definite rational function are rational numbers (i.e. it is an element
of $\mathbb{Q} ( \xnot[1]{n} ) $) is it in fact the sum of squares of
elements of $\mathbb{Q}( \xnot[1]{n})$?
\end{quotation}
The answer is ``yes'' and the proof is very similar.  Let $\mq =
\langle
\mathbb{Q}, \pmb{+}. \pmb{\cdot}, \pmb{<}, \pmb{0}, \pmb{1} \rangle$ be
the ordered field of rationals as in Example~\ref{X:real}.
Lemma~\ref{L:sum} holds for $\ma = \mq$ and $\mb = \langle \mathbb{Q} (
\xnot[1]{n}) , \pmb{+}, \pmb{\cdot}, \pmb{0}, \pmb{1} \rangle$; by
Lemma~\ref{L:Art} every positive rational number is the sum of squares
since every positive integer is the sum of squares $n = 1 + 1 + \dots +
1$.


\begin{exercise} Finish the answer to Hilbert's question by making any
appropriate changes to the proof of the corollary.  Hint: create a real closed 
ordered field into which $\mb'_{\mathbb{Q}}$ and $\mr _{\mathbb{Q}}$ are each isomorphically embedded. Exercise \ref{E:rcthm} and Exercise \ref{E:m.c.RCF} may be useful.
\end{exercise}


\chapter{ Submodel Completeness}

\addcontentsline{toc}{section}{Elimination of quantifiers}
\begin{definition}
\index{elimination of quantifiers}%
 A theory $\mathcal T$ is said to
\emph{admit elimination of quantifiers} in $ \mathcal L$ whenever for each
formula
$\varphi  (v_0 , \dots , v_p) $ of $\mathcal L$ there is a quantifier
free
formula $\psi (v_0 , \dots , v_p)$ such that: \[\mathcal T \models (
\forall v_0 \dots \forall v_p ) ( \varphi (v_0 , \dots , v_p)
\leftrightarrow \psi (v_0 , \dots, v_p)) \]

\end{definition}

\begin{rem} 
There is a fine point with regard to the above definition.  If
$\varphi$ is actually a sentence of $\lan$ there are no free variables
$v_0 , \dots , v_p$.  So $\theory \models \varphi \leftrightarrow \psi$
for some quantifier free formula with no free variables.  But if $\lan$
has no constant symbols, \emph{there are no} quantifier free formulas with
no free variables.  For this reason we assume that $\lan$ has 
at least one constant symbol, or we restrict to those formulas $\varphi$
with at least one free variable.  This will become relevant in the proof
of Theorem~\ref{T:subcom} for (2) $\Rightarrow$ (3).
\end{rem}

\begin{definition}
\index{submodel complete theory}%
 A theory $\mathcal T$ is said to be
\emph{submodel
complete} whenever $\mathcal T \cup \triangle_{\mathfrak{A}} $ is
complete in $\mathcal{L}_{\mathbf{A}}$ for each submodel $\mathfrak A$
of a model of $\mathcal T$.
\end{definition}

\begin{exercise}\label{X:four}  Use Theorem \ref{T:robinson} and the
following theorem
to find four proofs that every submodel complete theory is model
complete.
\end{exercise}


\begin{theorem}\label{T:subcom}
\index{submodel complete}%
 Let $\mathcal T$ be a theory of a language 
$\mathcal L$. The following are equivalent:

\begin{itemize}
\item[(1)] $\mathcal T$ is submodel complete
\item[(2)] If $\mb$ and $\mc$ are models of $\theory$ and $\ma$ is a
submodel of both $\mb$ and $\mc$, then every existential sentence which
holds in $\mb_\ba$ also holds in $\mc_\ba$.
\item[(3)] $\mathcal T$ admits elimination of quantifiers
\item[(4)] whenever $\mathfrak{A} \subseteq \mathfrak{B}$, 
$\mathfrak{A}
\seq \mathfrak{C}$, $\mathfrak{B} \models \mathcal T$ and $\mathfrak
C \models \mathcal T$ there is a model $\mathfrak D$ such that 
$\mathfrak A \subseteq \mathfrak D$ and both
$\mb_\ba$ and $\mc_\ba$ are elementarily embedded in $\md_\ba$.

\end{itemize}
\end{theorem}

 
\begin{proof} (1) $\Rightarrow$ (2) \\
Let $\mb \models \theory$ and $\mc \models \theory$ with $\ma \seq \mb$
and $\ma \seq \mc$.  Then $\mb_\ba \models \theory \cup \tria A$ and
$\mc_\ba \models \theory \cup \tria A$.  So (1) and Lemma \ref{L:com}
give $\mb_\ba \equiv \mc_\ba$.  Thus (2) is in fact proved for all
sentences, not just existential ones.

(2) $\Rightarrow$ (3) \\
We will proceed as we did in the proof of Theorem \ref{T:robinson}. Lemma \ref{L:prenex} shows that it suffices to prove (3) for formulas in prenex normal form.  We do this by induction on the prenex rank of
$\varphi$ using the following claim.

\begin{claim} For each existential formula $\varphi ( \vnot p )$ of $\lan$
there is a quantifier free formula $\psi ( \vnot p)$  such
that \[ \theory \models ( \frv p ) ( \varphi \leftrightarrow \psi ) \]
\end{claim}

\begin{proof}[Proof of Claim]  
Add new constant symbols $\cnot p $ to $\lan$ to form 
\[ 
\lan^{\ast} = \lan \cup \{ \cnot p \} 
\]
and to form the existential sentence $\varphi^{\ast}$ of $\lan^{\ast}$ obtained by
replacing each free occurrence of $v_i$ in $\varphi$ with the corresponding $c_i$.
It suffices to prove that there is a quantifier free sentence $\gamma$ of
$\lan^{\ast}$ such that 
\[ 
\theory \models \varphi^{\ast} \leftrightarrow \gamma . 
\]
Let
\[ 
 \Gamma= \{ \mbox{ quantifier free sentences  } \gamma \mbox{
of } \lan^{\ast} : \theory \models \varphi^{\ast} \to \gamma \}.
\]
It suffices to find some $\gamma$ in $\Gamma$ such that 
$\theory \models \gamma \to \varphi^{\ast}$.  
Since a finite conjunction of sentences of $\Gamma$ is also in $\Gamma$, it suffices to find $\gamma_1 , \dots , \gamma_n$ in $\Gamma$ such that 
\[
 \theory \models \gamma_1 \wedge \dots \wedge \gamma_n \to \varphi^{\ast}. 
\]  
If no such finite subset $\{ \gamma_1 , \dots , \gamma_n \}$
of $\Gamma$ does exist, then each 
\[ 
\theory \cup \{ \gamma_1 , \dots , \gamma_n \}\cup \{ \neg \varphi^{\ast} \} 
\] 
would be satisfiable.  So by compactness it suffices to prove that $\theory \cup \Gamma \models \varphi^{\ast}$.
        
Let $\mc \models \theory \cup \Gamma $ with intent to prove that 
$\mc \models \varphi^{\ast}$. 

Let $\ma$ be the smallest submodel of $\mc $ in the sense of the language 
$\lan^{\ast}$.  That is, every element of $\ma$ is the interpretation of a constant symbol from $\lan ^{\ast}$ or built from these using the functions of $\mc$. Let
 \[ 
 \Delta = \{ \delta : \delta \mbox{ is quantifier free sentence of } \lan ^{*} 
\mbox{ and } \ma \models \delta \}.
\]
We wish to show that $\theory \cup \{ \varphi^{\ast} \} \cup \Delta $ is
satisfiable.  By compactness, it suffices to consider only 
$\theory \cup \{ \varphi^{\ast} , \tau \}$ where $\tau$ is a single 
sentence in $\Delta$.  If this set is not satisfiable then 
$\theory \models \varphi^{\ast} \to \neg \tau $ so that by definition of 
$\Gamma$ we have
$\neg \tau \in \Gamma$ and hence $\mc \models \neg  \tau$.  But this is
impossible since $\ma \seq \mc$ means that $\mc \models \Delta $.

Let $\mb' \models \theory \cup \{ \varphi^{\ast} \} \cup \Delta$.  The
interpretations of the constant symbols in $\lan ^{\ast}$ generate a submodel of $\ma' \seq \mb'$ isomorphic to  $\ma$. So by Exercise \ref{X:eeek}, there is a model $\mb$ for $\lan^{\ast}$ such that $\mb \cong \mb'$ and $\ma \seq \mb$.

Since $\ma \seq \mb$ and $\ma \seq \mc$ the interpretation of each of $c_{0},\dots,c_{p}$ in $\ma$ is the same as the interpretation in $\mb$ or in 
$\mc$; let's denote these by $a_{0},\dots,a_{p}$. Let $\sigma$ denote the sentence
\[
   ( \exv[0]{p} )(\varphi \wedge v_{0} = c_{a_{0}} \wedge v_{1} = c_{a_{1}}
\wedge \dots \wedge v_{p} = c_{a_{p}})
\] 
which is equivalent to an existential sentence of $\lan_{\ba}$. 

In order to invoke (2) we use the restrictions of $\ma$, $\mb$ and $\mc$ to the language $\lan$.  We have $\mb |\lan \models \theory$, 
$\mc |\lan \models \theory$, $\ma |\lan \seq \mb | \lan$ and 
$\ma | \lan \seq \mc | \lan$.
Since $\mb' \models \varphi^{\ast}$ we have that 
$(\mb | \lan )_\ba \models \sigma$. 
So by (2), $(\mc | \lan )_\ba \models \sigma$ and finally this gives  $\mc \models \varphi^{\ast}$ which completes the proof of the claim.

\renewcommand{\qedsymbol}{}

\end{proof}

We now do the general cases for the proof of the induction on prenex
rank.  There are two cases, corresponding to the two methods available
for increasing the number of alternations of quantifiers:
\begin{itemize}

\item[(a)] the addition of universal quantifiers
\item[(b)] the addition of existential quantifiers.
\end{itemize}

For case (a), suppose $\varphi ( \vnot p ) $ is $\frw m \chi ( \vnot p
, \wnot m )$ and $\chi$ has prenex rank lower than $\varphi$. Then
$\neg \chi$ also has prenex rank lower than $\varphi$ and we can use
the inductive hypothesis on $\neg \chi$ to obtain a quantifier free
formula $\theta_1 ( \vnot p , \wnot m )$ such that 
\[\begin{aligned} \theory &\models (\frv p ) (\frw m ) (\neg \chi
\leftrightarrow
\theta_1) \\
\mbox{So } \theory &\models (\frv p ) (\exw m \neg \chi
\leftrightarrow \exw m \theta_1) 
\end{aligned}
\]
By the claim there is a quantifier free formula $\theta_2 ( \vnot p)$
such that 
\[ \begin{aligned}
\theory &\models ( \frv p ) ( \exw m \theta_1 \leftrightarrow
\theta_2)\\
\mbox{So } \theory &\models ( \frv p ) ( \exw m \neg \chi
\leftrightarrow 
\theta_2)\\
\mbox{So } \theory &\models ( \frv p ) (\frw m  \chi
\leftrightarrow \neg \theta_2)
\end{aligned}
\]
and so $\neg \theta_2$ is the quantifier free formula equivalent to
$\varphi$.

For case (b), suppose $\varphi(v_0 , \dots , v_p )$ is $\exw m \chi (
\vnot p , \wnot m )$ and $\chi$ has prenex rank lower than $\varphi$.
We use the inductive hypothesis on $\chi$ to obtain a quantifier free
formula $\theta_1 ( \vnot p , , \wnot m )$ such that \[ \begin{aligned}
\theory &\models ( \frv p ) ( \frw m ) ( \chi \leftrightarrow \theta_1
) \\
\mbox{So } \theory &\models ( \frv p ) ( \exw m   \chi
\leftrightarrow \exw m \theta_1 )
\end{aligned} 
\]
By the claim there is a quantifier free formula $\theta_2 ( \vnot p )$
such that  \[\begin{aligned}  \theory &\models ( \frv p ) ( \exw m
\theta_1 \leftrightarrow
\theta_2 ) \\
\mbox{So }   \theory &\models ( \frv p ) ( \exw m \chi
\leftrightarrow \theta_2 ) 
\end{aligned}
\]
and so $\theta_2$ is the quantifier free formula equivalent to
$\varphi$.  This completes the proof.


(3) $\Rightarrow$ (4)


Let $\mathfrak{A} \subseteq \mathfrak B$, $\mathfrak A \subseteq
\mathfrak C$, $\mathfrak B \models \mathcal T $ and $ \mathfrak C
\models \mathcal T$. Using the Diagram Lemmas it will suffice  
to show that Th$(\mathfrak{B}_{\bb}) \cup
$ Th$(\mathfrak{C}_{\bc} )$ is satisfiable. Without loss of generosity,
we can ensure that $\lan_\bb \cap \lan_\bc = \lan_\ba$.


By the Robinson Consistency Theorem, it suffices to show that there is
no sentence $\sigma$ of $\mathcal{L}_{\ba}$  such that both: \[
\mbox{Th}(\mathfrak{B}_{\bb} ) \models
\sigma \mbox{ and } \mbox{Th} (\mathfrak{C}_{\bc}) \models \neg \sigma
\]


Suppose $\sigma$ is such a sentence and let $\{ c_{a_0}  , \dots , c_{a_p} \}$ be the set of constant symbols
from $\mathcal{L}_\ba \setminus \mathcal L$ appearing in $\sigma$.

Let $\varphi  (u_0, \dots , u_p )$ be obtained from $\sigma$ by  
exchanging each 
$c_{a_i}$ for a new variable $u_i$.    Let $\psi (u_0, \dots, u_p)$ be
the quantifier free formula from (3): \[ \mathcal T \models (\forall
u_0,\dots ,\forall u_p) ( \varphi \leftrightarrow \psi ) \]

Let $\psi^{\ast}$ be the result of substituting $c_{a_i}$ for each
$u_i$ in $\psi$.  $\psi^{\ast}$ is also quantifier free.

Since $\mb_\bb \models \sigma$, $\mb \models \varphi [ \anot p ]$.
Since
$\mb \models \theory$, $\mb \models \psi [ \anot p ]$ and so
$\mb_\ba \models \psi^{\ast}$.  Since $\psi^{\ast}$ is quantifier
free and $\ma_\ba \seq \mb_\ba$ we have $\ma_\ba \models
\psi^{\ast}$; since $\ma_\ba \seq \mc_\ba $ we then get that
$\mc_\ba \models \psi^{\ast}$.  Hence $\mc \models \psi [ \anot p
] $ and then since $\mc \models \theory$ we then get that $\mc \models
\varphi [ \anot p ]$.  But then this means that $\mc_\ba \models
\sigma$
and so $\mc_\bc \models \sigma$ so $\sigma$ is in $\Th ( \mc_\bc )$ and
we are done.

(4) $\Rightarrow$ (1) \\
Let $\mb \models \theory$ and $\ma \seq \mb$; we show that $\theory
\cup \tria A$ is complete. Since $\mb_\ba \models \theory \cup
\tria A$, we see that it suffices by Lemma \ref{L:com} to show that
$\mb_\ba \equiv \mc'$ for each $\mc' \models \theory \cup \tria A$.

For each such $\mc'$, by Exercise \ref{X:diagram}, there is a model $\mc$ for
$\lan$ such that $\ma \seq \mc$ and $\mc_\ba \cong \mc'$.  Then $\mc
\models \theory$ so by (4) there is a $\md$ with $\ma \subseteq \md$ such that both $\mb_\ba $ and $\mc_\ba$ are elementarily embedded into $\md_\ba$.

In particular $\mb_\ba \equiv \md_\ba \equiv \mc_\ba$ so we are done.

\end{proof}

\begin{examples} (Chang and Keisler)\\
  Let $\tee$ be the theory in the language $\lan = \{ U, V, W, R, S \}$
where $U$, $V$ and $W$ are unary relation symbols and $R$ and $S$ are
binary relation symbols having  axioms which state that there are
infinitely many things, that $U \cup V \cup W$ is everything, that $U$,
$V$ and $W$ are pairwise disjoint, that $R$ is a one-to-one function
from $U$ onto $V$ and that $S$ is a one-to-one function from $U \cup V$
onto $W$.\end{examples}

\begin{exercise}  Show that $\tee$ above is complete and model complete
but not submodel complete.

Hints:  For completeness, use the  {\L}o\'{s}-Vaught test and for model
completeness use Lindstr\"{o}m's test.  For submodel completeness use
(2) of the theorem with $\bmt$ and $\ma \seq \mb$ where $a \in \ba = \{
b \in \bb : \mb \models W(v_0) [b] \}$ along with the sentence \[ (
\exists v_0 ) ( U
(v_0 ) \wedge S ( v_0 , c_a )). \]

\end{exercise}

We will prove in the next chapter that each of the following theories admits 
elimination of quantifiers:
\begin{enumerate}
\item dense linear orders with no end points (DLO)
\item algebraically closed fields (ACF)
\item real closed ordered fields (RCF)
\end{enumerate}


C. H. Langford proved elimination of quantifiers for DLO in 1924.  The
cases of ACF and RCF were more difficult and were done by A. Tarski.
Thus, by Exercise~\ref{X:four}, we will have model completeness of 
RCF which was promised at the beginning of Chapter~5.

\begin{exercise}\label{E:addconstants} be a theory in the language $\lan$
which is submodel complete. Expand $\lan$ to $\lan^{+}$ by only adding new constant symbols. 
Show that $\tee$ admits elimination of quantifiers in $\lan^{+}$. 
Use this and the fact that DLO admits elimination of quantifiers in its own language to show that in the language 
$\lan = \{ < , c_1 , c_2 \}$ where $c_1$ and $c_2$ are constant symbols, DLO is submodel complete but not complete.
\end{exercise}

\begin{exercise}  Suppose $\mathfrak A$ is the reduct of a real closed
ordered  field to the language of field theory.  Show 
that $\mathfrak A [ \sqrt{-1} ] $ is algebraically closed.
 
Hint: Show that any polynomial with coefficients from $\mathfrak A$ has a quadratic factor.
\end{exercise}


\addcontentsline{toc}{section}{The Tarski-Seidenberg Theorem}
\begin{corollary}  (The Tarski-Seidenberg Theorem)

The projection of a semi-algebraic set in $\mathbb{R}^n $ to $\mathbb{R}^m
$ for $m < n$ is also semi-algebraic.  The semi-algebraic sets of
$\mathbb{R}^n $ are defined to be all those subsets of $\mathbb{R}^n$
which can be obtained by repeatedly taking finite unions and intersections
of sets of these two forms 
\[ 
\{ \langle \xnot[1]{n} \rangle \in \mathbb{R}^n : p( \xnot[1]{n} ) =0 \} 
\]
\[  
\{ \langle \xnot[1]{n} \rangle  \in \mathbb{R}^n : q( \xnot[1]{n} ) <0 \} 
\]
where p and q are polynomials with real coefficients.

\end{corollary}

\begin{proof}  We first need a simple result which we state as an exercise. 

Let $\mathfrak{R} = \langle \mathbb R , \pmb{+} , \pmb{\cdot}  ,
\pmb{<}, \mathbf{0}, \mathbf{1} \rangle $ be the usual model of the reals. 
Let $\theory$ be RCF considered as a theory in the language $\lan _{\mathbb{R}}$.

\begin{exercise} A set $X \seq \rea^n$ is semi-algebraic iff there is a
quantifier free formula $\varphi ( \vnot[1]{n} )$ of $\lan _{\mathbb{R}}$  
such that 
\[ X = \{ \langle \xnot[1]{n} \rangle : 
\reals \models \varphi [ \xnot[1]{n} ] \}. \]
\end{exercise}

Now, in order to prove the corollary, let $X \seq \real^n$ be
semi-algebraic and let $\varphi$ be its associated quantifier free
formula. The projection $Y$ of $X$ into $\real^m$ is
 \[ 
 \{ \langle \xnot[1]{m} \rangle : \mbox{for some } \xnot[m+1]{n} \ \langle \xnot[1]{m},
\xnot[m+1]{n} \rangle \in X \} \] 
\[ \mbox{So } Y = \{ \langle \xnot[1]{m} \rangle :
\reals \models \exv[m+1]{n} \varphi [ \xnot[1]{m} ] \}  \]

By a Exercise \ref{E:addconstants} and the assumption that RCF is submodel complete we 
have that $\theory$ admits elimination of quantifiers, so there is a quantifier
free formula $\theta$ of $\lan _{\mathbb{R}} $ such that \[ \theory \models
(\frv[1]{m}) ( \exv[m+1]{n} \varphi \leftrightarrow \theta ) \] 

Hence for all $ \xnot[1]{m} $
\[ \reals \models \exv[m+1]{n} \varphi [ \xnot[1]{m} ] \mbox{ iff  } 
\reals \models \theta [ \xnot[1]{m} ] \] 
\[ \mbox{ So } Y = \{ \langle
\xnot[1]{m} \rangle : \reals \models \theta [\xnot[1]{m} ] \} \] 
and by the exercise, Y is semi-algebraic. 

\end{proof}

As an application of quantifier elimination of ACF we have the following result of A. Tarski.

\begin{corollary}
The truth value of any algebraic statement about the  complex numbers can
be determined algebraically in a finite number of steps.
\end{corollary}

\begin{proof} Let $\mc$ be the complex numbers in the language of field 
theory $\lan$; let $\sigma$ be a sentence of $\lan_{\mathbb C}$. Then let 
$\mathbf A$ be the finite subset $\{ \anot{p} \} \seq \mathbb C$ consisting of those elements of $\mathbb C$ (other than 0 or 1) which are mentioned in 
$\sigma$. Let $\varphi$ be the formula of $\lan$ formed by exchanging
each $c_{a_{i}}$ for a new variable $w_{i}$. Then 
\[
\mbox{ACF} \models \allforu{w}{p} (\varphi \leftrightarrow \psi )
\] 
for some quantifier free $\psi$. Hence 
$\mc \models \sigma$ iff $\cmodphi [ \anot{p} ]$ iff $\cmodpsi [ \anot{p} ]$ 
but checking this last statement amounts to evaluating finitely many 
polynomials in \anot{p}.
\end{proof}

Tarski's original proof actually gave an explicit method for
finding the quantifier free formulas and this led, via the argument
above, to an effective decision procedure for determining the truth of
elementary algebraic statements about the complex numbers.




\chapter{Model Completions}

Closely related to the notions of model completeness and submodel
completeness is the idea of a model completion.

\begin{definition}
\index{model completion}%
\index{theory!model completion}%
 Let $\theory \seq \theory^{\ast}$ be two theories in a
language $\lan$.  $\theory^{\ast}$ is said to be a \emph{model
completion} of
$\theory$ whenever $\theory^{\ast} \cup \tria A$ is satisfiable and
complete in $\lan_\ba$ for each model $\ma$ of $\theory$.
\end{definition}

\begin{lemma} Let $\theory$ be a theory in a language $\lan$.
\begin{itemize}
\item[(1)] If $\tstar$ is a model completion of $\theory$, then for each
$\ma \models \theory$ there is a $\mb \models \tst$ such that $\ma
\seq \mb$.
\item[(2)] If $\tstar$ is a model completion of $\theory$, then $\tstar$
is
model complete.
\item[(3)] If $\theory$ is model complete, then it is a model completion
of itself.
\item[(4)] If $\tstar_1$ and $\tstar_2$ are both model completions of
$\theory$, then $\tstar_1 \models \tstar_2$ and $\tstar_2 \models
\tstar_1$.
\end{itemize}
\end{lemma}

\begin{proof} 
(1) Easy. 
(2) Easier. 
(3) Easiest. 
(4) This needs a proof.  

Let $\ma \models \tstar_2$.  It will suffice to prove that $\ma \models \tstar_1$.

Let $\ma_0 = \ma$.  since $\ma_0 \models \theory$ and $\tstar_1$ is a
model completion of $\theory$ we obtain, from (1), a model $\ma_1 \models
\tstar_1$ such that $\ma_0 \seq \ma_1$.  Similarly, since $\ma_1
\models
\theory$ and $\tstar_2$ is a model completion of $\theory$ we obtain
$\ma_2 \models \tstar_2$ such that $\ma_1 \seq \ma_2$.

Continuing in this manner we obtain a chain: 
\[ \ma_0 \seq \ma_1 \seq \ma_2 \seq \dots \seq \ma_n \seq \ma_{n+1} \seq
\cdots \]
Let $\mb $ be the union of the chain, $\cup \{ \ma_n : n \in \mathbb N
\}$.  For each $n \in \mathbb{N}$ we have $\ma_{2n} \models \tstar_2$.  By part (2) of this lemma and 
by part (4) of Theorem \ref{T:robinson} we get that for each $n$, $\ma_{2n} \prec \ma_{2n+2}$.
By the Elementary Chain Theorem $\ma_0 \prec \mb$.  Similarly $\ma_1 \prec
\mb$.  So $\ma_0 \equiv \ma_1$ and hence $\ma \models \tstar_1$.

\end{proof}

\begin{rem} Part (4) of the above lemma shows that model completions are
essentially unique.  That is, if model completions $\tstar_1$ and
$\tstar_2$ of $\theory$ are closed theories in the sense of Definition
\ref{D:theory} then $\tstar_1 = \tstar_2$.  Since there is no loss in
assuming that model completions are closed theories, we speak of
\emph{the} model completion of a theory $\theory$.

\end{rem}

\begin{theorem}\label{T:modcomp} Suppose $\theory \seq \tstar$ are theories for
a language $\lan$. $\theory^{\ast}$ is the model completion of $\theory$ iff the following two conditions are satisfied.
\begin{itemize}
\item[(1)] For each $\ma \models \theory$ 
there is a $\mb \models \tstar$ with $\ma \seq \mb$.
\item[(2)]  For each $\ma \models \theory$, $\mb \models \theory^{\ast}$
and $\mc \models \tstar$ such that $\ma \seq \mb$ and $\ma \seq \mc$ we
have a model $\md$ such that $\mb_\ba$ is isomorphically embedded into $\md_\ba$
and $\mc \prec \md$. 
\end{itemize}
\end{theorem}

\begin{proof} First, assume that $\theory^{\ast}$ is the model completion of $\theory$. Condition (1) is part (1) of the previous lemma.

Now, let $\ma$, $\mb$ and $\mc$ be as in Condition (2).  By Exercise \ref{X:expand}, $\mb_\ba \models \tstar \cup \tria A$ and $\mc_\ba \models \tstar \cup \tria A$.
Without loss of generosity, we may assume that $\lan_\bb \cap \lan_\bc = \lan_\ba$.

By assumption $\tstar \cup \tria A$ is a complete theory in $\lan_\ba$.
Therefore $\mb_\ba \equiv \mc_\ba$. By the Robinson Consistency Theorem, the set 
of sentences Th$\mb_\bb$ $\cup$ Th$\mc_\bc$ is satisfiable. Let
	\[
   \me \models \mbox{Th}\mb_\bb \ \cup \ \mbox{Th}\mc_\bc
	\]
The Elementary Diagram Lemma now gives us a model $\md$ such that 
$\mc_\ba \prec \md_\ba$ and $\md_\ba \cong \me |\lan _\ba$. By the Diagram lemma $\mb_\ba$ is isomorphically embedded into $\me |\lan_\ba$ and hence also into $\md_\ba$.

\

Now assume that conditions (1) and (2) hold. 

We first show that $\tstar$ is model complete using
Theorem \ref{T:robinson}; we show that $\tstar$ is existentially complete.
Let $\ma \models \tstar$; we show that $\ma$ is existentially closed.  Let
$\mb \models \tstar$ such that $\ma \seq \mb$ and let $\sigma$ 
be an existential sentence of $\lan_\ba$ with $\mb_\ba \models \sigma$;
our aim is to prove that $\ma_\ba \models \sigma$.

We invoke condition (2) with $\mc = \ma$ to get a model $\md$ such that $\ma \prec \md$ and    $\mb_\ba $ is isomorphically embedded into $\md_\ba$. Referring to Exercise \ref{X:eeek} we get a model $\me$ for $\lan _{\ba}$ with 
$\mb _\ba \subseteq \me $ and $\md _\ba \cong \me$.
Since $\sigma$ is existential, By Exercise \ref{X:verify} we have that 
$\me \models \sigma $; and by Exercise \ref{X:iso}, $\md _{\ba} \models \sigma $.
Now $\ma \prec \md$ implies that $\ma_\ba \equiv \md_\ba$ so 
$\ma_\ba \models \sigma$ and $ \tstar$ is model complete.

We now show that $\tstar$ is the model completion of $\tee$.  Let $\ma
\models \theory$; condition (1) gives that $\tstar \cup \tria{A}$  is
satisfiable. We show that $\tstar \cup \tria A$  is
complete in $\lan_\ba$ by showing that for each $\mb \models
\theory^{\ast}$ and $\mc \models \tstar$ with $\ma \seq \mb$  and $\ma
\seq \mc$ we have $\mb_\ba \equiv \mc_\ba$.

Letting $\mb$ and $\mc$ be as above, we invoke condition (2) to obtain a 
model $\md$ such that $\mb_\ba$
is isomorphically embedded into $\md_\ba$ and $\mc \prec \md$.  $\mc
\prec \md$  gives that $\md \models \tstar$. The isomorphic
embedding gives us a model $\me$ such that $\mb \seq \me$ and $\md_\ba
\cong \me_\ba$. So $\me \models \tstar$ . Using the model
completeness of $\tst$ and Theorem \ref{T:robinson} we can infer that
$\mb \prec \me$. We have:
\[ \mb_\ba \equiv \me_\ba \equiv \md_\ba \equiv \mc_\ba\]
and we are done.
\end{proof}

Let's compare the definitions of model completion and submodel
complete. Let $\tst$ be the model completion of $\tee$.  Then $\tst$ will be
submodel complete provided that every submodel of a model of $\tst$ is a model
of $\tee$. Since $\theory \seq \tstar$, it would be enough to show
that every submodel of a model of $\tee$ is again a model of $\tee$.
And this is indeed the case whenever $\tee$ is a universal theory, that
is, whenever $\tee$ has a set of axioms consisting of universal
sentences. Unfortunately, this is not always the case.

\index{DLO!submodel complete}%
\index{ACF!submodel complete}%
\index{RCF!submodel complete}%
Our aim is to show that DLO, ACF and RCF are submodel complete by showing 
that these theories are the model completions of LOR, FLD and ORF respectively. See Example \ref{X:axioms} to recall the axioms for these theories. 
Well, LOR is a universal theory but FLD and ORF are not.
The culprits are the axioms asserting the existence of inverses: 

\[ \forall x \exists y ( x+ y = 0 ) \mbox{ and } 
\forall x (( x \neq 0) \rightarrow \exists y(y \cdot x = 1)) \].

In fact, a submodel $\ma$ of a field $\mb$ is only a commutative semi-ring,
not necessarily a subfield.  Nevertheless, $\ma$ generates a subfield of $\mb$
in a \emph{unique} way.  This motivates the following definition.

\addcontentsline{toc}{section}{Almost universal theories}
\begin{definition}
\index{almost universal}%
\index{theory!almost universal}%
  A theory $\tee$ is said to be \emph{almost
universal}
whenever $\ma \seq \mb$, $\mb \models \theory$ and $\ma \seq \mc $, $\mc
\models \theory$ imply there are models $\md$ and $\me$ such that $\md
\models \theory$, $\ma \seq \md \seq \mb$ and $\me \models \theory$, $\ma
\seq \me \seq \mc$ and $\md_\ba \cong \me_\ba$.
\end{definition}

\begin{examples}
\index{LOR!almost universal}%
 LOR is almost universal since any universal theory
$\tee$
is almost universal --- just let $\md = \me = \ma$ and note $\ma
\models
\theory$.
\end{examples}

\begin{examples}
\index{FLD!almost universal}%
 FLD is almost universal --- just let $\md$ and $\me$ be the
subfields of $\mb$ and $\mc$, respectively, generated by $\ba$.  The
isomorphism $\md_\ba \cong \me_\ba$ is the natural one obtained from the
identity map on $\ba$.
\end{examples}

\begin{examples} 
\index{ORF!almost universal}%
ORF is almost universal --- again just let $\md$ and $\me$
be the ordered subfields of $\mb$ and $\mc$, respectively, generated by
$\ba$.  The extension of the identity map on $\ba$ to the isomorphism
$\md_\ba \cong \me_\ba$ is aided by the fact that the order placement of
the inverse of an element $a$ is completely determined by the order
placement of $a$.
\end{examples}



\begin{theorem}\label{T:tstsubcom}
\index{model completion!submodel complete}%
Let $\tee$ and $\tst$ be theories of the language $\lan$ such that 
$\tee$ is almost universal and $\tst$ is the model completion of $\tee$.
Then $\tst$ is submodel complete.
\end{theorem}

\begin{proof}  We show that condition (2) of Theorem \ref{T:subcom} is
satisfied.  Let $\mb$ and $\mc$ be models of $\tst$ with $\ma$ a
submodel of
both $\mb$ and $\mc$; we will show that $\mb_\ba \equiv \mc_\ba$.

Now $\theory \seq \tstar$ so $\bmt$ and $\cmt$.  Since $\tee$ is almost
universal there are models $\md$ and $\me$ of $\tee$ such that $\ma
\seq \md
\seq \mb$, $\ma \seq \me \seq \mc$ and $\md_\ba \cong \me_\ba$.  So
$\mb_\bd \models \tstar \cup \tria D$ and $\mc_\be \models \tstar \cup
\tria E$.

Now $\mb_\bd$ is a model for the language $\lan_\bd$ whereas $\mc_\be$
is
a model for $\lan_\be$.  We wish to obtain a model $\mc'$ for $\lan_\bd$
which ``looks exactly like'' $\mc_\be$.  We just let $\bc'$ be $\bc$
and in
fact let $\mc' | \lan_\ba = \mc_\be | \lan_\ba$.  The interpretation of a
constant symbol $c_d \in \lan_\bd \setminus \lan_\ba$ is the
interpretation of $c_e \in \lan_\be \setminus \lan_\ba$ in $\mc_\be$ where
the isomorphism $\md_\ba \cong \me_\ba$ takes $d$ to $e$.

Now $\md \models \theory$ and since $\tst$ is the model completion of
$\tee$,
$\theory^{\ast} \cup \tria D$ is complete.  The isomorphism $\md_\ba \cong
\me_\ba$ ensures that $\mc' \models \tstar \cup \tria D$.  So $\mb_\bd
\equiv \mc'$.  Hence $\mb_\bd | \lan_\ba \equiv \mc'| \lan_\ba$; that is,
$\mb_\ba \equiv \mc_\ba$.

\end{proof}

The way to show that DLO, ACF and RCF admit elimination of quantifiers is
now clear: first use Theorem \ref{T:subcom} and Theorem \ref{T:tstsubcom}. They reduce our task to showing that DLO, ACF and RCF are the model completions of LOR, FLD and ORF respectively.  
To do this we use Theorem~\ref{T:modcomp};
we will show that each pair of theories satisfies both conditions (1) 
and (2) of Theorem \ref{T:modcomp}.
We begin with condition (1): if $\amt$ then there is a $\mb \models
\tstar$ such that $\ma \seq \mb$.

The case $\theory = \mbox{LOR}$ and $\tstar = \mbox{DLO}$ is easy;
every linear order can be enlarged to a dense linear order without
endpoints by judiciously placing copies of the rationals into the linear
order.

The case $\theory = \mbox{FLD}$ and $\tstar = \mbox{ACF}$ is just the well
known fact that every field has an algebraic closure.

The case $\theory = \mbox{ORF}$ and $\tstar = \mbox{RCF}$ is just
Lemma~\ref{L:ofrcf}.

So all that remains of the quest to prove elimination of quantifiers
for DLO, ACF and RCF is to verify condition (2) of
Theorem~\ref{T:modcomp} in each of these cases. At this point the reader may already be able to verify this condition for one or more of the pairs 
$\theory = \mbox{LOR}$ and $\tstar = \mbox{DLO}$,
$\theory = \mbox{FLD}$ and $\tstar = \mbox{ACF}$, or 
$\theory = \mbox{ORF}$ and $\tstar = \mbox{RCF}$.  
However the remainder of this chapter is devoted to a uniform method.



\begin{definition}
\index{realize}%
 Let $\lan$ be a language and $\sv$ a set of formulas
of 
$\lan$ in the free variable $v_0$. A model $\ma$ for $\lan$ is said to 
\emph{realise} $\sv$ whenever there is some $a \in \mathbf A$ such that 
$\amodphi [ a] $ for each $\varphi (v_0) $ in $\sv$.

\end{definition}

\begin{definition}
\index{type}%
 The set of formulas $\sv$ in the free variable $v_0$,  is said to be a
\emph{type}
of the model $\ma$ whenever 
\begin{itemize}
\item[(1)] every finite subset of $\sv$ is realised by $\ma$
\item[(2)] $\sv$ is maximal with respect to (1).
\end{itemize}
\end{definition}

%end of page 29 page 30 begins


\begin{rem} Every set of formulas $\Sigma (v_0)$ having property (1) of
the definition of type can be enlarged to also have property (2).
\end{rem}


\begin{lemma}\label{L:type} Suppose  $\ma$ is a model for a language $\lan$. 
Let $X  \seq \mathbf A$ and let $\sv$ be a type of $\ma_X$ in the language
$\lan_X$.
Then there is a $\mb$ such that 
$\ma \prec \mb$ and $\mb_X$ realises $\sv$.
\end{lemma}

\begin{proof} Let $\theory  = \Th \ma_\ba  \cup \sv[c] $ where $c$ is
a 
new constant symbol and  $\sv[c] =  \{ \varphi ( c ) : \varphi \in \sv \}$ 
and of course $\varphi ( c )$ is 
$\varphi (v_0 )$ with $c$ replacing $v_0$.

By the definition of type, for each finite $\theory' \seq \theory$, there is 
an expansion $\ma'$ of $\ma$ such that $\ma' \models \theory'$. 
The Compactness Theorem and the Elementary Diagram Lemma will complete
the proof.

\end{proof}

\begin{lemma}\label{L:Type}  Suppose $\ma$ is a model for a language
$\lan$.  There is a model $\mb$ for $\lan$ such that $\ma \prec \mb$
and $\mb_\ba$ realises each type of $\ma_\ba$ in the language
$\lan_\ba$.

\end{lemma}

\begin{proof} Let $\{ \Sigma_\alpha ( v_0 ) : \alpha \in I \}$
enumerate all types of $\ma_\ba$ in the language $\lan_\ba$.  For each
$\alpha \in I$ introduce a new constant symbol $c_\alpha$ and let
\[\Sigma_\alpha ( c_\alpha ) = \{ \vp (c_\alpha ) : \vp \in
\Sigma_\alpha (v_0) \}.\]  Let $\Sigma = \cup \{ \Sigma_\alpha (
c_\alpha ) : \alpha \in I \}$. Let $\Sigma' \seq \Sigma$ be any finite
subset. 

\begin{claim}  $\Sigma' \cup \Th \ma_\ba$ is satisfiable for the
language $\lan_\ba \cup \{ c_\alpha : \alpha \in I \}$.
\end{claim}

\begin{proof}[Proof of Claim]  Let $\Sigma_{\alpha_1} (v_0), \dots ,
\Sigma_{\alpha_n}(v_0)$ be finitely many types such that \[ \Sigma'
\seq \Sigma_{\alpha_1}(c_0) \cup \Sigma_{\alpha_2} (c_1)\cup \dots \cup
\Sigma_{\alpha_n}(c_{\alpha_n}). \]
By Lemma \ref{L:type} there is a model $\ma_1$ such that $\ma \prec
\ma_1$ and $(\ma_1)_\ba$ realises $\Sigma_{\alpha_1} (v_0)$.  Using
Lemma~\ref{L:type} repeatedly, we can obtain \[ \ma \prec \ma_1 \prec
\ma_2 \prec \dots \prec \ma_n \]
such that each $(\ma_j)_\ba$ realises $\Sigma_{\alpha_j}(v_0)$.

Now $\ma \prec \ma_n$ so $(\ma_n )_\ba \models \Th \ma_\ba$.  It is
easy to check that since each $\ma_j \prec \ma_n$, $\ma_n$ realises
each $\Sigma_{\alpha_j}(v_0)$ and furthermore so does $(\ma_n)_\ba$.
So we can expand $(\ma_n)_\ba$ to the language $\lan_\ba \cup \{
c_{\alpha_1}, \dots , c_{\alpha_n} \} $ to satisfy $\Sigma' \cup \Th
\ma_\ba$.

\renewcommand{\qedsymbol}{}
\end{proof}

By the claim and the Compactness Theorem, there is a model $\mc \models
\Sigma \cup \Th \ma_\ba$.  By the Elementary Diagram Lemma, $\ma$ is
elementarily embedded into $\mc | \lan$, the restriction of $\mc$ to
the language $\lan$.  Therefore there is a model $\mb$ for $\lan$ such
that $\ma \prec \mb$ and $\mb_\ba \cong \mc | \lan_\ba$.  It is now
straightforward to check that $\mb_\ba$ realises each type
$\Sigma_\alpha (v_0)$.

\end{proof}

\addcontentsline{toc}{section}{Saturated models}
\begin{definition}
\index{saturated!$\kappa$-saturated model}%
 A model $\ma$ for $\lan$ is said to be
\emph{$\kappa$-saturated } whenever we have that for each $X \seq
\mathbf A$ with  $|X| < 
\kappa$, $\ma_X$ realises each type of $\ma_X$.
\end{definition}


Recall that for any set $X$ we denote by $|X|$ the cardinality of $X$. 
The notation $\kappa^+$ is used for the cardinal number just larger than 
the cardinal $\kappa$.  So a model $\ma$ will be $\kappa^+$-saturated whenever
we have that for each $X \seq \ba$ with $|X| \leq \kappa$, $\ma_X$
realises each type of $\ma_X$.  In particular, if $B$ is any set, 
$\ma$ will be $|B|^+$-saturated whenever we have that for each 
$X \seq \ba$ with $|X| \leq |B|$, $\ma_X$ realises each type of $\ma_X$.



\begin{rem}  A model $\ma$ is said to be \emph{saturated} whenever it is
$| \ba |$-saturated, where $| \ba |$ is the size of the universe of $\ma$.
For example, $\langle \mathbb{Q} , \pmb{<} \rangle$ is saturated; to
prove
this let $X$ be a finite subset of $\rat$ and let $\Sigma (v_0)$ be a
type of $\langle \rat , \pmb{<} \rangle_X$.  By Lemma~\ref{L:type}
and the Downward L\"{o}wenheim-Skolem Theorem get a countable $\mb$ such
that $\langle \rat , \pmb{<} \rangle_X \prec \mb_X$ and $\mb$ realises
$\Sigma (v_0)$.  Use the hint for Exercise~\ref{X:cat} to show
that $\langle \rat , \pmb < \rangle_X \cong \mb_X$ and then note that
this means that $\Sigma (v_0)$ is realised in $\langle \rat , \pmb <
\rangle_X$.
\end{rem}

\begin{lemma}\label{L:vaught}  (R. Vaught)\\
Suppose $\mc$ is an infinite model for $\lan$ and $\bb$ is an infinite
set. There is a $|\bb|^+$-saturated model $\md$ such that $\mc \prec \md$.
\end{lemma}

\begin{proof}  We build an elementary chain \[ \mc = \mc_0 \prec \mc_1
\prec \mc_2 \prec \dots \prec \mc_n \prec \cdots \quad n \in \nat \]
such that for each $n \in \nat$ $(\mc_{n+1})_{\bc_n}$ realises each
type of $(\mc_n)_{\bc_n}$.  This comes immediately by repeatedly
applying Lemma~\ref{L:Type}.  Let $\md$ be the union of the chain; the
Elementary Chain Theorem assures us that $\mc \prec \md$ and indeed
each $\mc_n \prec \md$. This means that for each $n \in \mathbb{N}$, 
each type of $\md_{\bc_{n}}$ is realised in $\md_{\bc_{n}}$.

Let $X \seq \bd$ with $|X| \leq |\bb|$ and let $\Sigma ( v_0 )$ be a
type of $\md_X$.  If $X \seq \bc_n$ for some $n$, $\Sigma (v_0)$ can be 
enlarged to a type of $\md_{\bc_n}$ which is realised in $\md_{\bc_n}$.
Since $\Sigma ( v_0 )$ involves only constant symbols associated with
$X$, we have that $\md_X$ realises $\Sigma ( v_0 )$. 

We have \emph{almost} proved that $\md$ is $|\bb|^+$-saturated, but not
quite, because there is no guarantee that if \[ X \seq \bd = \cup \{
\bc_n : n \in \nat \} \mbox{\ \ and \ } |X| \leq |\bb | \]
then $X \seq \bc_n$ 
for some $n$.  There is no problem when $X$ is finite.  The problem with infinite $X$ is that the
elementary chain may not be long enough to catch $X$.

The solution is to upgrade the notion of an elementary chain to include
chains which are indexed by any well ordered sets, not just the natural
numbers.  We sketch the appropriate generalisation of the above
argument from the case of $\langle \nat , \pmb{<} \rangle$ to the case
of an arbitrary well ordered set $\langle I , < \rangle$ with least
element $0$. 

We construct an elementary chain of models \[ \mc = \mc_0 \prec \dots
\prec \mc_\beta \prec \dots \quad \beta \in I \] recursively as
follows.  At stage $\beta$, suppose we have already constructed
$\bc_\alpha$ for each $\alpha \in I$ with $\alpha < \beta$.  The union
of the chain up to $\beta$ \[ \me = \cup \{ \mc_\alpha : \alpha \in I
\mbox{ and } \alpha < \beta \} \] falls under the scope of an upgraded
Elementary Chain Theorem (which is proved exactly as
Theorem~\ref{T:tec})
and so $\mc_\alpha \prec \me$ for each $\alpha \in I$ with $\alpha <
\beta$. We now use Lemma~\ref{L:Type} to get $\mc_\beta$ such
that $\me \prec \mc_\beta$ and $(\mc_\beta )_\be$ realises each type of
$\me_\be$.

As before, let $\md = \cup \{ \mc_\alpha : \alpha \in I \}$ be the
union of the entire chain and by the upgraded Elementary Chain Theorem
$\mc \prec \md$.  Also as before, $\md_X$ realises each type of $\md_X$
for each $X \seq \bd$ such that $X \seq \bc_\alpha$ for some $\alpha
\in I$.  

We can now complete the proof of the lemma by choosing our well
ordered set $\langle I , < \rangle$ long enough so that if \[ X \seq
\bd = \cup \{ \bc_\alpha : \alpha \in I \}  \mbox{\ \ and \ }|X| \leq |\bb| \]
then there is some $\alpha \in I$ such that $X \seq \bc_\alpha$.  Such a
well ordered set is well known to exist --- for example, any ordinal
with cofinality $> |\bb|$.

\end{proof}

\begin{definition}
\index{simple extension}%
 We say that $\mb$ is a \emph{simple extension} of $\ma $ whenever 
\begin{enumerate}
 \item $\ma \seq \mb$ and 
\item there is some 
$b \in \bb$ such that no smaller submodel of $\mb$ contains $\ba 
\cup \{ b\}$.

\end{enumerate}
\end{definition}

\addcontentsline{toc}{section}{Blum's Test}
\begin{theorem}\label{T:blum} (Blum's Test)\\
\index{Blum's Test}%
Suppose $\theory \seq \theory^{\ast}$ are theories of a language $\lan$.  
Suppose further that:
\begin{itemize}
\item[(1)] $\theory$ is an almost universal theory,
\item[(2)] for each $\ma \models \theory$ there is a 
$\mb \models \tstar$ with $\ma \seq \mb$, and  
\item[(3)] for each $\amt$ and each simple extension $\mb$ of $\ma$ which  
is a submodel of a model of $\tee$, and for each $\mc
\models \theory^{\ast}$ with $\ma \seq \mc$ such that
$\mc$ is  $|\bb|^{+} $-saturated, there is an isomorphic 
embedding $f:\mb \to \mc$ such that $f \! \upharpoonright \! \ba$
is the identity on $\ba$.
\begin{flushleft} Then:
\end{flushleft}
\item[(4)]  $\tst$ is the model completion of $\tee$,
\item[(5)]  $\tst$ is submodel complete, and
\item[(6)]  $\tst$ admits elimination of quantifiers.
\end{itemize} 
\end{theorem}

\begin{proof}  With  Theorems ~\ref{T:subcom}, ~\ref{T:modcomp} and 
~\ref{T:tstsubcom}, statements (4), (5) and (6) all follow from (1), (2) and 
condition (2) of Theorem \ref{T:modcomp}.
 
We will therefore only need to prove that
for each $\ma \models \theory$, $\mb \models \theory^{\ast}$
and $\mc \models \tstar$ such that $\ma \seq \mb$ and $\ma \seq \mc$ we
have a model $\md$ such that $\mb_\ba$ is isomorphically embedded into
$\md_\ba$ and $\mc \prec \md$,

Let $\ma$, $\mb$ and $\mc$ be as above.  Using Lemma~\ref{L:vaught} we
obtain a $|\bb|^+$-saturated model $\md$ such that $\mc \prec \md$. 
We wish to prove that $\mb _{A} $ is isomorphically embedded into $\md _{A} $.

Since $\ma \subseteq \md$, the following collection $\mathcal{E}$ of functions is nonempty:
	\[
     \{ e : \mbox{for some } \ma \subseteq \me \subseteq \mb \ \ e \colon \me _{A}  
\hookrightarrow \md _{A} \mbox{ is an isomorphic embedding} \}
	\]
and so has a maximal member $f$ in the sense that no other $e \in \mathcal{E}$ 
extends $f$. 
From $f \colon \mf _{A} \hookrightarrow \md _{A}$ and Exercise \ref{X:eeek} we get $\mg$ with $\mf \subseteq \mg$ and an isomorphism $g \colon \mg \rightarrow \md $ 
extending $f$.

\begin{claim}
$\mf \models \tee $
\end{claim}
\begin{proof}[Proof of Claim]
We have both $\mf \subseteq \mb$ and $\mf \subseteq \mg$. By condition (1), there are models $\mh$ and $\mj$ of $\tee$ with  
$\mf \subseteq \mh \subseteq \mb$ and $\mf \subseteq \mj \subseteq \mg$ 
such that $\mh _{\mathbf{F}} \cong \mj _{\mathbf{F}}$.
This gives an isomorphic embedding $h \colon \mh \hookrightarrow \mg$ such 
that $h \! \upharpoonright \! \mathbf{F}$ is the identity on $\mathbf{F}$.

The composition $g \circ h \colon \mh \hookrightarrow \md $ is an isomorphic embedding with the property that for all $x \in \mathbf{F}$:
	\[
            (g \circ h) (x) = g(x) = f(x).
	\]
By the maximality of $f$, $f = g \circ h$. Hence $\mf = \mh$ and 
$\mf \models \tee$, finishing the proof of the claim.
\renewcommand{\qedsymbol}{}
\end{proof}
\begin{claim}
$\mf = \mb $
\end{claim}
\begin{proof}[Proof of Claim]
If not, pick $b \in \bb \setminus \mathbf{F}$ and form the simple extension 
$\mf '$ of $\mf$ by $b$. Since $\mg \cong \md$, $\mg$ is also $|\bb |^{+} -$ saturated so that we can apply condition (3) to $\mf$, $\mf '$ and $\mg$. 
We obtain an isomorphic embedding $f' \colon \mf ' \hookrightarrow \mg$ 
such that $f' \! \upharpoonright \! \mathbf{F}$ is the identity on $\mathbf{F}$. 
But now $g \circ f'$ contradicts the maximality of $f$ and completes the proof of the claim.
\renewcommand{\qedsymbol}{}
\end{proof}
Therefore $f$ isomorphically embeds $\mb _{\ba}$ into $\md _{\ba}$.

\end{proof}

The following lemma completes the proofs that each of the theories DLO,
ACF and RCF admits elimination of quantifiers.



\begin{lemma} Each of the following three pairs of theories $\tee$ and
$\tst$ satisfy condition (3) of Blum's Test.
\begin{itemize}
\item[(1)] $\theory = LOR, $ theory of linear orderings.
$\theory^{\ast} =$ DLO, theory of dense linear orderings without
endpoints.
%
\item[(2)] $\theory =$ FLD, theory of fields. $\theory^{\ast} =$
ACF, theory of algebraically closed fields.
%
\item[(3)] $\theory =$ ORF, theory of ordered fields. $\theory^{\ast}
=$ RCF, theory of real closed ordered fields.

\end{itemize}

\end{lemma}

\begin{proof}[Proof of (1)] Let $\ma$ and $\mb$ be linear orders, with 
$\bb = \ba \cup \{ b \}$ and $\ma \seq \mb$. 

Let $\mc$ be a
$|\bb|^+$-saturated dense linear 
order without endpoints with $\ma \seq \mc$.
We wish to find an isomorphic embedding  $f: \mb \to \mc$ which is the
identity on $\ba$.

Consider a type of $\mc_ \ba $ containing the following formulas: \[ c_a 
< v_0 \mbox{ for each  } a \in \ba \mbox{ such that } a < b \]
\[ v_0 < c_a  \mbox{ for each } a \in \ba \mbox{ such that } b < a \]
Since $\mc$ is a dense linear order without endpoints each finite subset 
of the type can be realised in $\mc_ \ba$.

Saturation now gives some $t \in \bc$ realising this type.
We set $f(b) = t $ and we are finished.
\renewcommand{\qedsymbol}{}
\end{proof}


\begin{proof}[Proof of (2)] Let $\ma$  be a field and $\mb$ a 
simple extension of $\ma$ witnessed by $b$ such that $\mb$ is a
submodel of a field (a commutative semi-ring).

Let $\mc$ be a $|\bb|^+$-saturated algebraically closed field such that 
$\ma \seq \mc$.
We wish to find an isomorphic embedding $f: \mb \to \mc$ which is the 
identity on $\ma$.

There are two cases:
\begin{itemize}
\item[(I)] $b$ is algebraic over $\ma$,
\item[(II)] $b$ is transcendental over $\ma$.

\end{itemize}


\begin{proof}[Case(I)] Let $p$ be a polynomial with coefficients from
$\ba$ such that $p (b) =0$ but $b$ is not the root of any such
polynomial of lower degree.  Since $\mc$ is algebraically closed there
is a $t \in \bc$ such that $p (t) = 0$.  We extend the identity map
$f$ on $\ba$ to make $f(b) = t$.  We extend $f$ to the rest of $\mb$ by
letting $f(r(b)) = r(t)$ for any polynomial $r$ with coefficients from
$\ba$.  It is straightforward to show that $f$ is still a well-defined
isomorphic embedding.


\renewcommand{\qedsymbol}{}
\end{proof}


\begin{proof}[Case (II)] Let us consider a type of
$\mc_{\ba}$ containing 
the following set of formulas: 
\[ 
   \{ \neg (p(v_0) = 0) : p \text{ is a polynomial with coefficients in } 
   \{ c_a : a \in \ba \} \} 
\]

Since $\mc$ is algebraically closed, it is infinite and hence each finite 
subset is realised in $\mc_{\ba}$.
Saturation will now give some $t \in \bc$ such that $t$ realises the 
type. 

We set $f(b) = t$. Since $t$ is transcendental over $\ma$, the extension 
of $f$ to all of $\bb$ comes easily from the fact that every element of
$\bb \setminus \ba$ is the value at $b$ of some polynomial function
with coefficients from $A$. 
\renewcommand{\qedsymbol}{}
\end{proof}

\end{proof}

\begin{proof}[Proof of (3)] Let $\ma$  be an ordered field and 
$\mb$ be a simple extension of $\ma$ witnessed by $b$ such that $\mb$
is a submodel of an ordered field (an ordered commutative semi-ring).

Let $\mc$ be a $|\bb|^+$-saturated real closed field such that $\ma \seq 
\mc$.
We wish to find an isomorphic embedding $f: \mb \to \mc$ which is the
identity on $\ma$.

There are two cases:
\begin{itemize}
\item[(I)] $b$ is algebraic over $\ma$.
\item[(II)] $b$ is transcendental over $\ma$.
\end{itemize}

\begin{proof}[Case (I)] Since $b$ is algebraic over $\ma$ we have a
polynomial $p$ with coefficients in $\ba$ such that $p (b ) = 0$.  All
other elements of the universe of the simple extension $\mb$ are of the
form $q(b)$ where $q$ is a polynomial with coefficients in $\ba$.
Before beginning the main part of the proof we need some algebraic
facts.

\begin{claim}  Let $\md$ be a real closed ordered field and $q(x) $ be
a polynomial over $\md$ of degree $n$.  Then for any $e \in \md$ we
have: \[ q(x) = \sum_{m=0}^n \frac{q^{(m)} (e)}{m!} (x-e )^m \]
where $q^{(m)}$ stands for the polynomial which is the  m-th derivative
of $q$.
\end{claim}

\begin{proof}[Proof of Claim]  This is Taylor's Theorem
from Calculus; unfortunately we cannot use Calculus to
prove it because we are in $\md$, not necessarily the
reals $\mr$.  However the reader can check that the
Binomial Theorem gives the identity for the special cases
of $q (x) = x^n$ and that these special cases readily
give the full result.

\renewcommand{\qedsymbol}{}
\end{proof}

\begin{claim} Let $\md$ be a real closed ordered field
and $q(x)$ a polynomial over $\md$ with $e \in \bd$ and
$q(e) = 0$.  If there is an $a < e$ such that $q(x) > 0$
for all $a < x <e$  then $q'(e) \leq 0$. If there is an $a > e$ such
that $q(x) > 0$ for all $e < x < a $ then $q'(e) \geq 0$.  Here $q'$ is
the first derivative of $q$.

\end{claim}

\begin{proof}[Proof of Claim] From the previous claim we get 
\[ \frac{q(x) - q(e)}{x-e}  = q'(e) + (x - e) \left( \sum_{m=2}^n
\frac{q^{(m)}(e)}{m!} (x-e)^{m-2} \right) \]
for any $x \neq e$ in $\md$.  By choosing $x$ close enough to $e$ we
can ensure that the entire right hand side has the same sign as
$q'(e)$.  A proof by contradiction now follows readily.

\renewcommand{\qedsymbol}{}
\end{proof}

\begin{claim}  Let $\md$ be a real closed ordered field and $q(x)$ be 
a polynomial over $\md$ with $e \in \bd$ and $q (e) = 0$.  If $w$
and $z$ are in $\bd$ such that $w < e < z$ and $q(w) \cdot q (z) >
0$ then there is a $d$ in $\bd$ such that $w < d < z$ and $q' (d)
=0$.
\end{claim}

\begin{proof}[Proof of Claim]  Without loss of generosity $q (w) >
0$ and $q(z) > 0$. Since $q$ has only finitely many roots, we can
pick $d_1$ to be the least $x$ such that $w < x \leq e$ and $q (x)
=0$.  Since $q(x) \neq 0$ for all $w < x < d_1$, the Intermediate
Value Property of Real Closed Ordered Fields shows that $q$ cannot
change sign here and so $q(x) > 0$ for all $w < x < d_1$.  By the
previous claim, $q'(d_1) \leq 0$.  A similar argument with $z$ shows
that there is a $d_2$ such that $e \leq d_2 < z$ and $q' (d_2) \geq
0$.  If $d_1 = e = d_2$ take $d =e$.  If $d_1 < d_2$ the
Intermediate Value Property gives a $d$ with the required
properties.

\renewcommand{\qedsymbol}{}
\end{proof}

\begin{claim} Let $\md$ be a real closed ordered field with an
ordered field $\me \seq \md$.  Let $f: \me \to \mc$ be an isomorphic
embedding into a real closed ordered field.  Let $q$ be a polynomial
with coefficients in $\be$ such that $\{ x \in \bd : q' (x) = 0 \}
\seq \be$.  Let $d \in \bd \setminus \be$ be such that $q(d) =0$ but
$d$ is not a root of a polynomial with coefficients from $\be$ which
has lower degree.  Then $f$ can be extended over  the
subfield of $\md$ generated by $\be \cup \{ d\}$.

\end{claim}

\begin{proof}[Proof of Claim]  Since the finitely many roots of $q'$
from $\bd$ actually lie in $\be$, we can get $e_1$ and $e_2$ in $\be$
such that $e_1 < d < e_2$ and $q'(x) \neq 0$ for all $x$ in $\bd$
such that $e_1 < x < e_2$.  Furthermore for all $x$ in $E$ we have
$q(x) \neq 0$.  We can now apply the previous claim to get that
$q(w) \cdot q(z) < 0$ for all $w$ and $z$ in $\be$ such that $e_1 <
w < d < z < e_2$.

We now move to the real closed ordered field $\mc$ and the
isomorphic embedding $f$.  For each $w$ and $z$ in $\be$ such that
$e_1 < w < d < z < e_2$ we have $f(w) < f(z)$ and $q(f(w)) \cdot
q(f(z)) < 0$.  By the Intermediate Value property of $\mc$ we get, for
each such $w$ and $z$,  a
$y \in \bc$ such that $f(w) < y < f(z)$ and $q(y) =0$.  Since $q$
has only finitely many roots there is some $t \in \bc$ such that $q
(t) = 0$, $f(w) < t$ for all $e_1 < w < d$ and $t < f(z)$ for all $d
< z < e_2$.

We now extend $f$ by letting $f(d) = t$ and $f(r(d)) =r(t)$ for any
polynomial $r$ with coefficients from $\be$.  It is straightforward
to check that the extension is a well-defined isomorphic embedding
of the simple extension of $\me$ by $d$ into $\mc$.  We use the fact
that ORF is almost universal to extend the isomorphic embedding to
all of the subfield of $\md$ generated by $\be \cup \{ d \}$, since
\index{almost universal}%
we can rephrase the definition of almost universal as
follows: \begin{quotation} Whenever $\mc \models \tee$, $\md \models
\tee$, $\me' \seq \md$  and
$f: \me' \hookrightarrow \mc$ is an isomorphic embedding there is
a model $\me'' \models \tee$ such that $\me' \seq \me'' \seq \md$ and
$f$ extends over
$\me''$.
\end{quotation}


\renewcommand{\qedsymbol}{}
\end{proof}


It is now time for the main part of the proof of this case. Using
Lemma~\ref{L:ofrcf},  let
$\md$ be a real closed ordered field with $\mb \seq \md$.
We have a polynomial $p$ with coefficients from $\ba$ such that
$p(b) =0$.   By induction on the degree of $p$, we can show
that there is a sequence of elements $\dnot m = b$ of elements of
$\md$, a sequence of subfields of $\md$: \[ \ma = \me_0 \seq \me_1
\seq \dots \seq \me_{m+1} \] with each $d_j \in \be_{j+1} \setminus
\be_j $ and corresponding isomorphic embeddings
 \[f_j : \me_j \to \mc\]
coming from the previous claim and having the property that $f_0$ is
the identity and $f_{j+1}$ extends $f_j$.  In this way we extend the
identity map $f_0 : \ma_0 \hookrightarrow \mc$ until we reach
$f_{m+1} : \me_{m+1} \hookrightarrow \mc$.  We then note that since
$b \in \me_{m+1} $ we have $\mb \seq \me_{m+1}$ and we are finished.

\renewcommand{\qedsymbol}{}
\end{proof}


\begin{proof}[Case (II)] Let us consider a type of $\mc_\ba $ containing 
the following formulas: 
\[ c_a < v_0 \mbox{ for all } a \in \ba \mbox{ with } a < b \]
\[v_0 < c_a \mbox{ for all } a \in \ba \mbox{ with }b < a \]
\[ \neg (p ( v_0 ) = 0) \mbox{ for all polynomials } p \mbox{ with 
coefficients in  } \{c_a : a \in \ba\} \]

Since each interval of $\mc$ is infinite, each finite subset of this type 
is realised by $\mc_ \ba $.
Saturation now gives $t \in \bc$ which realises this type. We put $f(b)
= t $. 

We can now extend $f$ on the rest of $\bb \setminus \ba$, since 
each such element is the value at $b$ of a polynomial function  with
coefficients from 
$\ba$.
\renewcommand{\qedsymbol}{}
\end{proof}
\end{proof}

%end of page 37

%tangorra



%\backmatter
\bibliographystyle{amsplain}
\bibliography{Model_theory}
\nocite{*}

\printindex


\end{document}