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

%\usepackage[notref,notcite]{showkeys}

\usepackage[headsepline]{scrpage2}
\pagestyle{scrheadings}
\clearscrheadings
\ohead{\pagemark}
\ihead{\headmark}
\ihead{Non-standard analysis}

\usepackage{cclicenses}
\usepackage[perpage,symbol]{footmisc}
\renewcommand{\captionformat}{. }

\usepackage{verbatim}

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


\usepackage{relsize} % Here \smaller scales by 1/1.2; \relscale{X} scales by X

\renewenvironment{quote}{\begin{list}{}
{\relscale{.90}\setlength{\leftmargin}{0.05\textwidth}
\setlength{\rightmargin}{\leftmargin}}
\item[]}
{\end{list}}



%\usepackage{multicol}
\usepackage{pstricks}

\usepackage{amsmath,amsthm,amssymb,bm,upgreek}
\usepackage[all]{xy}
\newcommand{\Forall}[1]{\forall#1\;}
\newcommand{\Exists}[1]{\exists#1\;}
\newcommand{\abs}[1]{\lvert#1\rvert}
\renewcommand{\epsilon}{\varepsilon}
\newcommand{\icl}{\simeq}  %infinitesimally close to
\newcommand{\N}{\mathbb N}
\newcommand{\Z}{\mathbb Z}
\newcommand{\Q}{\mathbb Q}
\newcommand{\R}{\mathbb R}
\newcommand{\C}{\mathbb C}
\newcommand{\F}{\mathbb F}
\newcommand{\included}{\subseteq}
\newcommand{\includes}{\supseteq}
\newcommand{\pincluded}{\subset}
\DeclareMathOperator{\characteristic}{char}
\newcommand{\Char}[1]{\characteristic(#1)}
\DeclareMathOperator{\standardpart}{st}
\newcommand{\stp}[1]{\standardpart(#1)}
\newcommand{\inv}{^{-1}}
\DeclareMathOperator{\support}{supp}
\newcommand{\supp}[1]{\support(#1)}
\newcommand{\symdiff}{\triangle}
\newcommand{\starred}{{}^*}
\newcommand{\stR}{{}^*\R}
\newcommand{\stf}{{}^*\!f}
\newcommand{\stN}{{}^*\N}
\newcommand{\sta}{{}^*\!a}
\newcommand{\stA}{{}^*\!A}
\newcommand{\units}{^{\times}}
\usepackage{mathrsfs}
\newcommand{\pow}[1]{\mathscr P(#1)}
\newcommand{\powf}[1]{\mathscr P_{\upomega}(#1)}
\renewcommand{\emptyset}{\varnothing}
\renewcommand{\setminus}{\smallsetminus}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\renewcommand{\phi}{\varphi}
%\newcommand{\Or}{\;\lor\;}
\newcommand{\Or}{\;\mathrel{\text{\textsc{or}}}\;}
\renewcommand{\models}{\vDash}
\newcommand{\nmodels}{\nvDash}
\newcommand{\bv}[1]{\lVert#1\rVert}
\newcommand{\sig}{\mathscr S}
\newcommand{\str}[1]{\mathfrak{#1}}
\newcommand{\monad}[1]{\upmu(#1)}
\DeclareMathOperator{\theory}{Th}
\newcommand{\Th}[1]{\theory(#1)}
\DeclareMathOperator{\spectrum}{Spec}
\newcommand{\spec}[1][R]{\spectrum(#1)}
\newcommand{\comp}{^{\mathrm c}}
\DeclareMathOperator{\diagram}{diag}
\newcommand{\diag}[1]{\diagram(#1)}
\newcommand{\lto}{\Rightarrow}
\newcommand{\liff}{\Leftrightarrow}
\DeclareMathOperator{\symmetry}{Sym}
\newcommand{\Sym}[1][\Omega]{\symmetry(#1)}
\DeclareMathOperator{\identity}{id}
\newcommand{\id}[1][\Omega]{\identity_{#1}}
\DeclareMathOperator{\modelclass}{Mod}
\newcommand{\Mod}[1][\sig]{\modelclass(#1)}
\DeclareMathOperator{\sentences}{Sn}
\newcommand{\Sn}[1][\sig]{\sentences(#1)}
\newcommand{\modsim}{/\mathord{\sim}}
\newcommand{\modequiv}{/\mathord{\equiv}}
\newcommand{\modapprox}{/\mathord{\approx}}
\DeclareMathOperator{\Lindenbaum}{Lin}
\newcommand{\Lin}[1][0]{\Lindenbaum_{#1}(\sig)}
\DeclareMathOperator{\Stone}{S}
\newcommand{\St}[1]{\Stone(#1)}
\DeclareMathOperator{\Automorphisms}{Aut}
\newcommand{\Aut}[1][K]{\Automorphisms(#1)}
\newcommand{\Grel}{G}

%\newcommand{\xca}{EXERCISE}
\newcommand{\xca}{\textsc{exercise}}

\newtheorem{theorem}{Theorem}
\newtheorem{porism}{Porism}
\newtheorem{axiom}{Axiom}
\newtheorem{lemma}{Lemma}
\newtheorem*{los}{\L o\'s's Theorem}

\theoremstyle{definition}
\newtheorem{problem}{Problem}

\newtheorem*{solution}{\c C\"oz\"um}

%\usepackage{verbatim}
%\let\solution=\comment
%\let\endsolution=\endcomment


\begin{document}

\title{Non-standard Analysis}
%\subtitle{log of course in \c Sirince}
\author{David Pierce}
\date{August 1, 2014}
\publishers{Miman Sinan G\"uzel Sanatlar \"Universitesi\\
\url{http://mat.msgsu.edu.tr/~dpierce/}}
\maketitle


\section*{Preface}

Here are notes of my course, called Rudiments of Nonstandard Analysis, 
given at the Nesin Mathematical Village, in \c Sirince, July 14--27, 2014.
I started lecturing in Turkish,
switching to English when it transpired that everybody understood this.
After every lecture, I wrote out a record what had happened.
The present document is a highly edited version of the daily records.
I have added some references, and cross-references,
and I have made some corrections and amplifications,
though without changing the content of particular days.

The experience of the students 
ranged from one year of university to some years of graduate school.
Prerequisites of the course had been given as 
\begin{quote}
Calculus and algebra (the theorem that maximal ideals are prime),
\end{quote}
though in the event, most of the students did not know much algebra.
The ``abstract'' of the course was
\begin{quote}
  The axiom of choice, ultrafilters, ultraproducts.
Connections with algebra.
The rudiments of nonstandard analysis.
\end{quote}
What actually happened can be seen in the main text.
A few \textsc{exercises} are made explicit in the text;
also, formally stated theorems without proofs can be considered as exercises.
In the actual course, some of these were proved by students at the board.

\tableofcontents

\listoffigures

\addsec{Summaries of the days}

\begin{enumerate}
\item 
  \begin{enumerate}[1.]
  \item 
Calculus with infinitesimals
(the limit of the sum is the sum of the limits).
Non-Archimedean ordered fields.
\item
More calculus with infinitesimals
(the limit of the product is the product of the limits).
Rings and their ideals.
Power sets as Boolean rings.
\item
Why $\R$ had to be rigorously defined.
Equivalence of standard and non-standard definitions of limits.
Dedekind's construction of $\R$.
The Cauchy-sequence construction of $\R$.
Valuation rings.
\item
Ideals of power sets.
The Maximal Ideal Theorem
and its proof by Zorn's Lemma.
Maximal ideals $\mathfrak m$ of $\pow{\upomega}$ 
that contain all finite subsets of $\upomega$.
The Sorites Paradox.
The ordering of the ultrapower $\R^{\upomega}/M$,
where $M$ is the maximal ideal 
$\{x\in\R^{\upomega}\colon\supp x\in\mathfrak m\}$.
\item
Ultraproducts $\left.\prod_{i\in\upomega}K_k\right/M$ of fields, as
for example finite fields.
Logical formulas.
The Prime Ideal Theorem.
\L o\'s's Theorem for fields,
and the Transfer Principle.
\item
\L o\'s's Theorem (and the Compactness Theorem) in an arbitrary signature.
$\stR$ as the [ultrapower] $\R^{\upomega}/M$.  $\stN$.
Non-standard analysis of sequences.
Filters and ultrafilters.
  \end{enumerate}
\item
  \begin{enumerate}[1.]
  \item 
Ultrafilters on $\upomega$.
More non-standard analysis of sequences.
Standard parts of finite non-standard real numbers.
Why the Transfer Principle does not apply to second-order properties.
\item
Non-standard analysis of bounded sets and limit points.
The Bolzano--Weierstrass Theorem.
\item
Closed sets and open sets.  Monads.
Logical and topological compactness.
The Heine--Borel Theorem.
\item
Topological spaces.
The compactness of the spectrum of a ring.
Non-standard characterization of topological compactness.
The logical Compactness Theorem implies the Prime Ideal Theorem.
Boolean algebras and the Stone Representation Theorem.
\item
Logical truth and Lindenbaum algebras.
Stone spaces and the proof of the Stone Representation Theorem.
Bases of topological spaces.
Proof of the logical Compactness Theorem
from the Prime Ideal Theorem.
\item
The Axiom of Choice
is equivalent to \L o\'s's Theorem and the Prime Ideal Theorem together.
  \end{enumerate}
\end{enumerate}

\section{First week}

\subsection{Monday}

Suppose a function $f$ is defined by
\begin{equation*}
  f(x)=
  \begin{cases}
    x\sin(1/x),&\text{ if }x\neq0,\\
0,&\text{ if }x=0.
  \end{cases}
\end{equation*}
Is $f$ continuous at $0$?  Why or why not?

By the standard definition,
for an arbitrary function $f$ from $\R$ to $\R$,
the expression
\begin{equation*}
  \lim_{x\to a}f(x)=L
\end{equation*}
means%%%%%
\footnote{Commonly the defining sentence is written as
$(\forall{\epsilon>0})(\exists{\delta>0})\forall x
(0<\abs{x-a}<\delta\lto\abs{f(x)-L}<\epsilon)$.}
%%%%%%%%%%%%%%%%%
\begin{multline}\label{eqn:st}
  \forall{\epsilon}\Bigl(\epsilon>0\implies\Exists{\delta}
\bigl(\delta>0\And\Forall x\\
(0<\abs{x-a}<\delta\implies\abs{f(x)-L}<\epsilon)\bigr)\Bigr).
\end{multline}
Then $f$ is continuous at $a$ if and only $\lim_{x\to a}f(x)=f(a)$.

\begin{theorem}\label{thm:+}
If
$\lim_{x\to a}f(x)=L$ and $\lim_{x\to a}g(x)=M$, 
then
\begin{equation*}
  \lim_{x\to a}(f+g)(x)=L+M
\end{equation*}
(``the limit of the sum is the sum of the limits'').
\end{theorem}

\begin{proof}[Standard proof.]
By the triangle inequality,
\begin{equation*}
  \abs{(f+g)(x)-(L+M)}\leq\abs{f(x)-L}+\abs{g(x)-M}.
\end{equation*}
  Suppose $\epsilon>0$.
For some positive $\delta_1$ and $\delta_2$,
\begin{gather*}
  0<\abs{x-a}<\delta_1\implies\abs{f(x)-L}<\frac{\epsilon}2,\\
  0<\abs{x-a}<\delta_2\implies\abs{g(x)-M}<\frac{\epsilon}2.
\end{gather*}
Let $\delta=\min(\delta_1,\delta_2)$.  Then
\begin{equation*}
  0<\abs{x-a}<\delta\implies\abs{f(x)-L}+\abs{g(x)-M}<\epsilon,
\end{equation*}
and therefore
\begin{equation*}
  0<\abs{x-a}<\delta\implies\abs{(f+g)(x)-(L+M)}<\epsilon.
\end{equation*}
Thus $\lim_{x\to a}(f+g)(x)=L+M$.
\end{proof}

By the standard, ``$\epsilon$-$\delta$'' definition,
$\lim_{x\to a}f(x)=L$ means that $f(x)$ 
is \textbf{relatively}\label{rel} close to $L$,
or as close as we like to $L$,
provided $x$ is \textbf{sufficiently} close (but not equal) to $a$.
Here the variable $x$ 
ranges over the \emph{ordered field} $\R$ of real numbers.

We are going to develop a notion of being ``absolutely'' close, 
denoted by $\simeq$.
Then $\lim_{x\to a}f(x)=L$ 
will mean that $f(x)$ is absolutely close to $L$,
provided $x$ is absolutely close (but not equal) to $a$:
in symbols,
\begin{equation}\label{eqn:nst}
  \Forall x(x\icl a\And x\neq a\implies f(x)\icl L).
\end{equation}
However, the variable $x$ here will range over an ordered field 
larger than $\R$.

If $x\icl a$, then $x-a\icl 0$,
and $x-a$ will be called \textbf{infinitesimal}
(or \textbf{infinitely small}).
The sum of two infinitesimals will be infinitesimal.
Then for the theorem above, we shall have:

\begin{proof}[Non-standard proof]
  If $x\icl a$, but $x\neq a$, then $f(x)\icl L$ and $g(x)\icl M$,
so $f(x)-L$ and $g(x)-M$ are infinitesimal,
and therefore so is their sum, which is equal to $(f+g)(x)-(L+M)$;
thus
\begin{equation*}
   (f+g)(x)\icl(L+M).\qedhere
\end{equation*}
\end{proof}

The simplest example of an ordered field 
that includes $\R$ and contains infinitesimals
is the field $\R(X)$ of rational functions in the variable $X$ over $\R$;
an arbitrary nonzero element of this field can be written as
\begin{equation*}
  \frac{a_nX^n+a_{n-1}X^{n-1}+\dots+a_0X^0}{b_mX^m+b_{m-1}X^{m-1}+\dots+b_0X^0}
\end{equation*}
for some nonnegative integers $n$ and $m$, 
for some $a_i$ and $b_j$ in $\R$, where $a_nb_m\neq0$.
We define the element of $\R(X)$ to be \textbf{positive} if $a_nb_m>0$.
Hence for all positive integers $n$,
\begin{equation*}
  X-n=\frac{1\cdot X^1-nX^0}{1\cdot X^0}>0,
\end{equation*}
so $X>n$, and therefore $0<1/X<1/n$.
Thus $X$ is \textbf{infinite,}
while $1/X$ is \textbf{infinitesimal.}

To be precise, there are two equivalent ways 
to define an ordering of a field $K$.
If $P\pincluded K$ and is closed under addition and multiplication,
while
\begin{equation*}
  P\sqcup\{0\}\sqcup\{-x\colon x\in P\}=K,
\end{equation*}
then $P$ is the set of \textbf{positive} elements of $K$ 
with respect to an ordering of $K$, given by
\begin{equation*}
  x<y\iff y-x\in P.
\end{equation*}
Alternatively, $<$ is linear ordering of $K$
such that
\begin{gather*}
  x<y\implies x+z<y+z,\\
x<y\And z>0\implies xz<yz.
\end{gather*}

Because it has infinite elements,
the ordered field $\R(X)$ is \textbf{non-Archi\-medean.}
It is not rich enough for doing analysis.
We are going to do analysis in a non-Archimedean ordered field denoted by
\begin{equation*}
  \stR,
\end{equation*}
which will be the \emph{quotient} $\R^{\upomega}/M$,
where
\begin{itemize}
\item 
$\upomega=\{0,1,2,\dots\}$, the set of nonnegative integers, and
\item
 $M$ is a \emph{nonprincipal maximal ideal} of the \emph{ring} $\R^{\omega}$
of functions from $\upomega$ to $\R$.
\end{itemize}

\subsection{Tuesday}

\begin{theorem}\label{thm:.}
  If
$\lim_{x\to a}f(x)=L$ and $\lim_{x\to a}g(x)=M$, 
then
\begin{equation*}
\lim_{x\to a}(fg)(x)=LM
\end{equation*}
(``the limit of the product is the product of the limits'').
\end{theorem}

\begin{proof}[Standard proof.]
Since
\begin{align*}
  \abs{(fg)(x)-LM}
&=\abs{f(x)\cdot g(x)-LM}\\
&=\abs{f(x)\cdot g(x)-f(x)\cdot M+f(x)\cdot M-LM}\\
&\leq\abs{f(x)}\cdot\abs{g(x)-M}+\abs{f(x)-L}\cdot\abs M,
\end{align*}
it is enough to let $\delta_1$ be such that
\begin{align*}
  0<\abs{x-a}<\delta_1
&\implies\abs{f(x)-L}<\frac{\epsilon}{2\abs M}\\
&\implies\abs{f(x)}<\abs L+\frac{\epsilon}{2\abs M},
\end{align*}
then let $\delta_2$ be such that
\begin{equation*}
    0<\abs{x-a}<\delta_2
\implies\abs{g(x)-M}
<\frac{\epsilon}{2\left(\abs L+\displaystyle\frac{\epsilon}{2\abs M}\right)},
\end{equation*}
then let $\delta=\max(\delta_1,\delta_2)$.
\end{proof}

For the non-standard proof,
taking place in the non-Archimedean ordered field $\stR$ mentioned above,
we have noted that the sum of infinitesimals is infinitesimal;
we also need that the product of a \textbf{finite}
(that is, non-infinite) number and an infinitesimal is infinitesimal.

\begin{proof}[Nonstandard proof]
  If $x\icl a$, then $f(x)\icl L$ and $g(x)\icl M$,
so $f(x)-L\icl0$ and $g(x)-M\icl0$, and therefore
\begin{align*}
(fg)(x)-LM
&=f(x)\cdot g(x)-LM\\
&=f(x)\cdot g(x)-f(x)\cdot M+f(x)\cdot M-LM\\
&=f(x)\cdot\bigl(g(x)-M\bigr)+\bigl(f(x)-L\bigr)\cdot M\\
&\icl0.\qedhere
\end{align*}
\end{proof}

What we now call simply calculus 
was once called \emph{infinitesimal} calculus
because it was conceived in terms of infinitesimals.
When calculus was made rigorous,
infinitesimals were not involved,
but today's $\epsilon$-$\delta$ definitions were developed.

Why make calculus rigorous?
Well, why do we believe that there is a number called $\surd2$?
For centuries or even millenia, 
we have been able to compute approximations to this number.
An algorithm for computing \emph{decimal} approximations
used to be learned in school (by my father, for example).
However, Dedekind asserts (and I agree) that,
before he gave a rigorous definition of the field $\R$ of real numbers, 
the equation
\begin{equation*}
  \surd2\cdot\surd3=\surd6
\end{equation*}
was not a theorem,
because there can be no algorithm for multiplying infinite decimal expansions.

Let us review precisely the axioms for fields.\label{fields}
First, an \textbf{abelian group} is a structure $(G,0,-,+)$,
where
\begin{itemize}
\item
addition ($+$) is a commutative, associative binary operation on the set $G$,
\item
$0$ is an identity with respect to addition, and
\item
$-$ is inversion with respect to addition and $0$.
\end{itemize}
A \textbf{field} is a structure $(K,0,1,-,+,\times)$, where
\begin{itemize}
\item 
$(K,0,-,+)$ and $(K\setminus\{0\},1,{}\inv,\times)$ are abelian groups
(for some singulary operation ${}\inv$ on $K\setminus\{0\}$), and
\item
multiplication ($\times$) distributes over addition.
\end{itemize}
If we do not require the existence of a multiplicative inverse ${}\inv$ 
on $K\setminus\{0\}$
(but we still require that $\times$ be commutative and associative,
with identity $1$),
then what we have is a \textbf{ring.}%%%%%
\footnote{In some books, what we have defined as a ring
would be called more precisely 
a nontrivial commutative ring with (multiplicative) identity;
but we shall consider no other rings than these.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
In a ring, by distributivity,
\begin{equation*}
  x\cdot0=x\cdot(0+0)=x\cdot0+x\cdot0.
\end{equation*}
Fields, like $\Q$ and $\R$, are rings,
but $\Z$ is a ring that is not a field.
Let
\begin{equation*}
  \N=\{1,2,3,\dots\};
\end{equation*}
this is not even a ring.
But if $n\in\N$, then there is a ring denoted by
\begin{equation*}
  \Z/n\Z,
\end{equation*}
consisting of the elements $x+n\Z$,
where
\begin{equation*}
  n\Z=\{ny\colon y\in\Z\},
\end{equation*}
so $x+n\Z=\{x+ny\colon y\in\Z\}$.
The ring $\Z/n\Z$ is a field if and only if $n$ is a prime $p$;
and then this field is denoted by
\begin{equation*}
  \F_p.
\end{equation*}
Can this be made into an \emph{ordered} field?
No, because in an ordered field, always
$1+\dots+1>0$.
Such a field has \textbf{characteristic} $0$;
but $\Char{\F_p}=p$, since in $\F_p$,
\begin{equation*}
  \underbrace{1+\dots+1}_p=0.
\end{equation*}
In general then, if $K$ is an ordered field, we may assume $\Q\included K$.
Let
\begin{gather*}
  R=\{\text{finite elements of $K$}\},\\
I=\{\text{infinitesimal elements of $K$}\}.
\end{gather*}
Then $R$ is a ring,
and $I$ is an \textbf{ideal}\label{ideal} of $R$,
because it is an additive subgroup of $R$
that is closed under multiplication by elements of $R$.

If $R$ is an arbitrary ring, and $I\included R$,
then $I$ is an ideal of $R$ if and only if
\begin{equation}\label{eqn:ideal}
\left.
  \begin{gathered}
  x,y\in I\implies x+y\in I,\\
r\in R\And x\in I\implies rx\in I,\\
0\in I.
\end{gathered}
\right\}
\end{equation}
A ring is the \textbf{improper ideal} of itself;
every other ideal of the ring is a \textbf{proper} ideal.
A \textbf{maximal ideal} of $R$ is a proper ideal $I$ that is maximal as such,
that is, for all ideals $J$ of $R$,
\begin{equation*}
  I\pincluded J\implies J=R.
\end{equation*}
Then $n\Z$ is an ideal of $\Z$; it is a proper ideal, if $n>1$;
it is a maximal ideal, if $n$ is prime.

An ideal is proper if and only if it does not contain $1$.
The ideal $I$\label{ideal-max} of infinitesimal elements 
of the ring $R$ of finite elements of a non-Archimedean field
is a maximal ideal,
because if $x\in R\setminus I$, then $x\inv\in R$, 
so any ideal of $R$ containing $x$ contains also $1$.

The \textbf{quotient ring} $R/I$ is defined like $\Z/n\Z$;
and when $I$ is a maximal ideal of $R$,
then $R/I$ is a field.

The ordered field $\R$ is \textbf{complete:}
every nonempty subset with an upper bound has a least upper bound,
that is, a \textbf{supremum.}
If again $R$ is the ring of finite elements of a non-Archimedean ordered field,
and $I$ is the ideal of infinitesimal elements,
then $R/I$ is an Archimedean ordered field,
and therefore it embeds in $\R$.
Indeed, since we may assume $\Q\included R$,
there is a map
\begin{equation}\label{eqn:sup}
  x+I\mapsto\sup\{u\in\Q\colon u<x\}
\end{equation}
from $R/I$ to $\R$, and this is an embedding.

An arbitrary element $a$ of the power $\R^{\upomega}$
can be written out as one of
\begin{align*}
  &(a_0,a_1,a_2,\dots),&&(a_k\colon k\in\upomega),
\end{align*}
where the $a_k$ are in $\R$.
Then the ring operations on $\R^{\upomega}$ are given by
\begin{gather*}
  a+b=(a_k+b_k\colon k\in\upomega),\\
  ab=(a_kb_k\colon k\in\upomega).
\end{gather*}
What are the ideals of $\R^{\upomega}$?
On $\R$, let us define\label{*}
\begin{equation*}
  x^*=
  \begin{cases}
    x\inv,&\text{ if }x\neq0,\\
0,&\text{ if }x=0;
  \end{cases}
\end{equation*}
and then on $\R^{\upomega}$,
\begin{equation*}
  x^*=(x_0{}^*,x_1{}^*,\dots)=(x_k{}^*\colon k\in\upomega).
\end{equation*}
There is a bijection $I\mapsto\bar I$\label{corr} 
from $\{\text{ideals of $\R^{\upomega}$}\}$
to $\{\text{ideals of $\F_2{}^{\upomega}$}\}$, where
\begin{equation*}
  \bar I=\{x^*x\colon x\in I\}.
\end{equation*}
Given $a$ in $\R^{\upomega}$ or $\F_2{}^{\upomega}$, we define
\begin{equation*}
  \supp a=\{i\in\upomega\colon a_i\neq0\},
\end{equation*}
the \textbf{support} of $a$.
Then $x\mapsto\supp x$ is a bijection 
from $\F_2{}^{\upomega}$ to $\pow{\upomega}$,
and for $x$ and $y$ in $\F_2{}^{\upomega}$ we have
\begin{gather*}
  \supp{xy}=\supp x\cap\supp y,\\
\supp{x+y}=\supp x\symdiff\supp y,
\end{gather*}
where $\symdiff$ denotes \textbf{symmetric difference:}
\begin{equation*}
  X\symdiff Y=(X\setminus Y)\cup(Y\setminus X)=(X\cup Y)\setminus(X\cap Y).
\end{equation*}
So $\pow{\upomega}$ is a ring,
with $\symdiff$ as addition
and $\cap$ as multiplication.
Then the maximal ideal $M$ of $\R^{\upomega}$
corresponds to a maximal ideal $\mathfrak m$ of $\pow{\upomega}$,
namely $\{\supp x\colon x\in M\}$.

The ring $\pow{\upomega}$ is a \textbf{Boolean ring,} that is,
\begin{equation*}
  x^2=x.
\end{equation*}
From this we have
\begin{gather*}
  2x=(2x)^2=4x^2=4x,\\
0=2x.
\end{gather*}
Thus the characteristic of a Boolean ring is $2$.
Hence also
\begin{equation*}
  x\cdot(1+x)=0,
\end{equation*}
so the only Boolean field is $\F_2$.
Hence $\pow{\upomega}/\mathfrak m\cong\F_2$, and
\begin{equation*}
  X\in\mathfrak m\iff\upomega\setminus X\notin\mathfrak m.
\end{equation*}

\subsection{Wednesday}

Why was it not a theorem before Dedekind that $\surd2\cdot\surd3=\surd6$?
We can approximate roots with decimals,
but have no algorithm for multiplying (or adding) infinite decimal expansions.
For example, what is
\begin{equation*}
  (2.333\dots)\times(2.\overline{142857})?
\end{equation*}
We have
\begin{align*}
  2.3\times2.1&=4.83,\\
2.33\times2.14&=4.9862,\\
2.333\times2.142&=4.997286,\\
2.3333\times2.1428&=4.99979524,\\
\intertext{but}
2.3334\times2.1429&=5.00024286.
\end{align*}
So we cannot know the first digit of the product,
just by computing with finitely many digits.

Dedekind gives us $\R$ as an ordered field.
Using this, we shall construct an ordered field $\stR$
(namely $\R^{\upomega}/M$ as before)
where $\R\pincluded\stR$.
If $f\colon\R\to\R$,
then $f$ will extend to a function $\stf$ from $\stR$ to $\stR$
(so $\stf\restriction\R=f$).
The equivalence between the standard and non-standard definitions
of limits (in \eqref{eqn:st} and \eqref{eqn:nst},
pages \pageref{eqn:st} and \pageref{eqn:nst}, respectively)
will be established as follows.

\begin{theorem}\label{thm:cong}
  In $\R$, \eqref{eqn:st} holds, namely
\begin{multline*}
  \forall{\epsilon}\Bigl(\epsilon>0\implies\Exists{\delta}
\bigl(\delta>0\And\Forall x\\
(0<\abs{x-a}<\delta\implies\abs{f(x)-L}<\epsilon)\bigr)\Bigr),
\end{multline*}
if and only if in $\stR$,
\begin{equation*}
  \Forall x(x\icl a\And x\neq a\implies\stf(x)\icl L).
\end{equation*}
\end{theorem}

\begin{proof}
  ($\Rightarrow$).
Suppose $b\icl a$ and $b\neq a$.
Then for all positive $\delta$ in $\R$,
$0<\abs{b-a}<\delta$.
Let $\epsilon\in\R$ and $\epsilon>0$.
By \eqref{eqn:st}, for some positive $\delta$ in $\R$,
\begin{equation*}
  \R\models
\Forall x(0<\abs{x-a}<\delta\implies\abs{f(x)-L}<\epsilon)
\end{equation*}
(here $\models$ is the truth relation),
and so (as we shall show)
\begin{equation*}
  \stR\models
\Forall x(0<\abs{x-a}<\delta\implies\abs{\stf(x)-L}<\epsilon),
\end{equation*}
and therefore $\abs{\stf(b)-L}<\epsilon$.
This being true for all positive $\epsilon$ in $\R$,
we have $\stf(b)\icl L$.

($\Leftarrow$).
Suppose \eqref{eqn:st} fails, so that, for some positive $\epsilon$ in $\R$,
\begin{equation*}
  \R\models\Forall{\delta}\bigl(\delta>0\implies
\Exists x(0<\abs{x-a}<\delta\And\abs{f(x)-L}<\epsilon)\bigr).
\end{equation*}
Then $\stR\models[\text{same thing, with $\stf$ for $f$}]$:
\begin{equation*}
  \stR\models\Forall{\delta}\bigl(\delta>0\implies
\Exists x(0<\abs{x-a}<\delta\And\abs{\stf(x)-L}<\epsilon)\bigr).
\end{equation*}
In particular, for all positive infinitesimal $\delta$,
there is $b$ in $\stR$ such that $0<\abs{b-a}<\delta$
(so $b\icl a$, but $b\neq a$), and $\abs{\stf(b)-L}\geq\epsilon$,
so $\stf(b)\not\icl L$.
\end{proof}

We could do non-standard analysis
(as in the non-standard proofs of Theorems \ref{thm:+} and \ref{thm:.}),
without proving Theorem \ref{thm:cong};
this theorem just assures us that we would not be doing anything new.

How do we get the property of $\stR$ used in the last proof?
First it will be useful to review how we obtain $\R$.
Recall from page \pageref{fields} 
that $(K,0,1,-,+,\times)$ is a \textbf{field}
if
\begin{itemize}
\item 
$(K,0,-,+)$ and $(K\setminus\{0\},1,{}\inv,\times)$ (for some ${}\inv$)
are abelian groups,
\item
$+$ distributes over $\times$.
\end{itemize}
If $(K\setminus\{0\},1,\times)$ is only a \textbf{monoid}
($\times$ is commutative and associative, $1$ is an identity),
then $(K,0,1,-,+,\times)$ is a \textbf{ring.}

If $K$ is a field, then $(K,<)$ is an \textbf{ordered field}
if $\{x\in K\colon x>0\}$ is closed under $+$ and $\times$,
and
\begin{equation*}
  K=\{x\in K\colon x<0\}\sqcup\{0\}\sqcup\{x\in K\colon x>0\}.
\end{equation*}

Adapting Dedekind's definition, let us say that
a \textbf{cut} of $\Q$ is a nonempty proper subset $A$ of $\Q$ such that%%%%%
\footnote{For Dedekind, the cut is $(A,\Q\setminus A)$,
and if $A$ has a supremum in $\Q$,
it does not matter whether this supremum belongs to $A$ or not.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{gather*}
  y\in A\And x<y\implies x\in A,\\
x\in A\implies\Exists y(y\in A\And x<y).
\end{gather*}
Let
\begin{equation*}
  \R=\{\text{cuts of $\Q$}\}.
\end{equation*}
Then $x\mapsto\{y\in\Q\colon y<x\}$ 
is an embedding of $(\Q,<)$ in $(\R,\pincluded)$,
and addition and multiplication on $\Q$
extend to \emph{continuous} operations on $\R$,
and then (by continuity)
$\R$ becomes an ordered field.

Note that Dedekind's construction relies only on the \emph{ordering} of $\Q$.
Another construction of $\R$ may be more useful for us.
For this, we let
\begin{align*}
  R&=\{\text{Cauchy sequences of $\Q$}\},\\
I&=\{\text{sequences of $\Q$ converging to $0$}\}.
\end{align*}
Recall that $a\in R$ means
\begin{multline*}
  \Forall{\epsilon}\bigl(\epsilon>0\implies\Exists k\Forall m\Forall n\\
(m\in\N\And k\leq m\And n\in\N\And k\leq n\implies\abs{a_m-a_n}<\epsilon)\bigr).
\end{multline*}
Then $I\pincluded R$.

\begin{theorem}
  $I$ is a maximal ideal of $R$.
\end{theorem}

\begin{proof}
  This is an \textsc{exercise;} but assuming $I$ is an ideal,
let us show it is maximal.
Say $a\in R\setminus I$.
We must show that every ideal $J$ containing $a$ and including $I$ is $R$.
Say $b\in R$ and $c\in I$.  Then $ab+c\in J$.
We want to show $1\in J$.  
So we want to find $b$ in $\R$ and $c$ in $I$ such that
\begin{equation*}
  ab+c=1.
\end{equation*}
Given that $a=(a_0,a_1,\dots)$, we could let $b=(a_0{}\inv,a_1{}\inv,\dots)$,
so $ab=(1,1,1,\dots)=1$.
But possibly $a_k=0$.
Recall from page \pageref{*} the definition on $\R$,
\begin{equation*}
  x^*=
  \begin{cases}
    x\inv,&\text{ if }x\neq0,\\
0,&\text{ if }x=0.
  \end{cases}
\end{equation*}
So let
\begin{equation*}
  b=a^*=(a_0{}^*,a_1{}^*,\dots).
\end{equation*}
Then $ab$ and $1-ab$ are in $\in\{0,1\}^{\upomega}$.
We want to show $1-ab\in I$.
That is, we want to show that, for some $k$,
if $n\in\N$ and $k\leq n$, then $a_n\neq0$.

The desired conclusion holds because $a$ is Cauchy, 
but does not converge to $0$.
To be precise,
for some positive $\epsilon$,
for all $k$, for some $n$ in $\N$, 
we have $k\leq n$, but $\abs{a_n}\geq\epsilon$;
but also, for some $k$, for all $m$ and $n$ in $\N$, 
if $k\leq m$ and $k\leq n$,
then $\abs{a_n-a_m}<\epsilon/2$.
We may assume $\abs{a_n}\geq\epsilon$, and so
\begin{equation*}
  \frac{\epsilon}2\leq\abs{a_n}-\frac{\epsilon}2<\abs{a_m};
\end{equation*}
in particular, $a_m\neq0$.
\end{proof}

\begin{theorem}
{}[In the notation above,]
  the function $x+I\mapsto\lim(x)$ 
is a well-defined bijection from $R/I$ to $\R$, 
and it preserves addition and multiplication:
it is an isomorphism of fields.
\end{theorem}

\begin{proof}
  \textsc{Exercise.}
\end{proof}

Now let $K$ be a non-Archimedean ordered field,
so it has infinite elements.  Let
\begin{gather*}
  R=\{\text{finite elements of $K$}\},\\
\begin{aligned}
I&=\{\text{infinitesimal elements of $K$}\}\\
&=\{x\inv\colon x\in K\setminus R\}\cup\{0\}.
\end{aligned}
\end{gather*}
Then $R$ is a \textbf{valuation ring} of $K$,
because
\begin{align*}
  \Forall x(x\in K\setminus R\implies x\inv\in R).
\end{align*}
Let
\begin{equation*}
  R\units=\{x\in R\setminus\{0\}\colon x\inv\in R\},
\end{equation*}
the \textbf{group of units} of $R$.  Then
\begin{equation*}
  I=R\setminus R\units.
\end{equation*}
We asserted on page \pageref{ideal} that $I$ is an ideal;
but this follows,
simply because $R$ is a valuation ring of $K$.
Indeed, suppose $x,y\in I$.  
Either $x/y$ or $y/x$ is a well-defined element of $R$;
assume $y/x\in R$.  Then $1+y/x\in R$, that is,
\begin{equation*}
  \frac{x+y}x\in R.
\end{equation*}
Since $x\inv\notin R$, also $1/(x+y)\notin R$, so $x+y\in I$.
Similarly, if $x\in I$ and $y\in R$, then $xy\in I$ (\textsc{exercise}).

So $I$ is an ideal; 
automatically it is a maximal ideal,
as we showed on page \pageref{ideal-max}:
if $a\in R\setminus I$, then $a\inv\in R$,
so every ideal containing $a$ contains $1$.

For another example, let $K=\Q(X)$ and
\begin{gather*}
  R=\{f\in K\colon f(0)\text{ is defined}\},\\
I=\{f\in K\colon f(0)=0\}.
\end{gather*}
Then $R$ is a valuation ring of $K$ with maximal ideal $I$.

We want to let $K=\R^{\upomega}/M$,
where $M$ is a maximal ideal of $R^{\upomega}$.
We know that $M$ is determined by a maximal ideal of the Boolean ring
$(\pow{\upomega},0,\upomega,\symdiff,\cap)$.

\begin{theorem}\label{thm:omega-id}
  A subset $I$ of $\pow{\upomega}$ is an ideal
if and only if
\begin{gather*}
  X,Y\in I\implies X\cup Y\in I,\\
Y\in I\And X\included Y\implies X\in I,\\
\emptyset\in I.
\end{gather*}
\end{theorem}

\begin{proof}
\textsc{Exercise:}
an adaptation of the definition \eqref{eqn:ideal} 
of ideals on page \pageref{eqn:ideal}.
\end{proof}

For example, $\pow{\upomega}$ has (at least) two kinds of ideals:
\begin{itemize}
\item 
 $\{\text{finite subsets of $\upomega$}\}$, and
\item
$\pow A$, if $A\included\upomega$.
\end{itemize}

\subsection{Friday}

We want to understand the ideals of $\pow{\upomega}$,
and more generally of $\pow{\Omega}$ for arbitrary sets $\Omega$.
We have the characterization of ideals of $\pow{\upomega}$ 
in Theorem \ref{thm:omega-id};
it still holds when $\upomega$ is replaced by $\Omega$.
If $A\included\pow{\Omega}$,
then the ideal $\pow A$ of $\pow{\Omega}$ 
is called a \textbf{principal ideal.}
If $\Omega$ is infinite,
then the set of finite subsets of $\pow{\Omega}$,
which we can denote by
\begin{equation*}
  \powf{\Omega},
\end{equation*}
is a \textbf{nonprincipal ideal,}
because there is no subset $A$ of $\Omega$ such that $\powf{\Omega}=\pow A$.

However, if $\Omega$ is finite,
then all ideals of $\pow{\Omega}$ are principal.
Consider for example the case where $\Omega$ is $3$,
where $3=\{0,1,2\}$, as in Figure \ref{fig:3}:
\begin{figure}
  \begin{equation*}
    \xymatrix{&\{0,1,2\}&\\
\{0,1\}\ar@{-}[ur]&\{0,2\}\ar@{-}[u]&\{1,2\}\ar@{-}[ul]\\
\{0\}\ar@{-}[u]\ar@{-}[ur]&\{1\}\ar@{-}[ul]\ar@{-}[ur]&\{2\}\ar@{-}[ul]\ar@{-}[u]\\
&\emptyset\ar@{-}[ul]\ar@{-}[u]\ar@{-}[ur]}
  \end{equation*}
  \caption{The elements of $\pow3$}\label{fig:3}
  
\end{figure}
every ideal consists of an element and the elements below it in the diagram.

\begin{theorem}
  Suppose $I$ is an ideal of $\pow{\Omega}$ and $A\included\Omega$.
The smallest ideal of $\pow{\Omega}$ that includes $I$ and contains $A$
is
\begin{equation}\label{eqn:IA}
  \{X\cup Y\colon X\in I\And Y\included A\}.
\end{equation}
\end{theorem}

\begin{proof}
  If $X_0,X_1\in I$ and $Y_0,Y_1\included A$, then
  \begin{gather*}
    (X_0\cup Y_0)\cup(X_1\cup Y_1)=(X_0\cup X_1)\cup(Y_0\cup Y_1),\\
X_0\cup X_1\in I,\qquad\qquad Y_0\cup Y_1\included A.
  \end{gather*}
Thus the set indicated in \eqref{eqn:IA} is closed under $\cup$.

If $X\in I$ and $Y\included A$ and $Z\included X\cup Y$,
then
\begin{gather*}
    Z=Z\cap(X\cup Y)=(Z\cap X)\cup(Z\cap Y),\\
Z\cap X\in I,\qquad\qquad Z\cap Y\included A.
\end{gather*}
Thus the indicated set is closed under taking subsets.

Obviously the indicated set is included in every ideal of $\pow{\Omega}$
that includes $I$ and contains $A$.
\end{proof}

Denote the new ideal in the theorem by
\begin{equation*}
  I+(A).
\end{equation*}
If this is $\pow{\Omega}$, then it contains $\Omega$,
so for some $X$ in $I$ and $Y$ in $\pow A$,
\begin{gather*}
  \Omega=X\cup Y,\\
X\includes\Omega\setminus Y\includes\Omega\setminus A,\\
\Omega\setminus A\in I.
\end{gather*}
From this we obtain:

\begin{theorem}
  Let $I$ be a proper ideal of $\pow{\Omega}$.
Then $I$ is a maximal ideal if and only if,
for all $X$ in $\pow{\Omega}$,
\begin{equation}\label{eqn:max}
  X\notin I\implies\Omega\setminus X\in I.
\end{equation}
\end{theorem}

\begin{proof}
  If $I$ is maximal, then for all $A$ in $\pow{\Omega}\setminus I$,
we have $I+(A)=\pow{\Omega}$, so $\Omega\setminus A\in I$, as above.

Suppose conversely \eqref{eqn:max} holds.
If $A\in\pow{\Omega}\setminus I$, then $\Omega\setminus A\in I$,
so $I+(A)$ contains both $A$ and $\Omega\setminus A$ and therefore $\Omega$.
\end{proof}

\emph{Principal} maximal ideals of $\pow{\upomega}$ exist,
namely $\pow{\upomega\setminus\{k\}}$.
Do nonprincipal maximal ideals exist?
They will, by the Maximal Ideal Theorem
(Theorem \ref{thm:mith}) below.

A subset $\mathscr C$ of $\pow{\Omega}$ is a \textbf{chain}
if it is linearly ordered by $\pincluded$, that is,
for all $X$ and $Y$ in $\mathscr C$,
\begin{equation*}
  X\included Y\Or Y\included X.
\end{equation*}

In the following, note well that
\begin{equation*}
  \bigcup\mathscr C
=\bigcup_{Y\in\mathscr C}Y
=\{x\colon\Exists Y(Y\in\mathscr C\And x\in Y)\}.
\end{equation*}

\begin{theorem}[Zorn's Lemma]\label{thm:zorn}
Let $\mathscr A\included\pow{\Omega}$.
Suppose that, 
for every subset $\mathscr C$ of $\mathscr A$ that is a chain, 
$\bigcup\mathscr C\in\mathscr A$.
Then $\mathscr A$ has a maximal element $X$
(so that, for all $Y$ in $A$, if $X\included Y$, then $X=Y$).
\end{theorem}

Actually we shall treat Zorn's Lemma as an \emph{axiom.}
It is equivalent to the \emph{Axiom of Choice} (see page \pageref{to-do}).

\begin{theorem}
  The union of a nonempty chain $\mathscr C$ of proper ideals of a ring $R$
is a proper ideal.
\end{theorem}

\begin{proof}
  If $x,y\in\bigcup\mathscr C$, 
then for some $I$ and $J$ in $\mathscr C$,
$x\in I$ and $y\in J$.  We may assume $I\included J$.
Then $x\in J$, so $x+y\in J$, and hence $x+y\in\bigcup\mathscr C$.

Similarly if $x\in\bigcup\mathscr C$ and $y\in R$, 
then $xy\in\bigcup\mathscr C$.
So $\bigcup\mathscr C$ is an ideal.

If $\bigcup\mathscr C$ is the improper ideal,
then $1\in\bigcup\mathscr C$, 
so for some $I$ in $\mathscr C$, $1\in I$;
but $I$ is proper, so $1\notin I$.
\end{proof}

\begin{theorem}[Maximal Ideal Theorem]\label{thm:mith}
  Every proper ideal $I$ of a ring $R$
is included in a maximal ideal of $R$.
\end{theorem}

\begin{proof}
  This maximal ideal is a maximal element 
of the set of proper ideals of $R$ that include $I$; 
it exists, by Zorn's Lemma and the last theorem.
\end{proof}

In particular,
there is a maximal ideal $\mathfrak m$ of $\pow{\upomega}$ 
that includes the ideal $\powf{\upomega}$.
Let
\begin{equation*}
  M=\{x\in\R^{\upomega}\colon\supp x\in\mathfrak m\},
\end{equation*}
where
\begin{equation*}
  \supp x=\{k\in\upomega\colon x_k\neq0\}.
\end{equation*}
As noted on page \pageref{corr}, $M$ is an ideal,
indeed a maximal ideal, of $\R^{\upomega}$.
Then $\R^{\upomega}/M$ consists of the elements $a+M$, where $a\in\R^{\upomega}$;
and
\begin{align*}
  a+M=b+M
&\iff a-b\in M\\
&\iff\supp{a-b}\in\mathfrak m\\
&\iff\{k\in\upomega\colon a_k\neq b_k\}\in\mathfrak m.
\end{align*}
Let us refer to elements of $\mathfrak m$ as \textbf{small,}
and to elements of $\pow{\upomega}\setminus\mathfrak m$ as \textbf{large.}
Then:
\begin{itemize}
\item 
the union of two small sets is small;
\item
a subset of a small set is small;
\item
the complement of a small set is large.
\end{itemize}
Note that, by this definition, all finite sets are small,
although some infinite sets will be small as well.
The definition is a kind of resolution of the \textbf{Sorites Paradox,}
or Paradox of the Heap,
attributed to Eubulides of Miletus, 4th century \textsc{bce.}
If from a heap of sand, one grain is removed,
still a heap of sand remains;
but all of the grains in the heap can be removed one by one,
so that, paradoxically, even one grain can constitute a heap.

A heap is a \emph{large} pile of sand,
and one grain is a \emph{small} pile;
but these are only relative terms, 
rather in the sense of page \pageref{rel}.
Elements of $\mathfrak m$ are \emph{absolutely} small;
of $\pow{\upomega}\setminus\mathfrak m$, absolutely large.

That $\R^{\upomega}/M$ is a field
follows from basic ring theory:
the quotient of a ring by a maximal ideal is a field.
We want $\R^{\upomega}/M$ to be an ordered field in which $\R$ embeds.
The embedding will be $x\mapsto(x,x,x,\dots)+M$;
this map is indeed injective, 
since $(x,x,x,\dots)$ is just $(x\colon k\in\upomega)$, and
\begin{align*}
  (x\colon k\in\upomega)+M=(y\colon k\in\upomega)+M
&\iff\{k\in\upomega\colon x\neq y\}\in\mathfrak m\\
&\iff x=y.
\end{align*}
We define the ordering by
\begin{equation*}
  a+M<b+M\iff\{k\in\upomega\colon a_k\geq b_k\}\in\mathfrak m.
\end{equation*}
This is a valid definition, 
because if $a+M=a'+M$ and $b+M=b'+M$,
then
\begin{multline*}
  \{k\in\upomega\colon a'_k\geq b'_k\}\\
\included  \{k\in\upomega\colon a_k\geq b_k\}
\cup  \{k\in\upomega\colon a'_k\neq a_k\}
\cup  \{k\in\upomega\colon b'_k\neq b_k\},
\end{multline*}
so if $\{k\in\upomega\colon a_k\geq b_k\}$ is small,
then so is $\{k\in\upomega\colon a'_k\geq b'_k\}$,
and conversely by symmetry.

Similarly all of the axioms of ordered fields hold in $\R^{\upomega}/M$,
as we shall show generally tomorrow.
Meanwhile, note that $(1,2,3,\dots)+M$
is an infinite element of $\R^{\upomega}/M$,
and so $(1,1/2,1/3,\dots)+M$ is an infinitesimal element.
Of the elements
\begin{align*}
  (0,1,0,1,0,1,\dots)&+M,&
  (1,0,1,0,1,0,\dots)&+M.
\end{align*}
Which one is greater?
We don't know.
Either the set of odd numbers 
or the set of even numbers
is in $\mathfrak m$.
If $\{\text{odd numbers}\}\in\mathfrak m$, then
\begin{align*}
  (0,1,0,1,\dots)+M
&=(0,0,0,0,\dots)+M\\
&<(1,1,1,1,\dots)+M\\
&=(1,0,1,0,\dots)+M.
\end{align*}

\subsection{Saturday}

We want to understand $\R^{\upomega}/M$,
where $M$ is a maximal ideal of the ring $\R^{\upomega}$.
This is a special case of
\begin{equation*}
  \left.\prod_{i\in\Omega}K_i\right/M,
\end{equation*}
where $\Omega$ is an arbitrary set, and each $K_i$ is a field,
so $\prod_{i\in\Omega}K_i$ is the ring consisting of $(a_i\colon i\in\Omega)$,
where $a_i\in K_i$; and $M$ is a maximal ideal of this ring.

For example, $\Omega$ could be the set of primes,
and if $p\in\Omega$, $K_p$ could be $\F_p$, that is, $\Z/p\Z$.
If $\ell\in\Omega$, let $\ell=0$ be the equation
\begin{equation*}
  \underbrace{1+\dots+1}_{\ell}=0.
\end{equation*}
This is true in $\F_p$ if and only if $p=\ell$.
Then
\begin{equation*}
  \{p\in\Omega\colon\ell=0\text{ in }\F_p\}=\{\ell\}.
\end{equation*}
Let
\begin{equation*}
  \mathfrak m=\{\supp x\colon x\in M\}.
\end{equation*}
Assume $\powf{\Omega}\included\mathfrak m$; then $\{\ell\}\in\mathfrak m$,
so $\ell=0$ is not true in $\prod_{p\in\Omega}\F_p$.
In particular, this field has characteristic $0$.
But it is a kind of ``average'' of the fields $\F_p$,
each of which has characteristic $p$.
It is an example of a \textbf{pseudofinite field.}

In general, let
\begin{align*}
    \mathscr K&=(K_i\colon i\in\Omega),&
\prod\mathscr K&=\prod_{i\in\Omega}K_i.
\end{align*}
There are homomorphisms
\begin{itemize}
\item 
$x\mapsto x+M$ from $\prod\mathscr K$ to $\prod\mathscr K/M$,
\item
$x\mapsto x_i$ from $\prod\mathscr K$ to $K_i$ for each $i$ in $\Omega$.
\end{itemize}
If $a\in\prod\mathscr K$,
we let the \textbf{interpretation} of $a$ in $\prod\mathscr K/M$ be $a+M$;
in $K_i$, $a_i$.
Then a polynomial equation $f=g$ 
with \textbf{parameters} from $\prod\mathscr K$
has a meaning in $\prod\mathscr K/M$ and in each $K_i$.
For example, $f=g$ could be
\begin{equation*}
  ab^2+5c=a^3c-6d^4
\end{equation*}
for some $a$, $b$, $c$, and $d$ in $\prod\mathscr K$.
\textbf{Truth} is denoted by $\models$.  Then
\begin{equation*}
  \prod\mathscr K/M\models f=g
\iff\{i\in\Omega\colon K_i\models f\neq g\}\in\mathfrak m,
\end{equation*}
where again $\mathfrak m=\{\supp x\colon x\in M\}$.
We can understand the equation $f=g$ as $\phi(a^0,\dots,a^{n-1})$
for some polynomial equation $\phi(x^0,\dots,x^{n-1})$
in no parameters, in the signature $\{0,1,-,+,\times\}$ of rings.
(The superscripts are not exponents, but indices.)
In the example above, $\phi$ is
\begin{equation*}
  x^0(x^1)^2+5x^2=(x^0)^3x^2-6(x^3)^4.
\end{equation*}
In general, $\phi$ is an \textbf{atomic formula.}
Other \textbf{formulas} are obtained from these
by use of $\land$ (and), $\lnot$ (not), and $\Exists x$ (there exists $x$).
A \textbf{sentence}\label{sentence} 
is a formula with no \textbf{free variables.}
In the formula
\begin{equation*}
  \Forall x(0<\abs{x-a}<\delta\lto\abs{f(x)-L}<\epsilon),
\end{equation*}
\begin{itemize}
\item
$x$ is a bound variable (not free),
\item
$a$ and $L$ are parameters,
\item
$\delta$ and $\epsilon$ are free variables,
\item
$<$, $\abs{{}\cdot{}}$, and $f$ 
are from a larger signature than that of plain rings.
\end{itemize}
A formula
$\sigma\lto\tau$ is an abbreviation for $\lnot\sigma\lor\tau$;
and $\sigma\lor\tau$, for $\lnot(\lnot\sigma\land\lnot\tau)$.

For any ring $R$ and sentences $\sigma$ and $\tau$,
\begin{align*}
  R\models\lnot\sigma&\iff R\nmodels\sigma,\\
R\models\sigma\land\tau&\iff R\models\sigma\And R\models\tau,\\
R\models\Exists x\phi(x)&\iff\text{ for some $a$ in $R$, }R\models\phi(a).
\end{align*}
Here $\iff$ and $\And$ are abbreviations 
for the English expressions ``if and only if'' and ``and'' respectively;
and $R\nmodels\sigma$ means $\sigma$ is not true in $R$.

Given a sentence $\sigma$ with parameters from $\prod\mathscr K$,
let
\begin{equation*}
  \bv{\sigma}=\{i\in\Omega\colon K_i\models\sigma\}.
\end{equation*}
Following Wilfrid Hodges in his \emph{Model Theory} \cite{MR94e:03002},
we may call $\bv{\sigma}$ the \textbf{Boolean value} of $\sigma$.
Then
\begin{gather*}
  \bv{\sigma\land\tau}=\bv{\sigma}\cap\bv{\tau},\\
\bv{\lnot\sigma}=\Omega\setminus\bv{\sigma},\\
 \bv{\sigma\lor\tau}=\bv{\sigma}\cup\bv{\tau}.
\end{gather*}
Because $\mathfrak m$ is an ideal,
\begin{equation}\label{eqn:or}
  \bv{\sigma\lor\tau}\in\mathfrak m
\iff\bv{\sigma}\in\mathfrak m\And\bv{\tau}\in\mathfrak m.
\end{equation}
Because $\mathfrak m$ is a \emph{maximal} ideal,
\begin{gather}\label{eqn:not}
  \bv{\sigma}\notin\mathfrak m\iff\bv{\lnot\sigma}\in\mathfrak m,\\
\label{eqn:and}
  \bv{\sigma\land\tau}\in\mathfrak m
\iff\bv{\sigma}\in\mathfrak m\Or\bv{\tau}\in\mathfrak m.
\end{gather}
Why?
Recall that
\begin{gather}
  \mathfrak m\included\pow{\Omega},\\
\label{eqn:cup}
X,Y\in\mathfrak m\iff X\cup Y\in\mathfrak m,\\
\label{eqn:inc}
Y\in\mathfrak m\And X\included Y\implies X\in\mathfrak m,\\
\label{eqn:comp}
X\notin\mathfrak m\iff\Omega\setminus X\in\mathfrak m.
\end{gather}
But \eqref{eqn:inc} follows from the other three conditions.
We have that \eqref{eqn:or} follows from \eqref{eqn:cup},
and \eqref{eqn:not} from \eqref{eqn:comp}.
Finally,
\eqref{eqn:and} follows from \eqref{eqn:or} and \eqref{eqn:not},
because
\begin{align*}
  \bv{\sigma\land\tau}\in\mathfrak m
&\iff\bv{\lnot\sigma\lor\lnot\tau}\notin\mathfrak m
&&\text{[by \eqref{eqn:not}]}\\
&\iff\bv{\lnot\sigma}\notin\mathfrak m\Or\bv{\lnot\sigma}\notin\mathfrak m
&&\text{[by \eqref{eqn:or}]}\\
&\iff\bv{\sigma}\in\mathfrak m\Or\bv{\tau}\in\mathfrak m.
&&\text{[by \eqref{eqn:not}]}
\end{align*}

Note that \eqref{eqn:and} means $\mathfrak m$ is a \emph{prime ideal.}
In general, a \emph{proper} ideal $I$ of a ring $R$ is a \textbf{prime ideal}
if
\begin{equation*}
  xy\in I\iff x\in I\Or y\in I.
\end{equation*}
The improper ideal is not counted as prime,
just as $1$ is not counted as a prime number.
In $\Z$, the prime ideals are $(p)$ and $(0)$;
the ideals $(p)$ are also maximal ideals, but $(0)$ is not, since
\begin{equation*}
  (0)\pincluded(p)\pincluded\Z.
\end{equation*}

In every ring, all maximal ideals are prime.
Indeed, if $I$ is a maximal ideal of $R$,
then $R/I$ is a field,
hence an \textbf{integral domain:}
this means
\begin{equation*}
 xy=0\implies x=0\Or y=0,
\end{equation*}
which in the present context means
\begin{equation*}
  xy+I=I\implies x+I=I\Or y+I=I,
\end{equation*}
that is, $xy\in I\implies x\in I\Or y\in I$.
The following then is a corollary of the Maximal Ideal Theorem:

\begin{theorem}[Prime Ideal Theorem]\label{thm:pith}
  Every proper ideal of a ring
is included in a prime ideal of the ring.
\end{theorem}

A reason for stating this result separately is that
it is strictly weaker than the Maximal Ideal Theorem:
see page \pageref{to-do}.
However, the two theorems are equivalent for
\emph{Boolean} rings, 
where all prime ideals are maximal \textsc{(Exercise)}.

The following is a special case of \emph{\L o\'s's Theorem:}

\begin{theorem}
If $\mathscr K$ is an indexed family $(K_i\colon i\in\Omega)$ of fields,
and $M$ is a maximal ideal of $\prod\mathscr K$,
then
for all sentences $\sigma$ with parameters from $\prod\mathscr K$,
\begin{equation}\label{eqn:Los}
  \prod\mathscr K/M\models\sigma\iff\bv{\sigma}\notin\mathfrak m.
\end{equation}
\end{theorem}

\begin{proof}
  We know this is true when $\sigma$ is atomic.
Suppose it is true when $\sigma$ is $\rho$ or $\tau$.
Then
\begin{align*}
  \prod\mathscr K/M\models\lnot\rho
&\iff\prod\mathscr K/M\nmodels\rho\\
&\iff\bv{\rho}\in\mathfrak m\\
&\iff\bv{\lnot\rho}\notin\mathfrak m,
\end{align*}
and similarly
\begin{align*}
  \prod\mathscr K/M\models\rho\land\tau
&\iff\prod\mathscr K/M\models\rho\And\prod\mathscr K/M\models\tau\\
&\iff\bv{\rho}\notin\mathfrak m\And\bv{\tau}\notin\mathfrak m\\
&\iff\bv{\rho\land\tau}\notin\mathfrak m.
\end{align*}
Finally, suppose for some formula $\phi(x)$,
for all $a$ in $\prod\mathscr K$, 
\eqref{eqn:Los} holds when $\sigma$ is $\phi(a)$.
Let $a$ be $(a_i\colon i\in\Omega)$ in $\prod\mathscr K$ such that,
for all $i$ in $\Omega$, if $K_i\models\Exists x\phi(x)$,
then $K_i\models a_i$.
Then
\begin{align*}
  \bv{\Exists x\phi(x)}
&=\{i\in\Omega\colon K_i\models\Exists x\phi(x)\}\\
&=\{i\in\Omega\colon K_i\models\phi(a_i)\}\\
&=\{i\in\Omega\colon K_i\models\phi(a)\}\\
&=\bv{\phi(a)}.
\end{align*}
Moreover, for all $b$ in $\prod\mathscr K$,
\begin{equation*}
  \bv{\phi(b)}\included\bv{\phi(a)}.
\end{equation*}
Hence
\begin{align*}
  \prod\mathscr K/M\models\Exists x\phi(x)
&\iff\text{ for some $b$ in $\prod\mathscr K$, }
\prod\mathscr K/M\models\phi(b)\\
&\iff\text{ for some $b$ in $\prod\mathscr K$, }
\bv{\phi(b)}\notin\mathfrak m\\
&\iff\bv{\phi(a)}\notin\mathfrak m\\
&\iff\bv{\Exists x\phi(x)}\notin\mathfrak m.\qedhere
\end{align*}
\end{proof}

In the proof,
we use the Axiom of Choice to find $a$;
see the final lecture (page \pageref{final}).
The whole proof uses pure logic:
nothing of ring theory (except for the algebra of $\pow{\Omega}$).
The fields $K_i$ could be replaced by groups,
linear orders, ordered fields, or something else.
Then we get \emph{\L o\'s's Theorem,}
namely Theorem \ref{thm:los}.

In case each $K_i$ is $\R$,
and the parameters of $\sigma$ are from $\R$ only, not $\R^{\omega}$,
we get $\bv{\sigma}\in\{\emptyset,\Omega\}$, so
\begin{equation*}
  \R^{\Omega}/M\models\sigma\iff\R\models\sigma.
\end{equation*}
We used this to prove Theorem \ref{thm:cong} (page \pageref{thm:cong}).

\subsection{Sunday}

We have proved:

\begin{los}\label{thm:los}
  For every indexed family $(\str A_i\colon i\in\Omega)$ 
of \emph{structures} having a common \emph{signature} $\sig$,
for every maximal ideal $\mathfrak m$ of $\pow{\Omega}$,
there is a structure $\str B$ of $\sig$ such that,
for all sentences $\sigma$ of $\sig$,
if
\begin{equation*}
  \bv{\sigma}=\{i\in\Omega\colon\str A\models\sigma\},
\end{equation*}
then
\begin{equation*}
  \str B\models\sigma\iff\bv{\sigma}\notin\mathfrak m.
\end{equation*}
(This much is the \textbf{Compactness Theorem};
again, see the final lecture, page \pageref{final}.)
The universe of $\str B$ can be taken as $\prod_{i\in\Omega}A_i/\mathord{\sim}$,
where
\begin{equation*}
  a\sim b\iff\{i\in\Omega\colon a_i\neq b_i\}\in\mathfrak m.
\end{equation*}
\end{los}

Here a \textbf{structure} $\str A$ is a set $A$, 
called the \textbf{universe} of $\str A$,
together with some operations and relations on $A$,
that is, functions from $A^n$ to $A$ and subsets of $A^n$
for various $n$ in $\upomega$.
The \textbf{signature} of the structure
consists of a symbol for each of the operations and relations.
For example,
\begin{itemize}
\item 
$\str G=(G,0,-,+)$, an abelian group;
\item
$\str R=(R,0,1,-,+,\times)$, a ring;
\item
$\str L=(L,<)$, a linear order.
\end{itemize}

Note that $A^0=\{\emptyset\}=\{0\}=1$.
Hence a \textbf{nullary} operation on $A$,
that is, a function from $A^0$ to $A$,
is determined by an element of $a$.
In \L o\'s's Theorem, let
\begin{equation*}
  A=\prod_{i\in\Omega}A_i.
\end{equation*}
Then each $\str A_i$ can be considered as a structure of $\sig(A)$,
the elements of $A$ being treated as constants,
$a$ being interpreted in $\str A_i$ as $a_i$.

We are interested in \L o\'s's Theorem
when
\begin{itemize}
\item 
$\Omega$ is $\upomega$,
\item
$\mathfrak m$ is a nonprincipal maximal ideal of $\pow{\upomega}$,
that is, $\powf{\upomega}\included\mathfrak m$,
and 
\item
each $\str A_i$ is $\R$ with its full structure,
that is, there is a symbol for \emph{every} operation and relation on $\R$.
\end{itemize}
Let
\begin{equation*}
  \stR=\R^{\upomega}/M,
\end{equation*}
where $M=\{x\in\R^{\upomega}\colon\supp x\in\mathfrak m\}$.
We treat the embedding $x\mapsto(x,x,x,\dots)+M$ of $\R$ in $\stR$
as an inclusion.
If $f\colon\R\to\R$, then,
as a symbol, $f$ is interpreted in $\stR$ 
as a function $\stf$ from $\stR$ to $\stR$ given by
\begin{equation*}
  \stf(a+M)=(f(a_k)\colon k\in\upomega)+M,
\end{equation*}
as in Figure \ref{fig:*f}.
\begin{figure}
\begin{equation*}
  \begin{array}{cccccc}
      a+M&=&(  a_0 ,&  a_1 ,&  a_2, &\dots)+M\\
\downarrow&&        &       &      &        \\
\stf(a+M)&=&(f(a_0),&f(a_1),&f(a_2),&\dots)+M
  \end{array}
\end{equation*}
  
  \caption{Extension of a function}\label{fig:*f}
  
\end{figure}
Then $\stf$ can be called the \textbf{extension} of $f$.
One must show that $\stf$ is well defined
(or take this as a consequence of \L o\'s's Theorem).
Likewise,
\begin{equation*}
  \stN=\{x+M\colon x\in\N^{\upomega}\}.
\end{equation*}

\begin{theorem}
  $\N$ consists of the finite elements of $\stN$.
\end{theorem}

\begin{proof}
  By definition, the elements of $\N$ are finite.
Suppose $n$ is a finite element of $\stN$.
Then the set $\{x\in\N\colon n<x+1\}$ is nonempty,
so it has a least element, $m$.
Then
\begin{equation*}
  m\leq n<m+1,
\end{equation*}
unless $n<1$; but this cannot happen since
\begin{equation*}
  \R\models\Forall x(x\in\N\implies 1\leq x),
\end{equation*}
so
\begin{equation*}
  \stR\models\Forall x(x\in\stN\implies 1\leq x).
\end{equation*}
Likewise, since
\begin{equation*}
  \R\models\Forall x(x\in\N\And m\leq x<m+1\implies m=x),
\end{equation*}
we have also
\begin{equation*}
  \stR\models\Forall x(x\in\stN\And m\leq x<m+1\implies m=x),
\end{equation*}
and therefore $m=n$, so $n\in\N$.
\end{proof}

See Figure \ref{fig:N}.
\begin{figure}
\psset{unit=7mm}
  \begin{pspicture}(-1,-1)(13,0)
    \psline{<->}(-1,0)(13,0)
\psdots(0,0)(4,0)(6,0)(7,0)(7.5,0)(7.75,0)(7.875,0)(10,0)
\psdots[dotstyle=o](8,0)
\uput[d](0,0){$1$}
\uput[d](4,0){$2$}
\uput[d](6,0){$3$}
%\uput[d](7,0){$4$}
\uput[d](7,0){$\cdots$}
%\uput[d](7.5,0){$5$}
%\uput[d](7.5,0){$\cdots$}
%\uput[d](7.75,0){$6$}
\uput[d](10,0){$(1,2,3,\dots)+M$}
  \end{pspicture}
  \caption{Non-standard natural numbers}\label{fig:N}
  
\end{figure}
In proving the theorem,
we use that $\N$ is \textbf{well ordered,}
that is, every nonempty subset has a least element.
Is $\stN$ well ordered?
No: $\stN\setminus\N$ has no least element,
since if $n$ is infinite, so is $n-1$.

By \L o\'s's Theorem, we have (and have used)
\begin{equation}\label{eqn:prec}
  \R\preccurlyeq\stR;
\end{equation}
this means all \textbf{first-order} sentences 
that are true in $\R$ are true in $\stR$.
first-order sentences
are the kinds of sentences defined on page \pageref{sentence}.
In a first-order sentence, variables refer to individuals, not subsets.

If $a\colon\N\to\R$, that is, $a\in\R^{\N}$, or
\begin{equation*}
  a=(a_k\colon k\in\N),
\end{equation*}
then we obtain $\sta$ from $\stN$ to $\stR$, that is,
\begin{equation*}
  \sta=(a_k\colon k\in\stN).
\end{equation*}
This is the extension of $a$, as $\stf$ is the extension of $f$,
and $\stN$ of $\N$.
If $k=(k(i)\colon i\in\upomega)+M$, then
\begin{equation*}
  a_k=(a_{k(i)}\colon i\in\upomega)+M.
\end{equation*}
The sequence $a$ is \textbf{bounded} 
if
\begin{equation}\label{eqn:bdd}
  \Exists R\Forall n(n\in\N\implies\abs{a_n}\leq R);
\end{equation}
this applies to $\sta$ if we replace $\N$ with $\stN$.
Then what condition on $\sta$ is equivalent to boundedness of $a$?

\begin{theorem}
  A sequence $a$ in $\R^{\N}$ is bounded if and only if
every element of $\sta$ is finite.
\end{theorem}

\begin{proof}
  If $a$ is bounded, 
then for some $S$ in $\R$,
\begin{gather*}
  \R\models\Forall n(n\in\N\implies\abs{a_n}\leq S),\\
  \stR\models\Forall n(n\in\stN\implies\abs{a_n}\leq S),
\end{gather*}
so $\sta$ has no infinite elements (since $S$ is finite).

If $a$ is not bounded, then
\begin{gather*}
  \R\models\Forall S\Exists n(n\in\N\And\abs{a_n}>S),\\
  \stR\models\Forall S\Exists n(n\in\stN\And\abs{a_n}>S).
\end{gather*}
Letting $S$ be positive and infinite,
we obtain that $a_n$ is infinite for some $n$ in $\stN$.
\end{proof}

Note how we had to manipulate the quantifiers.
The \emph{standard} definition of boundedness of a sequence
is first order;
it is the condition in \eqref{eqn:bdd}.
The theorem shows that this condition
is equivalent to a \emph{non-standard} definition that,
as such, is not expressed in a first-order way.

The same is true of Theorem \ref{thm:cong} (page \pageref{thm:cong}).
By analogy with limits of functions, we have the following;
the proof is an \textsc{exercise.}

\begin{theorem}\label{thm:a_n}
  $\lim_{n\to\infty}a_n=L$ if and only if, for all infinite $n$, $a_n\icl L$.
\end{theorem}

A \emph{filter} of a Boolean ring $\pow{\Omega}$ 
is ``dual'' to an ideal of the ring.
By ``dualizing'' the conditions in Theorem \ref{thm:omega-id} 
(page \pageref{thm:omega-id}),
we say that a subset $F$ of $\pow{\Omega}$ 
is a \textbf{filter of} $\pow{\Omega}$,
or a \textbf{filter on} $\Omega$, if 
\begin{gather*}
  X,Y\in F\implies X\cap Y\in F,\\
X\in F\And X\included Y\included\Omega\implies Y\in F,\\
\Omega\in F.
\end{gather*}
Then $\{\Omega\setminus X\colon X\in F\}$ is an ideal,
namely the \textbf{dual ideal} of the filter.
A maximal proper filter is called an \textbf{ultrafilter;}
its dual ideal is also its complement and is a maximal ideal.

In \L o\'s's Theorem,
if $\mathscr U=\pow{\Omega}\setminus\mathfrak m$,
then the structure $\str B$ is denoted by
\begin{equation*}
  \left.\prod_{i\in\Omega}\str A_i\right/\mathscr U
\end{equation*}
(or $\prod_{\mathscr U}\str A_i$ or some such)
and is called the \textbf{ultraproduct} of the structures $\str A_i$.

\section{Second week}

\subsection{Monday}

Recall that
\textbf{infinite} means greater than all $n$ in $\N$,
where
\begin{equation*}
\N=\{1,2,3,\dots\};
\end{equation*}
\textbf{infinitesimal} 
means less in absolute value than $1/n$ for all $n$ in $\N$;
$a_n\icl L$ means $a_n-L$ is infinitesimal.
$\mathscr U$ is an \textbf{ultrafilter} on $\upomega$
(which is $\{0,1,2,\dots\}$); 
this means $\mathscr U\included\pow{\upomega}$ and,
for all $X$ and $Y$ in $\pow{\upomega}$,
\begin{gather*}
  X,Y\in\mathscr U\iff X\cap Y\in\mathscr U,\\
X\in\mathscr U\iff\upomega\setminus X\notin\mathscr U.
\end{gather*}
Indeed, these conditions imply
\begin{equation*}
  X\in\mathscr U\And X\included Y\included\upomega\implies Y\in\mathscr U,
\end{equation*}
since if $X\included Y$, then $X\cap Y=X$.
We define an equivalence relation on $\R^{\upomega}$ so that,
if $a/\mathscr U$ is the equivalence class of an element $a$,
that is, $(a_k\colon k\in\upomega)$, of $\R^{\upomega}$, then
\begin{equation*}
  a/\mathscr U=b/\mathscr U\iff\{k\in\upomega\colon a_k=b_k\}\in\mathscr U.
\end{equation*}
The elements of $\mathscr U$ are \textbf{large.}
Similarly we obtain $\stN$.
If $a\in\R^{\N}$, we obtain $\sta$,
namely $(a_n\colon n\in\stN)$, where
\begin{equation*}
  a_n=
  \begin{cases}
    a_n,&\text{ if }n\in\N,\\
(a_{n_k}\colon k\in\upomega)/\mathscr U,
&\text{ if }n=(n_k\colon k\in\upomega)/\mathscr U.
  \end{cases}
\end{equation*}
If $n\in\N$, we identify $n$ with $(n,n,n,\dots)/\mathscr U$;
thus, in the definition of $a_n$ for $n$ in $\stN$,
it suffices to give only the second case.

Theorem \ref{thm:a_n} is that
$\lim_{n\to\infty}a_n=L$ if and only if, for all infinite $n$, $a_n\icl L$.
Suppose we try to prove the foreward direction as follows.
Assuming $\lim_{n\to\infty}a_n=L$, we have that 
for some positive $\epsilon$ in $\R$,
\begin{gather*}
  \R\models
\Exists M\Forall n(n\in\N\And n\geq M\implies\abs{a_n-L}<\epsilon),\\
  \stR\models
\Exists M\Forall n(n\in\stN\And n\geq M\implies\abs{a_n-L}<\epsilon).
\end{gather*}
This is true, but is not what we want.
Rather, we want to observe that,
for some positive $\epsilon$ in $\R$,
for some $M$ in $\R$,
\begin{gather*}
  \R\models
\Forall n(n\in\N\And n\geq M\implies\abs{a_n-L}<\epsilon),\\
  \stR\models
\Forall n(n\in\stN\And n\geq M\implies\abs{a_n-L}<\epsilon).
\end{gather*}
Thus, if $n$ is infinite, then $\abs{a_n-L}<\epsilon$.
This being true for all positive real $\epsilon$, $a_n\icl L$.

Suppose conversely $\lim_{n\to\infty}a_n\neq L$.
Then for some positive $\epsilon$ in $\R$,
\begin{gather*}
  \R\models\Forall M\Exists n(n\in\N\And n\geq M\And\abs{a_n-L}\geq\epsilon),\\
  \stR\models
\Forall M\Exists n(n\in\stN\And n\geq M\And\abs{a_n-L}\geq\epsilon).
\end{gather*}
Letting $M$ be positive and infinite, we find infinite $n$ so that
$\abs{a_n-L}\geq\epsilon$ and therefore $a_n\not\icl L$.

If you grew up using $\delta$-$\epsilon$ proofs,
but now want to do infinitesimal calculus,
then you have to prove things like the foregoing.
Alternatively, you can just define $\lim_{n\to\infty}a_n=L$
to mean $a_n\icl L$ for all infinite $n$.
Then other proofs become easier.

\begin{lemma}
  Suppose $a$ in $\R^{\N}$ is convergent.
Then every term of $\sta$ is finite.
\end{lemma}

\begin{theorem}
  Suppose $a,b\in\R^{\N}$ and $\lim(a)=L$, $\lim(b)=M$, and $r\in\R$.  Then
  \begin{gather*}
    \lim(a+b)=L+M,\\
\lim(ra)=rL,\\
\lim(ab)=LM,
  \end{gather*}
and if $L\neq0$, then
\begin{equation}\label{eqn:a-inv}
  \lim{a\inv}=L\inv.
\end{equation}
\end{theorem}

\begin{proof}
Follow the method of the non-standard proofs of Theorems 
\ref{thm:+} and \ref{thm:.},
using that the infinitesimals of $\stR$
compose an ideal of the ring of finite elements.
For \eqref{eqn:a-inv},
we need the foregoing lemma---an \textsc{exercise}---%
that $a_n$ is finite for all $n$.
If $L\neq0$, possibly some $a_n$ are $0$,
but we prove that $a_n\neq0$ if $n$ is infinite.
\end{proof}

\begin{theorem}
  A sequence $a$ is convergent if and only if,
for all infinite $m$ and $n$, $a_m\icl a_n$.
\end{theorem}

The proof, an \textsc{exercise,}
will want \emph{standard parts.}
If $a$ is a finite element of $\stR$,
its \textbf{standard part} is an element $\stp a$ of $\R$
such that $\stp a\icl a$.
We achieve this by defining
\begin{equation*}
  \stp a=\sup\{x\in\R\colon x<a\}.
\end{equation*}
(compare \eqref{eqn:sup} on page \pageref{eqn:sup}).
To prove that this works, consider the alternative
whereby $0<\delta<\abs{a-\stp a}$ for some $\delta$ in $\R$.

We showed yesterday that, since $\stN$ is not well ordered,
the property of being well ordered is not first order.
Similarly being complete is not first order,
since the set of finite elements of $\stR$ has no supremum.

However, in the two-sorted structure $\N\sqcup\pow{\N}$,
the first-order sentence
\begin{equation*}
  \Forall Y
\bigl(1\in Y\And\Forall x(x\in Y\implies x+1\in Y)
\implies\Forall xx\in Y\bigr),
\end{equation*}
so it is true in $\starred(\N\sqcup\pow{\N})$,
which can be understood as $\stN\sqcup\starred\!\pow{\N}$,
where $\starred\!\pow{\N}$ consists of the subsets
\begin{equation*}
  \left\{x/\mathscr U\colon x\in\prod_{k\in\upomega}Y_k\right\}
\end{equation*}
of $\stN$, where $(Y_k\colon k\in\upomega)\in\pow{\N}^{\upomega}$.
Thus $\starred\!\pow{\N}\included\pow{\stN}$,
but the inclusion is proper, since for example
\begin{equation*}
  \N\in\pow{\stN}\setminus\starred\!\pow{\N}.
\end{equation*}

\subsection{Tuesday}

If $a\icl b$, and $b$ is finite, why must $a$ be finite?
If $a\icl b$, and $b$ is finite, then
\begin{gather*}
    \abs a-\abs b\leq\abs{a-b}\leq1,\\
\abs a\leq1+\abs b,
\end{gather*}
so $a$ is finite.

Since all terms of convergent sequences are finite,
convergent sequences are bounded.

What is the standard proof of this?
If $\lim(a)=L$,
then for some $N$, if $n>N$, then $\abs{a_n-L}<1$,
so $\abs{a_n}<\abs L+1$.
Now let $M=\min\{\abs{a_1},\dots,\abs{a_N},\abs L+1\}$.
Then $\abs{a_n}\leq M$ for all $n$ in $\N$.

An arbitrary subset $A$ of $\R$ is \textbf{bounded}
if
\begin{equation*}
  \Exists x\Forall y(y\in A\implies\abs y\leq x).
\end{equation*}

\begin{theorem}\label{thm:bdd}
  A subset $A$ of $\R$ is bounded 
if and only if every element of $\stA$ is finite.
\end{theorem}

A \textbf{limit point} of a subset $E$ of $\R$
is an element $p$ of $\R$
such that, for all positive $\epsilon$,
\begin{equation*}
  (p-\epsilon,p+\epsilon)\cap(E\setminus\{p\})\neq\emptyset,
\end{equation*}
that is,
\begin{equation}\label{eqn:lp}
  \Exists x(x\in E\And 0<\abs{x-p}<\epsilon).
\end{equation}
What is the non-standard formulation of this definition?

\begin{theorem}
  $p$ is a limit point of $E$ if and only if,
for some $q$ in $\starred E$,
\begin{equation}\label{eqn:qp}
  q\icl p\And q\neq p.
\end{equation}
\end{theorem}

\begin{proof}
  For the forward direction, let $q$ be $x$ in \eqref{eqn:lp}
when $\epsilon$ is a positive infinitesimal.
More precisely, we have
  \begin{gather*}
    \R\models\Forall\epsilon(\epsilon>0\implies\Exists q
(q\in E\And0<\abs{q-p}<\epsilon)),\\
    \stR\models\Forall\epsilon(\epsilon>0\implies\Exists q
(q\in\starred E\And0<\abs{q-p}<\epsilon)),
  \end{gather*}
so if we let $\epsilon$ be a positive infinitesimal,
we have $q$ as desired.

Conversely, suppose \eqref{eqn:qp} holds.
Then for all positive $\epsilon$ in $\R$,
\eqref{eqn:lp} holds in $\stR$, so it holds in $\R$:
that is, we have
 $0<\abs{q-p}<\epsilon$, and so,
\begin{gather*}
  \stR\models\Exists x(x\in\starred E\And0<\abs{x-p}<\epsilon),\\
  \R\models\Exists x(x\in E\And0<\abs{x-p}<\epsilon).
\end{gather*}
This being true for all positive $\epsilon$ in $\R$,
$p$ is a limit point of $E$.
\end{proof}

An alternative proof of the reverse direction
uses the construction of $\stR$ as follows.
We can write out $q$ as $(q_k\colon k\in\upomega)/\mathscr U$,
while $p$ is just $(p,p,p,\dots)/\mathscr U$.
Then for all $n$ in $\N$, since $\abs{q-p}<1/n$, we have
\begin{equation*}
  \{k\in\upomega\colon\abs{q_k-p}<1/n\}\in\mathscr U.
\end{equation*}
Also, since $q\neq p$,
\begin{equation*}
  \{k\in\upomega\colon q_k\neq p\}\in\mathscr U.
\end{equation*}
Since $\mathscr U$ is closed under $\cap$, we conclude
\begin{equation*}
  \{k\in\upomega\colon\abs{q_k-p}<1/n\And q_k\neq p\}\in\mathscr U.  
\end{equation*}
Finally, since $q\in\starred E$, we have
\begin{equation*}
  \{k\in\upomega\colon q_k\in E\}\in\mathscr U.
\end{equation*}
Indeed, we can consider $\starred E$ as $E^{\upomega}/\mathscr U$,
but more precisely
\begin{equation*}
  \starred E=\{x/\mathscr U\in\stR\colon x\in E^{\upomega}\};
\end{equation*}
this allows for the possibility that $x/\mathscr U=y/\mathscr U$,
but $y\notin E^{\upomega}$.
Summing up,
\begin{equation*}
  \{k\in\upomega\colon\abs{q_k-p}<1/n\And q_k\neq p\And q_k\in E\}
\in\mathscr U.  
\end{equation*}
Thus for all $n$ in $\N$, there is $q$ in $E$ such that $q\neq p$,
but $\abs{q-p}<1/n$.
Therefore $p$ is a limit point of $E$.

In this alternative argument, 
it does not follow that $\lim_{n\to\infty}q_n=p$.
For example,
possibly $\{\text{odds}\}\in\mathscr U$,
and $q_{2k}=2k$, so $(q_n\colon n\in\upomega)$ diverges.
But there is still a subsequence that converges to $p$.

The definitions of bounded sets and limit points,
as well as the following theorem,
can be adapted to apply to $\R^n$ for any $n$ in $\N$.
We stick with $\R$ for simplicity.

\begin{theorem}[Bolzano--Weierstrass]
  A bounded infinite subset of $\R$ has a limit point.
\end{theorem}

The standard proof
is to ``divide and conquer'':
If the infinite subset $E$ of $\R$ is bounded,
it is included in a closed bounded interval.
If we divide the interval in half,
then at least one of the halves contains infinitely many points of $E$.
Then we divide that interval in two, and continue.
The sequence of left endpoints of the intervals that we find
has a limit, which is a limit point of $E$.

\begin{proof}[Non-standard proof.]
Since $E$ is infinite,
there is a nonrepeating sequence $(a_n\colon n\in\upomega)$
such that each term is in $E$.
Let $n$ be infinite.  
Since $a_n$ is finite,
it has a standard part $b$.
Since $a_n\icl b$,
if $a_n\neq b$ we are done.
Suppose $a_n=b$.  Then for some finite $k$, $a_k=b$, so $a_k=a_n$.
Thus $(a_n\colon n\in\upomega)$ repeats.
\end{proof}

A neater non-standard proof uses the following.

\begin{theorem}\label{thm:fin*}
  A subset $E$ of $\R$ is finite
if and only if $\starred E=E$.
\end{theorem}

The proof is an \textsc{exercise;} or see page \pageref{proof:fin*}.
Meanwhile,
if $E$ is infinite and bounded, 
we can find $a$ in $\starred E\setminus E$
and then let $b=\stp a$;
then $b$ is a limit point of $E$.

\subsection{Wednesday}

Recall that $p$ is a \emph{limit point} of $A$
if there is $q$ in $\stA$ such that $q\neq p$, but $q\icl p$.
(This makes sense in $\R^n$ for all $n$ in $\N$,
not just in $\R$; but again, we shall officially stay with $\R$.)
A set is \textbf{closed} if it contains all of its limit points.
The complement of a closed set is \textbf{open.}
Then a subset $U$ of $\R$ is open if and only if,
for all $p$ in $U$, if $q\in\stR$ and $p\icl q$, then $q\in\starred U$.
Thus uses that $\stR$ is the disjoint union 
of $\starred U$ and $\starred(\R\setminus U)$:
\begin{equation*}
  \stR\setminus\starred(\R\setminus U)=\starred U.
\end{equation*}
If $p\in\R$, let
\begin{equation*}
  \monad p=\{q\in\stR\colon q\icl p\},
\end{equation*}
the \textbf{monad} of $p$.
This is Robinson's term \cite[pp.~57, 90]{MR1373196},
but whether Robinson 
is alluding to Leibniz's philosophical use of the term is not clear.
In passing from $\R$ to $\stR$,
each point is replaced by a ``cloud''---its monad,
monads of distinct points being disjoint.

In any case,
we now have that $U$ is open if and only if, for all $p$ in $U$,
\begin{equation*}
  \monad p\included U.
\end{equation*}

\begin{theorem}
  The open subsets of $\R$
are just the unions of sets of open intervals.
\end{theorem}

\begin{proof}
  Suppose $U$ is open.
Then for every $p$ in $U$, $\monad p\included U$,
and so $(p-\delta,p+\delta)$ for infinitesimal positive $\delta$.
Thus
\begin{gather*}
  \stR\models\Exists x\starred(p-x,p+x)\included\starred U,\\
  \R\models\Exists x(p-x,p+x)\included U,
\end{gather*}
so for some positive $\delta_p$ in $\R$, $(p-\delta_p,p+\delta_p)\included U$.
Thus
\begin{equation*}
U=\bigcup\{(p-\delta_p,p+\delta_p)\colon p\in U\}.
\end{equation*}
The converse is easy.
\end{proof}

\begin{porism}
  The intersection of every set of closed sets is a closed set.
Every closed interval is a closed set.
\end{porism}

Not every closed set is a union of closed intervals.
Examples are singleton sets
and $\{1/n\colon n\in\N\}\cup\{0\}$.
An uncountable example is the \textbf{Cantor set,}
which results from starting with the closed interval $[0,1]$,
removing the open interval $(1/3,2/3)$,
then removing the middle thirds of the remaining intervals,
and so on.

\begin{theorem}
  A subset $A$ of $\R$ is closed and bounded if and only if
for all $q$ in $\stA$ there is $p$ in $A$ such that $p\icl q$.
\end{theorem}

\begin{proof}
  Suppose $A$ is closed and bounded, and $q\in\stA$.
Since $A$ is bounded, $q$ is finite, by Theorem \ref{thm:bdd}.
Now let $p$ be the standard part of $q$.
Either $p=q$, or $p$ is a limit point of $A$.
In either case, $p\in A$, since this is closed.

Suppose conversely
for all $q$ in $\stA$ there is $p$ in $A$ such that $p\icl q$.
Since $p$ is finite, $q$ must be finite.
Thus $A$ is bounded.
Suppose $p$ is a limit point of $A$.
For some $q$ in $\stA$, $p\icl q$, but $p\neq q$.
But for some $p'$ in $A$, $p'\icl q$.
Therefore $p\icl p'$, so $p=p'$, and $p\in A$.
\end{proof}

We are going to talk about \emph{compactness,}
both in the present context and in logic.
The \textbf{Compactness Theorem}\label{comp} of first-order logic
is that if $\Gamma$ is set of first-order sentences,
and every finite subset of $\Gamma$ has a model,
then $\Gamma$ has a model.  (See page \pageref{thm:comp}).

A collection $\mathscr O$ of open subsets of $\R$
is a \textbf{cover} (or \textbf{open cover}) of $A$ if
\begin{equation*}
  A\included\bigcup\mathscr O.
\end{equation*}
Then $A$ is \textbf{compact}
if for all open covers $\mathscr O$ of $A$,
there is a finite subset of $\mathscr O$ that covers $A$.

\begin{theorem}[Heine--Borel]\label{thm:HB}
  A subset $A$ of $\R$ (or $\R^n$) is compact
if and only if closed and bounded
(that is,
for all $q$ in $\stA$ there is $p$ in $A$ such that $q\in\monad p$).
\end{theorem}

\begin{proof}
  ($\Rightarrow$) (Standard)  $A\included\bigcup\{(-n,n)\colon n\in\N\}$.
If $p\notin A$, then
\begin{equation*}
  A\included\bigcup\{\R\setminus[p-\delta,p+\delta]\colon\delta>0\}.
\end{equation*}

($\Rightarrow$)  (Non-standard)
Suppose for some $q$ in $\stA$, for all $p$ in $A$, $q\notin\monad p$.
But (\textsc{exercise})
\begin{equation*}
  \monad p=\bigcap\{\starred U\colon U\text{ open and }p\in U\}.
\end{equation*}

So for some open set $U_p$ containing $p$, $q\notin\starred U_p$.
Then $\{U_p\colon p\in A\}$ covers $A$, 
but $\{\starred U_p\colon p\in A\}$ does not cover $\stA$.
However, if $\{p(0),\dots,p(n)\}$ is a finite subset of $A$, then
\begin{equation*}
  \starred(U_{p(0)}\cup\dots\cup U_{p(n)})
=\starred U_{p(0)}\cup\dots\cup\starred U_{p(n)},
\end{equation*}
so $U_{p(0)}\cup\dots\cup U_{p(n)}$ cannot include $A$.
That is, if
\begin{equation*}
  \R\models\Forall x(x\in A\lto x\in U_{p(0)}\lor\dots\lor x\in U_{p(n)}),
\end{equation*}
then
\begin{equation*}
  \stR\models\Forall x
(x\in\stA\lto x\in\starred U_{p(0)}\lor\dots\lor x\in\starred U_{p(n)}),
\end{equation*}
which cannot be.

($\Leftarrow$)  (Non-standard)
Suppose $\mathscr O$ is an open cover of $A$
with no finite subcover.
We may assume $\mathscr O$ is countable
by the \textbf{Lindel\"of Covering Theorem:}
For every $p$ in $A$,
there is $U$ in $\mathscr O$ such that $p\in U$;
but then for some $a_p$ and $b_p$ in $\Q$,
\begin{equation*}
  p\in(a_p,b_p)\And(a_p,b_p)\included U.
\end{equation*}
Thus we can replace $\mathscr O$ with $\{(a_p,b_p)\colon p\in A\}$,
which is countable.
If this has a finite subcover of $A$, so does $\mathscr O$.

Say then $\mathscr O=\{U_k\colon k\in\upomega\}$.
Let
\begin{gather*}
  q_k\in A\setminus\bigcup_{i<k}U_i=A\setminus(U_0\cup\dots\cup U_{k-1}),\\
q=(q_k\colon k\in\upomega)/\mathscr U.
\end{gather*}
If $p\in A$, then $p\in U_k$ for some $k$; but then
\begin{equation*}
  \{\ell\in\upomega\colon q_{\ell}\in U_k\}\included\{0,1,\dots,k\}
\end{equation*}
since
\begin{equation*}
k<\ell\implies q_{\ell}\notin U_0\cup\dots\cup U_k\cup\dots\cup U_{\ell-1}.
\end{equation*}
Since finite sets are small, $q\notin U_k$, so $q\notin\monad p$.
\end{proof}

In the non-standard proof of the sufficiency 
of the ``$q\in\monad p$'' condition,
we have used more than the \textbf{Transfer Principle,}
which is what we have written as $\R\preccurlyeq\stR$ 
in \eqref{eqn:prec} on page \pageref{eqn:prec}.
Likewise we need more than the Transfer Principle for:

\begin{proof}[Proof of Theorem \ref{thm:fin*}.]\label{proof:fin*}
Suppose $E=\{a_1,\dots,a_n\}$,
but $q$ is an element $(q_1,q_2,\dots)/\mathscr U$ of $\starred E\setminus E$.
If
\begin{equation*}
  A_i=\{k\in\upomega\colon q_k=a_i\},
\end{equation*}
then $A_i$ is small; but
\begin{equation*}%\label{eqn:wA}
\upomega=A_1\cup\dots\cup A_n,
\end{equation*}
which is therefore small, which is absurd.

Conversely (or inversely), 
suppose $\{q_n\colon n\in\upomega\}\included A$,
all $q_n$ different from one another.
Let $q=(q_n\colon n\in\upomega)/\mathscr U$.
If $a\in A$, then $q\neq a$, since the set
\begin{equation*}
  \{n\in\upomega\colon q_n=a\}
\end{equation*}
has at most one element.
\end{proof}

Alternatively, for the first part,
by the Transfer Principle we have
\begin{gather*}
  \R\models\Forall x(x\in A\implies x=a_1\lor\dots\lor x=a_n),\\
  \stR\models\Forall x(x\in\stA\implies x=a_1\lor\dots\lor x=a_n).
\end{gather*}

For an example of the logical Compactness Theorem,
given a structure $\str A$, let
\begin{equation}\label{eqn:Th}
  \Th{\str A}=\{\sigma\colon\str A\models\sigma\},
\end{equation}
the \textbf{theory of} $\str A$.  
Here $\sigma$ is a first-order sentence.
Let
\begin{equation*}
  \sigma_n=\Exists{x_0,\dots x_{n-1}}\bigwedge_{i<j<n}x_i\neq x_j.
\end{equation*}
By Compactness, 
$\bigcap\{\Th{\F_p}\colon p\text{ prime}\}\cup\{\sigma_n\colon n\in\N\}$ 
has a model.
In fact $\prod_{p\text{ prime}}\F_p/\mathscr U$ is a model,
$\mathscr U$ being a nonprincipal ultrafilter on $\{\text{primes}\}$.

By contrast, 
$\{\text{Peano axioms}\}\cup\{c\neq\overbrace{1+\dots+1}^n\colon n\in\N\}$ 
has no model;
so the Peano axioms for $\N$ have no first-order formulation.

\subsection{Friday}

Again,
the \textbf{open} subsets of $\R$ are just the unions of sets of open intervals.
Let $\mathscr O$ be the set of open subsets of $\R$.  Then
\begin{enumerate}
\item 
$\mathscr X\included\mathscr O\implies\bigcup\mathscr X\in\mathscr O$.
\item
In particular, $\emptyset\in\mathscr O$ (since $\bigcup\emptyset=\emptyset$).
\item
If $X,Y\in\mathscr O$, then $X\cap Y\in\mathscr O$,
since
\begin{equation*}
\bigcup\mathscr X\cap\bigcup\mathscr Y
=\bigcup\{Z\cap W\colon Z\in\mathscr X\And W\in\mathscr Y\}.
\end{equation*}
\item
$\R\in\mathscr O$.
\end{enumerate}
If $A$ is an arbitrary set,
and $\mathscr O$ is a subset of $\pow A$
with the four properties above
(with $A\in\mathscr O$ as the fourth property),
then $\mathscr O$ is the set of \textbf{open subsets} of $A$
in a \textbf{topology on} $A$,
and $(A,\mathscr O)$ is a \textbf{topological space.}\label{top}

We are going to be interested in the case
where $A$ is the set of prime ideals of some ring $R$;
this set is called
\begin{equation*}
  \spec,
\end{equation*}
the \textbf{spectrum} of $R$.
Recall then that $P\in\spec$ if and only if
\begin{gather*}
  x\in P\And y\in P\implies x+y\in P,\\
x\in P\Or y\in P\iff xy\in P,\\
0\in P\And 1\notin P.
\end{gather*}
For example:
\begin{itemize}
\item 
Writing $(n)=n\Z=\{nx\colon x\in\Z\}$, we have
\begin{equation*}
\spec[\Z]=\{(p)\colon p\text{ prime}\}\cup\{(0)\}.
\end{equation*}
\item
If $K$ is an algebraically closed field like $\C$, then
\begin{equation*}
  \spec[{K[X]}]=\{(X-a)\colon a\in K\}\cup\{(0)\},
\end{equation*}
while $\spec[{K[X,Y]}]$ consists of the ideals
\begin{itemize}
\item
$(X-a,Y-b)$, where $a,b\in K$;
\item 
$(f)$, where $f$ is an irreducible element of $K[X,Y]$;
\item
$(0)$.
\end{itemize}
\end{itemize}
If $R$ is a ring, and $a\in R$, let
\begin{equation*}
  [a]=\{P\in\spec\colon a\notin P\}.
\end{equation*}
If also $b\in R$, then
\begin{equation*}
  [a]\cap[b]=[ab].
\end{equation*}
Therefore unions of sets of sets $[a]$ 
are the open sets in a topology on $\spec$.
The sets $[a]$ themselves are like open intervals.

As with closed bounded subsets of $\R$,
a topological space $(A,\mathscr O)$ is \textbf{compact}
if for all subsets $\mathscr X$ of $\mathscr O$,
if $\bigcup\mathscr X=A$,
then for some finite subset $\mathscr X_0$ of $\mathscr X$,
\begin{equation*}
  \bigcup\mathscr X_0=A.
\end{equation*}

The open subsets of $\spec[\Z]$
are just the complements of finite sets of ideals $(p)$.
In particular, $(0)$ belongs to every nonempty open set.
Then easily $\spec[\Z]$ is compact.

\begin{theorem}\label{thm:spec}
  For all rings $R$, $\spec$ is compact.
\end{theorem}

\begin{proof}[Standard proof.]
  Suppose $A\included R$ and $\bigcup\{[x]\colon x\in A\}=\spec$.
Then
\begin{equation*}
  \bigcap\{[x]\comp\colon x\in A\}=\emptyset;
\end{equation*}
but in general
\begin{equation*}
  \bigcap\{[x]\comp\colon x\in A\}=\{P\in\spec\colon A\included P\}.
\end{equation*}
By the Prime Ideal Theorem (page \pageref{thm:pith}),
$A$ is included in no proper ideal.
In general, the smallest ideal including $A$ is
\begin{equation*}
  \{a_0x_0+\dots+a_{n-1}x_{n-1}\colon 
n\in\upomega\And\bm a\in A^n\And\bm x\in R^n\};
\end{equation*}
this is denoted by
\begin{equation*}
  (A).
\end{equation*}
In the present case, $1\in(A)$, so
\begin{equation*}
  1=a_0x_0+\dots a_{n-1}x_{n-1}
\end{equation*}
for some $a_i$ in $A$.  Then
\begin{gather*}
  [a_0]\comp\cap\dots\cap[a_{n-1}]\comp=\emptyset,\\
[a_0]\cup\dots\cup[a_{n-1}]=\spec.\qedhere
\end{gather*}
\end{proof}

For a non-standard proof,
if $(A,\mathscr O)$ is a topological space,
and $\Omega$ is some infinite set, 
and $\mathscr U$ is a nonprincipal ultrafilter on $\Omega$,
we define
\begin{equation*}
  \stA=A^{\Omega}/\mathscr U
\end{equation*}
as before.
If $P\in A$, we now \emph{define}
\begin{equation*}
  \monad P=\bigcap\{\starred U\in\mathscr O\colon P\in U\}.
\end{equation*}
Then the non-standard proof of the Heine--Borel Theorem (page \pageref{thm:HB})
gives us:

\begin{theorem}
  A topological space $A$ is compact if and only if,
for all choices of $\Omega$ and $\mathscr U$,
for all $Q$ in $\stA$ there is $P$ in $A$ such that
\begin{equation*}
  Q\in\monad P.
\end{equation*}
\end{theorem}

We must adjust the proof of sufficiency given for the Heine--Borel Theorem,
since now we cannot assume $\mathscr O$ countable.
We let $\Omega$ be the set of finite subsets of $\mathscr O$,
and we let $\mathscr U$ be an ultrafilter on $\Omega$
that contains, for each $E$ in $\mathscr O$, the set
\begin{equation*}
  \{X\in\Omega\colon E\in X\}.
\end{equation*}
(Such sets do generate a proper filter on $\Omega$,
since $\mathscr O$ is closed under taking intersections.)
If $X\in\Omega$, we can let
\begin{equation*}
  q_X\in A\setminus\bigcup X
\end{equation*}
The resulting point $(q_X\colon X\in\Omega)/\mathscr U$ of $\stA$ 
is not in $\monad p$.
Now we can proceed with:


\begin{proof}[Non-standard proof of Theorem \ref{thm:spec}.]
  Given $Q$ in $\starred\!\spec$, we are going to find $P$ in $\spec$ such that
  \begin{equation*}
    Q\in\monad P.
  \end{equation*}
Here 
\begin{equation*}
\monad P
=\bigcap\{\starred[x]\colon P\in[x]\}
=\bigcap\{\starred[x]\colon a\notin P\},
\end{equation*}
and for some $(Q_i\colon i\in\Omega)$ in $(\spec)^{\Omega}$,
\begin{gather*}
  Q=(Q_i\colon i\in\Omega)/\mathscr U,\\
  Q\in\starred[x]\iff\{i\in\Omega\colon x\notin Q_i\}\in\mathscr U.
\end{gather*}
Now define
\begin{equation*}
  P=\bigl\{x\in R\colon\{i\in\Omega\colon x\in Q_i\}\in\mathscr U\bigr\}.
\end{equation*}
Then $P\in\spec$ and $Q\in\monad P$.
Indeed, if $x,y\in P$, then
\begin{gather*}
  \{i\in\Omega\colon x\in Q_i\},
\{i\in\Omega\colon y\in Q_i\}\in\mathscr U,\\
\{i\in\Omega\colon x,y\in Q_i\}\in\mathscr U,\\
\{i\in\Omega\colon x+y\in Q_i\}\in\mathscr U
\end{gather*}
(using that $\mathscr U$ is closed under intersections and taking supersets),
so $x+y\in P$.
Likewise
\begin{equation*}
x\in P\Or y\in P\iff xy\in P.
\end{equation*}
Finally, $0\in P\And 1\notin P$.
\end{proof}

The non-standard proof seems to work by magic.
One need not recognize that if $1\in(A)$,
then $1\in(A_0)$ for some finite subset $A_0$ of $A$.

In the remainder of the course,
we want to establish the following:\label{to-do}
\begin{itemize}
\item 
The Prime Ideal Theorem (page \pageref{thm:pith}) 
is equivalent to the Compactness Theorem of first-order logic
(pages \pageref{thm:los}, \pageref{comp}, and \pageref{thm:comp}).
\item
The Maximal Ideal Theorem (page \pageref{thm:mith}) is equivalent to:
\begin{itemize}
\item
the Prime Ideal Theorem with \L o\'s's Theorem (page \pageref{thm:los});
\item
the Axiom of Choice;
\item
Zorn's Lemma (page \pageref{thm:zorn}).
\end{itemize}
\end{itemize}
In the background is Zermelo--Fraenkel set theory.

\begin{theorem}
The Compactness Theorem
implies the Prime Ideal Theorem.
\end{theorem}

\begin{proof}
  Supposing $R$ is a ring,
let $\diag R$ be the set of quantifier-free sentences in $\{0,1,-,+,\times\}$,
with parameters from $R$, that are true in $R$.
Let $P$ be a new singulary relation symbol, and let
\begin{multline*}
  \Gamma
=\diag R
\cup\{Pa\land Pb\lto P(a+b)\colon a,b\in R\}\\
\cup\{Pa\lor Pb\liff P(ab)\colon a,b\in R\}
\cup\{P0,\lnot P1\}.
\end{multline*}
Then $\Gamma$ has a model,
because every finite subset $\Gamma_0$ of $\Gamma$ has a model.
Indeed, $\Gamma_0$ involves only finitely many parameters,
so they generate a \emph{countable} sub-ring $R_0$ of $R$.

The Prime Ideal Theorem holds for nontrivial countable rings.
For, say $R_0=\{b_n\colon n\in\upomega\}$.  Let $B_0=\emptyset$ and
\begin{equation*}
  B_{n+1}=
  \begin{cases}
    B_n,&\text{ if $(B_n\cup(b_n))=R_0$},\\
B_n\cup\{b_n\},&\text{ otherwise.}
  \end{cases}
\end{equation*}
Then $\bigcup_{n\in\upomega}B_n$ is a maximal ideal of $R_0$,
hence a prime ideal of $R_0$.

Now the symbol $P$ can be interpreted as this prime ideal of $R_0$,
so that $R_0$ is a model of $\Gamma_0$.

By Compactness, $\Gamma$ has a model $(S,Q)$.
We may assume $R\included S$,
and then $R\cap Q$ is a prime ideal of $R$.

So far, we have shown only that $R$ has a prime ideal.
In particular, if $I$ is a proper ideal of $R$,
then $R/I$ has a prime ideal;
but this will be of the form $P/I$ for some prime ideal $P$ of $R$
that includes $I$.
\end{proof}

If one knows any \textbf{Galois Theory,}
then what we are doing can be seen in this context.
A \textbf{relation from} a set (or class) $A$
\textbf{to} a set $B$ is a subset of $A\times B$.
Suppose $\Grel$ is such a relation.
If $Y\included B$, then the set
\begin{equation*}
  \bigcap_{y\in Y}\{x\in A\colon x\mathrel{\Grel}y\}
\end{equation*}
is a \textbf{closed} subset of $A$ with respect to $\Grel$.
The closed subsets of $B$ are defined similarly.
It is not too hard to establish that there is a one-to-one,
inclusion-reversing correspondence
between the closed subsets of $A$
and the closed subsets of $B$.
It may be more difficult 
to give an interesting characterization of the closed subsets.
In some cases, the closed subsets of $A$
are closed with respect to a topology on $A$;
but this is not always true.

In the original case,
$B$ is a field $K$, and $A$ is its group $\Aut$ of automorphisms,
and
\begin{equation*}
  \Grel=\{(\sigma,x)\in\Aut\times K\colon x^{\sigma}=x\}.
\end{equation*}
We are interested in three other cases:
\begin{itemize}
\item 
$B$ is a ring $R$, and $A$ is its spectrum $\spec$, and
\begin{equation*}
  \Grel=\{(\mathfrak p,x)\in\spec\times R\colon x\notin\mathfrak p\}.
\end{equation*}
\item
$B$ is a \emph{Boolean algebra} (defined below),
$A$ is the set $\St B$ of its ultrafilters, and
  \begin{equation*}
    \Grel=\{(\mathscr U,x)\in\St B\times B\colon x\in\mathscr U\}.
  \end{equation*}
\item
For some logical signature $\sig$,
$B$ is the set $\Sn$ of sentences of $\sig$,
and $A$ is the \emph{class} $\Mod$ of structures having signature $\sig$,
and $\Grel$ is the relation of truth:
\begin{equation*}
  \Grel=\{(\str A,\sigma)\in\Mod\times\Sn\colon\str A\models\sigma\}.
\end{equation*}
(See tomorrow's lecture.)
\end{itemize}

For any set $\Omega$, the structure
\begin{equation*}
(\pow{\Omega},\emptyset,\Omega,\symdiff,\cap\}
\end{equation*}
is a Boolean ring; but the structure
\begin{equation*}
  (\pow{\Omega},\emptyset,\Omega,{}\comp,\cup,\cap\}
\end{equation*}
is a \textbf{Boolean algebra.}
If $(R,0,1,+,\times)$ is an arbitrary Boolean ring, then
$(R,0,1,\lnot,\lor,\land)$ is a Boolean algebra, where
\begin{gather*}
  \lnot x=1+x,\\
x\lor y=x+y+xy,\\
x\land y=xy,
\end{gather*}
and also
\begin{gather*}
  x+y=(x\land\lnot y)\lor(y\land\lnot x),
xy=x\land y.
\end{gather*}
We are going to prove (on page \pageref{proof:stone}):

\begin{theorem}[Stone Representation Theorem]\label{thm:Stone}
  Every Boolean algebra $\str A$ embeds in an algebra $\pow{\Omega}$.
Here $\Omega$ can be taken as the set 
$\St{\str A}$ of ultrafilters of $\str A$.
\end{theorem}

This is analogous to the simpler:

\begin{theorem}[Cayley's Theorem]
  Every group $G$ embeds in a symmetry group
  \begin{equation*}
  (\Sym,\id,{}\inv,\circ),
  \end{equation*}
where $\Sym$ is the set of bijections from $\Omega$ to $\Omega$.
Here $\Omega$ can be taken as $G$ itself, 
and the embedding of $G$ in $\Sym[G]$ is
\begin{equation*}
  g\mapsto\uplambda_g,
\end{equation*}
where $\uplambda_g(x)=gx$.
\end{theorem}

The original groups are a symmetry groups.
Such groups are seen to satisfy certain axioms,
and it turns out, as in Cayley's Theorem,
that all structures that satisfy these axioms
are isomorphic to symmetry groups.
The same will be seen to be true for Boolean algebras.

\subsection{Saturday}%\label{subsect:2sat}

Given a first-order signature $\sig$,
we let
\begin{gather*}
  \Mod=\{\text{structures of $\sig$}\},\\
\Sn=\{\text{sentences of $\sig$}\}.
\end{gather*}
The relation $\models$ of \textbf{truth}
is from $\Mod$ to $\Sn$.
If $\sigma,\tau\in\Sn$,
and for all $\str A$ in $\Mod$,
\begin{equation*}
  \str A\models\sigma\iff\str A\models\tau,
\end{equation*}
then we say $\sigma$ and $\tau$ are \textbf{logically equivalent,}
and we write
\begin{equation*}
  \sigma\sim\tau.
\end{equation*}

\begin{theorem}
$\Sn\modsim$ is a Boolean algebra.  
\end{theorem}

The Boolean algebra of the theorem
is called a \textbf{Lindenbaum algebra}
after a student of Tarski murdered by the Nazis;
it can be denoted by
\begin{equation*}
  \Lin.
\end{equation*}
The subscript $0$ indicates that there are no free variables
in the formulas whose logical equivalence classes compose the algebra.
(Later, on page \pageref{Lin1},
we shall have reason to consider 
the Lindenbaum algebra of formulas in one free variable.)

If $\str A,\str B\in\Mod$,
and for all $\sigma$ in $\Sn$,
\begin{equation*}
  \str A\models\sigma\iff\str B\models\sigma,
\end{equation*}
then we say $\str A$ and $\str B$ are \textbf{elementarily equivalent,}
and we write
\begin{equation*}
  \str A\equiv\str B.
\end{equation*}

By defining
\begin{equation*}\Th{\str A}=\{\sigma\in\Sn\colon\str A\models\sigma\}
\end{equation*}
as in \eqref{eqn:Th} on page \pageref{eqn:Th},
we have
\begin{equation*}
  \str A\equiv\str B\iff\Th{\str A}=\Th{\str B}.
\end{equation*}

\begin{theorem}
For all $\str A$ in $\Mod$,
the quotient
\begin{equation*}
\Th{\str A}\modsim
\end{equation*}
is an ultrafilter of $\Lin$.
\end{theorem}

Strictly,
$\Th{\str A}\modsim$ here should be understood as
\begin{equation*}
\{\sigma\modsim\in\Lin\colon\str A\models\sigma\}.
\end{equation*}
If now $\str A$ is an arbitrary Boolean algebra,
we let
\begin{equation*}
\St{\str A}=\{\text{ultrafilters of $\str A$}\};
\end{equation*}
this will be the \textbf{Stone space} of $\str A$.
In case $\str A=\Lin$, the situation is as in Figure \ref{fig}.
\begin{figure}
  \begin{equation*}
    \xymatrix@!0@=2.6cm{
\Mod\ar@{>>}[d]_{\str A\mapsto\str A\modequiv}
&\Sn\ar@{<~>}[l]_{\models}\ar@{>>}[d]^{\sigma\mapsto\sigma\modsim}\\
\Mod\modequiv\rule[-1.7ex]{0ex}{2ex}
\ar@{<~>}[r]\ar@{>->}[d]_{\str A\modequiv\mapsto\Th{\str A}\modsim}
&\Lin\\
\St{\Lin}\ar@{<~>}[ur]_{\ni}&
}
  \end{equation*}
  \caption{Stone space of Lindenbaum algebra}\label{fig}
  
\end{figure}
In general, if $U\in\St{\str A}$, this means
\begin{gather*}
  x\in U\And y\in U\iff x\land y\in U,\\
\lnot x\in U\iff x\notin U.
\end{gather*}
Hence
\begin{gather*}
  x\in U\Or y\in U\iff x\lor y\in U,\\
1\in U,\qquad 0\notin U.
\end{gather*}
The Boolean algebra $\str A$ is (partially) ordered by
\begin{align*}
  x\leq y
&\iff x\land y=x\\
&\iff x\lor y=y;
\end{align*}
see Figure \ref{fig:order}.
\begin{figure}
  \begin{equation*}
    \xymatrix@!0@=1.2cm{
&1&\\
&x\lor y\ar@{-}[u]&\\
x\ar@{-}[ur]&&y\ar@{-}[ul]\\
&x\land y\ar@{-}[ul]\ar@{-}[ur]&\\
&0\ar@{-}[u]&
}
  \end{equation*}
  \caption{Ordering of a Boolean algebra}\label{fig:order}
  
\end{figure}
If $a\in A$, let
\begin{equation*}
  [a]=\{U\in\St{\str A}\colon a\in U\}.
\end{equation*}

\begin{proof}[Proof of the Stone Representation Theorem.]\label{proof:stone}
In the Boolean algebra $\str A$, we now have
  \begin{gather*}
  [x]\cap[y]=[x\land y],\\
[\lnot x]=[x]\comp,\\
[x]\cup[y]=[x\lor y],\\
[1]=\St{\str A},\qquad[0]=\emptyset.
\end{gather*}
Thus the map $x\mapsto[x]$ from $A$ to $\pow{\St{\str A}}$
is a homomorphism of Boolean algebras.
Moreover, it is an embedding,
since if $a\neq b$, then we may assume $a\land b\neq a$,
so
\begin{equation*}
  a\land\lnot b=a\land(1+b)=a+(a\land b)\neq0,
\end{equation*}
since $a+a=0$.
Therefore $a\land\lnot b$ generates a proper filter, namely
\begin{equation*}
  \{x\lor(a\land\lnot b)\colon x\in A\},
\end{equation*}
which by the Prime Ideal Theorem (page \pageref{thm:pith})
is included in an element $U$ of $\St{\str A}$.
Then
\begin{equation*}
  U\in[a]\setminus[b],
\end{equation*}
so $[a]\neq[b]$.
\end{proof}

Suppose $(A,\mathscr O)$ is a topological space
as on page \pageref{top}.
If $\mathscr B\included\mathscr O$,
and every element of $\mathscr O$ is $\bigcup\mathscr X$ 
for some subset $\mathscr X$ of $\mathscr B$,
then $\mathscr B$ is a \textbf{base} or \textbf{basis} of $\mathscr O$.
For example,
\begin{itemize}
\item 
$\{(a,b)\colon a,b\in\R\}$ is a base for the topology of $\R$.
\item
$\{[a]\colon a\in R\}$ is a base for the topology of $\spec$
for any ring $R$.  Hence:
\item
$\{[a]\colon a\in A\}$ is a base for the topology of $\St{\str A}$
for any Boolean algebra $\str A$,
since $\St{\str A}=\{P\comp\colon P\in\spec[\str A]\}$.
The subsets $[a]$ of $\St{\str A}$ are both open and closed:
they are \textbf{clopen.}
\end{itemize}

A topological space $(A,\mathscr O)$ with base $\mathscr B$ is compact
if and only if, for all subsets $\mathscr X$ of $\mathscr B$
such that $\bigcup\mathscr X=A$,
there is a finite subset $\mathscr X_0$ of $\mathscr X$
such that $\bigcup\mathscr X_0=A$.
Taking the contrapositive and taking complements,
we have:

\begin{theorem}
  A topological space $(A,\mathscr O)$ with base $\mathscr B$ is compact
if and only if, for all subsets $\mathscr X$ of $\mathscr B$
such that,
for all finite subsets $\mathscr X_0$ of $\mathscr X$,
\begin{equation*}
  \bigcap\{X\comp\colon X\in\mathscr X_0\}\neq\emptyset,
\end{equation*}
it follows that
\begin{equation*}
  \bigcap\{X\comp\colon X\in\mathscr X\}\neq\emptyset.
\end{equation*}
\end{theorem}

The hypothesis of this condition is that $\{X\comp\colon X\in\mathscr X\}$
has the \textbf{finite intersection property} or \textbf{FIP.}

For a Boolean algebra $\str A$,
the theorem is that $\St{\str A}$ is compact
if and only if,
for all subsets $X$ of $A$ such that 
every finite subset of $A$ is included in an ultrafilter,
$X$ itself is included in an ultrafilter.
This condition is immediately satisfied.

Let $C$ be the subspace
\begin{equation*}
\{\Th{\str A}\modsim\colon\str A\in\Mod\}
\end{equation*}
of $\St{\Lin}$.
Then $C$
is compact
if and only if, for every subset $\Gamma$ of $\Sn$,
if every finite subset of $\Gamma$ has a model,
then $\Gamma$ itself has a model.
Thus the compactness of $C$
is equivalent to the Compactness Theorem (page \pageref{comp}).

The subspace $C$ is \textbf{dense} in $\St{\Lin}$,
because if $[\sigma\modsim]\neq\emptyset$,
then
\begin{equation*}
\sigma\not\sim\Exists xx\neq x,
\end{equation*}
so $\sigma$ has a model $\str A$,
and then $\Th{\str A}\modsim\in[\sigma\modsim]$.

Thus every element of $\St{\Lin}\setminus C$
is a limit point of $C$.
Therefore $C$ is closed if and only if $C=\St{\Lin}$.
In particular, if $C$ is closed, then it is compact.
Conversely,
since $\St{\Lin}$ is a \emph{Hausdorff space,}
its every compact subset is closed.

We shall not pursue this further,
but a topological space is a \textbf{Hausdorff space}
if for any two distinct points of the space,
there are disjoint open sets
containing the points respectively.
Easily a Stone space $\St{\str A}$ is Hausforff:
if $U_0$ and $U_1$ are distinct elements,
then we may assume there is $a$ in $U_0\setminus U_1$,
and so $U_0\in[a]$ and $U_1\in[\lnot a]$.

Now we prove the theorem
stated originally on page \pageref{comp};
we implicitly proved a version of it
in proving \L o\'s's Theorem (page \pageref{thm:los}).

\begin{theorem}[Compactness]\label{thm:comp}
  If $\Gamma$ is a subset of $\Sn$
whose every finite subset has a model,
then $\Gamma$ itself has a model.
\end{theorem}

\begin{proof}
  We can assume $\sig$ has been expanded
so that, for every singulary formula $\phi(x)$,
there is a new constant symbol
\begin{equation*}
  c_{\phi}.
\end{equation*}
Now let\label{Lin1}
\begin{equation*}
\Gamma^*=  \Gamma\cup\{\Exists x\phi(x)\lto\phi(c_{\phi})\colon
\phi\modsim\in\Lin[1]\}.
\end{equation*}
Then every finite subset of $\Gamma^*$
has a model.
By the Prime Ideal Theorem (page \pageref{thm:pith}), 
there is a subset $T$ of $\Sn$
such that $\Gamma\included T$
and $T\modsim$ is an ultrafilter of $\Lin$.
Then $T$ has a model $\str A$ such that
\begin{equation*}
  A=\{c_{\phi}\colon\phi\}\modapprox,
\end{equation*}
where
\begin{equation*}
  c_{\phi}\approx c_{\psi}\iff(c_{\phi}=c_{\psi})\in T.
\end{equation*}
For example, if $F$ is a singulary operation symbol in $\sig$,
then
\begin{equation*}
  F^{\str A}(c_{\phi})=c_{\psi}\iff(Fc_{\phi}=c_{\psi})\in T.
\end{equation*}
There are many details to check, but this is the idea.
\end{proof}

We obtained $\stR$ as an ultrapower $\R^{\upomega}/\mathscr U$;
but Robinson \cite[p.~55]{MR1373196} can be understood
to obtain it by the Compactness Theorem
as a model of
\begin{equation*}
  \Th{\R}\cup\{c>n\colon n\in\N\}.
\end{equation*}
(Here the signature of $\R$ has everything we might want.)
However, Robinson \cite[p.~13]{MR1373196} proves the Compactness Theorem
by means of ultraproducts and \L o\'s's Theorem (page \pageref{thm:los}).

\subsection{Sunday}\label{final}

We have shown the equivalence in Zermelo--Fraenkel set theory of:
\begin{itemize}
\item 
the Compactness Theorem (page \pageref{thm:comp}),
\item
The Prime Ideal Theorem (page \pageref{thm:pith}), and
\item
The Boolean 
$\left\{\text{\begin{tabular}{c}
  Prime\\
Maximal
\end{tabular}}\right\}$
Ideal Theorem.
\end{itemize}
We are going to show the equivalence of:
\begin{itemize}
\item 
The Prime Ideal Theorem, together with \L o\'s's Theorem, and
\item
The Axiom of Choice.%%%%%
\footnote{We could add to the list
examples like
the \emph{Tychonoff Theorem}:
the product of compact spaces is compact.
Restricted to Hausdorff spaces,
the theorem is equivalent to the Prime Ideal Theorem.
See Rubin and Rubin \cite{MR798475} and their references.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{itemize}

As we noted (page \pageref{thm:los}),
Compactness can be understood as a weak form of \L o\'s's Theorem
(with the Prime Ideal Theorem).
Indeed, suppose $\Gamma\included\Sn$, and every $\Delta$ in $\powf{\Gamma}$
has a model $\str A_{\Delta}$.
If $\sigma\in\Gamma$, let
\begin{equation*}
  [\sigma]=\{\Delta\in\powf{\Gamma}\colon\sigma\in\Delta\}.
\end{equation*}
Then for all $\Delta$ in $\powf{\Gamma}$,
\begin{equation*}
  \Delta\in\bigcap_{\sigma\in\Delta}[\sigma].
\end{equation*}
Thus $\{[\sigma]\colon\sigma\in\Gamma\}$ 
generates a proper filter on $\powf{\Gamma}$.
By the Prime Ideal Theorem,
this filter is included in an ultrafilter $\mathscr U$.
Let
\begin{equation*}
  A=\prod_{\Delta\in\powf{\Gamma}}A_{\Delta},
\end{equation*}
and if $a$ is an element $(a_{\Delta}\colon\Delta\in\powf{\Gamma})$ of $A$,
let $a$ be interpreted in $\str A_{\Delta}$ as $a_{\Delta}$.
For all $\sigma$ in $\sig(A)$, let
\begin{equation*}
  \bv{\sigma}=\{\Delta\in\powf{\Gamma}\colon\str A_{\Delta}\models\sigma\}.
\end{equation*}
Finally, let
\begin{equation*}
  T=\{\sigma\in\Sn[\sig(A)]\colon\bv{\sigma}\in\mathscr U\}.
\end{equation*}
Then $\Gamma\included T$, since if $\sigma\in\Gamma$, 
then $[\sigma]\included\bv{\sigma}$, and $[\sigma]\in\mathscr U$,
so $\bv{\sigma}\in\mathscr U$.
Also, if $\{\sigma_k\colon k<n\}\included T$, then
\begin{equation*}
  \left\lVert\bigwedge_{k<n}\sigma_k\right\rVert=\bigcap_{k<n}\bv{\sigma_k},
\end{equation*}
which is in $\mathscr U$, so in particular it is nonempty,
which means the set $\{\sigma_k\colon k<n\}$ has a model.
By the Compactness Theorem, $T$ has a model $\str C$,
and then $T=\Th{\str C}$.

We may assume $A/\mathscr U\included C$.
Then $\str C$ has a substructure $\str B$ whose universe $B$
is precisely $A/\mathscr U$;
for if $F$ is an $n$-ary operation symbol in $\sig$ for some $n$ in $\N$,
then
\begin{equation*}
  F^{\str C}(a^0/\mathscr U,\dots,a^{n-1}/\mathscr U)
=(F^{\str A_{\Delta}}(a^0_{\Delta},\dots,a^{n-1}_{\Delta})\colon\Delta\in\powf{\Gamma})
/\mathscr U,
\end{equation*}
so $B$ is closed under the operations of $\str C$.
Thus
\begin{equation*}
  \str B\included\str C.
\end{equation*}
\L o\'s's Theorem is then 
\begin{equation*}
  \str B\preccurlyeq\str C,
\end{equation*}
that is, for all $\sigma$ in $\Sn[\sig(B)]$ or $\Sn[\sig(A)]$,
\begin{equation*}
  \str B\models\sigma\iff\str C\models\sigma.
\end{equation*}
To prove this,
by the \textbf{Tarski--Vaught Test,}
it is enough to show that, for all formulas $\phi(x)$ of $\sig(A)$,
if
\begin{equation*}
  \str C\models\Exists x\phi(x),
\end{equation*}
then for some $b$ in $B$, $\str C\models\phi(b)$.
So we show this.
If $\str A_{\Delta}\models\Exists x\phi(x)$,
then for some $b_{\Delta}$ in $A_{\Delta}$, $\str A_{\Delta}\models\phi(b_{\Delta})$.
Otherwise let $b_{\Delta}$ be arbitrary.
Now let
\begin{equation*}
  b=(b_{\Delta}\colon\Delta\in\powf{\Gamma})/\mathscr U.
\end{equation*}
So \L o\'s's Theorem holds.
Note however that we used the Axiom of Choice to obtain $b$.

Conversely, the following is shown by Howard \cite{MR0384548}:

\begin{theorem}
The Axiom of Choice follows from \L o\'s's Theorem and the Prime Ideal Theorem.
\end{theorem}

\begin{proof}
Suppose $\mathscr A$ is a set of nonempty sets 
with no \textbf{choice function,} that is, 
no function $f$ from $\mathscr A$ to $\bigcup\mathscr A$ such that, 
for all $X$ in $\mathscr A$, $f(X)\in X$.
Let
\begin{gather*}
  \Omega=\bigcup\mathscr A\cup\mathscr A,\\
R=\left\{(x,Y)\in\bigcup\mathscr A\times\mathscr A\colon x\in Y\right\}
\cup\left\{(y,y)\colon y\in\bigcup\mathscr A\right\}.
\end{gather*}
Then
\begin{equation*}
  (\Omega,R)\models\Forall y\Exists xx\mathrel Ry.
\end{equation*}
Now, the subset
\begin{equation*}
\{\mathscr X\included\mathscr A\colon
\text{$\mathscr X$ has no choice function}\}
\end{equation*}
of $\pow{\mathscr A}$ is a proper ideal on $\mathscr A$,
so by the Prime Ideal Theorem,
its complement includes an ultrafilter $\mathscr U$ on $\mathscr A$.
This embeds in an ultrafilter $\mathscr U^*$ on $\Omega$.
by \L o\'s's Theorem,
\begin{equation*}
  (\Omega,R)^{\Omega}/\mathscr U^*\models\Forall y\Exists xx\mathrel Ry.
\end{equation*}
Replacing $y$ with $(i\colon i\in\Omega)/\mathscr U^*$,
we get $(a_i\colon i\in\Omega)/\mathscr U^*$ 
such that $\mathscr U$ contains $\{i\in\Omega\colon a_i\mathrel Ri\}$.
Let
\begin{align*}
  C
&=\{X\in A\colon a_X\mathrel RX\}\\
&=\{X\in A\colon a_X\in X\}.
\end{align*}
Then $X\mapsto a_X$ is a choice function on $C$.
But $C\in\mathscr U$, so by definition of $\mathscr U$,
$C$ cannot have a choice function.
This contradiction implies that $\mathscr A$ must have had a choice function.
\end{proof}

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

\def\rasp{\leavevmode\raise.45ex\hbox{$\rhook$}} \def\cprime{$'$}
  \def\cprime{$'$} \def\cprime{$'$} \def\cprime{$'$}
\begin{thebibliography}{1}

\bibitem{MR94e:03002}
Wilfrid Hodges.
\newblock {\em Model theory}, volume~42 of {\em Encyclopedia of Mathematics and
  its Applications}.
\newblock Cambridge University Press, Cambridge, 1993.

\bibitem{MR0384548}
Paul~E. Howard.
\newblock {\L}o{\'s}' theorem and the {B}oolean prime ideal theorem imply the
  axiom of choice.
\newblock {\em Proc. Amer. Math. Soc.}, 49:426--428, 1975.

\bibitem{MR1373196}
Abraham Robinson.
\newblock {\em Non-standard analysis}.
\newblock Princeton Landmarks in Mathematics. Princeton University Press,
  Princeton, NJ, 1996.
\newblock Reprint of the second (1974) edition, With a foreword by Wilhelmus A.
  J. Luxemburg.

\bibitem{MR798475}
Herman Rubin and Jean~E. Rubin.
\newblock {\em Equivalents of the axiom of choice. {II}}, volume 116 of {\em
  Studies in Logic and the Foundations of Mathematics}.
\newblock North-Holland Publishing Co., Amsterdam, 1985.

\end{thebibliography}


\end{document}
