\documentclass[twoside,a4paper,12pt,draft]{article}
%\documentclass[draft]{amsart}
\usepackage{amssymb,amsmath,amsthm}
\usepackage{amscd}     % commutative diagram
%\usepackage{fullpage}
%\setlength{\parindent}{0pt}
%\setlength{\parskip}{1ex plus 0.5ex minus 0.2ex}
\title{Model-Theory to Compactness}
\author{David Pierce}
%\address{Department of Mathematics \\
%Middle East Technical University\\Ankara, Turkey}
%\email{pierced@member.ams.org}
%\subjclass{}
\date{\today}
\pagestyle{myheadings}
 \markboth{Model-Theory to Compactness}{David Pierce, \today}

\newcommand{\Z}{\mathbf Z}          % the integers
\newcommand{\Q}{\mathbf Q}          % the rationals
%\newcommand{\A}{\mathbf A}          % affine space
\newcommand{\R}{\mathbf R}          % the reals
\newcommand{\N}{\mathbf{N}}         % the naturals

%I don't like the standard loose inequalities
\renewcommand{\leq}{\leqslant}
\renewcommand{\nleq}{\nleqslant}
\renewcommand{\geq}{\geqslant}

%I don't much like the standard here either:
\renewcommand{\setminus}{-}

%I don't want epsilon to look like `is an element of'
\renewcommand{\epsilon}{\varepsilon}

\newcommand{\To}{\longrightarrow}

