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

%\usepackage[notref,notcite]{showkeys}

\usepackage{scrpage2}
\pagestyle{scrheadings}
\clearscrheadings
\ofoot{\pagemark}
\automark[section]{section}
\refoot{Infinitesimal Analysis}
\lofoot{\headmark}
%\ifoot{Infinitesimal analysis}

\newcommand{\mysection}{\section}


\usepackage{relsize}
\renewenvironment{quote}{\begin{list}{}
{\relscale{.90}\setlength{\leftmargin}{0.05\textwidth}
\setlength{\rightmargin}{\leftmargin}}
\item\relax}
{\end{list}}

\usepackage{url,hfoldsty,upgreek}
\usepackage[neverdecrease]{paralist}
\usepackage{verbatim,relsize}
\usepackage[all]{xy}
\usepackage{amsmath,amssymb,amsthm,mathrsfs,amscd}
\allowdisplaybreaks
\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{\pow}[1]{\mathscr P(#1)}
\DeclareMathOperator{\supp}{supp}
\DeclareMathOperator{\support}{supp}
%\DeclareMathOperator{\Support}{Supp}
%\newcommand{\supp}[1]{\support(#1)}
\newcommand{\Supp}[1]{\support[#1]}
\newcommand{\Forall}[1]{\forall#1\;}
\newcommand{\st}{{}^*\!}
\newcommand{\stR}{{}^*\R}
\newcommand{\stN}{{}^*\N}
\newcommand{\lto}{\rightarrow}
\newcommand{\liff}{\leftrightarrow}
\newcommand{\bv}[1]{\lVert#1\rVert}
\newcommand{\sig}{\mathscr S}
\newcommand{\abs}[2][]{\lvert#2\rvert_{#1}}
\newcommand{\included}{\subseteq}
\newcommand{\pincluded}{\subset}
\newcommand{\Exists}[1]{\exists#1\;}
\newcommand{\str}[1]{\mathfrak{#1}}
\newcommand{\units}[1]{#1{}^{\times}}
\newcommand{\divides}{\mid}
\newcommand{\ndivides}{\nmid}
\DeclareMathOperator{\dee}{d}

%\newcommand{\bi}{\mathfrak I} % ideal of boolean ring
%\newcommand{\bmi}{\mathfrak M} % maximal ideal of boolean ring

%\newcommand{\gpgen}[1]{\langle#1\rangle}
%\newcommand{\Abs}[1]{\lVert#1\rVert}
\DeclareMathOperator{\stpt}{st}
\newcommand{\stp}[1]{\stpt\left(#1\right)}
\newcommand{\inv}{^{-1}}
%\newcommand{\gid}{\mathrm e}
%\newcommand{\up}[1]{{}^*\!#1}
%\newcommand{\up}[1]{{}^*#1}
%\newcommand{\uS}[2][S]{{}^{(#1)}#2}
%\newcommand{\met}{\mathrm d}

\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\renewcommand{\setminus}{\smallsetminus}
\renewcommand{\emptyset}{\varnothing}
\renewcommand{\phi}{\varphi}
\renewcommand{\epsilon}{\varepsilon}
\renewcommand{\amalg}{\sqcup}
\renewcommand{\models}{\vDash}
\newcommand{\nmodels}{\nvDash}

%\usepackage{chngcntr}
%\counterwithout{equation}{chapter}
%\renewcommand{\theequation}{\fnsymbol{equation}}


\newtheorem{theorem}{Theorem}
\newtheorem*{corollary}{Corollary}
\begin{document}

\title{Infinitesimal analysis}
\subtitle{Also known as\\
nonstandard analysis}
\author{David Pierce}
\date{September 1, 2015}
\publishers{Matematik B\"ol\"um\"u\\
Mimar Sinan G\"uzel Sanatlar \"Universitesi\\
\url{mat.msgsu.edu.tr/~dpierce/}}
\maketitle\thispagestyle{empty}

\begin{abstract}
These notes are based on my course,
officially called
Rudiments of Nonstandard Analysis,
given 
August 10--22, 2015,
at the Nesin Matematik K\"oy\"u,
Kayser Da\u g\i\ Mevkii,
\c Sirince, Sel\c cuk, \.Izmir, Turkey.
I gave similar courses in earlier years.
Before the course of 2009,
I typed up notes on everything that I might possibly want to talk about,
if I had time.
I revised the notes before the 2010 course.
In 2014, after each lecture,
I typed up notes of what I actually \emph{had} talked about;
later I tried to polish them.
I used these notes in 2015,
but did not follow them carefully.
I created the present notes
as I did the 2014 notes,
though with (perhaps even more)
embellishments, omissions, and rearrangements.

\end{abstract}

\tableofcontents

\mysection{Preliminary discussion}

Throughout these notes,
the symbols $\N$ and $\upomega$
represent what I would call 
the \emph{number-theorist's natural numbers}
and the \emph{set-theorist's natural numbers,}
respectively:
%More precisely,
\begin{align*}
	\N&=\{1,2,3,\dots\},&
	\upomega&=\{0,1,2,\dots\}.
\end{align*}
If the proof of a theorem is not supplied,
it is an exercise for the reader.

High-school algebra 
%(as opposed to ``abstract algebra'')
is largely a study
of the properties of arbitrary \emph{ordered fields,}
such as the ordered field $\Q$ of \emph{rational numbers}
or the ordered field $\R$ of \emph{real numbers.}
Calculus is a study of $\R$ as a \emph{complete} ordered field.
Here \textbf{completeness} is the property whereby every nonempty set of numbers
with an upper bound has a \emph{least upper bound,} or \textbf{supremum.}

Suppose $f$ is a function from $\R$ to itself
(that is, $f\colon\R\to\R$),
and $a$ and $L$ are in $\R$.
We say $f$ has the \textbf{limit} $L$ at $a$,
and we may write either of
\begin{align}\label{eqn:lim}
	\lim_{x\to a}f(x)&=L,&\lim_af&=L,
\end{align}
provided that $f(x)$ is close to $L$
whenever $x$ is close to, but not equal to, $a$.
This is vague.
By the ``standard'' definition,
\eqref{eqn:lim} means
we can make $f(x)$ \emph{arbitrarily} close to $L$
by making $x$ \emph{sufficiently} close to
(though not equal to) $a$.
Here ``arbitrarily close'' means ``within $\epsilon$,
for any positive $\epsilon$ given to us.''
Then ``sufficiently close'' means ``within $\delta$,
where $\delta$ is positive and depends on $\epsilon$.''
More precisely then,
the ``standard'' definition of \eqref{eqn:lim} is that,
for all positive $\epsilon$ in $\R$,%%%%%
\footnote{I do not say ``for all $\epsilon>0$,''
because I prefer to treat the expression $\epsilon>0$
always as a \emph{sentence} (``$\epsilon$ is greater than $0$''),
not as a noun phrase (``$\epsilon$ that are greater than $0$''
or ``$\epsilon$ greater than $0$'').}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
for some positive $\delta$ in $\R$,%%%%%
\footnote{Alternatively, one may say,
``there exists a positive $\delta$ in $\R$ such that\dots''}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%
for all $x$ in $\R$,
if $0<\abs{x-a}<\delta$, then $\abs{f(x)-L}<\epsilon$.
Even more symbolically, the definition is,
\begin{multline*}
\Forall{\epsilon}\Bigl(\epsilon>0\lto\Exists{\delta}\bigl(\delta>0\land\Forall x{}\\
\bigl(0<\abs{x-a}\land\abs{x-a}<\delta\lto\abs{f(x)-L}<\epsilon\bigr)\Bigr),
\end{multline*}
which can also be written as
\begin{multline}\label{eqn:e-d}
\Forall{\epsilon}\Exists{\delta}\Forall x\Bigl(\epsilon>0\lto\delta>0\land{}\\
\bigl(0<\abs{x-a}\land\abs{x-a}<\delta\lto\abs{f(x)-L}<\epsilon\bigr)\Bigr).
\end{multline}
These two expressions are equivalent sentences of \emph{first-order logic,}
in which the letters $\epsilon$, $\delta$, and $x$
are \emph{bound variables.}
One could use other letters as bound variables instead;
but $\epsilon$ and $\delta$ are almost always the letters used,
as an aid to the memory, 
because the sentences are so logically complicated. 
It is complicated to have \emph{three} blocks of quantifiers,
as shown at the head of \eqref{eqn:e-d};
most definitions in algebra require at most two,
as in the axiom ensuring existence of multiplicative inverses in fields,
\begin{equation*}
\Forall x\Exists y(x\neq0\lto xy=1).
\end{equation*}
The axiom of associativity of multiplication,
\begin{equation*}
\Forall x\Forall y\Forall zx(yz)=(xy)z,
\end{equation*}
has three quantifiers,
but they form one block:
they are all universal.

\textbf{Infinitesimal} or \textbf{``nonstandard'' analysis} provides a way to define limits
without using any such letters as $\epsilon$ and $\delta$.
By the ``nonstandard'' definition, $\lim_af=L$, 
provided that, for all $x$,
if $x$ is \emph{infinitesimally close} to $a$,
without being equal to $a$,
then $f(x)$ is infinitesimally close to $L$.
Symbolically, the definition is
\begin{equation}\label{eqn:non}
\Forall x(x\simeq a\land x\neq a\lto f(x)\simeq L).
\end{equation}
This is evidently much simpler than \eqref{eqn:e-d},
although, as we shall see below,
there is a quantifier in the precise definition of
$a\simeq x$ and $f(x)\simeq L$.

\mysection{Non-Archimedean fields}

The adjective ``infinitesimal''
is obtained from the adjective ``infinite''
by adding a Latin ending, 
which corresponds to the English ordinal ending \mbox{``-th''}
seen in ``fourth,'' ``fifth,'' ``sixth,'' and so on.
The English ordinals are used also to denote fractional parts:
one fourth, or the fourth part, 
is one of four equal parts, or $1/4$.
Then an infinitesimal part is an ``infinitieth'' part, or $1/\infty$.

To be precise then, a number $a$ is \textbf{infinitesimal}
if, for all $n$ in $\N$,
\begin{equation*}
\abs a<\frac1n.
\end{equation*}
A number $b$ is \textbf{infinite} if,
for all $n$ in $\N$,
\begin{equation*}
n<\abs b.
\end{equation*}
Then $b$ is infinite if and only if $b\neq0$ and $1/b$ is infinitesimal.
The ``nonstandard'' definition \eqref{eqn:non}
can be spelled out as
\begin{multline*}
\Forall x\left(
\Forall n\Bigl(n\in\N\lto\abs{x-a}<\frac1n\Bigr)\land x\neq a\lto\right.\\
\left.\Forall n\Bigl(n\in\N\lto\abs{f(x)-L}<\frac1n\Bigr)\right)
\end{multline*}
and hence as
\begin{multline}\label{eqn:non-long}
\Forall x\Exists m\Forall n\left(\Bigl(m\in\N\land\abs{x-a}>\frac1m\Bigr)\lor{}\right.\\
\left.\Bigl(x\neq a\land\abs{f(x)-L}<\frac1n\Bigr)\right).
\end{multline}
Thus there are still three blocks of quantifiers.
But again, two of them can be hidden,
as in \eqref{eqn:non};
this cannot be done in \eqref{eqn:e-d}.
This makes the ``nonstandard'' definition of limit
simpler than the ``standard.''

However, there is a new complication
with the ``nonstandard'' definition.
The only infinitesimal in $\R$ is $0$,
and $\R$ contains no infinite numbers.
This follows from the theorem below.
Thus if the variable $x$ must always represent a real number,
then \eqref{eqn:non-long} is always true.
So we shall have to allow $x$ to be a ``nonstandard'' number,
in a sense that we shall develop.

An ordered field is \textbf{Archimedean} if, 
for every element $c$ of the field,
for some $n$ in $\N$,
\begin{equation*}
\abs c\leq n.
\end{equation*}
That is, an ordered field is Archimedean \emph{precisely}
when none of its elements is infinite.

\begin{theorem}\label{thm:Arch}
$\R$ is Archimedean.
\end{theorem}

\begin{proof}
If $\R$ had an infinite element,
then it would have a positive infinite element,
and this would be an upper bound of $\N$.
Then $\N$ would have a supremum, say $d$.
In this case, $d-1$ would not be an upper bound of $\N$,
so $d-1<n$ for some $n$ in $\N$,
and then $d<n+1$,
which means $d$ is not an upper bound of $\N$ either,
since $n+1\in\N$.
\end{proof}

There \emph{are} ordered fields that contain infinite and (therefore)
nonzero infinitesimal elements.
(Note that containing infinite elements
is not the same as containing infinitely \emph{many} elements.)
For one example, first we let
\begin{multline*}
\R[X]=\bigl\{a_0+a_1X+a_2X^2+\dots+a_nX^n\colon\\
n\in\upomega\And\{a_0,\dots,a_n\}\included\R\bigr\}.
\end{multline*}
Here $a_0+a_1X+a_2X^2+\dots+a_nX^n$ is also written as
\begin{equation*}
\sum_{k=0}^na_kX^k;
\end{equation*}
it is a \textbf{polynomial} in the variable $X$ over $\R$,
and if $a_n\neq0$, then $a_n$ is the \textbf{leading coefficient}
of the polynomial.
Also $0$ is the leading coefficient
of the polynomial $0$.
Then $\R[X]$ is a \textbf{ring} (that is, a commutative unital ring:
it has associative, commutative operations of addition and multiplication;
multiplication distributes over addition;
there are additive and multiplicative identities;
and there are additive inverses).
We can form fractions with the elements of $\R[X]$,
just as the rational numbers are formed from the integers.
Thus we define
\begin{equation*}
\R(X)=\left\{\frac fg\colon f\in\R[X]\And g\in\R[X]\setminus\{0\}\right\},
\end{equation*}
which is the field of \textbf{rational functions} in $X$ over $\R$.
Here $f/g$ is the equivalence class of the ordered pair $(f,g)$
with respect to the equivalence relation $\sim$ given by
\begin{equation*}
(f,g)\sim(h,k)\iff fk=hg.
\end{equation*}

\begin{theorem}
$\R(X)$ is an ordered field with respect to the relation $<$ defined by
\begin{equation*}
\frac fg>0\iff\frac ab>0,
\end{equation*}
where $f\in\R[X]$ and $g\in\R[X]\setminus\{0\}$,
and $f$ and $g$ have leading coefficients $a$ and $b$ respectively.
In the ordered field,
$X$ is positive and infinite.
\end{theorem}

\mysection{Ultrafilters}

We shall denote by
\begin{equation*}
\R^{\upomega}
\end{equation*}
the set of functions from $\upomega$ to $R$,
that is, the set of real-valued sequences on $\upomega$.
The same such sequence can be denoted by any of the expressions
\begin{align*}
	&(a_0,a_1,a_2,\dots),&&(a_k\colon k\in\upomega),&&a.
\end{align*}
These sequences can be added, subtracted, and multiplied term by term:
\begin{align*}
	a\pm b&=(a_k\pm b_k\colon k\in\upomega),&
	a\cdot b=(a_k\cdot b_k\colon k\in\upomega).
\end{align*}
Then $\R^{\upomega}$ is a ring,
like $\R[X]$.
For each $n$ in $\upomega$,
there is an element $\chi^n$ of $\R^{\upomega}$, where
\begin{equation*}
\chi^n{}_m=
\begin{cases}
1,&\text{ if }n=m,\\
0,&\text{ if }n\neq m.
\end{cases}
\end{equation*}
Then the set $\{\chi^n\colon n\in\upomega\}$
generates a proper ideal of $\R^{\upomega}$.
Let this ideal be included in a maximal ideal $M$:
this exists by the \emph{Maximal Ideal Theorem}
(see page \pageref{MITh}).
We shall do infinitesimal analysis in the field
\begin{equation*}
\R^{\upomega}/M.
\end{equation*}
If $a\in\R^{\upomega}$, we define
\begin{equation*}
\supp(a)=\{k\in\upomega\colon a_k\neq0\};
\end{equation*}
this is the \textbf{support} of $a$.
Thus $\supp\colon\R^{\upomega}\to\pow{\upomega}$.
Like any function, the support function induces two additional functions,
as follows.
If $A\included\R^{\upomega}$
and $B\included\pow{\upomega}$,
we have
\begin{gather*}
\supp[A]=\{\supp(x)\colon x\in A\},\\
\supp\inv(B)=\{x\in\R^{\upomega}\colon\supp(x)\in B\}.
\end{gather*}
Then
\begin{align*}
	A&\included\supp\inv(\supp[A]),&
	B&=\supp[\supp\inv(B)].
\end{align*}
The ideal of $\R^{\upomega}$ generated by $\{\chi^n\colon n\in\upomega\}$
consists of the functions from $\upomega$ to $\R$
having finite support;
also, if this ideal is $I$,
then $\supp[I]$ is the set of all finite subsets of $\upomega$.

\begin{theorem}\label{thm:id}
A subset $I$ of $\R^{\upomega}$ is an ideal of $\R^{\upomega}$
if and only if
\begin{equation}\label{eqn:I}
\supp\inv(\supp[I])=I
%\{x\in\R^{\upomega}\colon\supp x\in\Supp I\}=I
\end{equation}
and,
for all $X$ and $Y$ in $\pow{\upomega}$,
\begin{compactenum}[(1)]
\item
$\emptyset\in\supp[I]$,
\item
$X,Y\in\supp[I]\implies X\cup Y\in\supp[I]$,
\item
$X\included Y\And Y\in\supp[I]\implies X\in\supp[I]$.
\end{compactenum}
If $I$ and $J$ are distinct ideals of $R^{\upomega}$,
then
\begin{equation*}
\supp[I]\neq\supp[J].
\end{equation*}
A subset $I$ of $\R^{\upomega}$ is a maximal ideal of $\R^{\upomega}$
if and only if \eqref{eqn:I} and,
for all $X$ and $Y$ in $\pow{\upomega}$,
\begin{compactenum}[(1)]
\item
$\emptyset\in\supp[I]$ and $\upomega\notin\supp[I]$,
\item
$X,Y\in\supp[I]\implies X\cup Y\in\supp[I]$,
\item
$X\notin\supp[I]\implies\upomega\setminus X\in\supp[I]$.
\end{compactenum}
A maximal ideal $M$ of $\R^{\upomega}$ is nonprincipal
if and only if $\supp[M]$
contains every finite subset of $\upomega$.
\end{theorem}

It may be observed that $\pow{\upomega}$ is a ring
when the \textbf{sum} of two elements is defined as their symmetric difference,
and their \textbf{product} as their intersection:
\begin{align*}
	X+Y&=X\mathrel{\triangle}Y=(X\setminus Y)\cup(Y\setminus X),\\
	X\cdot Y&=X\cap Y.
\end{align*}
In this case
\begin{align*}
	0&=\emptyset,&
	1&=\upomega,&
	-X&=X.
\end{align*}
The ring $\pow{\upomega}$ is then a \textbf{Boolean ring}
because it satisfies
\begin{equation}\label{eqn:x^2=x}
\Forall xx^2=x.
\end{equation}
From this axiom (along with the ring axioms), it follows that
\begin{equation}\label{eqn:2x=0}
\Forall x2x=0,
\end{equation}
or $\Forall x-x=x$.
Indeed, from \eqref{eqn:x^2=x} we have
$2x=(2x)^2=4x^2=4x$,
and then \eqref{eqn:2x=0}.
Now part of the last theorem can be formulated as follows.

\begin{theorem}
Let $I\included\pow{\upomega}$.
\begin{compactenum}
\item
$I$ is an ideal of $\pow{\upomega}$
if and only if $\supp\inv[I]$ is an ideal of $\R^{\upomega}$.
\item
$I$ is a maximal ideal of $\pow{\upomega}$
if and only if $\supp\inv[I]$ is a maximal ideal of $\R^{\upomega}$.
\end{compactenum}
\end{theorem}

But it will be more useful to think of ideals of $\pow{\upomega}$
in the terms of Theorem \ref{thm:id},
rather than in the usual terms of ring theory.
In fact, it will be useful to replace the notion of an ideal
with a ``dual'' notion, as follows.
A subset $F$ of $\pow{\upomega}$ is a 
\textbf{filter of} $\pow{\upomega}$ and a
\textbf{filter on} $\upomega$
if for all $X$ and $Y$ in $\pow{\upomega}$,
\begin{compactenum}[(1)]
\item
$\upomega\in F$,
\item
$X,Y\in F\implies X\cap Y\in F$,
\item
$X\in F\And X\included Y\implies Y\in F$.
\end{compactenum}
Thus $I$ is an ideal of $\pow{\upomega}$
if and only if $\{\upomega\setminus X\colon X\in I\}$
is a filter on $\upomega$.
A subset $\mathscr U$ of $\pow{\upomega}$ is an \textbf{ultrafilter on} $\upomega$
if for all $X$ and $Y$ in $\pow{\upomega}$,
\begin{compactenum}[(1)]
\item
$\upomega\in\mathscr U$ and $\emptyset\notin\mathscr U$,
\item
$X,Y\in\mathscr U\implies X\cap Y\in\mathscr U$,
\item
$X\notin\mathscr U\implies\upomega\setminus X\in\mathscr U$.
\end{compactenum}
Thus $M$ is a maximal ideal of $\pow{\upomega}$
if and only if $\{\upomega\setminus X\colon X\in M\}$
is an ultrafilter on $\upomega$;
moreover, in this case,
\begin{equation*}
\{\upomega\setminus X\colon X\in M\}=\pow{\upomega}\setminus M.
\end{equation*}
Suppose $\mathscr U$ is a \emph{nonprincipal}
ultrafilter on $\upomega$.
By Theorem \ref{thm:id},
$\mathscr U$ must contain every \textbf{cofinite} subset of $\upomega$,
that is, every subset whose complement is finite.
We may think of the elements of $\mathscr U$ as \textbf{large,}
and all other subsets of $\upomega$ as \textbf{small.}
Thus:
\begin{compactenum}[(1)]
\item
every set is large or small, but not both;
\item
the small sets are precisely the complements of the large sets;
\item
all finite sets are small, and so their complements are large;
\item
the union of two finite sets is small,
and the intersection of two large sets is large.
\end{compactenum}
However, some infinite sets will be small.
If $\upomega$ is a \emph{disjoint} union $A\sqcup B$,
then exactly one of $A$ and $B$ is large.
Hence if $\upomega=A_0\sqcup\dots\sqcup A_{n-1}$, 
%and $A_i\cap A_j=\emptyset$ whenever $i<j<n$,
then $A_i$ is large for exactly one index $i$.

\mysection{Application to K\"onig's Lemma}

In considering ultrafilters,
we can replace $\upomega$ with any infinite set.
This allows us to prove theorems like the following,
which need not have anything to do with calculus.

For present purposes,
a \textbf{tree} is an ordered set%%%%%
\footnote{As I use the term,
an \emph{ordered set} is a set equipped with a binary relation
that is irreflexive and transitive.
If any two distinct elements of the set are comparable
by means of the ordering,
then this ordering is \emph{linear.}
Thus an ordered set is what is often called a ``partially'' ordered set,
even though the ordering might be ``total,'' that is, linear.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%
$(T,<)$
where, for every $a$ in $T$,
the set $\{x\in T\colon x<a\}$
of elements that are \emph{below} $a$
is linearly ordered and, moreover,
well-ordered.
This well-ordered set then has the order-type of an ordinal,
which is called the \textbf{height} of $a$.
If $a$ has height $\alpha+1$,
and $b$ has height $\alpha$,
and $b<a$, then $a$ is a \textbf{successor} of $b$.
In a \textbf{finitely branching} tree,
every element has only finitely many successors.%%%%%
\footnote{We are not going to refer to successors again.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
A \textbf{branch} of a tree is a maximal 
linearly ordered subset.

\begin{theorem}[K\"onig's Lemma]
Every infinite finitely branching tree
has an infinite branch.
\end{theorem}

\begin{proof}
Let $(T,<)$ be such a tree,
and let $\mathscr U$ be a nonprincipal ultrafilter on $T$.
Being finitely branching,
$T$ can have only finitely many elements of each finite height.
Suppose $n\in\upomega$,
and the elements of $T$ of height $n$ are $a^0$, \dots, $a^{m-1}$.
If $i<m$, define
\begin{equation*}
A_i=\{x\in T\colon x\geq a^i\};
\end{equation*}
and let
\begin{equation*}
A_m=\left\{x\in T\colon\bigvee_{i<m}x<a^i\right\}.
\end{equation*}
Then
\begin{equation*}
T=A_0\sqcup\dots\sqcup A_{m-1}\sqcup A_m,
\end{equation*}
a disjoint union of $m+1$ sets.
Since the set $A_m$ is small (being finite),
exactly one of the other sets is large.
Supposing $A_i$ is large, let $b_n=a^i$.
Then the infinite set $\{b_n\colon n\in\upomega\}$ is linearly ordered;
for if $m$ and $n$ are in $\upomega$, then,
being large, the sets $\{x\in T\colon x\geq b_m\}$ and
$\{x\in T\colon x\geq b_n\}$ have a common element $c$,
and then $b_m\leq c$ and $b_n\leq c$,
so $b_m$ and $b_n$ must be comparable,
by the definition of a tree.
\end{proof}

An alternative approach to K\"onig's Lemma
sets the stage for our analysis of $\R$.
For any set $A$,
we define $A^{\upomega}$ as we did $\R^{\upomega}$.

\begin{theorem}\label{thm:eq}
For any set $A$, for any ultrafilter $\mathscr U$ on $\upomega$,
the binary relation $\sim$ on $A^{\upomega}$ given by
\begin{equation*}%\label{eqn:eq}
a\sim b\iff\{k\in\upomega\colon a_k=b_k\}\in\mathscr U
\end{equation*}
is an equivalence relation.
\end{theorem}

Given an ultrafilter $\mathscr U$ on $A$
and an element $a$ of $A^{\upomega}$,
we may denote by any of
\begin{align*}
	&[a],&
	&[a_0,a_1,a_2,\dots],&
	&[a_k\colon k\in\upomega]
\end{align*}
the equivalence-class of $a$ with respect to $\sim$
as in the theorem.
We could write $[a]_{\mathscr U}$ for $[a]$;
but we shall not be interested in changing the ultrafilter.
We shall however denote the set of all of the classes $[a]$ by
\begin{equation*}
A^{\upomega}/\mathscr U.
\end{equation*}
This is an \textbf{ultrapower} of $A$.

\begin{theorem}\label{thm:embed}
For any set $A$,
for any ultrafilter $\mathscr U$ on $\upomega$,
the map $x\mapsto[x,x,x,\dots]$ is an embedding
of $A$ in $A^{\upomega}/\mathscr U$.
If $A$ is finite or $\mathscr U$ is principal,
then this embedding is also surjective;
otherwise it is not.
\end{theorem}

\begin{proof}
If $a$ and $b$ in $A^{\upomega}$
are \emph{constant} sequences,
then the set
$\{k\in\upomega\colon a_k=b_k\}$ is either $\upomega$ or $\emptyset$.
The former must be true if $[a]=[b]$;
but in that case, $a=b$.

Now suppose $a$ is an arbitrary element of $A^{\upomega}$.
If $A$ is a finite set $\{b^0,\dots,b^{n-1}\}$,
then for some unique $i$ less than $n$,
we must have $\{k\in\upomega\colon a_k=b^i\}\in\mathscr U$.
In this case, $[a]=[b^i,b^i,b^i,\dots]$,
and so the indicated embedding is surjective.

If $\mathscr U$ is principal,
this means it is $\{X\in\pow{\upomega}\colon i\in X\}$ 
for some $i$ in $\upomega$.
In particular, $\{i\}\in\mathscr U$.
Then $[a]=[a_i,a_i,a_i,\dots]$,
so the embedding is again surjective.

If $A$ is infinite,
then there is an element $a$ of $A^{\upomega}$
with no repeated terms.
If also $\mathscr U$ is nonprincipal,
then for all $b$ in $A$,
the set $\{k\in\upomega\colon a_k=b\}$
has at most one element, so it is not large,
and thus $[a]$ is not in the image of the embedding.
\end{proof}

We shall usually treat the embedding of the theorem
as an inclusion, identifying $a$ in $A$
with $[a,a,a,\dots]$ in $A^{\upomega}/\mathscr U$.
Thus, by the theorem,
$A^{\upomega}/\mathscr U\setminus A$ is nonempty
if and only if $A$ is infinite and $\mathscr U$ is nonprincipal.
Because of the this,
we shall not be interested in principal ultrafilters,
though some of our claims will be true for them
as well as for nonprincipal ultrafilters.

\begin{theorem}\label{thm:A<}
For any ordered set $(A,<)$,
for any ultrafilter $\mathscr U$ on $\upomega$,
there is an ordering $\st{<}$ on $T^{\upomega}/\mathscr U$ given by
\begin{equation*}
[a]\mathrel{\st{<}}[b]\iff\{k\in\upomega\colon a_k<b_k\}\in\mathscr U.
\end{equation*}
The embedding $x\mapsto[x,x,x,\dots]$ respects the orderings:
for all $a$ and $b$ in $A$,
\begin{equation*}
a<b\iff[a,a,a,\dots]\mathrel{\st{<}}[b,b,b,\dots].
\end{equation*}
\end{theorem}

Finally we have the promised alternative formulation and proof
of K\"onig's Lemma:

\begin{theorem}\label{thm:T}
Suppose $(T,<)$ is an infinite, finitely branching tree,
$\mathscr U$ is nonprincipal ultrafilter on $\upomega$,
and $\st{<}$ is ordering of $T^{\upomega}/\mathscr U$,
induced as in the previous theorem.
Then the tree $(T,<)$ has infinite branches,
namely the sets
\begin{equation*}
\{x\in T\colon x\mathrel{\st{<}}a\},
\end{equation*}
where $a\in(T^{\upomega}/\mathscr U)\setminus T$.
\end{theorem}

\mysection{Limits}

We return to considering fields,
whose ultrapowers can be understood in terms of maximal ideals.
The following is true for all ordered fields, and not just $\R$;
but our main interest is in $\R$.

\begin{theorem}\label{thm:Ro/M}
Let $M$ be a nonprincipal maximal ideal of $\R^{\upomega}$,
and let $\mathscr U$ be the corresponding nonprincipal ultrafilter
on $\upomega$,
so that
\begin{equation*}
\mathscr U=\{\upomega\setminus\supp(x)\colon x\in M\}=\pow{\upomega}\setminus\supp[M].
\end{equation*}
The quotient $\R^{\upomega}/M$,
which is a field,
is precisely the ultrapower $\R^{\upomega}/\mathscr U$.
This field is an \emph{ordered} field
with respect to the relation $\st{<}$ of Theorem \ref{thm:A<},
and the embedding $x\mapsto[x,x,x,\dots]$
of $\R$ in $\R^{\upomega}/\mathscr U$
is an embedding of ordered fields.
The element $[0,1,2,\dots]$ of $\R^{\upomega}/\mathscr U$
is positive and infinite,
and the element $[1,1/2,1/3,\dots]$ is positive and infinitesimal.
\end{theorem}

By \L o\'s's Theorem (Theorem \ref{thm:Los} below),
all sentences of \emph{first-order logic}
will be true in $\R^{\upomega}/\mathscr U$
if and only if they are true in $\R$.
The same will be true
when $\R$ is replaced by an arbitrary structure,
such as a tree, as in Theorem \ref{thm:T}.
Then also Theorems \ref{thm:eq}, \ref{thm:embed}, \ref{thm:A<}, and \ref{thm:Ro/M}
will turn out to have been special cases of \L o\'s's Theorem.

The formal definition of a first-order logic is recursive.
For now, we shall just say that
\begin{compactenum}[(1)] 
\item
first-order sentences are \emph{finite,} and 
\item
their variables range only over \emph{individuals.}
\end{compactenum}
Here are corresponding examples of non-first-order sentences.
\begin{asparaenum}
\item
By the last theorem,
$\R^{\upomega}/\mathscr U$ differs from $\R$ in having infinite elements.
That is, the sentence written as one of
\begin{align*}
&\Exists x(x>1\land x>2\land x>3\land\cdots),&
&\Exists x\bigwedge_{n\in\N}x>n
\end{align*}
is true in $\R^{\upomega}/\mathscr U$, but false in $\R$.
Being infinite, 
in the sense of involving the conjunction of infinitely many formulas,
this sentence is not first order.
\item
In proving Theorem \ref{thm:Arch} (that $\R$ has no infinite elements),
we showed that an ordered field with infinite elements cannot be complete.
In particular, the sentence
\begin{multline*}
\Forall X\Forall y\Exists z\Forall v\Exists u\\
\biggl(
y\in X\lto
\Bigl((v\in X\lto v\leq z)\land
\bigl((u\in X\land u>v)\lor z\leq v\bigr)\Bigr)\biggr),
\end{multline*}
%(``For all $X$, if $X$ has an element $y$,
%then for some $z$, 
%$z$ is an upper bound of $X$,
%that is, $z$ is at least as great as every element $v$ of $X$,
%and moreover,
%every $v$ either is not an upper bound of $X$,
%because it is less than some element $u$ of $X$,
%or else $v$ is at least as great as $z$''),
which expresses completeness, is true in $\R$,
but false in $\R^{\upomega}/\mathscr U$.
The sentence is not first order,
because the variable $X$ ranges over sets as such,
not individuals.
\end{asparaenum}

We may denote the ordered field $\R^{\upomega}/\mathscr U$ by
\begin{equation*}
\stR.
\end{equation*}
We now establish the equivalence of 
the standard and nonstandard definitions of limit.

\begin{theorem}\label{thm:f}
Suppose $f$ is a function from $\R$ to itself, and $a$ and $L$ are in $\R$.
There is a well-defined function $\st f$ from $\stR$ to itself
given by
\begin{equation*}
\st f[x]=[f(x_k)\colon k\in\upomega].
\end{equation*}
Then $\lim_af=L$ if and only if, for all $x$ in $\R^{\upomega}$,
\begin{equation*}
[x]\simeq a\And [x]\neq a\implies \st f[x]\simeq L.
\end{equation*}
\end{theorem}

\begin{proof}
For all $a$ and $b$ in $\R^{\upomega}$, we have
\begin{equation*}
\{k\in\upomega\colon a_k=b_k\}\included\{k\in\upomega\colon f(a_k)=f(b_k)\}.
\end{equation*}
If $[a]=[b]$, then the former set is large,
and therefore the latter set is large, which means
\begin{equation*}
[f(a_k)\colon k\in\upomega]=[f(b_k)\colon k\in\upomega].
\end{equation*}
Thus $\st f$ is well defined.

Suppose $\lim_af=L$, and $[x]\simeq a$, but $[x]\neq a$.
For all $n$ in $\N$,
for some positive $\delta$ in $\R$,
for all $k$ in $\upomega$,
if $0<\abs{x_k-a}<\delta$, then $\abs{f(x_k)-L}<1/n$.
Thus
\begin{equation}\label{eqn:xafL}
\{k\in\upomega\colon0<\abs{x_k-a}<\delta\}
\included
\{k\in\upomega\colon\abs{f(x_k)-L}<1/n\}.
\end{equation}
The former set is
\begin{equation*}
\{k\in\upomega\colon x_k\neq a\}\cap\{k\in\upomega\colon x_k-a<\delta\}
\cap
\{k\in\upomega\colon a-x_k<\delta\},
\end{equation*}
the intersection of three sets,
all of which are large,
since, respectively, $[x]\neq0$,
and $[x]-a<\delta$, and $a-[x]<\delta$.
So the intersection itself is large,
and therefore the latter set in \eqref{eqn:xafL}
%$\{k\in\upomega\colon\abs{f(x_k)-L}<1/n\}$
is large, which means
\begin{equation*}
\abs{\st f[x]-L}<\frac1n.
\end{equation*}
This being the case for all $n$ in $\N$,
$\st f[x]\simeq L$.

Now suppose $\lim_af\neq L$.
Then for some positive $\epsilon$ in $\R$,
for every $n$ in $\upomega$,
there is $x_n$ in $\R$ such that
$0<\abs{x_n-a}<1/(n+1)$,
but $\abs{f(x_n)-L}\geq\epsilon$.
Then $[x]\simeq a$, but $[x]\neq a$,
and $\abs{\st f[x]-L}\geq\epsilon$,
so $\st f[x]\not\simeq L$.
\end{proof}

The nonstandard definition makes proofs about limits easier,
at least once one has the following.

\begin{theorem}\label{thm:ideal}
In any ordered field,
the finite elements compose a sub-ring,
and the infinitesimal elements compose a maximal ideal of the ring of finite elements.
In fact the ideal is the only maximal ideal of the ring.
\end{theorem}

\begin{corollary}
In the ring of finite elements of any ordered field,
the relation $\simeq$ of being infinitesimally close
is an equivalence relation,
and
\begin{gather*}
a\simeq b\And c\simeq d\implies a+c\simeq b+d\And ac\simeq bd,\\
a\simeq b\And a\not\simeq0\implies b\not\simeq0\And\frac1a\simeq\frac1b.
\end{gather*}
\end{corollary}

The ``standard'' proof of the following
involves taking different deltas for different epsilons,
and then taking the maximum.
The ``nonstandard'' proof is more straightforward.

\begin{theorem}
Suppose $\lim_af=L$ and $\lim_af=M$.
Then
\begin{align*}
	\lim_a(f+g)&=L+M,&
	\lim_a(fg)&=LM.
\end{align*}
If $L\neq0$, then
\begin{equation*}
\lim_a\frac1f=\frac1L.
\end{equation*}
\end{theorem}

\begin{proof}
Suppose $[x]\simeq a$, but $[x]\neq a$.
By hypothesis and Theorem \ref{thm:f},
$\st f[x]\simeq L$ and $\st g[x]\simeq M$.
Then the corollary of Theorem \ref{thm:ideal}
yields the desired results.
\end{proof}

\mysection{Standard parts}

Every finite element $a$ of $\stR$
is infinitesimally close to a unique element $\stp a$ of $\R$,
namely
\begin{equation*}
\sup\{x\in\R\colon x<a\}.
\end{equation*}
This is the \emph{standard part} of $a$.
If $a$ is infinite, we may define $\stp a=\infty$.
Then the function $x\mapsto\stp x$ from $\stR$
to $\R\cup\{\infty\}$,
is an example of a \emph{place,}
as we shall see.

In Theorem \ref{thm:ideal},
if the ordered field is $K$,
and the ring of its finite elements is $R$,
then
\begin{equation*}
x\in K\setminus R\implies\frac1x\in R.
\end{equation*}
This means $R$ is a \textbf{valuation ring} of $K$,
at least if $R$ is different from $K$.
The definition does not require $K$ to be ordered.
Every valuation ring $R$ of a field $K$ has a unique maximal ideal $M$,
which is the complement of the multiplicative group $\units R$
of invertible elements of $R$.
Then two functions can be defined on $K$
as follows.
\begin{compactenum}
\item
The function $\phi$ with range $R/M\cup\{\infty\}$ given by
\begin{equation*}
\phi(x)=
\begin{cases}
x+M,&\text{ if }x\in R,\\
\infty,&\text{ if }x\in K\setminus R
\end{cases}
\end{equation*}
is a \textbf{place} of $K$.
\item
The function $v$ with range $\{0\}\cup\units K/\units R$
given by
\begin{equation*}
v(x)=
\begin{cases}
x\units R,&\text{ if }x\in\units K,\\
0,&\text{ if }x=0
\end{cases}
\end{equation*}
is a \textbf{valuation} of $K$.
Here
\begin{equation*}
v(x)=0\iff x=0,
\end{equation*}
and
\begin{align*}
v(-x)&=v(x),&
v(xy)&=v(x)\cdot v(y).
\end{align*}
The multiplicative group $\units K/\units R$
is linearly ordered by the rule
\begin{equation*}
x\units R\leq y\units R\iff\frac xy\in R,
\end{equation*}
and $0$ is declared to be less than every element of the group.
Then a strong triangle inequality holds, namely
\begin{equation*}
v(x+y)\leq\max(v(x),v(y)).
\end{equation*}
Thus the map $(x,y)\mapsto v(x-y)$ is a \emph{metric} on $K$.
\end{compactenum}
There are two standard classes of examples.
\begin{asparaenum}
\item
If $K$ is any field,
we can form the field $K(X)$ of rational functions in $X$ over $K$.
If $\alpha\in K$,
then the function $f\mapsto f(\alpha)$ is a place on $K(X)$.
Here, if $f(\alpha)$ is ``undefined,''
because it involves division by $0$,
then we define $f(\alpha)=\infty$.
Thus the range of the place is indeed $K\cup\{\infty\}$.
If $K$ is algebraically closed, like $\C$,
then every nonzero element of $K(X)$ can be written as
\begin{equation*}
\frac{p(X)}{q(X)}\cdot(X-\alpha)^n,
\end{equation*}
where $p$ and $q$ are polynomials that are not zero at $\alpha$,
and $n\in\Z$.
If $0<t<1$,
the valuation can be understood as taking the above element of $\units K$
to $t^n$.
In particular, according to the associated metric,
the sequence $(X^n\colon n\in\upomega)$ converges to $0$.
\item
If $p$ is a prime number, then $\Q$ has a valuation ring
%\begin{equation*}
%\{0\}\cup\left\{\frac xy\cdot p^n\colon\{x,y\}\included\Z\setminus\{0\}
%\And p\ndivides xy\And n\in\upomega\right\},
%\end{equation*}
consisting of the fractions having denominators that are indivisible by $p$.
The range of the associated place can be understood as $\F_p\cup\{\infty\}$.
Indeed, if $p\ndivides b$, 
then the place can be understood as taking $a/b$ 
to that element $c$ of $\units{\F_p}$
such that $a\equiv bc\pmod p$.
The associated valuation 
can be understood as the map taking $(a/b)\cdot p^n$ to $1/p^n$
(and $0$ to $0$).
In the associated metric,
the sequence $(p^n\colon n\in\N)$ converges to $0$,
and so
every series $\sum_{n=m}^{\infty}a_np^n$,
where $m\in\Z$ and $a_n\in\{0,\dots,p-1\}$,
has a sequence of partial sums that is a Cauchy sequence.
Such series then constitute the field of \textbf{$p$-adic numbers.}
This is a field that, like $\R$, 
is complete in the sense that all of its Cauchy sequences converge.
This notion of completeness should be distinguished from
the completeness of the \emph{ordering} of $\R$.
\end{asparaenum}

\mysection{Logic}

In the \textbf{first-order logic} of ordered fields,
the \textbf{atomic formulas} are the polynomial equations and inequalities.
Then the \textbf{formulas} are defined recursively:
\begin{compactenum}
\item
Every atomic formula is a formula.
\item
If $\phi$ and $\psi$ are formulas,
and $x$ is an individual variable
(that is, such a variable as may occur in an atomic formula),
then each of the expressions
\begin{align*}
	&\lnot\phi,&
	&(\phi\land\psi),&
	&\Exists x\phi
\end{align*}
is a formula.
\end{compactenum}
By this scheme, 
the expressions
\begin{align*}
	&(\phi\lor\psi),&
	&(\phi\lto\psi),&
	&(\phi\liff\psi),&
	&\Forall x\phi
\end{align*}
are abbreviations of the formulas
\begin{align*}
	&\lnot(\lnot\phi\land\lnot\psi),&
	&(\lnot\phi\lor\psi),&
	&(\phi\lto\psi)\land(\psi\lto\phi),&
	&\lnot\Exists x\lnot\phi
\end{align*}
respectively.

An occurrence of a variable $x$ in a formula is
\textbf{bound} if it enters the formula
as occurring in a formula $\Exists x\phi$;
otherwise the occurrence is \textbf{free.}
Thus, in the formula $(x=y\lor\Exists x\lnot\;x=y)$
(usually written as $x\neq y\lto\Exists xx\neq y$),
the first occurrence of $x$ is free,
but the other two occurrences are bound.

A formula in which no variable occurs freely
is a \textbf{sentence.}
By the definition to be given presently,
a sentence $\sigma$ is either \textbf{true} or \textbf{false}
in a given ordered field $K$, and we write
\begin{align*}
	K&\models\sigma,&
	K&\nmodels\sigma
\end{align*}
accordingly.
For now, 
we take the definition of the truth or falsity 
of an atomic sentence in $K$ as obvious.
Then for all sentences $\sigma$ and $\tau$,
\begin{gather*}
	K\models\lnot\sigma\iff K\nmodels\sigma,\\
	K\models(\sigma\land\tau)\iff K\models\sigma\And K\models\tau,
\end{gather*}
Note here that the two-shafted arrow $\iff$
is just an abbreviation of the English expression ``if and only if'';
and the ampersand $\And$ is an abbreviation of ``and.''
We could replace the abbreviations with the full expressions
without changing the mathematical meaning of what we are saying.
By contrast, we cannot replace the symbol $\land$ in the formula $(\sigma\land\tau)$
with anything else, because our purpose is to study the uses of such formulas as they are.

It remains to declare that
$K\models\Exists x\phi$ if and only if,
for some $a$ in $K$,
\begin{equation*}
K\models\phi(a).
\end{equation*}
Here $\phi(a)$ is the result 
of replacing each free occurrence of $x$ in $\phi$ with $a$.

We can prove \L o\'s's Theorem just for $\R$,
but a more general form may actually be easier to understand.
Suppose $(K_n\colon n\in\upomega)$ is an indexed family of ordered fields.
Then we can form the product
\begin{equation*}
\prod_{n\in\upomega}K_n,
\end{equation*}
namely the set of sequences $a$ or $(a_n\colon n\in\upomega)$,
where $a_n\in K_n$ for each $n$ in $\upomega$.
Let us denote the product also by $R$.
Each element $a$ of $R$
can be understood as a \textbf{constant symbol,}
whose \textbf{interpretation} in the ordered field $K_n$ is just $a_n$,
for each $n$ in $\upomega$.
In other words, $a$ \emph{means} $a_0$ in $K_0$,
and $a_1$ in $K_1$, and so forth.
Likewise, the identity of an abelian group is usually $0$,
and this \emph{means} $0$ in the additive group $\Z$; 
but it means $1$ in multiplicative groups like $\units{\R}$.
For an arbitrary element $b$ of $K_n$,
with $a$ in $R$ as before,
\begin{equation*}
K_n\models a=b\iff a_n=b.
\end{equation*}
Now let $\sig$ be the set
\begin{equation*}
\{+,0,-,{}\cdot{},1,<\}
\end{equation*}
of symbols: 
this is the \textbf{signature} of ordered fields.
The constant symbols in $\sig$
are only $0$ and $1$.
Using these, we can form the polynomials
\begin{align*}
	&\Bigl(\cdots\bigl((1+1)+1\bigr)+\cdots+1\Bigr),&
	-\Bigl(\cdots\bigl((1+1)+1\bigr)+\cdots+1\Bigr).
\end{align*}
According to the associativity of addition in every field,
these polynomials can be written unambiguously as
\begin{align*}
	&1+\dots+1,&&-(1+\dots+1).
\end{align*}
Every integer can be denoted by such an expression.
(Even $0$ can be so denoted, if we allow the ``empty'' sum.)
Thus, every equation or inequality of polynomials
with coefficients from $\Z$
can be understood as an atomic formula in the pure signature of ordered fields.
We may also introduce, as coefficients, 
new constant symbols
standing for elements of a particular ordered field or fields.
The new constant symbols can be called \textbf{parameters.}
With $R$ being $\prod_{n\in\upomega}K_n$ as above,
if $\sigma$ is a sentence in the signature $\sig\cup R$ of ordered fields
with parameters from $R$, we define
\begin{equation*}
\bv{\sigma}=\{n\in\upomega\colon K_n\models\sigma\}.
\end{equation*}
(In his \emph{Model Theory,}
Hodges calls this the \emph{Boolean value} of $\sigma$.)
Then by the definition of truth and falsity,
\begin{gather*}
	\bv{\lnot\sigma}=\upomega\setminus\bv{\sigma},\\
	\bv{(\sigma\land\tau)}=\bv{\sigma}\cap\bv{\tau},
\end{gather*}
and for all $a$ in $R$,
\begin{equation*}
\bv{\phi(a)}\included\bv{\Exists x\phi}.
\end{equation*}
Moreover, given the formula $\phi$ in which only $x$ occurs freely,
we can define $a$ in $R$ so that, for all $n$ in $\upomega$,
if $K_n\models\Exists x\phi$, then $K_n\models\phi(a_n)$,
but if $K_n\nmodels\Exists x\phi$, then $a_n$ is
an arbitrary element of $K_n$
(for example, $0$ or $1$).
In this case
\begin{equation}\label{eqn:bva}
\bv{\Exists x\phi}=\bv{\phi(a)}.
\end{equation}
Now let $\mathscr U$ be an ultrafilter on $\upomega$,
and let $T$ be the set of sentences $\sigma$ of $\sig\cup R$
such that
$\bv{\sigma}\in\mathscr U$.
Then\label{T}
$T$ contains
every sentence of $\sig\cup R$
that is true in every ordered field 
(in which the parameters have interpretations).
Moreover,
\begin{subequations}\label{eqn:T}
\begin{gather}\label{eqn:Tn}
	\lnot\sigma\in T\iff\sigma\notin T,\\
	(\sigma\land\tau)\in T\iff\sigma\in T\And\tau\in T,\\\label{eqn:TE}
\Exists x\phi\in T\iff
\text{for some $a$ in $R$, }
\phi(a)\in T.
\end{gather}
\end{subequations}
Now, suppose $F$ is some ordered field,
and every element of $R$
has an interpretation in $F$,
and every element of $F$ 
is the interpretation of an element of $R$.
The set of sentences of $\sig\cup R$
that are true in $F$
is the \textbf{(complete) theory of} $F$
in the indicated signature.
But then, by the definition of truth, this theory
has the properties of $T$ that we have just determined.
The converse will turn out to true as well:
by having the indicated properties,
$T$ must itself be the complete theory of some ordered field
(in which the elements of $R$ have interpretations).
We shall denote this ordered field
(whose theory is $T$) by
\begin{equation*}
\left.\prod_{n\in\upomega}K_n\right/\mathscr U
\end{equation*}
or just $R/\mathscr U$:
it is an \textbf{ultraproduct} of the ordered fields $K_n$.
For all $a$ and $b$ in $R$,
since
\begin{equation*}
R/\mathscr U\models a=b\iff\{k\in\upomega\colon a_k=b_k\},
\end{equation*}
we can understand the elements of $R/\mathscr U$ 
as being the equivalence classes $[a]$ or
\begin{equation*}
\bigl\{x\in R\colon\{k\in\upomega\colon a_k=x_k\}\bigr\},
\end{equation*}
where $a\in R$.

In the special case where each ordered field $K_n$ is $\R$,
then the ultraproduct $\left.\prod_{n\in\upomega}K_n\right/\mathscr U$
will be the ultrapower $\stR$, that is, $\R^{\upomega}/\mathscr U$.
This is an ordered field by Theorem \ref{thm:Ro/M},
and we may consider $\R$ as a subfield.
Then a (first-order) sentence $\sigma$ with parameters from $\R$
will be true in $\R$ if and only if it is true in $\stR$,
because $\bv{\sigma}$ in this case is either $\mathscr U$ or $\emptyset$.

A structure in which every sentence of a set of sentences is true
is a \textbf{model} of that set.
So we are going to show that the set $T$ above has a model.
This will give us (a special case of) \L o\'s's Theorem.
There is a sense in which we need not prove this theorem though,
just to do ``nonstandard,'' infinitesimal analysis.
Analysis is a study of $\R$, not $\stR$.
We shall not really use the latter itself,
but only its theory,
and we have this already.

\mysection{\L o\'s's Theorem}

Strictly speaking though, even to understand the theory $T$ above,
we need to do more work.
We should understand the structure of polynomials.
The symbols $+$, $-$, and $\cdot$ in $\sig$
are examples of \textbf{operation symbols,}
taking two, one, and two arguments respectively;
and polynomials are examples of \emph{terms.}

In an arbitrary signature, 
the \textbf{terms} are defined recursively as follows.
\begin{compactenum}
\item
every individual variable is a term.
\item
every constant symbol is a term.
\item
for every $n$ in $\N$,
if $F$ is an $n$-ary operation symbol
(that is, an operation symbol taking $n$ arguments),
and $t_i$ is a term when $i<n$, then the expression
\begin{equation*}
Ft_0\cdots t_{n-1}
\end{equation*}
is a term.
In case $n=2$, it is conventional to write $t_0\mathbin Ft_1$
instead of $Ft_0t_1$.
\end{compactenum}
A term is called \textbf{closed} if no variable occurs in it.
Thus closed terms are obtained 
by omitting the first condition in the definition of terms.

An \textbf{interpretation} of an $n$-ary operation symbol
on a set $A$
is a function from $A^n$ to $A$
(where $A^n$ can be understood as the set of functions
from $\{0,\dots,n-1\}$ to $A$).%%%%%
\footnote{I think this is the best way to understand $A^n$,
but many people understand it as the set of functions
from the set $\{1,\dots,n\}$ to $A$.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
If each constant symbol and operation symbol in a signature
has an interpretation on $A$,
then, recursively, each closed term of $\sig$
has an interpretation as an element of $A$.%%%%%
\footnote{An arbitrary term can be interpreted
as an operation on $A$;
but the best way of making this precise is not clear.
It might be best to interpret the term $x+y$
as a function from $A^{\{x,y\}}$ to $A$;
but then if this term occurs in a formula where the variable $z$ also occurs,
then we should interpret $x+y$ as a function from $A^{\{x,y,z\}}$ to $A$.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%

The symbol $<$ in the signature of ordered fields
is a binary \textbf{relation symbol.}
In an arbitrary signature,
the atomic formulas are of two kinds:
\begin{compactenum}
\item
There are equations $t_0=t_1$ of terms $t_0$ and $t_1$.
\item
For every $n$ in $\N$,
for every $n$-ary relation symbol in the signature,
if $t_i$ is a term when $i<n$, there is an atomic formula
\begin{equation*}
Rt_0\cdots t_{n-1}.
\end{equation*}
If $n=2$, 
it is conventional to write $t_0\mathrel Rt_1$ instead of $Rt_0t_1$.
\end{compactenum}
An \textbf{interpretation} of an $n$-ary relation symbol on a set $A$
is a subset of $A^n$.
An interpretation of all symbols in a signature $\sig$,
on a set, is a \textbf{structure} whose \textbf{universe} is the set.
If the set is $A$,
then the structure itself may be $\str A$
(the same letter in a more elaborate font),
and the interpretation of a symbol or closed term $s$
can be denoted by
\begin{equation*}
s^{\str A}.
\end{equation*}
Then the truth or falsity of an atomic sentence in $\str A$
has the obvious definition:
\begin{gather*}
	\str A\models t_0=t_1\iff t_0{}^{\str A}=t_1{}^{\str A},\\
	\str A\models Rt_0\cdots t_{n-1}\iff(t_0{}^{\str A},\dots,t_{n-1}{}^{\str A})\in R^{\str A}.
\end{gather*}
Now arbitrary sentences,
and their truth or falsity,
are defined as before.
We just have to note that,
unless otherwise specified,
every element of a set can be understood as a constant symbol
whose interpretation is itself.

We now have all of the ingredients for the full statement of \L o\'s's Theorem.
As we did when proving K\"onig's Lemma,
we can replace our usual index set $\upomega$
with an arbitrary index set.

\begin{theorem}[\L o\'s]\label{thm:Los}
In a signature $\sig$,
let $(\str A_i\colon i\in\Omega)$ be a family of structures
indexed by elements of some infinite set $\Omega$.
In the product $\prod_{i\in\Omega}A_i$
of the universes of the structures $\str A_i$,
let each element $(a_i\colon i\in\Omega)$
be considered as a new constant symbol,
interpreted in $\str A_i$ as $a_i$
for each $i$ in $\Omega$.
Let $\mathscr U$ be an ultrafilter on $\Omega$.
In the signature $\sig\cup\prod_{i\in\Omega}A_i$,
there is a new structure
\begin{compactenum}[(1)]
\item
whose complete theory consists precisely of those $\sigma$
such that
\begin{equation}\label{eqn:sigma}
\{i\in\Omega\colon\str A_i\models\sigma\}\in\mathscr U,
\end{equation}
and
\item
whose universe
consists of the interpretations of the elements of
\begin{equation*}
\prod_{i\in\Omega}A_i.
\end{equation*}
\end{compactenum}
In case each of the structures $\str A_i$
is the same structure $\str A$,
then this embeds in the new structure
under the map sending each $a$ in $A$
to the interpretation of the constant sequence $(a\colon i\in\Omega)$.
In this case, a sentence of $\sig\cup A$ is true in the new structure
if and only if it is true in $\str A$.
\end{theorem}

\begin{proof}
Let $B=\prod_{i\in\Omega}A_i$,
and let $T$ be the set of sentences of $\sig\cup B$
such that \eqref{eqn:sigma} holds.
As we have shown,
$T$ must have the properties in \eqref{eqn:T}.
In particular, by \eqref{eqn:Tn},
if $T$ has a model, then $T$ is the complete theory of this model.
So we want to show $T$ has a model 
whose universe consists of the interpretations 
of the elements of $B$.
In fact, this will follow from \eqref{eqn:T},
along with the observation that 
$T$ contains all sentences that are
\textbf{logically true,} that is,
true in all structures of the signature $\sig\cup B$.
Indeed, for all $a$, $b$, and $c$ in $B$,
$T$ contains the sentences
\begin{gather*}
	a=a,\\
	a=b\lto b=a,\\
	a=b\land b=c\lto a=c.
\end{gather*}
Therefore the relation $\sim$ on $B$ given by
\begin{equation*}
a\sim b\iff\text{the sentence $a=b$ is in $T$}
\end{equation*}
is an equivalence relation.
Let us denote by $B/\mathscr U$
the set of equivalence classes of elements of $B$.
For every $n$ in $\N$,
for every $n$-ary operation symbol $F$ of $\sig$,
for all $(a_0,\dots,a_{n-1})$
and $(b_0,\dots,b_{n-1})$ in $B^n$,
$T$ contains
\begin{gather*}
\bigwedge_{i<n}a_i=b_i
%\land\dots\land a_{n-1}=b_{n-1}
\lto Fa_0\cdots a_{n-1}=Fb_0\cdots b_{n-1},\\
\Exists xFa_0\cdots a_{n-1}=x.
\end{gather*}
Therefore, by \eqref{eqn:TE},
$T$ determines an interpretation of $F$ on $B/\mathscr U$.
Similarly, $T$ determines an interpretation of every relation symbol in $\sig$.
Likewise, every atomic sentence is true in the resulting structure
if and only if it belongs to $T$.
Then the same is true for \emph{every} sentence,
by \eqref{eqn:T}.
\end{proof}

The new structure given by the theorem 
%(and called $\str B/\mathscr U$ in the proof)
can be denoted by
\begin{equation*}
\left.\prod_{i\in\Omega}\str A_i\right/\mathscr U;
\end{equation*}
it is the \textbf{ultraproduct} 
of the indexed family $(\str A_i\colon i\in\Omega)$
with respect to the ultrafilter $\mathscr U$.
In case $\mathscr U$ is a \emph{principal} ultrafilter
$\{X\in\pow{\Omega}\colon i\in X\}$ for some $i$ in $\Omega$,
then $T$ is just the complete theory of $\str A_i$,
and so the theorem is trivial.
It is the existence of nonprincipal ultrafilters
that makes the theorem interesting and useful.

In the special case of the theorem
where each $\str A_i$ is the same structure $\str A$,
the ultraproduct is an \textbf{ultrapower,}
denoted by
\begin{equation*}
\str A^{\Omega}/\mathscr U.
\end{equation*}
In this case,
the conclusion of \L o\'s's Theorem
is that $\str A$ is an \textbf{elementary substructure} of the ultrapower.
We denote this situation by
\begin{equation*}
\str A\preccurlyeq\str A^{\Omega}/\mathscr U.
\end{equation*}


\mysection{Applications}

We can now understand Theorem \ref{thm:f} 
as a consequence of \L o\'s's Theorem
in the following way.
We are given a function $f$ from $\R$ to $\R$.
this means $f$ is a singulary operation on $\R$,
and as such it can considered 
as the interpretation of some singulary operation symbol
(which we also write as $f$).
This symbol is interpreted in the ultrapower $\stR$
as $\st f$.
We assume $\lim_af=L$, that is,
for all $n$ in $\N$,
for some positive $\delta$ in $\R$, the sentence
\begin{equation*}
\Forall x\left(0<\abs{x-a}<\delta\lto\abs{f(x)-L}<\frac1n\right)
\end{equation*}
is true in $\R$.
Then the same sentence is true in $\stR$.
In particular, in $\stR$,
suppose $x\simeq a$, but $x\neq a$.
Then $0<\abs{x-a}<\delta$,
so $\abs{f(x)-L}<1/n$,
where the symbol $f$ means $\st f$.
This being so for all $n$ in $\N$,
we have $\st f(x)\simeq L$.

If instead $\lim_af\neq L$,
then for some positive $\epsilon$ in $\R$,
the sentence
\begin{equation*}
\Forall{\delta}\Exists x(\delta>0\lto0<\abs{x-a}<\delta\land\abs{f(x)-L}\geq\epsilon)
\end{equation*}
is true in $\R$, hence in $\stR$.
In particular, letting $\delta$ be a positive infinitesimal,
we obtain $x$ in $\stR$ such that $x\simeq a$, but $x\neq a$,
and $\st f(x)\not\simeq L$.

If we call $\stR$ a \textbf{(nonstandard) extension} of $\R$,
then $\st f$ as above is the corresponding extension of the function $f$.
Similarly,
being a subset of $\R$, the set $\N$ is a singulary relation on $\R$,
and so it has an extension $\stN$,
which is the set of all $a$ in $\stR$ such that the sentence $a\in\N$
is true in $\stR$.
(By the formal definition above,
the sentence $a\in\N$ would be written as $\N a$.)
This means
\begin{equation*}
\stN=\bigl\{[x]\colon x\in\R^{\upomega}\And\{k\in\upomega\colon x_i\in\N\}\in\mathscr U\bigr\}.
\end{equation*}

\begin{theorem}
$\N\pincluded\stN$,
and the finite elements of $\stN$ 
are precisely the elements of $\N$.
\end{theorem}

\begin{proof}
For every $n$ in $\N$, the sentence $n\in\N$ is true in $\R$, hence in $\stR$;
so $\N\included\stN$.
Since the sentence
\begin{equation*}
\Forall x\bigl(x\in\N\lto1\leq x\land(n\leq x<n+1\lto n=x)\bigr)
\end{equation*}
is true in $\R$, it is true in $\stR$,
and so there are no new finite elements of $\stN$.
Finally, 
the sentence $\Forall x\Exists y(y\in\N\land y>x)$ is true in $\R$,
hence in $\stR$, so letting $x$ be a positive infinite element of $\stR$
gives us an infinite element of $\stN$;
this element is not in $\N$, so $\N\pincluded\stN$.
\end{proof}

If now $a$ is a sequence $(a_k\colon k\in\N)$ of elements of $\R$,
this means $a$ is the binary relation $\{(k,a_k)\colon k\in\N\}$ on $\R$,
so it has an extension $\st a$.
This extension must be a sequence $(\st a_n\colon n\in\stN)$,
where $\st a_n=a_n$ if $n\in\N$;
for the sentences
\begin{gather*}
	\Forall x\Forall y(x\mathrel ay\lto x\in\N),\\
	\Forall x\Forall y\Forall z(x\mathrel ay\land x\mathrel az\lto y=z)
\end{gather*}
are true in $\R$, hence in $\stR$.

\begin{theorem}
A real-valued sequence $a$ on $\N$ is bounded
if and only if, for each infinite $n$ in $\stN$,
$\st a_n$ is finite.
\end{theorem}

\begin{theorem}
For all real-valued sequences $a$ on $\N$,
for all $L$ in $\R$,
\begin{equation*}
\lim_{n\to\infty}a_n=L
\end{equation*}
if and only if, for all infinite $n$ in $\stN$,
\begin{equation*}
\st a_n\simeq L.
\end{equation*}
\end{theorem}

Recall that a real-valued sequence $a$ on $\N$
is a \textbf{Cauchy sequence} if for all positive $\epsilon$
in $\R$,
for some $\ell$ in $\N$,
\begin{equation*}
m>\ell\And n>\ell\implies\abs{a_m-a_n}<\epsilon.
\end{equation*}
Easily, every convergent sequence is a Cauchy sequence.
The converse is more difficult.
The following is the ``nonstandard'' version of the theorem:
the proof will use standard parts as defined above.

\begin{theorem}
A real-valued sequence $a$ on $\N$ is convergent
if and only if, for all infinite $m$ and $n$,
\begin{equation*}
a_m\simeq a_n.
\end{equation*}
\end{theorem}

\mysection{Mock second-order logic}

We may consider a structure
as having a universe partitioned into several subsets,
called \textbf{sorts.}
For example, a vector space
has a sort of vectors and a sort of scalars.
Correspondingly, in the logic of vector spaces,
there will be vector variables and scalar variables.
In a many-sorted structure,
operations and relations do not simply take 
$n$ arguments for some $n$ in $\N$,
but the sort of each argument must be specified.
Thus, in a vector space, 
two vectors can be added together,
and two scalars can be added together,
but not a vector and a scalar.

We can consider the natural numbers
as composing a two-sorted structure,
the sorts being $\N$ and $\pow{\N}$.
The variables for these sorts 
are minuscule and capital letters, respectively.
In addition to the relation symbol $<$,
which takes two arguments from $\N$,
let the signature contain the membership relation $\in$,
taking an argument from $\N$ and an argument from $\pow{\N}$.
Then we can express the well-ordering property of $(\N,<)$
as a \emph{first-order} sentence in this signature:
\begin{equation}\label{eqn:wo}
\Forall X\forall y\Bigl(y\in X\lto
\Exists z\bigl(z\in X\land\Forall w(w\in X\lto z\leq w)\bigr)\Bigr).
\end{equation}
Denoting our two-sorted structure by $\N\amalg\pow{\N}$,
we can form the extension $\st(\N\amalg\pow{\N})$,
which can be understood as having the two sorts $\stN$ and $\st{\pow{\N}}$.
Then the same sentence \eqref{eqn:wo} is true in the extension.
However,
this does not mean that $\stN$ is well ordered.
This is because $\st{\pow{\N}}$ is not $\pow{\stN}$.
If $a\in\N^{\upomega}$ and $B\in\pow{\N}^{\upomega}$,
we have
\begin{equation*}
[a]\mathrel{\st{\in}}[B]\iff\{k\in\upomega\colon a_k\in B_k\}\in\mathscr U.
\end{equation*}
Thus we can identify $[B]$ with the subset
\begin{equation}\label{eqn:B}
\bigl\{[x]\in\stN\colon\{k\in\upomega\colon x_k\in B_k\}\in\mathscr U\bigr\}
\end{equation}
of $\stN$.
We can denote this subset of $\stN$ by
\begin{equation*}
\left.\prod_{k\in\upomega}B_k\right/\mathscr U;
\end{equation*}
however, it must be understood that if $[a]$ belongs to this set,
this does not mean $a\in\prod_{k\in\upomega}B_k$,
but only that $\{k\in\upomega\colon a_k\in B_k\}\in\mathscr U$,
as in \eqref{eqn:B}.
For example, if some $B_k$ is empty,
then $\prod_{k\in\upomega}B_k=\emptyset$,
but this does not imply that the set in \eqref{eqn:B} is empty.

The embedding $[X]\mapsto\left.\prod_{k\in\upomega}X_k\right/\mathscr U$
of $\st{\pow{\N}}$ in $\pow{\stN}$ is not surjective.
For example, $\N$ itself (considered as a subset of $\stN$)
is not in the image of $\st{\pow{\N}}$.
We can see this in two ways.
\begin{asparaenum}
\item
Every nonempty subset of $\st{\pow{\N}}$ has a least element,
because \eqref{eqn:wo} is true in $\st(\N\sqcup\pow{\N})$;
but $\stN\setminus\N$ has no least element.
\item
More directly,
suppose $B$ in $\pow{\N}^{\upomega}$ is such that
the element of $\pow{\stN}$ in \eqref{eqn:B} includes $\N$.
This means, for each $n$ in $\N$,
\begin{equation*}
\{k\in\upomega\colon n\in B_k\}\in\mathscr U.
\end{equation*}
In particular, 
there are infinitely many $k$ in $\upomega$ such that $n\in B_k$.
Thus if, for all $k$ in $\upomega$, we define
\begin{equation*}
a_k=\max\{n\in B_k\colon n\leq k+1\},
\end{equation*}
then the sequence $(a_k\colon k\in\upomega)$ is unbounded,
and so $[a_k\colon k\in\upomega]$ is not in (the image of) $\N$,
though it is in $\left.\prod_{k\in\upomega}B_k\right/\mathscr U$.
\end{asparaenum}

We can introduce power sets as sorts
in order to define \emph{integration.}
By one standard definition (attributed to Riemann),
a real-valued function $f$
whose domain includes a closed interval $[a,b]$
is \textbf{integrable} on $[a,b]$ if, for some $I$ in $\R$,
for all positive $\epsilon$ in $\R$,
there is a positive $\delta$ in $\R$
such that,
for all $n$ in $\N$,
for all subsets $\{a_0,\dots,a_n\}$ of $[a,b]$,
for all subsets $\{\xi_0,\dots,\xi_{n-1}\}$ of $[a,b]$,
if
\begin{equation}\label{eqn:part}
\left.\qquad
\begin{gathered}
a=a_0<\dots<a_n=b,\\
a_0\leq\xi_0\leq a_1\And\cdots\And a_{n-1}\leq\xi_{n-1}\leq a_n,
\end{gathered}
\qquad\right\}
\end{equation}
and 
\begin{equation*}
\max\{a_{k+1}-a_k\colon k<n\}<\delta,
\end{equation*}
then
\begin{equation*}
\left|\sum_{k<n}f(\xi_k)\cdot(a_{k+1}-a_k)-I\right|<\epsilon.
\end{equation*}
In this case $I$ is unique and is the \textbf{integral} of $f$ on $[a,b]$;
the integral is denoted by
\begin{equation*}
\int_a^b f.
\end{equation*}
If $f$ is given only in the form $x\mapsto f(x)$,
we may write the integral as
\begin{equation*}
\int_a^bf(x)\dee x.
\end{equation*}
The idea of the notation is that $\dee x$ is infinitesimal,
so that the integral itself is the \emph{sum}
(abbreviated by $\int$, an elongated letter S)
of rectangles of infinitesimal width.
Given $f$ as before, and $I$ in $\R$,
suppose that,
for all $n$ in $\stN$,
for all subsets $\{a_0,\dots,a_n\}$ of $\st[a,b]$ and
for all subsets $\{\xi_0,\dots,\xi_{n-1}\}$ of $\st[a,b]$
such that \eqref{eqn:part} and
\begin{equation*}
a_0\simeq a_1\And\dots\And a_{n-1}\simeq a_n
\end{equation*}
hold,
it follows that
\begin{equation*}
\sum_{k<n}f(\xi_k)\cdot(a_{k+1}-a_k)\simeq I.
\end{equation*}
In this case, by the nonstandard definition, $I=\int_a^bf(x)\dee x$.

\mysection{Set-theoretic considerations}

The signature of set theory as $\{\in\}$.
The \textbf{Extension Axiom} is that sets with the same elements are equal:
\begin{equation*}
\Forall x\Forall y\bigl(\Forall z(z\in x\liff z\in y)\lto x=y\bigr).
\end{equation*}
If $\phi$ is a formula of the signature $\{\in\}$
in which only the variable $x$ occurs freely,
then those sets $a$ such that $\phi(a)$ is true
compose a \textbf{class,} denoted by
\begin{equation*}
\{x\colon\phi\}.
\end{equation*}
Such an expression is not literally part of the logic of sets.
However, in what is known as Zermelo--Fraenkel set theory,
every axiom besides the Foundation Axiom
is that certain classes are sets.%%%%%
\footnote{This is not quite true.
The \textbf{Foundation Axiom} is that every nonempty set has a minimal element
with respect to $\in$, that is,
$\Forall x\Forall y\Exists z\Forall w\bigl(y\in x\lto z\in x\land(w\in z\lto w\notin x)\bigr)$.
There could in fact be sets without minimal elements;
all the Foundation Axiom does
is to decline to consider such sets \emph{as} sets.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
For example, the ``power class'' of a set $a$
is the class
\begin{equation*}
\{x\colon\Forall y(y\in x\lto y\in a)\};
\end{equation*}
the Power Set Axiom is accordingly
\begin{equation*}
\Forall z\Exists w\Forall x\bigl(x\in w\lto\Forall y(y\in x\lto y\in z)\bigr).
\end{equation*}
The Axiom of Choice is not of this form,
but is that, for every set $a$,
there is a function $f$ such that,
for every nonempty subset $b$ of $a$,
\begin{equation*}
f(b)\in b.
\end{equation*}
We used a version of this in proving \L o\'s's Theorem,
when we found $(a_n\colon n\in\upomega)$ so that \eqref{eqn:bva}
on page \pageref{eqn:bva} holds.

\L o\'s's Theorem requires also
the existence of nonprincipal ultrafilters
on arbitrary sets.
As we know,
ultrafilters are complements of maximal ideals of Boolean rings.
The \textbf{Maximal Ideal Theorem}\label{MITh}
is that, in arbitrary ring $R$,
if $I$ is a proper ideal,
then $I$ is included in a maximal ideal.

\begin{theorem}\label{thm:MITh}
The Maximal Ideal Theorem is a consequence of the Axiom of Choice.
\end{theorem}

\begin{proof}
This is commonly proved by means of \emph{Zorn's Lemma,}
which is equivalent to the Axiom of Choice.
A more useful approach for present purposes is the following.
The Axiom of Choice allows us to well-order any ring $R$,
writing it as $\{a_{\alpha}\colon\alpha<\kappa\}$,
where $\kappa$ is now the \emph{cardinality} of $R$.
We define an increasing sequence of ideals of $R$
by \emph{transfinite recursion}:
\begin{compactenum}
\item
$I_0$ is the given proper ideal $I$ of $R$.
\item
For all $\alpha$ in $\kappa$,
If $I_{\alpha}\cup\{a_{\alpha}\}$ generates a proper ideal of $R$,
this ideal is defined to be $I_{\alpha+1}$; otherwise $I_{\alpha+1}=I_{\alpha}$.
\item
If $\beta$ is a limit ordinal and $\beta\leq\kappa$,
then $I_{\beta}=\bigcup_{\alpha<\beta}I_{\alpha}$.
\end{compactenum}
Then $I_{\kappa}$ is a proper ideal of $R$;
it is maximal, 
since any larger ideal $J$ will contain some $a_{\alpha}$ 
that is not in $I_{\kappa}$,
but this means $I_{\alpha}\cup\{a_{\alpha}\}$
must generate $R$, and thus $J=R$.
\end{proof}

The proper ideal $I$ of $R$ is a \textbf{prime ideal}
if
\begin{equation*}
xy\in I\And x\notin I\implies y\in I.
\end{equation*}
For example, every element $n$ of $\Z$
generates the ideal $(n)$, namely $\{nx\colon x\in\Z\}$.
Then
\begin{equation*}
x\in(n)\iff n\divides x.
\end{equation*}
\textbf{Euclid's Lemma} is that for all primes $p$,
\begin{equation*}
p\divides xy\And p\ndivides x\implies p\divides y,
\end{equation*}
that is, $(p)$ is a prime ideal of $\Z$.
But $(0)$ is also a prime ideal of $\Z$,
although $0$ is not considered to be a prime number.

Any ring in which $(0)$ is a prime ideal
is an \textbf{integral domain.}
In general, the proper ideal $I$ of $R$ is
\begin{compactitem}
\item
maximal, if and only if $R/I$ is a field;
\item
prime, if and only if $R/I$ is an integral domain.
\end{compactitem}
Since all fields are integral domains,
all maximal ideals are prime.
The converse holds for \emph{Boolean} rings,
since the only Boolean integral domain has the two elements $0$ and $1$
(namely the solutions to $x^2=x$)
and is therefore the two-element field.

The \textbf{Prime Ideal Theorem}
is that every proper ideal of a ring
is included in a prime ideal.
It is known that the Prime Ideal Theorem
does not imply the Maximal Ideal Theorem
in Zermelo--Fraenkel set theory.
(Both the Prime and the Maximal Ideal Theorem
become real theorems
when the Axiom of Choice is introduced.)
Moreover, the Maximal Ideal Theorem
implies the Axiom of Choice \cite{MR533327}.

We derived the Compactness Theorem
from \L o\'s's Theorem,
but this turns out to be stronger than needed for the job:
for the following is true.

\begin{theorem}
The Compactness Theorem
is a consequence of the Prime Ideal Theorem.
\end{theorem}

\begin{proof}
In proving \L o\'s's Theorem,
in a certain signature we find a set $T$ of sentences
such that, for all sentences $\sigma$ and $\tau$,
and all formulas $\phi$ in which only $x$ occurs freely,
the properties \eqref{eqn:T} on page \pageref{T} hold;
moreover, $T$ contains all logically true sentences of its signature.
These properties ensure that $T$ is the set of all sentences
that are true in some structure,
whose universe consists of the interpretations of the constant symbols
in the signature.
(This result can be called the \textbf{Canonical Model Theorem.})

Given a set $\Gamma$ of sentences
such that every finite subset of $\Gamma$ has a model,
we want to enlarge $\Gamma$ to a set like $T$ above.
We do this first by adding to the signature,
for every $\phi$ as above, a new constant symbol, $c_{\phi}$.
Now let $\Gamma'$ consist of the sentences in $\Gamma$
along with, for every $\phi$ as above,
the sentence $\Exists x\phi\lto\phi(c_{\phi})$.
Then every finite subset of $\Gamma'$ has a model.

This means, as it were,
$\Gamma'$ generates a proper filter
of the set of sentences of its signature.
Now, this is not quite true,
because this set of sentences is not exactly a Boolean ring;
but it becomes a Boolean ring when we replace each of its sentences
with the \emph{logical equivalence class} of the sentence.
Two sentences $\sigma$ and $\tau$
are \textbf{logically equivalent}
if the sentence $\sigma\liff\tau$
is true in all structures of its signature.
As equipped with the operations $\wedge$, $\vee$, and $\lnot$
given by
\begin{gather*}
	[\sigma]\wedge[\tau]=[(\sigma\land\tau)],\\
	[\sigma]\vee[\tau]=[(\sigma\lor\tau)],\\
	\lnot[\sigma]=[\lnot\sigma],
\end{gather*}
the set of logical equivalence classes of sentences of a signature
is the \textbf{Lindenbaum algebra} of the signature.%%%%%
\footnote{Actually, for any list of variables,
there is a Lindenbaum algebra of formulas
in which only the variables on that list occur freely.}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
A Lindenbaum algebra is a \textbf{Boolean algebra,}
which is just a Boolean ring with different operations emphasized.
Addition in the Boolean ring is given by
$[\sigma]+[\tau]=[((\sigma\lor\tau)\land\lnot(\sigma\land\tau))]$;
multiplication is $\wedge$.
Then the image of $\Gamma'$ under $\sigma\mapsto[\sigma]$
generates a proper filter,
which is included in an ultrafilter $\mathscr U$
by the Prime Ideal Theorem.
Then the set $\{\sigma\colon[\sigma]\in\mathscr U\}$
is of the desired form of $T$ as above,
and so it has a model,
which is a model of $\Gamma$ since $\Gamma\included T$.
\end{proof}

We also have the converse.
To prove this,
we define the \textbf{diagram} of any structure $\str A$
to be the set of all \emph{quantifier-free} sentences,
with parameters from $A$, that are true in $\str A$.

\begin{theorem}
The Prime Ideal Theorem
is a consequence of the Compactness Theorem.
\end{theorem}

\begin{proof}
Suppose $I$ is a proper ideal of a ring $R$.
We consider $I$ as a singulary relation on $R$,
and we introduce a new singulary relation symbol $P$.
Let $\Gamma$ consist of the sentences of the diagram of $(R,I)$,
together with, for all $a$ and $b$ in $R$,
the sentences
\begin{gather*}
	a\in P\land b\in P\lto a+b\in P,\\
	a\in P\lor b\in P\lto ab\in P,\\
	1\notin P,\\
	a\in I\lto a\in P.
\end{gather*}
If $(R',I',P')\models\Gamma$,
then $R'$ is not necessarily a ring;
but $R$ embeds in $R'$,
since the sentence $a\neq b$ is in $\Gamma$,
and is therefore true in $R'$,
whenever $a$ and $b$ are distinct elements of $R$.
So we may assume $R\included R'$.
In this case $I=I'\cap R$,
and $P'\cap R$ is a proper prime ideal of $R$
that includes $I$.

The set $\Gamma$ does have a model,
by the Compactness Theorem.
For suppose $\Delta$ is a finite subset of $\Gamma$.
Then only finitely many elements of $R$
occur in the sentences of $\Delta$.
These elements generate a \emph{countable} sub-ring $S$ of $R$.
Then the Maximal Ideal Theorem is true for this sub-ring,
as in the proof of Theorem \ref{thm:MITh}.
In particular, since $I\cap S$ is a proper ideal of $S$,
it is included in a maximal ideal,
which is therefore a prime ideal,
and this provides a model of $\Delta$.
\end{proof}

Finally, it is possible to derive the Axiom of Choice
from \L o\'s's Theorem.
Using obvious abbreviations, we have
\begin{equation*}
\xymatrix{
\text{\L O\'S}\ar@{<=>}[r]\ar@{=>}[d]&\text{AC}\ar@{<=>}[r]&\text{MAX}\ar@{=>}[d]\\
\text{COM}\ar@{<=>}[rr]              &                     &\text{PRI}}
\end{equation*}

\setbibpreamble{When I set out to learn nonstandard analysis for this course,
I used the book of its creator,
Abraham Robinson \cite{MR1373196}.
A professor had referred me to this book
when I was starting graduate school;
but I could not make sense of the book then.
There are textbooks of nonstandard analysis,
but I confess to not having sought them out.
I have consulted two \emph{calculus} textbooks for beginners
that use the nonstandard approach:
Keisler \cite{Keisler-calculus} and
Henle and Kleinberg \cite{MR1999278}.
Most books on model theory will say something about ultraproducts;
the ones that I have used the most are Hodges \cite{MR94e:03002},
followed by Chang and Keisler \cite{Chang--Keisler}
and Bell and Slomson \cite{MR0269486}.\\\mbox{}}

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

\begin{thebibliography}{1}

\bibitem{MR0269486}
J.~L. Bell and A.~B. Slomson.
\newblock {\em Models and ultraproducts: {A}n introduction}.
\newblock North-Holland Publishing Co., Amsterdam, 1969.
\newblock Reissued by Dover, 2006.

\bibitem{Chang--Keisler}
C.~C. Chang and H.~J. Keisler.
\newblock {\em Model theory}.
\newblock North-Holland Publishing Co., Amsterdam, third edition, 1990.
\newblock First edition 1973.

\bibitem{MR1999278}
James~M. Henle and Eugene~M. Kleinberg.
\newblock {\em Infinitesimal calculus}.
\newblock Dover Publications Inc., Mineola, NY, 2003.
\newblock Reprint of the 1979 original [MIT Press, Cambridge, MA.

\bibitem{MR533327}
Wilfrid Hodges.
\newblock Krull implies {Z}orn.
\newblock {\em J. London Math. Soc. (2)}, 19(2):285--287, 1979.

\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{Keisler-calculus}
H.~Jerome Keisler.
\newblock {\em Elementary Calculus: {A}n Infinitesimal Approach}.
\newblock 2013.
\newblock First edition 1976, second edition 1986, both by Prindle, Weber \&\
  Schmidt. Published online at \url{www.math.wisc.edu/~keisler/calc.html}.

\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. First edition 1965.

\end{thebibliography}


\end{document}
