\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*}
x0\implies xz0$.
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 u0\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 x0\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**}(-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 xN$, 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>}[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**