\newcommand{\mapset}[2]{#2^{#1}}

\newcommand{\Mod}{\mathfrak{Mod}}
\DeclareMathOperator{\Th}{Th}
\newcommand{\pow}{\mathcal{P}}
\newcommand{\K}{\mathcal{K}}
\newcommand{\arity}[1]{\textrm{arity}(#1)}
\newcommand{\proj}{\pi}
\newcommand{\inv}{^{-1}}
\newcommand{\Fm}[1]{\textrm{Fm}^{#1}}
\newcommand{\Fmo}[1]{\textrm{Fm}^{#1}_0}
\newcommand{\2}{\mathbf{F}_2}

\newcommand{\abs}[1]{\lvert#1\rvert}
\newcommand{\elsub}{\preccurlyeq}
\newcommand{\Ba}{\mathcal{M}^\mathrm{a}}  % a Boolean algebra
\newcommand{\Br}{\mathcal{M}^\mathrm{r}}  % a Boolean ring

\DeclareMathOperator{\diag}{diag}   % Robinson diagram of a structure

\DeclareMathOperator{\sgn}{sgn}     % signum of a permutation

\newcommand{\included}{\subseteq}   % the name suggests the meaning here
\newcommand{\lang}{\mathcal L}      % a language
\newcommand{\SL}{\mathrm{PL}}       % Propositional (was sentential) logic
\newcommand{\pairing}[1]{\langle#1\rangle} % pairing

\newtheorem*{theorem}{Theorem}
\newtheorem*{lemma}{Lemma}
\newtheorem*{corollary}{Corollary}

\theoremstyle{remark}
\newtheorem*{remark}{Remark}
\newtheorem*{example}{Example}
\newtheorem*{examples}{Examples}

%  For distinguishing claims made and proved within proofs
%\newtheoremstyle{subclaim}{0pt}{0pt}{\itshape}{}{\bfseries}{}{0em}{}
%\theoremstyle{subclaim}
%\newtheorem*{claim}{}

\newcommand{\tuple}{\mathbf}
\newcommand{\reduct}{\overline}

%  Should the word `modulo' be italicized?
\newcommand{\modulo}{\emph{modulo}\ }

%  To distinguish terms being defined
\newcommand{\defn}[1]{{\bf#1}}

\begin{document}
%\begin{abstract}
%Some notes on the basics of model theory.
%\end{abstract}

\maketitle
\tableofcontents
\newpage

\setcounter{section}{-1}

\section{Introduction}

These notes are an attempt to develop model theory, as economically as
possible, on a foundation of some familiarity with algebraic structures.
References include \cite{Chang--Keisler}, \cite{Hodges} and
\cite{Poizat}.

\section{The natural numbers}

By one standard definition, the set $\omega$ of \defn{natural numbers} is
the smallest set that contains the empty set and that contains
$x\cup\{x\}$ whenever it contains $x$.  The empty set will be denoted $0$
here, and $x\cup\{x\}$, the \defn{successor} of $x$, can be denoted $x'$.
The triple $(\omega,{}',0)$ will turn out to be an example of a
\emph{structure}.

Throughout these notes, $n$ will be a natural number, understood as the
set $\{0,1,2,\dots,n-1\}$, possibly empty; and $i$ will range over the
elements of this set.  Also $m$ will be a natural number.

\section{Cartesian powers}

Let $M$ be a set.  The \defn{Cartesian power} $M^n$ is the set of
functions from $n$ to $M$.  Such a function will be denoted by a boldface
letter, as $\tuple a$, but then its value $\tuple a(i)$ at $i$ will be
denoted $a_i$.  The function $\tuple a$ can be identified with the
\defn{$n$-tuple} $(a_0,\dots,a_{n-1})$ of its values.

In particular, the power $M^0$ has but a single member, $0$; hence
$M^0=1$.  This is so, even if $M=0$; however, $0^n=0$ when $n$ is
\emph{positive} (different from $0$).  The set $M$ itself can be
identified with the power $M^1$.

Any function $f:m\to n$ determines the map
\begin{equation*}
\tuple a\mapsto(a_{f(0)},\dots,a_{f(m-1)}):M^n\to M^m,
\end{equation*}
no matter what set $M$ is.  In case $m=1$, we have the \defn{coordinate
projections} $\tuple a\mapsto a_i$.

The \defn{Cartesian product} $A\times B$ of sets $A$ and $B$ is
identified with the set of (ordered) pairs $(a,b)$ such that $a\in A$ and
$b\in B$.  There is a map
\begin{align*}
  M^n\times M^m & \To M^{n+m} \\
  (\tuple a,\tuple b) & \longmapsto(a_0,\dots,a_{n-1},b_0,\dots,b_{m-1}),
\end{align*}
often considered an identification.


\section{Structures and signatures}

A \defn{function on} the set $M$ is a map $M^n\to M$; the function then
is \defn{$n$-ary}---its \defn{arity} is $n$.  A nullary (that is,
$0$-ary) function is a \defn{constant} and can be identified with an
element of $M$.

An \defn{$n$-ary relation on} $M$ is a subset of $M^n$.  There are two
nullary relations, namely $0$ and $1$.  The relation of \emph{equality}
is binary ($2$-ary).

A \defn{structure} is a set equipped with some distinguished constants
and with some functions and relations of various positive arities. The
set then is the \defn{universe} of the structure.  If the universe is
$M$, then the structure might be denoted $\mathcal M$ or just $M$ again.
However, the structure $(\omega,{}',0)$ is denoted $\N$.  (This structure
is often considered to contain the binary functions of addition and
multiplication as well, but these are uniquely determined by the
successor-function.)

\begin{examples}
A set with no distinguished relations, functions or constants is
trivially a structure.  Groups, rings and partially ordered sets are
structures. A vector space is a structure whose unary functions are the
multiplications by the scalars. A valued field can be understood as a
structure when the valuation ring is distinguished as a unary relation.
\end{examples}

The \defn{signature} of a structure contains a \defn{symbol} for each
function, relation and constant in the structure; the function, relation
or constant is then the \defn{interpretation} of the symbol.
Notationally, the symbols are primary; their interpretations can be
distinguished, if need be, by superscripts indicating the structure.

\begin{examples}
The complete ordered field $\R$ has the signature $\{+, -, \cdot, \leq,
0, 1\}$.  The ordered field $\Q$ of rational numbers has the same
signature.  The binary function-symbol $+$ is interpreted in $\R$ by
addition of real numbers; the interpretation is also denoted by $+$, or
by $+^{\R}$ if it should be distinguished from addition $+^{\Q}$ of
rational numbers.  To make its signature explicit, we can write $\R$ as
the tuple $(\R, +, -, \cdot, \leq, 0, 1)$.
\end{examples}

Throughout these notes, $\lang$ will be a signature, and $f$, $R$ and $c$
will range respectively over the function-, relation- and
constant-symbols in $\lang$.  The structures with signature $\lang$
compose the class $\Mod(\lang)$.

\section{Homomorphisms and embeddings}

Suppose $M$ and $N$ are in $\Mod(\lang)$, and $h$ is a map $M\to N$. (So,
$N$ must be nonempty, unless $M$ is empty.)  Then $h$ induces maps
$M^n\to N^n$ in the obvious way, even when $n=0$; so, $h(\tuple
a)(i)=h(a_i)$, and $h(0)=0$.  The map $h$ is a
\defn{homomorphism} if it \emph{preserves} the functions,
relations and constants symbolized in $\lang$, that is,
\begin{itemize}
\item
$h(f^M(\tuple a))=f^N(h(\tuple a))$;
\item
$h(\tuple a)\in R^N$ when $\tuple a\in R^M$;
\item
$h(c^M)=c^N$.
\end{itemize}
Any map preserves \emph{equality}.  A homomorphism is an
\defn{embedding} if it preserves
both inequality and the complements of the relations symbolized in
$\lang$.

\begin{examples}
A group-homomorphism is a homomorphism of groups; a group-mono\-morphism
is an embedding of groups.  The zero-map on the ordered field $\R$ can be
seen as a homomorphism, but not an embedding.  (It would not even be a
homomorphism if the signature of an ordered ring contained $<$ instead of
$\leq$.)
\end{examples}

\section{Boolean algebras}

An essential and notationally exceptional example is the
\emph{Boolean algebra} of subsets of a nonempty set $\Omega$; this
structure is the tuple
\begin{equation*}
  (\pow(\Omega),\cap,\cup,{}^c,\emptyset,\Omega),
\end{equation*}
but we shall consider the signature of Boolean algebras to be the
set
\begin{equation*}
  \{\land,\lor,\lnot,0,1\}.
\end{equation*}
A \defn{Boolean ring} is a (unital) ring in which every element is
idempotent, that is, satisfies
\begin{equation*}
  x^2=x.
\end{equation*}
In particular, in such a ring we have $(x+y)^2=x+y$, whence
\begin{equation*}
  xy+yx=0;
\end{equation*}
replacing $y$ with $x$, we get $2x=0$, so every element is its
additive inverse; hence also $xy=yx$, so the ring is commutative.
We have $x(1+x)=0$, so if $x$ is a unit, then $1+x=0$, so $x=1$.
Thus also every nonzero nonunit of a Boolean ring is a
zero-divisor. Hence the only Boolean integral domain is the
two-element ring $\{0,1\}$ or $\2$, and this is a field. Therefore
prime ideals of Boolean rings are maximal, since the quotient of a
Boolean ring by an ideal is Boolean.

A structure $(M,\land,\lor,\lnot,0,1)$---call it $\Ba$---in the signature
of Boolean algebras determines a structure $\Br$ with the same universe
in the signature of rings:  This structure $\Br$---that is,
$(M,+,\cdot,0,1)$---is given by the rules
\begin{align*}
  x+y & =(x\land\lnot y)\lor(y\land\lnot x), \\
  x y & =x\land y
\end{align*}
and the rule that $0$ and $1$ have the same interpretation in each
structure. The structure $\Ba$ is a \defn{Boolean algebra} just in case
$\Br$ is a Boolean ring.  Any Boolean ring $(M,+,\cdot,0,1)$ is
determined in this way by the Boolean algebra $(M,\land,\lor,\lnot,0,1)$
such that
\begin{align*}
  x\land y & = x y, \\
  x\lor y & =x+y+xy, \\
  \lnot x & =1+ x.
\end{align*}
A Boolean algebra has a partial order $\leq$ such that
\begin{equation*}
  x\leq y\iff x\land y=x.
\end{equation*}

An \defn{ideal} of a Boolean algebra is just an ideal of the
corresponding ring.  A \defn{filter} of a Boolean algebra is
\emph{dual} to an ideal, so $F$ is a filter just in case $\{\lnot
x:x\in F\}$ is an ideal.  An \defn{ultrafilter} is dual to a
maximal ideal.  So, $F$ is a filter just in case
\begin{align*}
  & 1\in F,\\
  & x,y\in F\implies x\land y\in F, \\
  & x\in F \text{ and } x\leq y\implies y\in F, \\
  & 0\notin F;
\end{align*}
also, a filter $F$ is an ultrafilter just in case
\begin{equation*}
  x\lor y\in F \implies x\in F\text{ or } y\in F,
\end{equation*}
equivalently, $x\notin F\implies \lnot x\in F$.

The set of ultrafilters of a Boolean algebra is the \defn{Stone-space} of
the algebra.  For every element $x$ of a Boolean algebra, the
corresponding Stone-space has a subset $[x]$ comprising the ultrafilters
containing $x$.  Then
\begin{equation*}
  [x]\cap[y]=[x\land y]
\end{equation*}
since the elements of these sets are filters; since they are
ultrafilters, we have also
\begin{align*}
  [x]\cup[y] & =[x\lor y], \\
  [x]^c & =[\lnot x].
\end{align*}
Finally, $[1]$ is the whole Stone-space, and $[0]$ is empty.  Therefore
the map
\begin{equation*}
  x\longmapsto[x]
\end{equation*}
is a homomorphism of Boolean algebras; it is an embedding, since $[x]$ is
nonempty when $x\neq0$.

Since the collection of sets $[x]$ contains the whole Stone-space and the
empty set and is closed under finite unions, it is a \defn{basis} for the
\defn{closed} sets of a \defn{topology} for the Stone-space.  By definition then,
every closed subset is an intersection of some closed sets $[x]$.  These
basic closed sets are also open---they are \defn{clopen}.  The topology
is \defn{Hausdorff}, since distinct points are respectively contained in
some disjoint sets $[x]$ and $[\lnot x]$.

Suppose $B$ is a subset of a Boolean algebra.  Then the following are
equivalent:
\begin{itemize}
  \item
  the collection $\{[x]:x\in B\}$ has the \defn{finite-intersection
  property}, meaning any finite sub-collection has nonempty intersection;
  \item
  the set $B$ generates a filter of the algebra;
  \item
  $B$ included in an ultrafilter of this algebra;
  \item
  $\{[x]:x\in B\}$ has nonempty intersection.
\end{itemize}
That the first condition implies the last means that the topology of the
Stone-space is \defn{compact}.  Consequently, every clopen set is one of
the sets $[x]$.

Of the nonempty set $\Omega$, we can see the Boolean ring $\pow(\Omega)$
of its subsets as a compact \defn{topological ring}.  For, we can
identify any subset $A$ of $\Omega$ with its \defn{characteristic
function}, the map from $\Omega$ to $\2$ taking $x$ to $1$ just in case
$x\in A$.  The set of such maps can be denoted $\mapset{\Omega}{\2}$.
With the
\defn{discrete} topology, in which every subset is closed, $\2$ is a
compact topological ring.  Therefore on $\mapset{\Omega}{\2}$ is induced
a ring-structure and a compatible topology---the \defn{product}-topology
or topology of
\defn{pointwise convergence}, compact in this case since $\2$ is compact.
The induced ring-structure makes the bijection from $\pow(\Omega)$ to
$\mapset{\Omega}{\2}$ a homomorphism.  In the induced topology, every
finite subset of $\Omega$ determines for the zero-map on $\Omega$ an open
neighborhood, comprising those maps into $\2$ that are zero on that
finite subset.  Translating such a neighborhood by an element of
$\mapset{\Omega}{\2}$ gives an open neighborhood of that element, and
every open subset of $\mapset{\Omega}{\2}$ is a union of such
neighborhoods; the finite unions are precisely the clopen subsets.

\section{Functions and terms}

Suppose $M$ is in $\Mod(\lang)$.  Various functions on $M$ can be
derived, by composition, from:
\begin{itemize}
  \item
  the functions $f^M$,
  \item
  the constants $c^M$, and
  \item
  the coordinate projections.
\end{itemize}
These compositions can be described without reference to $M$; the result
is the \defn{terms} of $\lang$.

The \defn{interpretation} in $M$, or $t^M$, of an $n$-ary term $t$ of
$\lang$ will be an $n$-ary function on $M$.  Terms can be defined
precisely as follows:
\begin{itemize}
\item
Each constant-symbol $c$ is also an $n$-ary term whose interpretation is
the constant map $\tuple a\mapsto c^M$ on $M^{n}$.
\item
There is an $n$-ary term $x_i$ whose interpretation is the coordinate
projection $\tuple a\mapsto a_i$ on $M^n$.
\item
If $t_0$, \dots, $t_{n-1}$ are $m$-ary terms, and $f$ is $n$-ary, then
there is an $m$-ary term $f(t_0,\dots,t_{n-1})$ whose interpretation is
the map
\begin{equation*}
\tuple a\mapsto f^M(t_0^M(\tuple a),\dots, t_{n-1}^M(\tuple a)).
\end{equation*}
\end{itemize}
By this account, an $n$-ary term is also $n+1$-ary.  The nullary terms
are the \defn{constant} terms.

\begin{lemma}
If $t$ is an $n$-ary term, and $u_0$, \dots, $u_{n-1}$ are $m$-ary terms,
then there is an $m$-ary term whose interpretation in $M$ is the map
\begin{equation*}
\tuple a\mapsto t^M(u_0^M(\tuple a),\dots,u_{n-1}^M(\tuple a)).
\end{equation*}
\end{lemma}

The new term in the lemma can of course be denoted
$t(u_0,\dots,u_{n-1})$.

We can identify terms whose interpretations are indistinguishable in
every structure.  In particular, if $t$ is $n$-ary, but not $(n-1)$-ary,
then $t$ is precisely $t(x_0,\dots,x_{n-1})$, which we may abbreviate as
$t(\tuple x)$.

If $A$ is a subset of $M$, we let $\lang(A)$ be the signature $\lang$
augmented with a constant-symbol for each element of $A$.  The symbols
and the elements are generally not distinguished notationally, and an
$\lang$-structure $M$ naturally determines an $\lang(A)$-structure,
denoted $M_A$ if there is a need to distinguish.

\begin{lemma}
Every term of $\lang(A)$ is $t(\tuple a,\tuple x)$ for some term $t$ of
$\lang$ and tuple $\tuple a$ from $A$.
\end{lemma}

\section{Propositional logic}

The terms in the signature of Boolean algebras---the \defn{Boolean
terms}---can be considered as strings of symbols generated by the
following rules:
\begin{itemize}
  \item
  each constant-symbol $0$ or $1$ is a term;
  \item
  each symbol $x_i$ for a coordinate projection is a term;
  \item
  if $t$ and $u$ are terms, then so are $(t\land u)$ and $(t\lor
  u)$ and $\lnot t$.
\end{itemize}
A term here is $n$-ary just in case $i<n$ whenever $x_i$ appears in the
term.
Instead of $(\dots(t_0*t_1)*\dots*t_{n-1})$ we can write
\begin{equation*}
  t_0*\dots* t_{n-1},
\end{equation*}
where $*$ is $\land$ or $\lor$.

\begin{lemma}
Every $n$-ary function on $\2$ is the interpretation of an $n$-ary
Boole\-an term.
\end{lemma}

\begin{proof}
Suppose $f$ be an $n$-ary function on $\2$, and let $\tuple a^0$, \dots,
$\tuple a^{m-1}$ be the elements of $\mapset{n}{\2}$ at which $f$ is $1$.
If $m=0$, then $f$ is the interpretation of $0$.  If $m>0$, then $f$ is
the interpretation of
\begin{equation*}
  t^0\lor\dots\lor t^{m-1},
\end{equation*}
where $t^j$ is $u_0^j\land\dots u_{n-1}^j$, where $u_i^j$ is $x_i$, if
$a_i^j=1$, and otherwise is $\lnot x_i$.
\end{proof}

The Boolean terms can be considered as the \emph{propositional formulas}
composing a \emph{propositional logic}---call it $\SL$.  The
constant-symbols $0$ and $1$ can then be taken to stand for \defn{false}
and \defn{true} statements, respectively; an element of
$\mapset{\omega}{\2}$ is a \defn{truth-assignment} to the
\defn{propositional variables} $x_i$, and under such an assignment
$\sigma$, a propositional formula $t$ takes on the \defn{truth-value}
\begin{equation*}
  t^{\2}(\sigma(0),\dots,\sigma(n-1))
\end{equation*}
if $t$ is $n$-ary.  Write $\pairing{\sigma,t}$ for the truth-value of $t$
under $\sigma$.  A \emph{model} for a set of propositional formulas is a
truth-assignment $\sigma$ sending the set to $1$ under the map
$t\mapsto\pairing{\sigma,t}$.

\begin{theorem}[Compactness for sentential logic]
A set of propositional formulas has a model if each finite subset does.
\end{theorem}

\begin{proof}
If a set of sentences $t$ satisfies the hypothesis, then the collection
of closed subsets $\{\sigma:\pairing{\sigma,t}=1\}$ of
$\mapset{\omega}{\2}$ has the finite-intersection property.
\end{proof}

The sets $\{\sigma:\pairing{\sigma,t}=1\}$ are precisely the clopen
subsets of $\mapset{\omega}{\2}$.

\section{Relations and formulas}

From the relations $R^M$ and the interpretations $t^M$ of terms $t$, new
relations on $M$ can be derived by various techniques.  These relations
will be the \defn{$0$-definable} relations of $M$, and each of them will
be the interpretation of a \defn{formula} of $\lang$.  (The
\defn{definable} relations of $M$ are the interpretations of formulas of
$\lang(M)$.)  Distinctions are made according to which techniques are
needed to derive the relations.

The \defn{atomic} formulas are given thus:
\begin{itemize}
\item
If $t_0$ and $t_1$ are $n$-ary terms, then there is an $n$-ary atomic
formula $t_0=t_1$ whose interpretation $(t_0=t_1)^M$ is $\{\tuple a\in
M^n:t_0^M(\tuple a)=t_1^M(\tuple a)\}$.
\item
If $t_0$, \dots, $t_{n-1}$ are $m$-ary terms, and $R$ is $n$-ary, then
there is an $m$-ary atomic formula $R(t_0,\dots,t_{n-1})$ whose
interpretation $R(t_0,\dots,t_{n-1})^M$ is $\{\tuple a\in
M^m:(t_0^M(\tuple a),\dots,t_{n-1}^M(\tuple a))\in R^M\}$.
\end{itemize}
(In particular, $R(x_0,\dots,x_{n-1})^M=R^M$.)

If $t$ is an $m$-ary Boolean term, and $\phi_0$, \dots, $\phi_{n-1}$ are
$n$-ary atomic formulas, then there is an $n$-ary \defn{basic} or
\defn{quantifier-free} formula, say $t(\phi_0,\dots,\phi_{n-1})$, whose
interpretation is
\begin{equation*}
  t^{\pow(M^n)}(\phi_0^M,\dots,\phi_{n-1}^M).
\end{equation*}
If we identify formulas with indistinguishable interpretations in every
structure, then the set of basic formulas is a Boolean algebra generated
by the atomic formulas.  The set of \defn{formulas} is the smallest
Boolean algebra containing the atomic formulas and closed under the
operation converting an $n+1$-ary formula $\phi$ into an $n$-ary formula
$\exists x_n\,\phi$ whose interpretation is the image of $\phi^M$ under
the map
\begin{equation*}
  (a_0,\dots,a_n)\mapsto(a_0,\dots,a_{n-1}):M^{n+1}\to M^n.
\end{equation*}
The Boolean algebra of $n$-ary formulas of $\lang$ can be denoted
$\Fm{n}(\lang)$.

The formula $\lnot\exists x_n\,\phi$ is also denoted $\forall
x_n\,\lnot\phi$, and $\lnot\phi\lor\psi$ is denoted $\phi\to\psi$.  If
$\phi$ is an $n$-ary formula, and $t_0$, \dots, $t_{n-1}$ are $m$-ary
terms, then there is an $m$-ary formula $\phi(t_0,\dots,t_{n-1})$ with
the obvious interpretation; in particular, if it is not also $(n-1)$-ary,
then $\phi$ is the same as the formula $\phi(x_0,\dots,x_{n-1})$.

The $A$-definable relations of $M$ are the interpretations in $M$
of formulas of $\lang(A)$.  In particular, they are the sets
$\phi(a_0,\dots,a_{m-1},x_0,\dots,x_{n-1})^M$, where $\phi$ is an
$m+n$-ary formula of $\lang$, and $\tuple a$ is a tuple from $A$.

\defn{Sentences} are $0$-ary formulas.

\section{Substructures}

Suppose $M$ and $N$ are members of $\Mod(\lang)$.  We can now say
that an embedding of $M$ in $N$ is a map $h:M\to N$ such that
\begin{equation*}
  h\inv(\phi^N)=\phi^M
\end{equation*}
for all basic formulas $\phi$ of $\lang$; if the same holds for
\emph{all} formulas $\phi$ of $\lang$, then $h$ is an
\defn{elementary embedding}.
If the universe of $N$ includes the universe of $M$, and the
inclusion-map is an embedding, we say $M$ is a
\defn{substructure} of $N$ and write
\begin{equation*}
  M\included N;
\end{equation*}
if the inclusion-map is an elementary embedding, we write
\begin{equation*}
  M\elsub N
\end{equation*}
and say $M$ is an \defn{elementary} substructure of $N$.

\begin{lemma}[Tarski--Vaught]
Suppose $M\included N$.  Then $M\elsub N$, provided that
\begin{equation*}
  \phi(\tuple a,x_0)^N\cap M
\end{equation*}
is nonempty whenever $\phi(\tuple a,x_0)^N$ is, for all $\lang$-formulas
$\phi$ and all tuples $\tuple a$ from $M$.
\end{lemma}

\begin{proof}
Let $\Sigma$ comprise the formulas $\phi$ such that
\begin{equation*}
  \phi(x_0,\dots,x_{n-1})^M=\phi(x_0,\dots,x_{n-1})^N\cap M^n.\tag{$*$}
\end{equation*}
Then $\Sigma$ contains all the basic formulas and is closed under the
Boolean operations.  Suppose $\phi$ is in $\Sigma$ and $\tuple a$ is in
$M^n$.  Then
\begin{equation*}
  \phi(\tuple a,x_0)^M=\phi(\tuple a,x_0)^N\cap M.
\end{equation*}
By hypothesis then, $\phi(\tuple a,x_0)^M$ and $\phi(\tuple a,x_0)^N$ are
alike empty or not.  Hence $(*)$ holds, \emph{mutatis mutandis}, with
$\exists x_{n-1}\phi$ in place of $\phi$.  Therefore
$\Sigma=\Fm{}(\lang)$.
\end{proof}

\section{Models and theories}

Suppose $\phi$ is an $n$-ary formula of $\lang$, and $\tuple a$ is
an $n$-tuple of elements of $M$, so that $\phi(\tuple a)$ is a
sentence of $\lang(M)$.  We write
\begin{equation*}
  M\models\phi(\tuple a)
\end{equation*}
if $\phi(\tuple a)^M=1$, equivalently, $\tuple a\in\phi^M$. The
map $h:M\to N$ is an elementary embedding just in case
\begin{equation*}
  M\models\phi(\tuple a)\iff N\models\phi(h(\tuple a))
\end{equation*}
for all such $\phi$ and $\tuple a$.

If $\K$ is a subclass of $\Mod(\lang)$, then the
\defn{theory} $\Th(\K)$ of $\K$ is the subset of
$\Fm 0(\lang)$ comprising $\sigma$ such that $M\models\sigma$
whenever $M\in \K$; this subset is a filter, if $\K$ is nonempty;
otherwise it contains every sentence. In general, a
\defn{theory} of $\lang$ is $\Fm 0(\lang)$ or a filter of it; a
\defn{consistent} theory is a proper filter; a
\defn{complete} theory is an ultrafilter. A
\defn{model} of a set $\Sigma$ of sentences is a structure $M$
such that $\Sigma\included\Th(M)$.  We write
\begin{equation*}
  \Sigma\models\sigma
\end{equation*}
if every model of $\Sigma$ is a model of $\sigma$ (that is, of
$\{\sigma\}$).  We write
\begin{equation*}
  \Sigma\vdash\sigma
\end{equation*}
if $\sigma$ is in the theory generated by $\Sigma$.  If
$\Sigma\vdash\sigma$, then $\Sigma\models\sigma$.

\section{Compactness}

It is a consequence of the following that $\Sigma\vdash\sigma$ if
$\Sigma\models\sigma$.

\begin{theorem}[Compactness]
Every consistent theory has a model.
\end{theorem}

\begin{proof}
Let $T$ be a consistent theory in the signature $\lang$.  We shall extend
$\lang$ to a signature $\lang'$, and extend $T$ to a complete theory $T'$
of $\lang'$.  We shall do this in such a way that, for every unary
formula $\phi$ of $\lang'$, there will be a constant-symbol $c_{\phi}$
not appearing in $\phi$ such that
\begin{equation*}
  T'\vdash\exists x_0\,\phi\to\phi(c_{\phi}).
\end{equation*}
Then $T'$ and the constant-symbols $c_{\phi}$ will determine a structure
$M$ in the following way.  The universe of $M$ will consist of
equivalence-classes $[c_{\phi}]$ of the symbols $c_{\phi}$, where
\begin{equation*}
[c_{\phi}]=[c_{\psi}]\iff T'\vdash c_{\phi}=c_{\psi}.
\end{equation*}
Then we require
\begin{equation*}
  \tag{$*$}
  \phi^M=\{[\tuple c]:T'\vdash\phi(\tuple c)\}
\end{equation*}
for all basic formulas $\phi$ of $\lang'$ and all tuples $\tuple c$ of
symbols $c_{\phi}$.  The requirements ($*$) do make sense.  In
particular, $c_{\phi}^M=[c_{\phi}]$.  The requirements determine a
well-defined structure, since $T'$ is complete.

If $T'$ is as claimed, then ($*$) holds for all formulas $\phi$; we show
this by induction.  If $\phi$ is an $n$-ary formula, and $[\tuple c]$ is
an $(n-1)$-tuple from $M$, let $d$ be the constant-symbol determined by
the unary formula $\phi(\tuple c,x_0)$.  If ($*$) holds for $\phi$, then
we have:
\begin{align*}
  [\tuple c]\in(\exists x_n\,\phi)^M
  & \implies M\models\phi(\tuple c,[e]),\text{ some $[e]$ in }M \\
  & \implies T'\vdash\phi(\tuple c,e) \\
  & \implies T'\vdash\exists x_0\,\phi(\tuple c,x_0) \\
  & \implies T'\vdash\phi(\tuple c,d) \\
  & \implies M\models(\tuple c, [d]) \\
  & \implies [\tuple c]\in(\exists x_n\,\phi)^M;
\end{align*}
so ($*$) holds with $\exists x_n\,\phi$ in place of $\phi$.

Once ($*$) holds for all formulas $\phi$, then in particular it
holds when $\phi$ is a sentence in $T$; so $M\models T$.

It remains to find $T'$ as desired.  First we construct a chain
$\lang=\lang_0\included\lang_1\included\dots$ of signatures, where
$\lang_{n+1}\setminus\lang_n$ consists of a constant-symbol $c_{\phi}$
for each unary formula $\phi$ in $\lang_n$.  Taking the union of the
chain gives $\lang'$.

Now we work in the Stone space of $\Fm 0(\lang')$.  We claim that
the collection
\begin{equation*}
  \{[\sigma]:\sigma\in T\} \cup \{[\forall
  x_0\,\lnot\phi\lor\phi(c_\phi)]:\phi\in\Fm 1(\lang')\}
\end{equation*}
of closed sets has the finite-intersection property; from this, by
compactness, we can take $T'$ to be an element of the
intersection.

To establish the f.i.p., suppose that $[\psi]$ is a nonempty finite
intersection of sets in the collection.  Then $\psi\in\Fm 0(\lang_n)$ for
some $n$.  If $\phi\in\Fm 1(\lang')\setminus\Fm 1(\lang_{n-1})$, then
$c_{\phi}$ does not appear in $\psi$.  If also $[\psi]\cap[\forall
x_0\,\lnot\phi]$ is empty, then
\begin{equation*}
  [\psi]\cap[\phi(c_{\phi})]
\end{equation*}
is nonempty; for, if $M\models\psi\land\exists x_0\,\phi$, then we may
assume $M\models\psi\land\phi(c_{\phi})$.
\end{proof}

\begin{theorem}%[downward L\"{o}wenheim--Skolem]
Suppose $N\in\Mod(\lang)$, and $\kappa$ is a cardinal such that
\begin{equation*}
  \aleph_0+\abs{\lang}\leq\kappa\leq\abs{N}.
\end{equation*}
Then there is $M$ in $\Mod(\lang)$ such that $M\elsub N$ and
$\abs{M}=\kappa$.
\end{theorem}

\begin{proof}
Use the proof of Compactness, with $\Th(N)$ for $T$.  We can choose $T'$,
and we can choose $c_{\phi}^N$ in $N$, so that $N\models T'$.  Then we
may assume $M\included N$, and so $M\elsub N$ by the Tarski--Vaught test.
By construction, $\abs{M}\leq\abs{\lang'}=\aleph_0+\abs{\lang}$.

To ensure $M=\kappa$, we first add $\kappa$-many new
constant-symbols to $\lang$ and let their interpretations in $N$
be distinct.
\end{proof}

\begin{example}
In the signature $\{\in\}$ of set-theory, any infinite structure
has a countably infinite elementary substructure, even though the
power-set of an infinite set is uncountable.
\end{example}

\begin{corollary}%[upward L\"{o}wenheim--Skolem]
Suppose $A$ is an infinite $\lang$-structure and
$\abs{A}+\abs{\lang}\leq\kappa$.  Then there is $M$ in
$\Mod(\lang)$ such that $A\elsub M$ and $\abs{M}=\kappa$.
\end{corollary}

\begin{proof}
Let $\{c_{\mu}:\mu<\kappa\}$ be a set of new constant-symbols, and let
$T$ be the theory generated by $\Th(A_A)$ and $\{c_{\mu}\neq
c_{\nu}:\mu\neq\nu\}$.  Use Compactness to get a model $N$ of $T$; then
use the last Theorem to get $M$ as desired.
\end{proof}

\bibliographystyle{plain}
\bibliography{../references}
\end{document}
