\documentclass[twoside,a4paper,10pt,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}

 \addtolength{\voffset}{-1.5cm}
 \addtolength{\textheight}{3cm}
 %\raggedright


\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
\newcommand{\C}{\mathbf{C}}         % the complex numbers
\newcommand{\F}{\mathbf{F}}         % (finite) field

\newcommand{\id}{\mathrm{id}}       % identity-function

\newcommand{\unit}[1]{{#1}^{\times}} % group of units of a ring

\newcommand{\stroke}{\mathrel{|}}   % stroke for semi-group example

\newcommand{\str}[1]{\mathcal{#1}}  % structure with universe #1

%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 \thispagestyle{empty} \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.
(Formal definitions of these structures are given in \S\ \ref{algebra}.)
References for model-theory include \cite{Chang--Keisler}, \cite{Hodges}
and \cite{Poizat}.

Words in \defn{boldface} are technical terms and are often being defined,
implicitly or explicitly, by the sentence in which they occur.

\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, $()$ or $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 $\str 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)$; in the latter notation, we can
understand $\R$ as the \emph{set} of real numbers.
\end{examples}

A structure in a given signature, say $\lang'$, can be understood as a
structure with a smaller signature, say $\lang$: just ignore the
interpretations of the symbols in $\lang'\setminus\lang$.  The structure
in $\lang$ is then a \defn{reduct} of the structure in $\lang'$, which is
in turn an \defn{expansion} of the structure in $\lang$.

\begin{example}
The abelian group $(\R,+,-,0)$ is a reduct of the ordered field\\
\mbox{$(\R, +, -, \cdot, \leq, 0, 1)$;} the group can be \emph{expanded}
to the ordered field.
\end{example}

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 $\str M$ and $\str 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} from $\str M$ to $\str N$ if it \emph{preserves} the functions,
relations and constants symbolized in $\lang$, that is,
\begin{itemize}
\item
$h(f^{\str M}(\tuple a))=f^{\str N}(h(\tuple a))$;
\item
$h(\tuple a)\in R^{\str N}$ when $\tuple a\in R^{\str M}$;
\item
$h(c^{\str M})=c^{\str 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$.  In particular, the underlying map of an embedding is injective
(or \emph{one-to-one}); if it is also surjective (or \emph{onto}), then
the embedding is an \defn{isomorphism}.

We may confuse a structure with its isomorphism-class.

\begin{examples}
A group-homomorphism is a homomorphism of groups; a group-mono\-morphism
is an embedding of groups; a group-isomorphism is an isomorphism of
groups.
\end{examples}

If $M\included N$, and the inclusion-map of $M$ in $N$ is an embedding of
$\str M$ in $\str N$, then we write
\begin{equation*}
  \str M\included \str N
\end{equation*}
and say that $\str M$ is a \defn{substructure} of $\str N$.

\begin{example}
A subgroup of a group is a substructure of a group, and in fact any
substructure of a group is a subgroup.  However, while $\Z$ is a
substructure of $\R$, it is not a subfield (because it is not a field).
\end{example}

\section{Functions and terms}

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

The \defn{interpretation} $t^{\str M}$ in ${\str M}$ of an $n$-ary term
$t$ of $\lang$ will be an $n$-ary function on $M$.  Terms can be defined
as strings of symbols so that the following hold:
\begin{itemize}
\item
Each constant-symbol $c$ is also an $n$-ary term whose interpretation in
$\str M$ is the constant map $\tuple a\mapsto c^{\str M}$ on $M^{n}$.
\item
There is an $n$-ary term $x_i$ whose interpretation in $\str M$ 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---call it $f(t_0,\dots,t_{n-1})$---whose
interpretation is the map
\begin{equation*}
\tuple a\mapsto f^{\str M}(t_0^{\str M}(\tuple a),\dots, t_{n-1}^{\str
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; the terms $x_i$ are the \defn{variables}.

\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 ${\str M}$ is the
map
\begin{equation*}
\tuple a\mapsto t^{\str M}(u_0^{\str M}(\tuple a),\dots,u_{n-1}^{\str
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)$.  Sometimes letters like $x$, $y$ and $z$ are used for
variables.

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 ${\str M}$ naturally determines an
$\lang(A)$-structure, denoted ${\str 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{Algebras}\label{algebra}

Suppose $\str M\in\Mod(\lang)$.  An \defn{equation}
\begin{equation*}
  t=u
\end{equation*}
of $n$-ary terms of $\lang$ is an \defn{identity} of $\str M$ if $t^{\str
M}=u^{\str M}$; we can then write
\begin{equation*}
  \str M\models t=u
\end{equation*}
and say that $\str M$ is a \defn{model} of $t=u$ or that $\str M$
\defn{satisfies} the identity.

Suppose $\lang$ contains no relation-symbols.  An element of
$\Mod(\lang)$ can be called an \defn{algebra}.  A set of equations of
terms of $\lang$ determines a \defn{variety} of $\lang$ (namely the
subclass of $\Mod(\lang)$ comprising each structure that is a model of
each equation.)  A substructure of an element of a variety is also in the
variety.

Several standard classes of mathematical structures are varieties or
subclasses of these, in signatures comprising some of:
\begin{enumerate}\setcounter{enumi}{-1}
  \item
  the constant-symbols $0$ and $1$, for \defn{zero} and \defn{one};
  \item
  the unary function-symbols $-$ and $\inv$, for \defn{additive} and \defn{multiplicative
  inversion};
  \item
  the binary function-symbols $+$ and $\cdot$, for \defn{addition} and \defn{multiplication}.
\end{enumerate}
Specific signatures involving these symbols are sometimes named thus:
\begin{center}
\begin{tabular}{r|l}
 The set: & \dots is the signature of:\\ \hline
 $\{\cdot\}$ & semi-groups\\
 $\{\cdot,1\}$ & monoids\\
 $\{\cdot,\inv,1\}$ & groups\\
 $\{+,-,0\}$ & abelian groups\\
 $\{+,-,\cdot,0,1\}$ & rings
 \end{tabular}
 \end{center}
The corresponding structures will be defined presently.  First, terms
with these symbols are customarily written so that:
\begin{itemize}
  \item
  $0$, $1$ and the variables $x_i$ are terms;
  \item
  if $t$ is a term, then so are $(-t)$ and $t\inv$;
  \item
  if $t$ and $u$ are terms, then so are $(t+u)$ and $(t\cdot u)$.
\end{itemize}
Abbreviations of terms are also customary, so that, for example:\\
  outer brackets can be removed;\\
  $tu$ means $t\cdot u$;\\
  $t-u$ means $t+-u$;\\
  $t*u*v$ means $((t*u)*v)$, where each $*$ is the same symbol $+$ or
  $\cdot$; and\\
  $t+uv$ means $t+(uv)$.

A \defn{semi-group} is a model of the identity
\begin{equation*}
  x(yz)=xyz.
\end{equation*}

\begin{examples}
The empty set is the universe of a semi-group.  The structure
$(M,\frown)$ is a semi-group, where $M$ comprises the strings
\begin{equation*}
\stroke\stroke\cdots\stroke
\end{equation*}
 consisting of some (positive, finite) number of strokes, and
$\frown$ is concatenation of strings.
\end{examples}

A \defn{monoid} is a semi-group satisfying the identities
\begin{align*}
  x\cdot 1 & = x,\\
  1\cdot x & = x.
\end{align*}

\begin{examples}
Let $M$ comprise the functions from some set to itself; let $\circ$ be
functional composition; and let $\id$ be the identity-function on $M$.
Then
\begin{math}
(M,\circ,\id)
\end{math}
is a monoid.  So is $(\omega,+,0)$.
\end{examples}

A \defn{group} is a monoid satisfying
\begin{align*}
  x\cdot x\inv & = 1, \\
  x\inv\cdot x & = 1.
\end{align*}
The group is \defn{abelian} if it satisfies $xy=yx$---though, as noted,
an abelian group is usually `written additively,' with the signature
$\{+,-,0\}$.

\begin{examples}
The group $(\Z,+,-,0)$ of integers is abelian; so is the group\\
$(S,\cdot,\inv,1)$, where $S$ is the circle $\{z\in\C:\abs z=1\}$,
comprising the complex numbers of modulus 1.
\end{examples}

A \defn{ring} is a structure $(R,+,-,\cdot,0,1)$ such that:
\begin{itemize}
  \item
  $(R,+,-,0)$ is an abelian group;
  \item
  $(R,\cdot,1)$ is a monoid;
  \item
  the identities $x(y+z)=xy+xz$ and $(x+y)z=xz+yz$ are satisfied.
\end{itemize}
By this definition, there is a ring, the \defn{trivial} ring, satisfying
$0=1$, but its universe comprises a unique element.

A ring is \defn{commutative} if it satisfies $xy=yx$.  In a commutative
ring, an element $a$ is called:
\begin{itemize}
 \item
 a \defn{zero-divisor} if $a\neq0$, but $ab=0$ for some non-zero $b$ in the ring;
 \item
 a \defn{unit} if $ab=1$ for some $b$ in the ring.
\end{itemize}
Then a zero-divisor cannot be a unit, and zero is a unit only in the
trivial ring. The set of units of a commutative ring $R$ is denoted
\begin{equation*}
  \unit R.
\end{equation*}
Then $(\unit R,\cdot,1)$ is a (well-defined) monoid and can be expanded
to a group. A non-trivial ring is an \defn{integral domain} if it is
commutative and contains no zero-divisors.

Henceforth in this section, let \emph{ring} mean \emph{non-trivial
commutative ring}, and let $(R, +, -, \cdot, 0, 1)$ be such a ring. Then
$R$ is an integral domain just in case $(R\setminus\{0\},\cdot,1)$ is a
well-defined monoid. If this monoid can be expanded to a group, then $R$
is a \defn{field}. Hence $R$ is a field just in case $\unit R$ comprises
all non-zero elements of $R$.

\begin{examples}
The sets $\Q$, of rational numbers; $\R$, of real numbers; and $\C$, of
complex numbers---each is the universe of a field.  So is their subset
$\{0,1\}$ (though the resulting field is not a substructure of these).
Over any field $K$ can be formed the
\defn{polynomial-ring}
\begin{equation*}
  K[x_0,\dots,x_{n-1}],
\end{equation*}
which can be defined as follows.  First say that $n$-ary terms $t$ and
$u$ of $\lang(K)$ are equivalent if the identity $t=u$ is satisfied in
every field of which $K$ is a substructure.  (If $K$ is infinite, it is
enough that $t^K=u^K$.)  Then $K[x_0,\dots,x_{n-1}]$ comprises the
equivalence-classes of the $n$-ary terms of $\lang(K)$.
\end{examples}

The signature of \defn{$R$-modules} is the signature of abelian groups,
with a unary function-symbol for each element of $R$.  A structure with
this signature is an $R$-module just in case the structure is an abelian
group satisfying all identities
\begin{align*}
  r(x+y) & = rx+ry, \\
  (r+s)x & = rx + sx,\\
  r(sx) & = rsx,\\
  1(x) & = x,
\end{align*}
where $r$ and $s$ are in $R$.

\begin{example}
Every Cartesian power of $R$ is an $R$-module; in particular, $R$ is an
$R$-module.
\end{example}

A \defn{submodule} of $R$ is a substructure of $R$ when $R$ is considered
as an $R$-module.  Any subset $A$ of $R$ \defn{generates} the submodule
\begin{equation*}
  (A),
\end{equation*}
which is the smallest submodule including $A$.  A proper submodule of $R$
is an \defn{ideal} of $R$ (although $R$ is sometimes called an
\defn{improper} ideal of itself).  If $I$ is an ideal of $R$, then the
\defn{quotient} $R/I$ is a ring, whose elements are the \defn{cosets}
$r+I$, where $r\in R$.  (Here $r+I=\{r+a:a\in I\}$.)

\begin{example}
Any two integers $a$ and $b$ have a
\defn{greatest common divisor}, sometimes denoted $(a,b)$, which can be
found by the Euclidean algorithm; this integer generates the submodule of
$\Z$ that is also denoted $(a,b)$.  Thus every ideal of $\Z$ is
\defn{principal}---generated by a single element.  If $n$ is a non-zero integer,
then the quotient $Z/(n)$ is finite, and its universe can be identified
with $n$.  The quotient $\Z/(0)$ is $\Z$ itself.
\end{example}

If $h:R\to S$ is a homomorphism of rings, then its \defn{kernel}
comprises $a$ in $R$ such that $h(a)=0$; this kernel is an ideal of $R$.
Every ideal $I$ of $R$ is the kernel of the quotient-map from $R$ to
$R/I$.

\begin{example}
Suppose $\tuple a\in\C^m$.  Then there is a ring-homomorphism from\\
$\C[x_0,\dots,x_{n+m-1}]$ to $\C[x_0,\dots,x_{n-1}]$, namely
\begin{equation*}
t(x_0,\dots,x_{n+m-1})\longmapsto
               t(x_0,\dots,x_{n-1},\tuple a).
\end{equation*}
The kernel is an ideal.
\end{example}

An ideal $I$ of $R$ is \defn{prime} if the complement $R\setminus I$ is
closed under multiplication.  An ideal of $R$ is
\defn{maximal} if no ideal of $R$ properly includes it.

\begin{theorem}
Suppose $I$ is an ideal of the commutative ring $R$.  Then:
\begin{itemize}
  \item
  $I$ is prime if and only if $R/I$ is an integral domain;
  \item
  $I$ is maximal if and only if $R/I$ is a field.
\end{itemize}
\end{theorem}

A corollary of the theorem is that maximal ideals are prime.

\begin{examples}
The prime ideals of $\Z$ are the ideals $(p)$, where $p$ is a prime
number; these ideals are maximal.  Hence the quotients $\Z/(p)$ are
fields, which can be denoted $\F_p$.  The quotient $\C[x]/(x^2)$ is not
an integral domain, since $(x^2)$ is not prime.  The quotient $\C[x]/(x)$
is just $\C$, so $(x)$ is a maximal ideal.
\end{examples}

\section{Boolean algebras}

An essential and notationally exceptional example is the \emph{Boolean
algebra} of subsets of a 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 ring satisfying
\begin{equation*}
  x^2=x.
\end{equation*}
In particular, such a ring satisfies $(x+y)^2=x+y$, hence
\begin{equation*}
  xy+yx=0;
\end{equation*}
replacing $y$ with $x$, we get $2x=0$, hence
\begin{equation*}
  -x=x;
\end{equation*}
so the signature of Boolean rings can be considered to be
$\{+,\cdot,0,1\}$.  We also get $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\}$, which is the
field $\2$.  Therefore prime ideals of Boolean rings are maximal, since
the quotient of a Boolean ring by an ideal is Boolean.

In terms in the signature of Boolean algebras, customarily
\defn{negation} ($\lnot$) has priority over \defn{conjunction} ($\land$)
and \defn{disjunction} ($\lor$).  A structure in this signature \emph{is}
a \defn{Boolean algebra} if it can be expanded to a signature containing
$+$ in such a way that:
\begin{itemize}
  \item
  the identities
  \begin{align*}
  x\lor y & ={x+y}+(x\land y), \\
  \lnot x & =x+1
\end{align*}
are satisfied, and
  \item
  this expansion, reduced to the signature $\{+,\land,0,1\}$, is a Boolean ring.
\end{itemize}
If such an expansion is possible, then it is obtained
by defining
\begin{equation*}
  x+y =(x\land\lnot y)\lor(y\land\lnot x).
\end{equation*}
The algebra $(\pow(\Omega),\cap,\cup,{}^c,\emptyset,\Omega)$ is a Boolean
algebra, since the required expansion is obtained by interpreting $+$ as
\defn{symmetric difference}, $\vartriangle$.


Any Boolean algebra has a partial order $\leq$ such that
\begin{equation*}
  x\leq y\iff x\land y=x;
\end{equation*}
its interpretation in $\pow(\Omega)$ is \emph{inclusion} ($\included$).

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
non-empty when $x\neq0$.

A \defn{lower bound} of a subset $A$ of a Boolean algebra is an element
$a$ of the algebra such that
\begin{equation*}
  a\leq x
\end{equation*}
whenever $x\in A$; this lower bound is an \defn{infimum} of $A$ if $b\leq
a$ whenever $b$ is a lower bound of $A$.  Infima are unique when they
exist; but they may not exist.  However,
\begin{equation*}
  \inf\{x,y\}=x\land y,
\end{equation*}
so infima of finite sets exist.  Also, if $A\included\pow(\Omega)$, then
$\inf A$ is the \emph{intersection} of $A$.  Thus every Boolean algebra
embeds in an algebra where infima exist.  However, an embedding need not
preserve infima.

\begin{example}
Let $A$ comprise the \emph{cofinite} subsets of $\omega$.  Then $\inf
A=\emptyset$.  However, $A$ is a filter of $\pow(\omega)$, so $A$ is
included in an ultrafilter $F$.  In the Stone-space,
\begin{equation*}
  F\in[x]
\end{equation*}
whenever $x\in A$; so $[\emptyset]$ is not the infimum of $\{[x]:x\in
A\}$.
\end{example}

A \defn{topology} for a set $\Omega$ is a substructure of
$(\pow(\Omega),\cap,\cup,0,1)$ that is closed under \emph{arbitrary}
intersection.  (So the topology contains, for each of its subsets, the
infimum that exists in $\pow(\Omega)$.)  The elements of the topology are
the \defn{closed} sets; their complements are \defn{open}.  A
\defn{basis} for a topology is just a substructure of
$(\pow(\Omega),\cup,0,1)$; the closed sets are then intersections of sets
in the basis.

A topology is \defn{Hausdorff} if any two distinct elements of the
underlying set are contained in disjoint open sets.

A subset of $\pow(\Omega)$ has the \defn{finite-intersection property} if
it generates a (proper) filter.  A topology for $\Omega$ is
\defn{compact} if every collection of closed sets with the
finite-intersection property has non-empty intersection.  It is enough
that these closed sets be in the basis, if there is one.

In particular, the subsets $[x]$ of a Stone-space compose a basis for a
topology, and these basic sets are clopen.  The topology is Hausdorff,
since two distinct points of the space 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 finite-intersection
  property;
  \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}
Thus the topology of the Stone-space is 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{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 $(\cdots(((t_0*t_1)*t_2)*\dots*t_{n-1})$ we can write
\begin{equation*}
  t_0*t_1*t_2*\dots* t_{n-1},
\end{equation*}
where each $*$ is (independently) $\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\land 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}.  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^{\str M}$ and the interpretations $t^{\str M}$ of
terms $t$, new relations on $M$ can be derived by various techniques.
These relations will be the \defn{$0$-definable} relations of ${\str M}$,
and each of them will be the interpretation of a \defn{formula} of
$\lang$. (The \defn{definable} relations of ${\str 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$ and $u$ are $n$-ary terms, then there is an $n$-ary atomic formula
$t=u$ whose interpretation $(t=u)^{\str M}$ is $\{\tuple a\in M^n:t^{\str
M}(\tuple a)=u^{\str 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---call it
$R(t_0,\dots,t_{n-1})$---whose interpretation is $\{\tuple a\in
M^m:(t_0^{\str M}(\tuple a),\dots,t_{n-1}^{\str M}(\tuple a))\in R^{\str
M}\}$.
\end{itemize}
(In particular, $R(x_0,\dots,x_{n-1})^{\str M}=R^{\str M}$.)

A \defn{literal} is an atomic formula or its \defn{negation}.  The
negation of an atomic formula $\alpha$ can be written
\begin{equation*}
  \lnot \alpha,
\end{equation*}
but the negation of $t=u$ is also $t\neq u$.  The interpretation in $\str
M$ of $\lnot \alpha$ is the complement of $\alpha^{\str M}$.

A literal is an example of a \emph{basic} or \emph{quantifier-free}
formula.  If $t$ is an $n$-ary Boolean term, and $\phi_0$, \dots,
$\phi_{n-1}$ are $m$-ary atomic formulas, then there is an $m$-ary
\defn{basic} or
\defn{quantifier-free} formula, say $t(\phi_0,\dots,\phi_{n-1})$, whose
interpretation in $\str M$ is
\begin{equation*}
  t^{\pow(M^m)}(\phi_0^{\str M},\dots,\phi_{n-1}^{\str M}).
\end{equation*}
If we identify formulas that have indistinguishable interpretations in
every structure, then the set of basic formulas is a Boolean algebra
generated by the atomic formulas.  (This assumes that the Boolean terms
$0$ and $1$ are also $n$-ary formulas.  If $n>0$, then these are
identified respectively with $x_0\neq0$ and $x_0=x_0$.  If $n=0$, then
the formulas might be written $\bot$ and $\top$; but some model-theorists
don't use such formulas.)

The set of
\defn{formulas} is then the smallest Boolean algebra containing the atomic
formulas and closed under the operation of \defn{existential
quantification}; this converts an $n+1$-ary formula $\phi$ into an
$n$-ary formula $\exists x_n\,\phi$ whose interpretation is the image of
$\phi^{\str 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$.

\begin{lemma}
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.
\end{lemma}

In particular, if it is not also $n-1$-ary, then an $n$-ary formula
$\phi$ is the same as the formula $\phi(x_0,\dots,x_{n-1})$.

The $A$-definable relations of ${\str M}$ are the interpretations in
${\str 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})^{\str 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{Elementary embeddings}

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

\begin{lemma}[Tarski--Vaught]
Suppose ${\str M}\included {\str N}$.  Then ${\str M}\elsub {\str N}$,
provided that
\begin{equation*}
  \phi(\tuple a,x_0)^{\str N}\cap M
\end{equation*}
is nonempty whenever $\phi(\tuple a,x_0)^{\str 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})^{\str M}=\phi(x_0,\dots,x_{n-1})^{\str 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)^{\str M}=\phi(\tuple a,x_0)^{\str N}\cap M.
\end{equation*}
By hypothesis then, $\phi(\tuple a,x_0)^{\str M}$ and $\phi(\tuple
a,x_0)^{\str 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\in\Fm{n}(\lang)$, and $\tuple a\in M^n$, so that
$\phi(\tuple a)\in\Fm{0}(\lang(M))$.  Then
\begin{align*}
  \phi(\tuple a)^{\str M} &= \{()\in M^0:(a_0^{\str M}(),\dots,
  a_{n-1}^{\str M}())\in\phi^{\str M}\}\\
  &=\{()\in M^0:\tuple a\in\phi^{\str M}\}.
\end{align*}
So $\phi(\tuple a)^{\str M}=1$ if $\tuple a\in\phi^{\str M}$, and in this
case we write
\begin{equation*}
  {\str M}\models\phi(\tuple a);
\end{equation*}
if $\tuple a\in M^n\setminus\phi^{\str M}$, then $\phi(\tuple a)^{\str
M}=0$, and $\str M\models\lnot\phi(\tuple a)$. The map $h:M\to N$ is an
elementary embedding just in case
\begin{equation*}
  {\str M}\models\phi(\tuple a)\iff {\str 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 ${\str M}\models\sigma$
whenever ${\str 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 ${\str M}$
such that $\Sigma\included\Th({\str 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
${\str M}$ in the following way.  The universe of ${\str 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^{\str 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}^{\str 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)^{\str M}
  & \implies {\str 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 {\str M}\models(\tuple c, [d]) \\
  & \implies [\tuple c]\in(\exists x_n\,\phi)^{\str 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 ${\str 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 ${\str M}\models\psi\land\exists x_0\,\phi$, then we
may assume ${\str M}\models\psi\land\phi(c_{\phi})$.
\end{proof}

\begin{theorem}%[downward L\"{o}wenheim--Skolem]
Suppose ${\str 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 ${\str M}$ in $\Mod(\lang)$ such that ${\str M}\elsub {\str
N}$ and $\abs{M}=\kappa$.
\end{theorem}

\begin{proof}
Use the proof of Compactness, with $\Th({\str N})$ for $T$.  We can
choose $T'$, and we can choose $c_{\phi}^{\str N}$ in $N$, so that ${\str
N}\models T'$.  Then we may assume $M\included N$, and so ${\str M}\elsub
{\str 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 ${\str 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 $\str A$ is an infinite $\lang$-structure and
$\abs{A}+\abs{\lang}\leq\kappa$.  Then there is ${\str M}$ in
$\Mod(\lang)$ such that $\str A\elsub {\str 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(\str A_A)$ and $\{c_{\mu}\neq
c_{\nu}:\mu\neq\nu\}$.  Use Compactness to get a model ${\str N}$ of $T$;
then use the last Theorem to get ${\str M}$ as desired.
\end{proof}

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