\documentclass[a4paper,11pt,reqno]{amsart}
\title{Non-standard analysis}
\author{David Pierce}
\date{\today}
\address{Mathematics Department, Middle East Technical University,
  Ankara 06531, Turkey}
\urladdr{arf.math.metu.edu.tr/~dpierce/}
\email{dpierce@metu.edu.tr}

\usepackage{amssymb}
\usepackage{hfoldsty}
\usepackage{typearea}
\usepackage{pstricks,pst-plot}
\usepackage[polutonikogreek,english]{babel}
\usepackage[oxonia]{psgreek}
%\usepackage[notref,notcite]{showkeys}
\usepackage{paralist}
\usepackage{graphicx}
\usepackage{url}
\usepackage[all]{xy}
\usepackage{verbatim}
\usepackage{amscd}

%\usepackage{mathabx}
%\newcommand{\dotdiv}{-}
\newcommand{\dotdiv}{\stackrel{.}{-}}
%\newcommand{\dotdiv}{\stackrel{*}{-}}

\newcommand{\Gk}[1]{\selectlanguage{polutonikogreek}#1\selectlanguage{english}}

\newcommand{\stnd}[1]{\mathbb{#1}}
\newcommand{\starred}[1]{{}^*#1}
\newcommand{\N}{\stnd N}
\newcommand{\sN}{\starred{\N}}
\newcommand{\Z}{\stnd Z}
\newcommand{\Q}{\stnd Q}
\newcommand{\R}{\stnd R}
\newcommand{\sR}{\starred{\R}}
\newcommand{\C}{\stnd C}
\newcommand{\B}{\stnd B}
\newcommand{\sS}{\starred{\!S}}
\newcommand{\sT}{\starred T}
\newcommand{\stf}{\starred{\!f}}
\newcommand{\seq}[1]{#1^{\vnn}}
\newcommand{\Ro}{\seq{\R}}
\newcommand{\Ko}{\seq{K}}
\newcommand{\sK}{\starred{\!K}}
\newcommand{\starsub}[2]{\starred{\!(#1_{#2})}}
\newcommand{\sKt}[1]{\starsub{K}{#1}}
\newcommand{\sa}{\starred{\!a}}
\newcommand{\sX}{\starred{\!X}}
\newcommand{\startilde}[1]{\starred{\!(\tilde{#1})}}
\newcommand{\stK}{\startilde K}
\newcommand{\tsK}{\widetilde{\sK}}
\newcommand{\sA}{\starred{\!A}}

\newcommand{\included}{\subseteq}
\newcommand{\pincluded}{\subset}

%\newcommand{\abs}[1]{\mathopen|#1\mathclose|}
%\newcommand{\abs}[1]{\lvert#1\rvert}
\newcommand{\abs}[1]{\left|#1\right|}
\renewcommand{\epsilon}{\varepsilon}
\renewcommand{\setminus}{\smallsetminus}
\renewcommand{\emptyset}{\varnothing}
\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
%\usepackage{stmaryrd}
%\renewcommand{\land}{\mathrel{\binampersand}}
\renewcommand{\land}{\mathrel{\&}}

\newcommand{\str}[1]{\mathfrak{#1}}
\newcommand{\lett}[1]{\textsf{#1}}
\newcommand{\class}[1]{\mathbf{#1}}
\newcommand{\pred}[1]{\operatorname{pred}(#1)}
\newcommand{\Forall}[1]{\forall{#1}\;}
\newcommand{\Exists}[1]{\exists{#1}\;}
\newcommand{\val}[1]{\operatorname{val}(#1)}
\newcommand{\lto}{\Rightarrow}
\newcommand{\liff}{\Leftrightarrow}
\newcommand{\inv}{^{-1}}
\newcommand{\mapset}[2]{#2^{#1}}
\newcommand{\units}[1]{#1^{\times}}
\newcommand{\gpgen}[1]{\langle#1\rangle}
\newcommand{\vo}{\mathfrak O}
\newcommand{\mi}{\mathfrak p}
\newcommand{\Char}[1]{\operatorname{char}(#1)}
\usepackage{upgreek}
\newcommand{\vnn}{\upomega}
\usepackage{mathrsfs}
\newcommand{\pow}[1]{\mathscr P(#1)}
\usepackage{bm}
\newcommand{\tuple}[1]{\bm{#1}}
\renewcommand{\models}{\vDash}
\newcommand{\nmodels}{\nvDash}
\newcommand{\completion}[1]{\overline{#1}}
\newcommand{\supp}[1]{\operatorname{supp}(#1)}
\newcommand{\Supp}[1]{\operatorname{supp}[#1]}
\newcommand{\Suppinv}[1]{\operatorname{supp}\inv[#1]}
\newcommand{\dom}[1]{\operatorname{dom}(#1)} % domain
\newcommand{\symdiff}{\vartriangle}

\newtheorem{theorem}{Theorem}
\newtheorem{problem}[theorem]{Problem}
%\newtheorem{lemma}[theorem]{Lemma}
\newtheorem*{lemma}{Lemma}
\newtheorem*{corollary}{Corollary}

%\renewcommand{\theequation}{\roman{equation}}

%\setcounter{tocdepth}{1}

\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{comment}
\setcounter{page}{0}
\begin{center}
{\Huge Non-Standard Analysis}
\bigskip
{\LARGE David Pierce}
\bigskip
{\large August, 2009}
\vspace{3cm}
\includegraphics[width=10cm]{nesin-village.eps}
\end{center}
\newpage
\end{comment}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\maketitle

%\setcounter{section}{-1} 

%\section*{Preface}

These notes are edited from those used for a course given August
10--16, 2009, at the Nesin 
Mathematics Village (\emph{Nesin Matematik K\"oy\"u}), Kayser Da\u
g\i\ \emph{mevkii,} \c Sirince, Sel\c cuk, \.Izmir, Turkey.
The major changes have been to \S\S~\ref{sect:reals}
and~\ref{sect:non-Arch}.  I have made corrections throughout the
notes, but this is not a thorough revision. 
  The source files (with any further corrections and changes) will
  available at 
\begin{center}
\url{http://metu.edu.tr/~dpierce/Courses/Sirince/2009-Analysis/}
\end{center}
(This is a change from the address given in the original notes, for
reasons beyond my control.)

I had about two dozen students in the first lecture of the course.
About one dozen students came to each of the later lectures; but they
were not always the same dozen.  I managed to take the names of 16
students who attended at least one lecture. 

In six lectures I could not expect to discuss all details in these
notes.  I left many theorems unproved.  Another time, I might skip
Archimedes's quadrature of the parabola by balancing, discussing only
his quadrature by inscribed triangles.  (I want to do at least this
much, though, in order to connect the `Archimedean axiom' with the
person it is named for.)  As it was, I did do non-standard analysis
proper in the last two days.  I noted and resolved the paradoxes that
$\sN$ and $\sR$ should have the `same' properties as $\N$ and $\R$,
and yet cannot. 

\newpage

\tableofcontents

\newpage

\section*{Introduction}

\textbf{Mathematical analysis} is the
theoretical side of calculus.  Calculus consists of
methods of solving certain sorts of problems; analysis studies those
methods.  The
\textbf{standard} way of doing this is founded on the `epsilon-delta'
%$\epsilon$-$\delta$
definition of \emph{limit.}  The \textbf{non-standard} approach uses
\emph{infinitesimals,} with rigorous logical justification.
Abraham Robinson first gave this justification; it can be found in
his book, \emph{Non-standard Analysis} \cite{MR1373196}.


An \textbf{infinitesimal} is a number whose absolute value is less
than than every positive rational number.  If two numbers $a$ and
$b$ differ by an infinitesimal, we write
\begin{equation*}
  a\simeq b.
\end{equation*}
Zero is an infinitesimal, but there are no other infinitesimals among
the so-called \emph{real numbers.}

In standard analysis, a function $f$ is said to be \textbf{continuous}
at an element $a$ of its domain if
\begin{equation*}
  \lim_{x\to a}f(x)=f(a);
\end{equation*}
this means that, for all positive numbers $\epsilon$, there is a
positive number $\delta$ such that, for all $x$ in the domain of $f$,
if $\abs{x-a}<\delta$, then $\abs{f(x)-f(a)}<\epsilon$.  

In
non-standard analysis, there is an alternative formulation of
continuity: $f$ is 
continuous at $a$ just in case, for all
$x$ in the domain of $f$, if $x\simeq a$, then $f(x)\simeq f(a)$.

The alternative formulation of continuity and many other things will
be worked out in the last section, \S~\ref{sect:analysis}, of these
notes.  The other 
sections are meant 
to provide logical justication and motivation for this work.
Section~\ref{sect:Arch} looks at Archimedes's solution of a calculus
problem, and also mentions the \emph{Archimedean axiom,} which will
come up later in various contexts.  Today we think of calculus as
involving the \emph{complete 
  ordered field} $\R$ of real numbers; this field is constructed in
\S\S~\ref{sect:N2Q} and~\ref{sect:reals}.  Non-standard analysis
requires a certain larger ordered field, $\sR$, which is an example of a
\emph{non-Archimedean} ordered field.  Non-Archimedean ordered fields
in general, and 
simple examples of these and related fields, are discussed in
\S~\ref{sect:non-Arch}.  The field $\sR$ can be obtained as an
\emph{ultrapower} of $\R$; this construction is treated in
\S~\ref{sect:ultra}.  One can jump ahead to \S~\ref{sect:analysis} at
any time, provided one understands the meaning of
Theorem~\ref{thm:elsub} in \S~\ref{subsect:logic}.  

%There are six sections in all, intended to correspond to the six days
%of the course.    

\newpage

\section{Archimedes's quadrature of the parabola}\label{sect:Arch}

In the last chapter of \emph{Non-standard Analysis}~\cite{MR1373196},
Robinson treats the
history of calculus in the light of non-standard analysis.  Robinson
begins with Leibniz; but I think it worthwhile to go back much
further---about two thousand years further.
In the
work of Archimedes, both standard and non-standard approaches to
calculus (in our terms) can be discerned.
For example, 
Archimedes takes up the following

\begin{problem}\label{prob:Arch}
Find a square equal to a given segment of a parabola.
\end{problem}

Parabolas will be defined below; meanwhile, a
segment of a parabola can be seen in Figure~\ref{fig:parab}, 
\begin{figure}[ht]
  \begin{pspicture}(-4,-4)(2,0.2)
%\psgrid
    \psplot{-4}{2}{x x mul neg 4 div}
\psline(-4,-4)(2,-1)(-1,-0.25)(-4,-4)
\psdots(-4,-4)(2,-1)(-1,-0.25)
\uput[r](2,-1){$C$}
\uput[ul](-1,-0.25){$A$}
\uput[dl](-4,-4){$B$}
  \end{pspicture}
  \caption{}\label{fig:parab}
\end{figure}
with an
inscribed triangle.  A solution to Problem~\ref{prob:Arch} is
called a \textbf{quadrature} of the parabola.  Archimedes's solution is given
by the following 

\begin{theorem}[Archimedes]\label{thm:Arch}
  A parabolic segment is a third again as
large\footnote{\Gk{>ep'itritoc}, one and a third times as much.
See Appendix~\ref{app:Greek} for the Greek letters.}  as
the inscribed triangle with the same altitude.
\end{theorem}

In Figure~\ref{fig:parab}, triangle $ABC$ has the same altitude as the
parabolic segment, because the tangent to the parabola at $A$ is
parallel to the chord $BC$.  Archimedes proves Theorem~\ref{thm:Arch}
in two ways in his
\emph{Quadrature of the parabola:} in Proposition 17 (and the
propositions leading up to it), and in Proposition 24.  Heath
\cite{MR2000800} provides an 
English version of this work, though rather than translating,
he rewrites Archimedes in a way intended to be more comprehensible to
his readers.  Selections from the 
Greek text of Archimedes, with more literal English translations, are
provided by Thomas \cite{MR13:419b}.  
The first volume of a faithful translation of all of Archimedes's
works
by Netz \cite{MR2093668} has appeared; but this does not contain the
works that we are particularly interested in here.

Insight into the
\emph{discovery} of Theorem~\ref{thm:Arch} is given in Archimedes's
\emph{Method.}  This work was lost until 1906.
Then, in \.Istanbul, the Danish scholar J.L. Heiberg
discovered the \emph{Archimedes Palimpsest:}
a parchment codex of the works of 
Archimedes that had been washed and reused for writing Christian
prayers. 

%What does this mean?
Archimedes does not use the word
\emph{parabola}~\cite[p.~clxvii]{MR2000800}, but refers to a
\emph{section of an orthogonal
cone.}\footnote{\Gk{>orjogwn'iou k'wnou tom'h}.}  
Let me review what this means, sometimes following also the account of
Apollonius \cite{MR1660991}.  A
cone is determined by a circle, called its
\textbf{base,} and a point, called the \textbf{apex} of the cone,
that is not in 
the plane of the base.  The cone is traced out by a straight line, one
endpoint of which is at the apex, the other being moved about the
circumference of the base.  The straight line drawn from the apex
to the center of the base is the \textbf{axis} of the cone.  A plane
containing the axis intersects the cone in an \textbf{axial triangle.}
If the axis is perpendicular to the base, then the cone is
\textbf{right.}  
If an axial triangle of a right cone has a right
angle at the apex, then the cone is an \textbf{orthogonal}\footnote{Or
  `right-angled'; but I want to avoid confusion with \emph{right}
  cones in general.} cone.  In
such a cone, if a plane is perpendicular to one of the 
sides of the axial triangle that are about the apex, then the plane
cuts the cone in 
a curve that---following Apollonius---we call a \textbf{parabola.}  The
intersection of the cutting plane and the axial triangle is the
\textbf{axis} of the parabola (which is different from the axis of the
cone itself); the intersection of the axis of the parabola and the
parabola itself is the \textbf{vertex} of the parabola.  

A straight
line dropped from the parabola perpendicularly to the axis may be
called an \textbf{ordinate;} the part of the axis between the foot of
the ordinate and the vertex is the corresponding
\textbf{abscissa.}  The word \emph{abscissa} means \emph{cut off} in Latin,
while the word \emph{ordinate} is related to \emph{order,} which is
used for, among other 
things, any of the several classical styles of architecture.  These
orders feature columns standing parallel, like ordinates of a
parabola.  Consider for example the columns of the Ionic order erected
at Priene, S\"oke, Ayd\i n (which is accessible on a 
day trip from \c Sirince): see Figure~\ref{fig:ord}.
\begin{figure}[ht]
\hfill
  \includegraphics[width=6cm]{priene.eps}
\hfill
  \begin{pspicture}(-0.5,-2)(6.5,6)
    \psline(0,0)(6.5,0)
    \psset{plotpoints=200}
    \psplot{0}{6.5}{x sqrt}
    \psplot{0}{4}{x sqrt neg}
    \psline(1,0)(1,1)
    \psline(2,0)(2,1.414)
    \psline(3,0)(3,1.732)
    \psline(4,0)(4,2)
    \psline(5,0)(5,2.236)
    \psline(6,0)(6,2.449)
    \psdots(0,0)(6,0)(6,2.449)
    \uput[u](6,2.449){$B$}
    \uput[d](6,0){$C$}
    \uput[l](0,0){$A$}
  \end{pspicture}
\hfill\mbox{}
  \caption{The ordinate $BC$ cuts off from the axis the abscissa
    $AC$.  On the left, Priene}\label{fig:ord} 
  
\end{figure}

Apollonius's reason for using the term \emph{parabola} is shown in
Proposition 11 of his \emph{Conics} 
\cite{MR1660991,MR13:419b}.  Apollonius also shows that parabolas can be 
obtained from \emph{all} cones, not necessarily orthogonal, not
necessarily right.  What is important for us are the following
properties of a parabola, whose proofs can be found in Apollonius.
\begin{asparaenum}[1.]
\item \label{item:parab}
The squares on two ordinates are in the ratio of the corresponding
abscissas \cite[I.11]{MR1660991}.  (Below we shall talk more about
what this means.) 
\item\label{item:tan}
Suppose a parabola has the vertex $A$, and another point $B$ is chosen
on the parabola, and the ordinate $BC$ is drawn.  Extend the
axis $CA$ beyond $A$ to a point $D$.  The straight line $BD$ is
tangent to the parabola at $B$ if and only if $AD=CA$ \cite[I.33,
  35]{MR1660991} (see Figure~\ref{fig:tangent}).  
\begin{figure}[ht]
  \begin{pspicture}(-4,-1)(4,2)
    \psline(-4,0)(4,0)
    \psset{plotpoints=200}
    \psplot{0}{4}{x sqrt}
    \psplot{0}{1}{x sqrt neg}
    \psline(2,1.414)(2,0)
    \psline(-4,-0.707)(4,2.121)
    \psdots(-2,0)(0,0)(2,0)(2,1.414)
    \uput[u](2,1.414){$B$}
    \uput[d](2,0){$C$}
    \uput[dl](0,0){$A$}
    \uput[d](-2,0){$D$}
  \end{pspicture}
  \caption{$DB$ is tangent at $B$ if and only if
    $CA=AD$}\label{fig:tangent}  
\end{figure}

\item
Every straight line parallel to the axis is a \textbf{diameter} in the
following sense.  Where this diameter meets the parabola, a tangent
can be drawn.  If a chord of the parabola is drawn parallel to this
tangent, then the diameter bisects the chord \cite[I.46]{MR1660991}.
Half of such a chord is 
an ordinate with respect to the corresponding diameter, and the
squares on two such ordinates are in the ratio of the corresponding
abscissas, as in~\ref{item:parab} \cite[I.49]{MR1660991} (see
Figure~\ref{fig:diameter}). 
\begin{figure}[ht]
  \begin{pspicture}(0,-1)(9,3)
%\psgrid
%    \psline(0,0)(4,0)
    \psset{plotpoints=200}
    \psplot{0}{9}{x sqrt}
    \psplot{0}{1}{x sqrt neg}
%    \psline(2,1.414)(2,0)
%    \psline(0,0.707)(4,2.121)
    \psdots(2,1.414)(4,1.414)(3,1.414)
    \psline(2,1.414)(8,1.414)
    \psdots
    (0.172,0.414)(5.828,2.414)
    (0,0)(8,2.828)
    \psline(0.172,0.414)(5.828,2.414)
    \psline(0,0)(8,2.828)
  \end{pspicture}
  \caption{A new diameter}\label{fig:diameter}  
\end{figure}
\end{asparaenum}

In the \emph{Method,} Archimedes solves Problem~\ref{prob:Arch} as follows.
We add some 
straight lines to Figure~\ref{fig:parab}, getting
Figure~\ref{fig:parab+}. 
\begin{figure}[ht]
  \begin{pspicture}(-10,-4.6)(2,5.6)
%\psgrid
    \psplot{-4}{2}{x x mul neg 4 div}
\psline(-4,-4)(2,-1)(-1,-0.25)(-4,-4)
\psdots(-4,-4)(2,-1)(-1,-0.25)
\uput[r](2,-1){$C$}
\uput[ul](-1,-0.25){$A$}
\uput[dl](-4,-4){$B$}
\psline(2,-1)(-4,5)(-4,-4)
\psline(-1,-2.5)(-1,2)
\psline(-10,2)(-1,-0.25)
\psline(-3,-3.5)(-3,4)
\uput[dr](-1,-2.5){$D$}
\uput[ur](-1,2){$E$}
\uput[u](-4,5){$F$}
\uput[dl](-4,0.5){$G$}
\uput[l](-10,2){$H$}
\psline(-4,5)(-1,-2.5)
\uput[dl](-2,0){$K$}
\uput[ul](-3,-2.25){$L$}
\uput[dr](-3,-3.5){$M$}
\uput[dl](-3,0.25){$N$}
\uput[ur](-3,4){$P$}
\psline(-3,-2.25)(0.458,-0.583)
\uput[dr](-1,-1.25){$Q$}
\uput[d](0.458,-0.583){$R$}
\psdots(-1,-2.5)(-1,2)
(-4,5)
(-4,0.5)
(-10,2)
(-2,0)
(-3,-2.25)
(-3,-3.5)
(-3,0.25)
(-3,4)
(-1,-1.25)
(0.458,-0.583)
  \end{pspicture}
  \caption{}\label{fig:parab+}
\end{figure}
Here $D$ is the midpoint of $BC$, so that (since $BC$ is parallel to
the tangent at $A$) the straight line $AD$ must be a diameter of
the parabola.  The tangent to the parabola at $C$ meets $DA$ extended
at $E$.  Then $A$ is the midpoint of $DE$, by~\ref{item:tan} above.
A straight line from $B$ parallel to $DA$ meets $CE$
extended at $F$.  Extend $CA$ to meet $BF$ at $G$, then extend further
to $H$ so that $GH=CG$.  The idea now is to consider $CH$ as a
\emph{lever} with \emph{fulcrum} at $G$.  If we conceive of our
figures as having weights proportional to their sizes, then we shall
show that, if we place the weight of the parabolic segment $ABC$ at
$H$, then it will just balance triangle $BCF$ where it is.

Since $A$ is
the midpoint of $DE$, also
$G$ is the midpoint of $BF$.  Let $DF$ be drawn,
intersecting $CG$ at $K$.  Since $D$ is the midpoint of
$BC$, we can conclude that $K$ is the center of gravity (or centroid)
of triangle
$BCF$.  Then $GK$ is a third of $CG$, hence a third of $GH$.
Therefore triangle $BCF$ is balanced by a third of its weight at $H$.
If we can show that the parabolic segment balances the triangle, then
the segment must be a third of the triangle.  But triangle $BCF$ is
four times triangle $ABC$ (why?).  Then Theorem~\ref{thm:Arch} will
follow. 

Now, pick a point $L$ at random on the parabola between $B$ and $C$.
Let the straight line drawn through $L$ parallel to $BF$ meet $BC$ at
$M$ and $CG$ at $N$ and $CF$ at $P$.  It remains to show that 
\begin{equation}\label{Ar-prop}
  LM:MP::GN:GH.
\end{equation}
This is the key point.  If~\eqref{Ar-prop}
holds, then $LM$, if its midpoint is placed at $H$, will
just balance $MP$.  
Since $L$ was chosen arbitrarily, we conclude that, if all of the
parabolic segment were placed at $H$, then it would balance $BCF$.
Now, Archimedes
does not find this sort of argument to be sufficiently rigorous.
Indeed, in the preface to the \emph{Method,} he writes
\begin{quote}
  For some things first became clear to me by mechanics, though they
  had later to be proved geometrically owing to the fact that
  investigation by this method does not amount to actual proof; but it
  is, of course, easier to provide the proof when some knowledge of
  the things sought has been acquired by this method rather than to
  seek it with no prior knowledge.\hfill\cite[p.223]{MR13:419b}
\end{quote}
I want to look at the `actual proof' of Archimedes presently.
Meanwhile, let us establish~\eqref{Ar-prop}.  You probably think of it
as an equation of fractions: $LM/MP=GN/GH$.  That is fine;
but~\eqref{Ar-prop} simply expresses a relation of
\emph{proportionality} among four
\emph{magnitudes.}\label{magnitude}  Here are Definitions 3--6 from Book V of Euclid's
\emph{Elements} \cite{MR17:814b,MR1932864}.
\begin{quote}
\noindent 3. A \textbf{ratio} is a sort of relation in respect of size
between two 
magnitudes of the same kind. 

\noindent 4.  Magnitudes are said to \textbf{have a ratio} to one
another which are capable, 
when multiplied, of exceeding one another. 


\noindent 5.  Magnitudes are said to \textbf{be in the same ratio,} the first
to the second 
  and the third to the fourth, when, if any equimultiples whatever be
  taken of the first and third, and any equimultiples whatever of the
  second and fourth, the former equimultiples alike exceed, are alike
  equal to, or alike fall short of, the latter equimultiples
  respectively taken in corresponding order. 

\noindent 6.  Let magnitudes which have the same ratio be called
\textbf{proportional.}
\end{quote}
Briefly, 4 means you can't have a ratio between a line and a square:
this may be one source of the concern expressed by Archimedes in
the quote above.  If $a$ and $b$ \emph{are} magnitudes with a ratio, and so
are $c$ and $d$, then by 5, we may say variously
\begin{enumerate}
\item $a$ is to $b$ in the same ratio that $c$ is to $d$,
\item
$a$ is to $b$ as $c$ is to $d$,
\item
$a:b::c:d$,
\end{enumerate}
provided that, whenever we take a multiple $na$ of $a$, and the same
multiple 
$nc$ of $c$, and a multiple $mb$ of $b$, and the same multiple $md$ of
$d$, then 
\begin{gather*}
  na>mb\text{ if and only if }nc>nd,\\
  na=mb\text{ if and only if }nc=nd,\\
  na<mb\text{ if and only if }nc<nd.
\end{gather*}
In Books V and VI of the \emph{Elements,} Euclid goes on to prove the
properties of proportionality that we shall need.

To return to our problem.  From $L$ draw a
straight line parallel to $BC$, meeting 
$AD$ at $Q$ and $AC$ at $R$.
Then by property~\ref{item:parab} of the parabola given above,
\begin{equation*}
  LQ^2:CD^2::AQ:AD.
\end{equation*}
Since $LQ=MD$, and triangle $ACD$ is similar to $NCM$, while $ARQ$ is
similar to $ACD$,
we can rewrite the proportion as
\begin{gather*}
  NA^2:AC^2::AR:AC.
\end{gather*}
Therefore $NA$ is a mean proportional of $AC$ and $AR$ (see Euclid's
VI.13, 20, and 23), so
\begin{align*}
  NA:AC&::AR:NA\\
       &::NA+AR:NA+AC\\
       &::NR:NC\\
       &::NL:NM.
\end{align*}
Since $AC=AG$, and $MN=NP$, we obtain
\begin{gather*}
  NA:AG::NL:NM,\\
AG-NA:AG::NM-NL:NM,\\
NG:AG::LM:NM,\\
NG:2AG::LM:2NM,\\
NG:GC::LM:MP,\\
NG:GH::LM:MP,
\end{gather*}
which is~\eqref{Ar-prop}, as desired.

Archimedes works out a rigorous formulation of this argument in the
\emph{Quadrature of the parabola,} but I prefer now to look at the
alternative proof, given for Proposition 24 of that work.

Start over from Figure~\ref{fig:parab}, getting Figure~\ref{fig:parab-rig}.
\begin{figure}[ht]
  \begin{pspicture}(-4,-4)(2,0.2)
%\psgrid
    \psplot{-4}{2}{x x mul neg 4 div}
\psline(-4,-4)(2,-1)(-1,-0.25)(-4,-4)
\psdots(-4,-4)(2,-1)(-1,-0.25)(-1,-2.5)
(0.5,-0.625)(0.5,-0.0625)(-1,-1.375)
(-1,-0.8125)(-0.25,-0.4375)(-2.5,-1.5625)
\uput[r](2,-1){$C$}
\uput[ul](-1,-0.25){$A$}
\uput[dl](-4,-4){$B$}
\psline(-1,-0.25)(-1,-2.5)
\uput[dr](-1,-2.5){$D$}
\uput[d](0.5,-0.625){$E$}
\psline(0.5,-0.625)(0.5,-0.0625)
\uput[ur](0.5,-0.0625){$F$}
\psline(-1,-0.25)(0.5,-0.0625)(2,-1)
\psline(0.5,-0.625)(-1,-1.375)
\uput[ul](-2.5,-1.5625){$G$}
\psline(-1,-0.25)(-2.5,-1.5625)(-4,-4)
\uput[l](-1,-1.375){$H$}
\psline(0.5,-0.0625)(-1,-0.8125)
\uput[l](-1,-0.8125){$K$}
\uput[d](-0.25,-0.4375){$L$}
  \end{pspicture}
  \caption{}\label{fig:parab-rig}
\end{figure}
Here $D$ is the midpoint of $BC$ as before, and $E$ is the midpoint of
$AB$.  From $E$ a straight line is drawn parallel to $DA$, meeting the
parabola at $F$.  Draw straight lines $AF$ and $FC$.  Then triangle
$ACF$ has the same altitude as the parabolic segment in which it is
inscribed.  Similarly we can find $G$ on the parabola between $A$ and
$B$ so that the inscribed triangle $ABG$ has the same height as its
parabolic segment.
We show that triangles $ACF$ and $ABG$ are together one fourth of triangle
$ABC$.

To this end, from $E$ and $F$ we draw parallels to $BC$, meeting $AD$
at $H$ and $K$ respectively.  Then
\begin{equation*}
  FK^2:CD^2::AK:AD.
\end{equation*}
But $FK=EH$, and
\begin{equation*}
  EH:CD::EA:CA::1:2.
\end{equation*}
Therefore $AK$ is one fourth of $AD$.  Consequently $K$ is the
midpoint of $AH$, and so $L$ is the midpoint of $AE$.  Hence triangle
$AKL$ is equal to triangle $EFL$.  But $EFL$ is one fourth of $ACF$,
and $AKL$ is one thirty-second of $ABC$.  Therefore $ACF$ is one
eighth of $ABC$.  Similarly, $ABG$ is one eighth of $ABC$; so $ABG$
and $ACF$ together are one fourth of $ABC$.

We have started with the parabolic segment cut off by the chord $BC$,
and 
we have removed from it the triangle $ABC$.  Then we have removed
triangles equal 
to a fourth of $ABC$.  We can continue, removing triangles equal to a
sixteenth of $ABC$, and so on.  Moreover, at each step, we remove more
than one half the remainder of the original parabolic segment (why?).

Therefore, if we continue long enough, we can make the remainder of
the parabolic segment less than any pre-assigned area $M$.  This is the
conclusion of Euclid's Proposition X.1; let us note the proof.  The
pre-assigned area $M$ is assumed to \emph{have a ratio} with the parabolic
segment, so that, by Definition V.4 above, some multiple $nM$ of $M$
exceeds the segment.  Indeed, Archimedes himself makes the assumption
explicit in the preface to the \emph{Quadrature of the parabola;} it
is what we may refer to as the \textbf{Archimedean axiom:}
\begin{quote}
  given [two] unequal areas, the exess by which the greater exceeds
  the less can, by being added to itself, be made to exceed any given
  finite area. \hfill\mbox{\cite[p.231]{MR13:419b}}
\end{quote}
If we take away at least half of the parabolic segment,
and take $M$ from $nM$, then in the latter case we are taking not more
than half; so the former remainder is still less than
the latter remainder.  If we repeat this process $n-1$ times, then the
remainder of the parabolic segment will be less than $M$.

Suppose we have an area that is a third again as large as triangle
$ABC$.  If we remove triangle $ABC$, what is left is one third.  If we
then remove one fourth of triangle $ABC$, then what is left is one
twelfth of that triangle, which is one fourth of the previous
remainder.  Continuing, if we remove one fourth of what we last
removed, then what remains is one fourth of the previous remainder.
Therefore, continuing as far as necessary, we can make the remainder
as small as we like.  But this is the same process as we described in
the original parabolic segment.

Suppose the original parabolic segment is \emph{not} a third again as
large as $ABC$, but is greater.  Let the difference be $M$.  We can
inscribe in the parabolic segment a rectilinear figure which differs
from the segment by less than $M$; so it is more than a third greater
than $ABC$, which is absurd.  There is a similar contradiction if the
parabolic segment is less than a third again as large as $ABC$.
Theorem~\ref{thm:Arch} now follows.

\newpage

\section{Construction of the rational numbers}\label{sect:N2Q}

You know something about the chain
\begin{equation}\label{chain}
  \N\pincluded\Z\pincluded\Q\pincluded\R
\end{equation}
of number systems.
Here $\N$ is the set $\{0,1,2,\dots\}$ of \textbf{natural numbers;}
$\Z$ comprises the \textbf{integers;} $\Q$, the \textbf{rationals;}
$\R$, the \textbf{real numbers.}
What comes after $\R$ in~\eqref{chain}?  It depends on how we think of
$\R$.  If we think of it as a \emph{field,} then we might think of
$\R$ as included in $\C$, the field of \textbf{complex numbers.}  But
what if we think of $\R$ as an \emph{ordered field?}  I postpone an
answer until \S~\ref{sect:non-Arch}.  Meanwhile I want to look at how
we obtain~\eqref{chain} in the first place.


\subsection{The natural numbers}\label{subsect:N}

We can understand $\N$ axiomatically.  First of all,
\begin{enumerate}
\item 
it has a distinguished \textbf{initial element} called $0$
  (\textbf{zero}); 
\item
it has a distinguished singulary operation of \textbf{succession,}
  denoted by $n\mapsto n+1$: here $n+1$ is the \textbf{successor} of
  $n$. 
\end{enumerate}
I propose to refer to the ordered triple $(\N,0,n\mapsto n+1)$ as an
\emph{iterative structure.}
In general, by an \textbf{iterative structure,} I mean any set that has a
distinuished element and a distinguished \emph{singulary operation}
(that is, a function from the set to itself).  For example, modular arithmetic
involves the iterative structures\footnote{Some people might write
  these structures as $(\Z/n,\bar0,\bar k\mapsto\overline{k+1})$, to
  make sure that the reader distinguishes a natural 
number $k$ from its congruence class \emph{modulo} $n$.} 
 $(\Z/n,0,k\mapsto k+1)$.  The iterative structure $(\N,0,n\mapsto n+1)$ is
distinguished among iterative structures for  satisfying the
following axioms.
\begin{enumerate}
\item\label{ax:0}
$0$ is not a successor: $0\neq n+1$.
\item\label{ax:inj}
Succession is injective: if $m+1=n+1$, then $m=n$.
\item\label{ax:ind}
the structure admits \textbf{proof by induction,} in the sense that the only
  subset $A$ with the following two closure
  properties is the whole set:
  \begin{enumerate}
  \item 
$0\in A$;
\item
for all $n$, if $n\in A$, then $n+1\in A$.
  \end{enumerate}
\end{enumerate}

These axioms seem to have been discovered originally by
Dedekind~\cite[II, VI (71), p.~67]{MR0159773}, although they were also
written down by 
Peano~\cite{Peano} and are often known as the \textbf{Peano axioms.}
From these axioms, Landau develops the rational, real, and complex
numbers rigorously, over the course of a book \cite{MR12:397m}.  I
want to do the same here, though more quickly and in a different
style.  Landau's natural numbers start with $1$, not $0$.
Also, Landau does not use the following theorem.  The
proof is difficult, but the result is very useful.

\begin{theorem}[Recursion]
For every iterative structure $(A,b,f)$, there is a unique
\textbf{homomorphism} to this structure from $(\N,0,n\mapsto n+1)$:
that is, there is a unique function $h$ from $\N$ to 
$A$ such that
\begin{enumerate}
\item 
$h(0)=b$,
\item
$h(n+1)=f(h(n))$ for all $n$ in $\N$.
\end{enumerate}
\end{theorem}

\begin{proof}
I use the set-theoretic conception whereby a function $g$ is just
the set of ordered pairs $(x,y)$ such that $g(x)=y$; so if $(x,y)$ and
$(x,z)$ belong to $g$, then $y=z$.  We now seek $h$ as a particular
subset of $\N\times A$.

Let $B$ be the set whose elements are the subsets $C$ of $\N\times
A$ such that, if $(x,y)\in C$, then either 
\begin{enumerate}
\item 
$(x,y)=(0,b)$ or else
\item $C$ has an element
$(u,v)$ such that $(x,y)=(u+1,f(v))$.
\end{enumerate}
Let $R=\bigcup B$; so $R$ is a subset of $\N\times A$.  We may say $R$
is a \emph{relation} from $\N$ to $A$.  If
$(x,y)\in R$, we may write also 
\begin{equation*}
x\mathrel Ry.  
\end{equation*}
Since ${(0,b)}\in
B$, we have $0\mathrel Rb$.  If $n\mathrel Ry$, then $(n,y)\in C$ for
some $C$ in $B$, but then $C\cup\{(n+1,f(y))\}\in B$ by definition of $B$, so
$(n+1)\mathrel R f(y)$.  Therefore $R$ is the desired function $h$,
provided it is a \emph{function} from $\N$ to $A$.  Proving this has
two stages.
\begin{asparaenum}[1.]
  \item
For all $n$ in $\N$, there is $y$ in $A$ such that $n\mathrel Ry$.
Indeed, let $D$ be the set of such $n$.  Then we have just seen that
$0\in D$, and if $n\in D$, then $n+1\in D$.  By induction, $D=\N$.
\item
For all $n$ in $\N$, if $n\mathrel Ry$ and $n\mathrel Rz$, then $y=z$.
Indeed, let $E$ be the set of such $n$.  Suppose $0\mathrel R y$.  Then
$(0,y)\in C$ for some $C$ in $B$.  Since $0$ is not a successor, we
must have $y=b$, by definition of $B$.  Therefore $0\in E$.  Suppose
$n\in E$, and $(n+1)\mathrel Ry$.  Then $(n+1,y)\in C$ for some $C$ in
$B$.  Again since $0$ is not a successor, we must have
$(n+1,y)=(m+1,f(v))$ for some $(m,v)$ in $C$.  Since succession is
injective, we must have $m=n$.  Since $n\in E$, we know $v$ is
\emph{unique} such that $n\mathrel Rv$.  Since $y=f(v)$, therefore $y$
is unique such that $(n+1)\mathrel Ry$.  Thus $n+1\in E$.  By
induction, $E=\N$.
\end{asparaenum}

So $R$ is the desired function $h$.
Finally, $h$ is unique by induction.
\end{proof}

\begin{corollary}
For every set $A$ with a distinguished element $b$, and for every function
$F$ from $\N\times B$ to $B$, there is a unique function $H$ from $\N$ to
$A$ such that
\begin{enumerate}
\item 
$H(0)=b$,
\item
$H(n+1)=F(n,H(n))$ for all $n$ in $\N$.
\end{enumerate}
\end{corollary}

\begin{proof}
Let $h$ be the unique homomorphism from $(\N,0,n\mapsto n+1)$ to
$(\N\times A,(0,b),f)$, where $f$ is the operation
$(n,x)\mapsto(n+1,F(n,x)))$.  In particular, $h(n)$ is always an
ordered pair.  By induction, the 
first entry of $h(n)$ is always $n$; so there is a function $H$ from
$\N$ to $A$ such that $h(n)=(n,H(n))$.  Then $H$ is as desired.  By
induction, $H$ is unique.
\end{proof}

The proof of the Recursion Theorem used each of the three Peano
axioms; induction alone would not
enough.  Indeed, if some iterative structure
$\str A$ has the property
that is
guaranteed to $(\N,0,n\mapsto n+1)$ by the Recursion Theorem, then
$\str A$ is \textbf{isomorphic} to $\N$ (why?), and consequently
$\str A$ satisfies the Peano axioms.\footnote{Here $\str A$ is
  the Fraktur version of $A$.  The idea is that $A$ is just a set, but
  $\str A$ is that set together with some other things---here a
  distinguished element and singulary operation.  Then $A$ is the
  \textbf{universe} of $\str A$.  I shall not later distinguish
  notationally between structures and their universes.  If I did want
  to make a distinction, I would use the letters depicted in
  Appendix~\ref{app:German}.}   But these axioms are
independent.  For example, $(\Z/n,0, k\mapsto k+ 1)$
satisfies axioms~\ref{ax:inj} and~\ref{ax:ind}, but not~\ref{ax:0};
and there are examples satisfying~\ref{ax:0} and~\ref{ax:ind}, but
not~\ref{ax:inj}; and satisfying~\ref{ax:0} and~\ref{ax:inj}, but
not~\ref{ax:ind} (can you find them?).

Moreover, it is possible to 
assume the Recursion Theorem and \emph{prove} the Peano axioms from it.

We can now use recursion to \emph{define} the binary operation
$(x,y)\mapsto x+y$
of \textbf{addition,} along with the binary operation
$(x,y)\mapsto x\cdot y$ or $(x,y)\mapsto xy$
of \textbf{multiplication,} on
$\N$.  The definitions are:
\begin{align*}
    n+0&=n,&     n+(m+1)&=(n+m)+1,&
n\cdot0&=0,& n\cdot(m+1)&=n\cdot m+n.
\end{align*}

\begin{lemma}\label{lem:+}
For all $n$ and $m$ in $\N$,
\begin{align*}
  0+n&=n,&(m+1)+n&=(m+n)+1.
\end{align*}
\end{lemma}

\begin{proof}
  Induction.
\end{proof}

\begin{theorem}
Addition on $\N$ is
  \begin{enumerate}
  \item 
\textbf{commutative:} $n+m=m+n$; and
\item
\textbf{associative:} $n+(m+k)=(n+m)+k$.
  \end{enumerate}
\end{theorem}

\begin{proof}
  Induction and the lemma.
\end{proof}

\begin{theorem}\label{thm:cancel}
  Addition on $\N$ allows \textbf{cancellation:}
if $n+x=n+y$, then $x=y$.
\end{theorem}

\begin{proof}
  Induction, and injectivity of succession.
\end{proof}

\begin{lemma}\label{lem:.}
For all $n$ and $m$ in $\N$,
\begin{align*}
  0\cdot n&=0,&(m+1)\cdot n&=m\cdot n+n.
\end{align*}
\end{lemma}

\begin{proof}
  Induction.
\end{proof}

\begin{theorem}
Multiplication on $\N$ is
  \begin{enumerate}
  \item 
commutative: $nm=mn$;
\item
\textbf{distributive} over addition: $n(m+k)=nm+nk$; and
\item
associative: $n(mk)=(nm)k$.
  \end{enumerate}
\end{theorem}

\begin{proof}
  Induction and the lemma.
\end{proof}

Landau proves \emph{using induction alone} that $+$ and $\cdot$ exist
as given by the recursive definitions above.  Note however that
Theorem~\ref{thm:cancel} needs more than induction (why?).  Also, the
existence of \textbf{exponentiation,} as an operation $(x,y)\mapsto
x^y$ such that
\begin{align*}
  n^0&=1,& n^{m+1}&=n^m\cdot n,
\end{align*}
requires more than induction.

The usual ordering $<$ of $\N$ is defined recursively as follows.
First note that $m\leq n$ means simply $m<n$ or $m=n$.  Then the
definition of $<$ is:
\begin{enumerate}
\item 
$m\not<0$;% for \emph{no} $m$ in $\N$;
\item
$m<n+1$ if and only if $m\leq n$.
\end{enumerate}
In particular, $n<n+1$.
Really, it is the sets $\{x\in\N\colon x<n\}$ that are defined by
recursion:
\begin{enumerate}
\item 
$\{x\in\N\colon x<0\}=\emptyset$;
\item
$\{x\in\N\colon x<n+1\}=\{x\in\N\colon x<n\}\cup\{n\}$.
\end{enumerate}
We now have $<$ as a binary relation on $\N$;
we must \emph{prove} that it is an ordering.

\begin{theorem}\label{thm:<trans}
  The relation $<$ is \textbf{transitive} on $\N$, that is, if $k<m$
  and $m<n$, then $k<n$.
\end{theorem}

\begin{proof}
  Induction on $n$.
\end{proof}

\begin{lemma}
  $m\neq m+1$.
\end{lemma}

\begin{proof}
  The claim is true when $m=0$, since $0$ is not a successor.  Suppose
  the claim is true when $m=k$, that is, $k\neq k+1$.  Then $k+1\neq
  (k+1)+1$, by injectivity of succession, so the claim is true when
  $m=k+1$.  By induction, the claim is true for all $m$.
\end{proof}

\begin{theorem}\label{thm:<irr}
  The relation $<$ is \textbf{irreflexive} on $\N$:  $m\not<m$.
\end{theorem}

\begin{proof}
  The claim is true when $m=0$, since $m\not<0$ by definition.
  Suppose the claim \emph{fails} when $m=k+1$.  This means $k+1<k+1$.
  Therefore $k+1\leq k$ by definition.  By the previous lemma,
  $k+1<k$.  But $k\leq k$, so $k<k+1$ by definition.  So $k<k+1$ and
  $k+1<k$; hence $k<k$ by
  Theorem~\ref{thm:<trans}, that is, the claim fails when $m=k$.  By
  induction, the claim holds for all $m$. 
\end{proof}

\begin{lemma}
%  \mbox{}
  \begin{enumerate}
  \item 
$0\leq m$.
\item
If $k<m$, then $k+1\leq m$.
  \end{enumerate}
\end{lemma}

\begin{proof}
  \begin{asparaenum}
  \item 
Induction.
\item
The claim is vacuously true when $m=0$.  Suppose it is true when
$m=n$.  Say $k<n+1$.  Then $k\leq n$.  If $k=n$, then
$k+1=n+1<(n+1)+1$.  If $k<n$, then $k+1<n+1$ by inductive hypothesis,
so $k+1<(n+1)+1$ by transitivity.  Thus the claim holds when $m=n+1$.
By induction, the claim holds for all $m$.\qedhere
  \end{asparaenum}
\end{proof}

\begin{theorem}\label{thm:<tot}
  The relation $\leq$ is \textbf{total} on $\N$: either $k\leq m$ or
  $m\leq k$.
\end{theorem}

\begin{proof}
  Induction and the lemma.
\end{proof}

Because of Theorems~\ref{thm:<trans},~\ref{thm:<irr},
and~\ref{thm:<tot}, the set $\N$ is \textbf{(strictly) ordered} by $<$.

\begin{theorem}\label{thm:m+x=n}
  For all $m$ and $n$ in $\N$, we have $m\leq n$ if and only if the
  equation
  \begin{equation}\label{eqn:m+x=n}
    m+x=n
  \end{equation}
is soluble in $\N$.
\end{theorem}

\begin{proof}
  By induction on $k$, if $m+k=n$, then $m\leq n$.  

Conversely, if $m\leq0$, then $m=0$ (why?), so $m+0=0$.
Suppose the equation $m+x=r$ is soluble whenever $m\leq r$, but now $m\leq r+1$.
If $m=r+1$, then $m+0=r+1$.  If $m<r+1$, then $m\leq r$, so the
equation $m+x=r$ has a solution $k$, and therefore $m+(k+1)=r+1$.
Thus the equation $m+x=r+1$ is soluble whenever $m\leq r+1$.
By
induction, for all $n$ in $\N$, if $m\leq n$, then~\eqref{eqn:m+x=n}
is soluble in $\N$. 
\end{proof}

\begin{theorem}\label{thm:N<}
  \begin{enumerate}
  \item\label{part:<+}
If $k<\ell$, then $k+m<\ell+m$.
\item\label{part:cancel}
If $k<\ell$ and $m\neq0$, then $km<\ell m$.
  \end{enumerate}
\end{theorem}

Here part~\ref{part:<+} is a refinement of Theorem~\ref{thm:cancel},
and part~\ref{part:cancel} yields the following analogue of
Theorem~\ref{thm:cancel} for multiplication.

\begin{corollary}
  If $km=\ell m$ and $m\neq0$, then $k=\ell$.
\end{corollary}

\begin{theorem}\label{thm:wo}
  $\N$ is \textbf{well ordered} by $<$: every nonempty set of natural
  numbers has a least element.
\end{theorem}

\begin{proof}
  Suppose $A$ is a set of natural numbers with no least element.  Let
  $B$ be the set of natural numbers $n$ such that, if $m\leq n$, then
  $m\notin A$.  Then
  $0\in B$, by the last lemma, since otherwise $0$ would be the least
  element of $A$.  Suppose $m\in B$.  Then $m+1\in B$, since otherwise
  $m+1$ would be the least element of $A$.  By induction, $B=\N$, so
  $A=\emptyset$. 
\end{proof}

\subsection{The positive rationals}\label{subsect:+rat}

The integers can be constructed from the natural numbers; and the
rationals, from the integers.  Since the latter construction is
probably more familiar than the former, I begin with it; rather, I
construct the \emph{positive} rational numbers from the
\textbf{positive integers,} which we already have: the are just the
non-zero natural numbers.  

Let us denote the set of positive integers by $\N^+$, so
\begin{equation*}
  \N^+=\N\setminus\{0\}.
\end{equation*}
We want to define a set
\begin{equation*}
  \Q^+
\end{equation*}
of \textbf{positive rationals.}  These are certain
\textbf{fractions,} namely
numbers of the form
\begin{equation*}
  \frac ab
\end{equation*}
or $a/b$.  In particular, $a/b\in\Q^+$ if and only if $a$ and $b$ are
in $\N^+$.   
But what does this \emph{mean?}  

One is
taught in school that arithmetic of fractions obeys the
following rules: 
\begin{align}\label{eqn:Q}
  \frac ab+\frac cd&=\frac{ad+bc}{bd},&
\frac ab\cdot\frac cd&=\frac{ac}{bd}.
\end{align}
%Also $a/b<c/d$ if and only if $ad<bc$.
However, in $\Q^+$, one must \emph{prove} that these rules are valid,
because the positive rational number $a/b$ does not uniquely determine
the ordered pair $(a,b)$ of positive integers.  For example,
$1/2=2/4$, although $(1,2)\neq(2,4)$.

One might try defining a new operation $\oplus$ on $\Q^+$ by writing
down a formula like\footnote{This example, and the difficulty it
  illustrates, are discussed on [Timothy] Gowers's Weblog at
  \url{http://gowers.wordpress.com/2009/06/08/why-arent-all-functions-well-defined/}.} 
\begin{equation}\label{eqn:oplus}
  \frac ab\oplus\frac cd=\frac{a+c}{b+d}.
\end{equation}
But this implies $1/2\oplus 1/3=2/5$, while $2/4\oplus
1/3=3/7$.  Since $1/2=2/4$, while $2/5\neq 3/7$, we conclude that
$\oplus$ is not \emph{well defined.}  This is a common loose way of
speaking.  The point is that there is no operation $\oplus$ on $\Q^+$ with the
property required by~\eqref{eqn:oplus}.

On the set
$\N^+\times \N^+$ or $(\N^+)^2$, let $\sim$ be the
relation given by 
\begin{equation}\label{eqn:sim}
  (a,b)\sim(c,d)\iff ad=bc.
\end{equation}
One checks easily that $\sim$ is \textbf{reflexive} ($x\sim x$),
\textbf{symmetric} ($x\sim y$ if and only if $y\sim x$) and
\textbf{transitive} 
(if $x\sim y$ and $y\sim z$, then $x\sim z$).  By definition therefore,
$\sim$ is an \textbf{equivalence relation.}  If $a$ and $b$ are in
$\N^+$, we can now define $a/b$ precisely: it is the
set of elements of $(\N^+)^2$ that are equivalent
to $(a,b)$ with respect to $\sim$.  Thus
\begin{equation*}
  \frac ab=\{(x,y)\in(\N^+)^2\colon ay=bx\}.
\end{equation*}
Traditionally, $a/b$ is therefore called the \textbf{equivalence
  class} of $(a,b)$ with respect to $\sim$.
Then $\Q^+$ is the set of such equivalence classes; we might write
\begin{equation*}
  \Q^+=(\N^+)^2/\mathord{\sim}.
\end{equation*}
Now we can check that the rules
in~\eqref{eqn:Q} are valid.  Supposing $a/b=a'/b'$ and $c/d=c'/d'$, we
have $ab'=ba'$ and $cd'=dc'$, so for example 
\begin{equation*}
  acb'd'=ab'cd'=ba'dc'=bda'c',
\end{equation*}
and therefore $ac/bd=a'c'/b'd'$.

Considering~\eqref{eqn:oplus} again, note that there is indeed a
function $f$ from $(\N^+)^2\times(\N^+)^2$ to $\Q^+$ given by
\begin{equation*}
  f\bigl((x,y),(z,w)\bigr)=\frac{x+z}{y+w}.
\end{equation*}
There are just no functions $g$ from $(\N^+)^2\times (\N^+)^2$ to
$\Q^+\times \Q^+$ and $h$ from $\Q^+\times \Q^+$ to $\Q^+$ such that
$f=h\circ g$. 

By our construction, a positive integer is not literally a positive
rational, because a positive rational is a class of pairs of positive
integers.  However, the 
positive integers embed in the positive rationals under the map
\begin{equation*}
  x\mapsto\frac x1.
\end{equation*}
This embedding respects arithmetic:  $a/1+b/1=(a+b)/1$ and
$(a/1)(b/1)=(ab)/1$.  It also respects the ordering, where we define
\begin{equation*}
  \frac ab<\frac cd\iff ad<bc.
\end{equation*}
On $\Q^+$ there is a binary operation $(x,y)\mapsto x\div y$ of
\textbf{division,} given by
\begin{equation*}
\frac ab\div\frac cd=\frac{ad}{bc};
\end{equation*}
one checks that division is indeed well defined.  In particular, we
have 
\begin{equation*}
  \frac a1\div\frac b1=\frac ab.
\end{equation*}
We usually confuse a
positive integer $a$ with the positive rational $a/1$, and for $x\div
y$ we write $x/y$.  For $1/a$, we write $a\inv$.

\subsection{The integers}

If $a$ and $b$ are in $\N^+$, then the equation
\begin{equation}\label{eqn:.}
  a=bx
\end{equation}
may or may not have a solution in $\N^+$.  Suppose it does have a
solution; this solution is unique by the corollary to
Theorem~\ref{thm:N<}.  If $c$ and $d$ are also in $\N^+$, and the equation
\begin{equation}\label{eqn:.2}
  c=dx
\end{equation}
has a solution in $\N^+$, then it is the \emph{same} solution
that~\eqref{eqn:.} has if and only if 
\begin{equation}\label{eqn:ad=bc}
  ad=bc
\end{equation}
(why?).  Then $\Q^+$ is
defined 
to ensure two things:
\begin{enumerate}
\item 
the equation~\eqref{eqn:.} always has a solution in $\Q^+$;
\item
equations~\eqref{eqn:.} and~\eqref{eqn:.2} have the same solution in
$\Q^+$ if and only if~\eqref{eqn:ad=bc} holds.
\end{enumerate}
The integers can be understood to arise from the natural numbers in
the same way, with addition taking the place of multiplication.
If $m$ and $n$ are in $\N$ and $m\leq n$,
then~\eqref{eqn:m+x=n} has a 
solution by Theorem~\ref{thm:m+x=n}; moreover, this solution is
\emph{unique} (why?).
In this case, the equation $k+x=\ell$ has the same solution if and
only if
$m+\ell=n+k$.  We use this idea to define an equivalence relation
$\approx$ on $\N\times\N$ or $\N^2$ by
\begin{equation}\label{eqn:approx}
  (m,n)\approx(k,\ell)\iff m+\ell=n+k.
\end{equation}
The equivalence class of $(m,n)$ with respect to
$\approx$ can be denoted by
\begin{equation*}
  m\dotdiv n.
\end{equation*}
We denote the set of all such
classes by $\Z$; this is the set of \textbf{integers.}  So we have
\begin{equation}\label{eqn:Z}
  \Z=\N^2/\mathord{\approx}.
\end{equation}
One checks that arithmetic can be defined on $\Z$ by
\begin{align*}
(m\dotdiv n)+(k\dotdiv\ell)&=(m+k)\dotdiv(n+\ell),&
%  [m,n]+[k,\ell]&=[m+k,n+\ell],&
(m\dotdiv n)\cdot(k\dotdiv\ell)&=(mk+n\ell)\dotdiv(m\ell+nk);
%[m,n]\cdot[k,\ell]&=[mk+n\ell,m\ell+nk];
\end{align*}
and a strict ordering, by
\begin{equation*}
m\dotdiv n<k\dotdiv\ell
%  [m,n]<[k,\ell]
\iff m+\ell< n+k.
\end{equation*}
We can embed $\N$ in $\Z$ by the map
\begin{equation*}
  x\mapsto x\dotdiv 0.
%[x,0].
\end{equation*}
For the class $0\dotdiv n$, we introduce the name
\begin{equation*}
  -n.
\end{equation*}
We identify $\N$ with its image in $\Z$.  
The function
$(x,y)\mapsto x\dotdiv y$ from $\N^2$ to $\Z$ extends to the binary
operation of \textbf{subtraction} on $\Z$, given by
\begin{equation*}
  (m\dotdiv n)-(k\dotdiv\ell)=(m+\ell)\dotdiv(n+k).
\end{equation*}

\begin{lemma}
Every element of $\Z$ is either $n$ or $-n$ for some unique $n$ in $\N$.
\end{lemma}

We can now define \textbf{multiplication} on $\Z$ as usual by
\begin{align*}
-m\cdot -n&=m\cdot n,& -m\cdot n&=m\cdot -n=-(m\cdot n),
\end{align*}
where $m$ and $n$ are in $\N$.

\begin{theorem}
  $\Z$ is an \textbf{integral domain,} that is,
\begin{enumerate}
\item
it contains the additive identity $0$ and the
multiplicative identity $1$,
\item 
addition is commutative and associative,
\item
equations~\eqref{eqn:m+x=n} are always soluble;
\item
multiplication is commutative and associative;
\item
multiplication distributes over addition,
\item
if $x\cdot y=0$, but $x\neq0$, then $y=0$.
\end{enumerate}
\end{theorem}

\subsection{The rationals}

The construction of the \textbf{rationals} in general proceeds just as
for the positive rationals in~\ref{subsect:+rat}, only now the
relation $\sim$ defined in~\eqref{eqn:sim} must be understood as a
relation on $\Z\times(\Z\setminus\{0\})$.  The set of classes $m/n$,
where $m\in \Z$ and $n\in\Z\setminus\{0\}$, is denoted by $\Q$; so
\begin{equation*}
  \Q=(\Z\times(\Z\setminus\{0\}))/\mathord{\sim}.
\end{equation*}

\begin{lemma}
  $\Q$ is a \textbf{field,} that is,
\begin{enumerate}
\item
it is an integral domain,
\item
equations~\eqref{eqn:.} are always soluble when $b\neq0$.
\end{enumerate}
\end{lemma}

\begin{theorem}
  $\Q$ is an \textbf{ordered field,} that is, 
  \begin{enumerate}
  \item 
  it is both a field and
  an ordered set, 
\item
for all nonzero elements $x$, exactly one of $x$
  and $-x$ is positive,
\item
the the sum and product of two positive
  elements is always positive.
  \end{enumerate}
\end{theorem}

On any ordered field, there is an operation $x\mapsto\abs x$, where
\begin{equation*}
  \abs a=
  \begin{cases}
    a,&\text{ if }a\geq0;\\
   -a,&\text{ if }a<0.
  \end{cases}
\end{equation*}
Here $\abs a$ is the \textbf{absolute value} of $a$.  An absolute
value is always positive or $0$.

\begin{theorem}\label{thm:Q=subfield}
$\Q$ embeds uniquely in every ordered field.  
\end{theorem}

\begin{proof}
  Suppose $K$ is an ordered field.  Then $K$ contains elements $0$ and
  $1$, and so there is a unique homomorphism $h$ from $(\N,0,n\mapsto n+1)$
  to $(K,0,x\mapsto x+1)$.  By induction on $n$, if $m<n$ in $\N$,
  then $h(m)<h(n)$.  Therefore $h$ is injective.  Hence we can treat
  $\N$ as a subset of $K$, and then we can construct $\Q$ inside $K$. 
\end{proof}

We can now replace $\Z$ with its
image in $\Q$.

\begin{theorem}\label{thm:density}
  The ordering of every ordered field is \textbf{dense,} that is, if
  $x$ and $y$ are elements of the field, and $x<y$, then there is $z$
  in the field such that $x<z<y$.
\end{theorem}

\begin{proof}
  Let $z=(x+y)/2$.
\end{proof}

An ordered set is
\textbf{complete} if every nonempty subset with an upper bound has a
\emph{least} upper bound.  If a subset does have a least upper bound,
then it is unique and is called the \textbf{supremum} of the subset.
A \emph{greatest lower} bound is called an \textbf{infimum.}

\begin{theorem}
  In a complete ordered set, every nonempty subset with a lower bound
  has an infimum.
\end{theorem}

\begin{proof}
  Suppose $A$ has an element $b$ and a lower bound.  Let $C$ be the
  set of lower bounds of $A$.  Then $C$ is nonempty and has the upper
  bound $b$.  A supremum of $C$ is an infimum of $A$.  Indeed, suppose
  $d$ is a supremum of $C$.  If $x<d$, then there is $y$ in $C$ such
  that $x<y\leq d$, so in particular $x\notin A$.  Thus $d$ is a lower
  bound of $A$.  In particular, $d\in C$; so $d$ is the greatest of
  the lower bounds of $A$.
\end{proof}



Even though $\Q$ is dense as an ordered set, we shall show that it is
not complete.

\begin{theorem}\label{thm:2}
  The equation
  \begin{equation}\label{eqn:2}
    x^2=2
  \end{equation}
has no solution in $\Q$.
\end{theorem}

\begin{proof}
We can use the method of \textbf{infinite descent.}
  Suppose there were a solution, $n/m$.  We may assume $m$ and $n$ are
  positive integers.  Then $n^2=2m^2$, so $n$ must be \emph{even:} say
  $n=2k$.  So $4k^2=2m^2$, hence $2k^2=m^2$.  Thus $m/k$ is also a
  solution to~\eqref{eqn:2}.  But $0<m<n$.  Thus there is no
  \emph{least} $n$ in $\N$ such that, for
  some $m$ in $\N$, $n/m$ solves~\eqref{eqn:2}.
  Therefore~\eqref{eqn:2} has no solution, by Theorem~\ref{thm:wo}.
\end{proof}

\begin{theorem}\label{thm:sqrt2}
  The set $\{x\in\Q\colon x^2<2\}$ has an upper bound in $\Q$, but no
  supremum.
\end{theorem}

\begin{proof}
  Call the set $A$.  It has $2$ as an upper bound.  Suppose $b$ is an
  upper bound.  We show:
  \begin{enumerate}
  \item \label{part:2<b^2}
$2<b^2$;
\item\label{part:Ab}
$A$ has upper bounds less than $b$.
  \end{enumerate}
For~\ref{part:2<b^2}, suppose $c\in\Q$ and $c^2\leq 2$.  We show $c$
is \emph{not} an 
upper bound of $A$ by finding some  positive $h$ in $\Q$ such that
$(c+h)^2<2$. 
For all $h$, we have
\begin{equation*}
  (c+h)^2=c^2+2ch+h^2=c^2+(2c+h)h.
\end{equation*}
We have $c^2<2$ by Theorem~\ref{thm:2}, and moreover $c<2$.
If also $0<h<1$, then $2c+h<5$, so
\begin{equation*}
  (c+h)^2<c^2+5h.
\end{equation*}
Thus, if we require also $h<(2-c^2)/5$, then $(c+h)^2<2$.  We can
certainly find such $h$; just let $h$ be the lesser of $1/2$ and
$(2-c^2)/6$.  Therefore
$c$ is not an upper bound of $A$.  This proves~\ref{part:2<b^2}.

For~\ref{part:Ab}, since $2$ is an upper bound for $A$, we may assume
$b\leq2$.  If $k>0$, then
\begin{equation*}
  (b-k)^2=b^2-2bk+k^2>b^2-2bk\geq b^2-4k.
\end{equation*}
Let also $k<(b^2-2)/4$; then $(b-k)^2>2$, so $b-k$ is an upper bound
of $A$ that is less than $b$.
\end{proof}

\newpage

\section{Construction of the real numbers}\label{sect:reals}



As a consequence of Theorem~\ref{thm:sqrt2}, we can write $\Q$ as the
union of two 
nonempty disjoint sets $A$ and $B$, where
\begin{enumerate}
\item 
each element of $A$ is less than each element of $B$;
\item
$A$ has no greatest element;
\item
$B$ has no least element.
\end{enumerate}
Indeed, just let $A=\{x\in\Q\colon x<0\lor x^2<2\}$, and
$B=\{x\in\Q\colon x>0\land x^2>2\}$.  See Figure~\ref{fig:cut}.
\begin{figure}[ht]
  \begin{pspicture}(-5,-0.1)(5,0.5)
\psline{o->}(-1,0)(-5,0)
\psline{o->}(1,0)(5,0)
\uput[u](-3,0){$A$}
\uput[u](3,0){$B$}
  \end{pspicture}
  \caption{}\label{fig:cut}
\end{figure}
Here the pair $(A,B)$ is an example of a \emph{cut} in the sense of
Dedekind \cite[I, IV., pp.~12~f.]{MR0159773}.  Since $B$ can be
obtained from $A$ as $\Q\setminus A$, we may just refer to $A$ as a
cut.  To be precise then, we define a
\textbf{cut} of $\Q$ to be a nonempty proper subset $A$ of $\Q$ such
that 
\begin{enumerate}
\item 
every element of $A$ is less than every element of $\Q\setminus A$,
\item\label{item:no-least}
if $A$ has a supremum
  in $\Q$, then it belongs to $A$.
\end{enumerate}
So a cut may be as in Figure~\ref{fig:cut} \emph{or}~\ref{fig:cut2}.
\begin{figure}[ht]
  \begin{pspicture}(-5,-0.1)(5,0.5)
\psline{->}(-1,0)(-5,0)
\psdot(-1,0)
\psline{o->}(1,0)(5,0)
\uput[u](-3,0){$A$}
\uput[u](3,0){$B$}
  \end{pspicture}
  \caption{}\label{fig:cut2}
\end{figure}
Note that condition~\ref{item:no-least} is somewhat arbitrary; one might alternatively require any supremum of $A$ \emph{not} to belong to $A$.
We denote the set of cuts of $\Q$ by
\begin{equation*}
  \R.
\end{equation*}
That is, a cut of $\Q$ is precisely a \textbf{real number.}

Dedekind \cite[I]{MR0159773} observes that this construction of $\R$
results in the complete ordered field that we want.  Details are
worked out in Landau~\cite{MR12:397m}, and also in
 Spivak's \emph{Calculus} \cite[ch.~28]{Spivak-Calc}.
Spivak writes,
\begin{quote}
  The mass of drudgery which this chapter necessarily contains is
  relieved by one truly first-rate idea
\end{quote}
---namely, the idea of what Dedekind calls a cut.  My own view is
that, in mathematics, if you think something is drudgery, then perhaps
you are not looking at it the right way.

\subsection{Cuts}

In the interest of finding some insight in the construction of $\R$, I
note that the notion of a cut makes sense in 
any ordered set.  
Suppose $A$ is an ordered set.  
If $b\in A$, let us define
\begin{equation*}
	(b)=\{x\in A\colon x\leq b\}.
\end{equation*}
Note then that
\begin{equation*}
(x)\cup (y)=(\max(x,y)).
\end{equation*}
The collection of sets $(b)$ is thus closed under binary intersection; therefore these sets are \textbf{basic closed sets} for a \emph{topology} on $A$.  In particular, the intersection of any collection of basic closed subsets of $A$ is a \textbf{closed set} in this topology.  A \textbf{cut} of $A$ is a non-empty closed subset of $A$, except for $A$ itself unless it has a maximum element.  In particular, every \emph{basic} closed subset of $A$ is a cut; but the empty set is a closed set that is not a cut.  Let us denote by
\begin{equation*}
\completion A
\end{equation*}
the set of all cuts of $A$.

\begin{theorem}\label{thm:completions}
Let $A$ be an ordered set.
\begin{enumerate}
\item
The set $\completion A$ is ordered by inclusion:
\begin{equation*}
  X<Y\iff X\pincluded Y.
\end{equation*}
	\item 
	The map $x\mapsto(x)$ from $A$ to $\completion A$ is an embedding of ordered sets.
	\item
	The ordered set $\completion A$ is complete: indeed, if $B$ is a non-empty subset of $\completion A$ with an upper bound, then
	\begin{equation*}
\sup(B)=\bigcap\{(x)\colon\textstyle\bigcup B\included(x)\}.
\end{equation*}
	\item
	If $X\in\completion A$, then
	\begin{equation}\label{eqn:Xsup}
X=\sup(\{(x)\colon(x)\included X\})=\bigcap\{(y)\colon X\included(y)\}.
\end{equation}
\item
The ordered set $\completion A$ is a \textbf{completion} of $A$ in the sense that,
if $f$ is an embedding of $A$ in a complete ordered set $C$, then the map
\begin{equation*}
X\mapsto\sup(\{f(x)\colon(x)\included X\})
\end{equation*}
is an embedding $\completion f$ of $\completion A$ in $C$ such that
\begin{equation}\label{eqn:bar-f}
\completion f((x))=f(x).
\end{equation}
\item
If, further, $C$ is another completion of $A$, then $\completion f$ is an isomorphism.
\end{enumerate}
\end{theorem}

\begin{proof}
\begin{asparaenum}[1.]\setcounter{enumi}{1}
\item
If $x<y$, then $(x)\pincluded(y)$.
\item
Suppose $B$ is a nonempty subset of $\completion A$ with an upper bound.  Then it has an upper bound $(c)$, and
the set $\bigcap\{(x)\colon\bigcup B\included(x)\}$ is an element $B^*$ of $\completion A$ and is an upper bound of $B$, and $B^*\included(c)$.  Every upper bound of $B$ is the intersection of a nonempty collection of such upper bounds $(c)$.  Therefore $B^*$ is the supremum of $B$.
\item
Immediately $\sup(\{(x)\colon(x)\included X\})\included X$.  If $Y$ is an element of $\completion A$ such that 
\begin{equation*}
\sup(\{(x)\colon(x)\included X\})\pincluded Y, 
\end{equation*}
then the set $\{(x)\colon(x)\included X\}$ has an upper bound $(d)$ that is less than $Y$, so that $B\included(d)\pincluded Y$; thus $X\neq Y$.
\item
Easily~\eqref{eqn:bar-f} holds.
Among elements of $\completion A$, if $X\pincluded Y$, then $X\included(u)\pincluded(v)\included Y$ for some $u$ and $v$ in $A$, so that
\begin{equation*}
\completion f(X)\leq\completion f((u))<\completion f((v))\leq\completion f(Y).
\end{equation*}
Thus $\completion f$ is an embedding of ordered sets.
\item
The ordered set $\completion A$ is \emph{the} completion of $A$ in the sense that,
if $C$ is also a completion, then it embeds in $\completion A$ under a map $g$, where
\begin{equation*}
g\circ f(x)=(x).
\end{equation*}
By~\eqref{eqn:bar-f}, we now have $g\circ\completion f((x))=(x)$.  Say $X\in \completion A$.  By~\eqref{eqn:Xsup}, we have
\begin{equation*}
X\leq g\circ\completion f(X).
\end{equation*}
If $X<Y$, then $X\leq(z)<Y$ for some $z$ in $A$, so that $g\circ\completion f(X)\leq g\circ\completion f((z))=(z)<Y$; this shows $g\circ\completion f(X)\leq X$.  Thus $g\circ\completion f$ is a bijection from $\completion A$ to itself.   Since $g$ is injective, $\completion f$ must be surjective.
\qedhere
\end{asparaenum}
\end{proof}

\subsection{Ordered Abelian groups}

An \textbf{ordered Abelian group} is an Abelian group that is ordered
so that
\begin{equation}\label{eqn:<+}
  x<y\implies x+z<y+z;
\end{equation}
equivalently,
\begin{align*}
  x>0&\iff -x<0,& x>0\land y>0&\implies x+y>0.
\end{align*}
Here those $x$ such that $x>0$ are \textbf{positive.}  
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{comment}

As usual, we
define
\begin{equation*}
  \abs x=
  \begin{cases}
    x,&\text{ if }x\geq0;\\
-x,&\text{ if }x<0.
  \end{cases}
\end{equation*}

\end{comment}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
An ordered Abelian group is \textbf{complete} if it is complete as an
ordered set.  For example, $\Q$ is an ordered Abelian group, but is
\emph{not} complete, by Theorem~\ref{thm:sqrt2}.

\begin{theorem}
$\Z$ \emph{is} a complete ordered Abelian group. 
\end{theorem}

\begin{proof}
Theorem~\ref{thm:wo}.
\end{proof}

However, $\Z$ is \textbf{discrete,} because it has a least positive
element (namely $1$); but $\Q$ is not discrete.

\begin{theorem}
  Every ordered Abelian group that is not discrete is dense.
\end{theorem}

\begin{proof}
  Suppose $G$ is an ordered Abelian group that is not discrete, and
  $a<b$ in $G$.  Then $0<c<b-a$ for some $c$, and then $a<a+c<b$.
\end{proof}

The positive part of an ordered Abelian group satisfies
\begin{gather}\notag %\label{eqn:mag-comm}
x+y=y+x,\\\notag %\label{eqn:mag-ass}
x+(y+z)=(x+y)+z,\\\label{eqn:mag-ord}
x<x+y,\\\notag %\label{eqn:mag-sol}
\Exists z(x<y\lto x+z=y).
\end{gather}
Let us refer to any ordered set with an addition satisfying these rules as a \textbf{magnitudinal structure.}  Indeed, such a structure behaves like a set of \emph{magnitudes} that is closed under addition and subtraction; see p.~\pageref{magnitude} above.
In particular, $\N^+$ is magnitudinal.  Note that $\Z$ can be obtained from $\N^+$ just as from $\N$: we could use
\begin{equation*}
\Z=(\N^+)^2/\mathord{\approx}
\end{equation*}
in place of~\eqref{eqn:Z}.  We need not concern ourselves further with magnitudinal structures as such, because of the following.

\begin{theorem}
Every magnitudinal structure $B$ is the positive part of an ordered Abelian group, namely $B^2/\mathord{\approx}$, where $\approx$ is defined by~\eqref{eqn:approx}.
\end{theorem}

Suppose $A$ is an ordered Abelian group.  Then on $\completion A$ we can define an addition by
\begin{equation*}
X+Y=\sup\{(x+y)\colon x\in X\land y\in Y\}.
\end{equation*}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{comment}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{lemma}
If $A$ is an ordered Abelian group, then, in $\completion A$,
\begin{equation*}
X+Y=\bigcap\{(z)\colon x\in X\land y\in Y\lto x+y\leq z\}.
\end{equation*}
\end{lemma}

\begin{proof}
Theorem~\ref{thm:completions}.
\end{proof}

\end{comment}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Recall that a \textbf{monoid} is a group, except that it might not have inverses.

\begin{theorem}\label{thm:monoid}
If $A$ is an ordered Abelian group, then $\completion A$ is an Abelian \emph{monoid} in which $A$ embeds under $x\mapsto(x)$; moreover, the weak form of~\eqref{eqn:<+}, namely
\begin{equation}\label{eqn:<+weak}
x\leq y\implies x+z\leq y+z,
\end{equation}
holds in $\completion A$.
\end{theorem}

\begin{proof}
Immediately from the definition, addition on $\completion A$ is commutative; almost as easily, $X+(0)=X$.  
We also have
\begin{align*}
(X+Y)+Z&=\sup(\{(u+z)\colon u\in X+Y\land z\in Z\})\\
&\geq\sup(\{(x+y+z)\colon x\in X\land y\in Y\land z\in Z\}).
\end{align*}
Moreover, if $u\in X+Y$, then
\begin{equation*}
(u)\included\sup(\{(x+y)\colon x\in X\land y\in Y\}),
\end{equation*}
and hence
\begin{equation*}
(u+z)\included\sup(\{(x+y+z)\colon x\in X\land y\in Y\});
\end{equation*}
this shows
\begin{equation*}
(X+Y)+Z\leq
\sup(\{(x+y+z)\colon x\in X\land y\in Y\land z\in Z\}).
\end{equation*}
So the two members are equal.  Similarly, the right member is equal to $X+(Y+Z)$.  So addition is associative.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{comment}%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
We have by the lemma
\begin{align*}
X+(Y+Z)&=\bigcap\{(w)\colon x\in X\land v\in Y+Z\lto x+v\leq w\}\\
&=\bigcap\{(w)\colon x\in X\land v\in Y+Z\lto v\leq w-x\}
\end{align*}
and similarly for $(X+Y)+Z$; so to prove associativity, it will be enough to establish
\begin{equation*}
(y\in Y\land z\in Z\lto y+z\leq w-x)\implies(v\in Y+Z\lto v\leq w-x).
\end{equation*}
But this  follows from the definition of addition.  
\end{comment}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Finally, from the definitions, we have $(x)+(y)=(x+y)$, so $x\mapsto(x)$ is an embedding of monoids, and~\eqref{eqn:<+weak}.
\end{proof}

The completion of an ordered Abelian group might not be a group.
For example, let the
free Abelian group $\Z\oplus\Z$ be given the \emph{left lexicographic ordering,} so that
\begin{equation*}
  (a,b)<(c,d)\iff (a<c\lor(a=c\land b<d)).
\end{equation*}
Then
\begin{equation*}
  \dotsb<(-1,0)<(-1,1)<\dotsb
  <(0,-1)<(0,0)<(0,1)<\dotsb<(1,-1)<(1,0)<\dotsb 
\end{equation*}
The only \emph{non-principal} cuts of this group (that is, cuts not of the form $(x)$) are the cuts $c_n$, where
\begin{equation*}
c_n=\{(k,m)\colon k\leq n\}.
\end{equation*}
Identifying $\Z\oplus\Z$ with its image in the completion,
we have
\begin{equation*}
  \dotsb<(-1,0)<\dotsb<c_{-1}<\dotsb
  <(0,0)<\dotsb<c_0<\dotsb<(1,0)<\dotsb.
\end{equation*}
Also,
\begin{equation*}
c_m+c_n=\{(k+\ell,r)\colon k\leq m\land\ell\leq n\}=c_{m+n}.
\end{equation*}
In particular, $c_m+c_0=c_m$, although $c_0\neq(0)$.  Thus $\completion{\Z\oplus\Z}$ is not a group.

The problem here lies in the possibility that two positive elements of an ordered Abelian group might not \emph{have a ratio} (p.~\pageref{magnitude}).  The problem is eliminated in an \emph{Archimedean} group.
Precisely, an ordered Abelian group is \textbf{Archimedean} if for all positive
elements $a$ and $b$ there is an integer $n$ such that $b<na$.  Then $\Z$ and $\Q$ are Archimedean, but not $\Z\oplus\Z$.  

\begin{theorem}\label{thm:com-Arch}
  Every complete ordered Abelian group is Archimedean.
\end{theorem}

\begin{proof}
  In a non-Archimedean ordered Abelian group, there are two positive elements
  $a$ and $b$ such that $b$ is an upper bound of
  $\{na\colon n\in\Z\}$.  Then $b-a$ is also an upper bound of this
  set.  Therefore this set has no supremum.  Hence the ordered group
  is not complete.
\end{proof}

In the proof, the set $\{na\colon n\in\Z\}$ does have a supremum $c$ in the completion; but then $a+c=\sup(\{a+na\colon n\in\Z\})=a$.  Thus~\eqref{eqn:mag-ord} fails in the completion.

\begin{theorem}\label{thm:Zgp}
Every discrete Archimedean ordered Abelian group is uniquely isomorphic
to~$\Z$.
\end{theorem}

\begin{proof}
  Suppose $A$ is a discrete
  Archimedean ordered Abelian group, and let $a$ be its least positive
  element.  If $b\in A$, then $\abs b\leq na$ for some minimal $n$ in
  $\N^+$, and then
  \begin{align*}
    (n-1)a&<\abs b\leq na,&
0&<\abs b-(n-1)a\leq a,
  \end{align*}
so $\abs b=na$ by minimality of $a$.  Thus $a$ generates $A$.
Then there is an isomorphism from $A$ to $\Z$ taking $a$ to
  $1$, and this is the only isomorphism.
\end{proof}

\begin{theorem}
The completion of an Archimedean ordered Abelian group is an ordered Abelian group.
\end{theorem}

\begin{proof}
It suffices to consider a \emph{dense} Archimedean ordered Abelian group $A$.  
%Let $A$ be the group.
If $X\in\completion A$, define
\begin{equation*}
-X=\sup(\{(-x)\colon X\included(x)\}),
\end{equation*}
and for $X+-Y$, write $X-Y$ as usual.
Then
\begin{equation*}
X<Y\iff-Y<-X,
\end{equation*}
and
\begin{equation*}
-(x)=(-x),
\end{equation*}
so
\begin{align*}
X-X&=\sup(\{(x+y)\colon(x)\leq X\land (y)\leq-X\})\\
&=\sup(\{(x+y)\colon(x)\leq X\leq(-y)\})\\
&\leq\sup(\{(x+y)\colon x+y\leq0\})\\
&=(0).
\end{align*}
We have not used the Archimedean property so far; but we must use it for the reverse inequality, because of Theorem~\ref{thm:com-Arch}.  Indeed, if $\completion A$ is indeed a group, then it is an ordered group by Theorem~\ref{thm:monoid}.

So, to prove $X-X\geq(0)$,
suppose $z<0$ in $A$.  
Then $z<w<0$ for some $w$ in $A$, by density.  
Since $\completion A$ is also Archimedean, for some $n$ in $\Z$,
\begin{equation*}
n(w)\leq X<(n-1)(w),
\end{equation*}
so in particular $(w)-n(w)<-X$;
but then
\begin{equation*}
(z)<(w)\leq X-X.
\end{equation*}
Therefore $X-X\geq\sup(\{(z)\colon z<0\})=(0)$.
\end{proof}

We now know that $\R$ is a complete dense ordered Abelian group.

\begin{theorem}\label{thm:AA1}
For every complete dense ordered Abelian group with positive element $a$, there is a unique isomorphism $\phi$ from $\R$ to the group that takes $1$ to $a$.
\end{theorem}

\begin{proof}
Let $A$ be the group, and let $\phi$ be the embedding of $\Z$ in $A$ that takes $1$ to $a$.  We extend $\phi$ to an isomorphism on $\R$.

Suppose $n\in\N^+$.  The set
$\{x\in A\colon nx\leq a\}$ contains $0$ and has $a$ as an upper
bound; so it has a supremum, which for the moment let us call $b$.  We shall show $nb=a$.

Suppose first $nb'<a$.  By density, there are
  $x_k$ in $A$ such that
  \begin{equation*}
    nb'=x_0<x_1<\dotsb<x_{n-1}<x_n=a.
  \end{equation*}
Let $c$ be the least of the $x_k-x_{k-1}$.  Then 
$nc\leq x_n-x_0=a-nb'$, so $n(b'+c)\leq a$, which implies that $b'$ is not an upper bound of $\{x\in
A\colon nx\leq a\}$.  Similarly, if $a<nb'$, then $b'$ is not the
supremum of $\{x\in A\colon nx\leq a\}$.  So $nb=a$.  

For $b$ now, we may use the suggestive notation $a/n$; and we can extend the definition to negative integers by letting $a/-n=-a/n$.  We can extend $\phi$ to an embedding of $\Q$ (as an ordered group) by defining
\begin{equation*}
\phi\left(\frac mn\right)=\frac{ma}n;
\end{equation*}
but we must check that this is a valid definition.
If $m/n=m'/n'$ in $\Q$, so
that $mn'=m'n$, then indeed
\begin{equation*}
  \frac{ma}n=\frac{m'a}{n'},
\end{equation*}
since if $ma=nx$, while $m'a=n'y$, then $m'nx=mn'y$, so $x=y$. 

Finally, suppose $c\in A$, and let $d=\sup(\{\phi(x)\colon\phi(x)\leq c\})$.  Then $d\leq c$.  If $d'<c$, then $a<n(c-d')$ for some $n$ in $\N^+$, so that $a/n<c-d'$, and therefore
\begin{equation*}
d'<\frac{ma}n\leq c
\end{equation*}
for some $m$ in $\Z$, so that $d'\neq d$.  Therefore
\begin{equation*}
c=\sup(\{\phi(x)\colon\phi(x)\leq c\}).
\end{equation*}
This shows that $A$ is the completion of $\phi[\Q]$.  Therefore $\phi$ extends to an isomorphism from $\R$ to $A$ by Theorem~\ref{thm:completions}.
\end{proof}

\subsection{The complete ordered field of real numbers}

%Recall that $\R=\completion{\Q}$.  
Let
\begin{equation*}
  \R^+=\{X\in \R\colon X\geq(0)\}.
\end{equation*}
Then there is an obvious isomorphism from $\R^+$ to $\completion{\Q^+}$,
namely $X\mapsto X\cap\Q^+$.

\begin{theorem}
  $\R$ is a complete ordered field, and every complete ordered field
  is isomorphic to it.
\end{theorem}

\begin{proof}
Since $\Q^+$ is a dense ordered Abelian group under multiplication, so is $\R^+$.
On this group, we have
\begin{align*}
X(Y+Z)&=\sup(\{(xu)\colon x\in X\land u\in Y+Z\})\\
&\geq\sup(\{(x(y+z))\colon x\in X\land y\in Y\land z\in Z\}).
\end{align*}
Conversely, if $u\in Y+Z$, then
\begin{equation*}
(u)\included\sup(\{(y+z)\colon y\in Y\land z\in Z\})
\end{equation*}
and hence
\begin{equation*}
(xu)\included\sup(\{(x(y+z))\colon y\in Y\land z\in Z\});
\end{equation*}
this shows
\begin{equation*}
X(Y+Z)\leq\sup(\{(x(y+z))\colon x\in X\land y\in Y\land z\in Z\}).
\end{equation*}
So the two members are equal.  We have also
\begin{align*}
XY+XZ&=\sup(\{(u+v)\colon u\in XY\land v\in XZ\})\\
&\geq\sup(\{(xy+x'z)\colon x\in X\land x'\in X\land y\in Y\land z\in Z\});
\end{align*}
this becomes equality when we note that, if $u\in XY$ and $v\in XZ$, then 
\begin{align*}
(u)&\included\sup(\{(xy)\colon x\in X\land y\in Y\}),
\intertext{hence}
(u+v)&\included\sup(\{(xy+v)\colon x\in X\land y\in Y\})\\
&\included\sup(\{\sup(\{(xy+x'z)\colon x'\in X\land Z\in Z\})\colon x\in X\land y\in Y\}),
\end{align*}
which is just $\sup(\{(xy+x'z)\colon x\in X\land x'\in X\land y\in Y\land z\in Z\})$ (why?).  But thie last supremum is just
$\sup(\{(xy+xz))\colon x\in X\land y\in Y\land z\in Z\})$ (which is $X(Y+Z)$), since $xy+x'z\leq\max(x,x')z$.

So multiplication distributes over addition on $\R^+$.  This extends to all of $\R$ when we define multiplication by $0$ and negative numbers in the way taught in school.  Thus $\R$ becomes an ordered field.
Its uniqueness as such follows from Theorem~\ref{thm:AA1}.
\end{proof}


Henceforth we may say $\R$ is \emph{the} complete ordered field.

\subsection{Cauchy sequences}

Another way to construct $\R$ is by means of \emph{Cauchy sequences.}  
First of all, a sequence $(a_n\colon n\in\N)$ \textbf{converges} to
the real number 
$b$ if, for all positive real numbers $\epsilon$, there is a natural
number $R$ such that, for all $n$ in $\N$, if $n\geq R$, then
\begin{equation*}
  \abs{a_n-b}<\epsilon.
\end{equation*}
In this case, we write
\begin{equation*}
  \lim_{n\to\infty}a_n=b,
\end{equation*}
or perhaps $\lim(a_n\colon n\in\N)=b$.

\begin{lemma}
  A bounded monotone sequence in $\R$ converges.
\end{lemma}

\begin{proof}
  Let $(a_n\colon n\in\N)$ be bounded an increasing, and let
  $b=\sup(\{a_n\colon n\in\N\})$.  Suppose $\epsilon>0$.  Then
  $b-\epsilon$ is not an upper bound of $\{a_n\colon n\in\N\}$, so for
  some $R$ in $\N$, we have
  \begin{equation*}
    b-\epsilon<a_R\leq b.
  \end{equation*}
Since the sequence is increasing, if $n\geq R$, we have
  \begin{equation*}
    b-\epsilon<a_R\leq a_n\leq b,
  \end{equation*}
and therefore
\begin{equation*}
  \abs{a_n-b}=b-a_n<\epsilon.
\end{equation*}
Thus $(a_n\colon n\in\N)$ converges to $b$.  Similarly, bounded
decreasing sequences converge.
\end{proof}

  A sequence $(a_n\colon n\in\N)$ of
real numbers is a \textbf{Cauchy sequence} if, for every positive real
number $\epsilon$, there is a natural number $R$ such that, for all
$m$ and $n$ in $\N$, if $m\geq R$ and $n\geq R$, then
\begin{equation*}
  \abs{a_m-a_n}<\epsilon.
\end{equation*}


For example, let sequences $(p_n\colon n\in\N)$ and $(q_n\colon
n\in\N)$ be defined recursively by
\begin{align*}
  p_0&=1,&q_0&=1,\\
p_{n+1}&=p_n+2q_n,&q_{n+1}&=p_n+q_n.
\end{align*}
Let $a_n=p_n/q_n$.  Then
\begin{equation*}
  (a_n\colon
  n\in\N)=
\Bigl(1,\frac32,\frac75,\frac{17}{12},\frac{41}{29},\dots\Bigr). 
\end{equation*}
You can show that
\begin{equation*}
  p_nq_{n+1}-q_np_{n+1}=(-1)^{n+1},
\end{equation*}
and hence
\begin{equation*}
    a_{n+1}-a_n=\frac{(-1)^n}{q_{n+1}q_n}.
\end{equation*}
Since $(q_n\colon n\in\N)$ is increasing, it follows that
\begin{equation*}
  a_0<a_2<a_4<\cdots<a_5<a_3<a_1,
\end{equation*}
and moreover $(a_n\colon n\in \N)$ is a Cauchy sequence.  Finally,
\begin{equation*}
  p_n{}^2-2q_n{}^2=(-1)^{n+1},
\end{equation*}
so $(a_n\colon n\in\N)$ converges to $\surd 2$, which however is not
in $\Q$, by Theorem~\ref{thm:2}.

\begin{lemma}
  Every Cauchy sequence in $\R$ is bounded.
\end{lemma}

\begin{proof}
  Let $(a_n\colon n\in\N)$ be a Cauchy sequence.  Let $R$ be such
  that, if $m\geq R$ and $n\geq R$, then $\abs{a_m-a_n}\leq 1$.  In
  particular, if $m\geq R$, then
  \begin{equation*}
    \abs{a_m}\leq\abs{a_m-a_R}+\abs{a_R}\leq 1+\abs{a_R}.
  \end{equation*}
Thus each $\abs{a_n}$ is bounded by
$\max(\abs{a_0},\dots,\abs{a_{R-1}},1+\abs{a_R})$. 
\end{proof}

\begin{theorem}\label{thm:Cc}
  Every Cauchy sequence in $\R$ converges.
\end{theorem}

\begin{proof}
  Let $(a_n\colon n\in\N)$ be a Cauchy sequence.  Then the sequence is
  bounded, by the last lemma.  In particular, we can define
  \begin{equation*}
    b_k=\sup(\{a_n\colon n\geq k\}).
  \end{equation*}
Then $(b_k\colon k\in\N)$ is bounded (why?) and decreasing, so it
converges to some $c$ by the next to last lemma.  We have
\begin{equation*}
  \abs{a_m-c}\leq\abs{a_m-a_n}+\abs{a_n-b_k}+\abs{b_k-c}.
\end{equation*}
Let $\epsilon>0$.  
There is some $R$ such
that, if $k\geq R$, $m\geq R$, and $n\geq R$, then
$\abs{a_m-a_n}<\epsilon/3$
and $\abs{b_k-c}<\epsilon/3$.  For all $k$, there is $n$ such that
$n\geq k$ and
$\abs{a_n-b_k}<\epsilon/3$.  Therefore, if $m\geq R$, then
$\abs{a_m-c}<\epsilon$.  Thus $(a_n\colon n\in\N)$ converges.
\end{proof}

For the alternative construction of $\R$, let us denote by
\begin{equation*}
  \mapset{\N}{\Q}
\end{equation*}
the set of functions from $\N$ to $\Q$, that is, rational sequences.
This becomes a commutative ring when, writing $a$ for $(a_n\colon
n\in\N)$, we define
\begin{align*}
  (a+b)_n&=a_n+b_n,&
(-a)_n&=-a_n,&
(ab)_n&=a_nb_n.
\end{align*}
Then $\Q$ embeds in this ring under the map that takes $x$ to the
sequence that is identically $x$.  We may identify $\Q$ with its image
in $\mapset{\N}{\Q}$.  Let $S$ be the set of Cauchy sequences in
$\mapset{\N}{\Q}$.  Then $\Q\included S$.

\begin{lemma}
  $S$ is a sub-ring of $\mapset{\N}{\Q}$; that is, $S$ contains $0$
  and $1$ and is closed under $+$, $-$, and $\cdot$.
\end{lemma}

\begin{proof}
  The most difficult part is closure under multiplication.  Let $a$
  and $b$ be in $S$.  By the previous lemma, there is $R$ such that,
  for all $n$ in $\N$, we 
  have $\abs{a_n}\leq R$ and $\abs{b_n}\leq R$.  Hence
  \begin{multline*}
    \abs{a_mb_m-a_nb_n}=\abs{a_mb_m-a_nb_m+a_nb_m-a_nb_n}
\leq\abs{a_m-a_n}\abs{b_m}+\abs{a_n}\abs{b_m-b_n}\\
{}\leq R(\abs{a_m-a_n}+\abs{b_m-b_n}).
  \end{multline*}
Then $ab$ is Cauchy.
\end{proof}

By Theorem~\ref{thm:Cc}, we have a map $x\mapsto\lim x$, in fact a
homomorphism, from $S$ to $\R$.  Let $I$ be the kernel, namely the set
of sequences in $\mapset{\N}{\Q}$ that converge to $0$.  Then $I$ is
an \emph{ideal} of $S$.

\begin{theorem}
  $S/I\cong\R$ under $x\mapsto\lim x$; in particular, $I$ is a maximal
  ideal of $S$.
\end{theorem}

\begin{proof}
We just have to show $x\mapsto\lim x$ is surjective. 
  Let $a\in\R$.  Then $a=\sup\{x\in\Q\colon x<a\}$.   By the
  \emph{Axiom of
    Choice,} there is a sequence $b$ in $\mapset{\N}{\Q}$ such that
  \begin{align*}
    b_0&<a,& b_n+\frac{a-b_n}2&<b_{n+1}<a.
  \end{align*}
Then $\lim b=a$.  Thus $S$ maps onto $\R$ under $x\mapsto\lim x$.
\end{proof}

Independently of the theorem---that is, without having previously defined $\R$---, one can show that $I$ is a maximal ideal of $S$.  Then $S/I$ is a field, and one can show that it is a complete ordered field.  Thus there is an alternative construction of $\R$.  The construction is carried out more generally in Theorem~\ref{thm:val-comp} in the next section.


\newpage

\section{Non-Archimedean fields and valuations}\label{sect:non-Arch}

In moving from $\N$ to $\Z$ to $\Q$ to $\R$, we achieve the
following.  The formal sentence
\begin{equation*}
  \Forall x\Forall y\Exists zx+z=y
\end{equation*}
is false in $\N$, but true in $\Z$.  The sentence
\begin{equation*}
  \Forall x\Forall y\Exists z(x\cdot z=y\lor x=0)
\end{equation*}
is false in $\Z$, but true in $\Q$.  The sentence
\begin{equation*}
  \Forall x\Exists y(y^2=x\lor x<0)
\end{equation*}
is false in $\Q$, but true in $\R$ (why?).  Thus, moving to $\R$
allows us to solve more equations.  Is there any advantage to moving
\emph{beyond} $\R$?

\subsection{Non-Archimedean fields}

In any case, we \emph{can} move beyond $\R$.  Let
\begin{equation*}
  \R[x]
\end{equation*}
denote the set of \textbf{polynomials} in $x$ over $\R$: these have
the form
\begin{equation}\label{eqn:poly}
  a_0+a_1x+a_2x^2+\dotsb+a_nx^n
\end{equation}
or
\begin{equation*}
  \sum_{k=0}^na_kx^k,
\end{equation*}
where the coefficients $a_k$ are in $\R$.  Then $\R[x]$ is an integral
domain in
which $\R$ embeds.  Note that, if $m\leq n$, then
\begin{equation*}
  \sum_{k=0}^ma_kx^k=\sum_{k=0}^nb_kx^k\iff a_0=b_0\land\dots\land
  a_m=b_m \land b_{m+1}=0\land\dots\land b_n=0.
\end{equation*}
Thus, a polynomial is not simply an expression of the form
in~\eqref{eqn:poly}; it is an equivalence-class of such expressions.
However, every polynomial in $x$ can be written uniquely as an
\textbf{infinite series}
\begin{equation*}
  \sum_{k=0}^{\infty}a_kx^k;
\end{equation*}
but here all but finitely many of the coefficients $a_k$ are $0$.

Just as we construct $\Q$ from $\Z$, so from $\R[x]$ we construct
$\R(x)$, the set of \textbf{rational functions} in $x$ over $\R$,
consisting of the fractions
\begin{equation}\label{eqn:rat}
  \frac{a_0+\dots+a_nx^n}{b_0+\dotsb+b_mx^m}.
\end{equation}
Then $\R(x)$ is a field.

\begin{theorem}
  $\R(x)$ becomes a non-Archimedean ordered field when, for every element
  %$\sum_{k=0}^na_kx^k/\sum_{\ell=0}^mb_{\ell}x^{\ell}$ 
as in~\eqref{eqn:rat} such that
  $a_nb_m\neq0$, that element is considered positive if and only if
  $a_nb_m>0$. 
\end{theorem}

\begin{proof}
  Easily $\R(x)$ is an ordered field; it is non-Archimedean, since
  $-a+x>0$, that is, $x>a$, for all $a$ in $\Z$.
\end{proof}

Suppose now $K$ is an arbitrary ordered field that
includes $\R$.  Each element of $K$ that is smaller (in absolute
value) than \emph{some} rational is called \textbf{finite;} each
element that is smaller than \emph{every} nonzero rational is called
\textbf{infinitesimal.}  Elements of $K$ that are not finite are
\textbf{infinite.} 

For example, in $\R(x)$, for
all $a$ in $\Q$, we have
\begin{equation}\label{eqn:a<x}
  a<x<x^2<x^3<\cdots,
\end{equation}
so the positive powers of $x$ are infinite.
Hence also, if $a$ is a \emph{positive} rational, we have
\begin{equation}\label{eqn:a>1/x}
  a>\frac1x>\frac1{x^2}>\frac1{x^3}>\cdots>0,
\end{equation}
so the negative powers of $x$ are infinitesimal.

With $K$ as before, let $R$ be the set of finite elements of $K$, and
let $I$ be the set of infinitesimal elements.
Then $R$ is a sub-ring of $K$, and $I$ is an ideal of $R$.  

The \textbf{units} or multiplicatively invertible elements
of a ring $R$ compose a multiplicative group denoted by
\begin{equation}
  \units R.
\end{equation}
In our situation, an element $a$ of $\units K$ is infinite if and only
if $a\inv\in I$.  In particular, either $a$ or $a\inv$ is
finite---belongs to $R$.  For this reason, $R$ is called a
\textbf{valuation ring;}  the reason for the terminology will be seen below.
It also follows that every element of $R\setminus I$ is a
unit of $R$.  Consequently, $I$ is a maximal ideal of $R$ and is
moreover the \emph{unique} maximal ideal of $R$.  For this reason, $R$
is called a \textbf{local ring.}  (So every valuation ring is a local
ring.)  Since $I$ is maximal, we know $R/I$ is a field. 

\begin{theorem}\label{thm:RR/I}
  Let $K$ be an ordered field that includes $\R$, and let $R$ be the
  ring of finite elements of $K$, with maximal ideal $I$ of
  infinitesimals. Then the quotient map $x\mapsto x+I$ determines an
  isomorphism from $\R$ onto $R/I$.
\end{theorem}

\begin{proof}
  Let $h$ be $x\mapsto x+I$ on $\R$.  Then $\ker(h)=I\cap\R$, which is
  $\{0\}$.  Thus $h$ is injective.  It remains to show $h$ is
  surjective onto $R/I$.

Let $a\in R$.  Since $a$ is finite, the set $\{x\in\R\colon x<a\}$ has
an upper bound in $\R$, hence a supremum, $a'$.  We shall show
$h(a')=a+I$.  To this end, suppose $b\in\R$, but $h(b)\neq a+I$.  This
means $b-a$ is not infinitesimal.  In particular, for some real number
$\delta$, we have
\begin{equation*}
  0<\delta<\abs{b-a}.
\end{equation*}
If $b<a$, then $b<b+\delta<a$, so $b$ is not an upper bound of
$\{x\in\R\colon x<a\}$.  If $a<b$, then $a<b-\delta$, so $b$ is not
the supremum of $\{x\in\R\colon x<a\}$.  In either case, $b\neq a'$.
\end{proof}

If $a$ and $b$ are arbitrary elements of $K$ such that $a-b\in I$,
then $a$ and $b$ are \textbf{infinitely close,} and we write
\begin{equation*}
  a\simeq b.
\end{equation*}
By the theorem, if $a$ is finite, then $a$ is infinitesimally close to
some \emph{unique} real number; this number is called the
\textbf{standard part} of $a$.  In particular, the infinisimals are
the elements whose standard part is $0$.

Let us see how this all works in $\R(x)$.  The finite elements here
are those of the form
\begin{equation*}
  \frac{a_nx^n+\dotsb+a_0}{b_nx^n+\dotsb+ b_0},
\end{equation*}
where $b_n\neq0$.  The standard part of this element is $a_n/b_n$,
since
\begin{equation*}
  \frac{a_nx^n+\dotsb+a_0}{b_nx^n+\dotsb+ b_0}-\frac{a_n}{b_n}
=\frac{(a_{n-1}-a_nb_{n-1}/b_{n-1})x^{n-1}+\dotsb}{b_nx^n+\dotsb+b_0}.
\end{equation*}
Using the division algorithm taught in school, we can formally compute
the quotient of two nonzero elements of $\R[x]$, getting a possibly
infinite series 
\begin{equation*}
  c_0+c_1x\inv+c_2x^{-2}+\dotsb
\end{equation*}
or simply
\begin{equation*}
  \sum_{n=0}^{\infty}c_kx^{-k};
\end{equation*}
this is a \textbf{formal power series} in $x\inv$ with coefficients from
$\R$. 
For example, formally,
\begin{equation*}
  \frac{x}{x-1}=1+x\inv+x^{-2}+\dotsb.
\end{equation*}
The set of all formal power series in $x\inv$ over $\R$ is denoted by
$\R[[x\inv]]$ or 
rather
\begin{equation*}
  \R[[t]],
\end{equation*}
where $t=x\inv$.  This set is an integral domain in the obvious way,
and its \emph{quotient field} is denoted by
\begin{equation*}
  \R((t));
\end{equation*}
this is the field of \textbf{formal Laurent series} in $t$ with
coefficients from $\R$, namely series
\begin{equation}\label{eqn:L}
  \sum_{n=k}^{\infty}a_nt^n,
\end{equation}
where $k\in\Z$, and each $a_n$ is in $\R$.  This field includes
$\R(t)$, which is $\R(x)$.

The ordering of $\R(t)$ extends to $\R((t))$.  Indeed, let $a$ be the
element in~\eqref{eqn:L}, and assume $a_k\neq0$.  Then $a$ is 
\begin{enumerate}
\item 
positive
if and only if $a_k>0$,
\item
finite if and only if $k\geq0$,
\item
infinitesimal if and only if $k>0$.
\end{enumerate}
If $a$ is finite, then its standard part is $a_0$ (which is $0$ if $k>0$).

\subsection{Valuations}

The construction of $\R((t))$ as a field uses only that $\R$ is a
field.  Let $K$ be an arbitrary field, not necessarily ordered; then
we can form the field
\begin{equation*}
  K((t))
\end{equation*}
of formal Laurent series in $t$ with coefficients from $K$.  This has
the sub-ring
\begin{equation*}
  K[[t]]
\end{equation*}
of formal power series in $t$ with coefficients from $K$.  This ring
is a valuation ring, with unique maximal ideal $(t)$; here $(t)$
consists of the series $\sum_{n=1}^{\infty}a_nt^n$ with no constant term.

\begin{theorem}\label{thm:K[[t]]}
  $K\cong K[[t]]/(t)$ under $\xi\mapsto\xi+(t)$.
\end{theorem}

There is another quotient we can form, namely
\begin{equation*}
  \units{K((t))}/\units{K[[t]]}.
\end{equation*}
Here
\begin{align*}
  \units{K((t))}&=K((t))\setminus\{0\},&
\units{K[[t]]}&=K[[t]]\setminus (t).
\end{align*}
The quotient map $\xi\mapsto\xi\units{K[[t]]}$ is the
\textbf{$t$-adic valuation.}  This can be understood by noting that,
if $a_k\neq0$, then
\begin{equation*}
  \frac1{t^k}\sum_{n=k}^{\infty}a_nt^n=\sum_{n=0}^{\infty}a_{k+n}t^n,
\end{equation*}
which is in $\units{K[[t]]}$.  We might write
\begin{equation*}
  \sum_{n=k}^{\infty}a_nt^n\equiv t^k\pmod{\units{K[[t]]}}.
\end{equation*}
Thus the $t$-adic valuation maps $\gpgen t$ (that is,
$\{t^n\colon n\in\Z\}$) bijectively onto $\units{K((t))}/\units{K[[t]]}$.
When we assume 
\begin{equation*}
  0<\dotsb<t^2<t<1<t\inv<\dotsb,
\end{equation*}
then an ordering is induced on $\{0\}\cup\units{K((t))}/\units{K[[t]]}$, and the $t$-adic valuation becomes a map $x\mapsto\abs x$ such that
\begin{enumerate}
\item 
$\abs{xy}=\abs x\abs y$,
\item
$\abs x=0$ if and only if $x=0$,
\item
the \textbf{strong triangle inequality} $\abs{x+y}\leq\max(\abs x,\abs y)$ holds.
\end{enumerate}
In general, if $K$ is an arbitrary field, and 
$\Gamma$ is an ordered field written multiplicatively, and the ordering is extended to $\{0\}\cup\Gamma$ so that $0<v$ for all $v$ in $\Gamma$, and there is a function $x\mapsto\abs x$ from $K$ to $\{0\}\cup\Gamma\cup$ so that the three properties just listed hold, then $K$, then the function $x\mapsto\abs x$ may be called a \textbf{strong valuation}\footnote{This is not standard terminology.  Usually what I am calling a strong valuation is just called a valuation, and what I shall call a valuation is called an `absolute value,' at least if its range is included in $\R$.  I object to this usage on linguistic grounds:  An absolute value should be the \emph{value} of a function at a particular argument, not the whole function itself.  (Similarly a \emph{product} is the value or result of a \emph{multiplication;} the two terms are not properly interchangeable.  In linear algebra then, if one is being linguistically strict, an `inner product' should be called an `inner multiplication,' if the operation itself is meant.)} 
on $K$, and $K$ itself, considered with the valuation, may be called a \textbf{strongly valued field.}  
If, moreover, $\Gamma$ is the positive part of an ordered field, but the triangle inequality holds only in its weaker form
\begin{equation*}
\abs{x+y}\leq\abs x+\abs y,
\end{equation*}
then $K$ is simply a \textbf{valued field} with respect to the \textbf{valuation} $x\mapsto\abs x$.

So every ordered field, such as $\R$, is a valued field with respect to the absolute value function; but also $\C$ is a valued field with respect to this function.  The field $K((t))$ is strongly valued with respect to the $t$-adic valuation.

%In particular, with the $t$-adic valuation, $K((t))$ is a strongly valued field.

%Strongly valued fields arise quite generally.  

Let $\vo$ be an arbitrary
valuation ring with 
unique maximal ideal $\mi$ and
and quotient field $K$.
We order the multiplicative group $\units K/\units{\vo}$ by the rule
\begin{equation*}
  a\units{\vo}\leq b\units{\vo}\iff a/b\in\vo,
\end{equation*}
and we say $0$ is less than all elements of the group.
Let the quotient map from $\units K$ to $\units{\vo}$, together with
$\{(0,0)\}$ (the function taking $0$ to $0$) be denoted by
\begin{equation*}
  \xi\mapsto\abs{\xi}_{\mi}.
\end{equation*}
this is the \textbf{$\mi$-adic valuation} on $K$, and the terminology is justified by the following.

\begin{theorem}
Let $\vo$ be a valuation ring with maximal ideal $\mi$.  With the $\mi$-adic valuation, the
quotient field of~$\vo$ is a strongly valued field.
\end{theorem}

\begin{proof}
  For the strong triangle inequality, if
  $b\neq0$, we have 
  \begin{equation*}
    \abs{a+ b}_{\mi}\leq\abs b_{\mi}
\iff\frac{a+ b}b\in\vo\iff \frac ab+ 1\in\vo\iff\frac ab\in\vo
\iff\abs a_{\mi}\leq\abs b_{\mi}.\qedhere
  \end{equation*}
\end{proof}

A valuation ring can be recovered from a strong valuation, which in turn can be recovered from the valuation ring:

\begin{theorem}
In a strongly valued field $K$, let
\begin{align*}
  \vo&=\{x\in K\colon\abs x\leq 1\},&
%\units{\vo}&=\{x\in K\colon\abs x=1\},&
\mi&=\{x\in K\colon\abs x<1\}.
\end{align*}
Then $K$ is the quotient field of $\vo$, and $\vo=\{x\in K\colon\abs x_{\mi}\leq 1\}$.
\end{theorem}

In the notation of the theorem, the ordered group $\units K/\units{\vo}$ is the \textbf{value group,}
and the field $\vo/\mi$ is
the \textbf{residue field.}  So $K((t))$, with the $t$-adic valuation,
has the residue field $K$, by Theorem~\ref{thm:K[[t]]}.  For an
arbitrary ordered field extending $\R$, with valuation determined by
the infinitesimals, the residue field is (isomorphic to) $\R$, by 
Theorem~\ref{thm:RR/I}. 


In an arbitrary strongly valued field $K$,
the elements of
the subgroup $\{n\cdot 1\colon n\in\Z\}$ of $K$
% generated by $1$
take values no greater than 
$1$.  But the elements of $K\setminus\vo$ take values greater than
$1$. 
For this reason, if $\mi\neq(0)$, the $\mi$-adic valuation is
\textbf{non-Archimedean.} 
By contrast, the absolute value function on a subfield of $\R$ or $\C$
is Archimedean.  But what about the absolute value function on a non-Archimedean ordered field?  This has non-Archimedean value group, and usually the definition of valuation requires the value group to be Archimedean (or equivalently, to be a subgroup of $\R^+$).  I am not making this requirement here.


In any valued field, there is the notion of \textbf{Cauchy sequence}
and \textbf{convergent sequence:} the definitions are formally the
same as for sequences in $\R$.  A valued field is \textbf{complete}
if every Cauchy sequence of its elements converges.  Then $K((t))$ is
complete with respect both to the $t$-adic valuation.  Also, $\R$ and $\C$ are
complete with respect to the absolute value function.  Finally, $\R((t))$ is complete both with respect to the $t$-adic valuation and with respect to the absolute value function induced by the ordering in which $t$ is infinitesimal.

\begin{lemma}
In a strongly valued field, if $\abs a<\abs b$, then $\abs{a\pm b}=\abs b$.
\end{lemma}

\begin{proof}
%Suppose $\abs a_{\mi}<\abs b_{\mi}$.  
Since
\begin{equation*}
  \abs b=\abs{\pm b}=\abs{a\pm b-
    a}\leq\max(\abs{a\pm b},\abs a), 
\end{equation*}
we have
$\abs b\leq\abs{a\pm b}\leq\abs b$,
so $\abs b=\abs{a\pm b}$. 
\end{proof}

\begin{theorem}\label{thm:val-comp}
  Every valued field $K$ has a
  \textbf{completion,} namely a
  complete valued field $\completion K$ in which $K$ embeds, such that any
  embedding of $K$ in a valued field extends to an embedding of $\completion
  K$ in that valued field.
\end{theorem}

\begin{proof}
%If the valuation is trivial, then the field is already complete; so we may assume that the %valuation is not trivial.
  Let $R$ consist of the Cauchy sequences of
  $K$, and let $I$ consist of those sequences that converge to $0$.
  Then $R$ is a ring with maximal ideal $I$.  Indeed, suppose $(a_n\colon
  n\in \N)\in R\setminus I$.  Then for some non-zero value $\epsilon$, for all positive integers $M$, there is an integer $n$ such that $n>M$ and $\abs{a_n}\geq\epsilon$.  We may assume $\epsilon<1$.  For some positive integer $N$, if $m>N$ and $n>N$, then $\abs{a_m-a_n}<\epsilon^2$.  But we can choose $k$ so that $k>N$ and $\abs{a_k}\geq\epsilon$.  In this case, if $m>N$, then, in case the valuation is weak, we have
  \begin{gather*}
\abs{a_k}-\abs{a_m}\leq\abs{a_m-a_k}<\epsilon^2,\\
\epsilon\leq\abs{a_k}<\abs{a_m}+\epsilon^2,\\
\epsilon-\epsilon^2<\abs{a_m},
\end{gather*}
while if the valuation is strong, then by the lemma, $\epsilon^2<\abs{a_k}=\abs{a_m}=\abs{a_k}$.
  
  In particular, if $m>N$ and $n>N$, then $a_ma_n\neq0$, and we have
  \begin{equation*}
    \abs{\frac 1{a_n}-\frac1{a_m}}=\abs{\frac{a_m-a_n}{a_na_m}}
=\frac{\abs{a_m-a_n}}{\abs{a_na_m}}.
  \end{equation*}
%By the lemma, $\abs{a_na_m}$ is eventually constant and nonzero.
Therefore, if we define
  \begin{equation*}
    b_n=
    \begin{cases}
      a_n{}\inv,&\text{ if }a_n\neq0,\\
      1,&\text{ if }a_n=0,
    \end{cases}
  \end{equation*}
then $(b_n\colon n\in\N)\in R$.  Now let
  \begin{equation*}
    c_n=
    \begin{cases}
      0,&\text{ if }a_n\neq0,\\
      1,&\text{ if }a_n=0.
    \end{cases}
  \end{equation*}
Then $(c_n\colon n\in\N)\in I$, and $a_nb_n+c_n=1$.  Therefore $I$ is
indeed a maximal ideal of $R$.  We can embed $K$ in the field $R/I$
under the quotient map.  We extend the valuation to $R/I$ by letting a
Cauchy sequence have the value that its terms eventually reach.  (Why
is $R/I$ complete, and the completion of $K$?)
\end{proof}

For example, $K((t))$ is the completion of $K(t)$ with respect to the $t$-adic valuation, and $\R((t))$ is the completion of $\R(t)$ with respect to the absolute value function induced by the ordering in which $t$ is infinitesimal.

The field of rationals has a non-Archimedean completion $\Q_p$ for
each prime $p$.  Indeed, the \textbf{$p$-adic valuation} on $\Q$ is
given by
\begin{equation*}
  \abs{p^n\cdot\frac ab}_p=\frac 1{p^n},
\end{equation*}
where $n\in \Z$, and $a$ and $b$ are integers indivisible by $p$.
Then $\Q_p$ consists of the \textbf{$p$-adic numbers,} namely the
formal sums
\begin{equation*}
  \sum_{n=k}^{\infty}a_np^n,
\end{equation*}
where $k\in\Z$, and $a_n\in\{0,1,\dots,p-1\}$.  For example, in
$\Q_p$,
\begin{equation*}
  -1=\sum_{n=0}^{\infty}(p-1)p^k.
\end{equation*}
Even though $\Q_p$ is of characteristic $0$, its residue field is finite, with $p$ elements.

It is possible for an ordered field to be complete with respect to the absolute value function, simply because there are no Cauchy sequences that are not eventually constant.  Indeed, suppose $\kappa$ is an iterative structure that is also well-ordered so that $\alpha<\alpha+1$ for all $\alpha$ in $\kappa$.  Let $X$ be a set $\{x_{\alpha}\colon \alpha\in\kappa\}$ of variables indexed by $\kappa$.  Given a field $K$, we can define a sequence $(K_{\alpha}\colon\alpha\in\kappa)$ of fields by \emph{transfinite recursion:}
\begin{enumerate}
	\item 
	$K_0=K$,
	\item
	$K_{\alpha+1}=K_{\alpha}(x_{\alpha})$,
	\item
	$K_{\beta}=\bigcup\{K_{\alpha}\colon\alpha<\beta\}$, if $\beta$ is not a successor or $0$.
\end{enumerate}
Now let
\begin{equation*}
K(X)=\bigcup\{K_{\alpha}\colon\alpha\in\kappa\}.
\end{equation*}
If $K$ is ordered, then $K(X)$ is ordered so that each $x_{\alpha}$ is greater than each element of $K$, and $x_{\alpha}<x_{\beta}\iff\alpha<\beta$.  Suppose that every countable subset of $\kappa$ is bounded in $\kappa$.  (It is a set-theoretical fact that such $\kappa$ exist.)  Then the only Cauchy sequences in $K(X)$ with respect to the absolute value function are eventually constant.  Indeed, if $(a_n\colon n\in\N)$ is a sequence of elements of $K(X)$, then the set of reciprocals $1/\abs{a_n-a_m}$ of nonzero differences is bounded by some $x_{\alpha}$, and then 
\begin{equation*}
\abs{a_n-a_m}<1/x_{\alpha}\lto a_n=a_m.  
\end{equation*}
Consequently, $K(X)$ is complete with respect to the absolute value function.


In sum:
\begin{enumerate}
\item 
The field $\R$ is the unique complete ordered field.
\item
The field $\R$ is complete with respect to the absolute value function, but so too
  is $\C$.
\item
There are non-Archimedean ordered fields.  The completion of one of these with respect to the ordering is never a field.  But there is a completion with respect to the absolute value function determined by the ordering, and this completion is always a field.
%\item
%there are many fields, even fields that include $\Q$, that are complete with
%respect to a strong valuation. 
\end{enumerate}


\newpage

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

\subsection{Algebra}

%The question remains, How do we obtain $\sR$?

For notational convenience, if $n\in\N$, let us assume
\begin{equation*}
  n=\{x\in\N\colon x<n\}=\{0,\dots,n-1\}.
\end{equation*}
To be precise, we can define $f$ on $\N$ by
\begin{align*}
  f(0)&=\emptyset,&f(n+1)&=f(n)\cup\{f(n)\}.
\end{align*}
By induction, $f(n)=\{f(0),\dots,f(n-1)\}$.  With more work, one shows
$f$ is injective.  The image $f[\N]$ of $\N$ under $f$ is denoted by
\begin{equation*}
  \vnn.
\end{equation*}
So $0$ in $\vnn$ is $\emptyset$, and $n+1$ is $n\cup\{n\}$.
It will be convenient to treat $\vnn$ as $\N$.

Let $\Omega$ be a set, and $n\in\vnn$.  We define
\begin{equation*}
  \Omega^n
\end{equation*}
as the set of functions from $n$ (that is, $\{0,\dots,n-1\}$) to
$\Omega$.  In particular,
\begin{equation*}
  \Omega^0=\{\emptyset\}=\{0\}=1.
\end{equation*}
A subset of $\Omega^n$ is an \textbf{$n$-ary relation} on $\Omega$.
A typical element of $\Omega^n$ might be denoted by
\begin{equation*}
  (x^0,\dots,x^{n-1})
\end{equation*}
or more simply
\begin{equation*}
  \tuple x.
\end{equation*}
On $\Omega$ there are just two $0$-ary relations,
namely $\emptyset$ and $\{\emptyset\}$, that is, $0$ and $1$.

Suppose now $m$ and $n$ are in $\vnn$, and
\begin{equation*}
  f\colon m\to n.
\end{equation*}
(If $n=0$, then $m$ must be $0$.)  Then a function from $\Omega^n$ to
$\Omega^m$ is induced, namely
\begin{equation*}
  x\mapsto x\circ f.
\end{equation*}
Let us denote this function
by
\begin{equation*}
f^*
\end{equation*}
or more precisely $f^*_{\Omega}$.  Then\footnote{In the language of category
  theory, the pair $(m\mapsto\Omega^m,f\mapsto f^*)$ is a
  \emph{contravariant functor} 
  from the category $(\vnn,\{\text{functions}\})$ to the
  category $(\{\text{sets}\},\{\text{functions}\})$.} 
\begin{equation*}
  f^*(x^0,\dots,x^{n-1})=(x^{f(0)},\dots,x^{f(m-1)}).
\end{equation*}
For example, if $f$ is the inclusion of $n$ in $n+1$, then
$f^*(x^0,\dots,x^{n-1},x^n)=(x^0,\dots,x^{n-1})$, or more simply
$f^*(\tuple x,y)=\tuple x$.  

In general, we get
$X\mapsto f^*[X]$ from $\pow{\Omega^n}$ to $\pow{\Omega^m}$, where
\begin{align*}
  f^*[A]&=\{f^*(\tuple x)\colon \tuple x\in A\}\\
&=\{\tuple y\in\Omega^m\colon\Exists{(x^0,\dots,x^{n-1})}
((x^0,\dots,x^{n-1})\in A\land
\tuple y=(x^{f(0)},\dots,x^{f(m-1)}))\}. 
\end{align*}
We also have a function $Y\mapsto f_*(Y)$ from $\pow{\Omega^m}$ to
$\pow{\Omega^n}$ where
\begin{align*}
  f_*(B)&=(f^*)\inv[B]\\
&=\{(x^0,\dots,x^{n-1})\in\Omega^n\colon(x^{f(0)},\dots,x^{f(m-1)})\in
  B\}. 
\end{align*}
If again $f$ is the inclusion of $n$ in $n+1$, then $f_*(B)$ can be
understood as $B\times\Omega$.  If $f$ is a permutation of $n$, then 
\begin{equation*}
  f^*[A]=(f\inv)_*(A).
\end{equation*}

Now the statement of Theorem~\ref{thm:*K} below makes some sense.

So that the \emph{proof} makes sense,
suppose $R$ is a commutative ring.  As in \S~\ref{sect:reals}, we
obtain the commutative ring
\begin{equation*}
  \seq R.
\end{equation*}
If $a$ is an element $(a_n\colon n\in\vnn)$ of this ring, let
\begin{equation*}
  \supp a=\{n\in\vnn\colon a_n\neq0\},
\end{equation*}
the \textbf{support} of $a$.  In one case of interest, $R$ is $\B$,
the two-element field $\{0,1\}$.

If $X$ and $Y$ are subsets of some set, let
\begin{equation*}
  X\symdiff Y=(X\setminus Y)\cup(Y\setminus X),
\end{equation*}
the \textbf{symmetric difference} of $X$ and $Y$.

\begin{theorem}
  The map $x\mapsto\supp x$ is a bijection from $\seq{\B}$ onto
  $\pow{\vnn}$.  Also
  \begin{gather*}
    \supp 0=\emptyset,\\
\supp 1=\vnn,\\
\supp{xy}=\supp x\cap\supp y,\\
\supp{x+y}=\supp x\symdiff\supp y,
  \end{gather*}
Thus  $\pow{\vnn}$ inherits from $\seq{\vnn}$ the structure of a ring.
\end{theorem}

A ring (not necessarily commutative) is called \textbf{Boolean} if in
it
\begin{equation}\label{eqn:x^2=x}
  x^2=x.
\end{equation}
So $\B$, $\seq{\B}$, and $\pow{\vnn}$ are Boolean rings.

\begin{theorem}\label{thm:Br}
Let $R$ be a Boolean ring.  In $R$,
\begin{equation}\label{eqn:2x=0}
  2x=0,
\end{equation}
and hence
\begin{equation*}
  -x=x.
\end{equation*}
Also $R$ is commutative, and $R$ can be partially ordered by the rule
\begin{equation*}
  x\leq y\iff xy=x.
\end{equation*}
Then a nonempty subset $I$ of $R$ is an ideal of $R$ if and only if
\begin{gather}\notag
  x\in I\land y\in I\implies x+y\in I,\\
x\in I\land y\leq x\implies y\in I.\label{eqn:I<}
\end{gather}
All prime ideals of $R$ are maximal, and and ideal $I$ is maximal if
and only if 
\begin{equation*}
  x\in I\iff x+1\notin I.
\end{equation*}
\end{theorem}

\begin{proof}
  For~\eqref{eqn:2x=0}, compute
  \begin{equation*}
    2x=(2x)^2=4x^2=4x.
  \end{equation*}
For commutativity then, compute
\begin{gather*}
  x+y=(x+y)^2=x^2+xy+yx+y^2=x+xy+yx+y,\\
0=xy+yx.
\end{gather*}
Immediately from the definitions, $x\leq x$. If $x\leq y$ and $y\leq
x$, then $x=xy=yx=y$.  If $x\leq y$ and $y\leq z$, then $xz=xyz=xy=x$,
so $x\leq z$.  Thus $\leq$ partially orders $R$.

For the characterization of ideals, note that~\eqref{eqn:I<} is
equivalent to $x\in I\implies xz\in I$. 

From~\eqref{eqn:x^2=x}, we get
\begin{equation*}
  x(x-1)=0,
\end{equation*}
so in every Boolean integral domain, the only elements are $0$ and
$1$.  In short, every Boolean integral domain is a field, so prime
ideals of $R$ are maximal.  Moreover, an ideal $I$ of $R$ is maximal
if and only if $R/I$ is the disjoint union of two cosets, $I$ and
$1+I$; this yields the characterization of maximal ideals.
\end{proof}

\begin{corollary}
  A subset $M$ of $\pow{\vnn}$ is a maximal ideal if and only if
  \begin{enumerate}
\item
$x\in M\land y\in M\implies x\cup y\in M$,
\item
$x\in M\land y\included x\implies y\in M$,
\item
$x\in M\iff\vnn\setminus x\notin M$.
  \end{enumerate}
A \textbf{principal} ideal $(A)$ of $\pow{\vnn}$ is maximal if and
only if $A=\vnn\setminus\{n\}$ for some $n$ in $\vnn$.
A maximal ideal of $\pow{\vnn}$ is non-principal
if and only if it contains all finite subsets of $\vnn$.
\end{corollary}

For example, if $n\in\vnn$, then the principal ideal
$(\vnn\setminus\{n\})$, namely $\{x\in\pow{\vnn}\colon n\notin x\}$, 
is a maximal ideal of $\pow{\vnn}$.

\begin{theorem}
  Let $K$ be a field.  The function $X\mapsto\Supp X$ gives a one-to-one
  correspondence between the ideals of $\Ko$ and the ideals of
  $\pow{\vnn}$. 
\end{theorem}

\begin{proof}
Suppose $I$ is an ideal of $\Ko$, and
$a\in I$.
\begin{enumerate}
\item
If $\supp b\included\supp a$, then $b\in I$, since $b=ca$,
where 
\begin{equation*}
  c_n=
  \begin{cases}
    a_n{}\inv,&\text{ if }a_n\neq0,\\
0,&\text{ if }a_n=0.
  \end{cases}
\end{equation*}
\item
If $b\included\supp a$, then $b=\supp c$ for some $c$ in $I$.
\end{enumerate}
The first observation shows
$\Suppinv{\Supp I}=I$; thus, $X\mapsto\Supp X$ is injective on ideals.
With the second observation, along with the identities
  \begin{gather}\label{eqn:cap}
    \supp x\cap \supp y=\supp{xy},\\\notag
\supp x\symdiff\supp y\included\supp{x+y},
  \end{gather}
we can conclude that $\Supp I$ is an ideal of $\pow{\vnn}$.  Finally, if $J$ is an ideal of $\pow{\vnn}$, then~\eqref{eqn:cap} and
  \begin{equation*}
\supp{x+y}\included\supp x\cup\supp y
=\supp x\symdiff \supp y\symdiff\supp{xy},
  \end{equation*}
  along with surjectivity of $x\mapsto\supp x$,
  show that $\Suppinv J$ is an ideal.
\end{proof}

Suppose $M$ is a maximal ideal of $\pow{\vnn}$.  Then
$\Suppinv M$ is a maximal ideal of $\Ko$; let us denote this
ideal also by $M$.  We can form the quotient
\begin{equation*}
  \Ko/M,
\end{equation*}
which must be a field; it is called an
  \textbf{ultrapower} of $K$.  The \textbf{diagonal map}
\begin{equation*}
  x\mapsto(x\colon n\in\vnn)+M
\end{equation*}
is an embedding of $K$ in $\Ko/M$; we shall identify $K$ with its
image in $\Ko/M$.  

If $a$ and $b$ are in $\Ko$, and $a+M=b+M$, let us write also
\begin{equation}\label{eqn:a=b}
  a\equiv b\pmod M,
\end{equation}
or simply $a\equiv b$.
The elements of $M$ (as an ideal
of $\pow{\vnn}$) can be thought of as \textbf{small.}
Then~\eqref{eqn:a=b} holds if and
only if the set $\{n\in\vnn\colon a_n\neq b_n\}$ of indices where $a$
and $b$ differ is small.  This definition makes no use of the
algebraic structure of $K$.  So $K$ can be just a set, although in
\S~\ref{sect:analysis} we shall be interested only in the case where
$K$ is the complete ordered field $\R$. 

\begin{theorem}\label{thm:proper}
  Let $K$ be an infinite set, and $M$ a maximal ideal of
  $\pow{\vnn}$.  Then the diagonal embedding of $K$ in $\seq K/M$ is
  surjective if and only if $M$ is principal.
\end{theorem}

\begin{proof}
  Suppose the element $a$ of $\Ko$ is injective, so that, if $m\neq
  n$, then $a_m\neq a_n$.  Then $a+M$ is in the image of the
  diagonal embedding if and only if $M$ is principal.
\end{proof}

We may henceforth assume that $M$ is a non-principal maximal ideal of
$\pow{\vnn}$, though we shall not actually use the assumption until
\S~\ref{sect:analysis}. 
We have a bijection
\begin{equation*}
  ((x^0_k\colon k\in\vnn),\dots,(x^{n-1}_k\colon k\in\vnn))\mapsto
((x^0_k,\dots,x^{n-1}_k)\colon k\in\vnn)
\end{equation*}
from $(\Ko)^n$ onto $\seq{(K^n)}$; we may write the bijection more
simply as
\begin{equation*}
  (x^0,\dots,x^{n-1})\mapsto(\tuple x_k\colon k\in\vnn).
\end{equation*}
So a plainface $x$ or $x^j$, with a superscript at most, is an element
of $\Ko$ or $K$, while a boldface $\tuple x_k$, with a subscript at most, is
an element of $K^n$; but $x^j_k$, with both superscripts and
subscripts, is in $K$.
Instead of writing
\begin{equation*}
(x^0+M,\dots,x^{n-1}+M), 
\end{equation*}
we may write simply
\begin{equation*}
  (x^0,\dots,x^{n-1})+M;
\end{equation*}
and instead of
\begin{equation*}
  x^0\equiv y^0\land\dotsb\land x^{n-1}\equiv y^{n-1}\pmod M,
\end{equation*}
we may write
\begin{equation*}
(x^0,\dots,x^{n-1})\equiv(y^0,\dots,y^{n-1})\pmod M.
\end{equation*}
If $S\included K^n$, we define
\begin{equation}\label{eqn:*S}
  \sS=\{(x^0,\dots,x^{n-1})+M\colon(\tuple
  x_k\colon k\in\vnn)\in \seq S\}.
\end{equation}
Thus we have a function $X\mapsto\sX$ from $\pow{K^n}$ to
$\pow{{\sK}^n}$ for each $n$ in $\vnn$.  Also
\begin{equation}\label{eqn:sKKoM}
  \sK=\Ko/M.
\end{equation}

\begin{lemma}
Let $S\included K^n$.  Then
\begin{equation*}
  (x^0,\dots,x^{n-1})+M\in\sS\iff\{k\in\vnn\colon\tuple x_k\notin
  S\}\in M.
\end{equation*}
\end{lemma}

\begin{proof}
  Suppose $(x^0,\dots,x^{n-1})+M\in\sS$.  There is
  $(y^0,\dots,y^{n-1})$ in $(\Ko)^n$ such that
  $(x^0,\dots,x^{n-1})\equiv(y^0,\dots,y^{n-1})$ and each $\tuple y_k$
  is in $S$.  Then
  \begin{align*}
    \{k\in\vnn\colon\tuple x_k\notin S\}
&\included\{k\in\vnn\colon x_k^0\neq y_k^0\lor\dotsb\lor x_k^{n-1}\neq
    y_k^{n-1}\}\\
&=\{k\in\vnn\colon x_k^0\neq y_k^0\}\cup\dotsb\cup
\{k\in\vnn\colon x_k^{n-1}\neq y_k^{n-1}\}.
  \end{align*}
Each of the sets $\{k\in\vnn\colon x_k^j\neq y_k^j\}$ is in $M$, so
their union is, and therefore $\{k\in\vnn\colon\tuple x_k\notin S\}\in
M$, by the corollary to Theorem~\ref{thm:Br}.

Now suppose conversely $\{k\in\vnn\colon\tuple x_k\notin S\}\in M$.
Then in particular $S\neq\emptyset$.  Pick some $\tuple y$ in $S$, and
define
\begin{equation*}
  \tuple z_k=
  \begin{cases}
    \tuple x_k,&\text{ if }\tuple x_k\in S,\\
\tuple y,&\text{ if }\tuple x_k\notin S.
  \end{cases}
\end{equation*}
Then $(x^0,\dots,x^{n-1})+M=(z_0,\dots,z^{n-1})+M$, which is in
$\sS$. 
\end{proof}

\begin{theorem}\label{thm:*K}
Let $K$ be a set, and let
the functions $X\mapsto\sX$ from $\pow{K^n}$ to $\pow{{\sK}^n}$
be as given in~\eqref{eqn:*S}.  Then
\begin{gather}
\label{eqn:*=}
\starred{\{(x,x)\colon x\in K\}}=\{(x,x)\colon x\in\sK\};
\intertext{for all $n$ in $\vnn$ and all subsets $S$ and $T$ of $K^n$,}
\label{eqn:SRS}
\sS\cap K^n=S,\\
\label{eqn:st-neg}
\starred{( K^n\setminus S)}=\sK^n\setminus\sS,\\
\label{eqn:st-and}
  \starred{(S\cap T)}=\sS\cap\sT;
\intertext{for all $m$ and $n$ in $\vnn$, all $f$
  from $m$ to $n$, and all subsets $S$ of $K^n$ and $T$ of $K^m$,}
\label{eqn:upper}
  \starred{(f^*[S])}=f^*[\sS],\\
\label{eqn:lower}
  \starred{(f_*(T))}=f_*(\sT).
\end{gather}
(More precisely, the last equations are
  $\starred{(f^*_{ K}[S])}=f^*_{\sK}[\sS]$ and
  $\starred{(f_*^{K}(T))}=f_*^{\sK}(\sT)$.)
\end{theorem}

\begin{proof}
For~\eqref{eqn:*=}, we have
\begin{align*}
  (x,y)+M\in\starred{\{(x,x)\colon x\in K\}}
&\iff\{k\in\vnn\colon x_k\neq y_k\}\in M\\
&\iff x+M=y+M.
\end{align*}

For~\eqref{eqn:SRS}, we
easily have $S\included\sS\cap K^n$.  
Suppose conversely
$(x^0,\dots,x^{n-1})+M\in\sS\cap K^n$.  Then
\begin{equation*}
  \{k\in\vnn\colon\tuple x_k\notin S\}\in M,
\end{equation*}
and also, for some $\tuple y$ in $K^n$, we have
$\{k\in\vnn\colon \tuple x_k\neq\tuple y\}\in M$.
Since
\begin{equation*}
  \{k\in\vnn\colon\tuple y\notin S\}
\included\{k\in\vnn\colon \tuple y\neq\tuple x_k\lor\tuple x_k\notin
S\}
=\{k\in\vnn\colon \tuple y\neq\tuple x_k\}
\cup\{k\in\vnn\colon \tuple x_k\notin S\},
\end{equation*}
we can conclude
$\{k\in\vnn\colon\tuple y\notin S\}\in M$.  (In particular, the set
must be empty.)  Hence $\tuple y\in S$, so 
$(x^0,\dots,x^{n-1})+M\in S$.

For~\eqref{eqn:st-neg}, we have
\begin{align*}
  (x^0,\dots,x^{n-1})+M\in\starred{(K^n\setminus S)}
&\iff\{k\in\vnn\colon\tuple x_k\notin K^n\setminus S\}\in M\\
&\iff\{k\in\vnn\colon\tuple x_k\notin S\}\notin M\\
&\iff  (x^0,\dots,x^{n-1})+M\notin\sS\\ 
&\iff  (x^0,\dots,x^{n-1})+M\in\sK^n\setminus\sS.
\end{align*}

For~\eqref{eqn:st-and}, we have
\begin{align*}
  (x^0,\dots,x^{n-1})+M\in\starred{(S\cap T)}
&\iff\{k\in\vnn\colon\tuple x_k\notin S\cap T\}\in M\\
&\iff\{k\in\vnn\colon\tuple x_k\notin S\}
\cup\{k\in\vnn\colon\tuple x_k\notin T\}\in M\\
&\iff\{k\in\vnn\colon\tuple x_k\notin S\}\in M\land
\{k\in\vnn\colon\tuple x_k\notin T\}\in M\\
&\iff  
\begin{aligned}[t]
&(x^0,\dots,x^{n-1})+M\in\sS\land\\
  &(x^0,\dots,x^{n-1})+M\in\sT
\end{aligned}\\
&\iff  (x^0,\dots,x^{n-1})+M\in\sS\cap\sT.
\end{align*}

For~\eqref{eqn:upper}, we may assume $S\neq\emptyset$, since
$\starred{\emptyset}=\emptyset$.  Let
$(x^0,\dots,x^{n-1})\in(\Ko)^m$.  There is $(\tuple y_k\colon
k\in\vnn)$ in $\seq S$ such that, for all $k$ in $\vnn$, if
$\tuple x_k\in f^*[S]$, then $\tuple x_k=f^*(\tuple y_k)$.  Hence
\begin{align*}
  (x^0,\dots,x^{m-1})+M\in\starred{(f^*[S])}
&\iff\{k\in\vnn\colon\tuple x_k\notin f^*[S]\}\in M\\
&\iff\{k\in\vnn\colon\tuple x_k\neq f^*(\tuple y_k)\}\in M\\
&\iff(x^0,\dots,x^{m-1})+M=f^*(y^0+M,\dots,y^{n-1}+M)\\
&\iff(x^0,\dots,x^{m-1})+M\in f^*[\sS].
\end{align*}

Finally, for~\eqref{eqn:lower}, we have
\begin{align*}
&\phantom{{}\iff{}}(x^0,\dots,x^{n-1})+M\in\starred{(f_*(T))}\\
&\iff\{k\in\vnn\colon \tuple x_k\notin f_*(T)\}\in M\\
&\iff\{k\in\vnn\colon f^*(\tuple x_k)\notin T\}\in M\\
&\iff\{k\in\vnn\colon f^*(\tuple x_k)\neq \tuple y_k\}\in M\text{ for some
  $(\tuple y_k\colon k\in\vnn)$ in $\seq T$}\\
&\iff f^*(x^0+M,\dots,x^{m-1}+M)=(y^0,\dots,y^{n-1})+M\text{ for some
  $(\tuple y_k\colon k\in\vnn)$ in $\seq T$}\\
%&\iff f^*(x^0+M,\dots,x^{m-1}+M)=(y^0,\dots,y^{n-1})+M\text{ for some
%$(y^0,\dots,y^{n-1})+M$ in $\sT$}\\
&\iff (x^0,\dots,x^{m-1})+M\in f_*(\sT).
\qedhere
\end{align*}
\end{proof}

\subsection{Logic}\label{subsect:logic}

It will follow from Theorem~\ref{thm:*K} that $K$ and $\sK$ agree on
\emph{sentences} of 
\emph{first-order logic.}  This result is stated formally as
Theorem~\ref{thm:elsub}, in \S~\ref{sect:analysis} below, for the case
$K=\R$; but the general claim has the same proof, and the preliminary
work done now will be in terms of an arbitrary set $K$.

If $S\included K^n$, then $S$ can be understood as a \emph{name} for:
\begin{enumerate}
\item 
itself, in $K$,
\item
$\sS$, in $\sK$.
\end{enumerate}
We can express this more symbolically by
\begin{align*}
  S^K&=S,&S^{\sK}&=\sS.
\end{align*}
An \textbf{atomic formula} is a string
\begin{equation*}
  St^0\dotsb t^{n-1},
\end{equation*}
where $S\included K^n$, and each $t^k$ is either a variable or an
element of $\sK$.  
In case $n=2$, we customarily write 
\begin{equation*}
t^0\mathrel St^1
\end{equation*}
instead of
$St^0t^1$.

The \textbf{formulas,} simply, are defined
recursively:
\begin{enumerate}
\item 
atomic formulas are formulas,
\item
if $\phi$ is a formula, then so is the \textbf{negation} $\lnot\phi$,
\item
if $\phi$ and $\psi$ are formulas, then so is the \textbf{conjunction}
$(\phi\land\psi)$, 
\item
if $\phi$ is a formula, and $x$ is a variable, then so is the
\textbf{instantiation}\footnote{I don't know of a common term for
  formulas $\Exists x\phi$; \emph{instantiation} seems to work,
  though, since the formula will be interpreted as saying that $\phi$
  is true for some \emph{instance} of $x$.} $\Exists x\phi$ is
a formula.
\end{enumerate}

The following is sometimes overlooked in expositions of logic; but it
is needed to allow recursive definitions on the set of formulas.

\begin{theorem}[Unique Readability]
  Every formula is \emph{uniquely} an atomic formula, a negation, a
  conjunction. or an instantiation.  Every conjunction is
  $(\phi\land\psi)$ for some \emph{unique} formulas $\phi$ and $\psi$.
\end{theorem}

We can introduce the other customary symbols as abbreviations:
\begin{enumerate}
\item 
$(\phi\lto\psi)$ means $\lnot(\phi\land\lnot\psi)$,
\item
$(\phi\lor\psi)$ means $(\lnot\phi\lto\psi)$,
\item
$(\phi\liff\psi)$ means $((\phi\lto\psi)\land(\psi\lto\phi))$,
\item
$\Forall x\phi$ means $\lnot\Exists x\lnot\phi$.
\end{enumerate}
Whether  a variable is \textbf{free} in a formula is defined
recursively:
\begin{enumerate}
\item 
all variables in an atomic formula are free,
\item
the free variables of $\lnot\phi$ are those of $\phi$,
\item
the free variables of $(\phi\land\psi)$ are those of $\phi$ or $\psi$,
\item
the free variables of $\Exists x\phi$ are those of $\phi$, except $x$.
\end{enumerate}
If the free variables of a formula are all on the list
$(x^0,\dots,x^{n-1})$, then the formula can be called
\textbf{$n$-ary.}  In this case, if $n\leq r$, then the formula is
also $r$-ary.  If we want to understand a formula $\phi$ \emph{as}
$n$-ary, we may write it as $\phi(x^0,\dots,x^{n-1})$.

Suppose $t^k$ is in $\sK$ or is a variable for each
$k$ in $\vnn$.  For each $n$-ary formula $\theta$, a formula
$\theta(t^0,\dots,t^{n-1})$ is defined.  The definition is recursive: 
\begin{enumerate}
\item 
If $\theta$ is atomic, then $\theta(\tuple t)$ is the result of
replacing each $x^k$ with $t^k$.
\item
If $\theta$ is $\lnot\phi$, then $\theta(\tuple t)$ is $\lnot\psi$,
where $\psi$ is
$\phi(\tuple t)$.
\item
If $\theta$ is $(\phi\land\psi)$, then $\theta(\tuple t)$ is
$(\phi(\tuple t)\land\psi(\tuple t))$.
\item
If $\theta$ is $\Exists{x^{\ell}}\phi$, then we can understand $\phi$
as $r$-ary, where $r=\max(\ell+1,n)$.  In this case,
 $\theta(\tuple t)$ is $\Exists{x^{\ell}}\psi$, where $\psi$ is
$\phi(\tuple u)$, where
\begin{equation*}
  u^k=
  \begin{cases}
x,&\text{ if }k=\ell,\\
    t^k,&\text{ if }k\neq\ell.
  \end{cases}
\end{equation*}
\end{enumerate}
The case $n=0$ is not excluded; in this case,
$\theta(t^0,\dots,t^{n-1})$ is simply $\theta$.

The \textbf{parameters} of a formula are the (names of) elements of
$\sK$ that appear in the formula.  A \textbf{sentence} is a formula
with no free variables, namely a $0$-ary or \textbf{nullary} formula.  

A sentence $\sigma$ with parameters from $K$
may be \textbf{true} in $K$, in which case we write
\begin{equation*}
  K\models\sigma;
\end{equation*}
otherwise $\sigma$ is \textbf{false} in $K$, and we write
\begin{equation*}
  K\nmodels\sigma.
\end{equation*}
The definition is recursive:
\begin{enumerate}
\item 
$K\models Sa^0\dotsb a^{n-1}$ if and only if $(a^0,\dots,a^{n-1})\in
  S$.
\item
$K\models\lnot\sigma$ if and only if $K\nmodels\sigma$.
\item
$K\models(\sigma\land\tau)$ if and only if $K\models\sigma$ and
  $K\models\tau$.
\item
$K\models\Exists x\phi$ if and only if, assuming $\phi$ is $n$-ary,
 there is $\tuple a$
in $K^n$ such that $K\models\phi(\tuple a)$.
\end{enumerate}
All of the foregoing holds also with $K$ replaced by $\sK$.

The definition of truth shows why formulas as we have defined them are
more precisely called formulas of \textbf{first-order logic.}  In our
formulas, variables stand only for \emph{elements} of $K$.  If we
allowed variables standing for \emph{relations} on $K$, then our
formulas would be \emph{second order.}  The third of the Peano axioms
in \S~\ref{subsect:N} is second order; so is the definition of
completeness of an ordered field.  In \S~\ref{sect:analysis} we shall
note that there is no first-order definition of $\N$ or $\R$.

If $S=\{(x,x)\colon x\in K\}$, then, instead of $t^0\mathrel St^1$, we
may write
\begin{equation*}
  t^0=t^1.
\end{equation*}
Then $K\models a^0=a^1$ if and only if $a^0=a^1$; and likewise in
$\sK$, by~\eqref{eqn:SRS}.
An $n$-ary formula~$\phi$ \textbf{defines} an $n$-ary relation
on $\sK$, namely $\{\tuple a\in\sK^n\colon\sK\models\phi(\tuple
a)\}$; this relation can be denoted by
\begin{equation*}
  \phi^{\sK}.
\end{equation*}
In case $\sigma$ is nullary, we have
  $\sigma^{\sK}=\{x\in\{0\}\colon\sK\models\sigma\}$,
so that
\begin{equation*}
  \sK\models\sigma\iff\sigma^{\sK}=1.
\end{equation*}
If the parameters of a formula all come from $K$, then the
formula similarly defines a relation on $K$, denoted by $\phi^K$.

\begin{theorem}\label{thm:*}
  Let $\theta$ be a formula with parameters from $K$.  Then
  \begin{equation*}
    \starred{(\theta^K)}=\theta^{\sK}.
  \end{equation*}
\end{theorem}

\begin{proof}
  Since formulas are defined recursively, we can argue inductively.
  The claim is true when $\theta$ is atomic, by~\eqref{eqn:SRS}.  If
  the claim is true when $\theta$ is $\phi$, then by~\eqref{eqn:st-neg}
  \begin{align*}
\starred{((\lnot\phi)^K)}
&=\starred{(K^n\setminus\phi^K)}\\
&=\sK^n\setminus\starred{(\phi^K)}\\
&=\sK^n\setminus\phi^{\sK}\\
&=(\lnot\phi)^{\sK},
  \end{align*}
so the claim is true when $\theta$ is $\lnot\phi$.
Similarly, if the claim is true when $\theta$ is $\phi$ or $\psi$,
then by~\eqref{eqn:st-and} the claim is true when $\theta$ is
$(\phi\land\psi)$.  

For the final case, let us first note that, if the claim is true when
$\theta$ is considered as $m$-ary, and $m\leq n$, then the claim is
still true when $\theta$ is considered as $n$-ary.  Indeed, let $f$ be
the inclusion of $m$ in $n$.  Then
\begin{equation*}
  \theta(x^0,\dots,x^{n-1})^K
=\theta(x^0,\dots,x^{m-1})^K\times K^{n-m}
=f_*^K(\theta(x^0,\dots,x^{m-1})^K),
\end{equation*}
and likewise with $\sK$ in place of $K$.  Now use~\eqref{eqn:lower}.

To finish then,
we suppose the claim is true when $\theta$
is $\phi$, and we prove the claim when $\theta$ is $\Exists{x^{\ell}}\phi$.
We may assume $\phi$ and $\Exists{x^{\ell}}\phi$ are both $n$-ary,
where $\ell<n$.  Then we can understand $(x^0,\dots,x^{n-1})$ as
$(\tuple x,y,\tuple z)$, where
$\tuple x$ is $(x^0,\dots,x^{\ell-1})$,
and $y$ is $x^{\ell}$, and
$\tuple x$ is $(x^{\ell+1},\dots,x^{n-1})$.
Then
\begin{align*}
  (\Exists{x^{\ell}}\phi)^K
&=\{(\tuple a,b,\tuple c)\in
  K^n\colon K\models(\Exists{x^{\ell}}\phi)(\tuple a,b,\tuple c)\}\\
&=\{(\tuple a,b,\tuple c)\in
  K^n\colon K\models\Exists{x^{\ell}}\phi(\tuple a,x^{\ell},\tuple c)\}\\
&=f_*^K(
\{(\tuple a,\tuple c)\in
  K^{n-1}\colon K\models\Exists{x^{\ell}}\phi(\tuple
  a,x^{\ell},\tuple c)\}), 
\end{align*}
where $f$ is the function from $n-1$ to $n$ given by
\begin{equation*}
  f(k)=
  \begin{cases}
    k,&\text{ if }k<\ell,\\
k+1,&\text{ if }\ell\leq k<n-1.
  \end{cases}
\end{equation*}
We have also that $K\models\Exists{x^{\ell}}\phi(\tuple
a,x^{\ell},\tuple c)$ if and only if $K\models\phi(\tuple a,b,\tuple
c)$ for some $b$ in $K$.  Then
\begin{equation*}
  \{(\tuple a,\tuple c)\in
  K^{n-1}\colon K\models\Exists{x^{\ell}}\phi(\tuple
  a,x^{\ell},\tuple c)\}
=f^*_K[\phi^K].
\end{equation*}
Combining these results, we have
\begin{equation*}
  (\Exists{x^{\ell}}\phi)^K=f_*^K(f^*_K[\phi^K]).
\end{equation*}
By~\eqref{eqn:upper} and~\eqref{eqn:lower} then, the claim holds when
$\theta$ is $\Exists{x^{\ell}}\phi$.  Therefore it holds generally.
\end{proof}

\begin{theorem}\label{thm:elsub}
  Let $\sigma$ be a sentence with parameters from $K$.
  Then\footnote{In model-theoretic terms, the full structure on $K$ is
    an \emph{elementary substructure} of the structure induced on
    $\sK$ by $X\mapsto\sX$.}
  \begin{equation*}
    K\models\sigma\iff\sK\models\sigma.
  \end{equation*}
\end{theorem}

\begin{proof}
  When $n=0$, then equation~\eqref{eqn:SRS} is simply $\sS=S$.
\end{proof}

\subsection{Mock higher-order logic}\label{subsect:higher}

If we want our logic to be able to refer generally to subsets of a
set, to functions on the set of functions on the set, and so forth,
then we can proceed as follows.
First, we recursively define \textbf{types} as certain strings:

\begin{enumerate}
\item 
$0$ is a type,
\item
if $n\in\vnn\setminus\{0\}$, and $(t_0,\dots,\tau_{n-1})$ is a list of
$n$ types, then the string 
\begin{equation*}
n\tau_0\dotsb\tau_{n-1}
\end{equation*}
is a type.
\end{enumerate}
Note that the type $0$ is also a type of the form
$n\tau_0\dotsb\tau_{n-1}$, where $n=0$.

\begin{theorem}[Unique Readability]
  Every type has the form $n\tau_0\dotsb\tau_{n-1}$ for some
  \emph{unique} $n$ in $\vnn$ and some \emph{unique} list
  $(\tau_0,\dots,\tau_{n-1})$ of types.
\end{theorem}

Given a set $K$, we can now define
\begin{enumerate}
\item 
$K_0=K$,
\item
if $\tau$ is a type $n\tau_0\dotsb\tau_{n-1}$, where $n>0$, then 
\begin{equation*}
K_{\tau}=\pow{K_{\tau(0)}\times\dotsb\times K_{\tau(n-1)}}.
\end{equation*}
\end{enumerate}
Here $\tau(j)$ is just $\tau_j$, when used as a subscript itself.
The first condition is not a special case of the second: if $\tau$ is
not $0$, then elements of $K_{\tau}$ are \emph{relations;} but
elements of $K_0$ are just elements of $K$.
Letting $T$ be the set of types, we define
\begin{equation*}
  \tilde K=\bigcup_{\tau\in T}K_{\tau}.
\end{equation*}
Letting $M$ be a maximal ideal of $\pow{\vnn}$ as before, we have a
special case of~\eqref{eqn:sKKoM}:
\begin{equation*}
  \stK=\seq{\tilde K}/M.
\end{equation*}
This introduces a potential ambiguity, since
$K\included\tilde K$,  but $\sK$ is not literally a subset of
$\stK$. 
Since a relation $S$ on $K$ is
also a relation on $\tilde K$, its image $\sS$ is either a relation on
$\sK$ or on $\stK$, but these two relations called $\sS$ are not
generally the same.  This
problem is taken care of by the following.

\begin{theorem}
$\sK$ embeds in $\stK$ under
  \begin{equation*}
\{x\in\seq K\colon x\equiv a\}\mapsto \{x\in\seq{\tilde
  K}\colon x\equiv a\}.
  \end{equation*}
Then an embedding $i$ of $\pow{\sK^n}$ in $\pow{\stK^n}$ is induced,
and the following diagram commutes.
\begin{equation*}
  \begin{CD}
\pow{K^n}       @>*>>  \pow{\sK^n}\\
@V{\included}VV        @VViV\\
\pow{\tilde K^n}@>>*>  \pow{\stK^n}
  \end{CD}
\end{equation*}
In particular, if $S\included K^n$, then 
\begin{equation*}
i(\sS)=\sS, 
\end{equation*}
where $\sS$ is
computed in $\sK$ and $\stK$ respectively.
\end{theorem}

Another ambiguity arises when we consider that some \emph{elements} of
$\tilde K$ are also \emph{relations} on $\tilde K$.  Indeed, every
element $S$ of $\tilde K\setminus K_0$ is a relation on $\tilde K$, so
it determines both the element $(S\colon k\in\vnn)+M$ or $S$ of $\stK$ and 
  the relation $\sS$ on $\stK$, but these are not literally the same.
  This is taken care of by the following.

  \begin{theorem}\label{thm:iota}
    There is an embedding $\iota$ from
the subset $\bigcup_{\tau\in T}\sKt{\tau}$ of $\stK$ into $(\tsK)$
such that  
    \begin{enumerate}
    \item 
$\iota(x)=x$ when $x\in \sK$,
\item
$\iota(x)\in(\sK)_{\tau}$ when $x\in\sKt{\tau}$,
% $\iota[\sKt{\tau}]\included(\sK)_{\tau}$, 
and 
\item
if $S\in \tilde K\setminus K_0$, then
    \begin{equation}\label{eqn:iota(S)}
      \iota(S)=\{(\iota(x^0),\dots,\iota(x^{n-1}))\colon \tuple
      x\in \sS\}.
    \end{equation}
    \end{enumerate}
  \end{theorem}

\begin{proof}
If $\tau$ is a type $n\tau_0\dotsb\tau_{n-1}$, let
\begin{equation*}
  E_{\tau}=\{(\tuple x,y)\in\tilde K^{n+1}\colon\tuple x\in y\land y\in
  K_{\tau}\}. 
\end{equation*}
Then the sentence
\begin{equation*}
  \Forall{\tuple x}\Forall y(E_{\tau}\tuple xy\lto
  K_{\tau(0)}x^0\land\dotsb\land K_{\tau(n-1)}x^{n-1}\land K_{\tau}y)
\end{equation*}
is true in $\tilde K$.  By Theorem~\ref{thm:elsub}, it is true in
$\stK$.
By Theorem~\ref{thm:*},
\begin{equation*}
  (K_{\tau}x)^{\stK}=\sKt{\tau}.
\end{equation*}
Hence, if $S\in\sKt{\tau}$, then
\begin{equation*}
(E_{\tau}\tuple xS)^{\stK}
\included\sKt{\tau(0)}\times\dotsb\times\sKt{\tau(n-1)}, 
\end{equation*}
and the function that converts such $S$ to $(E_{\tau}\tuple
xS)^{\stK}$ is an embedding.
We can now define~$\iota$ recursively: 
\begin{enumerate}
\item 
$\iota(x)=x$ if $x\in \sKt0$,
\item
if $\tau=n\tau_0\dotsb\tau_{n-1}$, and $R\in\sKt{\tau}$, then
\begin{equation}\label{eqn:iota(R)}
  \iota(R)
  =\{(\iota(a^0),\dots,\iota(a^{n-1}))\colon
\stK\models E_{\tau}\tuple aR\}.
\end{equation}
\end{enumerate}
By induction, $\iota$ maps $\sKt{\tau}$ into $(\sK)_{\tau}$.
Moreover, if again
 $\tau=n\tau_0\dotsb\tau_{n-1}$, and $S\in K_{\tau}$, then
the sentence
\begin{equation*}
  \Forall{\tuple x}(S\tuple x\iff E_{\tau}\tuple xS)
\end{equation*}
is true in $\tilde K$, so it is true in $\stK$, which means in
particular
\begin{equation*}
  \sS=S^{\stK}=(S\tuple x)^{\stK}=(E_{\tau}\tuple xS)^{\stK}.
\end{equation*}
This and~\eqref{eqn:iota(R)} establish~\eqref{eqn:iota(S)}. 
\end{proof}

As we shall see in \S~\ref{sect:analysis}, $\iota$ is not generally
surjective. 
Also, even though every element of $\tilde K$ is an element of some
$K_{\tau}$, not 
every element of $\stK$ is an element of some $\sKt{\tau}$. 


\newpage

\section{Analysis}\label{sect:analysis}

Let $\sR$ be the ultrapower $\seq{\R}/M$ of $\R$, where $M$ is a
\emph{non-principal} maximal ideal of $\pow{\vnn}$.  Then $\R$ embeds
properly in $\sR$, by Theorem~\ref{thm:proper}.
Everything we do now will be based on Theorem~\ref{thm:elsub} in case
$K=\R$ or $K=\tilde{\R}$.  

If $S$ is a relation on $\R$, then $\sS$ is a
\textbf{standard} relation and is the \textbf{extension} of $S$.
Also, elements of $\R^n$ are \textbf{standard.}  Note then that a 
standard relation might have nonstandard elements.

Suppose $S\included\R^n$, and $f$ is a function from $S$ to $\R$.
Let
\begin{equation*}
  T=\{(\tuple x,f(\tuple x))\colon\tuple x\in S\};
\end{equation*}
this is the \textbf{graph} of $f$.  Then the sentences
\begin{gather*}
  \Forall{\tuple x}\Exists y(S\tuple x\lto T\tuple xy),\\
\R\models\Forall{\tuple x}\Forall y\Forall z(S\tuple x\land T\tuple
xy\land T\tuple xz\lto y=z)),
\end{gather*}
are true in $\R$; by Theorem~\ref{thm:*}, they
are true in $\sR$.  Therefore $\sT$ is the graph of a
function from $\sS$ to $\sR$.  We may denote this function by
\begin{equation*}
  \stf.
\end{equation*}
We have then
\begin{equation}\label{eqn:*f}
  \stf\restriction S=f.
\end{equation}
In a formula, in place of $T\tuple xy$, we may write
\begin{equation*}
  f(\tuple x)=y.
\end{equation*}

\begin{theorem}
  $\sR$ is a non-Archimedean ordered field with respect to
  ${}^*\mathord{<}$, $\starred +$, $\starred -$, and
  $\starred{\cdot}$, and $\R$ is an ordered subfield of $\sR$.
\end{theorem}

\begin{proof}
There is a first-order sentence $\sigma$ saying that $\R$ is an
ordered field; but then $\sR\models\sigma$.  By~\eqref{eqn:SRS}
and~\eqref{eqn:*f}, $\R$ is an ordered subfield of $\sR$.  Since $\R$
is a \emph{proper} subset of $\sR$, the latter must be
non-Archimedean.
\end{proof}

\begin{corollary}
Being Archimedean is not a first-order property of fields.
\end{corollary}

In the notation of the proof of Theorem~\ref{thm:iota}, we have the sentence 
\begin{multline*}
  \Forall x(
\Exists yE_{10}yx\land\Exists z\Forall y(E_{10}yx\lto y\leq z)
\lto\\
\Exists w(\Forall y(E_{10}yx\lto y\leq w)
  \land
\Forall z(\Forall y(E_{10}yx\lto y\leq z)
\lto 
w\leq z))),
\end{multline*}
which says in $\tilde{\R}$ that every subset $x$ of $\R$ with an element $y$
and an upper bound $z$ has a least upper bound $w$.  This is true, so
the same sentence is
true in $\startilde{\R}$.  But more precisely, in $\tilde{\R}$,  the
sentence is 
not about subsets of $\R$, but about elements of $\R_{10}$, which is
$\pow{\R}$. 
In $\startilde{\R}$, the sentence says that every element of
$\starsub{\R}{10}$ with an upper bound has a least upper bound.  
We know that $\iota(\starsub{\R}{10})\included(\sR)_{10}$, which is
$\pow{\sR}$.  Now we can conclude that the embedding is proper, not
surjective. 


\begin{theorem}
  $\N$ is a proper initial segment of $\sN$.  In particular, $\N$
  consists of the finite elements of $\sN$.
\end{theorem}

\begin{proof}
  For each $n$ in $\N$, the sentence
\begin{equation*}
  \Forall x(\N x\lto x=0\lor x=1\lor\dotsb\lor x=n\lor x>n)
\end{equation*}
is true in $\R$, hence in $\sR$, so that $\{0,1,\dots,n\}$ is an
initial segment of $\sN$.  The sentence
\begin{equation*}
  \Forall x\Exists y(\N y\land x<y)
\end{equation*}
is true in $\R$ and hence in $\sR$.  In particular, let $a$ be a
positive infinite element of $\sR$. Then there is $n$ in $\sN$ such
that $a<n$.  Such $n$ must be infinite and so are not in $\N$.
\end{proof}

\begin{corollary}
The Peano Axioms are not first order.
\end{corollary}

\begin{theorem}
  A standard relation has nonstandard elements if and only if it is
  infinite. 
\end{theorem}

\begin{proof}
  Suppose $S=\{\tuple a_0,\dots,\tuple a_{n-1}\}\included\R^m$.  Then
  the sentence
  \begin{equation*}
    \Forall{\tuple x}(S\tuple x\liff\tuple x=\tuple
    a_0\lor\dotsb\lor\tuple a_{n-1})
  \end{equation*}
is true in $\R$ and $\sR$, so $\sS=S$.

Now suppose $f$ is an injective function from $\N$ into $\R$.  Then
$\stf$ is an injective function on $\sN$. If
$\stf(n)$ is an element $a$ of $\R$ for some $n$ in $\sN$, then the
sentence 
\begin{equation*}
  \Exists x(\N x\land f(x)=a)
\end{equation*}
is true in $\sR$ and $\R$,
so $n\in\N$.  Thus, if $n\in\sN\setminus\N$, then
$\stf(n)\in\sR\setminus\R$. 
\end{proof}

\subsection{Sequences}

\begin{theorem}
  Let $a$ be a sequence $(a_n\colon n\in\N)$ in $\R$.  Then $\sa$ is a
  sequence $(a_n\colon n\in\sN)$ for some $a_n$ in $\sR$ (for 
  $n$ in $\sN\setminus\N$).  Also $a$ converges if and only if
  $\sa$ converges.  If $\sa$ converges to $b$, then
  $b\in\R$. 
\end{theorem}

The following theorem can be understood as an alternative
\emph{definition} of convergence, if one does not want to bother with
the traditional definition.

\begin{theorem}
  A standard sequence $(a_n\colon n\in\sN)$ converges to $L$ if and
  only if, for all infinite $n$,
  \begin{equation*}
    a_n\simeq L.
  \end{equation*}
\end{theorem}

\begin{proof}
Let $a$ be the sequence, and suppose it converges to $L$.  For every
positive standard 
  $\epsilon$, there is a standard $M$ such that the sentence
  \begin{equation*}
    \Forall x(\N x\land x\geq M\lto\abs{a_n-L}<\epsilon)
  \end{equation*}
is true in $\R$ and $\sR$.
In particular, for every infinite $n$, we have $\abs{a_n-L}<\epsilon$
for every standard positive $\epsilon$; but this just means $a_n\simeq
L$.  

Suppose $a$ does not converge to $L$.  Then there is some positive
standard $\epsilon$ such that the sentence
\begin{equation*}
  \Forall y\Exists x(\N x\land x\geq
  y\land\abs{a_n-L}\geq\epsilon)
\end{equation*}
is true in $\R$ and $\sR$.
In particular, if $M$ is infinite, then there is some $n$ in $\sN$
that is greater than $M$ (and therefore infinite) such that
$\abs{a_n-L}\geq\epsilon$. 
\end{proof}

For example, $\lim_{n\to\infty}1/n=0$, simply because $1/n$ is
infinitesimal when $n$ is infinite.

\begin{theorem}
Let $a$ and $b$ be standard convergent sequences, and $r\in\R$.  Then
\begin{gather}\label{eqn:lim+}
\lim(a+b)=\lim(a)+\lim(b),\\\label{eqn:lim-r}
\lim(ra)=r\lim(a),\\\label{eqn:lim.}
  \lim(ab)=\lim(a)\lim(b).
\end{gather}
\end{theorem}

\begin{proof}
  Let $R$ be the ring of finite members of $\sR$, and let $I$ be its
  ideal of infinitesimals.  Suppose $a_n\simeq L$ and $b_n\simeq M$.  Then
  $a_n-L$ and $b_n-M$ are in $I$, hence so are $(a_n+b_n)-(L+M)$ and
  $ra_n-rL$.   This shows~\eqref{eqn:lim+} and~\eqref{eqn:lim-r}.
  For~\eqref{eqn:lim.}, note
  \begin{equation*}
    \abs{a_nb_n-LM}=
    \abs{a_nb_n-a_nM+a_nM-LM}\leq
    \abs{a_n}\abs{b_n-M}+\abs{a_n-L}\abs{M}.
  \end{equation*}
But the last is in $I$ since $\abs{a_n}$ and $\abs M$ are in $R$ (why?).
\end{proof}

\begin{theorem}\label{thm:bdd}
  A standard sequence is bounded if and only if
  every term is finite.
\end{theorem}

\begin{proof}
  That $a$ is bounded means that, for some $M$, the sentence
  \begin{equation*}
    \Forall x(x\in\N\lto \abs{a_x}<M)
  \end{equation*}
is true in $\R$; then it is true in $\sR$, so every entry in $\sa$ is
bounded by $M$, hence finite. 

Suppose $a$ is unbounded.  Then the sentence
\begin{equation*}
  \Forall x\Exists y(y\in\N\land\abs{a_y}>x
\end{equation*}
is true in $\R$, hence in $\sR$.  Let $L$ be positive and infinite;
then there is $n$ in $\sN$ such that $\abs{a_n}>L$.
\end{proof}

Compare the following with Theorem~\ref{thm:Cc}.

\begin{theorem}
  A standard sequence $(a_n)$ converges if and only if, for all
  infinite $m$ and~$n$,
  \begin{equation*}
    a_m\simeq a_n.
  \end{equation*}
\end{theorem}

\begin{proof}
If $(a_n)$ converges to $L$, then $a\simeq L$ for all infinite $n$,
and therefore $a_m\simeq a_n$ for all infinite $m$ and $n$, since
$\simeq$ is an equivalence relation. 

Suppose conversely $a_m\simeq a_n$ for all infinite $m$ and $n$.  If
each $a_n$ is \emph{finite}, and $n$ is in particular infinite, then
$(a_n)$ converges to the standard part of $a_n$.  Suppose some $a_n$ is
infinite.  Then by Theorem~\ref{thm:bdd}, the sequence $(a_n\colon n\in\N)$ is
unbounded.  Hence the sentence
\begin{equation*}
  \Forall x\Exists y(x\in\N\lto y\in N\land x\leq
  y\land\abs{a_x}+1\leq\abs{a_y}) 
\end{equation*}
is true in $\R$ and $\sR$, so $a_m$ and $a_n$ fail to be infinitely
close for some infinite $m$ and $n$.
\end{proof}

Traditionally, $L$ is a \textbf{limit point} of $(a_n)$ if for all
positive $\epsilon$ and for all $m$ in $\N$, there is $n$ such that
$m<n$ and $\abs{L-a_n}<\epsilon$.  The following can be used as an
alternative definition.

\begin{theorem}\label{thm:l-point}
  A finite number $L$ is a limit point of the standard sequence
  $(a_n)$ if and only if, for some infinite $n$,
  \begin{equation*}
    a_n\simeq L.
  \end{equation*}
\end{theorem}

\begin{proof}
  If $L$ is a limit point of $(a_n)$, then the sentence
  \begin{equation*}
    \Forall x\Forall y\Exists z(x>0\land y\in\N\lto z\in N\land
    y<z\land\abs{L-a_z}<x)
  \end{equation*}
is true in $\R$ and $\sR$, so for an infinitesimal $\epsilon$ there is
an infinite $n$ such that $\abs{L-a_n}<\epsilon$ and hence $a_n\simeq
L$.

Suppose $L$ is not a limit point of $(a_n)$.  Then there is some
positive $\epsilon$ and some $n$ in $\N$ such that the sentence
\begin{equation*}
  \Forall x(x\in\N\lto\abs{L-a_x}\geq\epsilon)
\end{equation*}
is true in $\R$ and $\sR$.  This means $\abs{L-a_n}\geq\epsilon$
whenever $n$ is infinite.
\end{proof}

The non-standard proof of the following should be compared with the
traditional divide-and-conquer proof.

\begin{theorem}[Bolzano--Weierstra\ss]
  Every bounded standard sequence has a limit point.
\end{theorem}

\begin{proof}
Indeed, by Theorem~\ref{thm:bdd}, if $(a_n)$ is bounded, then each
$a_n$ has a standard part when $n$ is infinite, and that standard part
is a limit point of the sequence by Theorem~\ref{thm:l-point}.  
\end{proof}

\subsection{Continuity}

Suppose now $f$ is a standard function defined on an interval $[a,b]$.
If $c\in[a,b]$, we say, classically, that
\begin{equation*}
  \lim_{x\to c}f(x)=\lim_c(f)=L
\end{equation*}
if for all positive $\epsilon$ there is a positive $\delta$ such that,
for all $x$ in $[a,b]$, 
\begin{equation*}
  0<\abs{x-c}<\delta\implies\abs{L-f(x)}<\epsilon.
\end{equation*}

\begin{theorem}
If $f$ is a standard function defined on an interval $I$ that contains
$c$, then $\lim_cf=L$ if and only if, for all $x$ in $I$ that are
distinct from $c$,
\begin{equation*}
  x\simeq c\implies f(x)\simeq L.
\end{equation*}
\end{theorem}

\begin{theorem}
  If $\lim_cf$ and $\lim_cg$ exist, then
  \begin{gather}\notag
    \lim_c(f+g)=\lim_c(f)+\lim_c(g),\\\notag
    \lim_c(fg)=\lim_c(f)\lim_c(g);
\intertext{if also $\lim_c(f)\neq0$, then}\label{eqn:1/f}
    \lim_c\left(\frac1f\right)=\frac1{\lim_c(f)}.
  \end{gather}
\end{theorem}


\begin{proof}
  For~\eqref{eqn:1/f}, if $f(x)\simeq L$, and $L\neq0$, then
  $\abs{f(x)}>\abs L/2$, so that
  \begin{equation*}
    \left|\frac1{f(x)}-\frac1L\right|
=\frac{\abs{L-f(x)}}{\abs{f(x)L}}
<\frac2{L^2}\abs{L-f(x)}
\simeq0.\qedhere
  \end{equation*}
\end{proof}

The function $f$ is \textbf{continuous at} $c$, if $\lim_c(f)=f(c)$;
\textbf{continuous on} $[a,b]$, if continuous at every point of
$[a,b]$. 

\begin{theorem}[Intermediate Value]
  If $f$ is continuous on $[a,b]$, and $d$ lies between $f(a)$ and
  $f(b)$, then for some $c$ in $(a,b)$, 
  \begin{equation*}
    f(c)=d.
  \end{equation*}
\end{theorem}

\begin{proof}
  Suppose $f(a)<d<f(b)$. In $\R$, for all $n$ in $\N$, there is some
  \emph{least} $j$ in $\N$ such that
  \begin{equation}\label{eqn:IVT}
    f(a+\frac jn(b-a))<d\leq f(a+\frac{j+1}n(b-a)).
  \end{equation}
Then the same is true in $\sR$, with $\sN$ replacing $\N$.  In
particular, we have~\eqref{eqn:IVT} for some $j$ in $\sN$, where $n$
is in $\sN\setminus\N$.  Let $c$ be the standard part of
$a+(j/n)(b-a)$.  Then
\begin{equation*}
      f(a+\frac jn(b-a))\simeq f(c)\simeq f(a+\frac{j+1}n(b-a)).
\end{equation*}
Therefore $f(c)=d$.
\end{proof}

\begin{theorem}[Extreme Value]\label{thm:EVT}
  If $f$ is continuous on $[a,b]$, then it attains a maximum and
  minimum value on the interval.
\end{theorem}

\begin{proof}
  For all positive natural numbers $n$, for some natural number $j$
  such that $j\leq n$, the value of
  \begin{equation*}
    f(a+\frac jn(b-a))
  \end{equation*}
is maximized.  In particular, this is so when $n$ is infinite.  
If $i\leq n$, we now have
  \begin{equation*}
f(a+\frac in(b-a))\leq    f(a+\frac jn(b-a)).
  \end{equation*}
Let $d$ be the standard part of $a+(j/n)(b-a)$. 
For every $c$ in $[a,b]$, there is a natural number $i$ such that
\begin{equation*}
  a+\frac in(b-a)\leq c<a+\frac{i+1}n(b-a).
\end{equation*}
Then these three numbers are infinitely close, so
\begin{equation*}
  f(c)\simeq f(a+\frac in(b-a)).
\end{equation*}
Therefore $f(c)\leq f(d)$.
\end{proof}

\subsection{Derivatives}

If
\begin{equation*}
  \lim_{x\to c}\frac{f(x)-f(c)}{x-c}=d,
\end{equation*}
then we write
\begin{equation*}
  f'(c)=d,
\end{equation*}
saying $f$ is \textbf{differentiable} at $c$, with \textbf{derivative}
$d$ at $c$.
So
$f'(c)=d$ if and only if, whenever $c\simeq c$ but $x\neq c$, we have
\begin{equation*}
  \frac{f(x)-f(c)}{x-c}\simeq d.
\end{equation*}

\begin{theorem}
If $f$ is differentiable at $c$, then it is continuous at $c$.
\end{theorem}

\begin{proof}
If $f$ is differentiable at $c$ and $x\simeq c$, then
\begin{equation*}
  f(x)-f(c)\simeq (x-c)f'(c)\simeq0;
\end{equation*}
so $f$ is continuous at $c$.
\end{proof}

\begin{theorem}
If $f$ and $g$ are differentiable at $c$, then so are $f+g$ and $fg$,
and
\begin{align*}
  (f+g)'(c)&=f'(c)+g'(c),& (fg)'(c)&=f'(c)g(c)+f(c)g'(c).
\end{align*}
\end{theorem}

\begin{proof}
  If $x\simeq c$, then 
  \begin{equation*}
    \frac{(fg)(x)-(fg)(c)}{x-c}
=\frac{f(x)-f(c)}{x-c}g(c)+
f(x)\frac{g(x)-g(c)}{x-c}\simeq f'(c)g(c)+f(c)g'(c).\qedhere
  \end{equation*}
\end{proof}

The standard function $f$ has a \textbf{local maximum} at $c$ if, for
some positive $\delta$, the function $f$ is defined on
$(c-\delta,c+\delta)$ and on this interval is maximized at $c$.

\begin{theorem}
  A standard function $f$ has a local maximum at $c$ if and only if
  $f$ is defined on $\{x\colon x\simeq c\}$ and on this interval is
  maximized at $c$.
\end{theorem}

\begin{proof}
  Necessity of the condition is immediate.  To prove sufficiency,
  suppose $f$ does not have a local maximum at $c$.  Then for every
  positive $\delta$, and in particular for $\delta$ that are
  infinitely close to $c$, either $f$ is not defined on
  $(c-\delta,c+\delta)$, or else $f$ is not maximized there at $c$.
  But that interval is a subset of $\{x\colon x\simeq c\}$.
\end{proof}

\begin{theorem}\label{thm:lmd}
  If $f$ has a local maximum and is differentiable at $c$, then $f'(c)=0$.
\end{theorem}

\begin{proof}
  We assume that, if $x\simeq c$, but $x\neq c$, then $f(x)\leq c$, so
  \begin{equation*}
    \frac{f(x)-f(c)}{x-c}
    \begin{cases}
      \geq0,&\text{ if }x<c,\\
\leq0,&\text{ if }x>c.
    \end{cases}
  \end{equation*}
Since $(f(x)-f(c))/(x-c)\simeq f'(c)$, we can conclude that $f'(c)=0$.
\end{proof}

\begin{theorem}[Rolle]
  If $f$ is continuous on $[a,b]$ and differentiable on $(a,b)$, and
  $f(a)=f(b)$, then,
  for some $c$ in $(a,b)$,
  \begin{equation*}
    f'(c)=0.
  \end{equation*}
\end{theorem}

\begin{proof}
  Theorems~\ref{thm:EVT} and~\ref{thm:lmd}.
\end{proof}

\subsection{Integrals}

Classically, the integral of a bounded function $f$ on an interval
$[a,b]$ can be defined as follows.  Suppose $I$ is a number such that,
for all positive $\epsilon$, 
there is a positive $\delta$ such that, for all positive integers $n$,
for all lists $(a_0,\dots,a_n)$ and $(\xi_1,\dots,\xi_n)$ of numbers
such that  
\begin{equation}\label{eqn:axa}
  a=a_0\leq\xi_1\leq a_1\leq\dotsb\leq a_{n-1}\leq\xi_n\leq a_n=b
\end{equation}
and also
\begin{equation*}
  \min(a_1-a_0,\dots,a_n-a_{n-1})\leq\delta,
\end{equation*}
we have
\begin{equation*}
  \abs{I-\sum_{i=1}^nf(\xi_i)(a_i-a_{i-1})}<\epsilon.
\end{equation*}
Then $f$ is \textbf{integrable} on $[a,b]$, and
\begin{equation*}
  \int_a^bf=I.
\end{equation*}
This is not a first-order statement in $\R$, so we move to $\tilde{\R}$.
Let $A_{[a,b]}$ be the set of finite
  sequences $(a_0,\xi_1,a_1,\dots,x_n,a_n)$ with entries from $\R$,
  where $n\in\N$ and~\eqref{eqn:axa}
  holds.  Such sequences can be understood as binary relations on
  $\R$, so that $A_{[a,b]}\in\R_{200}$.
 If $f$ is a bounded function on $[a,b]$, let $S_{f,a,b}$ be the function
  \begin{equation*}
    (a_0,\xi_1,a_1,\dots,\xi_n,a_n)\mapsto\sum_{i=1}^nf(\xi_i)(a_i-a_{i-1})
  \end{equation*}
on $A$.  So $S_{f,a,b}\in\R_{22000}$.  An element of $\sA_{[a,b]}$
also takes the form $(a_0,\xi_1,a_1,\dots,\xi_n,a_n)$, where
again~\eqref{eqn:axa} holds; but now $n\in\sN$.  Such an element can
be called \textbf{fine} if $a_{i-1}\simeq a_i$ for each $i$ in
$\{1,\dots,n\}$. 
It must be noted that fine elements of $\sA$ do exist: for example,
\begin{equation*}
(a,a+\frac1n(b-a),a+\frac1n(b-a),\dots,a+\frac{n-1}n(b-a),a+\frac{n-1}n(b-a)),
\end{equation*}
where $n$ is infinite.

\begin{theorem}
  Given a bounded function $f$ on $[a,b]$,
Then $f$ is integrable on $[a,b]$ if and only if, for any two fine
elements $a$ and $a'$ of $\sA_{[a,b]}$,
\begin{equation*}
  \sS_{f,a,b}(a)\simeq
\sS_{f,a,b}(a').
\end{equation*}
In this case, $\int_a^bf$ is the standard part of either of these sums.
\end{theorem}

\begin{theorem}[Fundamental, of Calculus]
  Suppose $f$ is continuous on $[a,b]$.  If $a\leq c\leq b$, then $f$ is
  integrable on $[a,c]$.  The function
  \begin{equation*}
    x\mapsto\int_a^xf
  \end{equation*}
is differentiable on $[a,b]$, and its derivative is $f$.
\end{theorem}

\newpage

\appendix

\section{The Greek alphabet}\label{app:Greek}
\vfill
  \begin{center}
      \begin{tabular}{c c c c}
capital&minuscule&transliteration&name\\\hline
\Gk{A}& \Gk{a} & a & alpha \\ 
\Gk{B}& \Gk{b} & b & beta   \\ 
\Gk{G}& \Gk{g} & g & gamma \\ 
\Gk{D}& \Gk{d} & d & delta \\ 
\Gk{E}& \Gk{e} & e & epsilon\\ 
%&\Gk{\stigma}& stigma\\
\Gk{Z}& \Gk{z} & z & zeta   \\ 
\Gk{H}& \Gk{h} & \^e & eta \\ 
 \Gk{J}& \Gk{j} & th & theta \\
%\hline 
 \Gk{I}& \Gk{i} & i & iota\\ 
\Gk{K}& \Gk{k} & k & kappa\\ 
 \Gk{L}& \Gk{l} & l & lambda\\ 
 \Gk{M}& \Gk{m} & m & mu \\
 \Gk{N}& \Gk{n} & n & nu \\ 
 \Gk{X}& \Gk{x} & x & xi \\ 
 \Gk{O}& \Gk{o} & o & omicron\\ 
 \Gk{P}& \Gk{p} & p & pi\\ 
%&\Gk{\qoppa}& koppa\\
%\hline
 \Gk{R}& \Gk{r} & r & rho\\ 
 \Gk{S}& \Gk{s, c} & s & sigma \\
 \Gk{T}& \Gk{t} & t & tau \\ 
 \Gk{U}& \Gk{u} & y, u & upsilon \\ 
 \Gk{F}& \Gk{f} & ph & phi\\ 
 \Gk{Q}& \Gk{q} & ch & chi\\ 
 \Gk{Y}& \Gk{y} & ps & psi\\ 
 \Gk{W}& \Gk{w} & \^o & omega\\
%&\Gk{\sampi}& sampi\\
\hline
  \end{tabular}
  \end{center}
\vfill
\vfill
The following remarks pertain to \emph{ancient} Greek.
The vowels are 
%\begin{center}
\Gk{a, e, h, i, o, u, w,} 
%\end{center}
where
\Gk h is a long \Gk e, and \Gk w is a long \Gk o; the other vowels
(\Gk{a, i, u}) can be long or short.  
Some vowels may be given tonal accents
(\Gk{'a, ~a, `a}).  
An initial vowel takes either a rough\-{}-breathing mark (as in
\Gk{<a}) or a 
smooth\-{}-breathing mark (\Gk{>a}): the former mark is transliterated
by a preceding
\lett h, and the latter can be ignored, as in
  \Gk{<uperbol'h} hyperbol\^e \emph{hyperbola,}
\Gk{>orjog'wnion} orthog\^onion \emph{rectangle.}
Likewise, \Gk{<r} is
transliterated as \lett{rh}, as in
  \Gk{<r'omboc} rhombos \emph{rhombus.}
A long vowel may have an iota subscript (\Gk{a|, h|, w|}), especially
in case-endings of nouns.
Of the two forms of minuscule sigma, the \Gk{c} appears at
the ends of words; elsewhere, \Gk{sv} appears, as in
\Gk{b'asic} basis \emph{base.}
\vfill
\vfill
%\appendix\setcounter{chapter}1 % needed because of language-switching


%\appendix\setcounter{chapter}1 % needed because of language-switching

\section{The German script}\label{app:German}

Writing in 1993, Wilfrid Hodges \cite[Ch.~1, p.~21]{MR94e:03002} observes
\begin{quotation}
  Until about a dozen years ago, most model theorists named structures
  in horrible Fraktur lettering.  Recent writers sometimes adopt a
  notation according to which all structures are named $M$, $M'$,
  $M^*$, $\bar M$, $M_0$, $M_i$ or occasionally $N$.  
%I hope I cause no offence by using a more freewheeling notation.
\end{quotation}
For Hodges, structures are $A$, $B$, $C$, and so forth; he refers to
their universes as
\textbf{domains}
and denotes these by $\dom A$ and so forth.  
%\begin{comment}
This practice is
convenient if one is using a typewriter (as in the preparation of
another of Hodges's books \cite{Hodges-Building}, from 1985).
In 2002, David Marker \cite{MR1924282} uses `calligraphic' letters for
structures, so that $M$ is the universe of~$\mathcal M$.
%\end{comment}
I still prefer the Fraktur letters:
%In \AmS\ \LaTeX\ (by which these notes are typeset) these letters are:
\begin{align*}
&\begin{array}{ccccccccc}
\mathfrak A&\mathfrak B&\mathfrak C&\mathfrak D&\mathfrak E&\mathfrak F&\mathfrak G&\mathfrak H&\mathfrak I\\\mathfrak J&\mathfrak K&\mathfrak L&\mathfrak M&\mathfrak N&\mathfrak O&\mathfrak P&\mathfrak Q&\mathfrak R\\\mathfrak S&\mathfrak T&\mathfrak U&\mathfrak V&\mathfrak W&\mathfrak X&\mathfrak Y&\mathfrak Z&
  \end{array}
&
&\begin{array}{ccccccccc}
\mathfrak a&\mathfrak b&\mathfrak c&\mathfrak d&\mathfrak e&\mathfrak f&\mathfrak g&\mathfrak h&\mathfrak i\\\mathfrak j&\mathfrak k&\mathfrak l&\mathfrak m&\mathfrak n&\mathfrak o&\mathfrak p&\mathfrak q&\mathfrak r\\\mathfrak s&\mathfrak t&\mathfrak u&\mathfrak v&\mathfrak w&\mathfrak x&\mathfrak y&\mathfrak z&
  \end{array}
\end{align*}
A way to write these by hand is seen in a textbook
of German from 1931 \cite{German}:
\vfill
\begin{center}
\includegraphics[width=417pt,height=292pt]{german-script-cropped.eps}
\end{center}
\vfill\vfill
\newpage

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

\bibitem{MR1660991}
{Apollonius of Perga}, \emph{Conics. {B}ooks {I}--{III}}, revised ed., Green
  Lion Press, Santa Fe, NM, 1998, Translated and with a note and an appendix by
  R. Catesby Taliaferro, With a preface by Dana Densmore and William H.
  Donahue, an introduction by Harvey Flaumenhaft, and diagrams by Donahue,
  Edited by Densmore. \MR{MR1660991 (2000d:01005)}

\bibitem{MR2000800}
Archimedes, \emph{The works of {A}rchimedes}, Dover Publications Inc., Mineola,
  NY, 2002, Reprint of the 1897 edition and the 1912 supplement, Edited by T.
  L. Heath. \MR{MR2000800 (2005a:01003)}

\bibitem{MR2093668}
\bysame, \emph{The works of {A}rchimedes. {V}ol. {I}}, Cambridge University
  Press, Cambridge, 2004, The two books on the sphere and the cylinder,
  Translated into English, together with Eutocius' commentaries, with
  commentary, and critical edition of the diagrams by Reviel Netz.
  \MR{MR2093668 (2005g:01006)}

\bibitem{MR0159773}
Richard Dedekind, \emph{Essays on the theory of numbers. {I}: {C}ontinuity and
  irrational numbers. {II}: {T}he nature and meaning of numbers}, authorized
  translation by Wooster Woodruff Beman, Dover Publications Inc., New York,
  1963. \MR{MR0159773 (28 \#2989)}

\bibitem{MR17:814b}
Euclid, \emph{The thirteen books of {E}uclid's {E}lements translated from the
  text of {H}eiberg. {V}ol. {I}: {I}ntroduction and {B}ooks {I}, {I}{I}. {V}ol.
  {I}{I}: {B}ooks {I}{I}{I}--{I}{X}. {V}ol. {I}{I}{I}: {B}ooks
  {X}--{X}{I}{I}{I} and {A}ppendix}, Dover Publications Inc., New York, 1956,
  Translated with introduction and commentary by Thomas L. Heath, 2nd ed.
  \MR{17,814b}

\bibitem{MR1932864}
\bysame, \emph{Euclid's {E}lements}, Green Lion Press, Santa Fe, NM, 2002, All
  thirteen books complete in one volume, the Thomas L. Heath translation,
  edited by Dana Densmore. \MR{MR1932864 (2003j:01044)}

\bibitem{German}
Roe-Merrill~S. Heffner, \emph{Brief {G}erman grammar}, D. C. Heath and Company,
  Boston, 1931.

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

\bibitem{Hodges-Building}
\bysame, \emph{Building models by games}, Dover Publications, Mineola, New
  York, 2006, original publication, 1985. \MR{MR812274 (87h:03045)}

\bibitem{MR12:397m}
Edmund Landau, \emph{Foundations of analysis. {T}he arithmetic of whole,
  rational, irrational and complex numbers}, third ed., Chelsea Publishing
  Company, New York, N.Y., 1966, translated by F. Steinhardt; first edition
  1951; first German publication, 1929. \MR{12,397m}

\bibitem{MR1924282}
David Marker, \emph{Model theory: an introduction}, Graduate Texts in
  Mathematics, vol. 217, Springer-Verlag, New York, 2002. \MR{1 924 282}

\bibitem{Peano}
Giuseppe Peano, \emph{The principles of arithmetic, presented by a new method
  (1889)}, From {F}rege to {G}{\"o}del (Jean van Heijenoort, ed.), Harvard
  University Press, 1976, pp.~83--97.

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

\bibitem{Spivak-Calc}
Michael Spivak, \emph{Calculus}, 2nd ed., Publish or Perish, Berkeley,
  California, 1980.

\bibitem{MR13:419b}
Ivor Thomas (ed.), \emph{Selections illustrating the history of {G}reek
  mathematics. {V}ol. {II}. {F}rom {A}ristarchus to {P}appus}, Harvard
  University Press, Cambridge, Mass, 1951, With an English translation by the
  editor. \MR{13,419b}

\end{thebibliography}

\end{document}
