\documentclass[%
version=last,%
a5paper,
10pt,%
headings=small,%
bibliography=totoc,%
twoside,%
reqno,%
cleardoublepage=empty,%
open=any,%
parskip=half,%
draft=true,%
%DIV=classic,%
DIV=12,%
headinclude=false,%
pagesize]
{scrbook}

%\usepackage[notref,notcite]{showkeys}

\addtocounter{tocdepth}{-1}

%\usepackage[turkish]{babel}
%\usepackage[utf8]{inputenc}
%\usepackage[latin5]{inputenc}

\usepackage{hfoldsty}
\usepackage[neverdecrease]{paralist}
\usepackage{cclicenses}

%\renewcommand{\captionformat}{\ }  % didn't work?

\usepackage{verbatim}

\begin{comment}
  


\usepackage{float}
\floatstyle{boxed}
\restylefloat{figure}


\end{comment}

\usepackage{amssymb, amsmath,
  amsthm,url,upgreek,bm,mathrsfs,stmaryrd,pstricks,pst-node,pst-tree,pst-plot}
\usepackage[all]{xy}


%\newcommand{\Sym}[1]{\operatorname S_{#1}}  % symmetric group
\newcommand{\Sym}[1]{\operatorname{Sym}(#1)}  % symmetric group
\newcommand{\id}[1]{\operatorname{id}_{#1}}
%\newcommand{\Dih}[1]{\operatorname D_{#1}}  % dihedral group
%\newcommand{\Cen}[2]{\operatorname C_{#1}(#2)} % centralizer
\newcommand{\Z}{\mathbb Z}
\newcommand{\N}{\mathbb N}
\newcommand{\R}{\mathbb R}
\newcommand{\Q}{\mathbb Q}
\newcommand{\C}{\mathbb C}
\newcommand{\F}{\mathbb F}
\newcommand{\U}[1]{\operatorname U_{#1}}
\newcommand{\V}[2][L]{\operatorname Z_{#1}(#2)}
\newcommand{\I}[2][K]{\operatorname I_{#1}(#2)}
\newcommand{\zk}[2][K]{\overline{#2}^{#1}}
%\newcommand{\tp}[1]{\operatorname{tp}(#1)}
\newcommand{\Exists}[1]{\exists#1\;}
\newcommand{\Forall}[1]{\forall#1\;}
\newcommand{\lto}{\rightarrow}
\newcommand{\liff}{\leftrightarrow}
\newcommand{\abs}[1]{\lvert#1\rvert}
\newcommand{\Abs}[1]{\operatorname{Abs}(#1)}  % absolute numbers
\newcommand{\supp}[1]{\operatorname{supp}(#1)}
\newcommand{\Supp}[1]{\operatorname{supp}[#1]}
\newcommand{\sig}[1][S]{\mathscr{#1}}
\newcommand{\Mod}[1][\sig]{\operatorname{Mod}(#1)}
\newcommand{\Sn}[1][\sig]{\operatorname{Sn}(#1)}
\newcommand{\Fm}[2][n]{\operatorname{Sn}^{#1}(#2)}
\newcommand{\Th}[1]{\operatorname{Th}(#1)}
\newcommand{\Def}[1][n]{\operatorname{Def}^{#1}_B(\str A)}
\newcommand{\proves}{\vdash}
\newcommand{\divides}{\mathrel{\mid}}
\newcommand{\ndivides}{\mathrel{\nmid}}

%\newcommand{\indexset}{\Omega}
\newcommand{\ideal}{I}
\newcommand{\LT}[2]{\operatorname B_{#1}(#2)}

\newcommand{\included}{\subseteq}
\newcommand{\nincluded}{\nsubseteq}
\newcommand{\includes}{\supseteq}
\newcommand{\pincluded}{\subset}
\newcommand{\pincludes}{\supset}
\newcommand{\fsub}{\included_{\mathrm{fin}}}

\newcommand{\units}[1]{{#1}^{\times}}
\newcommand{\pow}[1]{\mathscr P(#1)}
\newcommand{\powf}[1]{\mathscr P_{\upomega}(#1)}
\newcommand{\symdiff}{\vartriangle}
\newcommand{\comp}{^{\mathrm c}}
\newcommand{\alg}[1]{{#1}^{\mathrm{alg}}}
\newcommand{\sep}{^{\mathrm{sep}}}
\newcommand{\str}[1]{\mathfrak{#1}}
\newcommand{\inv}{^{-1}}
\newcommand{\rad}{\sqrt{\vphantom{I}}}
\newcommand{\spec}[1][R]{\operatorname{Spec}(#1)}
\newcommand{\Oplain}{\mathscr O}
\newcommand{\Oh}[1]{\Oplain(#1)}
\newcommand{\Gal}[1]{\operatorname{Gal}(#1)}
\newcommand{\Fix}[1]{\operatorname{Fix}(#1)}
\newcommand{\pc}[1][R]{#1^{+}}
\newcommand{\st}[1]{{}^*\!#1}
\newcommand{\St}[2][]{\operatorname S_{#1}(#2)}
\newcommand{\Br}[1]{\operatorname B(#1)}
\newcommand{\Aut}[1]{\operatorname{Aut}(#1)}
\newcommand{\Frob}{\operatorname{Frob}}
\newcommand{\gpgen}[1]{\langle#1\rangle}
\newcommand{\Char}[1]{\operatorname{char}(#1)}
\newcommand{\diag}[1]{\operatorname{diag}(#1)}
\newcommand{\lcm}{\operatorname{lcm}}

\newcommand{\nmodels}{\nvDash}
\renewcommand{\models}{\vDash}

\renewcommand{\phi}{\varphi}
\renewcommand{\theta}{\vartheta}
\renewcommand{\epsilon}{\varepsilon}
\renewcommand{\vec}[1]{\bm{#1}}
\renewcommand{\setminus}{\smallsetminus}
\renewcommand{\emptyset}{\varnothing}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}

\renewcommand{\theequation}{\fnsymbol{equation}}

\newtheorem*{lemma}{Lemma}%[section]
\newtheorem{theorem}{Theorem}
\newtheorem*{corollary}{Corollary}
\newtheorem*{porism}{Porism}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{question}{Question}
%\newtheorem{problem}{Problem}
\theoremstyle{definition}
\newtheorem*{definition}{Definition}



\begin{document}
\title{Ultraproducts}
\author{David Pierce}
\date{\today}
\publishers{Mimar Sinan G\"uzel Sanatlar \"Universitesi\\
Matematik B\"ol\"um\"u\\
\url{http://mat.msgsu.edu.tr/~dpierce/}}
\uppertitleback{\centering
\emph{Ultraproducts}\\
\mbox{}\\
This work is licensed under the\\
 Creative Commons Attribution--Noncommercial--Share-Alike
License.\\
 To view a copy of this license, visit\\
  \url{http://creativecommons.org/licenses/by-nc-sa/3.0/}\\
\mbox{}\\
\cc \ccby David Pierce \ccnc \ccsa\\
\mbox{}\\
Mathematics Department\\
Mimar Sinan Fine Arts University\\
Istanbul, Turkey\\
\url{http://mat.msgsu.edu.tr/~dpierce/}\\
\url{dpierce@msgsu.edu.tr}
}
%\frontmatter
\maketitle

%\mainmatter
\chapter{Preface}
These notes are for a course called Ultraproducts
and Their Consequences, to be given at the Nesin Mathematics Village in
\c Sirince,
Sel\c cuk, \.Izmir, Turkey, in August, 2012.  The notes are mainly for my use;
they do not constitute a textbook, although parts of them
may have been written in textbook style.  The notes have not been
thoroughly checked for correctness; writing the notes has been my own
way of learning some topics.

The notes have grown like a
balloon, at all points: I have added things here and there as I have
seen that they
are needed or useful.  I have also rearranged sections.  There is too
much material here for a week-long course.  Some of the material is
background necessary for thorough consideration of some topics; this
background may be covered in a simultaneous course in \c Sirince.   

The catalogue listing for the
course\footnote{From
  \url{http://matematikkoyu.org/etkinlikler/2012-tmd-lisans-lisansustu/ultra_pierce.pdf},
  to which there is a link on
  \url{http://matematikkoyu.org/etkinlikler/2012-tmd-lisans-lisansustu/}
  as of August 6, 2012.}(with abstract as submitted by me on January
27, 2012) is as follows. 
  \begin{compactdesc}
    \item[Title of course:] Ultraproducts and their consequences

\item[Instructor:] Assoc.\ Prof.\ David Pierce

\item[Institution:] Mimar Sinan GS\"U

\item[Dates:] 13--19 A\u gustos 2012

\item[Prerequisites:] Some knowledge of algebra, including the theorem
  that a quotient of a ring by an ideal is a field if and only if the
  ideal is maximal. 

\item[Level:] Advanced undergraduate and graduate

\item[Abstract:] An ultraproduct is a kind of average of infinitely many
structures. The construction is usually traced to a 1955 paper of
Jerzy Los; however, the idea of an ultraproduct can be found in Kurt
Goedel's 1930 proof (from his doctoral dissertation) of the
Completeness Theorem for first-order logic.  Non-standard analysis,
developed in the 1960s by Abraham Robinson, can be seen as taking
place in an ultraproduct of the ordered field of real numbers: more
precisely, in an ultrapower.  Indeed, for each integer, the `average'
real number is greater than that integer; therefore an ultrapower of
the ordered field of real numbers is an ordered field with infinite
elements and therefore infinitesimal elements.  Perhaps the first
textbook of model theory is Bell and Slomson's \emph{Models and
Ultraproducts} of 1969: the title suggests the usefulness of
ultraproducts in the development various model-theoretic ideas.  Our
course will investigate ultraproducts, starting from one of the
simplest interesting examples: the quotient of the cartesian product
of an infinite collection of fields by a maximal ideal that has
nontrivial projection onto each coordinate.  No particular knowledge
of logic is assumed. 
  \end{compactdesc}

Such was the abstract that I submitted in January.  I have written the
following notes since then, by way of working out for myself some of
the ideas that might be presented in the course.  I have tried to
emphasize examples.  In some cases, I may have sacrificed generality
for concreteness.  A theorem that I might have covered, but have not,
is the theorem of Keisler and Shelah that elementary equivalence is
the same thing as isomorphism of ultrapowers. 


\tableofcontents

\listoffigures

\setcounter{chapter}{-1}


\chapter{Notation}\label{sect:not}

The set-theorist's natural numbers compose the set $\upomega$:
\begin{equation*}
\upomega=\{0,1,2,\dots\}.
\end{equation*}
In these notes, this set is used:
\begin{compactenum}[1)]
\item
 as an index-set for countably infinite sequences $(a_k\colon k\in\upomega)$;
 \item
 as the cardinal number of each countably infinite set.\footnote{The $\upomega$ here is printed in an upright, `roman' font, since it has a constant meaning.  This means the sloping, `italic' $\omega$ is available for use as a variable; but in fact it will not be used here.}
 \end{compactenum}  
 The set-theoretic feature of $\upomega$ is that
if $n\in\upomega$, then
\begin{equation*}
n=\{0,\dots,n-1\}.
\end{equation*}
In particular
\begin{align*}
0&=\emptyset,&1&=\{0\},&2&=\{0,1\}.
\end{align*}
If $A$ and $B$ are sets, we let
\begin{equation*}
A^B=\{\text{functions from $B$ to $A$}\}.
\end{equation*}
In particular, if $n\in\upomega$, then
\begin{equation*}
A^n=\{\text{functions from $n$ to $A$}\}.
\end{equation*}
An element of $A^n$ may be written as either of
\begin{align*}
&(b_0,\dots,b_{n-1}),&&(b^0,\dots,b^{n-1}),
\end{align*}
and this can be abbreviated by
\begin{equation*}
\vec b,
\end{equation*}
in boldface: it is an \textbf{$n$-tuple} of elements of $A$.  The superscripts in $(b^0,\dots,b^{n-1})$ are \emph{not} exponents, but just (upper) indices; we may use them, because we shall occasionally use \emph{lower} indices at the same time, as for example in consideration of sequences $(\vec b_k\colon k\in\upomega)$, where $\vec b_k\in A^n$, so that
\begin{equation*}
\vec b_k=(b_k^0,\dots,b_k^{n-1}).
\end{equation*}
Note that
\begin{equation*}
A^0=\{0\}=1.
\end{equation*}
The ring of (rational) integers is $\Z$, which is a sub-ring of $\Q$, the field of rational numbers; this in turn is a subfield of $\R$, the field of real numbers.  The set of \emph{positive} integers can be denoted by $\N$.  Thus
\begin{equation*}
\N=\{1,2,3,\dots\}.
\end{equation*}
One could write this also as $\upomega\setminus\{0\}$.  Some people also put $0$ in $\N$, and that is fine.  However, in these notes, I attempt to distinguish notationally the two roles of natural numbers: 
\begin{inparaenum}[(1)]
\item as indices and
\item
as rational numbers.
\end{inparaenum}
In the former role, the natural numbers compose $\upomega$; in the latter, $\N$.  It is also just useful to have distinct simple symbols for the two sets $\{0,1,2,\dots\}$ and $\{1,2,3,\dots\}$.

\chapter{Introduction}

\section{Products of fields}
Suppose $\mathscr K$ is an indexed family $(K_0,K_1,K_2,\dots)$ or $(K_i\colon i\in\upomega)$, where each $K_i$ is a \emph{field.}\footnote{The basic of rings and fields are reviewed, for completeness, in Chapter \ref{ch:rings}; but it is assumed that the reader is already somewhat familiar with them.  In the present section, we could work with an arbitrary index set $\Omega$ in place of $\upomega$.  Later (\S\ref{sect:red-prod}) we shall do this; but there is no obvious need to do so \emph{now.}}  For example, each $K_i$ might be $\R$, or each $K_i$ might be a different finite field.  We can form the \textbf{Cartesian product} of the family $\mathscr K$.  This product is denoted by one of the expressions
\begin{align*}
&\prod_{i\in\upomega}K_i,&&\prod\mathscr K.
\end{align*}
If $a$ belongs to this product, this means
\begin{equation*}
a=(a_i\colon i\in\upomega),
\end{equation*}
where $a_i\in K_i$ in each case.  Here $a$ is simply a function on $\upomega$ that, at every element $i$ of this domain, takes a value in $K_i$; we write this value as $a_i$, though it could be written also\footnote{Even the notation $i^a$ might be used.  Indeed, $a^{\sigma}$ is used below (p.\ \pageref{upper-sigma}, \S\ref{sect:Gal}) for the image under an automorphism $\sigma$ of an element $a$ of a given field.} as $a(i)$ or $a^i$.

The product $\prod\mathscr K$ is a ring in the obvious way, with respect to the termwise operations:
\begin{gather*}
a+b=(a_i+b_i\colon i\in\upomega),\\
-a=(-a_i\colon i\in\upomega),\\
0=(0\colon i\in\upomega)=(0,0,0,\dots),\\
a\cdot b=(a_i\cdot b_i\colon i\in\upomega),\\
1=(1\colon i\in\upomega)=(1,1,1,\dots).
\end{gather*}
Suppose $M$ is a \emph{maximal ideal} of the ring $\prod\mathscr K$.  Then the quotient $\prod\mathscr K/M$ is a field, called an \textbf{ultraproduct} of the family $\mathscr K$.  We want to understand this ultraproduct.  

There is a trivial case.  There may be some $j$ in $\upomega$ such that
\begin{equation*}
M=\{x\in\prod\mathscr K\colon x_j=0\}.
\end{equation*}
Then $M$ is a \emph{principal ideal}: it is generated by an element
\begin{equation*}
(1,\dots,1,0,1,\dots),
\end{equation*}
where every entry is $1$, except the entry $0$ with index $j$.  For, if this element of $M$ is $c$, then for every $a$ in $M$ we have $a=a\cdot c$.
In this case
\begin{equation*}
x+M=y+M\iff x_j=y_j.
\end{equation*}
Thus $\prod\mathscr K/M\cong K_j$ under the map $x\mapsto x_j$.  This isomorphism constitutes a proof that the ideal $(c)$ generated by $c$ is indeed maximal (since the quotient of a ring by an ideal is a field if and only if the ideal is maximal\footnote{This is written out and proved below as Theorem~\ref{thm:max-field} on page \pageref{thm:max-field}; but the reader should already be familiar with it.}).  By contrast, if $I$ is an ideal generated by an element
\begin{equation*}
(1,\dots,1,0,1,\dots,1,0,1,\dots),
\end{equation*}
with two zero entries, indexed by $j$ and $\ell$ respectively, then $\prod\mathscr K/I\cong K_j\times K_{\ell}$.  Since then $K_j\times K_{\ell}$ is not a field---since for example the nonzero elements $(1,0)$ and $(0,1)$ are not invertible---, $I$ must not be maximal.

If $M$ is a nonprincipal maximal ideal of $\prod\mathscr K$, then the ultraproduct $\prod\mathscr K/M$ will be seen to be a kind of `average' of the fields $K_j$.  But this must be properly understood.  More precisely, if $a\in\prod\mathscr K$, then $a+M$ will be a kind of average of the individual elements $a_i$ of the factors $K_i$.  We consider a particular example in the next section.

\section{Ultrapowers of the field of real numbers}

If each $K_i$ is $\R$, then the product $\prod_{i\in\upomega}K_i$ is the power $\R^{\upomega}$.  If $M$ is a maximal ideal of this ring, then the quotient $\R^{\upomega}/M$ is called an \textbf{ultrapower} of $\R$.  The field $\R$ embeds in $\R^{\upomega}/M$ under the \textbf{diagonal map,}
\begin{equation*}
x\mapsto(x,x,x,\dots)+M.
\end{equation*}
The diagonal map is so called, presumably because of the similarity of its definition to that of the map $x\mapsto(x,x)$ from $\R$ to $\R^2$, whose range is called a `diagonal' line.\footnote{Etymologically speaking, a diagonal line is a line joining two angles of a polygon.}  Perhaps we are likely to consider points $(x,x,x,\dots)$ of $R^{\upomega}$ themselves as \emph{horizontal} lines, as in Figure~\ref{fig:diag}.
\setlength{\unitlength}{1cm}
\begin{figure}[ht]
\centering
\begin{picture}(6.5,4.5)(-2.5,-0.5)
\put(-2,0){\line(0,1){4}}
\put(-1.5,2){\vector(1,0){1}}
\multiput(0,0)(1,0){5}{\line(0,1){4}}
\multiput(0,2)(1,0){5}{\circle*{0.1}}
\put(-2,2){\circle*{0.1}}
\put(-2.5,2){\makebox(0,0)[l]{$x$}}
\put(0,-0.5){\makebox(0,0)[b]{$0$}}
\put(1,-0.5){\makebox(0,0)[b]{$1$}}
\put(2,-0.5){\makebox(0,0)[b]{$2$}}
\put(3,-0.5){\makebox(0,0)[b]{$3$}}
\put(4,-0.5){\makebox(0,0)[b]{$4$}}
\end{picture}
\caption{The diagonal map}\label{fig:diag}
\end{figure}
It should be clear that the diagonal map is an embedding of $\R$ in $\R^{\upomega}/M$: it is a monomorphism, with trivial kernel.  For, if $x\neq0$, then for every element $a$ of $\R^{\upomega}$ we have
\begin{equation*}
a=\Bigl(\frac{a_0}x,\frac{a_1}x,\frac{a_2}x,\dots\Bigr)\cdot(x,x,x,\dots)=\Bigl(\frac{a_i}x\colon i\in\upomega\Bigr)\cdot(x\colon i\in\upomega).
\end{equation*}
Thus, if it were possible that $x\neq0$, but $(x,x,x,\dots)\in M$, then $M$ would be the improper ideal $\R^{\upomega}$.

If $M$ is a non-principal maximal ideal of $\R^{\upomega}$, then the diagonal embedding of $\R$ in $\R^{\upomega}/M$ is not surjective: it is not an epimorphism.  For, the element $(1,2,3,\dots)+M$ of the quotient is not in its range.  See Figure~\ref{fig:123}.
\begin{figure}[ht]
\centering
\begin{picture}(3,4.5)(-0.5,-0.5)
\multiput(0,0)(1,0){4}{\line(0,1){4}}
\multiput(0,0.5)(1,1){4}{\circle*{0.1}}
\put(0,-0.5){\makebox(0,0)[b]{$0$}}
\put(1,-0.5){\makebox(0,0)[b]{$1$}}
\put(2,-0.5){\makebox(0,0)[b]{$2$}}
\put(3,-0.5){\makebox(0,0)[b]{$3$}}
\put(-0.5,0.5){\makebox(0,0)[l]{$1$}}
\put(-0.5,1.5){\makebox(0,0)[l]{$2$}}
\put(-0.5,2.5){\makebox(0,0)[l]{$3$}}
\put(-0.5,3.5){\makebox(0,0)[l]{$4$}}
\end{picture}
\caption{An infinite element of $\R^{\upomega}/M$}\label{fig:123}
\end{figure}
Indeed, suppose if possible
\begin{equation*}
(1,2,3,\dots)+M=(x,x,x,\dots)+M,
\end{equation*}
so that $(1-x,2-x,3-x,\dots)\in M$.  If $x\notin\N$, then for every $a$ in $\R^{\upomega}$ we have
\begin{equation*}
a=\Bigl(\frac{a_0}{1-x},\frac{a_1}{2-x},\frac{a_2}{3-x},\dots\Bigr)\cdot(1-x,2-x,3-x,\dots),
\end{equation*}
which must be in $M$; and this contradicts that $M$ is proper.  If $x\in\N$, so that $1-x$ is a non-positive element $n$ of $\Z$, then $M$ contains $(n,n+1,\dots,-1,0,1,2,\dots)$, and therefore $M$ also contains $(1,\dots,1,0,1,\dots)$, because this is
\begin{equation*}
(n,n+1,\dots,-1,0,1,2,\dots)\cdot\Bigl(\frac1n,\frac1{n+1},\dots,\frac1{-1},0,\frac11,\frac12,\dots\Bigr).
\end{equation*}
Thus $M$ includes a principal maximal ideal as before, so $M$ itself is either principal or improper.

On the assumption that $M$ is a nonprincipal maximal ideal of $\R^{\upomega}$, we have shown that the element $(1,2,3,\dots)+M$ of the quotient $\R^{\upomega}/M$ is not in the image of $\R$ under the diagonal map.  But this element will be seen as a kind of average of the elements of $\N$.  Indeed, for every $m$ in $\N$, all but finitely many elements of $\N$ are greater than $m$.  So the `average' element of $\N$ is greater than $m$.  And we shall see that
\begin{equation*}
(1,2,3,\dots)+M>(m,m,m,\dots)+M.
\end{equation*}
Since this will be true for all $m$ in $\N$, the element $(1,2,3,\dots)+M$ of $\R^{\upomega}/M$ will be \emph{infinite.}

But so far, all we know is that $\R^{\upomega}/M$ is a field.   We now want to show that it has a (linear) ordering that makes it into an ordered field.  

\section{Ordered rings}\label{sect:of}

In these notes, a \textbf{ring} is always a commutative unital ring.  Then an \textbf{ordered ring} (or more precisely a \emph{partially ordered ring}) is a pair $(R,\pc)$, where $R$ is a ring in our sense, and $\pc$ is a subset of $R$ that is closed under addition and multiplication and that, for all $x$ in $R$, contains both $x$ and $-x$ if and only if $x=0$.  That is,
\begin{gather*}
	x\in R\And y\in R\implies x+y\in R\And xy\in R,\\
	x\in R\And -x\in R\implies x=0,\\
	0\in R.
\end{gather*}
In this case, we can define
\begin{equation*}
x\leq y\iff y-x\in \pc.
\end{equation*}
Then
\begin{equation*}
\pc=\{x\in R\colon 0\leq x\}.
\end{equation*}
The set $\pc$ is the \textbf{positive cone} of $\leq$.  However, only the elements of $\pc\setminus\{0\}$ should be called positive.\footnote{The Wikipedia article `Ordered ring' defines this as what, for present purposes, should be called a linearly or totally ordered ring: it meets the additional condition that at least one of $x$ and $-x$ is always in $\pc$.  Then what for us is an ordered ring is what, for the Wikipedia article, should be called a partially ordered ring; but the article defines no such thing.  At least this is the situation as of July 22, 2012.  The notation $\pc$ and the term \emph{positive cone} are used only in another Wikipedia article, `Partially ordered group'.  The notation and term are unfortunate, since the positive cone in the present sense contains $0$, but the real number $0$ is not normally considered positive.  We could define ordered rings in terms of the set $\{x\colon x>0\}$; but then the possibility of positive zero-divisors would have to be dealt with; also, there would be a complication in the definition of the product order.}
It follows that
\begin{compactenum}[(1)]
\item
the relation $\leq$ is reflexive, that is,
\begin{equation*}
x\leq x,
\end{equation*}
since $x-x\in \pc$;
\item
the relation $\leq$ is anti-symmetric, that is,
\begin{equation*}
x\leq y\And y\leq x\implies x=y,
\end{equation*}
since if $y-x$ and $x-y$ are in $\pc$, then they must be $0$;
\item
the relation $\leq$ is transitive, that is,
\begin{equation*}
x\leq y\And y\leq z\implies x\leq z,
\end{equation*}
since if $y-x$ and $z-y$ are in $\pc$, so is their sum, $z-x$.
\end{compactenum}
The relation $\leq$ is thus a (partial) ordering of $R$, induced by $\pc$.  Moreover,
\begin{compactenum}[(1)]\setcounter{enumi}{3}
\item
this ordering is translation-invariant, that is,
\begin{equation*}
x\leq y\implies x+z\leq y+z,
\end{equation*}
since if $y-x$ is in $\pc$, so is $(y+z)-(x+z)$.  Finally,
\item
multiplication by positive elements preserves the ordering, that is,
\begin{equation*}
x\leq y\And 0<z\implies xz\leq yz,
\end{equation*}
since if $y-x$ and $z$ are in $\pc$, so is their product, $zy-zx$.
\end{compactenum}
Conversely, these properties of $\leq$ imply that the set $\{x\in R\colon 0\leq x\}$ is a positive cone that induces the ordering $\leq$.  So we can write $(R,\pc)$ also as $(R,\leq)$.

Suppose $((R_i,\pc[R_i])\colon i\in I)$ is an indexed family of ordered rings.  Then easily the product
\begin{equation*}
\Bigl(\prod_{i\in I}R_i,\prod_{i\in I}\pc[R_i]\Bigr)
\end{equation*}
is an ordered ring.  For example, the `Cartesian plane' $\R^2$ (that is, $\R\times\R$) is an ordered ring whose positive cone is the first quadrant.  See Figure~\ref{fig:quad}.
\begin{figure}[ht]
\mbox{}\hfill
\begin{picture}(4,4)(-2,-2)
\put(0,-2){\line(0,1){2}}
\put(-2,0){\line(1,0){2}}
\thicklines
\put(0,0){\vector(1,0){2}}
\put(0,0){\vector(0,1){2}}
\qbezier[9](0.1,0.1)(0.1,1)(0.1,1.9)
\qbezier[9](0.3,0.1)(0.3,1)(0.3,1.9)
\qbezier[9](0.5,0.1)(0.5,1)(0.5,1.9)
\qbezier[9](0.7,0.1)(0.7,1)(0.7,1.9)
\qbezier[9](0.9,0.1)(0.9,1)(0.9,1.9)
\qbezier[9](1.1,0.1)(1.1,1)(1.1,1.9)
\qbezier[9](1.3,0.1)(1.3,1)(1.3,1.9)
\qbezier[9](1.5,0.1)(1.5,1)(1.5,1.9)
\qbezier[9](1.7,0.1)(1.7,1)(1.7,1.9)
\qbezier[9](1.9,0.1)(1.9,1)(1.9,1.9)
\end{picture}
\hfill
\begin{picture}(4,4)(-2,-2)
\put(0,-2){\vector(0,1){4}}
\put(-2,0){\line(1,0){2}}
\thicklines
\put(0,0){\vector(1,0){2}}
\end{picture}
\hfill\mbox{}
\caption{The positive cones of $\R^2$ and $\C$}\label{fig:quad}
\end{figure}
However, this quadrant is not the positive cone of an ordering of $\C$, since it is not closed under complex multiplication.  The complex field does however have an ordering, whose positive cone consists of the non-negative real numbers (as in Figure~\ref{fig:quad}).  In this ordering, $a+b\mathrm i\leq x+y\mathrm i$ if and only if $a\leq x$ and $b=y$.  The product-ordering of the power $\R^{\upomega}$ is given by the rule
\begin{equation*}
0\leq x\iff 0\leq x_0\And 0\leq x_1\And 0\leq x_2\And\dots\iff\bigwedge_{i\in\upomega}0\leq x_i.
\end{equation*}

Suppose again $(R,\pc)$ is an arbitrary ordered ring, and $I$ is an ideal of $R$.  We let
\begin{equation*}
\pc/I=\{x+I\in R/I\colon x\in I\}.
\end{equation*}
It is possible that $x+I\in\pc/I$ although $x\notin\pc$.  The set $\pc/I$ is closed under addition and multiplication.  So it is the positive cone of an ordering of $R/I$ if and only if
\begin{equation*}
x+I\in\pc/I\And -x+I\in\pc/I\implies x+I=I,
\end{equation*}
that is (since $-x+I\in\pc/I$ means $x+y\in I$ for some $y$ in $\pc$),
\begin{equation*}
x\in\pc\And y\in\pc\And x+y\in I\implies x\in I.
\end{equation*}
(By symmetry, $y\in I$ can also be concluded.)  For example, the only proper, non-trivial ideals of the product ring $\R^2$ are the principal ideals generated respectively by $(1,0)$ and $(0,1)$.  These ideals meet the desired condition with respect to the product ordering, and the quotient (in either case) is an ordered ring that is order-isomorphic to $\R$.

The same is true for ideals $I$ of $\R^{\upomega}$.  Indeed, suppose $x$ and $y$ in $\R^{\upomega}$ are positive or zero (that is, $x_i\geq0$ and $y_i\geq0$ in each case), and $x+y\in I$.  Since
\begin{equation*}
x_i+y_i=0\implies x_i=0,
\end{equation*}
it follows that $x\in I$.  Indeed, under the hypothesis, $x=(x+y)z$, where
\begin{equation*}
z_i=\begin{cases}
	x_i/(x_i+y_i),&\text{ if }x_i+y_i\neq0,\\
	0,&\text{ if }x_i+y_i=0.
\end{cases}
\end{equation*}
Thus $\R^{\upomega}/I$ is ordered.

Now let $M$ be a maximal ideal of $\R^{\upomega}$.  We want to show that the ordering of $\R^{\upomega}/M$ is \emph{linear.}  For every $a$ in $\R^{\upomega}$, we have $a+M\geq0$ if and only if there is $b$ in $M$ such that $a+b\geq0$, that is, $a_i+b_i\geq0$ in each case.  If there is such an element $b$ of $M$, it meets the condition
\begin{equation*}
b_i=0\implies a_i\geq0.
\end{equation*}
In this case, replacing $b$ with an appropriate product $bc$, we may assume
\begin{equation}\label{eqn:>}
b_i=0\iff a_i\geq0.
\end{equation}
Moreover, this condition on an element $b$ of $M$ is sufficient---not to ensure that $a+b\geq0$, but to ensure that $a+d\geq0$ for \emph{some} $d$ in $M$.  This $d$ could be $e\cdot b$, where, if $b_i\neq0$, so that $a_i<0$, then
\begin{equation*}
e_i=\frac{-2a_i}{b_i}.
\end{equation*}
We can see now that the following are equivalent:
\begin{compactitem}
\item
$a+M\geq0$.
\item
$M$ has an element $b$ such that \eqref{eqn:>} holds.
\item
$M$ contains every element $b$ of $\R^{\upomega}$ such that \eqref{eqn:>} holds.
\end{compactitem}
Suppose one of these conditions fails.  Then there is some $b$ in $\R^{\upomega}\setminus M$ such that \eqref{eqn:>} holds.  In this case, since $M$ is maximal,
\begin{equation*}
M+(b)=\R^{\upomega}.
\end{equation*}
In particular, $(1,1,1,\dots)\in M+(b)$.
Hence $M$ has an element $c$ such that
\begin{equation*}
b_i=0\implies c_i\neq0,
\end{equation*}
that is,
\begin{equation*}
a_i\geq0\implies c_i\neq0.
\end{equation*}
As before, by replacing $c$ with a multiple of it, so that $c_i=0$ when $a_i<0$, we may assume
\begin{equation*}
a_i\geq0\iff c_i\neq0;
\end{equation*}
indeed, $M$ contains \emph{every} such element $c$ of $\R^{\upomega}$.  Then not only does $M$ contain $c$ such that $a_i+c_i\neq0$ for all $i$ in $\upomega$, but it contains $c$ such that $a_i+c_i<0$ for all $i$ in $\upomega$.  Consequently $a+M<0$, under the assumption that $a+M$ is not positive.  Thus the ordering of $\R^{\upomega}/M$ is linear.

\section{Non-standard analysis}\label{sect:nsa}

Suppose now $M$ is a \emph{non-principal} maximal ideal of $\R^{\upomega}$.  If $m\in\N$, we want to show finally
\begin{equation*}
(1,2,3,\dots)+M>(m,m,m,\dots)+M,
\end{equation*}
that is,
\begin{equation*}
(1-m,2-m,3-m,\dots,-1,0,1,2,3,\dots)+M>0.
\end{equation*}
It is enough to show that $M$ has an element $a$ such that
\begin{equation}\label{eqn:im}
i<m\implies a_i\neq0.
\end{equation}
Again, $M$ is maximal, but not principal.  In particular, it is not included in the principal maximal ideal generated by an element $(1,\dots,1,0,1,\dots)$.  Then for all $j$ in $\upomega$, $M$ has an element that is nonzero at $j$.  Therefore $M$ contains $\updelta^j$, where
\begin{equation*}
\updelta^j_i=\begin{cases}
	1,&\text{ if }i=j,\\
	0,&\text{ if }i\neq j.
\end{cases}
\end{equation*}
Then $M$ contains $\updelta^0+\dots+\updelta^{m-1}$, which is an element $a$ as desired in~\eqref{eqn:im}.

We may assume that $\Q$ is included in every ordered field.  An element of an ordered field that is greater than every element of $\Q$ is \textbf{infinite;} an element whose absolute value is less than every positive element of $\Q$ is \textbf{infinitesimal.}  We have now shown that $\R^{\upomega}/M$ has infinite elements.  Therefore it also has nonzero infinitesimal elements (namely the reciprocals of the infinite elements).  Thus the possibility is opened up of saying that a function $f$ from $\R$ to $\R$ is \emph{continuous} at $a$ if $f(a)-f(x)$ is infinitesimal whenever $a-x$ is infinitesimal.  

However, $\R$ itself contains no infinitesimals; so if $a\in\R$, but $a-x$ is infinitesimal, then $x\notin\R$.  However, $x$ might be in $\R^{\upomega}/M$.  So we want to extend $f$ to a function $\st f$ on $\R^{\upomega}/M$.  It is obvious how to do this:  If $a\in\R^{\upomega}$, then we should define
\begin{equation*}
\st f(a+M)=(f(a_i)\colon i\in\upomega)+M.
\end{equation*}
However, we must check that such a function $\st f$ exists: we must show
\begin{equation*}
a+M=b+M\implies(f(a_i)\colon i\in\upomega)+M=(f(b_i)\colon i\in\upomega)+M,
\end{equation*}
or rather
\begin{equation*}
a-b\in M\implies(f(a_i)-f(b_i)\colon i\in\upomega)\in M.
\end{equation*}
But this is true since
\begin{equation*}
a_i-b_i=0\implies f(a_i)-f(b_i)=0,
\end{equation*}
so that, as before, $(f(a_i)-f(b_i)\colon i\in\upomega)$ is a multiple of $a-b$.

We have been using implicitly (or proving special cases of) the lemma that if
\begin{equation*}
a_i=0\implies b_i=0
\end{equation*}
and $a\in M$, then $b\in M$.  For an arbitrary element $a$ of $\R^{\upomega}$, we define
\begin{equation*}
\supp a=\{i\in\upomega\colon a_i\neq0\}.
\end{equation*}
Let us now write $\mathfrak m$ for $\Supp M$; that is,
\begin{equation*}
\mathfrak m=\{\supp x\colon x\in M\}.
\end{equation*}
Then $M$ is determined by $\mathfrak m$, and moreover
\begin{equation*}
M=\{x\in\R^{\upomega}\colon\supp x\in\mathfrak m\}.
\end{equation*}
The subset $\mathfrak m$ of $\pow{\upomega}$ has the following properties:
\begin{gather*}
\emptyset\in\mathfrak m,\\
	X\included Y\And Y\in\mathfrak m\implies X\in\mathfrak m,\\
	X\in\mathfrak m\And Y\in\mathfrak m\implies X\cup Y\in\mathfrak m.
\end{gather*}
Indeed, the first of these properties follows because $0\in M$.  The second is by the lemma just mentioned.  For the third, if $\supp a=X$ and $\supp b=Y$, then $\supp{c\cdot b}=Y\setminus X$ for some $c$, and then
\begin{equation*}
\supp{a+c\cdot b}=X\cup Y.
\end{equation*}

Let us write $\mathfrak u$ for $\pow{\upomega}\setminus\mathfrak m$.  Then we have
\begin{gather*}
\upomega\in\mathfrak u,\\
	X\included Y\And X\in\mathfrak u\implies Y\in\mathfrak u,\\
	X\in\mathfrak u\And Y\in\mathfrak u\implies X\cap Y\in\mathfrak u.
\end{gather*}
Finally,
\begin{equation*}
X\in\mathfrak m\iff X\notin\mathfrak u.
\end{equation*}
Elements of $\mathfrak m$ will be called \textbf{small;} elements of $\mathfrak u$, \textbf{large.}  If $a+M=b+M$, that is, $a-b\in M$, this means $\supp{a-b}\in\mathfrak m$, that is, $a$ and $b$ differ on a small subset of $\upomega$, but they agree on a large subset of $\upomega$.  Then the same is true of $(f(a_i)\colon i\in\upomega)$ and $(g(a_i)\colon i\in\upomega)$.  Thus there is a well-defined function $\st f$ as above.

Much more now follows.  For example, $\R^{\upomega}/M$ is \textbf{real-closed,} that is, it satisfies the Intermediate Value Theorem for polynomial functions.  Indeed, suppose $p$ is a polynomial (in one variable) with coefficients from $\R^{\upomega}/M$ such that, for some $a$ and $b$ in $\R^{\upomega}/M$, we have $p(a)<0$ and $p(b)>0$.  We may assume $a<b$.  It follows that
\begin{equation*}
\{i\colon a_i<b_i\}\in\mathfrak u.
\end{equation*}
The value $p(a)$ of $p$ at $a$ can be written as $(p_i(a_i)\colon i\in\upomega)$, where $p_i$ is obtained from $p$ by replacing its coefficients with their values at $i$.  Then the sets $\{i\colon p_i(a_i)<0\}$ and $\{i\colon p_i(b_i)>0\}$ are large, and therefore their intersection is large, and therefore (by the usual Intermediate Value Theorem for $\R$) there are $c_i$ between $a_i$ and $b_i$ for a large set of $i$ such that $p_i(c_i)=0$.  Choosing $c_i$ for the other $i$ arbitrarily, we have $a<c<b$, and $p(c)=0$.

In model-theoretic terms, $\R^{\upomega}/M$ is an \emph{elementary extension} of $\R$.  This is a special case of a general theorem, \L o\'s's Theorem, which is fairly easy to prove, once one understands what it is all about.  The theorem itself is Theorem \ref{thm:Los} on page \pageref{thm:Los} below; the pages before then are preparation for it.  First we shall generalize the fields of the present chapter to arbitrary \emph{structures.}

\chapter{Model theory}

\section{Theories and models}

If $n\in\upomega$, then on a set $A$, an \textbf{$n$-ary relation} on $A$ is just a subset of $A^n$; an \textbf{$n$-ary operation} on $A$ is a function from $A^n$ to $A$.  Since $A^0=\{0\}$, so that a function on $A^0$ takes only one value, a $0$-ary or \emph{nullary} operation on $A$ can be considered as an element of $A$.  Much of mathematics is a study of operations and relations on sets.  Group-theory is a study of binary operations with certain properties; field-theory, \emph{two} binary operations; lattice-theory, a binary relation.\footnote{This is (nearly?) all that I shall say about \emph{examples} in this chapter, despite the intention stated in the Preface to emphasize examples.  Perhaps model-theory as a branch of mathematics can be characterized as \emph{not} being about particular examples, but being an abstraction from them.  In any case, the subject of these notes is not model-theory as such, but ultraproducts.}  A particular nonempty set,\footnote{It simplifies things to require the set to be nonempty, although one can certainly define empty structures if one wishes, and sometimes this is useful.} considered together with certain operations and relations on it, is called a \textbf{structure.}  If the set is $A$, $B$, or $C$, then the structure might be denoted respectively by $\str A$, $\str B$, or $\str C$.  The distinguished operations and relations of $\str A$ are denoted by certain symbols, which constitute the \textbf{signature} of $\str A$.  The \textbf{universe} of $\str A$ is just the set $A$.

More than one structure can share the same signature.  For example, the signature of fields is $\{0,1,-,+,\cdot\}$; of ordered fields, $\{0,1,-,+,\cdot,<\}$ (or $\{0,1,-,+,\cdot,\leq\}$).  In general, if $\sig$ is a signature, then the class of all structures with this signature can be denoted by
\begin{equation*}
\Mod.
\end{equation*}
If $\str A\in\Mod$, and $s\in\sig$, then, to avoid ambiguity, the operation or relation on $A$ that is denoted in $\str A$ by $s$ can also be denoted by
\begin{equation*}
s^{\str A}.
\end{equation*}
A symbol in a signature is more precisely
\begin{compactitem}
\item
an \textbf{$n$-ary predicate,} if it denotes an $n$-ary relation, or
\item
an \textbf{$n$-ary operation-symbol.} 
\end{compactitem}
The symbol for a nullary operation (that is, element) can be called a \textbf{constant.}  The same symbol will never denote, say, an element of one set, but a binary relation on another set.

If $\sig$ is a signature, then the \emph{terms} of $\sig$ are built up from the operation-symbols in $\sig$, along with \emph{(individual) variables.}  The \emph{formulas} of $\sig$ are then built up from the terms and predicates of $\sig$, along with logical symbols such as $\lnot$, $\land$, and $\exists$ (and brackets, if needed).  A term is merely a recipe for obtaining new operations through composition of some given operations.  (The coordinate projections are always understood as given.)  Then a formula is a recipe for obtaining new relations through set-theoretic manipulations of given operations and relations.  We shall review the formal definition of terms and formulas in the next section.

An occurrence of a variable in a formula of $\sig$ will be either \emph{free} or \emph{bound.}  If precisely the variables $x_0$, \dots, $x_{n-1}$ occur freely in a formula $\phi$ of $\sig$, then $\phi$ can be written as $\phi(x_0,\dots,x_{n-1})$ or $\phi(\vec x)$.  If $\str A\in\Mod$, and $\vec a\in A^n$, then $\phi(\vec a)$ is the result of replacing each free occurrence of $x_i$ in $\phi$ with $a_i$, for each $i$ in $n$.  This new formula $\phi(\vec a)$ may not be a formula of $\sig$; but it is a formula of $\sig(A)$, which is just $\sig$ along with a constant for each element of $A$.  Such constants are often called \textbf{parameters.}  The new formula $\phi(\vec a)$ is a \textbf{sentence,}\label{sentence} because it has no free variables.  This sentence will be either true or false in $\str A$; if it is true, then we shall write
\begin{equation*}
\str A\models\phi(\vec a).
\end{equation*}
The symbol $\models$ thus stands for a relation in a more general sense: it is not a binary relation on a set, but it is a relation between certain structures and certain sentences.  We might call this the \textbf{satisfaction} relation.  (However, if $\str A\models\phi(\vec a)$, it might be said that $\vec a$ \emph{satisfies} $\phi$ in $\str A$.)

The set of all sentences of $\sig$ can be denoted by
\begin{equation*}
\Sn.
\end{equation*}
If $\Gamma\included\Sn$, and every sentence in $\Gamma$ is true in $\str A$, then we write
\begin{equation*}
\str A\models\Gamma;
\end{equation*}
in this case, $\str A$ is a \textbf{model} of $\Gamma$.  We can define
\begin{equation}\label{eqn:mod}
\Mod[\Gamma]
=\{\str A\in\Mod\colon\str A\models\Gamma\}
=\bigcap_{\sigma\in\Gamma}\{\str A\in\Mod\colon\str A\models\sigma\};
\end{equation}
a class of structures of this form is called an \textbf{elementary class.}  If $\mathcal K\included\Mod$, then we define
\begin{equation}\label{eqn:th}
\Th{\mathcal K}=\bigcap_{\str A\in\mathcal K}\{\sigma\in\Sn\colon\str A\models\sigma\};
\end{equation}
a set of sentences of this form is called a \textbf{theory.}  Both theories and elementary classes are defined in the same way, as intersections of sets defined in terms of the satisfaction relation $\models$.  Therefore it turns out that there is a one-to-one correspondence between elementary classes and theories.  This is a kind of \emph{Galois correspondence}; see \S\ref{sect:Gal} (and before that, \eqref{eqn:zl} on page \pageref{eqn:zl}).  

If $\mathcal K=\{\str A\}$, then $\Th{\mathcal K}$ can be written as
\begin{equation*}
\Th{\str A}.
\end{equation*}
Such a theory is a \textbf{complete theory,} namely a theory that, for every sentence $\sigma$ if its signature, contains either $\sigma$ or its negation $\lnot\sigma$, but not both.  For an arbitrary subclass $\mathcal K$ of $\Mod$, if $\Th{\mathcal K}$ contains both $\sigma$ and $\lnot\sigma$, then $\mathcal K$ must be empty, so
\begin{equation*}
\Th{\mathcal K}=\Sn.
\end{equation*}
Suppose now $\Th{\mathcal K}$ is complete.   Then $\mathcal K$ contains some $\str A$, and then, since
\begin{equation*}
\Th{\mathcal K}\included\Th{\str A}\pincluded\Sn,
\end{equation*}
the first inclusion must be an equation.  Thus the complete theories are precisely the theories of individual structures.  However, there are proper classes\footnote{That is, classes that are not sets, because they are `too large'.} of structures whose theories are complete.  For example, the theory of algebraically closed fields of characteristic $0$ is complete (Theorem \ref{thm:ACF_0} on page \pageref{thm:ACF_0}).

If $\Th{\str A}=\Th{\str B}$, then $\str A$ and $\str B$ are said to be \textbf{elementarily equivalent,} and we write
\begin{equation*}
\str A\equiv\str B.
\end{equation*}
If $\str A$ and $\str B$ are \emph{isomorphic} in the familiar sense,
then (trivially) they are elementarily equivalent.  However, by what we have just observed about complete theories, the converse fails: non-isomorphic
structures can be elementarily equivalent.  This is easily shown with
the Compactness Theorem, which we shall prove as
Theorem~\ref{thm:compact} by using ultraproducts.  Also, a
non-principal ultrapower of an infinite structure is elementarily
equivalent, but not isomorphic, to that structure.  See also
\S\ref{sect:Skolem}. 

\section{Definable relations}

We are usually interested in $\Mod[T]$ for particular theories $T$ of a signature $\sig$.  One way to study this is to study the \emph{definable relations} in elements of $\Mod[T]$.  Suppose $\str A$ is one of these elements, and $\phi$ is an $n$-ary formula of $\sig$.   Then $\phi$ defines the subset
\begin{equation*}
\{\vec a\in A^n\colon\str A\models\phi(\vec a)\}
\end{equation*}
of $A^n$.  This subset, denoted by one of
\begin{align*}
&\phi^{\str A},&&\phi(\str A),
\end{align*}
 is more precisely a \textbf{$0$-definable relation} of $\str A$.  If $B\included A$, and $\phi$ is a formula of $\sig(B)$, then $\phi^{\str A}$ is a \textbf{$B$-definable relation} of $\str A$.

\subsection{Terms}

The \textbf{terms} of $\sig$ are defined recursively as follows.
\begin{compactenum}
\item
Every variable is a term: we use variables $x_i$, where $i\in\upomega$.  These variables are more precisely called \textbf{individual variables,} because they stand for individual elements of sets.
\item
For all $n$ in $\upomega$, if $F$ is an $n$-ary operation-symbol of $\sig$, and $t_0$, \dots, $t_{n-1}$ are terms of $\sig$, then the string
\begin{equation*}
Ft_0\cdots t_{n-1}
\end{equation*}
is a term of $\sig$.  In particular, if $n=0$, so that $F$ is a constant, then, standing by itself, it is a term. 
\end{compactenum}
This recursive definition allows theorems about all terms to be proved by \emph{induction.}  A trivial example is that every term that is not a variable begins with an operation-symbol (possibly a constant); slightly less trivial is that every term ends with a variable or a constant.

We also want to be able to define functions recursively on the set of terms (of a given signature).  This requires knowing that every term is \textbf{uniquely readable:} it can be constructed in only one way.  For example, we want to have that, if $\str A\in\Mod$, then the terms $t$ of $\sig$ that use only variables from the set $\{x_i\colon i<n\}$ can be understood as $n$-ary operations $t^{\str A}$ on $A$ as follows:
\begin{gather*}
x_i{}^{\str A}(\vec a)=a_i,\\
Ft_0\cdots t_{n-1}{}^{\str A}(\vec a)=F^{\str A}(t_0{}^{\str A}(\vec a),\dots,t_{n-1}{}^{\str A}(\vec a)).
\end{gather*}
This is a valid definition, only if we know that $Ft_0\dots t_{n-1}$ cannot also be analyzed as $Fu_0\dots u_{n-1}$ for some terms $u_i$, where in at least one case $u_i$ is not $t_i$.  But this is true: $Ft_0\dots t_{n-1}$ cannot be otherwise analyzed.  Perhaps the simplest way to prove it is by means of a lemma, proved by induction: every term neither \emph{is} a proper initial segment of another term, nor \emph{has} a proper initial segment that is a term.

\subsection{Formulas}\label{subsect:formulas}

The \textbf{atomic formulas} of $\sig$ are of two kinds: \textbf{equations,} which take the form
\begin{equation*}
t=u,
\end{equation*}
where $t$ and $u$ are terms of $\sig$; and expressions of the form
\begin{equation*}
Rt_0\cdots t_{n-1},
\end{equation*}
where $n\in\upomega$, $R$ is an $n$-ary predicate in $\sig$, and the $t_i$ are terms of $\sig$.  Then the \textbf{formulas} of $\sig$ in general are defined recursively:
\begin{compactenum}
\item
Atomic formulas are formulas.
\item
If $\phi$ and $\psi$ are formulas, then so are $\lnot\phi$ and $(\phi\land\psi)$.
\item
If $\phi$ is a formula and $x$ is a variable, then $\Exists x\phi$ is a formula.
\end{compactenum}
Because this definition (like that of terms) is recursive, induction can be used to prove that certain sets of formulas of $\sig$ contain \emph{all} formulas of $\sig$.  For example, induction will be used to establish the lemma called the Tarski--Vaught Test on page \pageref{TV} below.  However, that lemma also involves \emph{truth,} which can be understood formally as a function defined recursively on the set of all formulas of $\sig$.  (See the next subsection.)  As with terms, for such a definition to be valid, unique readability of formulas must be established: every formula is built up from its \textbf{subformulas,} but this can happen in only one way.  

An occurrence of a variable $x$ in a formula is \textbf{free,} unless this occurrence is in a subformula of the form $\Exists x\phi$: then the occurrrence is \textbf{bound.}  This definition would be possible without unique readability, but it would not then be particularly useful.

There are some standard abbreviations:
\begin{gather*}
(\phi\lor\psi)\text{ means }\lnot(\lnot\phi\land\lnot\psi);\\
(\phi\lto\psi)\text{ means }(\lnot\phi\lor\psi);\\
(\phi\liff\psi)\text{ means }((\phi\lto\psi)\land(\psi\lto\phi));\\
\Forall x\phi\text{ means }\lnot\Exists x\lnot\phi.
\end{gather*}
It is possible to remove some parentheses from formulas without
ambiguity,\label{precedence} if it is understood for example that
$\land$ and $\lor$ take precedence over $\lto$ and $\liff$, and of two
instances of $\lto$, the one on the right takes precedence.  Also
outer parentheses can be removed. 


\subsection{Truth}

Now \emph{sentences} are defined as before (p.\ \pageref{sentence}), as formulas with no free variables; and we can now define truth of sentences in structures.  Assuming $t$, $u$, and the $t_i$ are terms with no variables, and $\sigma$ and $\tau$ are sentences, but $\phi$ is formula with the unique free variable $x$, we have
\begin{gather*}\label{truth}
\str A\models t=u\iff t^{\str A}=u^{\str A},\\
\str A\models Rt_0\cdots t_{n-1}\iff(t_0{}^{\str A},\dots,t_{n-1}{}^{\str A})\in R^{\str A},\\
	\str A\models\lnot\sigma\iff \str A\nmodels\sigma,\\
	\str A\models\sigma\land\tau\iff \str A\models\sigma\And \str A\models\tau,\\
\str A\models\Exists x\phi(x)\iff\text{ for some $b$ in $A$, }\str A\models\phi(b).
 \end{gather*}
Note here that the expressions $\And$ and $\iff$ are not parts of formulas; they are abbreviations of the English \emph{and} and \emph{if and only if.}  We can understand our definition as follows.  Given the structure $\str A$ in $\Mod$, we have now recursively defined, on the set of formulas of $\sig(A)$, the function $\phi\mapsto\phi^{\str A}$, where, if $\phi$ is $n$-ary, we have
  \begin{equation*}
\phi^{\str A}=\{\vec a\in A^n\colon\str A\models\phi(\vec a)\}.
\end{equation*}
It is worthwhile to note that as $\phi$ varies here, $\phi^{\str A}$ ranges over a subset of $A^n$ with some natural closure properties; and as $n$ varies as well, there are still some good closure properties.  Section \ref{sect:def} is an investigation of these.  Before that (as well as later), it is useful to have the notion of \emph{substructure,} developed in the next section.


\section{Substructures}

$\str B\in\Mod$, and $A\included B$, and $A$ is closed under the operations of $\str B$, then $A$ is the universe of a \textbf{substructure} of $\str B$.  This substructure is $\str A$, where
\begin{gather*}
	R^{\str A}=A^n\cap R^{\str B},\\
	F^{\str A}=F^{\str B}\restriction A^n
\end{gather*}
for all $n$-ary predicates $R$ and operation-symbols $F$ of $\sig$, for all $n$ in $\upomega$.  In this case, we write
\begin{equation*}
\str A\included\str B.
\end{equation*}
It follows that, if $\str A$ and $\str B$ are two structures with the same signature $\sig$, and $A\included B$, then $\str A\included\str B$ if and only if, for all $n$ in $\upomega$, for all $n$-ary quantifier-free formulas $\phi$ of $\sig$, for all $\vec a$ in $A^n$,
\begin{equation}\label{eqn:sub}
\str A\models\phi(\vec a)\iff\str B\models\phi(\vec a).
\end{equation}

Suppose now there is just a function $h$ from $A$ to $B$.  Then $h$ is an \textbf{embedding} of $\str A$ in $\str B$ if $h$ is an isomorphism from $\str A$ to a substructure of $\str B$.  In any case, the \textbf{diagram} of $\str A$, denoted by
\begin{equation*}
\diag{\str A},
\end{equation*}
is the set of \emph{quantifier-free} sentences of $\sig(A)$ that are true in $\str A$.  When we consider $\str A$ as having signature $\sig(A)$, we may write the structure as
\begin{equation*}
\str A_A.
\end{equation*}
This is an \textbf{expansion} of $\str A$ to $\sig(A)$; and $\str A$ is then the \textbf{reduct} of $\str A_A$ to $\sig$.  Now $\str B_{h[A]}$ can also be understood as having signature $\sig(A)$.  In this case, the map $h$ above is an embedding if and only if
\begin{equation*}
\str B_{h[A]}\models\diag{\str A}.
\end{equation*}
Thus the structures in which $\str A$ embeds are precisely (the reducts to $\sig$ of) the models of $\diag{\str A}$.


A theory $T$ of $\sig$ is \textbf{axiomatized} by a subset $\Gamma$ of $\Sn$ if
\begin{equation*}
T=\Th{\Mod[\Gamma]},
\end{equation*}
equivalently, every model of $\Gamma$ is a model of $T$.

A \textbf{universal} formula is a formula of the form $\Forall{\vec x}\phi$, where $\phi$ is quantifier-free.  If $T$ is a theory, then we denote by
\begin{equation*}
T_{\forall}
\end{equation*}
the theory axiomatized by the universal sentences in $T$.

\begin{lemma}\label{lem:TA}
$T_{\forall}$ is included in the theory of substructures of models of $T$, that is,
\begin{equation*}
\str A\included\str B\And\str B\models T\implies\str A\models T_{\forall}.
\end{equation*}
\end{lemma}

\begin{proof}
Suppose $\phi$ is quantifier-free, and $\Forall{\vec x}\phi$ is in $T$.  If $\vec a\in A^n$, then $\vec a\in B^n$, so $\str B\models\phi(\vec a)$ and therefore, by \eqref{eqn:sub}, $\str A\models\phi(\vec a)$.  Thus $\str A\models\Forall{\vec x}\phi$.
\end{proof}

The converse is given in Theorem \ref{thm:TA} on page \pageref{thm:TA} below.  


If \eqref{eqn:sub} holds for \emph{all} formulas $\phi$ of $\sig$, then $\str A$ is called an \textbf{elementary substructure} of $\str B$, and we write
\begin{equation*}
\str A\preccurlyeq\str B.
\end{equation*}
A map $h$ from $A$ to $B$ is an \textbf{elementary embedding} of $\str A$ in $\str B$ if $h$ is an isomorphism from $\str A$ to an elementary substructure of $\str B$.  Thus the structures in which $\str A$ embeds elementarily are precisely (the reducts to $\sig$ of) the models of $\Th{\str A_A}$.


A theory $T$ of a signature $\sig$ is called \textbf{model-complete}\label{mc} if for all models $\str A$ of $T$, the theory of $\sig(A)$ axiomatized by $T\cup\diag{\str A}$ is complete.

\begin{theorem}
A theory is model-complete if and only if, for all of its models $\str A$ and $\str B$,
\begin{equation*}
\str A\included\str B\implies\str A\preccurlyeq\str B.
\end{equation*}
\end{theorem}

\begin{proof}
Each condition is equivalent to the condition that, for all models $\str A$ of $T$, $T\cup\diag{\str A}$ axiomatizes $\Th{\str A_A}$.
\end{proof}



The theorem below is a generalization of the theorem published by
L\"owenheim in 1915 \cite{Lowenheim} and improved by Skolem in 1920
\cite{Skolem-LS}: a sentence with a model has a countable model.
Skolem's argument uses what we shall call the \emph{Skolem normal
  form} of the given sentence; we shall discuss this in
\S\ref{sect:arb}.  Meanwhile, an example is $\Forall x\Exists yRxy$.
If this has a model $\str A$, then there is a singulary operation
$x\mapsto x^*$ on $A$ such that 
\begin{equation*}
\str A\models\Forall x Rxx^*.
\end{equation*}
If $b\in A$, we can define $(b_k\colon k\in\upomega)$ recursively by
\begin{align*}
b_0&=b,&b_{k+1}=b_k{}^*.
\end{align*}
Then $\{b_k\colon k\in\upomega\}$ is countable and is the universe of a substructure of $\str A$ in which $\Forall x\Exists yRxy$ is true.  Our own proof of the general theorem will follow the lines of Skolem's idea; the following lemma will allow us to work in the general situation.

\begin{lemma}[Tarski--Vaught Test]\label{TV}
Suppose $\str A\included\str B$, both having signature $\sig$.  Then $\str A\preccurlyeq\str B$, provided that, for all singulary formulas $\phi$ of $\sig(A)$,
\begin{equation*}
\str B\models\Exists x\phi(x)\implies\text{ for some $c$ in $A$, } \str B\models\phi(c),
\end{equation*}
that is,
\begin{equation*}
\phi^{\str B}\neq\emptyset\implies\phi^{\str B}\cap A\neq\emptyset.
\end{equation*}
\end{lemma}

\begin{proof}
Under the given condition, we show by induction that for all formulas $\phi$ of $\sig$, if $\phi$ is $n$-ary and $\vec a\in A^n$, then
\begin{equation*}
\str A\models\phi(\vec a)\iff\str B\models\phi(\vec a).
\end{equation*}
This is given to be the case when $\phi$ is atomic (or more generally quantifier-free), and it is easily preserved under negation and conjunction.  Suppose it holds when $\phi$ is an $(m+1)$-ary formula $\psi$.  By hypothesis, for all $\vec a$ in $A^n$, the following are equivalent:
\begin{gather*}
	\str B\models\Exists y\phi(\vec a,y),\\
	\text{for some $b$ in $B$, } \str B\models\phi(\vec a,b),\\
	\text{for some $b$ in $A$, } \str B\models\phi(\vec a,b),\\
	\text{for some $b$ in $A$, } \str A\models\phi(\vec a,b),\\
	\str A\models\Exists y\phi(\vec a,y).
\end{gather*}
This completes the induction.
\end{proof}

\begin{theorem}[Downward L\"owenheim--Skolem--Tarski]\label{thm:dLST}
If $\str B\in\Mod$, $\max(\abs{\sig},\upomega)\leq\abs B$, and $X\included B$, there is a structure $\str A$ such that
\begin{align*}
	\str A&\preccurlyeq\str B,&
	X&\included A,&
	\abs A&\leq\kappa,
\end{align*}
where $\kappa=\max(\abs X,\abs{\sig},\upomega)$.
\end{theorem}

\begin{proof}
There is a subset $X'$ of $B$ of cardinality no greater than $\kappa$ such that, for every singulary formula $\phi$ of $\sig(X)$, if $\phi^{\str B}$ is non-empty, then it has an element in $X'$.  By considering formulas $a=x$, where $a\in X$, we see $X\included X'$.  Now we can form $X''$, and so forth; and we can let
\begin{equation*}
A=X\cup X'\cup X''\cup\dots
\end{equation*}
By considering formulas $F\vec x=y$, we see that $A$ is the universe of a substructure $\str A$ of $\str B$.  It is of the required cardinality, and by the Tarski--Vaught Test, it is an elementary substructure of $\str B$.
\end{proof}


  





\chapter{Ultraproducts and \L o\'s's Theorem}%\label{sect:up}

\section{Ideals and filters}\label{sect:id-fil}

For every set $\Omega$, the power-set $\pow{\Omega}$ is a \emph{ring} in which
\begin{compactitem}
\item
sums are symmetric differences: $+$ is $\symdiff$;
\item
products are intersections: $\cdot$ is $\cap$;
\item
the additive identity is the empty set: $0$ is $\emptyset$;
\item
every element is its own additive inverse: $-X$ is just $X$;
\item
the multiplicative identity is the whole set: $1$ is $\Omega$.
\end{compactitem}
It is easy to check this.  We note first:
\begin{align*}
X\symdiff Y&=Y\symdiff X,&
X\symdiff(Y\symdiff Z)&=(X\symdiff Y)\symdiff Z,&
\end{align*}
(see Figure~\ref{fig:symdiff})
\begin{figure}[ht]
\psset{unit=5mm,linewidth=1pt,fillstyle=solid}
\mbox{}\hfill
\begin{pspicture}(-3,-2.866)(3,2)
  \pscustom[fillcolor=gray]{%
\psarc(1,0)2{-120}{120}
\psarc(-1,0)2{60}{300}}
\pscustom[fillcolor=white]{%
\psarc(-1,0)2{-60}{60}
\psarc(1,0)2{120}{240}}
\end{pspicture}
\hfill
\begin{pspicture}(-3,-2)(3,3.73)
\pscustom[fillcolor=gray]{%
\psarc(-1,0){2}{120}{300}
\psarc(1,0)2{-120}{60}
\psarc(0,1.73)20{180}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pscustom[fillcolor=white]{%
\psarc(0,1.73)2{180}{240}
\psarc(1,0)2{180}{240}
\psarc(-1,0)2{-60}0
\psarc(0,1.73)2{-60}0
\psarc(1,0)2{60}{120}
\psarc(-1,0)2{60}{120}}
%%%%%%%%%%%%%%%%%%%%%%%%%%
\pscustom[fillcolor=gray]{%
\psarc(1,0)2{120}{180}
\psarc(0,1.73)2{-120}{-60}
\psarc(-1,0)20{60}}
\end{pspicture}
\hfill\mbox{}
\caption{Symmetric differences of two sets and three sets}\label{fig:symdiff}
\end{figure}
 and
\begin{align*}
X\symdiff\emptyset&=X,&X\symdiff X&=\emptyset.
\end{align*}
So $(\pow{\Omega},\symdiff,\emptyset)$ is an abelian group in which every element is its own inverse.  (That is, it is an abelian group of exponent $2$.  It is a standard exercise to show that every group of exponent $2$ is abelian.)
As for multiplication, we have
\begin{gather*}
	X\cap(Y\cap Z)=(X\cap Y)\cap Z,\\
	X\cap Y=Y\cap X,\\
	X\cap\Omega=X,\\
	X\cap(Y\symdiff Z)=X\cap Y\symdiff X\cap Z,
\end{gather*}
where multiplication $\cap$ takes notational precedence over addition $\symdiff$ in the line; see Figure \ref{fig:dist}.
\begin{figure}[ht]
\psset{unit=5mm,linewidth=1pt,fillstyle=solid}
\mbox{}\hfill
\begin{pspicture}(-3,-2)(3,2)
  \pscustom[fillcolor=gray]{%
\psarc(1,0)2{-120}{120}
\psarc(-1,0)2{60}{300}}
\pscustom[fillcolor=white]{%
\psarc(-1,0)2{-60}{60}
\psarc(1,0)2{120}{240}}
\end{pspicture}
\hfill
\begin{pspicture}(-3,-2)(3,3.73)
\pscustom[fillcolor=white]{%
\psarc(-1,0){2}{120}{300}
\psarc(1,0)2{-120}{60}
\psarc(0,1.73)20{180}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pscustom[fillcolor=gray]{%
\psarc(0,1.73)2{-60}0
\psarc(1,0)2{60}{120}
\psarc(-1,0)2{60}{120}
\psarc(0,1.73)2{180}{240}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pscustom[fillcolor=white]{%
\psarc(1,0)2{180}{240}
\psarc(-1,0)2{-60}0}
%%%%%%%%%%%%%%%%%%%%%%%%%%
\pscustom[fillcolor=white]{%
\psarc(1,0)2{120}{180}
\psarc(0,1.73)2{-120}{-60}
\psarc(-1,0)20{60}}
\end{pspicture}
\hfill\mbox{}
\caption{Distribution in Boolean rings}\label{fig:dist}
\end{figure}
So $(\pow{\Omega},\symdiff,\cap,\emptyset,\Omega)$ is a ring (commutative and unital, as always in these notes).  We have in this ring also
\begin{equation*}
X\cap X=X.
\end{equation*}
That is, in the more usual notation of ring-theory, $\pow{\Omega}$ is a ring in which
\begin{equation}\label{eqn:x^2=x}
x^2=x.
\end{equation}
Therefore $\pow{\Omega}$ is called a \textbf{Boolean ring.}
We shall see in Chapter \ref{ch:Boole} that all of the algebraic properties of $\pow{\Omega}$ and its sub-rings follow from their being Boolean rings: the class of Boolean rings is precisely the class of rings that embed in rings of the form $\pow{\Omega}$.

This ring $\pow{\Omega}$ has ideals in the usual sense: a subset $I$ of $\pow{\Omega}$ in ideal if and only if
\begin{gather}\notag
	\emptyset\in I,\\\label{eqn:scaling}
	Y\in I\implies X\cap Y\in I,\\\label{eqn:adding}
X\in I\And Y\in I\implies X\symdiff Y\in I.	
\end{gather}
  However, since
\begin{gather*}
	X\cap Y\included Y,\\
	X\included Y\iff X\cap Y=X,
\end{gather*}
the condition \eqref{eqn:scaling} is equivalent to
\begin{equation*}
	X\included Y\And Y\in I\implies X\in I.
\end{equation*}
Since also
\begin{gather*}
	X\cup Y=X\symdiff Y\symdiff X\cap Y,\\
	X\symdiff Y\included X\cup Y,
\end{gather*}
we can replace the condition \eqref{eqn:adding} with
\begin{equation*}
X\in I\And Y\in I\implies X\cup Y\in I.
\end{equation*}
That is, a subset $I$ of $\pow{\Omega}$ is an ideal\label{ideal} if and only if
\begin{gather*}
\emptyset\in I,\\
	X\included Y\And Y\in I\implies X\in I,\\
X\in I\And Y\in I\implies X\cup Y\in I.
\end{gather*}
Thus ideals of $\pow{\Omega}$ are just those subsets that are
\begin{compactitem}
\item
downwardly closed,
\item
closed under finite unions.
\end{compactitem}
Indeed, taken strictly, the last condition implies non-emptiness, since $\emptyset$ is the finite union $\bigcup\emptyset$.  See Figure \ref{fig:ideal}.
\begin{figure}[ht]
\centering
\psset{unit=15mm}
\begin{pspicture}(-1,-2)(1,2)
%\psgrid
\psarc(-1,0)2{-60}{60}
\psarc(1,0)2{120}{240}
\pscustom[fillstyle=solid,fillcolor=gray]{%
\psline(0.6,-0.2)(0,0.4)(-0.6,-0.2)
\psset{linewidth=0pt}  % doesn't have the effect I want
\psarc(1,0)2{210}{240}
\psarc(-1,0)2{-60}{-30}
}
\psdots(0,-1.73)(0,1.73)(0.6,-0.2)(0,0.4)(-0.6,-0.2)
\uput[ur](0.6,-0.2){$Y$}
\uput[u](0,0.4){$X\cup Y$}
\uput[ul](-0.6,-0.2){$X$}
\uput[d](0,-1.73){$\emptyset$}
\uput[u](0,1.73){$\Omega$}
\end{pspicture}
\caption{An ideal of a Boolean ring}\label{fig:ideal}
\end{figure}
Our observations in \S\ref{sect:nsa} generalize to show that if $(K_i\colon i\in\Omega)$ is an indexed family of fields, and $J$ is an ideal of $\prod_{i\in\Omega}K_i$, then $\Supp J$ is an ideal of $\pow{\Omega}$.  Moreover, every ideal $I$ of $\pow{\Omega}$ is $\Supp J$, where
\begin{equation*}
J=\{x\in\prod_{i\in\Omega}K_i\colon\supp x\in I\};
\end{equation*}
and this is an ideal of $\prod_{i\in\Omega}K_i$, in fact the only ideal whose image under $J\mapsto\Supp J$ is $I$. So this map establishes a one-to-one correspondence between the (set of) ideals of $\prod_{i\in\Omega}K_i$ and the (set of) ideals of $\pow{\Omega}$.

There are two standard examples of ideals of $\pow{\Omega}$.
\begin{compactenum}
\item
If $A\included\Omega$, then $\pow A$ is the principal ideal of $\pow{\Omega}$ generated by $A$.  It corresponds to the ideal $\prod_{i\in A}K_i$ of $\prod_{i\in\Omega}K_i$.
\item
The set $\powf{\Omega}$\label{powfO} of finite subsets of $\Omega$ is an ideal of $\pow{\Omega}$, called the \textbf{Fr\'echet ideal} of $\pow{\Omega}$, corresponding to the ideal $\sum_{i\in\Omega}K_i$ of $\prod_{i\in\Omega}K_i$.
\end{compactenum}

There is a notion that is `dual' to the notion of an ideal:  A subset $F$ of $\pow{\Omega}$ is a \textbf{filter} if $\{X\comp\colon X\in F\}$ is an ideal, that is,
\begin{gather*}
\Omega\in F,\\
	X\in F\And X\included Y\implies Y\in F,\\
X\in F\And Y\in F\implies X\cap Y\in F.
\end{gather*}
See Figure \ref{fig:filter}.
\begin{figure}[ht]
\centering
\psset{unit=15mm}
\begin{pspicture}(-1,-2)(1,2)
%\psgrid
\psarc(-1,0)2{-60}{60}
\psarc(1,0)2{120}{240}
\pscustom[fillstyle=solid,fillcolor=gray]{%
\psline(0.6,0.2)(0,-0.4)(-0.6,0.2)
\psset{linewidth=0pt}  % doesn't have the effect I want
\psarcn(1,0)2{150}{120}
\psarcn(-1,0)2{60}{30}
}
\psdots(0,-1.73)(0,1.73)(0.6,0.2)(0,-0.4)(-0.6,0.2)
\uput[dr](0.6,0.2){$Y$}
\uput[d](0,-0.4){$X\cap Y$}
\uput[dl](-0.6,0.2){$X$}
\uput[d](0,-1.73){$\emptyset$}
\uput[u](0,1.73){$\Omega$}
\end{pspicture}
\caption{A filter of a Boolean ring}\label{fig:filter}
\end{figure}
Intuitively, elements of an ideal are `small' subsets of $\Omega$; elements of a filter are `large' subsets of $\Omega$.

Since filters easily correspond to ideals, we need not introduce the concept of a filter. Alternatively, once we have filters, we can forget about ideals.  I prefer not to forget about ideals, since they are familiar from ring-theory.  And yet sometimes it will be useful to think in terms of filters as well.  

A filter \emph{of} $\pow{\Omega}$ is also called a filter \textbf{on} $\Omega$ itself.

Suppose $P$ is a prime ideal of $\pow{\Omega}$, that is, $P$ is an ideal such that
\begin{equation*}
X\cap Y\in P\And X\notin P\implies Y\in P.
\end{equation*}
The quotient $\pow{\Omega}/P$ is then an integral domain.  But it is an integral domain in which \eqref{eqn:x^2=x} holds, that is, for all elements $x$,
\begin{align*}
x^2&=x,&0=x^2-x=x\cdot(x-1).
\end{align*}
In every integral domain, these equation is solved by $0$ and $1$, but by no other elements.
So $\pow{\Omega}/P$ has only two elements, namely $P$ and $\Omega+P$.  A two-element integral domain (even a two-element ring) is a field.  So $\pow{\Omega}/P$ is a field, and therefore $P$ is a maximal ideal.  Thus all prime ideals of $\pow{\Omega}$ are maximal.\label{prime-maximal}  Since in $\pow{\Omega}$ we have
\begin{equation*}
X\symdiff\Omega=X\comp,
\end{equation*}
we have that $X$ and $X\comp$ are always in different cosets of $P$, that is,
\begin{equation*}
X\in P\iff X\comp\notin P.
\end{equation*}
The filter $\{X\comp\colon X\in P\}$ that is dual to $P$ is called an \textbf{ultrafilter.}  As a filter, it is the set of complements (in $\Omega$) of elements of $P$; as an ultrafilter, it is the complement (in $\pow{\Omega}$) of $P$.

\section{Reduced products}\label{sect:red-prod}

Suppose $(\str A_i\colon i\in {\Omega})$ is an indexed family of structures with a
common signature $\sig$.  An element of the Cartesian product $\prod_{i\in {\Omega}}A_i$ is a tuple $(a_i\colon i\in {\Omega})$, where $a_i\in A_i$; we may write this tuple simply as $a$.  Let the product $\prod_{i\in {\Omega}}A_i$ be called also $B$.  This is the universe of a structure
\begin{equation*}
\prod_{i\in\Omega}\str A_i
\end{equation*}
or $\str B$ of $\sig$, where for all $n$ in $\upomega$, for all $n$-ary operation-symbols $F$ and predicates $R$ of $\sig$,
\begin{align*}
	F^{\str B}(\vec a)&=(F^{\str A_i}(\vec a_i)\colon i\in\Omega),&
	R^{\str B}&=\prod_{i\in\Omega}R^{\str A_i}.
\end{align*}
Here notation is as in \S\ref{sect:not}, so that $\vec a\in B^n$, which means $\vec a=(a^0,\dots,a^{n-1})$, where $a^k=(a^k_i\colon i\in\Omega)$; and $\vec a_i=(a^0_i,\dots,a^{n-1}_i)$.  See Figure \ref{fig:not}.
\begin{figure}[ht]
\begin{equation*}
\begin{array}{cccccc}
\vec a& &\vec a_0 &\vec a_1 &\vec a_2 &\dots\\
\shortparallel      & &\shortparallel&\shortparallel&\shortparallel&\\
   a^0&=&a^0_0    &a^0_1    &a^0_2    &\dots\\
\vdots& &\vdots   &\vdots   &\vdots   &\\   
%   a^j&=&a^j_0    &a^j_1    &a^j_2    &\dots\\
%\vdots& &\vdots   &\vdots   &\vdots   &\\   
   a^{n-1}&=&a^{n-1}_0    &a^{n-1}_1    &a^{n-1}_2    &\dots
\end{array}
\end{equation*}
\caption{Notation for sequences of tuples}\label{fig:not}
\end{figure}
Note that, if $R^{\str A_i}=\emptyset$ for even one index $i$, then $R^{\str B}=\emptyset$.

Now let $I$ be an ideal of $\pow{\Omega}$.  We shall define a quotient
\begin{equation*}
\prod_{i\in\Omega}\str A_i/I
\end{equation*}
or $\str B/I$.  First, we define two elements of $B$ to be \textbf{congruent} \emph{modulo} $I$ if they disagree only on a \emph{small} set of indices, that is, a set belonging to $I$:
\begin{equation*}
\{i\in {\Omega}\colon a_i\neq b_i\}\in I\iff
a\equiv b\pmod I.
\end{equation*}
Equivalently, if $F$ is the dual filter of $I$ (that is, $F=\{X\comp\colon X\in I\}$, then two elements of $B$ are congruent if and only if they agree on a \emph{large} set of indices, that is, a set belonging to $F$:
\begin{equation*}
\{i\in {\Omega}\colon a_i=b_i\}\in F\iff
a\equiv b\pmod I.
\end{equation*}
We may write:
\begin{compactitem}
\item
 $a/I$ for the congruence-class $\{b\colon a\equiv b\pmod I\}$,
 \item
 $B/I$ for the set of these congruence-classes,
 \item
 $\vec a/I$ for $(a^0/I,\dots,a^{n-1}/I)$.
\end{compactitem}
(Or one could write $F$ for $I$ here.)  We want to define a structure $\str B/I$ of $\sig$ with universe $B/I$.  Then for all $n$-ary operation-symbols $F$ of $\sig$, we should define
\begin{equation*}
F^{\str B/I}(\vec a/I)=F^{\str B}(\vec a)/I.
\end{equation*}
However, we must check that this is a valid definition.  We shall do this presently; meanwhile, for an $n$-ary predicate $R$ of $\sig$, what should $R^{\str B/I}$ be?  By one generalization of the definition in \S\ref{sect:of} of the ordering of $\R^{\upomega}/I$, we should define $R^{\str B/I}$ as
\begin{equation*}
\{\vec a/I\colon\vec a\in R^{\str B}\}.
\end{equation*}
However, by what we noted above, this relation is empty if $R^{\str A_i}=\emptyset$ for even one index $i$.  The empty relation is still a relation, but it is not what we want here.  The `correct' definition of $R^{\str B/I}$ is given as follows.

\begin{theorem}
For all indexed families $(\str A_i\colon i\in\Omega)$ of structures with common signature $\sig$, there is a structure $\str B/I$ in $\Mod$, with universe $\prod_{i\in\Omega}A_i/I$, such that
  all $n$ in $\upomega$, for all $n$-ary operation-symbols $F$ and
  predicates $R$ of $\sig$, 
\begin{align*}
	F^{\str B/I}(\vec a/I)&=F^{\str B}(\vec a)/I,
&	R^{\str B/I}&=\bigl\{\vec a/I\colon\{i\colon\vec a_i\notin R^{\str A_i}\}\in I\bigr\}.
\end{align*}
If $R^{\str A_i}\neq\emptyset$ for each $i$ in $\Omega$, then
\begin{equation*}
R^{\str B/I}=\{\vec a/I\colon\vec a\in R^{\str B}\}.
\end{equation*}
\end{theorem}

\begin{proof}
We need only check that the definition of $F^{\str B/I}$ is valid.  Suppose
\begin{equation*}
\vec a\equiv\vec b\pmod I,
\end{equation*}
that is, $\vec a/I=\vec b/I$, that is, $a^k/I=b^k/I$ for each $k$ in $n$.  This means $\{i\colon a^k_i\neq b^k_i\}\in I$ for each $k$ in $n$.  But then
\begin{equation*}
\bigcup_{k\in n}\{i\colon a^k_i\neq b^k_i\}\in I.
\end{equation*}
We have also
\begin{equation*}
\{i\colon F^{\str A_i}(\vec a_i)\neq F^{\str A_i}(\vec b_i\}\included\bigcup_{k\in n}\{i\colon a^k_i\neq b^k_i\},
\end{equation*}
so $\{i\colon F^{\str A_i}(\vec a_i)\neq F^{\str A_i}(\vec b_i)\}\in I$ and therefore 
\begin{equation*}
F^{\str B}(\vec a)\equiv F^{\str B}(\vec b)\pmod I.\qedhere
\end{equation*}
\end{proof}

The structure $\str B/I$ is a \textbf{reduced product} of the family $(\str A_i\colon i\in {\Omega})$.

We can understand each element $a$ of $\prod_{i\in {\Omega}}A_i$ as
a new constant, to be interpreted in each $\str
A_i$ as $a_i$, and in $\str B$ as $a/I$.
Then the definition
\begin{equation*}
R^{\str B/I}=\bigl\{\vec a/I\colon\{i\colon\vec a_i\notin R^{\str A_i}\}\in I\bigr\}
\end{equation*}
in the theorem just means
\begin{equation*}
\str B/I\models R\vec a\iff\{i\colon\str A_i\models\lnot R\vec a\}\in I,
\end{equation*}
and the definition
\begin{equation*}
F^{\str B/I}(\vec a/I)=F^{\str B}(\vec a)/I
\end{equation*}
has the meaning of
\begin{equation*}
\str B/I\models F\vec a=b\iff\{i\colon\str A_i\models\lnot(F\vec a=b)\}\in I.
\end{equation*}
The formulas $R\vec x$ and $F\vec x=y$ here are
\emph{unnested} atomic formulas. (So is $x=y$.)  Our equivalences have the form
\begin{equation}\label{g}
\str B/I\models\sigma\iff\{i\colon\str A_i\models\lnot\sigma\}\in I,
\end{equation}
which can be written also as
\begin{equation*}
\str B/I\models\sigma\iff\{i\colon\str A_i\models\sigma\}\in F.
\end{equation*}
So this is true by definition when $\sigma$ is an unnested atomic
sentence (in the expanded signature $\sig(B)$).  For which other $\sigma$ is it
true? 

\begin{lemma}\label{land}
The equivalence \eqref g, that is,
\begin{equation*}
\str B/I\models\sigma\iff\{i\colon\str A_i\models\lnot\sigma\}\in I,
\end{equation*}
considered as a function of $\sigma$, is preserved under conjunction: if it holds when $\sigma$ is $\tau$ or $\rho$, then it holds when $\sigma$ is $\tau\land\rho$.
\end{lemma}

\begin{proof}
From the definition of an ideal, we have
\begin{gather*}
X\included Y\And Y\in I\implies X\in I,\\
X\in I\And Y\in I\implies X\cup Y\in I.
\end{gather*}	
Together these imply the converse of the latter; so we have
\begin{equation*}
X\in I\And Y\in I\iff X\cup Y\in I.
\end{equation*}
If now \eqref g holds when $\sigma$ is $\tau$ or $\rho$, then the following are equivalent:
\begin{gather*}
\str B/I\models\tau\land\rho,\\
\str B/I\models\tau\And\str M\models\rho,\\
\{i\colon\str A_i\models\lnot\tau\}\in I\And
\{i\colon\str A_i\models\lnot\rho\}\in I,\\
\{i\colon\str A_i\models\lnot\tau\}\cup
\{i\colon\str A_i\models\lnot\rho\}\in I,\\
\{i\colon\str A_i\models\lnot\tau\lor\lnot\rho\}\in I,\\
\{i\colon\str A_i\models\lnot(\tau\land\rho)\}\in I.\qedhere
\end{gather*}
\end{proof}

\begin{lemma}\label{exists}
The equivalence \eqref g, that is,
\begin{equation*}
\str B/I\models\sigma\iff\{i\colon\str A_i\models\lnot\sigma\}\in I,
\end{equation*}
considered as a function of $\sigma$, is preserved under quantification:
\begin{compactdesc}
\item[if] it holds when $\sigma$ is $\psi(a)$, for all parameters $a$, for some singulary formula $\psi$ (possibly with parameters),
\item[then] it holds when $\sigma$ is $\Exists x\psi(x)$.
\end{compactdesc}
\end{lemma}

\begin{proof}
Under the given hypothesis, the following are equivalent:
\begin{gather*}
\str B/I\models\Exists x\psi(x),\\
\str B/I\models\psi(a)\text{ for some $a$ in $B$},\\
\{i\colon\str A_i\models\lnot\psi(a_i)\}\in I\text{ for some $a$ in $B$}.	
\end{gather*}
For all $a$ in $B$, we have
\begin{equation*}
\{i\colon\str A_i\models\lnot\psi(a_i)\}\includes
\{i\colon\str A_i\models\lnot\Exists x\psi(x)\}.
\end{equation*}
Moreover, for some choice of $a$, this inclusion is an equality.  This yields the result.
\end{proof}

\section{Ultraproducts}

Suppose $P$ is a prime ideal (hence a maximal ideal) of $\pow{\Omega}$.  Then the reduced product $\str B/P$ is called more precisely an \textbf{ultraproduct} of $(\str A_i\colon i\in {\Omega})$.  There is a trivial example:  For some $j$ in ${\Omega}$, let $P$ be the \emph{principal} ideal $({\Omega}\setminus\{j\})$ of $\pow {\Omega}$, that is, $P=\{X\included {\Omega}\colon j\notin {\Omega}\}$.  Then
\begin{equation*}
\prod_{i\in {\Omega}}\str A_i/P\cong \str A_j.
\end{equation*}
All ultraproducts are thus if ${\Omega}$ is finite; but if ${\Omega}$ is infinite, then the Fr\'echet ideal of $\pow{\Omega}$ (that is, the ideal consisting of all finite subsets of ${\Omega}$) is a proper ideal, so it may be included in $P$, which is therefore not principal.\footnote{So we are assuming the Prime Ideal Theorem, that every proper ideal of a ring is included in a prime ideal.  This is apparently weaker than the Maximal Ideal Theorem, that every proper ideal of a ring is included in a maximal ideal; this is equivalent to the Axiom of Choice.  Some discussion and references are found in \cite[\S6.2, pp.\ 272--3]{MR94e:03002}.}  Immediately we have:

\begin{lemma}\label{lnot}
If $P$ is a prime ideal of $\pow {\Omega}$, then the equivalence
\begin{equation*}
\str B/P\models\sigma\iff\{i\colon\str A_i\models\lnot\sigma\}\in P,
\end{equation*}
as a function of $\sigma$, is preserved under negation.
\end{lemma}

The three lemmas of this chapter 
%(on pages \pageref{land}, \pageref{exists}, and \pageref{lnot}) 
together yield:

\begin{theorem}[\L o\'s\footnote{The usual reference is \cite{MR0075156} although the theorem is not given clearly there.}]\label{thm:Los}
If $P$ is a maximal ideal of $\pow {\Omega}$, then
\begin{equation*}
\str B/P\models\sigma\iff\{i\colon\str A_i\models\lnot\sigma\}\in P
\end{equation*}
holds for all $\sigma$ (with parameters).
\end{theorem} 

As a special case, if each $\str A_i$ is the same structure $\str A$, so that in particular $\prod_{i\in {\Omega}}A_i$ is the Cartesian power $A^{\Omega}$, then the ultraproduct $\str B/I$ (that is $\str A^{\Omega}/P$) is an \textbf{ultrapower} of $\str A$.
The diagonal embedding $a\mapsto(a\colon i\in {\Omega})$ of $\str A$ in $\str B/I$ is now an \emph{elementary embedding,} that is, for all sentences $\sigma$ with parameters from $A$ (or more precisely from the image of $A$ in $A^{\Omega}$),
\begin{equation*}
\str B/I\models\sigma\iff\str A\models\sigma.
\end{equation*}
Considering the embedding as an inclusion (that is, identifying $\str A$ with its image in $\str B/I$), we may write then
\begin{equation*}
\str A\preccurlyeq\str B/I.
\end{equation*}

\section{Cardinality}

By the theorem below, a non-principal ultrapower $\str C$ of a
countably infinite structure $\str A$ is uncountable.  By the Downward
L\"owenheim--Skolem--Tarski Theorem, in a countable signature, there
will then be a countable structure $\str B$ such that 
\begin{equation*}
\str A\prec\str B\prec C.
\end{equation*}
Indeed, $\str B$ may be chosen to include $A\cup\{x\}$ for some $x$ in
$C\setminus A$.  However, even though $\str A$ is then a proper
substructure of $\str B$, these two may be isomorphic.  However, this
is not the case when $\str A$ is $(\N,+,\cdot)$.  Thus \emph{countable
non-standard models of arithmetic} exist.  A more illuminating
construction of such models is given in \S\ref{sect:Skolem} below.   

The following is a special
case of \cite[Thm 9.5.4(a)]{MR94e:03002} (and is said to be found in
Frayne, Morel, and Scott \cite{MR0142459}\footnote{I have a printout
  of this article, but have not sorted through all of its many basic
  results to find this one.  It should be noted that the article has a
  `correction' \cite{MR0154807}, which merely refines the account of Tarski's
  contribution to the subject (as well as taking some of the credit
  away from Frayne).}).  

\begin{theorem}\label{thm:card}
For all signatures $\sig$, for all $\str A$ in $\Mod$, for all
singulary formulas $\phi$ of $\sig(A)$, for all non-principal prime
ideals $P$ of $\pow{\upomega}$,  
\begin{equation*}
\upomega\leq\abs{\phi(\str A)}\implies
\abs{\phi(\str A^{\upomega}/P)}=\abs{\phi(\str A)}^{\upomega}.
\end{equation*}
In particular, if $\str A$ is countable, then all infinite definable
relations of $\str A^{\upomega}/P$ have the cardinality of the
continuum. 
\end{theorem}

\begin{proof}
For all $a$ in $A^{\upomega}$, if $a/P\in\phi(\str A^{\upomega}/P)$,
then by \L o\'s's Theorem 
\begin{equation*}
\{i\in\upomega\colon a_i\notin\phi(\str A)\}\in P.
\end{equation*}
Then we may assume this set $\{i\in\upomega\colon a_i\notin\phi(\str
A)\}$ is actually empty.  More precisely, there is $a'$ in $\phi(\str
A)^{\upomega}$ such that $a/P=a'/P$.  More precisely still, there is
an injection $a/P\mapsto a'$ from $\phi(\str A^{\upomega}/P)$ to $\phi(\str
A)^{\upomega}$.  This shows 
\begin{equation*}
\abs{\phi(\str A^{\upomega}/P)}\leq\abs{\phi(\str A)}^{\upomega}.
\end{equation*}
For the reverse inequality, it is enough to find a function $x\mapsto
x^*$ from $\phi({\str A}^{\upomega})$ to itself such that 
\begin{equation*}
x\neq y\implies x^*/P\neq y^*/P,
\end{equation*}
that is,
\begin{equation*}
x\neq y\implies\{i\colon x^*_i\neq y^*_i\}\notin P.
\end{equation*}
Now $x\neq y$ means $x_i\neq y_i$ for some $i$ in $\upomega$.  If
\begin{equation}\label{eqn:w-i}
\{j\colon x^*_j\neq y^*_j\}\includes\upomega\setminus i,
\end{equation}
that is, if $\{j\colon x^*_j= y^*_j\}\included i$, then since $i\in
P$, we have
$\{j\colon x^*_j\neq y^*_j\}\notin P$. 
So it is enough that
\begin{equation}\label{eqn:ileqj}
x_i\neq y_i\And i\leq j\implies x^*_j\neq y^*_j.
\end{equation}
We can achieve this by letting $x^*_j$ be an injective function of
$(x_0,\dots,x_j)$, for each $j$ in $\upomega$.  We can do \emph{this,}
if $\phi(\str A)$ is infinite.  Indeed, for each $i$ in $\upomega$,
let $\mu_i$ be an injection from $\phi(\str A)^{i+1}$ to $\phi(\str
A)$.  Now we can define 
\begin{equation*}
x^*_i=\mu_i(x_0,\dots,x_i).\qedhere
\end{equation*}
\end{proof}

Let us try to generalize this argument, replacing $\upomega$ with an
arbitrary infinite index-set $\Omega$.  In the condition \eqref{eqn:w-i}, the
element $\upomega\setminus i$ of the dual filter $F$ of $P$ will be
replaced by some element $X_i$ of the dual filter.  Then
\eqref{eqn:ileqj} becomes 
\begin{equation*}
x_i\neq x_j\And j\in X_i\implies x^*_j\neq y^*_j.
\end{equation*}
So $x^*_j$ should be an injective function of $(x_i\colon j\in X_i)$,
for each $j$ in $\Omega$.  For this, it is enough if the sets 
\begin{equation*}
\{i\in\Omega\colon j\in X_i\}
\end{equation*}
are finite.  An ultrafilter $F$ on $\Omega$ (that is, an ultrafilter
of $\pow{\Omega}$ is called \textbf{regular} if it has such elements
$X_i$ for all $i$ in $\Omega$. 

It is easy to show that there are regular ultrafilters on
$\powf{\Omega}$ (that is, regular ultrafilters of
$\pow{\powf{\Omega}}$.  For, if $i\in\powf{\Omega}$, we need only
define 
\begin{equation*}
X_i=\{j\in\powf{\Omega}\colon i\included j\}.
\end{equation*}
Since $X_i\cap X_j=X_{i\cup j}$, the $X_i$ do generate a filter
on $\powf{\Omega}$.  The filter is proper, since $i\in X_i$, so none
of the $X_i$ is empty.  Moreover, 
\begin{equation*}
\{i\in\powf{\Omega}\colon j\in X_i\}=\{i\in\powf{\Omega}\colon
i\included j\}=\pow j, 
\end{equation*}
which is finite.  So there are regular proper filters, and hence
regular ultrafilters, on $\powf{\Omega}$.  Since $\powf{\Omega}$ has
the same cardinality as $\Omega$ (assuming this is infinite), there
are regular ultrafilters on $\Omega$.

We shall use an index-set of the form $\powf{\Omega}$ in proving the
Compactness Theorem (Theorem \ref{thm:compact}) on page
\pageref{thm:compact} below.


\chapter{Simple applications}

\section{Arrow's Theorem}

This section is inspired by Sasha Borovik's article
\cite{Borovik-infinitesimals}.  We
consider an index-set $\Omega$ as a set of \emph{voters.}  Each voter
$i$ in $\Omega$
is called on to assign a linear ordering $<_i$ to a set $A$ of
\emph{candidates.}  These orderings are to be used to assign a linear
ordering $<$ to $A$.  This ordering $<$ should be a kind of average of
the orderings $<_i$.  This suggests that we should take an
ultraproduct of the structures $(A,<_i)$.  We shall see that, on some
reasonable assumptions, we \emph{must} do this.

We want to determine $<$ by first selecting a subset $D$ of
$\pow{\Omega}$ such that, for all $x$ and $y$ in $A$, we shall be able
to require
\begin{equation*}
  \{i\colon x<_i y\}\in D\implies x<y.
\end{equation*}
So $D$ will be, so to speak, a collection of `winning coalitions'.  If
$X\in D$, then the members of $X$ can determine how the candidates in
$A$ shall be ordered (if all members of $X$ agree).
Then we must have, first of all,
\begin{gather*}
  D\neq\emptyset,\\
  X\in D\implies X\comp\notin D.
\end{gather*}
We also require that additional votes for a
particular ordering can only help that ordering:
\begin{equation*}
  X\in D\And X\included Y\included\Omega\implies Y\in D.
\end{equation*}
Hence in particular $\Omega\in D$.
We require voting to be decisive:
\begin{equation*}
  X\notin D\implies X\comp\in D.
\end{equation*}
If $A$ consists of just two candidates, this is all we need.  Then $D$
is not necessarily an ultrafilter on $\Omega$; for it need not be
closed under intersections.  Indeed, in the `democratic' case, if
$\Omega$ has a finite number $2n-1$ of members, then $D$ will be
$\{X\in\pow{\Omega}\colon\abs X\geq n\}$; this is definitely not
closed under intersections unless $n=1$.

But now suppose $A$ contains
three distinct candidates, $a$, $b$, and $c$; and let
\begin{align*}
  \{i\colon a<_ib\}&=A,&\{i\colon b<_ic\}&=B.
\end{align*}
Suppose both $A$ and $B$ are in $D$.
Then we must conclude $a<b$ and $b<c$ and therefore $a<c$.  We have now
\begin{align*}
  A\cap B&\included\{i\colon a<_ic\}, & \{i\colon a<_ic\}&\in D.
\end{align*}
  However, possibly 
\begin{equation*}
  A\cap B=\{i\colon a<_ic\};
\end{equation*}
this is the case when---as is possible---
\begin{gather*}
  \{i\colon c<_ia<_ib\}=A\setminus B,\\
\{i\colon b<_ic<_ia\}=B\setminus A,\\
\{i\colon c<_ib<_ia\}=(A\cup B)\comp.
\end{gather*}
See Figure~\ref{fig:vote}.
\begin{figure}
\centering
%\psset{xunit=10mm,yunit=5mm}
  \begin{pspicture}(-3,-1)(3,1.5)
    \psellipse(-1,0)(2,1)
\psellipse(1,0)(2,1)
\rput(0,0){\makebox[0pt][c]{$a<b<c$}}
\rput(-2,0){\makebox[0pt][c]{$c<a<b$}}
\rput(2,0){\makebox[0pt][c]{$b<c<a$}}
\rput(0,1.3){\makebox[0pt][c]{$c<b<a$}}
  \end{pspicture}
  \caption{An election with three candidates}\label{fig:vote}
\end{figure}
Thus we must have $A\cap B\in D$.  Therefore $D$ is an ultrafilter on
$\Omega$.  If $\Omega$ is finite, then $D$ must be a principal
ultrafilter: that is, one voter decides everything, and the system is
a dictatorship.

\section{Compactness}

\begin{theorem}[Compactness]\label{thm:compact}
Suppose $\Gamma\included\Sn$, and every finite
subset of $\Gamma$ has a model.  Then $\Gamma$ itself has a
model.
\end{theorem}

\begin{proof}
Assuming $\str A_{\Delta}\models\Delta$ for each $\Delta$ in
$\powf{\Gamma}$, we shall find an ultrafilter $F$ on $\powf{\Gamma}$
such that
\begin{equation}\label{eqn:compact}
\prod_{\Delta\in\powf{\Gamma}}\str A_{\Delta}/F\models\Gamma.
\end{equation}
This just means, by \L o\'s's Theorem, that for each $\sigma$ in $\Gamma$,
\begin{equation*}
\{\Delta\in\powf{\Gamma}\colon\str A_{\Delta}\models\sigma\}\in F.
\end{equation*}
But we have 
\begin{equation*}
\{\Delta\in\powf{\Gamma}\colon\sigma\in\Delta\}\included\{\Delta\in\powf{\Gamma}\colon\str
A_{\Delta}\models\sigma\}. 
\end{equation*}
Let the former set be denoted by $[\sigma]$; more generally, if
$\Delta\in\powf{\Gamma}$, let 
\begin{equation*}
[\Delta]=\{\Theta\in\powf{\Gamma}\colon\Delta\included\Theta\}.
\end{equation*}
Then
\begin{align*}
\Delta&\in[\Delta],&
[\Delta]\cap[\Theta]&=[\Delta\cup\Theta].
\end{align*}
Consequently the sets $[\Delta]$ generate a filter on
$\pow{\powf{\Gamma}}$.  Let it be included in the ultrafilter $F$, and
let $\str B$ be the ultraproduct of $(\str
A_{\Delta}\colon\Delta\in\powf{\Gamma})$ with respect to $F$.  For
every $\sigma$ in $\Gamma$, we have $[\sigma]\in F$, and for every
$\Delta$ in $[\sigma]$, we have $\str A_{\Delta}\models\sigma$.
Then by \L o\'s's Theorem, we have \eqref{eqn:compact}.
\end{proof}

Now we can establish a complement to Theorem \ref{thm:dLST} (p.\ \pageref{thm:dLST}):

\begin{theorem}[Upward L\"owenheim--Skolem--Tarski]
If $\str A$ is an infinite structure with signature $\sig$, and $\max(\abs A,\abs{\sigma})\leq\kappa$, then there is a structure $\str B$ such that
\begin{align*}
\str A&\preccurlyeq\str B,&\abs B=\kappa.
\end{align*}
\end{theorem}

\begin{proof}
Let $C$ be a set $\{c_{\alpha}\colon\alpha<\kappa\}$ be a set of new constants, all distinct.  By Compactness, the set
\begin{equation*}
\Th{\str A_A}\cup\{c_{\alpha}\neq c_{\beta}\colon \alpha<\beta<\kappa\}
\end{equation*}
of sentences has a model $\str D_{A\cup C}$.  By construction, this model has cardinality at least $\kappa$.  By the downward version of the theorem, $\str D$ has an elementary substructure $\str B$ of size $\kappa$ such that $A\included B$.  Since also $\str A\preccurlyeq\str D$, the structure $\str B$ is as desired.
\end{proof}

This theorem yields an easy test for completeness of theories.  For an infinite cardinal $\kappa$, a theory is \textbf{$\kappa$-categorical} if all of its models of size $\kappa$ are isomorphic to one another.

\begin{theorem}[\L o\'s--Vaught Test]
If a theory $T$ of a signature $\sig$ has models, but no finite models; $\abs{\sig}\leq\kappa$; and $T$ is $\kappa$-categorical; then $T$ is complete.
\end{theorem}

\begin{proof}
If $T$ contains neither $\sigma$ nor $\lnot\sigma$, then both $T\cup\{\lnot\sigma\}$ and $T\cup\{\sigma\}$ have models, which must be infinite.  Then by the L\"owenheim--Skolem--Tarski theorems (both upward and downward forms may be needed), each of the two sets has a model of cardinality $\kappa$; but these two models cannot be isomorphic to one another.
\end{proof}

\begin{theorem}\label{thm:ACF_0}
\mbox{}
\begin{itemize}
\item
The theory of algebraically closed fields of characteristic $0$ is complete.
\item
For all primes $p$, the theory of algebraically closed fields of characteristic $p$ is complete.
\end{itemize}
\end{theorem}

\begin{proof}
None of these theories has no finite models.  Every algebraically closed field is determined up to isomorphism by its characteristic and its transcendence-degree.  If $\kappa$ is uncountable, then a field with transcendence-degree $\kappa$ has cardinality $\kappa$.  Now the \L o\'s--Vaught Test applies.
\end{proof}

Similarly we have the following (see page \pageref{mc} above):

\begin{theorem}\label{thm:ACF}
The theory of algebraically closed fields is model-complete.
\end{theorem}

\begin{proof}
If $T$ is this theory, $K\models T$, and $\abs K<\kappa$, then $T\cup\diag K$ is $\kappa$-categorical, but has no finite models.
\end{proof}

We can also now prove the converse of the lemma on page \pageref{lem:TA} above. 

\begin{theorem}\label{thm:TA}
For all theories $T$, the models of $T_{\forall}$ are precisely the substructures of models of $T$.
\end{theorem}

\begin{proof}
Assuming $\str A\models T_{\forall}$, we want to show $T\cup\diag{\str A}$ has a model.  By Compactness, and since $\diag{\str A}$ is closed under conjunction, it is enough to show $T\cup\{\theta(\vec a)\}$ has a model whenever $\theta$ is a quantifier-free formula of $\sig$ and $\str A\models\theta(\vec a)$.  If it has no model, then $T\proves\lnot\theta(\vec a)$, so (since no entry of $\vec a$ is in $\sig$) $T\proves\Forall{\vec x}\lnot\theta(\vec x)$, and therefore $\str A\models\Forall{\vec x}\lnot\theta(\vec x)$, which is absurd.
\end{proof}

In particular, when $T$ is just field-theory, then $T_{\forall}$ is the theory of integral domains: see page \pageref{id} below.

\section{Elementary classes}

In \cite{MR0075156} \L o\'s defined ultraproducts (but not by that
name) in order to state the following algebraic test for being an
elementary class of structures.

\begin{theorem}
A subclass of $\Mod$ is elementary if and only if it contains:
\begin{compactitem}
\item
 every structure that is elementarily equivalent to a member, and
 \item
 every ultraproduct of members.
 \end{compactitem}
\end{theorem}

\begin{proof}
The `only if' direction is the easier.  An elementary class is the
class of models of some theory $T$.  If the class is $\mathcal K$, and
$\str A\in\mathcal K$, and $\str A\equiv\str B$, then $\str B\models
T$, so $\str B\in\mathcal K$.  If $\{\str A_i\colon
i\in\Omega\}\included\mathcal K$, then $\str A_i\models T$ in each
case, so every ultraproduct of the $\str A_i$ is a model of $T$, by \L
o\'s's Theorem.

The more difficult direction is `if'.  Suppose $\mathcal K$ is a
non-elementary subclass of $\Mod$.  Then there is a model $\str B$ of
$\Th{\mathcal K}$ that does not belong to $\mathcal K$.  However,
every element $\sigma$ of $\Th{\str B}$ has a model in $\mathcal K$,
since otherwise $\lnot\sigma$ would be in $\Th{\mathcal K}$.
Therefore every finite subset $\Delta$ of $\Th{\str B}$ has a model
$\str A_{\Delta}$ in $\mathcal K$ (since otherwise the negation of the
conjunction of the members of $\Delta$ would be in $\Th{\mathcal K}$).
By (the proof of) the Compactness Theorem, some ultraproduct of $(\str
A_{\Delta}\colon\Delta\in\powf{\Th{\str B}})$ is elementarily
equivalent to $\str B$. 
\end{proof}

\section{A countable non-standard model of arithmetic}\label{sect:Skolem}

By \textbf{arithmetic} we mean the theory of $(\upomega,+,\cdot)$ or
of $(\upomega,+,\cdot,0,1,\leq)$; it makes little difference, since
\begin{compactenum}[1)]
\item  
$\leq$ is definable in $(\upomega,+,\cdot)$ by the formula $\Exists
  zx+z=y$,
\item
$\{0\}$ is definable by $\Forall yy+x=y$,
\item
$\{1\}$ is definable by $0<x\land\Forall y(0=y\lor x\leq y)$.
\end{compactenum}
Similarly $\{n\}$ is definable in $(\upomega,+,\cdot)$ for all $n$ in
$\upomega$.

Every ultrapower of $(\upomega,+,\cdot)$ is a model of arithmetic.
Every \emph{non-prin\-cipal} ultrapower $\str B$ (determined by a
non-principal ultrafilter $F$ on $\upomega$) is a
\emph{non-standard} model of arithmetic,
in the sense that it is not isomorphic to $(\upomega,+,\cdot)$, but
contains an infinite element $c$.  However, $\str B$ here must be
uncountable by Theorem~\ref{thm:card}.  As we noted before this
theorem, by the Downward L\"owenheim--Skolem--Tarski Theorem (Theorem
\ref{thm:dLST}), we can obtain a countable elementary substructure
$\str A$ of $\str B$ that includes $\upomega\cup\{c\}$, and then $\str
A$ will be an elementary extension of $(\upomega,+,\cdot)$. 

We can construct such a structure $\str A$ more directly as follows.
Let $A$ be the set of \emph{$0$-definable} singulary operations of
$(\upomega,+,\cdot)$.  This means $f\in A$ if and only if the relation
$\{(x,f(x))\colon x\in\upomega\}$ is $0$-definable (that is, definable
without parameters).  We can consider
$A$ as a subset of $\upomega^{\upomega}$.  Then a constant sequence
$(x,x,x,\dots)$ should be understood as the constant function
$\{(n,x)\colon n\in\upomega\}$ or $n\mapsto x$, which is in $A$.  Thus
the diagonal map 
embeds $\upomega$ in $A$.  Also $A$ is closed under $+$ and $\cdot$.
Therefore $A$ is the universe of a substructure $\str A$ of $\str B$.  Also,
if $n\in\upomega$, and $\phi$ is an $(n+1)$-ary formula, and $\vec
f$ is an element $(f^0,\dots,f^{n-1})$ of $A^n$, then $A$ has an
element $g$ such that for all $i$ in 
$\upomega$, 
\begin{equation*}
(\upomega,+,\cdot)\models\Exists y\phi(\vec f(i),y)\iff (\upomega,+,\cdot)\models \phi(\vec f(i),g(i)).
\end{equation*}
Indeed, $g$ can be such that $g(i)$ is the \emph{least} $b$ such that
$(\upomega,+,\cdot)\models\phi(\vec f(i),b)$, if such $b$ exist; and
otherwise $g(i)=0$.  Then $g$ is defined by the formula 
\begin{equation*}
(\phi(\vec f(x),y)\land(\Forall z(\phi(\vec f(x),z)\lto y\leq
  z)))\lor(\Forall z\lnot\phi(\vec f(x),z)\land y=0). 
\end{equation*}
It follows by the Tarski--Vaught Test (page \pageref{TV}) that
\begin{equation*}
  \str A\preccurlyeq\str B;
\end{equation*}
therefore, since $(\upomega,+,\cdot)\included\str A$, we have
\begin{equation*}
  (\upomega,+,\cdot)\prec\str A.
\end{equation*}
Indeed, we now have that the following are equivalent:
\begin{gather*}
  \str B\models\Exists y\phi(\vec f,y),\\
\{i\colon(\upomega,+,\cdot)\models\Exists y\phi(\vec f(i),y)\}\in F,\\
\{i\colon(\upomega,+,\cdot)\models\phi(\vec f(i),g(i))\}\in F,\\
  \str B\models\phi(\vec f,g).
\end{gather*}
Now the Tarski--Vaught Test applies.  This construction of $\str A$ is
apparently due to Skolem.\footnote{I take it from Bell and Slomson \cite[Ch.\ 12, \S2]{MR0269486}.}

\chapter{G\"odel's Completeness Theorem}\label{ch:complete}

A sentence that is true in all structures of its signature can be
called \textbf{valid} sentence or a \textbf{validity.}  It is easy in principle to show that a
sentence is \emph{not} valid: just exhibit a model of its negation.
But if a sentence \emph{is} valid, how can this be shown?  We cannot
simply verify the sentence in all structures of its signature, since
there will be infinitely many of these structures.  The method of
\emph{formal proof} is a finitary alternative.  We shall show by means
of ultraproducts that this method always works in principle.  This
result is \emph{G\"odel's Incompleteness Theorem.} 

\section{Formal proofs}

A \textbf{formal proof} is just a (finite) list of sentences such that each sentence on the list is either
\begin{compactenum}[1)]
\item
an \emph{axiom,} or
\item
derivable from sentences earlier in the list by means of a \emph{rule of inference.}
\end{compactenum}
We choose the axioms and rules of inference to serve our needs; taken all together, they constitute a \textbf{proof-system.}  In his
doctoral dissertation of 1930, G\"odel \cite{Goedel-compl} gave a particular proof-system, obtained from the \emph{Principia Mathematica} \cite{PM} of Russell and Whitehead.  The first four of G\"odel's axioms, or rather \emph{schemes} of axioms, are found on page 13, Chapter 1, of the \emph{Principia Mathematica.}\footnote{As G\"odel notes, there was a fifth axiom, $\phi\lor(\psi\lor\chi)\lto\psi\lor(\phi\lor\chi)$, but apparently Bernays showed it to be redundant.  For us, each of the four formulas given here represents infinitely
  many axioms, since $\phi$, $\psi$, and $\chi$ can be
  any formulas.  It should be noted that Russell and Whitehead were involved in \emph{creating} formal logic; our way of understanding formulas was not yet fully developed.  For an amusing fictionalized account of Russell's interactions with G\"odel, see \cite{Logicomix}.}  Recall that, by our convention on symbolic
  precedence given on page \pageref{precedence}, $\lor$
  takes precedence over $\lto$, and of two instances of
  $\lto$, the one on the right takes precedence.
\begin{enumerate}[1)]
\item
$\phi\lor\phi\lto\phi$,
\item
$\phi\lto\phi\lor\psi$,
\item
$\phi\lor\psi\lto\psi\lor\phi$,
\item
$(\phi\lto\psi)\lto\chi\lor\phi\lto\chi\lor\psi$.
\end{enumerate}
The primitive Boolean connectives here are actually $\lor$ and $\lnot$; so
$\phi\lto\psi$ should be understood as an abbreviation of
$\lnot\phi\lor\psi$.	In Chapter 9 of the \emph{Principia} (at $*$9.2 and $*$9.25, pp.~138--40) are found G\"odel's next two axioms:\footnote{See the previous note.  For
  G\"odel, there were just six axioms in all, using \emph{propositional
    variables} where I have put $\phi$, $\psi$, and $\chi$; and using
  a \emph{functional variable} where I have put $\theta$.  Then in addition to the three rules of inference given below, there was a fourth, allowing propositional and
  functional variables to be replaced by \emph{formulas} in our
  sense.} 
	\begin{enumerate}[1)]\setcounter{enumi}4
	\item
$\Forall x\phi\lto\phi^x_y$,
\item
$\Forall x(\theta\lor\phi)\lto\theta\lor\Forall x\phi$.
\end{enumerate}
In the former scheme, $\phi^x_y$ is the result of replacing
every free occurrence of $x$ in $\phi$ with $y$.  In the latter scheme,
$x$ must not occur freely in $\theta$.  The primitive quantifier can be taken as $\forall$, so that $\Exists x\psi$ will be an abbreviation of $\lnot\Forall x\lnot\psi$.  Finally, equality is treated in two axioms, found in Chapter 13 of the \emph{Principia} (at $*$13.15 and $*$13.101, pp.\ 177--8):
\begin{enumerate}[1)]\setcounter{enumi}6
\item
$x=x$,
\item
$x=y\lto\phi\lto\phi^x_y$.
\end{enumerate}
Here $y$ should not occur in $\phi$, or at least there should be no subformula $\Forall y\psi$ in which there is an occurrence of $x$ that is free as an occurrence in $\phi$.

  The rules of inference are three:\footnote{See
  the previous note on G\"odel's fourth rule of inference (which was actually third
  on his list).  G\"odel notes, `Although Whitehead and Russell use these rules throughout their derivations, they do not formulate all of them explicitly.'} 
\begin{compactdesc}
\item[Detachment:] From $\phi$ and $\phi\lto\psi$ may be\footnote{Detachment is not G\"odel's name for this rule; he (or more precisely his translator) calls it the Inferential Schema.} inferred $\psi$.
\item[Generalization:]
From $\theta$ may be inferred $\Forall x\theta$.
\item[Change of variables:]
`Individual variables (free or bound) may be replaced by others, so
  long as this does not cause overlapping of the scopes of variables
  denoted by the same sign' \cite[p.\ 584]{Goedel-compl}. 
\end{compactdesc}
Again, a \emph{formal proof} is a finite list of formulas such that each
formula on the list is an axiom or else is derived from previous
formulas on the list by means of a rule of inference.  The last formula
on the list is then said to be \emph{provable.}  If $\phi$ is
provable, we may express this by
\begin{equation*}
  \proves\phi.
\end{equation*}
Note that in fact \emph{every} formula in a formal proof is provable, because every initial segment of a formal proof is still a formal proof.

A \textbf{generalization} of a formula $\phi$ is a formula
$\Forall{\vec x}\phi$, where all free variables of $\phi$ occur in $\vec x$.  Then we can generalize the notion of validity by saying that an arbitrary formula is \textbf{valid} if some (and hence every) generalization
of it is true in every structure of its signature. 

It should be clear that every provable formula is valid.  G\"odel
proves the converse: this is his Completeness Theorem.

Before G\"odel, a completeness theorem for \emph{propositional logic}
was known.\footnote{G\"odel's reference for this is Bernays from 1926; but
the theorem can be found in Post's 1921 article \cite{Post}.}
\textbf{Propositional formulas} are, strictly, not formulas as defined in \S\ref{subsect:formulas} above; but they can be understood as formulas in which:
\begin{compactenum}[1)]
  \item
the place of atomic formulas is taken by \textbf{propositional
  variables;}
\item
no quantifier $\exists$ or $\forall$ is used.
\end{compactenum}
In particular, there are no \emph{individual} variables in a propositional formula, but only \emph{propositional} variables.  A \emph{structure} for propositional logic assigns a truth-value to each of these propositional variables.  Then a propositional formula is true or false in the structure, according to the relevant parts of the definition of truth of sentences (on page \pageref{truth}), namely:
\begin{gather*}
		\str A\models\lnot\sigma\iff \str A\nmodels\sigma,\\
	\str A\models\sigma\land\tau\iff \str A\models\sigma\And \str A\models\tau.
\end{gather*}
Strictly, since $\lor$ is now primitive instead of $\land$, we should replace the latter rule with
\begin{equation*}
	\str A\models\sigma\lor\tau\iff \str A\models\sigma\;\text{ or }\; \str A\models\tau.
\end{equation*}
We may treat the truth-value \emph{true} as $1$, and \emph{false} as $0$.  Then a propositional formula $F$ in an $n$-tuple $(P_0,\dots,P_{n-1})$ of
propositional variables determines an $n$-ary operation $\hat F$ on $2$, where if $\vec e\in 2^n$, then $\hat F(\vec e)$ is the truth-value of $F$ in any propositional structure that assigns the value $e_i$ to $P_i$ when $i<n$.  This
operation $\hat F$ can be described completely in a \emph{truth-table.}  If the operation is
identically $1$, then $F$ is a \textbf{(propositional) tautology.}  The first
four axiom-schemes above, along with the inference-rule of Detachment,
constitute a proof-system for propositional logic in which every
tautology is provable.  This is possibly not an exciting
theorem, since there is already an algorithm for determining
whether a formula is a tautology: just write out its truth-table.

A \textbf{tautology} in general can be understood as resulting from a propositional tautology by replacing each occurrence of a propositional variable with the same formula of some signature $\sig$, for all propositional variables occurring in the propositional tautology.  Evidently tautologies in this broader sense are valid.  They are therefore provable, by the completeness theorem of propositional logic.  If we do not want to bother to prove this completeness theorem, we can just introduce, as new axioms, all tautologies, since again there is an algorithm for determining which formulas these are.

If $\phi$ is a formula, we may define a formal proof \textbf{from} $\phi$ as a
formal proof in the earlier sense, but with $\phi$ treated as an
axiom, and with generalization of free variables in $\phi$ not allowed.\footnote{The restriction is to ensure that, if $\psi$ is provable from $\phi$, then the formula $\phi\lto\psi$ is valid,  while the converse is still true.}  If $\psi$ is provable from $\phi$ in this sense, we may write 
\begin{equation*}
\phi\proves\psi;
\end{equation*}
to give it a name, we may call this a \textbf{sequent.}  For example, by Detachment, the axiom $\Forall x\phi\lto\phi^x_y$
gives us the sequent
\begin{equation}\label{eqn:rev-gen}
  \Forall x\phi\proves\phi^x_y,
\end{equation}
because the sequence
\begin{equation*}
\Forall x\phi,\ \Forall x\phi\lto\phi^x_y,\ \phi^x_y.
\end{equation*}
is a formal proof from $\Forall x\phi$.
Likewise, the axiom $\Forall
x(\theta\lor\phi)\lto\theta\lor\Forall x\phi$ gives us
\begin{equation}\label{eqn:rule}
  	\Forall x(\theta\lor\phi)\proves\theta\lor\Forall x\phi.
\end{equation}
(Recall that $x$ must not be free in $\theta$.)

\section{Completeness by ultraproducts}\label{sect:c-ultra}

Suppose $\sigma$ is an arbitrary sentence.  We want to show that either $\sigma$ is provable, or else its negation has a model, in fact a countable model.\footnote{The ensuing argument is based mainly on that of Bell and Slomson \cite[Ch.\ 12,
  \S1]{MR0269486}.  These writers cite J.N. Crossley for the suggestion of introducing ultraproducts to G\"odel's
original argument.  Church \cite[\S44]{MR18:631a} explicates G\"odel's
original argument more faithfully.}  

We make several simplifying assumptions:
\begin{compactenum}
\item
No operation-symbols occur in $\sigma$.
\item
The sign $=$ of equality does not occur in $\sigma$.
\item
For some positive integers $p$ and $q$, for some quantifier-free $(p+q)$-ary formula $\phi$, $\sigma$ is the sentence 
\begin{equation*}
\Exists{\vec x}\Forall{\vec y}\phi(\vec x,\vec y),
\end{equation*}
where $\vec x$ and $\vec y$ are respectively a $p$-tuple and a
$q$-tuple of variables.
\end{compactenum}
The justification of these assumptions does not involve ultraproducts, so it is relegated to a later section, \S\ref{sect:arb}.



Let $V$ be a countably infinite set $\{v_k\colon k\in\upomega\}$ of individual
variables.  The power $V^p$ is countable,
so we may assume 
\begin{equation*}
V^p=\{\vec x_k\colon k\in\upomega\}.
\end{equation*}
Now we may suppose
\begin{equation*}
\{\vec y_k\colon k\in\upomega\}\included V^q,
\end{equation*}
where if $k<\ell$, then $\vec y_k$ and $\vec y_{\ell}$ have no entries
in common, and if $j\leq k$, then $\vec x_j$ and $\vec y_k$ have no
entries in common.  We now denote 
\begin{gather*}
	\phi(\vec x_k,\vec y_k)\text{ by }\phi_k,\\
	\phi_0\text{ by }\theta_0,\\
	\phi_{k+1}\lor\theta_k\text{ by }\theta_{k+1},\\
	\Forall{\vec x_0}\cdots\Forall{\vec y_k}\theta_k\text{ by }\sigma_k.
\end{gather*}
That is, $\theta_k$ is defined recursively in $k$ as shown; and $\sigma_k$ is a
generalization of $\theta_k$.
We shall prove that, for all $k$ in $\upomega$,
\begin{equation*}
\sigma_k\proves\sigma.
\end{equation*}
To this end, we note first that since no
entry of $\vec y_{k+1}$ appears in $\theta_k$, we have, as a special case
of the sequent \eqref{eqn:rule},
\begin{equation*}
\Forall{\vec y_{k+1}}(\theta_k\lor\phi_{k+1})\proves
\theta_k\lor\Forall{\vec y_{k+1}}\phi_{k+1},
\end{equation*}
that is (by definition of $\theta_{k+1}$),
\begin{equation*}
\Forall{\vec y_{k+1}}\theta_{k+1}\proves
\theta_k\lor\Forall{\vec y_{k+1}}\phi_{k+1}.
\end{equation*}
By the sequent \eqref{eqn:rev-gen} (used repeatedly), we have
\begin{equation*}
\sigma_{k+1}\proves\Forall{\vec y_{k+1}}\theta_{k+1}.
\end{equation*}
Therefore, by stringing together the (short) proofs of the last two sequents, we have
\begin{equation}\label{eqn:sk+1}
\sigma_{k+1}\proves\theta_k\lor\Forall{\vec y_{k+1}}\phi_{k+1}.
\end{equation}
By repeated use of the axiom allowing removal of universal quantifiers, we have
\begin{equation*}
	\proves\Forall{\vec x}\lnot\Forall{\vec y}\phi(\vec x,\vec y)\lto\lnot\Forall{\vec y_{k+1}}\phi_{k+1};
	\end{equation*}
	therefore, by contraposition (justified by completeness for propositional logic),
	\begin{equation*}
	\proves\Forall{\vec y_{k+1}}\phi_{k+1}\lto\Exists{\vec x}\Forall{\vec y}\phi(\vec x,\vec y),
\end{equation*}
that is,
\begin{equation*}
\proves\Forall{\vec y_{k+1}}\phi_{k+1}\lto\sigma.
\end{equation*}
Combining this with \eqref{eqn:sk+1} gives
\begin{equation*}
\sigma_{k+1}\proves\theta_k\lor\sigma
\end{equation*}
and therefore (by Generalization mainly)
\begin{equation*}
\sigma_{k+1}\proves\sigma_k\lor\sigma.
\end{equation*}
Thus if $\sigma_k\proves\sigma$, then $\sigma_{k+1}\proves\sigma$.
Since by change of variables we have
\begin{equation*}
\sigma_k\proves\sigma
\end{equation*}
when $k=0$, by induction we now have this for all $k$ in $\upomega$.

Now we can show that either $\sigma$ is provable, or $\lnot\sigma$ has a model.
to do so, we consider two cases.  The first one is easy to dispose of:  If some $\sigma_k$ is provable,
then so is $\sigma$ itself, and we are done.  

So now let us suppose that no $\sigma_k$ is provable.  Then no $\theta_k$ is provable; so it
must not be a tautology.


Since $\theta_k$ is quantifier-free, but not a tautology, there
must be a truth-assignment to its atomic subformulas that makes $\theta_k$
false.  We can extend this to a truth-assignment $F$ to \emph{all} atomic formulas in variables from $V$ (that is, in the variables $v_i$) with predicates occurring in $\phi$.  Since none of those predicates is $=$, the truth-assignment $F$ determines a structure $\str A_k$ whose universe is $\upomega$ such that, for each $n$ in $\upomega$, for each $n$-ary predicate $R$ occurring in $\phi$,
\begin{equation*}
R^{\str A_k}=\{(i(0),\dots,i(n-1))\in\upomega^n\colon F(Rv_{i(0)}\cdots v_{i(n-1)})=1\}.
\end{equation*}
If we now treat each variable $v_i$ as a constant whose interpretation in $\str A_k$ is $i$, then we have
\begin{equation*}
\str A_k\models Rv_{i(0)}\cdots v_{i(n-1)}\iff F(Rv_{i(0)}\cdots v_{i(n-1)})=1.
\end{equation*}
Then by construction
\begin{equation*}
  \str A_k\models\lnot\theta_k.
\end{equation*}
Suppose $k\leq\ell$.  Then
\begin{equation*}
  \theta_k\proves\theta_{\ell},
\end{equation*}
so that also $\lnot\theta_{\ell}\proves\lnot\theta_k$, and hence
\begin{equation*}
  \str A_{\ell}\models\lnot\theta_k.
\end{equation*}
Thus for all $j$ in $\upomega$,
\begin{equation*}
  \{i\in\upomega\colon\str A_i\models\theta_j\}\included j.
\end{equation*}
Now let $\str C$ be a non-principal ultraproduct of the $\str A_i$.
It follows that, for all $j$ in $\upomega$,
\begin{equation*}
  \str C\models\lnot\theta_j.
\end{equation*}
(Here $v_i$ is interpreted as the image of $i$ under the diagonal map.)
Hence the conjuncts of the $\lnot\theta_j$ are true in $\str C$:
\begin{equation*}
  \str C\models\lnot\phi(\vec x_j,\vec y_j).
\end{equation*}
Since we have no operation-symbols in our signature, every subset of
$C$ is the universe of a substructure of $\str C$.  Let $B$ be the
image of $\upomega$ under the diagonal map in $C$.  Since $\phi$ is
quantifier-free, and the interpretations of all of the variables are
now in $B$, we have
\begin{gather*}
  \str B\models\lnot\phi(\vec x_j,\vec y_j),\\
  \str B\models\Exists{\vec y}\lnot\phi(\vec x_j,\vec y).
\end{gather*}
But we have arranged things so that every element of $B^p$ is the
interpretation of some $\vec x_j$.  Therefore
\begin{equation*}
  \str B\models\Forall{\vec x}\Exists{\vec y}\lnot\phi(\vec x,\vec y),
\end{equation*}
that is, $\sigma$ is false in $\str B$.

\section{Completeness by K\"onig's Lemma}

G\"odel himself does not use an ultraproduct explicitly in his argument, but he can be understood to create the
structure $\str B$ (with universe $\upomega$) as follows.\footnote{I am guided by Church's version of G\"odel's argument here.  See below.}  Let $(\alpha_k\colon k\in\upomega)$ be
a list of all of the atomic formulas appearing in the formulas
$\phi_{\ell}$.  We define $\str B$ by determining in each case whether
$\alpha_k$ is to be true in $\str B$ (again with variable $v_i$
understood as $i$).  This determination can be made recursively as
follows.  First, we let
\begin{equation*}
  \str B\models\alpha_0\iff\abs{\{i\colon\str
    A_i\models\alpha_0\}}=\upomega
\end{equation*}
(that is, $\alpha_0$ is true in $\str B$ if and only if the set of $i$ such that $\alpha_0$ is true in $\str A_i$ is infinite), and then
\begin{gather*}
\str B\models\alpha_1\iff\abs{\{i\colon\alpha_0{}^{\str
    A_i}=\alpha_0{}^{\str B}\And\str A_i\models\alpha_1\}}=\upomega,\\
\str B\models\alpha_2\iff\abs{\{i\colon\alpha_0{}^{\str
    A_i}=\alpha_0{}^{\str B}\And\alpha_1{}^{\str
    A_i}=\alpha_1{}^{\str B}\And\str A_i\models\alpha_2\}}=\upomega,
\end{gather*}
and so on, where $\alpha_j{}^{\str A_i}=\alpha_j{}^{\str B}$ means simply that $\alpha_j$ is alike true or false in $\str A_i$ and $\str B$.  Strictly the definition is by strong or well-ordered recursion, requiring only the single condition
\begin{equation*}
\str B\models\alpha_k\iff
  \abs{\{i\colon\bigwedge_{j<k}\alpha_j{}^{\str
    A_i}=\alpha_j{}^{\str B}\And\str A_i\models\alpha_k\}}=\upomega.
\end{equation*}
It follows by induction that, at each step,
\begin{equation}\label{eqn:inf}
  \abs{\{i\colon\bigwedge_{j<k}\alpha_j{}^{\str
    A_i}=\alpha_j{}^{\str B}\}}=\upomega.
\end{equation}
The construction ensures $\str B\models\lnot\theta_j$ as before.
Indeed, suppose if possible $\str B\models\theta_j$.  Then the atomic subformulas of
$\theta_j$ belong to a finite set $\{\alpha_i\colon i<k\}$, so
\begin{equation*}
  \{i\colon\bigwedge_{j<k}\alpha_j{}^{\str
    A_i}=\alpha_j{}^{\str B}\}\included   \{i\in\upomega\colon\str
  A_i\models\theta_j\}.
\end{equation*}
However, as before we have also
\begin{equation*}
  \{i\in\upomega\colon\str A_i\models\theta_j\}\included j.
\end{equation*}
These two inclusions together contradict \eqref{eqn:inf}.

There is some arbitrariness in this definition of $\str B$.  If the truth of $\alpha_j$ in $\str B$ has been determined when $j<k$ so that \eqref{eqn:inf} holds, then we shall want
\begin{gather*}
\abs{\{i\colon\bigwedge_{j<k}\alpha_j{}^{\str A_i}=\alpha_j{}^{\str B}\And\str A_i\models\lnot\alpha_k\}}<\upomega\implies\str B\models\alpha_k,\\
\abs{\{i\colon\bigwedge_{j<k}\alpha_j{}^{\str A_i}=\alpha_j{}^{\str B}\And\str A_i\models\alpha_k\}}<\upomega\implies\str B\models\lnot\alpha_k.	
\end{gather*}
If both of these sets are infinite, then the question of whether $\str B\models\alpha_k$ can be decided arbitrarily.  We decided above that $\alpha_k$ would be true in $\str B$ in this case.  However, if at the beginning we had chosen an ultrafilter $D$ on $\upomega$, then we could just define
\begin{equation*}
  \str B\models\alpha_k\iff\{i\colon\str A_i\models\alpha_k\}\in D.
\end{equation*}

G\"odel himself is not explicit about how he obtains $\str B$.  His editor van Heijenoort detects an allusion to K\"onig's Lemma.  There are more than one theorem called by this name, but probably what is meant is the following \cite[Lemma II.5.7, p.\ 69]{MR85e:03003}.

   A \textbf{tree} is a (partially) ordered set such that, for every element $a$, the subset $\{x\colon x<a\}$ is well-ordered.  The ordinal that is isomorphic to this set is then the \textbf{height} of $a$.  If this height is $\beta$, then a \textbf{successor} of $a$ is an element $b$ of the tree with height $\beta+1$ such that $a<b$.  A \textbf{branch} of a tree is a maximal linearly ordered subset.
   
An \textbf{$\upomega$-tree} is a tree whose every element has finite height and finitely many successors.  One version of K\"onig's Lemma is that every infinite $\upomega$-tree has an infinite branch.  To prove this, we select an infinite branch recursively by first letting $a_0$ be an element at height $0$ such that $\{x\colon a_0<x\}$ is infinite; then, assuming $\{x\colon a_k<x\}$ is infinite, we let $a_{k+1}$ be a successor of $a_k$ such that $\{x\colon a_{k+1}<x\}$ is infinite.

This lemma applies to the present situation as follows.  We start with the complete binary tree $2^{<\upomega}$, that is, $\bigcup_{n\in\upomega}2^n$, ordered by inclusion, so that $\vec a\leq\vec b$ if and only if $\vec a$ is an initial segment of $\vec b$.  See Figure \ref{fig:bin}.
\begin{figure}[ht]
\centering
\pstree[treemode=R]{\TR{$\emptyset$}}{
  \pstree{\TR{$(0)$}}{
    \pstree{\TR{$(0,0)$}}{
      \TR{$(0,0,0)$}
      \TR{$(0,0,1)$}
      }
    \pstree{\TR{$(0,1)$}}{
      \TR{$(0,1,0)$}
      \TR{$(0,1,1)$}
      }
      }
  \pstree{\TR{$(1)$}}{
    \pstree{\TR{$(1,0)$}}{
      \TR{$(1,0,0)$}
      \TR{$(1,0,1)$}
      }
    \pstree{\TR{$(1,1)$}}{
      \TR{$(1,1,0)$}
      \TR{$(1,1,1)$}
      }
      }
      }
\caption{A complete binary tree}\label{fig:bin}
\end{figure}
This has a sub-tree consisting of those $(e_0,\dots,e_{n-1})$ such that the set
\begin{equation*}
\{i\colon\bigwedge_{j<n}\alpha_j{}^{\str A_i}=e_j\}
\end{equation*}
is infinite.  This sub-tree is infinite, because it has elements at each finite height.  By K\"onig's Lemma, the sub-tree has an infinite branch, whose union is a sequence $(e_k\colon k\in\upomega)$; we can then define
\begin{equation*}
\str B\models\alpha_k\iff e_k=1.
\end{equation*}
As before, $\str B\models\lnot\sigma$.

\section{Arbitrary formulas}\label{sect:arb}

We have to justify the assumptions about $\sigma$ made at the beginning of \S\ref{sect:c-ultra}.

\subsection{Operation-symbols}

What we call relations, G\"odel calls functions; but he has no symbols for what we call operations.  However, even if we do use them, we can dispose of them as follows.  Suppose, for some $n$-ary operation-symbol $F$, there were an atomic subformula $\alpha$ of $\sigma$ featuring a term $Ft_0\cdots t_{n-1}$.  Introducing a new $(n+1)$-ary predicate $R_F$, we could replace the term $Ft_0\cdots t_{n-1}$ in $\alpha$ with a new variable $x$, obtaining an atomic formula $\alpha'$.  We could then replace $\alpha$ in $\sigma$ with the formula
\begin{equation*}
\Exists x(\alpha'\land R_Ft_0\cdots t_{n-1}x),
\end{equation*}
obtaining $\sigma'$.  Then $\sigma$ would be logically equivalent to
\begin{equation*}
\sigma'\land\Forall{\vec x}\Exists y\Forall z(R\vec xy\land(R\vec xz\lto y=z)).
\end{equation*}
We should show that $\sigma$ is provable from this equivalent sentence.

\subsection{Equality}

Suppose no operation-symbol occurs in $\sigma$, but the sign $=$ of equality does occur.  We have to deal with the requirement that this sign is interpreted in every structure as equality itself (and not merely an equivalence-relation).  We introduce a new binary predicate $\equiv$, and we replace each occurrence of $=$ in $\sigma$ with this new predicate $\equiv$, obtaining a new sentence $\sigma$.  Now let $(R_0,\dots,R_m)$ be a list of all predicates (including $\equiv$) occurring in $\sigma'$, and let $\sigma''$ be the sentence
\begin{equation*}
\sigma'\land\Forall{\vec x}\Forall{\vec y}\bigl(\vec x\equiv\vec y\lto\bigwedge_{j\leq m}(R_j\vec x_j\lto R_j\vec y_j)\bigr).
\end{equation*}
(Here $\vec x_j$ and $\vec y_j$ are initial segments, of appropriate length, of $\vec x$ and $\vec y$ respectively; and $\vec x$ and $\vec y$ are long enough to make this possible.)  One shows that $\sigma$ is provable from $\sigma''$.  Also, if $\str A\models\sigma''$, then $\equiv^{\str A}$ is an equivalence-relation on $A$, and the set of equivalence-classes is the universe of a model of $\sigma$.

\subsection{Skolem normal form}

Every formula $\phi$ is equivalent to a formula $\hat\phi$ of the same signature in \textbf{prenex normal form,} that is, with all quantifiers in front.  For example, if $x$ is not free in $\theta$, then
\begin{align*}
\Forall x\phi\land\theta&\sim\Forall x(\phi\land\theta),&
\Forall x\phi\lor\theta&\sim\Forall x(\phi\lor\theta).
\end{align*}

We shall show that, for every formula $\phi$, there is a \emph{sentence} $\tilde\phi$, possibly with new predicates, with the following two properties.
\begin{compactenum}
\item
$\tilde\phi$ has the form $\Exists{\vec x}\Forall{\vec y}\theta$, where $\theta$ is quantifier-free.
\item
If $\tilde\phi$ is valid, then so is $\phi$; but if $\lnot\tilde\phi$ has a model, then $\lnot\phi$ will be satisfied in that model (that is, it will define a nonempty subset of that model).
\end{compactenum}
The sentence $\tilde\phi$ is a \textbf{Skolem normal form} for $\phi$.  We can obtain it as follows.  First, write out a generalization of $\phi$ in prenex normal form, as
\begin{equation*}
\Exists{\vec x}\Forall y\mathsf Q\;\theta,
\end{equation*}
where $\mathsf Q$ is a string of quantifiers, and $\theta$ is quantifier-free.  Introduce a new predicate $R$ and form the sentence
\begin{equation*}
\Exists{\vec x}(\Forall y(\mathsf Q\;\theta\lto R\vec xy)\lto\Forall yR\vec xy).
\end{equation*}
This has the second of the desired properties.  It is also equivalent to
\begin{gather*}
\Exists{\vec x}(\Exists y(\mathsf Q\;\theta\land\lnot R\vec xy)\lor\Forall yR\vec xy),\\
\Exists{\vec x}\Exists y((\mathsf Q\;\theta\land\lnot R\vec xy)\lor\Forall zR\vec xz),\\
\Exists{\vec x}\Exists y(\mathsf Q\;(\theta\land\lnot R\vec xy)\lor\Forall zR\vec xz),\\
\Exists{\vec x}\Exists y\mathsf Q\;((\theta\land\lnot R\vec xy)\lor\Forall zR\vec xz),\\
\Exists{\vec x}\Exists y\mathsf Q\;\forall z((\theta\land\lnot R\vec xy)\lor R\vec xz),
\end{gather*}
This last sentence is in prenex normal form, though perhaps not be in Skolem normal form.  Still, the number of universal quantifiers that precede existential quantifiers has decreased.  So the process terminates in a sentence that must be in Skolem normal form. 

\chapter{Boolean rings and Stone spaces}\label{ch:Boole}

\section{Boolean rings}

In the ring $(\pow{\Omega},\symdiff,\cap)$, every element is its own
square.  As we said in \S\ref{sect:id-fil} on page \pageref{eqn:x^2=x}, an arbitrary ring with this property is called a
\textbf{Boolean ring.}  We now establish the promised \emph{Stone
  Representation Theorem} \cite{MR1501865}, that for every Boolean ring $R$ the set $\spec$ of prime ideals of $R$ is such that $R$ embeds (as a ring) in $(\pow{\spec},\symdiff,\cap)$.
This result is comparable to the so-called Cayley Theorem, that every
group $G$ embeds in the group $(\Sym G,\circ,{}\inv,\id G)$ under
$g\mapsto(x\mapsto gx)$.

So let $R$ be a Boolean ring, namely a ring that satisfies the identity
\begin{equation*}
x^2=x.
\end{equation*}
We assume that $R$ has a unit (like all other rings in these notes), but we need not assume that $R$ is commutative, we shall prove it.  First, $R$ has characteristic $2$, since
\begin{align*}
  2x&=(2x)^2=4x^2=4x,& 0&=2x,& -x&=x.
\end{align*}
It follows that $R$ must be commutative, since now
\begin{gather*}
  x+y=(x+y)^2=x^2+xy+yx+y^2=x+xy+yx+y,\\
0=xy+yx,\\
yx=-xy=xy.
\end{gather*}
There are Boolean rings-without-units, for example $\powf{\upomega}$ (the set of finite subsets of $\upomega$, defined on page \pageref{powfO}); but again, we shall not consider these as Boolean rings.

We can rewrite the defining identity $x^2=x$ for Boolean rings as
\begin{equation*}
  0=x^2-x=x\cdot(x-1)=x\cdot(x+1).
\end{equation*}
Hence if $\mathfrak p$ is a prime ideal of $R$,\label{prime-maximal-2} then since $0\in\mathfrak p$, for all $x$ in $R$ we have either $x\in\mathfrak p$ or $x-1\in\mathfrak p$ (that is, $x+1\in\mathfrak p$).  Thus $\mathfrak p$ has just two cosets: itself and $1+\mathfrak p$.  Therefore
$R/\mathfrak p\cong\F_2$, a field, so $\mathfrak p$ must be maximal.  (We showed this for $\pow{\Omega}$ on page \pageref{prime-maximal}.)  Also,
\begin{equation*}
  x\in\mathfrak p\iff x+1\notin\mathfrak p.
\end{equation*}



As above, we let $\spec$ be the set of prime ideals of $R$, and if
$x\in R$, we let
$[x]$ be the set of prime ideals of $R$ that do \emph{not} contain
$x$.  If $\mathfrak p\in\spec$, we have
\begin{equation*}
  xy\in\mathfrak p\iff x\in\mathfrak p\lor y\in\mathfrak p,
\end{equation*}
hence
\begin{equation*}
  xy\notin\mathfrak p\iff x\notin\mathfrak p\And y\notin\mathfrak p.
\end{equation*}
Thus,
\begin{equation*}
  [xy]=[x]\cap[y].
\end{equation*}
Because $R$ has characteristic $2$, the sum of any two elements of
$\{x,y,x+y\}$ is the third.  Since
\begin{equation*}
  xy(x+y)=x^2+xy^2=xy+xy=0,
\end{equation*}
$\mathfrak p$ must contain at least one of $x$, $y$, and $x+y$.  Then
$\mathfrak p$ contains exactly one of these, or all:
\begin{equation*}
  x+y\notin\mathfrak p\iff(x\in\mathfrak p\And y\notin\mathfrak
  p)\lor(x\notin\mathfrak p\And y\in\mathfrak p).
\end{equation*}
Thus
\begin{equation*}
  [x+y]=[x]\symdiff[y].
\end{equation*}
Since finally $[1]=\spec$, we have now that $x\mapsto[x]$ is a homomorphism (of rings)
from $R$ to $\pow R$.  It is injective too, since if $x\neq0$, then
$x+1\neq1$, so $x+1$ generates a proper ideal that does not contain
$x$, and this ideal is included in a prime ideal, which must be in $[x]$, so
$[x]\neq\emptyset$. 

\section{Ultrafilters}\label{sect:ultra}

It follows now that an arbitrary Boolean ring $R$ has all of the operations and relations that can be defined on a Boolean ring $\pow{\Omega}$ and its sub-rings.  For example, $R$ is (partially) ordered by $\leq$ corresponding to $\subseteq$, where
\begin{equation*}
x\leq y\iff xy=x.
\end{equation*}
Also $R$ has operations $\lnot$ and $\wedge$, corresponding respectively to ${}\comp$ and $\cap$, so that
\begin{align*}
\lnot x&=x+1,&x\wedge y&=xy.
\end{align*}
Then
\begin{align*}
0&=x\land\lnot x,&1&=\lnot0,
\end{align*}
and the operation $\vee$ corresponding to $\cup$ can be given by
\begin{equation}\label{eqn:vee}
x\vee y=\lnot(\lnot x\land\lnot y).
\end{equation}
The structure $(R,\lnot,\wedge)$ is called a \textbf{Boolean algebra.}  Usually the signature of Boolean algebras is considered to be $\{0,1,\lnot,\wedge,\vee\}$; but again the additional operations can be defined from $\lnot$ and $\wedge$.

There is an equivalent axiomatic definition, which for the record can be given as follows.  A structure $(R,\lnot,\wedge)$ is a Boolean algebra if and only if $R$ has at least two elements, and the following equations are identities in the structure:
\begin{gather*}
	x\land y=y\land x,\\
	x\land(y\land z)=(x\land y)\land z,\\
	x\land x=x,\\
	\lnot\lnot x=x,\\
	(x\land\lnot x)\land y=x\land\lnot x,\\
	\lnot(x\land\lnot(y\land z))=\lnot(x\land\lnot y)\land\lnot(x\land\lnot z).
\end{gather*}
The last identity is equivalent to
\begin{equation*}
x\land(y\lor z)=(x\land y)\lor(x\land z),
\end{equation*}
when $\vee$ is defined as in \eqref{eqn:vee}.  The Boolean ring $(R,+,\cdot,0,1)$ can be recovered from the algebra by the rules
\begin{align*}
%x+y&=\lnot(\lnot(x\wedge\lnot y)\land\lnot(\lnot x\wedge y)),&
x+y&=(x\land\lnot y)\vee(\lnot x\land y),&
xy&=x\wedge y.
\end{align*}
Now we have the characterization of ideals on page \pageref{ideal}, as well as the definition of filters:  A subset $I$ of $R$ is an ideal if and only if
\begin{gather*}
	0\in I,\\
	x\leq y\And y\in I\implies x\in I,\\
	x\in I\And y\in I\implies x\vee y\in I,
\end{gather*}
and a subset $F$ is a \textbf{filter} if and only if $\{x+1\colon x\in F\}$ is an ideal, or equivalently
\begin{gather*}
	1\in F,\\
	x\in F\And x\leq y\implies y\in F,\\
	x\in F\And y\in F\implies x\wedge y\in F.
\end{gather*}
Then $F$ is an \textbf{ultrafilter} if and only if $\{x+1\colon x\in F\}$ is a prime ideal, and in this case $F$ is the complement in $R$ of the prime ideal.

\section{Stone spaces}

Given a Boolean ring $R$, we denote the set of its ultrafilters by
\begin{equation*}
\St R.
\end{equation*}
We have a bijection $\mathfrak p\mapsto\mathfrak p\comp$ from $\spec$ to $\St R$; this induces an isomorphism from $\pow{\spec}$ to $\pow{\St R}$.  In particular, if $x\in R$, we may now define
\begin{equation*}
[x]=\{\mathfrak f\in\St R\colon x\in f\},
\end{equation*}
so that $x\mapsto[x]$ is an embedding of $R$ in $\pow{\St R}$.  

A reason for working with $\St R$ rather than $\spec$ is that, as we shall discuss in \S\ref{sect:types} below, logical theories can be understood as filters, and then theories that are ultrafilters will be called \emph{complete theories.}  Also, in a \emph{topological space} $X$, the set of \emph{neighborhoods} of a point is a filter of $\pow X$.

The set $\St R$ is called the \textbf{Stone
  space} of $R$.  Indeed, since (as we saw)
\begin{align*}
  [x]\cap[y]&=[xy],&
  [1]&=\St R,
\end{align*}
the subsets $[x]$ of $\St R$ compose a \emph{basis} for a topology on $\St
R$ called the \textbf{Stone topology.}  Every union of sets $[x]$ is called
is \emph{open} in this topology, and it follows that:\label{topology}
\begin{compactenum}[1)]
  \item
if $\mathcal U$ is a finite collection of open sets, then
$\bigcap\mathcal U$ is also open---here we may by convention allow
$\bigcap\emptyset=\St R$;
%if $U$ and $V$ are open, then so is $U\cap V$;
\item
if $\mathcal U$ is a collection of open sets, then $\bigcup\mathcal U$
is open---in particular, $\bigcup\emptyset=\emptyset$, so this is
understood to be open.
\end{compactenum}
The complement of an open set is \emph{closed.}  Since
\begin{equation*}
  [x]\comp=[x+1],
\end{equation*}
the basic open sets $[x]$ are also closed.

Suppose $\mathfrak f$ and $\mathfrak g$ are distinct elements of $\St
R$.  Then we may assume $\mathfrak f\setminus\mathfrak g$ has an
element $x$.  In this case
\begin{align*}
  &\mathfrak f\in[x],&&\mathfrak g\in[x+1],&&[x]\cap[x+1]=\emptyset.
\end{align*}
Thus the Stone topology is \emph{Hausdorff:} it separates points.

Suppose $\bigcup_{x\in A}[x]=\St R$ for some subset $A$ of $R$.  Then
every ultrafilter of $R$ contains some element of $A$.  Then no prime ideal of $R$ includes $A$ (since otherwise its complement would be an ultrafilter disjoint from $A$).  Therefore the ideal $(A)$
of $R$ generated by $A$ must the improper ideal $R$.  In particular,
this ideal contains $1$.  But then $(A_0)$ must contain $1$ for some
finite subset $A_0$ of $A$.  In this case no prime ideal of $R$
includes $A_0$, so every ultrafilter contains an element of $A_0$, which means
\begin{equation*}
  \bigcup_{x\in A_0}[x]=\St R.
\end{equation*}
This shows the Stone topology is \emph{compact.}

Another way to prove this topology compact is the following.  We have
$\St R\included\pow R$, and we may identify the power $2^R$ with $\pow R$ under the map
\begin{equation*}
  (x_i\colon i\in R)\mapsto\{i\in R\colon x_i=1\}
\end{equation*}
from $2^R$ to $\pow R$.  (This map can be understood as $x\mapsto x\inv(1)$.)  If we give the set $2$ the discrete topology, then
$2^R$ can be 
given the corresponding \emph{product topology,} which is the weakest
topology in which all of the maps $x\mapsto x_i$ (where $i\in R$) are
continuous.  Since the factors $2$ are finite, this means the topology
has a basis comprising, for each finite subset $R_0$ of $R$, for each
$(a_i\colon i\in R_0)$ in $2^{R_0}$, the set $\{x\in
2^R\colon(x_i\colon i\in R_0)=(a_i\colon i\in R_0)\}$.  This set is
both open and closed.  Then $\St R$
has the subspace topology and is moreover a closed subset of $2^R$,
being the intersection of all closed sets of the forms
\begin{gather*}
\{x\in 2^R\colon x_1=1\},\\
\{x\in 2^R\colon x_{ab}=0\lor x_b=1\},\\
\{x\in 2^R\colon x_a=0\lor x_b=0\lor x_{ab}=1\},\\
\{x\in 2^R\colon x_a=0\iff x_{a+1}=1\}.
\end{gather*}
As $2^R$ is compact by the \emph{Tychonoff Theorem,}\label{Tychonoff} so must $\St R$
be compact.

Note that this case of the Tychonoff Theorem is easy to prove (and the general theorem is not much harder).  Suppose $\mathcal F$ is a collection of closed subsets of $2^R$ with the \emph{finite-intersection property,} that is, for every finite subset $\mathcal F_0$ of $\mathcal F$, the intersection $\bigcap\mathcal F_0$ is nonempty.  We want to show that $\bigcap\mathcal F$ itself is nonempty.  We may assume that the elements of $\mathcal F$ are \emph{basic} closed sets; and then we may assume that each element of $\mathcal F$ has the form $\{x\in 2^R\colon x_i=e\}$ for some $i$ in $R$ and $e$ in $2$.  By the finite intersection property, there is no $i$ in $R$ such that $\mathcal F$ contains both $\{x\colon x_i=0\}$ and $\{x\colon x_i=1\}$.  Then $\bigcap\mathcal F$ contains $a$, where
\begin{equation*}
a_i=\begin{cases}
	e,&\text{ if }\{x\colon x_i=e\}\in\mathcal F,\\
	0,&\text{ otherwise.}
\end{cases}
\end{equation*}

We can compute
\begin{align*}
  [x]\cup[y]&=([x]\comp\cap[y]\comp)\comp\\
&=([x+1]\cap[y+1])\comp\\
&=[(x+1)(y+1)]\comp\\
&=[xy+x+y+1]\comp\\
&=[xy+x+y]\\
&=[x\vee y].
\end{align*}
Consequently, the only open sets that are also closed are the basic
open sets, that is, the sets $[x]$.  For if the open set
$\bigcup_{x\in A}[x]$ is also closed, then (since closed subsets
of compact spaces are compact), we have
\begin{equation*}
  \bigcup_{x\in A}[x]=[x_0]\cup\dots\cup[x_{n-1}]=[x_0\vee\dots\vee x_{n-1}]
\end{equation*}
for some $x_i$ in $A$.  Thus the subsets of $\St R$ that are both closed and
open---\emph{clopen}---compose a Boolean algebra or ring, which is the isomorphic
image of $R$ under $x\mapsto[x]$. 

An arbitrary compact Hausdorff space with a basis of clopen sets can
be called a \textbf{Stone space} simply.  Suppose $S$ is one of these,
and let $\Br S$ be the set of clopen subsets of $S$. Then $\Br S$ is a
Boolean sub-ring of $\pow S$.  In the special case where $S=\St R$, we
have just noted
\begin{equation*}
  R\cong\Br{\St R}.
\end{equation*}
In the general case, for every point $P$ in $S$, the set $\{U\in\Br
S\colon P\in U\}$ of basic neighborhoods of $P$ is a filter and in fact an ultrafilter of $\Br S$.
 Thus we have a map
\begin{equation}\label{eqn:P}
  P\mapsto\{U\in\Br S\colon P\in U\}
\end{equation}
from $S$ to $\St{\Br S}$.  Since $S$ is Hausdorff, the map is
injective.  Suppose $\mathfrak f\in\St{\Br S}$.  The intersection of every
finite subset of $\mathfrak f$ is an element of $\mathfrak f$; in particular, it is a nonempty subset of $S$.  Thus $\mathfrak f$ has the finite intersection property.  Since $S$
is compact, $\bigcap\mathfrak f$ itself must be a nonempty subset of
$S$.  Since also again $S$ is Hausdorff, $\bigcap\mathfrak f$ must consist of a single point, $P$; and then we must have
\begin{equation*}
  \mathfrak f=\{U\in\Br S\colon P\in U\}.
\end{equation*}
So the map in \eqref{eqn:P} is a bijection from $S$ to $\St{\Br S}$.  In fact it is a
homeomorphism.  For, it takes every clopen subset $V$ of $S$ (that is,
every element $V$ of $\Br S$) to the subset
\begin{equation*}
  \bigl\{\{U\in\Br S\colon P\in U\}\colon P\in V\bigr\}
\end{equation*}
of $\St{\Br S}$; and this subset is $[V]$, namely $\{\mathfrak f\in\St{\Br S}\colon V\in\mathfrak f\}$, since
\begin{equation*}
V\in\{U\in\Br S\colon P\in U\}\iff P\in V.
\end{equation*}

\section{Boolean operations}

We observed in \S\ref{sect:ultra} that Boolean rings and Boolean algebras are `interdefinable': every Boolean ring is also a Boolean algebra whose basic operations are the interpretations in the ring of certain terms; and then the Boolean ring can be obtained from the algebra in the same way.

A \textbf{Boolean operation} on a power-set $\pow{\Omega}$ is just an operation on $\pow{\Omega}$ that is the interpretation of a term in the signature of rings or Boolean algebras.  We should like to verify that every operation on $\pow{\Omega}$ that can be defined without reference to $\Omega$ itself is a Boolean operation.  One way of doing this is as follows.

Suppose we have $n$ subsets $X^0$, \dots, $X^{n-1}$ of $\Omega$.  For each element $\sigma$ of $2^n$, there is a subset $X_{\sigma}$ of $\Omega$ given by
\begin{equation*}
X_{\sigma}=X^0_{\sigma}\cap\dots\cap X^{n-1}_{\sigma},
\end{equation*}
where
\begin{equation*}
X^i_{\sigma}=
\begin{cases}
	X^i,&\text{ if }\sigma(i)=1,\\
	(X^i)\comp,&\text{ if }\sigma(i)=0.
\end{cases}
\end{equation*}
See Figure \ref{fig:X2} for the cases $n=2$ and $n=3$ (here each set $X_{\sigma}$ is labelled with $\sigma$).
\begin{figure}[ht]
\psset{unit=8mm,linewidth=1pt}
\mbox{}\hfill
\begin{pspicture}(-3,-2.866)(3,2)
\pscircle(1,0)2
\pscircle(-1,0)2
\rput(0,0){\makebox[0pt][c]{$(1,1)$}}
\rput(-2,0){\makebox[0pt][c]{$(1,0)$}}
\rput(2,0){\makebox[0pt][c]{$(0,1)$}}
\rput(-3,2.4){\makebox[0pt][l]{$(0,0)$}}
\end{pspicture}
\hfill
\begin{pspicture}(-3,-2)(3,3.73)
%\psgrid
\pscircle(-1,0){2}
\pscircle(1,0)2
\pscircle(0,1.73)2
\rput(0,0.58){\makebox[0pt][c]{$(1,1,1)$}}
\rput(0,2.7){\makebox[0pt][c]{$(1,0,0)$}}
\rput(-2,-0.5){\makebox[0pt][c]{$(0,1,0)$}}
\rput(2,-0.5){\makebox[0pt][c]{$(0,0,1)$}}
\rput(0,-0.6){\makebox[0pt][c]{$(0,1,1)$}}
\rput(1.2,1.5){\makebox[0pt][c]{$(1,0,1)$}}
\rput(-1.2,1.5){\makebox[0pt][c]{$(1,1,0)$}}
\rput(3,3.68){\makebox[0pt][r]{$(0,0,0)$}}
\end{pspicture}
\hfill\mbox{}
\caption{Boolean combinations}\label{fig:X2}
\end{figure}
In case $n=0$, the set $2^n$ has the unique element $0$ (the empty function), and then $X_{\sigma}$ should be understood as $\Omega$.  In any case, the sets $X_{\sigma}$ partition $\Omega$ into at most $2^n$ subsets---or $\abs{2^n}$ subsets, if we still consider $2^n$ as the set of functions from $n$ to $2$.
For every subset $S$ of $2^n$ in this sense, the subset $\bigcup_{\sigma\in S}X_{\sigma}$ of $\Omega$ is a Boolean combination of the sets $X^i$; and every Boolean combination of these sets is of this form.  Thus the number of Boolean combinations of the $X^i$ is at most $2^{2^n}$.  (It is less, if one of them is included in the union of the others.)


\chapter{More model theory}

\section{The structure of definable relations}\label{sect:def}

The structures that we have worked with so far are more precisely called \textbf{one-sorted structures.}  By contrast, a vector-space is a two-sorted structure, with a sort for the vectors and a sort for the scalars.  It is difficult to use a general notation for structures of arbitrarily many sorts; so we just describe the general situation for one-sorted structures, and then we point out that things can be adapted to many-sorted structures as needed.

The definable relations of a (one-sorted structure) $\str A$ are themselves elements of a many-sorted structure, with a sort for each finite subset $I$ of $\upomega$: this sort corresponds to the set $\{x_i\colon i\in I\}$ of variables.

The $n$-ary relations on $A$ compose the set $\pow{A^n}$.  Suppose $B\included A$.  The set of $n$-ary $B$-definable relations of $\str A$ can be denoted by
\begin{equation*}
\Def.
\end{equation*}
This is a subset of $\pow{A^n}$, and moreover it closed under the Boolean operations; that is, $\Def$ is (the universe of) a Boolean sub-algebra of $\pow{A^n}$.  To check this, we need only note:
\begin{align}\label{eqn:not-and}
(\phi^{\str A})\comp&=(\lnot\phi)^{\str A},&\phi^{\str A}\cap\psi^{\str A}&=(\phi\land\psi)^{\str A},
\end{align}
and also
\begin{equation*}
\emptyset=\Bigl(\bigvee_{i<n}x^i\neq x^i\Bigr)^{\str A},
\end{equation*}
so that $\Def$ has the two distinct elements $\emptyset$ and its complement $A^n$.

On the set $\pow{A^n}$, if $n>1$, additional operations besides the Boolean operations are possible.  Indeed, if $\sigma$ is a permutation of $n$, then there is a function $\sigma^*$ from $A^n$ to $A^n$, given by
\begin{equation*}
\sigma^*(x^0,\dots,x^{n-1})=(x^{\sigma(0)},\dots,x^{\sigma(n-1)}).
\end{equation*}
Now the singulary operation $X\mapsto\sigma^*[X]$ on $\pow{A^n}$ is induced.



The same idea gives us functions from $\pow{A^n}$ to $\pow{A^m}$.  Indeed, suppose now $\sigma$ is a function from $m$ to $n$, where $n>0$ or $m=0$.  For example, if $m<n$, then $\sigma$ could be the inclusion of $m$ in $n$.  Or if $m=n+1$, then $\sigma$ could be given by
\begin{equation}\label{eqn:n+1}
\sigma(i)=\begin{cases}
	i,&\text{ if }i<n,\\
	n-1,&\text{ if }i=n.
\end{cases}
\end{equation}
In any case, a function $\sigma^*$ from $A^n$ to $A^m$ is induced, given by
\begin{equation*}
\sigma^*(x^0,\dots,x^{n-1})=(x^{\sigma(0)},\dots,x^{\sigma(m-1)}).
\end{equation*}
Then we have the function $X\mapsto\sigma^*[X]$ from $\pow{A^n}$ to $\pow{A^m}$; here
\begin{equation*}
\sigma^*[X]=\{(x^{\sigma(0)},\dots,x^{\sigma(m-1)})\colon(x^0,\dots,x^{n-1})\in X\}.
\end{equation*}
For example, if $n=m+1$, and $\sigma$ is the inclusion of $m$ in $n$, then
\begin{equation*}
\sigma^*[X]=\{(x^0,\dots,x^{m-1})\colon(x^0,\dots,x^m)\in X\};
\end{equation*}
but since the appearance of $x^m$ here may seem peculiar, we can also write
\begin{equation*}
\sigma^*[X]=\{(x^0,\dots,x^{m-1})\colon(x^0,\dots,x^m)\in X\text{ for some }x^m\}.
\end{equation*}
For another example, if $m=2$ and $n=1$, so that $\sigma$ must be the constant function $x\mapsto0$ on $2$, then
\begin{equation*}
\sigma^*[X]=\{(x,x)\colon x\in X\}.
\end{equation*}
In the general situation, we also have $X\mapsto\sigma_*[X]$ from $\pow{A^m}$ to $\pow{A^n}$, where
  \begin{equation*}
\sigma_*[X]=(\sigma^*)\inv[X]=\{(x^0,\dots,x^{n-1})\in A^n\colon(x^{\sigma(0)},\dots,x^{\sigma(m-1)})\in X\}.
\end{equation*}
For example, if $\sigma$ is the inclusion of $m$ in $n$, then $\sigma_*[X]$ can be understood as $X\times A^{n-m}$; while if $\sigma\colon 2\to 1$, then
\begin{equation*}
\sigma_*[X]=\{x\in A\colon(x,x)\in X\}.	
\end{equation*}
Note that, in general, every function $\sigma$ from $m$ to $n$ is a composition of:
\begin{compactenum}
\item
permutations of some $k$,
\item
inclusions of some $k$ in $k+1$;
\item
maps from some $k+1$ to $k$ as in \eqref{eqn:n+1}.
\end{compactenum}
It should be clear that $X\mapsto\sigma^*[X]$ takes $\Def[m]$ to $\Def$, and $X\mapsto\sigma_*[X]$ takes $\Def$ to $\Def[m]$.

The elements of $\upomega$ are also finite subsets of $\upomega$.  We could work with arbitrary finite subsets of $\upomega$.  A formula whose free variables compose the set $\{x_i\colon i\in I\}$ then defines in $\str A$ a subset of $A^I$; and then we have the subsets $\Def[I]$ of $\pow{A^I}$.  

Consider the collection of all indexed families $(P_I\colon I\in\powf{\upomega})$, where $P_I\included\pow{A^I}$, and
\begin{compactitem}
\item
each $P_I$ is closed under the Boolean operations,
\item
if $\sigma\colon I\to J$, the function $X\mapsto\sigma^*[X]$ takes $P_J$ to $P_I$, and $X\mapsto\sigma_*[X]$ takes $P_I$ to $P_J$,
\item
for each $n$ in $\upomega$, for each $n$-ary predicate $R$ in $\sig$, $P_n$ contains $R^{\str A}$,
\item
for each $n$ in $\upomega$, for each $n$-ary operation-symbol $F$ in $\sig$, $P_{n+1}$ contains $\{(\vec a,b)\in A^{n+1}\colon F^{\str A}(\vec a)=b\}$ (that is, $(F\vec x=x^n)^{\str A}$).
\item
for each $c$ in $B$, $P_1$ contains $\{c\}$.
\end{compactitem}
The indexed family $(\Def[I]\colon I\in\powf{\upomega})$ is a minimum among these families.



\section{Lindenbaum--Tarski algebras}

For any signature $\sig$ and $n$ in $\upomega$, let us denote by
\begin{equation*}
\Fm{\sig}
\end{equation*}
the set of $n$-ary formulas of $\sig$.  Two elements $\phi$ and $\psi$ of $\Fm{\sig}$ are said to be \textbf{logically equivalent} if the formula $\phi\liff\psi$ is a validity in the sense of Chapter \ref{ch:complete}, that is, for
every structure $\str A$ of $\sig$,
\begin{equation*}
  \phi^{\str A}=\psi^{\str A},
\end{equation*}
or equivalently the sentence
\begin{equation*}
  \Forall{\vec x}(\phi(\vec x)\liff\psi(\vec x))
\end{equation*}
is true in all structures in $\Mod$.  The set of logical equivalence-classes of elements of $\Fm{\sig}$ is denoted by
\begin{equation*}
\LT n{\sig}.
\end{equation*}
This is the $n$th \textbf{Lindenbaum--Tarski algebra} of $\sig$, and it is a Boolean algebra in a fairly obvious way.  The rest of this section is devoted to spelling this out.

The set $\Fm{\sig}$ can be understood as a structure equipped with the operations $\lnot$ and $\land$.  A structure without relations, but only operations, is called an \textbf{algebra.}  So we have an algebra $(\Fm{\sig},\lnot,\land)$.  This algebra is \emph{not} a Boolean algebra, simply because, for example, $\lnot\lnot\phi$ is never the same formula as $\phi$.  

Still, if $\str A\in\Mod$ and $B\included A$, the function $\phi\mapsto\phi^{\str A}$ is an epimorphism from $(\Fm{\sig(B)},\lnot,\land)$ to $(\Def,{}\comp,\cap)$: it is a surjection that respects the operations, as in \eqref{eqn:not-and} on page \pageref{eqn:not-and}.

For an arbitrary homomorphism $h$ from an algebra $\str M$ to $\str N$, the \textbf{(generalized) kernel} of $h$ is the binary relation $\{(x,y)\colon h(x)=h(y)\}$ on $M$.  If the structures are rings, then the connection between the usual kernel and the generalized kernel is shown by the equivalence
\begin{equation*}
h(x)=h(y)\iff h(x-y)=0.
\end{equation*}
Such an equivalence is not always available for arbitrary algebras.  Still, the generalized kernel is an equivalence-relation; and then a quotient $\str M/\ker(h)$ can be defined, which is isomorphic to the image of $\str M$ under $h$.

In particular then, there is a quotient of $(\Fm{\sig(B)},\lnot,\land)$ that is a Boolean algebra, namely the quotient by the kernel of $\phi\mapsto\phi^{\str A}$: this quotient is isomorphic to $\Def$.

The kernel of a homomorphism on the arbitrary algebra $\str M$ is an example of a \textbf{congruence-relation:} an equivalence-relation $\sim$ on $M$ that respects the algebraic structure of $\str M$ in the sense that, for every $n$ in $\upomega$, for every basic $n$-ary operation of $\str M$,
\begin{equation*}
x^0\sim y^0\And\dots\And x^{n-1}\sim y^{n-1}\implies F(\vec x)\sim F(\vec y).
\end{equation*}
In this case there is a well-defined quotient $\str M/\mathord{\sim}$, and there is a quotient-map from $\str M$ to $\str M/\mathord{\sim}$ whose kernel is of course $\sim$.

We have seen the one-to-one correspondence between ideals and filters of a Boolean algebra.  There is also a one-to-one correspondence between ideals and congruence-relations of a Boolean algebra, namely
\begin{equation*}
I\mapsto\{(x,y)\colon x+I=y+I\},
\end{equation*}
with inverse ${\sim}\mapsto\{x\colon x\sim 0\}$.

The set of congruence-relations on $(\Sn{\sig},\lnot,\land)$ (or on any algebra) is closed under arbitrary intersections.  The intersection of the set of kernels of all homomorphisms $\phi\mapsto\phi^{\str A}$, where $\str A\in\Mod$, is just the relation of logical equivalence defined above, and $\LT n{\sig}$ is the quotient of $\Fm{\sig}$ by this relation.  We shall henceforth each formula with its logical equivalence-class, that is, confuse each element of $\Fm{\sig}$ with its image in $\LT n{\sig}$.






\section{Theories and type-spaces}\label{sect:types}


By G\"odel's Completeness Theorem, the relation $\proves$ can be considered as a binary relation on $\LT n{\sig}$; indeed, it is the ordering induced by the algebraic structure.  That is, $\phi\proves\psi$ means that the formula $\phi\lto\psi$ is a validity.  With respect to the ordering, the greatest and least elements of the algebra (that is, the $1$ and the $0$) can be denoted respectively by
\begin{align*}
&\top,&&\bot.
\end{align*}

Every theory of $\sig$ can be understood as a filter of $\LT0{\sig}$.  That is, if $\mathcal K\included\Mod$, then $\Th{\mathcal K}$ has the closure properties required of a filter:
\begin{compactenum}[1)]
\item
 it contains $\top$;
 \item
if it contains $\sigma$ and $\tau$, then it contains $\sigma\land\tau$;
 \item
if it contains $\sigma$, and if $\sigma\proves\tau$, then it contains $\tau$.
\end{compactenum}
Suppose $\Gamma\included\LT0{\sig}$.  Then the set
  \begin{equation*}
\Th{\Mod[\Gamma]}
\end{equation*}
is a filter of $\LT0{\sig}$.  This filter is the set of all elements of $\LT0{\sig}$ that are true in all models of $\Gamma$.  But there is also a filter generated by $\Gamma$, namely the set of all $\sigma$ such that $\bigwedge\Gamma_0\proves\sigma$ for some finite subset $\Gamma_0$ of $\Gamma$.  By the Compactness Theorem (Theorem \ref{thm:compact}, page \pageref{thm:compact}), these two filters are the same.  If $\sigma$ is a member, we may write
\begin{equation*}
\Gamma\proves\sigma.
\end{equation*}
By the Compactness Theorem then, every proper filter of $\LT0{\sig}$ has a model.

The sameness of the two foregoing filters is not trivial, because the Compactness Theorem is not trivial.  The Compactness Theorem does not follow merely from the compactness of Stone spaces.  For example, the \emph{second-order} theory of $(\upomega,0,x\mapsto x+1)$ is axiomatized by
\begin{gather*}
\Forall xx+1\neq0,\\
\Forall x\Forall y(x+1=y+1\lto x=y),\\
\Forall X(0\in X\land\Forall y(y\in X\lto y+1\in X)\lto\Forall yy\in X).
\end{gather*}
All models of these axioms are isomorphic to one another.  In particular, there is no model that is also a model of each of the sentences $c\neq0$, $c\neq1$, $c\neq2$, and so on, where $c$ is a new constant.  However, every finite set of these sentences has a model, if the interpretation of $c$ is large enough.

If $T$ is a theory of $\sig$, then two formulas $\phi$ and $\psi$ are \textbf{equivalent \emph{modulo} $T$} if
\begin{equation*}
T\proves\Forall{\vec x}(\phi(\vec x)\liff\psi(\vec x)).
\end{equation*}
The equivalence-classes with respect to this relation compose the Boolean algebra
\begin{equation*}
\LT nT.
\end{equation*}
Then $\LT n{\sig}$ is $\LT n{\emptyset}$ or $\LT n{\top}$.  The Stone space of $\LT nT$ can be denoted by
\begin{equation*}
\St[n]T.
\end{equation*}
The elements of this space are called \textbf{$n$-types} of $T$---or one may call them \textbf{complete $n$-types} of $T$, if one wants to use the word \emph{type} more generally for arbitrary filters of $\LT nT$ or just arbitrary collections of $n$-ary formulas.  In any case, an element of $\St[0]{\sig}$ is called a \textbf{complete theory.}

Suppose $\Phi\in\St[n]T$.  If $\Phi_0$ is a finite subset of $\Phi$, then $\bigwedge\Phi_0$ is \emph{not} equivalent to $\bot$ \emph{modulo} $T$.  In this case $T\cup\Bigl\{\Exists{\vec x}\bigwedge\Phi_0(\vec x)\Bigr\}$ has a model.

Suppose also $\str A\models T$.  An element $\vec a$ of $A^n$ \textbf{realizes} $\Phi$ if, for all $\phi$ in $\Phi$,
\begin{equation*}
\str A\models\phi(\vec a).
\end{equation*}
In this case, we may say also that $\str A$ itself \textbf{realizes} $\Phi$.  By Compactness, some model of $T$ realizes $\Phi$.  Indeed, $\str A$ has an elementary extension that realizes $\Phi$.

\section{Saturation}

We are often concerned with the \emph{parameters} used in formulas and types.  If $\str M\in\Mod$, and $A$ is a subset of $M$, then by $\str M_A$ we mean $\str M$, considered as having signature $\sig(A)$.  We may then denote $\St[n]{\Th{\str M_A}}$ simply by
\begin{equation*}
\St[n]A;
\end{equation*}
an element of this can be called a type \textbf{over} $A$.  For every infinite cardinal $\kappa$, a structure is called \textbf{$\kappa$-saturated} if it realizes every type that has fewer than $\kappa$-many parameters.  In particular, a structure is \textbf{$\upomega_1$-saturated} or \textbf{$\aleph_1$-saturated} if it realizes all types in countably many parameters.

\begin{theorem}\label{thm:sat}
For every structure $\str A$ with a countable signature, every non-principal ultrapower $\str A^{\upomega}/P$ of $\str A$ is $\upomega_1$-saturated.
\end{theorem}

\begin{proof}
If $\Phi$ is a type in countably many parameters, then $\Phi$ itself is countable, so we can write it as $\{\phi_n\colon n\in\upomega\}$.  Let $\vec a_n$ satisfy $\phi_0\land\dots\land\phi_n$ in $\str A$.  Then
\begin{equation*}
k\leq n\implies\str A\models\phi_k(\vec a_n).
\end{equation*}
Therefore, if $P$ is a non-principal prime ideal of $\pow{\upomega}$, then $(\vec a_n\colon n\in\upomega)/P$ realizes $\Phi$ in $\str A^{\upomega}/P$.
\end{proof}

There is a version \cite[Thm 6.1.1, p.\ 384]{MR91c:03026} of the foregoing for uncountable index-sets (or exponents) $\Omega$; but then $P$ must have a countable subset whose union is $\Omega$ (so one should show that such prime ideals can be found).

\chapter{Rings}\label{ch:rings}

\section{Ideals}

In this chapter, as throughout these notes, the word \textbf{ring} will always mean a commutative unital ring.  The letter $R$ will always denote a ring in this sense.  We have spent time with Boolean rings; now we work more generally (and also review some of the basic facts about integral domains and fields that we have already used).  The main point is to develop some of the algebraic geometry that will be used in the examples of ultraproducts in the remaining two chapters.

The following are equivalent conditions on the ring $R$:
\begin{compactitem}
\item
$1=0$ in $R$.
\item
$R$ has only one element.
\end{compactitem}
A ring meeting either of these conditions will be called \textbf{trivial.}

Let the variables $x$ and $y$ range over $R$.  If $x\neq0$ and $y\neq0$
(that is, if $x\in R\setminus\{0\}$ and $y\in R\setminus\{0\}$), but
\begin{equation*}
xy=0,
\end{equation*}
then $x$ and $y$ are called \textbf{zero-divisors.}  An \textbf{integral domain} is a nontrivial ring with no zero-divisors.\footnote{Lang \cite[pp.\ 91--92]{Lang-alg} recommends
  \emph{entire} as the adjective form of \emph{integral domain,}
  observing that \emph{integral} would have been better, had it not
  already been taken for other purposes.}  Equivalently, $R$ is an integral domain if and only if
\begin{equation*}
xy=0\land x\neq0\implies y=0.
\end{equation*}

For example, the ring $\Z$ of rational integers is an integral domain.  So are the polynomial rings $K[X]$, $K[X,Y]$, and so forth, where $K$ is a field.  However, suppose $n$ is a positive integer.  Then $\Z/n\Z$ (namely the ring of integers \emph{modulo} $n$) is an integral domain if and only if $n$ is prime.  

Here $n\Z$ is the ideal $\{nx\colon x\in \Z\}$ of $\Z$.  In general, an \textbf{ideal} of $R$ is an additive subgroup $I$ such that the quotient group $R/I$ is also a ring with respect to the multiplication given by
\begin{equation*}
(x+I)\cdot(y+I)=xy+I.
\end{equation*}
That is, for $I$ to be an ideal, we need
\begin{equation*}
(x+I)\cdot I=I
\end{equation*}
(since $I$ is the zero of $R/I$); this means
\begin{equation*}
y\in I\implies xy\in I;
\end{equation*}
and this is enough.

Every ideal contains $0$ at least; if it contains nothing else, it is the \textbf{trivial ideal} or \textbf{zero-ideal.}

A \textbf{proper} ideal of $R$ is an ideal different from $R$ itself: equivalently, it is an ideal that does not contain $1$.

A proper ideal $I$ of $R$ is called \textbf{prime} if
\begin{equation*}
xy\in I\And x\notin I\implies y\in I.
\end{equation*}
Compare this with the definition of integral domains:

\begin{theorem}
A ring is an integral domain if and only if the trivial ideal is prime.
\end{theorem}

For another example, $\{0\}\cup\{\text{zero-divisors}\}$ is a prime ideal, which we shall denote by
\begin{equation*}\label{eqn:I_0}
I_0.
\end{equation*}
So $R$ is an integral domain if and only if $I_0=\{0\}$.
A positive integer $n$ is prime if and only if $n\Z$ is a prime ideal of $\Z$.

\begin{theorem}
Let $I$ be an ideal of $R$.  Then
$R/I$ is an integral domain if and only if $I$ is prime.
\end{theorem}

\begin{proof}
We have that $R/I$ is nontrivial if and only if $I$ is proper. 
Assuming $I$ is proper we have that the following are equivalent.
\begin{compactitem}
\item
$R/I$ is an integral domain.
\item
$(x+I)\cdot(y+I)=I\And x+I\neq I\implies y+I=I$.
\item
$xy\in I\And x\notin I\implies y\in I$.
\item
$I$ is prime.\qedhere
\end{compactitem}
\end{proof}

A \textbf{unit} of a ring is a divisor of $1$.  That is, if
\begin{equation*}
xy=1,
\end{equation*}
then both $x$ and $y$ are units.  The units of $R$ compose a multiplicative subgroup of $R$, denoted by
\begin{equation*}
\units R.
\end{equation*}
In a trivial ring, $0$ is a unit.
but zero-divisors are never units or $0$; that is, if $R$ has any zero-divisors, they belong to $R\setminus(\units R\cup\{0\})$.  We can also write
\begin{equation*}
1\neq0\implies I_0\cap\units R=\emptyset.
\end{equation*}

A ring is a \textbf{field} if all nonzero elements are units.  That is, $R$ is a field if and only if $R=\units R\cup\{0\}$.  In particular, fields have no zero-divisors, so they are integral domains.

The standard examples of fields are $\Q$, $\R$, and $\C$.  Moreover, if $p$ is prime, then $\Z/p\Z$ is (not only an integral domain, but) a field.

A \textbf{maximal ideal} is a proper ideal that is maximal as such.  An ideal $I$ of $R$ is maximal if $I$ is a proper ideal and, for all ideals $J$ of $R$,
\begin{equation*}
I\included J\And I\neq J\implies J=R.
\end{equation*}
If $A\included R$, then by
\begin{equation*}
(A)
\end{equation*}
is meant the smallest ideal of $R$ that includes $A$.  Then $(A)$ is the set of sums
\begin{equation*}
a^0x_0+\dots+a^{n-1}x_{n-1},
\end{equation*}
where $a^i\in A$ and $x_i\in R$ and $n\in\upomega$.  In particular, $n$ can be $0$, and in this case the sum above is $0$.  Thus $(\emptyset)=\{0\}$, the trivial ideal.

When $A=\{a_0,a_1,\dots\}$, we may write $(A)$ as $(a_0,a_1,\dots)$.  In particular, $R=(1)$.  Also the trivial ideal is $(0)$, where $0$ is the ring element, not the empty set; but then this notation is redundant: strictly we should be able to write the zero-ideal as $(\ )$.



A proper ideal $I$ of $R$ is maximal if and only if,  for all $x$ in $R\setminus I$, we have
\begin{equation*}
(I\cup\{x\})=R,
\end{equation*}
that is,
\begin{equation*}
1\in(I\cup\{x\}),
\end{equation*}
that is, for some $y$ in $R$,
\begin{equation*}
1\in xy+I.
\end{equation*}

\begin{theorem}\label{thm:max-field}
Let $I$ be an ideal of $R$.  Then
$R/I$ is a field if and only if $I$ is maximal.
\end{theorem}

\begin{proof}
Again, $R/I$ is nontrivial if and only if $I$ is proper. 
Assuming $I$ is proper we have that the following are equivalent.
\begin{compactitem}
\item
$R/I$ is a field.
\item
If $x+I\neq I$, then
for some $y$, $(x+I)(y+I)=1+I$.
\item
If $x\notin I$, then
for some $y$, $1\in xy+I$.
\item
$I$ is maximal.\qedhere
\end{compactitem}
\end{proof}

\begin{corollary}
Maximal ideals are prime.
\end{corollary}

The converse is true in $\Z$.

\section{Localizations}

Throughout this section, the ring $R$ will be nontrivial.  It will then have a \emph{quotient field} (or \emph{field of fractions}) constructed as $\Q$ is constructed from $\Z$.  

A \textbf{multiplicative subset} of a ring is just a subset that is closed under multiplication.  More precisely, if $S$ is a multiplicative subset of $R$, this means that for all finite subsets $\{a^k\colon k<n\}$ of $S$, the product $\prod_{k<n}a^k$ is also in $S$.  In particular, $1\in S$, since $\prod_{k<n}a^k$ is $1$ when $n=0$ (that is, the empty product is multiplicatively neutral element $1$, just as the empty sum is $0$).

For example, the set $R\setminus I_0$ of non-zero non-zero-divisors of $R$ is a multiplicative subset of $R$; more generally, so is the complement of any prime ideal; and so are $\{1\}$ and $\units R$.  

\begin{lemma}
If $S$ is a multiplicative subset of $R$, there is an equivalence-relation $\sim$ on $R\times S$ given by
\begin{equation}\label{eqn:rs}
(a,b)\sim(x,y)\iff(ay-bx)\cdot s=0\text{ for some $s$ in $S$}.
\end{equation}
\end{lemma}

If $R$ is an integral domain and $0\notin S$, or more generally if $S\cap I_0=\emptyset$, then the equivalence-relation of the lemma is given by
\begin{equation*}
(a,b)\sim(x,y)\iff ay-bx=0;
\end{equation*}
but we shall be interested in the more general situation, especially in Chapter \ref{sect:vN}, and then a broader condition as in \eqref{eqn:rs} is needed.

The $\sim$-class of $(a,b)$ is denoted by
\begin{equation*}
\frac ab
\end{equation*}
or $a/b$.  The set of these classes is denoted by
\begin{equation*}
S\inv R;
\end{equation*}
it can be called the \textbf{localization} of $R$ at $S$.

\begin{theorem}
Let $S$ be a multiplicative subset of $R$.
The localization $S\inv R$ is a ring with respect to the usual operations:
\begin{align*}
\frac ab+\frac cd&=\frac{ad+bc}{bd},&\frac ab\cdot\frac cd=\frac{ac}{bd}.
\end{align*}
There is a homomorphism $x\mapsto x/1$ from $R$ to $S\inv R$.  This homomorphism is injective if and only if $S\cap I_0=\emptyset$.
\end{theorem}

For the homomomorphism of the theorem, the condition of injectivity is not always met.  It \emph{is} met when $0\notin S$ and also $R$ is an integral domain (that is, $I_0$ is trivial).  In particular, we have

\begin{theorem}\label{thm:id}
A ring is an integral domain if and only if it a sub-ring of a field.
\end{theorem}

\begin{proof}
For sufficiency, note that a zero-divisor of a sub-ring is a zero-divisor of the original ring.

To show necessity, we note that an integral domain $R$ embeds in the ring $(R\setminus\{0\})\inv R$, which is a field.
\end{proof}

The field $(R\setminus\{0\})\inv R$ in the proof is the \textbf{quotient field} (or \textbf{field of fractions}) of $R$ (assuming $R$ is a integral domain; otherwise this field is $(R\setminus I_0)\inv R$).

Every substructure of a field is a ring.\label{id}  Therefore, by Theorem \ref{thm:TA} on page \pageref{thm:TA}, if $T$ is field-theory, then $T_{\forall}$ is the theory of integral domains.  The following is obvious, but should be noted:



\begin{theorem}
If an integral domain embeds in a field, then the embedding factors through the fraction field of the integral domain.  That is, if $R$ is an integral domain embedding under $\iota$ in its fraction-field $K$, and $R$ embeds in a field $L$ under $\phi$, then $K$ embeds in $L$ under a map $\psi$ such that $\psi\circ\iota=\phi$.\hfill\qedsymbol
\end{theorem}

See Figure \ref{fig:qf}.
\begin{figure}[ht]
\begin{equation*}
\xymatrix{
R\ar[r]^{\phi}\ar[d]_{\iota}&L\\
K\ar@{.>}[ur]_{\psi}&
}
\end{equation*}
\caption{The universal property of the quotient field}\label{fig:qf}
\end{figure}
Suppose now $K$ is a field, and $L$ is a field of which $K$ is a subfield, that is, $K\included L$.  In short, $L/K$ is a field-extension.  If $n\in\upomega$, we may let $\vec X$ be an $n$-tuple $(X^0,\dots,X^{n-1})$ of indeterminates, so that we can form the \textbf{ring of polynomials} in $\vec X$ over $K$, denoted by
\begin{equation*}
K[\vec X].
\end{equation*}
The fraction-field of this ring is denoted by
\begin{equation*}
K(\vec X);
\end{equation*}
it is the \textbf{field of rational functions} in $\vec X$ over $K$.  Suppose now $\vec a\in L^n$.  Then there is a function $f\mapsto f(\vec a)$ (or $X^i\mapsto a^i$) from $K[\vec X]$ to $L$.  The range of this function is denoted by
\begin{equation*}
K[\vec a],
\end{equation*}
and the fraction-field of this ring is denoted by
\begin{equation*}
K(\vec a);
\end{equation*}
by the last theorem, we may consider this field as a subfield of $L$.  In other words,
\begin{compactitem}
\item
$K[\vec a]$ is the smallest sub-ring of $L$ that includes $K\cup\{a_0,\dots,a_{n-1}\}$;
\item
$K(\vec a)$ is the smallest subfield of $L$ that includes $K\cup\{a_0,\dots,a_{n-1}\}$.
\end{compactitem}
Note well that the function $f\mapsto f(\vec a)$ is not generally defined on all of $K(\vec X)$, though it may be defined on a sub-ring of this field that strictly includes $K[\vec X]$.  We shall consider this situation presently.  Meanwhile, the kernel of the homomorphism $f\mapsto f(\vec a)$ on $K[\vec X]$ is a prime ideal $\mathfrak p$, and then
\begin{equation*}
K[\vec a]\cong K[\vec X]/\mathfrak p.
\end{equation*}
If that ideal is nontrivial, then $\vec a$ is said to be \textbf{algebraically dependent} over $K$, or simply \textbf{algebraic} over $K$ in case $n=1$.

\begin{theorem}
If $a$ is algebraic over $K$, then
\begin{equation*}
K[a]=K(a).
\end{equation*}
Thus prime ideals of $K[X]$ are maximal.
\end{theorem}

\begin{proof}
If $b_0+b_1\cdot a+\dots+b_n\cdot a^n=0$, then
\begin{equation*}
\frac1a=-\Bigl(\frac{b_1}{b_0}+\frac{b_2}{b_0}\cdot a+\dots+\frac{b_n}{b_0}\cdot a^{n-1}\Bigr).\qedhere
\end{equation*}
\end{proof}

Recall that Boolean rings also have the property that prime ideals are maximal (pages \pageref{prime-maximal} and \pageref{prime-maximal-2}).
This is not generally true for $K[\vec X]$.  For example $K[X,Y]/(X-Y)\cong K[X]$, an integral domain that is not a field; so $(X-Y)$ is a non-maximal prime ideal of $K[X,Y]$.

In general, if $S$ is a multiplicative subset of $R$, then, using the notation above, we can denote the localization $S\inv R$ also by
\begin{equation*}
R[S\inv].
\end{equation*}
In case $S$ is the complement of a prime ideal $\mathfrak p$ of $R$, then this localization is denoted also by
\begin{equation*}
R_{\mathfrak p}.
\end{equation*}
Confusingly, this may called the \textbf{localization} of $R$ at $\mathfrak p$, although in the earlier terminology it is the localization of $R$ at the \emph{complement} of $\mathfrak p$.  If $R$ is an integral domain, then its fraction-field is the localization $R_{\{0\}}$.  

Suppose again $L/K$ is a field-extension and $\vec a\in L^n$.  If $\mathfrak p$ is the prime ideal of $K[\vec X]$ that is the kernel of $f\mapsto f(\vec a)$, then $K[\vec X]_{\mathfrak p}$ is the largest sub-ring of $K(\vec X)$ on which the homomorphism $f\mapsto f(\vec a)$ is defined.

In general, as we noted, if $\mathfrak p$ is a prime ideal of $R$, then $R\setminus\mathfrak p$ is multiplicative.  The converse is true, and more, in the following sense:

\begin{theorem}
Let $I$ be a proper ideal of $R$.
\begin{compactenum}
\item
$R\setminus I$ is multiplicative if and only if $I$ is prime.
\item
$R\setminus I=\units R$ if and only if $I$ is the unique maximal ideal of $R$.\hfill\qedsymbol
\end{compactenum}
\end{theorem}

A ring with a unique maximal ideal is called a \textbf{local ring.}

\begin{theorem}
The localization of a ring at (the complement of) a prime ideal is a local ring, whose maximal ideal is generated by the image of that prime ideal.\hfill\qedsymbol
\end{theorem}

We can now refer to $R_{\mathfrak p}$ (where $\mathfrak p$ is prime) as the local ring of $R$ at $\mathfrak p$.  A reason for the terminology can be seen in algebraic geometry, to which we now turn.

\section{Algebraic geometry}\label{sect:ag}

Again suppose $K$ and $L$ are fields such that $K\included L$.  For example, $K$ might be $\Q$, and then $L$ might be $\C$.  Let $\vec X$ be $(X^0,\dots,X^{n-1})$ for some $n$ in $\upomega$.  Given a point $\vec x$ of $L^n$, we have looked at the homomorphism $f\mapsto f(\vec x)$ from $K[\vec X]$ to $L$.  `Dually', an element $f$ of $K[\vec X]$ determines a function $\vec x\mapsto f(\vec x)$ from $L^n$ to $L$.  Often we are interested in the solution-set of the equation
\begin{equation*}
f(\vec x)=0.
\end{equation*}
Such equations are studied in school, at least when $L=\R$ and $n=1$.  We define
\begin{equation*}
\V f=\{\vec x\in L^n\colon f(\vec x)=0\};
\end{equation*}
this is the \textbf{zero-locus} of $f$ in $L$.  See
Figure~\ref{fig:y-x^2}.
\begin{figure}
\centering
  \begin{pspicture}(-1.4,-0.5)(1.4,2)
\psline{->}(-1.4,0)(1.4,0)
\psline{->}(0,-0.5)(0,2)
    \psplot{-1.4}{1.4}{x x mul}
  \end{pspicture}
  \caption{The zero-locus of $y-x^2$ in $\R$}\label{fig:y-x^2}
\end{figure}
We may also want to
look at more than one equation simultaneously, as for example in
defining a straight line in $\R^3$.  Accordingly, if $A\included
K[\vec X]$, we define 
\begin{equation*}
\V A=\bigcap_{f\in A}\V f,
\end{equation*}
that is,
\begin{equation}\label{eqn:zl}
\V A=\bigcap_{f\in A}\{\vec x\in L^n\colon f(\vec x)=0\};
\end{equation}
this is the \textbf{zero-locus} of $A$ in $L$.  See Figure
\ref{fig:2eq}.
\begin{figure}
\centering
  \begin{pspicture}(-1.4,-0.5)(1.4,2)
\psline{->}(-1.4,0)(1.4,0)
\psline{->}(0,-0.5)(0,2)
\psdots(0,0)(1,1)
\psset{linestyle=dotted}
    \psplot{-1.4}{1.4}{x x mul}
\psline(-0.5,-0.5)(1.4,1.4)
  \end{pspicture}
  \caption{The zero-locus of $\{y-x^2,y-x\}$ in $\R$}\label{fig:2eq}
\end{figure}
  (The definition should be compared with \eqref{eqn:mod} and \eqref{eqn:th} on page \pageref{eqn:mod}.)  The function $A\mapsto\V A$ is the \textbf{zero-locus map.}  A course in `analytic geometry' is a study of zero-loci in $\R$, in case $n$ is $2$ or $3$, where $K[\vec X]$ can be written as $K[X,Y]$ or $K[X,Y,Z]$.

If $I$ is an ideal of an arbitrary ring $R$, we define
\begin{equation*}
\rad I=\bigcup_{n\in\upomega}\{x\in R\colon x^n\in I\};
\end{equation*}
this is the \textbf{radical} of $I$.  (Note that the radical is indeed an ideal: if $f^n\in I$ and $g^m\in I$, then $(f+g)^{n+m-1}\in I$.)  An ideal is a \textbf{radical ideal} if it is equal to its own radical.

\begin{theorem}
For all subsets $A$ of $K[\vec X]$,
\begin{equation*}
\V A=\V{(A)}=\V{\rad(A)}.
\end{equation*}
Thus all zero-loci are zero-loci of radical ideals.
\end{theorem}

The zero-loci of the various subsets (or just ideals, or just radical ideals) of $K[\vec X]$ are also called \textbf{algebraic sets.}  As the notation is supposed to recall, the definition of $\V A$ depends on $L$.  We intend to overcome this dependence.  Meanwhile, we have the following.

\begin{theorem}\label{thm:Z}
The algebraic sets in $L$ are the closed sets of a topology on $L^n$.
\end{theorem}

\begin{proof}
What this means, and what we shall show, is that
\begin{inparaenum}[(1)]
\item
 the intersection of an arbitrary collection of algebraic sets is an algebraic set, and 
 \item
 the union of a finite collection of algebraic sets is an algebraic set.  
 \end{inparaenum}
 (In particular, since $\emptyset=\bigcup\emptyset$, this will be shown to be an algebraic set; also, $\bigcap\emptyset$ is to be understood as $L^n$, so this too will be an algebraic set.  See also page \pageref{topology}.)  

The first point is obvious from the definition.  Indeed, if $\mathcal A$ is a collection of ideals of $K[\vec X]$, then
\begin{equation*}
\bigcap_{\mathfrak a\in\mathcal A}\V{\mathfrak a}=\V{\sum\mathcal A},
\end{equation*}
where $\sum\mathcal A$ is the ideal generated by $\bigcup\mathcal A$.  (So the ideal is $(\bigcup\mathcal A)$; but it consists of finite sums of elements of $\bigcup\mathcal A$, and the notation $\sum\mathcal A$ is more suggestive of this.)  In particular, as a special case we have
\begin{equation*}
L^n=\V{\{0\}}.
\end{equation*}

For the second point, let $\mathfrak a$ and $\mathfrak b$ be ideals of $K[\vec X]$.  Then
\begin{equation*}
\mathfrak a\included\mathfrak b\implies\V{\mathfrak a}\includes\V{\mathfrak b}.
\end{equation*}
Consequently
\begin{equation*}
\V{\mathfrak a\cap\mathfrak b}\includes\V{\mathfrak a}\cup\V{\mathfrak b}.
\end{equation*}
Conversely, suppose $\vec x\in\V{\mathfrak a\cap\mathfrak b}\setminus\V{\mathfrak a}$.  Then for some $f$ in $\mathfrak a$ we have $f(\vec x)\neq0$.  But then for all $g$ in $\mathfrak b$ we have $f\cdot g\in\mathfrak a\cap\mathfrak b$, so $f(\vec x)\cdot g(\vec x)=0$, and hence $g(\vec x)=0$ (since $L$ is an integral domain).  Thus $\vec x\in\V{\mathfrak b}$.
Therefore
\begin{equation}\label{eqn:Vab}
\V{\mathfrak a\cap\mathfrak b}=\V{\mathfrak a}\cup\V{\mathfrak b}.
\end{equation}
Finally
\begin{equation*}
\V{(1)}=\emptyset.
\end{equation*}
Thus finite unions of algebraic sets are algebraic.
\end{proof}

The zero-locus of an \emph{arbitrary} intersection of radical ideals need not be the union of the zero-loci of the ideals.  For example, if $K=\Q$ and
\begin{equation*}
\mathfrak a_k=\Bigl(\prod_{i=1}^k(X-i)\Bigr)=\bigl((X-1)\dotsm(X-k)\bigr),
\end{equation*}
then $\V{\mathfrak a_k}=\{1,\dots,k\}$, but $\bigcap_{k\in\N}\mathfrak a_k=\{0\}$, so
\begin{equation*}
\bigcup_{k\in\N}\V{\mathfrak a_k}=\N\pincluded L=\V{\{0\}}=\V{\bigcap_{k\in\N}\mathfrak a_k}.
\end{equation*}

The topology on $L^n$ given by the theorem is called the \textbf{Zariski topology over} $K$.  Then algebraic sets may be called \textbf{Zariski-closed over} $K$, or perhaps \textbf{$K$-closed.}
All intersections of such sets are finite intersections, because of the following:

\begin{theorem}[Hilbert Basis Theorem]\label{thm:H}
For every $n$ in $\upomega$, every ideal of the polynomial ring $K[X^0,\dots,X^{n-1}]$ is finitely generated.
\end{theorem}

\begin{proof}
The claim implies, and is therefore equivalent to, an apparently stronger claim, namely that every ideal $(A)$ of $K[X^0,\dots,X^{n-1}]$ is $(A_0)$ for some finite subset $A_0$ of $A$.  For, if $(A)=(f_0,\dots,f_{m-1})$, then each $f_k$ is in $(A^k)$ for some finite subset $A^k$ of $A$; and then we can let $A_0=\bigcup_{k<m}A^k$.

The claim as also equivalent to the claim that every sequence $(\mathfrak a_k\colon k\in\upomega)$ of ideals such that
\begin{equation*}
\mathfrak a_0\included\mathfrak a_1\included\mathfrak a_2\included\dotsb
\end{equation*}
---that is, every increasing chain of ideals (indexed by $\upomega$)---is eventually constant.  For, the union of such a chain is an ideal $\mathfrak b$, and if this ideal is finitely generated, then it has a generating set whose elements all lie in some $\mathfrak a_{\ell}$, and then this ideal is $\mathfrak b$.  Conversely (or inversely), if $\mathfrak a$ were not finitely generated, then for all subsets $\{f_k\colon k<\ell\}$ of $\mathfrak a$ we could find $f_{\ell}$ in $\mathfrak a\setminus(f_k\colon k<\ell)$; thus we could form a strictly increasing chain $((f_k\colon k<\ell)\colon\ell\in\upomega)$.

There is now also a fourth form of our claim: every \emph{countably} generated ideal is finitely generated.
We turn to proving the claim, in any convenient form.

The claim is trivially true when $n=0$, since a field has only two ideals: the trivial ideal and the improper ideal $(1)$.

The claim is still easy when $n=1$, because $K[X]$ is a Euclidean domain.  In particular, if $f$ and $g$ are in $K[X]$, we have an algorithm (the Euclidean algorithm) for finding their greatest common divisor---say $h$; and then $(f,g)=(h)$.  Hence if $\mathfrak a=(f_k\colon k\in\upomega)$, for each $k$ in $\upomega$ we can find $g_k$ so that
\begin{equation*}
(f_0,\dots,f_k)=(g_k).
\end{equation*}
In particular, $g_{k+1}$ divides $g_k$.  Then $\min\{\deg(g_k)\colon k\in\upomega\}=\deg(g_{\ell})$ for some $\ell$, and consequently $\mathfrak a=(g_{\ell})$.

When $n\geq2$, we have not got the Euclidean algorithm; but we can come close enough if we use induction.  Suppose then that the claim is true when $n=m$.  Let $\mathfrak a$ be an ideal of $K[X^0,\dots,X^m]$.  We form a sequence $(f_0,f_1,\dots)$ of elements of $\mathfrak a$ by recursion:  Given $(f_k\colon k<\ell)$, we let $f_{\ell}$, if it exists, be an element of $\mathfrak a\setminus(f_k\colon k<\ell)$ of minimal degree as a polynomial in $X^m$ over $K[X^0,\dots,X^{m-1}]$.  Then these degrees form an increasing sequence:
\begin{equation*}
\deg_{X^m}(f_0)\leq\deg_{X^m}(f_1)\leq\deg_{X^m}(f_2)\leq\dots
\end{equation*}
Let $g_k$ be the leading coefficient of $f_k$ (as a polynomial in $X^m$ over $K[X^0,\dots,X^{m-1}]$; so $g_k\in K[X^0,\dots,X^{m-1}]$).  By inductive hypothesis, for some $\ell$,
\begin{equation*}
(g_k\colon k\in\upomega)=(g_k\colon k<\ell).
\end{equation*}
Then in particular
\begin{equation*}
g_{\ell}\in(g_k\colon k<\ell).
\end{equation*}
Therefore $(f_k\colon k<\ell)$ has an element $h$ whose leading coefficient (as a polynomial in $X^m$ over $K[X^0,\dots,X^{m-1}]$) is $g_{\ell}$; and the degree of this element can have any value that is at least the degree of $f_{\ell-1}$.  In particular we may assume $h$ has the degree of $f_{\ell}$.  But then $f_{\ell}-h$ has lower degree and belongs to $\mathfrak a\setminus(f_k\colon k<\ell)$; that is, $f_{\ell}$ did not have minimal degree.  Thus there \emph{is} no $f_{\ell}$; that is, $\mathfrak a=(f_k\colon k<\ell)$.
\end{proof}

A \emph{singly} generated ideal is called \textbf{principal.}
Then part of our proof of the theorem gives the following:

\begin{porism}
Every ideal of $K[X]$ is principal.\hfill\qedsymbol
\end{porism}

Hence, although in the example above $\N$ is the union of zero-loci, it cannot itself be a zero-locus; for, every zero-locus of polynomials in one variable is the zero-locus of a single polynomial, so it is either the whole field $L$ or a finite subset of this.

The theorem itself has the following:

\begin{corollary}
Every decreasing chain of closed subsets of $L^n$ is eventually constant.\hfill\qedsymbol
\end{corollary}

It is not obvious that the corollary implies the theorem, since it is
not obvious that $\mathfrak a\pincluded\mathfrak b$ implies
$\V{\mathfrak a}\pincludes\V{\mathfrak b}$, even if $\mathfrak a$ and $\mathfrak b$ are radical ideals.  In fact, this can be
\emph{false.}  For example, when $L=\R$, then $(X^2+1)$ is a radical ideal
whose zero-locus is the same as the zero-locus of $(1)$, namely
empty. 

\section{A Galois correspondence}\label{sect:Gal}

For a `dual' to the definition of zero-loci,
if $A\included L^n$, we define
\begin{equation*}
\I A=\bigcap_{\vec x\in A}\{f\in K[\vec X]\colon f(\vec x)=0\};
\end{equation*}
this is a radical ideal of $K[\vec X]$, and we may call it the
\textbf{ideal of $A$ over $K$}.  The function $A\mapsto\I A$ is the \textbf{ideal map.}  The definition does not involve the field $L$
as such, but it does involve $K$, as the notation indicates.

Every subset $A$ of $L^n$ has a \textbf{Zariski closure} over $K$, namely the
smallest $K$-closed subset of $L^n$ that includes $A$.  We can denote this
closure by 
\begin{equation*}
\zk A.
\end{equation*}
Then we have easily:

\begin{theorem}
For all subsets $A$ of $L^n$,
\begin{align*}
\zk A&=\V{\I A},&
\I A&=\I{\zk A}.
\end{align*}
\end{theorem}

In the proof of Theorem \ref{thm:Z} we used that the zero-locus map is inclusion-reversing.  This is by the form of the definition.  Since the definition of the ideal map has the same form, this function too is inclusion-reversing.  

The last theorem theorem is entirely formal in this way.  Indeed, the
form of the definitions of the zero-locus and ideal maps is just the
form used in establishing the original \textbf{Galois correspondence}
in field theory.  In that context, $L$ is a normal and separable
finite extension of $K$.  We let $G$ be the group of automorphisms of
$L$ over $K$, that is, $G=\Aut{L/K}$.  For subgroups $H$ of $G$, we
define\label{upper-sigma} 
\begin{equation*}
\Fix H=\bigcap_{\sigma\in H}\{x\in L\colon x^{\sigma}=x\};
\end{equation*}
for intermediate extensions $F$ of $L/K$, we have
\begin{equation*}
\Aut{L/F}=\bigcap_{x\in F}\{\sigma\in G\colon x^{\sigma}=x\}.
\end{equation*}
If we abbreviate $\Fix H$ as $H'$, and $\Aut{L/F}$ as $F'$, then we always have
\begin{align*}
X\included Y&\implies X'\includes Y',&
X&\included X'',
\end{align*}
so that (as a special case of the latter) $X'\included X'''$, but also $X'\includes X'''$.  Thus
\begin{equation*}
X'''=X'.
\end{equation*}
Therefore we have a one-to-one correspondence $X\mapsto X'$ between
the fields $\Fix H$ and the groups $\Aut{L/F}$; and this is entirely
by the general form of the definitions.  What makes the correspondence
useful is the special features of the situation: that $\abs G=[L:K]$,
simply because $L/K$ is normal, separable, and finite; and then
$\abs{\Aut{L/F}}=[L:F]$ for all intermediate extensions $F$ of $L/K$; and
therefore \emph{every} intermediate field of $L/K$ is $\Fix H$ for
some $H$, and every subgroup of $G$ is $\Aut{L/F}$ for some intermediate
field $F$ of $L/K$. 

We return to the algebraic-geometric situation.  For the formal
reasons just discussed, we have a one-to-one \textbf{Galois
  correspondence} between the $K$-closed subsets of $L^n$ and certain
radical ideals of $K[\vec X]$, namely those of the form $\I F$ for
some $K$-closed set $F$.  See Figure \ref{fig:gal-ag}.
\begin{figure}
\mbox{}\hfill
  \begin{pspicture}[shift=-2.5](-1.4,-0.5)(1.4,2)
\psline{->}(-1.4,0)(1.4,0)
\psline{->}(0,-0.5)(0,2)
\psdots(0,0)(1,1)
%\psset{linestyle=dotted}
    \psplot{-1.4}{1.4}{x x mul}
\psline(-0.5,-0.5)(1.4,1.4)
  \end{pspicture}
\hfill
$\xymatrix@C=0pt{
(x,y)&&(x-1,y-1)\\
&(y-x,y-x^2)\ar@{-}[ul]\ar@{-}[ur]&\\
(y-x)\ar@{-}[ur]&&(y-x^2)\ar@{-}[ul]
}$
\hfill\mbox{}
  \caption{Algebraic-geometric Galois correspondence}\label{fig:gal-ag}
\end{figure}
We may refer to those ideals as being
themselves \textbf{$L$-closed.}  Is this Galois correspondence of any
use? 

The $L$-closed ideals of $K[\vec X]$ are just those of the form $\I{\V{\mathfrak a}}$ for some radical ideal $\mathfrak a$ of $K[\vec X]$; and then
\begin{equation}\label{eqn:inclusion}
\mathfrak a\included\I{\V{\mathfrak a}}.
\end{equation}
This is an equation if and only if $\mathfrak a$ is $L$-closed.
We noted in effect that if $L=\R$ then the radical ideal $(X^2+1)$ is not $L$-closed:
\begin{equation*}
(X^2+1)\pincluded(1)=\I{\V[\R]{(X^2+1)}}.
\end{equation*}
However, as $L$ grows larger, so does $\V{\mathfrak a}$; but then
$\I{\V{\mathfrak a}}$ becomes smaller.  In fact 
\begin{equation*}
(X^2+1)=\I{\V[\C]{(X^2+1)}}.
\end{equation*}
We now are faced with the following:
\begin{question}
For every radical ideal $\mathfrak a$ of $K[\vec X]$, is there
an extension $L$ of $K$ large enough that 
\begin{equation*}
\mathfrak a=\I{\V{\mathfrak a}}?
\end{equation*}
\end{question}

\begin{question}
Is there an extension $L$ of $K$ large enough that for all ideals
$\mathfrak a$ of $K[\vec X]$ and all extensions $M$ of $K$,
\begin{equation*}
\I{\V{\mathfrak a}}\included\I{\V[M]{\mathfrak a}}?
\end{equation*}
\end{question}

Note well that $\mathfrak a$ and $L$ are quantified in different
orders in the two questions, as $\Forall{\mathfrak a}\Exists L$ and $\Exists L\Forall{\mathfrak a}$ respectively.  This means a positive answer to Question
1 does not immediately give a positive answer to Question 2.  We would
first have to show that the different fields $L$ corresponding to the
different ideals $\mathfrak a$ are all included in one large field.
This is true however, since the class of fields has the \textbf{joint
  embedding property:}  If $f_0$ embeds $K$ in $L_0$, and $f_1$ embeds
$K$ in $L_1$, then there is a field $M$, and there are embeddings
$g_i$ of the $L_i$ (respectively) in $M$, such that $g_0\circ
f_0=g_1\circ f_1$.  See Figure \ref{fig:jep}.
\begin{figure}[ht]
\begin{equation*}
\xymatrix{
              &M                      &\\
L_0\ar@{-}[ur]^{g_0}&                       &L_1\ar@{-}[ul]_{g_1}\\
              &K\ar@{-}[ul]^{f_0}\ar@{-}[ur]_{f_1}&
              }
\end{equation*}  
  \caption{Joint embedding property of fields}\label{fig:jep}
\end{figure}

By contrast, even if Question 2 has a positive answer, it is not at
all clear that the answer to Question 1 must be positive.  We settle
Question 1 first in a special case. 

\begin{lemma}
For all \emph{maximal} ideals $\mathfrak m$ of $K[\vec X]$, for all
extensions $L$ of $K$ in which $K[\vec X]/\mathfrak m$ embeds over $K$,
\begin{equation*}
\mathfrak m=\I{\V{\mathfrak m}}.
\end{equation*}
\end{lemma}

\begin{proof}
As formulated here, the lemma almost proves itself.  We just have to show $\I{\V{\mathfrak m}}$ is a proper ideal.  But the image of $\vec X$ in $K[\vec X]/\mathfrak m$ is in
the zero-locus of $\mathfrak m$.  In particular, if $L$ includes this field,
then $\V{\mathfrak m}$ is not empty, so $\I{\V{\mathfrak m}}$ cannot be all of $K[\vec X]$.
\end{proof}

This gives us another special case:

\begin{theorem}
If $\alg{K[\vec X]}\included L$, for all ideals $\mathfrak a$ of $K[\vec X]$ such that $\I{\V{\mathfrak a}}$ is the improper ideal,
\begin{equation*}
\mathfrak a=\I{\V{\mathfrak a}}.
\end{equation*}
\end{theorem}

\begin{proof}
The claim is
\begin{equation*}
\I{\V{\mathfrak a}}=(1)\implies\mathfrak a=(1).
\end{equation*}
We prove the contrapositive.  If $\mathfrak a$ is a proper ideal of $K[\vec X]$, then it is included in some maximal ideal $\mathfrak m$.  The field
$K[\vec X]/\mathfrak m$ can be understood as an algebraic extension of $K(X^i\colon
i\in I)$ for some subset $I$ of $n$, so it embeds in $\alg{K(\vec X)}$.
  By the lemma then, since
$\I{\V{\mathfrak m}}$ is a proper ideal, so is $\I{\V{\mathfrak a}}$.
\end{proof}

Note that if $\I{\V{\mathfrak a}}\neq(1)$, then $\V{\mathfrak a}\neq\emptyset$.  Thus every proper ideal has non-empty zero-locus in a large-enough field.  \emph{Nullstellensatz} means zero-locus theorem:

\begin{theorem}[Nullstellensatz]\label{thm:N}
If $\alg{K[\vec X,Y]}\included L$, for all radical ideals $\mathfrak a$ of $K[\vec X]$,
\begin{equation*}
\mathfrak a=\I{\V{\mathfrak a}}.
\end{equation*}
\end{theorem}

\begin{proof}
Say $f\in\I{\V{\mathfrak a}}$.  If $\vec x\in\V{\mathfrak a}$,
then $f(\vec x)=0$.  This shows $\V{\mathfrak
  a\cup\{f-1\}}=\emptyset$, so 
\begin{equation*}
\I{\V{\mathfrak a\cup\{f-1\}}}=(1).
\end{equation*}
By the last theorem, $\mathfrak a\cup\{f-1\}$ too must generate the improper ideal of
$K[\vec X]$.  We want to be able to conclude $f\in\mathfrak a$.  To do so, we modify the argument so far.  We have $f\cdot
Y\in\I{\V{\mathfrak a}}$, if we consider $\mathfrak a$ now as a subset
of $K[\vec X,Y]$.  As before, $\mathfrak a\cup\{f\cdot Y-1\}$
must generate
the improper ideal of $K[\vec X,Y]$.  Now, by itself, $\mathfrak a$
generates the ideal of $K[\vec X,Y]$ whose elements are polynomials in
$Y$ with coefficients from $\mathfrak a$.  Hence there is some such
polynomial $g$, and there is some $h$ in $K[\vec X,Y]$, such that 
\begin{equation*}
g+h\cdot(f\cdot Y-1)=1.
\end{equation*}
Substituting $1/f$ for $Y$, we get $g(1/f)=1$; that is,
\begin{gather*}
g_0+g_1\cdot\frac1f+\dots g_m\cdot\frac1{f^m}=1
\end{gather*}
for some $g_i$ in $\mathfrak a$, and hence
\begin{gather*}
g_0\cdot f^m+g_1\cdot f^{m-1}+\dots+g_m=f^m.
\end{gather*}
This means $f^m\in\mathfrak a$.  Assuming $\mathfrak a$ is radical, we
have $f\in\mathfrak a$.  Thus $\I{\V{\mathfrak a}}\included\mathfrak
a$ and therefore $\I{\V{\mathfrak a}}=\mathfrak a$. 
\end{proof}

We have now settled both Questions 1 and 2.  This suggests that
understanding algebraic sets can somehow be reduced to understanding
radical ideals of $K[\vec X]$.  Indeed, there is \emph{some} extension $L$ of $K$ large enough that we have a Galois correspondence between the $K$-closed subsets of $L^n$ and the radical ideals of $K[\vec X]$.  It is not particularly important for what follows that this field $L$ can be chosen as $\alg K$.  Nonetheless, it is true:
 
\begin{theorem}[Hilbert's Nullstellensatz, weak form]\label{thm:HN}
Every proper ideal of $K[\vec X]$ has a non-empty zero-locus in every extension of $\alg K$.
\end{theorem}

\begin{proof}
In the lemma, by the Hilbert Basis Theorem, $\mathfrak m$ has the form $(f_0,\dots,f_\ell)$ for some $f_i$ in $K[\vec X]$.  Thus the formula
\begin{equation*}
f_0=0\land\dots\land f_{\ell}=0
\end{equation*}
has a solution in $K[\vec X]/\mathfrak m$ and \emph{a fortiori} in $\alg{(K[\vec X]/\mathfrak m)}$.  The latter field is an \emph{elementary} extension of $\alg K$, by the model-completeness of the theory of algebraically closed fields (Theorem \ref{thm:ACF} on page \pageref{thm:ACF}).  Therefore the formula has a solution here too.  Thus as long as $\alg K\included L$, we have $\V{\mathfrak m}\neq0$.
\end{proof}

Now the proof of Theorem \ref{thm:N} gives:

\begin{corollary}[Hilbert's Nullstellensatz, strong form]
For all radical ideals $\mathfrak a$ of $K[\vec X]$,
\begin{equation*}
\I{\V[\alg K]{\mathfrak a}}=\mathfrak a.
\end{equation*}
\end{corollary}



\chapter{Finite fields}

\section{Ultraproducts of finite structures}

Suppose a theory $T$ has arbitrarily large finite models.  Then there
is a sequence $(\str A_m\colon m\in\upomega)$ of finite models of $T$ such
that $\abs{A_m}>m$ in each case.
Consequently, the sentence
\begin{equation*}
\Exists{(x_0,\dots,x_m)}\bigwedge_{i<j<m}x_i\neq x_j
\end{equation*}
is true in each $\str A_n$ such that $m\leq n$.  By \L o\'s's Theorem
then, the sentence is true in every non-principal ultraproduct of the
structures $\str A_i$.  In particular, this ultraproduct is infinite.
Moreover, every sentence that is true in each $\str A_i$ is true in
the ultraproduct; that is, the ultraproduct is a model of the theory
of the structures $\str A_i$.  Thus the ultraproduct is an infinite
model of the theory of finite models of $T$.  Such a structure might
be called a \textbf{pseudo-finite} model of $T$.  We shall consider
the case where $T$ is the theory of fields.  

\section{Finite fields}

Let us review the basic theorems about finite fields.  Suppose $K$ is a field.  There is a homomorphism $1\mapsto1$ (or $k\mapsto k\cdot1$) from $\Z$ to
$K$.  The kernel of this homomorphism is $n\Z$ for some
\emph{positive} $n$, called the \textbf{characteristic} of $K$, $\Char K$.
Since $\Z/n\Z$ must be an integral domain (by Theorem \ref{thm:id},
p.\ \pageref{thm:id}), $n$ is either $0$ or prime. 
If $\Char K=0$, we may consider $\Q$ as a subfield of $K$; if $\Char
K$ is a prime $p$, we consider $\Z/p\Z$, denoted by $\F_p$, as a
subfield of $K$.  Respectively, $\Q$ or $\F_p$ is the \textbf{prime
  field} of $K$. 

Let $K$ be a finite field of characteristic $p$.  Then $K$ is a
vector-space over $\F_p$ of some finite dimension $m$, so $K$ has
order $p^m$.  The group $\units K$ of units of $K$ has order $p^m-1$,
so its every element is a root of $x^{p^m-1}-1$.  Then \emph{every}
element of $K$ is a root of the polynomial
\begin{equation*}
x^{p^m}-x.  
\end{equation*}
Since the formal derivative of this is $-1$, it has no repeated roots.
Thus its roots (in an algebraic closure $\alg{\F_p}$ of $\F_p$ that includes $K$) are
precisely the elements of $K$: we have 
\begin{equation*}
K=\{x\in\alg{\F_p}\colon x^{p^m}=x\}.
\end{equation*}
Conversely, for all $m$ in $\N$, since the map $x\mapsto x^{p^m}$ is an automorphism of $\alg{\F_p}$, the set $\{x\in\alg{\F_p}\colon x^{p^m}=x\}$ (namely the fixed field of the automorphism) is a subfield having order $p^m$.  This then is the \emph{unique} subfield of $\alg{\F_p}$ of this order, and we can denote it by
\begin{equation*}
\F_{p^m}.
\end{equation*}
The group $\units{\F_{p^m}}$ of units of this field is cyclic.  For again, it is a finite abelian group of order $p^m-1$ and is therefore a direct product
\begin{equation*}
\prod_{\ell\divides p^m-1}G_{\ell},
\end{equation*}
where each $G_{\ell}$ is an $\ell$-group (a group whose elements have orders that are powers of $\ell$; here and elsewhere in this chapter, $\ell$ is, like $p$, a prime number).  Since $G_{\ell}$ is finite, for some positive integer $n$, every element of $G_{\ell}$ is a solution of
\begin{equation*}
x^{\ell^n}=1.
\end{equation*}
But in a field, this equation has no more than $\ell^n$ solutions.  Therefore, if $n$ is minimal, $G_{\ell}$ must be cyclic of order $\ell^n$.  Then the product $\units{\F_{p^m}}$ is itself cyclic, of order $p^m-1$.

The collection of finite subfields of $\alg{\F_p}$, ordered by inclusion, is isomorphic, under the map $\F_{p^m}\mapsto m$, to $\N$ as ordered by dividing.  That is,
\begin{equation*}
\F_{p^m}\included\F_{p^n}\iff m\divides n.
\end{equation*}
See Figure~\ref{fig:ord}.
\begin{figure}[ht]
\begin{equation*}
\xymatrix{\F_{p^8}&&\F_{p^{12}}&&\F_{p^{18}}&&\F_{p^{27}}\\
&\F_{p^4}\ar@{-}[ul]\ar@{-}[ur]&&\F_{p^6}\ar@{-}[ul]\ar@{-}[ur]&&\F_{p^9}\ar@{-}[ul]\ar@{-}[ur]&\\
&&\F_{p^2}\ar@{-}[ul]\ar@{-}[ur]&&\F_{p^3}\ar@{-}[ul]\ar@{-}[ur]&&\\
&&&\F_p\ar@{-}[ul]\ar@{-}[ur]&&&}
\end{equation*}
\caption{The lattice of finite fields of characteristic $p$}\label{fig:ord}
\end{figure}
Indeed, if $\F_{p^m}\included\F_{p^n}$, then $\F_{p^n}$ is a vector-space over $\F_{p^m}$, so its order is $(p^m)^k$ for some $k$, and then $n=mk$, so $m\divides n$.  Conversely, if $m\divides n$, then
\begin{equation*}
p^m-1\divides p^n-1,
\end{equation*}
and therefore
\begin{equation*}
x^{p^m-1}-1\divides x^{p^n-1}-1,
\end{equation*}
so $\F_{p^m}\included\F_{p^n}$.  

Finally,
\begin{equation}\label{eqn:algFp}
\alg{\F_p}=\bigcup_{n\in\N}\F_{p^n}
\end{equation}
(since every extension $\F_{p^n}/\F_p$ is certainly algebraic, while every finite algebraic extension of $\F_p$ is a finite field).

\section{Galois groups}

We have shown that for each prime $p$, for each $m$ in $\N$, there is a subfield $\F_{p^m}$ of $\alg{\F_p}$, and this subfield is generated by (in fact it consists of) the roots of the polynomial $x^{p^m}-x$, which is separable.  Therefore the finite field-extension $\F_{p^m}/\F_p$ is normal and separable, that is, Galois.  The order of its group of automorphisms is $[\F_{p^m}\colon\F_p]$, that is, $m$.  But the \textbf{Frobenius automorphism} of $\alg{\F_p}$, namely $x\mapsto x^p$ or
\begin{equation*}
\Frob,
\end{equation*}
restricts to an automorphism of $\F_{p^m}$ of order $m$, since we have shown in effect
\begin{equation*}
\Fix{\Frob^k}=\F_{p^k}.
\end{equation*}
Thus
\begin{equation*}
  \Aut{\F_{p^m}/\F_p}=\gpgen{\Frob\restriction\F_{p^m}}\cong\Z/m\Z.
\end{equation*}

For any field $K$, let us write
\begin{equation*}
\Gal K=\Aut{K\sep/K},
\end{equation*}
the \emph{absolute Galois group} of $K$.  We want to determine $\Gal{\F_p}$.  Suppose $\sigma\in\Gal{\F_p}$.  For every $n$ in $\N$, we have
\begin{equation*}
\sigma\restriction\F_{p^n}\in\Aut{\F_{p^n}/\F_p},
\end{equation*}
and hence for some $\sigma(n)$ in $\Z$
\begin{equation*}
  \sigma\restriction\F_{p^n}=(\Frob\restriction\F_{p^n})^{\sigma(n)}.
\end{equation*}
All that matters here is the congruence-class of $\sigma(n)$ \emph{modulo}
$n$.  Thus we have an injective map
\begin{equation*}
\sigma\mapsto(\sigma(n)\colon n\in\N)
\end{equation*}
from
$\Gal{\F_p}$ to $\prod_{n\in\N}\Z/n\Z$.  The map is not surjective,
but if $m\divides n$, then since $\F_{p^m}\included\F_{p^n}$ we must have
\begin{equation*}
  \sigma(n)\equiv \sigma(m)\pmod m.
\end{equation*}
However, suppose an element $(\sigma(n)\colon n\in\N)$ of
$\prod_{n\in\N}\Z/n\Z$ meets this condition.  For any $x$ in $\alg{\F_p}$ we can define an element $\sigma$ of $\Gal{\F_p}$ by
\begin{equation*}
x^{\sigma}=x^{p^{\sigma(m)}},
\end{equation*}
where $x\in\F_{p^m}$.  (Here $x^{\sigma}$ is of course the image of $x$ under $\sigma$.) This definition of $x^{\sigma}$ is independent of the choice of $m$, since if also $x\in\F_{p^n}$, then
\begin{equation*}
x\in\F_{p^{\gcd(m,n)}},
\end{equation*}
so
\begin{equation*}
\sigma(m)\equiv\sigma(\gcd(m,n))\equiv\sigma(n)\pmod{\gcd(m,n)}
\end{equation*}
and therefore
\begin{equation*}
x^{p^{\sigma(m)}}=x^{p^{\sigma(\gcd(m,n))}}=x^{p^{\sigma(n)}}.
\end{equation*}
Thus
\begin{equation*}
\Gal{\F_p}\cong\{(\sigma(n)\colon n\in\N)\in\prod_{i\in\N}\Z/n\Z\colon\bigwedge_{m\divides n}\pi^n_m(\sigma(n))=\sigma(m)\}
\end{equation*}
where $\pi^n_m$ is the quotient-map $x+n\Z\mapsto x+m\Z$ from $\Z/n\Z$ to $\Z/m\Z$.

In particular, $\Gal{\F_p}$ has a certain `universal property'\label{up} with respect to the system of groups $\Z/n\Z$ and homomorphisms $\pi^n_m$:
\begin{compactenum}
\item
$\Gal{\F_p}$ is a group $G$ from which there is a homomorphism $h^G_n$ to $\Z/n\Z$ for every $n$ in $\N$ such that, if $m\divides n$, then
\begin{equation*}
\pi^n_m\circ h^G_n=h^G_m.
\end{equation*}
\item
For every such group $G$, there is a unique homomorphism $h$ from $G$ to $\Gal{\F_p}$ such that, for each $n$ in $\N$,
\begin{equation*}
h^G_n=h^{\Gal{\F_p}}_n\circ h.
\end{equation*}
\end{compactenum}
See Figure~\ref{fig:Gal}.
\begin{figure}[ht]
\begin{equation*}
\xymatrix{
&\Gal{\F_p}\ar[ddl]_{h^{\Gal{\F_p}}_n}\ar[ddr]^{h^{\Gal{\F_p}}_m}&\\
&G\ar[dl]^{h^G_n}\ar[dr]_{h^G_m}\ar[u]_h&\\
\Z/n\Z\ar[rr]_{\pi^n_m}&&\Z/m\Z
}
\end{equation*}
\caption{The universal property of $\Gal{\F_p}$}\label{fig:Gal}
\end{figure}
Therefore $\Gal{\F_p}$ is called a \textbf{limit} of the given system
of groups and homomorphisms.  This is the category-theoretic sense of
\emph{limit} as given in, say, \cite[p.\ 705]{MR97a:13001} or
\cite{MR1094561}.  Every set of groups, equipped with some
homomorphisms, has a limit in this sense, though the limit might be
empty.

The group $\Gal{\F_p}$ is called more precisely a \textbf{projective
  limit} or an \textbf{inverse limit} of the system of groups $\Z/n\Z$
with the quotient-maps, because any two of these groups are quotients of a
third.  This condition is not required for the existence of the limit.

We give the finite groups $\Z/n\Z$ the discrete topology, and their
product the product topology.  This product is compact by the
Tychonoff Theorem (mentioned above on page \pageref{Tychonoff}).  The
image of $\Gal{\F_p}$ in this group is closed, so it too is compact:
it is called a \textbf{pro-finite completion} of the system of finite
cyclic groups.\footnote{Perhaps one should talk about convergent sequences here\dots}

\section{Pseudo-finite fields}

Two examples of infinite models of the theory of finite fields are:
\begin{align}\label{eqn:psf}
&\prod_{p\text{ prime}}\F_p/M,&
&\prod_{n\in\N}\F_{p^n}/M,
\end{align}
where in each case $M$ is some non-principal maximal ideal.  The first
example has characteristic $0$; the second, characteristic $p$. 

By the `Riemann Hypothesis for curves' as proved by Weil,\footnote{See for
example \cite[Ex.~V.1.10, p.~368]{MR0463157} or \cite[Thm 3.14,
  p.~35]{MR89b:12010}.} for every prime power $q$, for every curve $C$
of genus $g$ over $\F_q$, the number of $\F_q$-rational points of $C$
is at least  
\begin{equation*}
1+q-2g\rad q.
\end{equation*}
In particular, if $q$ is large enough, then $C$ does have an
$\F_q$-rational point. 

A field $K$ is called \textbf{pseudo-algebraically-closed} or
\textbf{PAC} if every plane curve defined over $K$ has a $K$-rational
point.  This condition entails that every absolutely
  irreducible variety over $K$ has a $K$-rational point.\footnote{See
  \cite[ch.~10, pp.~129--131]{MR89b:12010}.}  
  
  The following are now true of every infinite model of the theory of finite fields: 
\begin{compactenum}
\item
It is perfect.
\item
It has exactly one extension of each degree (in some algebraic closure).
\item
It is pseudo-algebraically-closed.
\end{compactenum}
This is not obvious, even given the results stated above; one must show that these conditions are
\emph{first-order,} that is, the structures that satisfy them make up
an elementary class.
By the definition of Ax \cite{MR0229613}, a field with the first two
of these properties is \textbf{quasi-finite;} with all three of these
properties, \textbf{pseudo-finite.}  So every infinite model of the
theory of finite fields is (quasi-finite and) pseudo-finite.  Ax
proves the converse.  In particular, Ax proves that every
pseudo-finite field is elementarily equivalent to a non-principal ultraproduct of finite fields, and indeed to one of the
ultraproducts given above in \eqref{eqn:psf}.  The method is as
follows; here I use Ax \cite{MR0229613} and also Chatzidakis \cite{Chatzidakis-psf}. 

For every field $K$, the field $\Abs K$ of \textbf{absolute numbers}
of $K$ consists of the algebraic elements of $K$ (here algebraic means
algebraic over the prime field). 
The following is \cite[Prop.~7$'$, \S10, p.~261]{MR0229613}.

\begin{lemma}
For every field $K$ of prime characteristic $p$, there is a maximal
ideal $M$ of $\prod_{n\in\N}\F_{p^n}$ such that 
\begin{equation*}
\Abs K\cong\Abs{\prod_{n\in\N}\F_{p^n}/M}.
\end{equation*}
\end{lemma}

\begin{proof}
Because $\alg{\F_p}=\bigcup_{n\in\N}\F_{p^n}$ as in \eqref{eqn:algFp} on page \pageref{eqn:algFp}, we need only choose $M$ so that, for all $m$ in $\N$,
\begin{equation*}
\F_{p^m}\included K\iff\F_{p^m}\included \prod_{n\in\N}\F_{p^n}/M.
\end{equation*}
For each $m$ in $\N$, let $f_m$ be an irreducible element of $\F_p[X]$
of degree $m$.  Then each zero of $f_m$ generates $\F_{p^m}$ over $\F_p$.  So we want $M$ to be such that
\begin{equation*}
\F_{p^m}\included K\iff f_m\text{ has a zero in }\prod_{n\in\N}\F_{p^n}/M.
\end{equation*}
Let $F$ be the ultrafilter on $\N$ corresponding to $M$, that is,
\begin{equation*}
F=\{\N\setminus\supp f\colon f\in M\}=\bigl\{\{n\colon f_n=0\}\colon f\in M\}.
\end{equation*}
Then
\begin{equation*}
f_m\text{ has a zero in }\prod_{n\in\N}\F_{p^n}/M\iff\{n\colon f_m\text{ has a zero in }\F_{p^n}\bigr\}\in F.
\end{equation*}
Moreover,
\begin{equation*}
f_m\text{ has a zero in }\F_{p^n}\iff m\divides n.
\end{equation*}
So, combining all of our equivalences, we want to choose $F$ on $\N$ such that 
\begin{equation*}
\F_{p^m}\included K\iff\{n\colon m\divides n\}\in F.
\end{equation*}
For each $m$ in $\N$, the subset
\begin{equation*}
\{k\colon k\divides m\And\F_{p^k}\included K\}
\end{equation*}
of $\N$ is a sublattice of the lattice of factors of $m$ with respect to
divisibility: in particular, it contains the least common multiple of
any two members.  It also contains $1$.\footnote{Thus it contains the least common multiple of every (finite) set of members, including the empty set.}  Therefore it has a maximum element, say $g(m)$.  The
arithmetic function $g$ is multiplicative: 
\begin{equation*}
\gcd(m,n)=1\implies g(mn)=g(m)\cdot g(n).
\end{equation*}
Now let
\begin{equation*}
b_m=\{x\colon \gcd(m,x)=g(m)\}.
\end{equation*}
Then the function $m\mapsto b_m$ is also multiplicative, in the sense that
\begin{equation}\label{eqn:bmn}
\gcd(m,n)=1\implies b_{mn}=b_m\cap b_n.
\end{equation}
Indeed, suppose $\gcd(m,n)=1$.  Then or all $x$ in $\N$,
\begin{equation*}
\gcd(mn,x)=\gcd(m,x)\cdot\gcd(n,x),
\end{equation*}
and these factors are co-prime, being respectively factors of $m$ and $n$.  But also $g(mn)=g(m)\cdot g(n)$, and these factors are co-prime, being respectively factors of $m$ and $n$.  Therefore
\begin{equation*}
\gcd(mn,x)=g(mn)\iff\gcd(m,x)=g(m)\And\gcd(n,x)=g(n).
\end{equation*}
So we have \eqref{eqn:bmn}.  Moreover, we have also
\begin{equation}\label{eqn:bn-bm}
m\leq n\implies b_{\ell^n}\included b_{\ell^m}.
\end{equation}
For, we have
\begin{equation*}
b_{\ell^n}=
\begin{cases}
\{g(\ell^n)\cdot y\colon\ell\ndivides y\},&\text{ if }g(\ell^n)<\ell^n,\\
\{\ell^ny\colon y\in\N\},&\text{ if }g(\ell^n)=\ell^n,
\end{cases}
\end{equation*}
and also
\begin{equation*}
m\leq n\implies g(\ell^m)=\min\bigl(\ell^m,g(\ell^n)\bigr).
\end{equation*}
Now we can just check that \eqref{eqn:bn-bm} holds in each of the three cases
\begin{align*}
g(\ell^n)&=\ell^n,& \ell^m&<g(\ell^n)<\ell^n,& g(\ell^n)&<\ell^m.
\end{align*}
So we have finally
\begin{equation*}
b_m\cap b_n=b_{\lcm(m,n)}.
\end{equation*}
Thus, since each $b_m$ is nonempty, the set of these generates a proper filter on $\N$.  Let $F$ be an ultrafilter on $\N$ that contains all of the sets $b_m$.  We claim
that this $F$ is as desired.  Indeed, 
\begin{compactitem}
\item
if $\F_{p^m}\included K$, so $g(m)=m$, then $b_m=\{mx\colon x\in\N\}$;
\item
if $\F_{p^m}\nincluded K$, so $g(m)<m$, then $b_m\cap\{mx\colon x\in\N\}=\emptyset$. 
\end{compactitem}
Consequently the following are equivalent:
\begin{gather*}
	\F_{p^m}\included K,\\
	\{mx\colon x\in\N\}\in F,\\
	f_m\text{ has a root in }\prod_{n\in\N}\F_{p^n}/M,\\
	\F_{p^m}\included\prod_{n\in\N}\F_{p^n}/M.\qedhere
\end{gather*}
\end{proof}

The lemma has a companion \cite[Prop.~7]{MR0229613}, namely that for
every quasi-finite field $K$ of characteristic $0$, there is a maximal
ideal $M$ of $\prod_{p}\F_p$ such that 
\begin{equation*}
\Abs K=\Abs{\prod_p\F_p/M},
\end{equation*}
but the proof is more difficult.  Since all fields of characteristic
$0$ are perfect, quasi-finiteness in this case just means having
exactly one extension of each degree.  In this case the field of
absolute numbers has \emph{at most} one extension of each degree.
This is because, if $\alpha$ is algebraic over $\Abs K$, then $\alpha$ has the same degree over $K$ that it has over $\Abs K$.  For, the minimal polynomial of $\alpha$ over $\Abs K$ is a product
\begin{equation*}
\prod_{i<n}(X-\alpha_i),
\end{equation*}
the $\alpha_i$ being the conjugates of $\alpha$ over $\Abs K$.  The minimal polynomial over $K$ is a factor of this; so its coefficients are polynomial functions of (some of) the conjugates of $\alpha$ over $\Abs K$.  So the coefficients are algebraic (over $\Abs K$); therefore the already belong to $\Abs K$, by its definition.

We now want to prove \cite[Thm 4, \S8, p.~255]{MR0229613}, that if $F$
and $F'$ are pseudo-finite fields, then 
\begin{equation}\label{eqn:FF'}
\Abs F\cong\Abs{F'}\implies F\equiv F'.
\end{equation}
With this and the foregoing lemma, we shall have that every
pseudo-finite field (at least in positive characteristic) is
elementarily equivalent to an ultraproduct of finite fields. 

To establish \eqref{eqn:FF'}, since $\Abs F$ is determined by $\Th F$,
we can replace $F$ and $F'$ (respectively) by elementarily equivalent
fields.  In particular, we can replace them with ultrapowers with exponent
$\upomega$; these ultrapowers are $\upomega_1$-saturated by
Theorem~\ref{thm:sat} on page \pageref{thm:sat}. 
Now take a countable elementary substructure $F_0$ of $F$; this exists by the
downward L\"owenheim--Skolem--Tarski Theorem, Theorem~\ref{thm:dLST}.
One shows \cite[5.10, Lemme de plongement]{Chatzidakis-psf} that this
embeds in $F'$ under a monomorphism $\phi_0$.  Then $F'$ has an
elementary substructure $F'_0$ that includes the image of $F_0$; and
$F'_0$ embeds in $F$ under a monomorphism $\phi'_0$ that extends
$\phi_0{}\inv$.  Continuing, we obtain isomorphic elementary
substructures $F_{\upomega}$ and $F'_{\upomega}$ of $F$ and $F'$
respectively.  See Figure~\ref{fig:tower}.
\begin{figure}
  \begin{equation*}
    \xymatrix{
F                                              &F'\\
F_{\upomega}\ar[r]^{\bigcup_{n\in\upomega}\phi_n}\ar@{-}[u]&F_{\upomega}'\ar@{-}[u]\\
F_1\ar[r]^{\phi_1}\ar@{.}[u]                      &\phi_1[F_1]\ar@{.}[u]\\
\phi_0'[F_0']\ar@{-}[u]                          &F_0'\ar[l]_{\phi_0'}\ar@{-}[u]\\
F_0\ar[r]^{\phi_0}\ar@{-}[u]                      &\phi_0[F_0]\ar@{-}[u]
}
  \end{equation*}
  \caption{Isomorphisms of pseudo-finite fields}\label{fig:tower}  
\end{figure}
This establishes \eqref{eqn:FF'}.
\begin{comment}



An uncountable, quasi-finite field $F$ is called \textbf{hyper-finite}
if for every subfield $E$ of $F$, for every \emph{absolutely entire}
$E$-algebra $R$ of cardinality less than $F$, there is a homomorphism
from $R$ to $F$ over $E$.  Here, $R$ is \textbf{absolutely entire} if
$\alg E\otimes_ER$ is \emph{entire,} that is, is an integral
domain.\footnote{Lang \cite[pp.\ 91--92]{Lang-alg} recommends
  \emph{entire} as the adjective form of \emph{integral domain,}
  observing that \emph{integral} would have been better, had it not
  already been taken for other purposes.} 

Hyper-finiteness is a kind of \emph{saturation.}  Ax's route is to
show \cite[Prop.~4, \S7, p.~254]{MR0229613} that saturation implies
hyper-finiteness, and to show \cite[Thm~2, \S5, p.~248]{MR0229613}
that if $F$ and $F'$ in \eqref{eqn:FF'} are hyper-finite of the same
cardinality, then 
\begin{equation*}
\Abs F\cong\Abs{F'}\implies F\cong F'
\end{equation*}



\end{comment}

\chapter{Schemes}

Sources for the algebraic geometry of this chapter include Coombes \cite{Coombes} and Hartshorne \cite{MR0463157}.  The main point is to look at the \emph{ultraproduct scheme} at the end; this work is based on the first of the three MSRI/Evans Hall Lectures, given at the University of California at Berkeley in the spring of 1998 by Angus Macintyre.\footnote{These lectures used to be preserved on the MSRI website; but I could not find them there, the last time I looked.}


\section{The spectrum of a polynomial ring}

In \S\ref{sect:Gal}, letting $f$ range over $K[\vec X]$ where $\vec X=(X^0,\dots,X^{n-1})$, and letting $\vec x$ range over $L^n$ where $K\included L$, we used the equation
$f(\vec x)=0$ to establish a Galois correspondence between the
$K$-closed subsets of $L^n$ and certain radical ideals of $K[\vec X]$.
If $L$ is large enough (by Theorem~\ref{thm:N} on page
\pageref{thm:N})---more precisely, if $L$ includes $\alg K$ (by Theorem 
\ref{thm:HN} and its corollary)---, then the Galois correspondence is
between the $K$-closed subsets of $L^n$ and (all of) the radical
ideals of $K[\vec X]$.  In particular, the correspondence is inclusion-reversing.  Thus the set of radical ideals of $K[\vec X]$
encodes the topological structure of $L^n$ for sufficiently large $L$,
even for $L$ including $\alg K$. 

Suppose indeed $\alg K\included L$.
We want more than the Galois correspondence.  Suppose we are given a particular $f$ in $K[\vec X]$.  We
are interested in its zero-locus, the $K$-closed set $\V f$; and this now corresponds to $\I{\V f}$, which is $\rad(f)$.  We
should should like to have a way of picking out this ideal among all
of the radical ideals of $K[\vec X]$, without having to refer to $L^n$.  One way of doing this is simply to observe that $\rad(f)$ is the intersection of all radical ideals of $K[\vec X]$ that contain $f$.  We shall develop an alternative that is in some ways more satisfying.

If $\vec a\in L^n$, let us write $\I{\vec a}$ for $\I{\{\vec a\}}$.  That is,
\begin{equation*}
\I{\vec a}=\{f\in K[\vec X]\colon f(\vec a)=0\}.
\end{equation*}
This is always a prime ideal.  In particular,
it is radical.  Moreover, for every subset $A$ of $L^n$,
\begin{equation*}
  \I A=\bigcap_{\vec x\in A}\I{\vec x}.
\end{equation*}
In particular,
\begin{equation*}
  \I{\V f}=\bigcap_{\vec x\in\V f}\I{\vec x}.
\end{equation*}
Thus $\I{\V f}$ is the intersection of \emph{some} prime ideals of $K[\vec X]$ that include it.  Therefore it is the intersection of \emph{all} prime ideals of $K[\vec X]$ that include it.  

Let us henceforth denote $K[\vec X]$ simply by $R$.
Then the set of all prime ideals of $K[\vec X]$ is denoted by
\begin{equation*}
\spec.
\end{equation*}
(This will later be understood as part of the \emph{spectrum} of $R$.)  Usually $\mathfrak p$ will be understood as ranging over this set.  We have the following.

\begin{theorem}\label{thm:rad-pre}
For all radical ideals $\mathfrak a$ of $R$,
\begin{equation*}
\mathfrak a=\bigcap\{\mathfrak p\in\spec\colon\mathfrak a\included\mathfrak p\}.
\end{equation*}
In particular, for all $f$ in $R$,
\begin{equation*}
\rad(f)=\bigcap\{\mathfrak p\in\spec\colon f\in\mathfrak p\}.
\end{equation*}
\end{theorem}

\begin{proof}
If $L$ is large enough, then we now have
\begin{equation*}
\mathfrak a=\I{\V{\mathfrak a}}
=\bigcap\{\mathfrak p\colon\I{\V{\mathfrak a}}\included\mathfrak p\}
=\bigcap\{\mathfrak p\colon\mathfrak a\included\mathfrak p\}.
\end{equation*}
Also, for all $\mathfrak p$ in $\spec$,
\begin{equation*}
\rad(f)\included\mathfrak p\iff f\in\mathfrak p.\qedhere
\end{equation*}
\end{proof}

This theorem is true for arbitrary rings $R$ (see Theorem \ref{thm:rad} below); but in the present case the work of proving it has already been done for the Nullstellensatz (Theorem \ref{thm:N}).

In the theorem, the condition that $f\in\mathfrak p$ is equivalent to the condition that $f+\mathfrak p=0$ in $R/\mathfrak p$.  Moreover:

\begin{theorem}
The homomorphism 
\begin{equation*}
f\mapsto(f+\mathfrak p\colon\mathfrak p\in\spec)
\end{equation*}
from $R$ into the product
\begin{equation*}
\prod_{\mathfrak p\in\spec}R/\mathfrak p
\end{equation*}
is an embedding.
\end{theorem}

\begin{proof}
The kernel of this map is $\bigcap\spec$, which is the trivial ideal since this ideal is prime.
\end{proof}

So if $L$ is large enough, that is $L\includes \alg K$, we have a one-to-one correspondence between:
\begin{compactitem}
\item
closed subsets $\V{\mathfrak a}$ of $L^n$;
\item
radical ideals $\mathfrak a$ of $R$;
\item
subsets $\{\mathfrak p\in\spec\colon\mathfrak a\included\mathfrak p\}$ of $\spec$.
\end{compactitem}
Moreover, suppose we write
\begin{equation*}
(f_{\mathfrak p}\colon\mathfrak p\in\spec)=(f+\mathfrak p\colon\mathfrak p\in\spec).
\end{equation*}
That is, we consider this as a function $\mathfrak p\mapsto f_{\mathfrak p}$ on $\spec$, where $f_{\mathfrak p}\in R/\mathfrak p$.  If $A\included R$, then
\begin{align*}
\{\mathfrak p\in\spec\colon A\included\mathfrak p\}
&=\bigcap_{f\in A}\{\mathfrak p\in\spec\colon f\in\mathfrak p\}\\
&=\bigcap_{f\in A}\{\mathfrak p\in\spec\colon f_{\mathfrak p}=0\}.
\end{align*}
This is a kind of zero-locus.  If $f\in R$, we can define
\begin{equation*}
\V[]f=\{\mathfrak p\in\spec\colon f_{\mathfrak p}=0\}
\end{equation*}
(with no subscript on the Z this time), and if $A\included R$, we define
\begin{equation*}
\V[]A=\bigcap_{f\in A}\V[]f.
\end{equation*}
Just as in \S\ref{sect:ag}, by the same proofs, we have
\begin{equation*}
\V[]A=\V[]{\rad(A)},
\end{equation*}
and these sets are the closed sets of a topology on $\spec$.  In particular, to establish
\begin{equation*}
\V[]{\mathfrak a}\cup\V[]{\mathfrak b}=\V[]{\mathfrak a\cap\mathfrak b}
\end{equation*}
corresponding to \eqref{eqn:Vab} on page \pageref{eqn:Vab},
we need that the functions $\mathfrak p\mapsto f_{\mathfrak p}$ on $\spec$ take values in integral domains; and this is the case, since $f_{\mathfrak p}\in R/\mathfrak p$.

The inverse image of the basic closed set $\V[]f$ under $\vec x\mapsto\I{\vec x}$ is just $\V f$, since
\begin{align*}
\{\vec x\in L^n\colon\I{\vec x}\in\V[]f\}
&=\{\vec x\in L^n\colon f\in\I{\vec x}\}\\
&=\{\vec x\in L^n\colon f(x)=0\}\\
&=\V f.
\end{align*}
Thus the function $\vec x\mapsto\I{\vec x}$ from $L^n$ to $\spec$ is continuous, and moreover, every closed subset of $L^n$ is the inverse image of a closed subset of $\spec$.
The argument here uses nothing about $L$ (except $L\includes K$, as always).

The function $\vec x\mapsto\I{\vec x}$ injective on $K^n$, since if $\vec a\in K^n$ then 
\begin{equation*}
\I{\vec a}=(X^0-a^0,\dots,X^{n-1}-a^{n-1}).
\end{equation*}
The map is not generally injective:\label{pi} if $n=2$, $K=\Q$, and $L$ is
$\R$ or $\C$, then 
\begin{equation*}
\I{(\uppi,\uppi)}=(X-Y)=\I{(\mathrm e,\mathrm e)}.
\end{equation*}
The map is not generally surjective, even if $L$ is large enough to ensure $\mathfrak a=\I{\V{\mathfrak a}}$ for radical $\mathfrak a$:  If $L=\alg{\Q}$, then $(X-Y)$ is not in the range.  But still the map is surjective when $L$ is large enough, not just `algebraically', but also `transcendentally':

\begin{lemma}
If $\alg{K(\vec X)}\included L$, then every prime ideal of $K[\vec X]$ is $\I{\vec a}$ for some $\vec a$ in $L^n$.
\end{lemma}

\begin{proof}
Suppose $\mathfrak p$ is a prime ideal of $K[\vec X]$.  We can embed $K[\vec X]/\mathfrak p$ in $L$ over $K$.  Let $a^i$ be the image of $X^i+\mathfrak p$ under this embedding.  Then for all $f$ in $K[\vec X]$ we have that $f(\vec a)$ is the image of $f+\mathfrak p$. Therefore $\I{\vec a}=\mathfrak p$.
\end{proof}

\begin{theorem}\label{thm:scco}
If $\alg{K(\vec X)}\included L$, then the map $\vec x\mapsto\I{\vec x}$ from $L^n$ to $\spec$ is surjective, continuous, closed, and open.
\end{theorem}

\begin{proof}
The lemma gives surjectivity.  Before that, we proved continuity.  We also proved that closed subsets of $L^n$ are inverse images of closed subsets of $\spec$.  Taking complements, we have that open sets are inverse images of open sets.  By surjectivity, a set is the inverse image only of its own image; so $\vec x\mapsto\I{\vec x}$ must be closed and open.
\end{proof}

Thus, if $\alg{K(\vec X)}$, then $L^n$ is nearly indistinguishable from $\spec$.  However, as we observed with $(\uppi,\uppi)$ and $(\mathrm e,\mathrm e)$, the former space can contain distinct, but topologically indistinguishable, points: distinct points $\vec a$ and $\vec b$ such that every open set containing one of them contains the other.  This just means $\I{\vec a}=\I{\vec b}$, that is, the two points are sent to the same point of $\spec$.  The $\spec$ itself is not Hausdorff, but it is `$\mathrm T_0$': if $\mathfrak p$ and $\mathfrak q$ are distinct points of $\spec$, then there is $f$ belonging to $\mathfrak p\symdiff\mathfrak q$, and this means $\V[]f$ contains only one of the points.

It will be useful to have a notation for the \emph{open} subsets of $\spec$.  If $f\in R$, let us write
\begin{equation*}
\U f=\V[]f\comp=\{\mathfrak p\in\spec\colon f\notin\mathfrak p\}. 
\end{equation*}
If $A\included R$, we let
\begin{equation*}
\U A=\V[]A\comp=\bigcup_{f\in A}\U f=\{\mathfrak p\in\spec\colon A\not\included\mathfrak p\}. 
\end{equation*}
These are the open subsets of $\spec$, and each of them is $\U{\mathfrak a}$ for some radical ideal $\mathfrak a$ of $R$.  

\section{Regular functions}

At the beginning of the last section, we considered the equation $f(\vec x)=0$, where $f\in K[\vec X]$ and $\vec x\in L^n$.  We have generally $f(\vec x)\in L$, that is, $f$ is a function from $L^n$ to $L$.  There can be other such functions.  An arbitrary function $h$ from a subset $S$ of $L^n$ to $L$ is \textbf{regular} (or more precisely \emph{$K$-regular}) \emph{at} a point $\vec a$ of $S$ if there is a neighborhood $U$ of $\vec a$ (in the Zariski topology over $K$, restricted to $S$) and there are elements $f$ and $g$ of $K[\vec X]$ such that, for all $\vec x$ in $U$,
\begin{equation*}
h(\vec x)=\frac{f(\vec x)}{g(\vec x)}.
\end{equation*}
The function is \textbf{regular,} simply, if it is regular at all points of its domain.
The only regular functions on $L^n$ itself are the elements of $K[\vec X]$.  However,\label{Y^2-X^3} let
\begin{align*}
S_0&=\V{Y^2-X^3}\setminus\V X,&
S_1&=\V{Y^2-X^3}\setminus\V Y.
\end{align*}
These are open subsets of their union.
On $S_0$ and $S_1$ respectively there are regular functions $h_0$ and $h_1$ given by
\begin{align*}
h_0(x,y)&=\frac y{x^2},&
h_1(x,y)&=\frac xy.
\end{align*}
These two functions agree on $S_0\cap S_1$, since $y^2=x^3$ for all $(x,y)$ in that set (and even in $S_0\cup S_1$).  Thus $h_0\cup h_1$ is a regular function $h$ on $S_0\cup S_1$.  However, there are no $f$ and $g$ in $K[X,Y]$ such that, for all $(x,y)$ in $S_0\cup S_1$, $h(x,y)= f(x,y)/g(x,y)$.

In the example, $S_0\cup S_1$ is an open subset of the closed subset $\V{Y^2-X^3}$ of $L^2$.  For now, we shall look just at open subsets of the powers $L^n$ themselves.  

If $\mathfrak p$ is a prime ideal of $K[\vec X]$, and $f$ and $g$ in $K[\vec X]$ are such that $\vec x\mapsto f(\vec x)/g(\vec x)$ is well-defined (and therefore regular) on $L^n\setminus\V{\mathfrak p}$, this means $f/g$ is a well-defined element of the local ring $K[\vec X]_{\mathfrak p}$.

Now write $R=K[\vec X]$ as before, and let $\mathfrak a$ be an arbitrary radical ideal of $R$, so that $\U{\mathfrak a}$ is an open subset of $\spec$.  We define shall define a sub-ring, to be denoted by
\begin{equation*}
\Oh{\U{\mathfrak a}},
\end{equation*}
of the product\footnote{Note well that the factors of the product are
  the localizations $R_{\mathfrak p}$, rather than, say, the
  quotient-fields of the quotients $R/\mathfrak p$.  However, in the
  other case that we shall be interested in, where $R$ is itself a
  product of fields, then the integral domains $R/\mathfrak p$ will
  already be fields, which are isomorphic to the localizations
  $R_{\mathfrak p}$.  See \S\ref{sect:vN} below.} 
\begin{equation*}
\prod_{\mathfrak p\in\U{\mathfrak a}}R_{\mathfrak p}.
\end{equation*}
See Figure \ref{fig:stalk}.
\begin{figure}[ht]
\centering
\psset{unit=8mm}
    \begin{pspicture}(0,1)(9.5,5.5)
%\psgrid
    \psellipse(4,3)(4,2)
\psline{->}(6,3)(6,5.4)
\psdot(6,3)
\uput[r](6,5.4){$R_{\mathfrak p}$}
\uput[r](6,3){$\mathfrak p$}
\uput[r](8.1,3){$\spec$}
  \end{pspicture}
  \caption[A stalk of a sheaf]{A stalk of a sheaf (see p.\ \pageref{stalk})}\label{fig:stalk}
\end{figure}
Elements of this product are functions on $\U{\mathfrak a}$; so as
before we have a notion of being \emph{regular:}  An element $h$ of
the product is \textbf{regular} at a point $\mathfrak p$ of
$\U{\mathfrak a}$ if, for some open subset $V$ of $\U{\mathfrak a}$
that contains $\mathfrak p$, there are $f$ and $g$ in $R$ such that,
for all $\mathfrak q$ in $V$, 
\begin{equation*}
h_{\mathfrak q}=\frac fg.
\end{equation*}
Note that this requires $g\notin\mathfrak q$.  The ring $\Oh{\U{\mathfrak a}}$ consists of the elements of $\prod_{\mathfrak p\in\U{\mathfrak a}}R_{\mathfrak p}$ that are regular at all points of $\U{\mathfrak a}$.

There is a simpler definition when $\mathfrak a$ is a principal ideal $(g)$.  In this case, one shows
\begin{equation*}
\Oh{\U{(g)}}\cong\{g^k\colon k\in\upomega\}\inv R,
\end{equation*}
because the map $x/g^n\mapsto(x/g^n\colon\mathfrak p\in\U{(g)})$ from this ring to $\Oh{\U{(g)}}$ is injective and surjective.  See Hartshorne \cite[Prop.~II.2.2, p.~71]{MR0463157}.

If $U$ and $V$ are open subsets of $R$ such that $U\includes V$, then the restriction-map from $\prod_{\mathfrak p\in U}R_{\mathfrak p}$ to
$\prod_{\mathfrak p\in V}R_{\mathfrak p}$ itself restricts to a map $\rho^U_V$ from $\Oh U$ to $\Oh V$.  If $h\in\Oh U$, we then write
\begin{equation*}
\rho^U_V(h)=h\restriction V.
\end{equation*}
 The function $U\mapsto\Oh U$ on the collection of open subsets of $R$, together with these homomorphisms $\rho_{UV}$, is called a \textbf{pre-sheaf} of rings on $\spec$ because:
\begin{align*}
\Oh{\emptyset}&=\{0\},&
\rho^U_U&=\id U,&
\rho^U_W&=\rho^V_W\circ\rho^U_V.
\end{align*}
(The notation $\rho^U_V$ implies $U\includes V$; so for the last equation we have $U\includes V\includes W$.)
We now have a situation that is `dual' (because the arrows are reversed) to that of the Galois group $\Gal{\F_p}$: see page \pageref{up}.  For all $\mathfrak p$ in $\spec$, $R_{\mathfrak p}$ has a certain `universal property' with respect to the system of rings $\Oh U$ such that $\mathfrak p\in U$:
\begin{compactenum}
\item
$R_{\mathfrak p}$ is a ring $A$ to which there is a homomorphism $h^U_A$ from $\Oh U$ for such that, if $U\includes V$, then
\begin{equation*}
h^V_A\circ\rho^U_V=h^U_A.
\end{equation*}
\item
For every such ring $A$, there is a unique homomorphism $h$ to $A$ from $R_{\mathfrak p}$ such that
\begin{equation*}
h^U_A=h\circ h^U_{R_{\mathfrak p}}.
\end{equation*}
\end{compactenum}
See Figure~\ref{fig:Rp}.
\begin{figure}[ht]
\begin{equation*}
\xymatrix{
&R_{\mathfrak p}\ar[d]_h&\\
&A&\\
\Oh V\ar[uur]^{h^V_{R_{\mathfrak p}}}\ar[ur]_{h^V_A}&&\Oh U\ar[uul]_{h^U_{R_{\mathfrak p}}}\ar[ul]^{h^U_A}\ar[ll]^{\rho^U_V}
}
\end{equation*}
\caption{The universal property of $R_{\mathfrak p}$}\label{fig:Rp}
\end{figure}
Therefore $R_{\mathfrak p}$ is called a \textbf{co-limit} or \textbf{direct limit} of the given system of rings.  This limit can be obtained as a quotient of the sum $\sum_{\mathfrak p\in U}\Oh U$ by the smallest ideal that contains, for each pair $U$ and $V$ such that $U\pincludes V$, every element $x$ such that $x_V=\rho^U_V(x_U)$, and $x_W=0$ if $W$ is not $U$ or $V$.

The pre-sheaf $U\mapsto\Oh U$ is further a \textbf{sheaf} of rings because it has two additional properties:
\begin{compactenum}
\item
If $h\in\Oh U$, and $h\restriction V=0$ for all $V$ in an open covering of $U$, then $h=0$.
\item
If there is $h_V$ in $\Oh V$ for every $V$ in an open covering of $U$, and
\begin{equation*}
h_V\restriction(V\cap W)=h_W\restriction(V\cap W)
\end{equation*}
for all $V$ and $W$ in this open covering, then for some $h$ in $\Oh U$, for each $V$ in the open covering,
\begin{equation*}
h_V=h\restriction V.
\end{equation*}
\end{compactenum}
The local ring $R_{\mathfrak p}$ is the \textbf{stalk}\label{stalk} of
the sheaf at $\mathfrak p$.  In the fullest sense, the
\textbf{spectrum} of $R$ is $\spec$ as a topological space equipped
with this sheaf.  The sheaf is then the \textbf{structure sheaf} of
the spectrum of $R$. 

\section{Generic points and irreducibility}

This section is here for completeness, but will not be used later.
Every point $\vec a$ of $L^n$ is called a \textbf{generic point} of
$\V{\I{\vec a}}$; more precisely, $\vec a$ is a generic point
\emph{over} $K$ of $\V{\I{\vec a}}$.  In the example on page \pageref{pi},
$(\uppi,\uppi)$ and $(\mathrm e,\mathrm e)$ 
are generic points of $\V{X-Y}$
%$\{(x,x)\colon x\in\R\}$ 
over $\Q$.  

In any case, if for some radical
ideal $\mathfrak a$, the algebraic set $\V{\mathfrak a}$ has a generic
point, then $\mathfrak a$ must be prime. 
The converse may fail.  For example, $\V{(X-Y)}$ has no generic point
if $L\included\alg{\Q}$.  However, to Theorem \ref{thm:scco}, we have the following

\begin{corollary}
If $\alg{K(\vec X)}\included L$, then the zero-locus in $L$ of every prime ideal has a generic point. 
\end{corollary}


A closed subset of $L^n$ is called \textbf{irreducible} if it cannot
be written as the union of two closed subsets, neither of which
includes the other.

\begin{theorem}
For all radical ideals $\mathfrak a$ of $K[\vec X]$, if $\alg K\included L$,
\begin{center}
$\mathfrak a$ is prime $\iff$ $\V{\mathfrak a}$ is irreducible.
\end{center}
\end{theorem}

\begin{proof}
If $\mathfrak p$ is prime, and $\V{\mathfrak p}=\V{\mathfrak a}\cup\V{\mathfrak b}$ for some radical ideals $\mathfrak a$ and $\mathfrak b$, then (by Hilbert's Nullstellensatz)
\begin{equation*}
\mathfrak p=\mathfrak a\cap\mathfrak b,
\end{equation*}
so we may assume $\mathfrak p=\mathfrak a$ and therefore $\V{\mathfrak a}\includes\V{\mathfrak b}$.

Suppose conversely $\V{\mathfrak a}$ is irreducible, and $fg\in\mathfrak a$.  Then
\begin{equation*}
\V{\mathfrak a}=\V{\mathfrak a\cup\{f\}}\cup\V{\mathfrak a\cup\{g\}},
\end{equation*}
so we may assume $\V{\mathfrak a}=\V{\mathfrak a\cup\{f\}}$ and therefore (again by Hilbert's Nullstellensatz) $f\in\mathfrak a$.
\end{proof}

For example, $L^n$ itself is irreducible, since the zero-ideal of $K[\vec X]$
is prime.  Therefore the closure of every open subset is the whole
space $L^n$.  In any case, every closed set is the union of only
finitely many irreducible closed sets: this is by the corollary to the
Hilbert Basis Theorem (Theorem~\ref{thm:H} on page \pageref{thm:H}).  Hence every radical
ideal of $K[\vec X]$ is the intersection of just finitely many elements of
$\spec[{K[\vec X]}]$.  

\section{Affine schemes}

The construction of the spectrum of $K[\vec X]$ can be carried out for any ring (that is, commutative unital ring).  For an arbitrary ring $R$, we can still let $\spec$ be the set of prime ideals of $R$.  Then every element $f$ of $R$ determines a function $\mathfrak p\mapsto f_{\mathfrak p}$ on $\spec$, where $f_{\mathfrak p}$ is the element $f+\mathfrak p$ of $R/\mathfrak p$.  However, the corresponding map
\begin{equation}\label{eqn:Rto}
f\mapsto(f_{\mathfrak p}\colon\mathfrak p\in\spec)
\end{equation}
from $R$ to $\prod_{\mathfrak p\in\spec}R/\mathfrak p$ need not be injective.  For example, the kernel of this map contains $X+(X^2)$ when $R=K[X]/(X^2)$.

We do have the generalization of Theorem \ref{thm:rad-pre} on page \pageref{thm:rad-pre}:

\begin{theorem}\label{thm:rad}
For all subsets $A$ of $R$,
\begin{equation*}
\rad(A)=\bigcap\{\mathfrak p\in\spec\colon A\included\mathfrak p\}.
\end{equation*}
\end{theorem}

\begin{proof}
It is clear that the intersection includes $\rad(A)$.  Now suppose $x\in R\setminus\rad(A)$.  Let $\mathfrak b$ be an ideal of $R$ that is maximal with respect to including $\rad(A)$, but not containing any power of $x$.  Say $y$ and $z$ are not in $\mathfrak b$.  By maximality,
\begin{align*}
x&\in\mathfrak b+(y),&
x&\in\mathfrak b+(z),
\end{align*}
and therefore
\begin{equation*}
x^2\in\mathfrak b+(yz),
\end{equation*}
so $yz\notin\mathfrak b$ (since $x^2\notin\mathfrak b$).  Thus $\mathfrak b$ is prime.
\end{proof}

\begin{corollary}
$\bigcap\spec=\rad\{0\}$.
\end{corollary}

In particular, the kernel of $f\mapsto(f_{\mathfrak p}\colon\mathfrak p\in\spec)$ is $\rad\{0\}$.  (Again this is non-trivial if, for example, $R=K[X]/(X^2)$.)

As before, we still obtain a Galois correspondence between certain subsets of $R$ and of $\spec$.  If $A\included R$ and $B\included\spec$, we define
\begin{gather*}
\V[] A=\bigcap_{f\in A}\{\mathfrak p\in\spec\colon f_{\mathfrak p}=0\}
=\{\mathfrak p\in\spec\colon A\included\mathfrak p\},\\
\I[] B=\bigcap_{\mathfrak p\in B}\{f\in R\colon f_{\mathfrak p}=0\}=\bigcap B.
\end{gather*}
As before,
\begin{equation*}
\V[]A=\V[]{\rad{(A)}}.
\end{equation*}
So the sets $\V[]A$ (where $A\included R$) are just the sets $\V[]{\mathfrak a}$ (where $\mathfrak a$ is a radical ideal of $R$).  Moreover, by the last theorem, if $\mathfrak a$ and $\mathfrak b$ are distinct radical ideals, then $\V[]{\mathfrak a}\neq\V[]{\mathfrak b}$.  Thus we have:

\begin{theorem}[Nullstellensatz]
The functions $V\mapsto\I[] V$ and $\mathfrak a\mapsto\V[]{\mathfrak a}$ establish a one-to-one order-reversing correspondence between the radical ideals of $R$ and certain subsets of $\spec$.\hfill\qedsymbol
\end{theorem}

If $A\included R$, we define
\begin{equation*}
\U A=\V[]A\comp=\{\mathfrak p\in\spec\colon A\not\included\mathfrak p\}.
\end{equation*}

\begin{theorem}
The subsets $\U{\mathfrak a}$ of $\spec$ are the open sets of a topology on $\spec$.
\end{theorem}

\begin{proof}
Since the elements $\mathfrak p$ of $\spec$ are prime, we have
\begin{equation*}
\mathfrak a\mathfrak b\included\mathfrak p\iff\mathfrak a\included\mathfrak p\;\text{ or }\;\mathfrak b\included\mathfrak p
\end{equation*}
or rather
\begin{equation*}
\mathfrak a\mathfrak b\nincluded\mathfrak p\iff\mathfrak a\nincluded\mathfrak p\And\mathfrak b\nincluded\mathfrak p.
\end{equation*}
Therefore
\begin{equation*}
\U{\mathfrak a}\cap\U{\mathfrak b}=\U{\mathfrak{ab}}.
\end{equation*}
Also, $\spec=\U{(1)}$.  Finally, if $\mathcal A$ is a collection of ideals of $\spec$, then
\begin{equation*}
\bigcup_{\mathfrak a\in\mathcal A}\U{\mathfrak a}=\U{\sum\mathcal A}.
\end{equation*}
(As a special case, $\emptyset=\U{\{0\}}$.)
\end{proof}

The topology just given is of course the \textbf{Zariski topology.}  Just as before, we obtain the sheaf $U\mapsto\Oh U$ of rings on $\spec$, with stalks $R_{\mathfrak p}$.
Continuing the example on page \pageref{Y^2-X^3}, we may let
\begin{equation*}
R=K[X,Y]/(Y^2-X^3).
\end{equation*}
Let $x$ and $y$ be the images of $X$ and $Y$ respectively in $R$.  Then
\begin{equation*}
\U{(x,y)}=\U x\cup\U y,
\end{equation*}
and
\begin{align*}
\mathfrak p\in\U x&\implies\frac y{x^2}\in R_{\mathfrak p},&
\mathfrak p\in\U y&\implies\frac xy\in R_{\mathfrak p},
\end{align*}
 and if $\mathfrak p\in\U x\cap\U y$, then $y/x^2$ and $x/y$ are the same element of $R_{\mathfrak p}$.  Thus we obtain an element of $\Oh{\U{(x,y)}}$.

The spectrum of a ring is called an \textbf{affine scheme.}  One point of introducing this terminology is that a \emph{scheme,} simply, is a topological space with a sheaf of rings such that such that every point of the space has a neighborhood that, with the restriction of the sheaf to it, is an affine scheme.  However, we shall not look at schemes in general.  In fact we shall look at just one affine scheme whose underlying ring is not a polynomial ring.

\section{Regular rings (in the sense of von Neumann)}\label{sect:vN}

Again $R$ is an arbitrary ring (commutive and unital as always), and $\mathfrak p$ is a prime ideal.  We have worked with both the quotient $R/\mathfrak p$ and the localization $R_{\mathfrak p}$.  Are these two rings ever isomorphic?  More precisely, is there ever a well-defined isomorphism
\begin{equation*}
x+\mathfrak p\mapsto\frac x1
\end{equation*}
from $R/\mathfrak p$ to $R_{\mathfrak p}$?
\begin{compactitem}
\item
There is, if $R$ is already a field.
\item
There is not, if $R$ is an integral domain that is not a field; for in this case the homomorphism from $R$ to $R_{\mathfrak p}$ is a proper embedding.
\end{compactitem}
The homomorphism $x+\mathfrak p\mapsto x/1$ is well-defined if and only if
\begin{equation*}
x\in\mathfrak p\implies \frac x1=0,
\end{equation*}
that is, if $x\in\mathfrak p$, then $x\cdot s=0$ for some $s$ in $R\setminus\mathfrak p$.
In particular, we must have $\mathfrak p\included I_0$ (the set $\{0\}\cup\{\text{zero-divisors}\}$, defined on page \pageref{eqn:I_0}).

The homomorphism $x+\mathfrak p\mapsto x/1$ is injective if and only if
\begin{equation*}
\frac x1=0\implies
x\in\mathfrak p,
\end{equation*}
that is, if $x\cdot s=0$ for some $s$ in $R\setminus\mathfrak p$, then $x\in\mathfrak p$.  Since $\mathfrak p$ contains $0$ and is prime, the homomorphism is automatically injective (if it is well-defined).

The homomorphism is surjective if and only if, for all $x/y$ in $R_{\mathfrak p}$, there is $z$ in $R$ and there is $s$ in $R\setminus\mathfrak p$ such that $(x-yz)\cdot s=0$, that is,
\begin{equation*}
xs=yzs.
\end{equation*}
It is enough if, for some $z$,
\begin{equation*}
xy=yzy.
\end{equation*}
It is then enough if $z$ has the form $xy^*$ for some $y^*$.  Then it is enough if
\begin{equation*}
y=yy^*y.
\end{equation*}
A ring in which for every element $y$ there is $y^*$ with this property is called a \textbf{regular ring} (in the sense of von Neumann).\footnote{The definition applies to non-commutative rings as well.}

A Boolean ring is a regular ring: just let $x^*$ be $1$ or $x$ (or anything in between).  We have shown in effect that every such ring embeds in a power $\F_2{}^{\Omega}$ of the two-element field.  More generally, if $(K_i\colon i\in \Omega)$ is an indexed family of arbitrary fields, then the product
\begin{equation*}
\prod_{i\in \Omega}K_i
\end{equation*}
is a regular ring.  Indeed, if $x\in R$, we can define $x^*$ by
\begin{equation*}
x^*{}_i=
\begin{cases}
	x_i{}\inv,&\text{ if }x_i\neq0,\\
	0,&\text{ if }x_i=0.
\end{cases}
\end{equation*}
Then indeed $xx^*x=x$.  We shall see presently that all regular rings embed in such products.

\begin{theorem}
Let $R$ be a regular ring, and let $\mathfrak p$ be a prime ideal, then the map
\begin{equation*}
x+\mathfrak p\mapsto\frac x1
\end{equation*}
is a well-defined isomorphism from $R/\mathfrak p$ to $R_{\mathfrak p}$.  Moreover, each of these rings is a field.  Thus $\mathfrak p$ is maximal.
\end{theorem}

\begin{proof}
For all $x$ in $R$, we have $x=xx^*x$, that is,
\begin{equation*}
x\cdot(1-xx^*)=0.
\end{equation*}
Since $\mathfrak p$ is a proper ideal, we have
\begin{equation*}
x\in\mathfrak p\iff 1-xx^*\in R\setminus\mathfrak p.
\end{equation*}
Thus, as above, the homomorphism is well-defined.  It is then injective and surjective, as we said.  In particular, in $\R_{\mathfrak p}$,
\begin{equation*}
\frac x1\neq0\iff x\in R\setminus\mathfrak p\iff \frac 1x\text{ is well-defined};
\end{equation*}
so $R_{\mathfrak p}$ is a field.
\end{proof}

The map in \eqref{eqn:Rto} on page \pageref{eqn:Rto} is now an embedding into a product of fields:

\begin{corollary}
Every regular ring $R$ embeds in the product
\begin{equation*}
\prod_{\mathfrak p\in\spec}R/{\mathfrak p}
\end{equation*}
(which is a product of fields) under the map
\begin{equation*}
f\mapsto(f+\mathfrak p\colon p\in\spec).
\end{equation*}
\end{corollary}

\begin{proof}
We need only note that the given map is injective, which it is because all ideals of $R$ are radical, so that
\begin{equation*}
\bigcap\spec=\rad{\{0\}}=\{0\}.\qedhere
\end{equation*}
\end{proof}

\section{The ultraproduct scheme}

Now let $R$ be the product $\prod_{i\in\Omega}K_i$ of fields as above.  As $\mathfrak p$ ranges over $\spec$, the quotients $R/\mathfrak p$ are just the possible ultraproducts of the fields $K_i$.  We want to investigate how these arise from the structure sheaf of the spectrum of $R$.  So, letting $\mathfrak a$ be an ideal of $R$, we want to understand $\Oh{\U{\mathfrak a}}$. 

We can identify $\spec$ with $\spec[\pow{\Omega}]$, and more generally, we can identify ideals of $R$ with ideals of $\pow{\Omega}$.  Because $R_{\mathfrak p}\cong R/\mathfrak p$, we may assume
\begin{equation*}
\Oh{\U{\mathfrak a}}\included\prod_{\mathfrak p\in\U{\mathfrak a}}R/\mathfrak p.
\end{equation*}
Here we may treat $\mathfrak a$ as an ideal of $\pow{\Omega}$, so $\U{\mathfrak a}$ can be thought of as an open subset of $\spec[\pow{\Omega}]$.  Then, in the product $\prod_{\mathfrak p\in\U{\mathfrak a}}R/\mathfrak p$, the index $\mathfrak p$ ranges over this open subset, but in the quotient $R/\mathfrak p$, the index returns to being the corresponding ideal of $R$.

Let $s\in\prod_{\mathfrak p\in\U{\mathfrak a}}R/\mathfrak p$.  Every \emph{principal} ideal in $\U{\mathfrak a}$ is $(\Omega\setminus\{i\})$ for some $i$ in $\Omega$.  In this case we have $\mathfrak a\nincluded(\Omega\setminus\{i\})$, that is,
\begin{equation*}
i\in\bigcup\mathfrak a.
\end{equation*}
Let us denote $(\Omega\setminus\{i\})$ by $\mathfrak p(i)$.
There is only one prime ideal of $\pow{\Omega}$ that does not contain $\{i\}$, namely $\mathfrak p(i)$.  Thus
\begin{equation*}
\U{\{i\}}=\{\mathfrak p(i)\}.
\end{equation*}
In particular, $s$ is automatically regular at $\mathfrak p(i)$.  We want to understand when $s$ is regular at not-principal ideals.  

Still considering also the principal ideals, we have
\begin{equation*}
R/\mathfrak p(i)\cong K_i.
\end{equation*}
Let $s_{\mathfrak p(i)}$ be sent to $s_i$ under this isomorphism, so whenever $x$ in $R$ is such that $x_i=s_i$, we have
\begin{equation*}
s_{\mathfrak p(i)}=x+\mathfrak p(i).
\end{equation*}
By definition, we have $s\in\Oh{\U{\mathfrak a}}$ if and only if, for all $\mathfrak p$ in $\U{\mathfrak a}$, for some subset $\U{\mathfrak b}$ of $\mathfrak a$ such that $\mathfrak b\nincluded\mathfrak p$, for some $x$ in $R$, for all $\mathfrak q$ in $\U{\mathfrak b}$,
\begin{equation*}
s_{\mathfrak q}=x+\mathfrak q.
\end{equation*}
We may assume $\mathfrak b$ is a principal ideal $(A)$, where $A\in\mathfrak a\setminus\mathfrak p$.  If $\mathfrak q$ in $\U A$ here is the principal ideal $\mathfrak p(j)$, so that $j\in A$, we must have $x_j=s_j$.  More generally, $\mathfrak q\in\U A$ means $A\notin\mathfrak q$, so $A$ is $\mathfrak q$-large, and hence for all $x$ in $R$, $x+\mathfrak q$ is determined by $(x_i\colon i\in A)$.  Thus we may assume
\begin{equation*}
x=(s_i\colon i\in\Omega).
\end{equation*}
This establishes that $\Oh{\U{\mathfrak a}}$ is the image of $R$ in $\prod_{\mathfrak p\in\U{\mathfrak a}}R/\mathfrak p$:
\begin{equation*}
\Oh{\U{\mathfrak a}}=\{(x+\mathfrak p\colon\mathfrak p\in\U{\mathfrak a})\colon x\in R\}.
\end{equation*}
In particular, $\Oh{\U{\mathfrak a}}$ is a quotient of $R$, that is, a reduced product of the $K_i$.  More precisely,
\begin{equation*}
\Oh{\U{\mathfrak a}}\cong R/\mathfrak b,
\end{equation*}
where
\begin{equation*}
\mathfrak b
=\bigcap_{\mathfrak p\in\U{\mathfrak a}}\mathfrak p
=\bigcap_{\mathfrak a\nincluded\mathfrak p}\mathfrak p.
\end{equation*}
It follows that
\begin{equation}\label{eqn:OU}
\Oh{\U{\mathfrak a}}\cong\prod_{i\in\bigcup\mathfrak a}K_i.
\end{equation}
We can see this in two ways.  For example, if $\mathfrak
p\in\U{\mathfrak a}$, so that $\mathfrak a\nincluded\mathfrak p$, then
$\bigcup\mathfrak a\notin\mathfrak p$, that is, $\bigcup\mathfrak a$
is $\mathfrak p$-large.  Therefore the image of $x$ in
$\Oh{\U{\mathfrak a}}$ depends only on $(x_i\colon
i\in\bigcup\mathfrak a)$.  This shows that $\Oh{\U{\mathfrak a}}$ is a
quotient of $\prod_{i\in\bigcup\mathfrak a}K_i$. 

It is moreover the quotient by the trivial ideal.  For, if
$i\in\bigcup\mathfrak a$, then $\mathfrak p(i)\in\U{\mathfrak a}$, so
that $x+\mathfrak p(i)$ depends only on $x_i$, that is,
\begin{equation*}
  x+\mathfrak p(i)=0\iff x_i=0.
\end{equation*}
This gives us \eqref{eqn:OU}.

Note that possibly $\bigcup\mathfrak a\notin\mathfrak p$, although
$\mathfrak a\included\mathfrak p$.  Such is the case when $\mathfrak
p$ is non-principal, but $\mathfrak a$ is the ideal of finite sets.
However, we always have
\begin{equation*}
  \bigcup\mathfrak a\notin\mathfrak p\implies(\bigcup\mathfrak
  a)\nincluded\mathfrak p.
\end{equation*}

Another way to establish \eqref{eqn:OU} is to show
\begin{equation*}
  \bigcap_{\mathfrak a\nincluded\mathfrak p}\mathfrak
  p=(\Omega\setminus\bigcup\mathfrak a).
\end{equation*}
If $X\included\Omega\setminus\bigcup\mathfrak a$, and $\mathfrak
a\nincluded\mathfrak p$, then $\bigcup\mathfrak a\notin\mathfrak p$,
so $\Omega\setminus\bigcup\mathfrak a\in\mathfrak p$, and therefore
$X\in\mathfrak p$.  Inversely, if
$X\nincluded\Omega\setminus\bigcup\mathfrak a$, then
$X\cap\bigcup\mathfrak a$ has an element $i$, so that
$X\notin\mathfrak p(i)$ and $\mathfrak a\nincluded\mathfrak p(i)$.

Because the stalk $R_{\mathfrak p}$ is always a direct limit of those
$\Oh U$ such that $\mathfrak p\in U$, we have in the present situation
that the ultraproduct $\prod_{i\in\Omega}K_i/\mathfrak p$
is a direct limit of those products 
$\prod_{i\in A}K_i$ such that $A\notin\mathfrak p$.
Symbolically,
\begin{equation*}
  \prod_{i\in\Omega}K_i/\mathfrak p=\lim_{\longrightarrow}\Bigl\{\prod_{i\in
    A}K_i\colon A\notin\mathfrak p\Bigr\}.
\end{equation*}
Equivalently, the ultraproduct is the direct limit of those
$R/\mathfrak a$ such that $\mathfrak a$ is a principal ideal included
in $\mathfrak p$:
\begin{equation*}
  \prod_{i\in\Omega}K_i/\mathfrak
  p=\lim_{\longrightarrow}\Bigl\{\prod_{i\in\Omega}K_i/(B)\colon
  B\in\mathfrak p\Bigr\}. 
\end{equation*}



%\bibliographystyle{amsplain}
%\bibliography{../../../references}
%\bibliography{../references}

\def\rasp{\leavevmode\raise.45ex\hbox{$\rhook$}} \def\cprime{$'$}
  \def\cprime{$'$} \def\cprime{$'$} \def\cprime{$'$}
\providecommand{\bysame}{\leavevmode\hbox to3em{\hrulefill}\thinspace}
\providecommand{\MR}{\relax\ifhmode\unskip\space\fi MR }
% \MRhref is called by the amsart/book/proc definition of \MR.
\providecommand{\MRhref}[2]{%
  \href{http://www.ams.org/mathscinet-getitem?mr=#1}{#2}
}
\providecommand{\href}[2]{#2}
\begin{thebibliography}{10}

\bibitem{MR0229613}
James Ax, \emph{The elementary theory of finite fields}, Ann. of Math. (2)
  \textbf{88} (1968), 239--271. \MR{MR0229613 (37 \#5187)}

\bibitem{MR1094561}
Michael Barr and Charles Wells, \emph{Category theory for computing science},
  Prentice Hall International Series in Computer Science, Prentice Hall
  International, New York, 1990. \MR{MR1094561 (92g:18001)}

\bibitem{MR0269486}
J.~L. Bell and A.~B. Slomson, \emph{Models and ultraproducts: {A}n
  introduction}, North-Holland Publishing Co., Amsterdam, 1969, reissued by
  Dover, 2006. \MR{MR0269486 (42 \#4381)}

\bibitem{Borovik-infinitesimals}
Alexandre Borovik and Mikhael Katz, \emph{Inevitability of infinitesimals},
  \url{http://manchester.academia.edu/AlexandreBorovik/Papers/305871/Inevitability_of_infinitesimals},
  accessed July 18, 2012.

\bibitem{MR91c:03026}
C.~C. Chang and H.~J. Keisler, \emph{Model theory}, third ed., Studies in Logic
  and the Foundations of Mathematics, vol.~73, North-Holland Publishing Co.,
  Amsterdam, 1990. \MR{91c:03026}

\bibitem{Chatzidakis-psf}
Zo{\'e} Chatzidakis, \emph{Th{\'e}orie de mod{\`e}les des corps finis et
  pseudo-finis}, Pr{\'e}publications de l'Equipe de Logique, Universit\'e Paris
  VII, Octobre 1996, \url{http://www.logique.jussieu.fr/~zoe/}.

\bibitem{MR18:631a}
Alonzo Church, \emph{Introduction to mathematical logic. {V}ol. {I}}, Princeton
  University Press, Princeton, N.~J., 1956. \MR{18,631a}

\bibitem{Logicomix}
Apostolos Doxiadis and Christos~H. Papadimitriou, \emph{Logicomix}, Bloomsbury,
  London, 2009.

\bibitem{MR97a:13001}
David Eisenbud, \emph{Commutative algebra}, Graduate Texts in Mathematics, vol.
  150, Springer-Verlag, New York, 1995, With a view toward algebraic geometry.
  \MR{97a:13001}

\bibitem{MR0142459}
T.~Frayne, A.~C. Morel, and D.~S. Scott, \emph{Reduced direct products}, Fund.
  Math. \textbf{51} (1962/1963), 195--228. \MR{0142459 (26 \#28)}

\bibitem{MR0154807}
\bysame, \emph{Correction to the paper ``{R}educed direct products''}, Fund.
  Math. \textbf{53} (1963), 117. \MR{0154807 (27 \#4751)}

\bibitem{MR89b:12010}
Michael~D. Fried and Moshe Jarden, \emph{Field arithmetic}, Ergebnisse der
  Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related
  Areas (3)], vol.~11, Springer-Verlag, Berlin, 1986. \MR{89b:12010}

\bibitem{Goedel-compl}
Kurt G{\"o}del, \emph{The completeness of the axioms of the functional calculus
  of logic (1930a)}, From Frege to G{\"o}del (Jean van Heijenoort, ed.),
  Harvard University Press, 1976, pp.~582--91.

\bibitem{MR0463157}
Robin Hartshorne, \emph{Algebraic geometry}, Springer-Verlag, New York, 1977,
  Graduate Texts in Mathematics, No. 52. \MR{MR0463157 (57 \#3116)}

\bibitem{MR94e:03002}
Wilfrid Hodges, \emph{Model theory}, Encyclopedia of Mathematics and its
  Applications, vol.~42, Cambridge University Press, Cambridge, 1993.
  \MR{94e:03002}

\bibitem{Coombes}
howpublished={\url{http://odin.mdacc.tmc.edu/~krcoombes/agathos/contents.html}}~note={accessed
  August 6, 2012} Kevin R.~Coombes, title={AGATHOS: Algebraic Geometry: A Total
  Hypertext Online System}.

\bibitem{MR85e:03003}
Kenneth Kunen, \emph{Set theory}, Studies in Logic and the Foundations of
  Mathematics, vol. 102, North-Holland Publishing Co., Amsterdam, 1983, An
  introduction to independence proofs, Reprint of the 1980 original.
  \MR{85e:03003}

\bibitem{Lang-alg}
Serge Lang, \emph{Algebra}, third ed., Addison-Wesley, Reading, Massachusetts,
  1993, reprinted with corrections, 1997.

\bibitem{MR0075156}
Jerzy {\L}o{\'s}, \emph{Quelques remarques, th\'eor\`emes et probl\`emes sur
  les classes d\'efinissables d'alg\`ebres}, Mathematical interpretation of
  formal systems, North-Holland Publishing Co., Amsterdam, 1955, pp.~98--113.
  \MR{MR0075156 (17,700d)}

\bibitem{Lowenheim}
Leopold L\"owenheim, \emph{On possibilities in the calculus of relatives
  (1915)}, From Frege to G{\"o}del (Jean van Heijenoort, ed.), Harvard
  University Press, 1976, pp.~228--251.

\bibitem{Post}
Emil~L. Post, \emph{Introduction to a general theory of elementary
  propositions}, Amer. J. Math. \textbf{43} (1921), no.~3, 163--185.

\bibitem{Skolem-LS}
Thoralf Skolem, \emph{Logico-combinatorial investigations in the satisfiability
  or provability of mathematical propositions: {A} simplified proof of a
  theorem by {L}. {L}{\"o}wenheim and generalizations of the theorem (1920)},
  From Frege to G{\"o}del (Jean van Heijenoort, ed.), Harvard University Press,
  1976, pp.~252--63.

\bibitem{MR1501865}
M.~H. Stone, \emph{The theory of representations for {B}oolean algebras},
  Trans. Amer. Math. Soc. \textbf{40} (1936), no.~1, 37--111. \MR{MR1501865}

\bibitem{PM}
Alfred~North Whitehead and Bertrand Russell, \emph{Principia mathematica},
  vol.~I, University Press, Cambridge, 1910.

\end{thebibliography}


\newpage
\thispagestyle{empty}

\begin{figure}[p]
  \begin{sideways}
\centering
%\includegraphics[width=417pt,height=292pt]{german-script-cropped.eps}
\includegraphics%[width=1\textwidth]%[width=350pt]%
{german-script-cropped.eps}
  \end{sideways}
%\caption{Alman el yaz\i s\i}%\label{fig:German}
\end{figure}


\end{document}
