%\documentclass[a4paper,twoside,draft]{article}
\documentclass[a4paper,twoside,draft,11pt]{amsart}

\title{Foundations of number-theory}
\author{David Pierce}
\date{November 9, 2007; recompiled, \today}

\address{Mathematics Dept\\
Middle East Technical Univ.\\
Ankara 06531, Turkey}

\email{dpierce@metu.edu.tr}
\urladdr{http://www.math.metu.edu.tr/~dpierce}


%\input{../abbreviations}    % I now prefer to incorporate only 
%\input{../article-theorems} % what I need from these  

\usepackage{amssymb,amsmath,amsthm}
%\usepackage{amscd}     % commutative diagram
%\usepackage[mathscr]{euscript}
%\usepackage{url}
\usepackage{verbatim}  % allows a comment environment:
%\usepackage{showlabels}


%\usepackage{parskip}   % paragraphs not indented, but separated by spaces

%\usepackage{eco}  % gives old-style numerals
\usepackage{hfoldsty}  % gives old-style numerals

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%  Theorem-like environments  %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\swapnumbers


\newtheorem{theorem}{Theorem}
\newtheorem{axdef}[theorem]{Axiom and definition}
\newtheorem{lemma}[theorem]{Lemma}

\theoremstyle{definition}

\newtheorem{definition}[theorem]{Definition}
\newtheorem{parag}[theorem]{}

\theoremstyle{remark}

\newtheorem{remarks}[theorem]{Remarks}
\newtheorem{remark}[theorem]{Remark}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\renewcommand{\leq}{\leqslant}
\renewcommand{\geq}{\geqslant}
\renewcommand{\setminus}{\smallsetminus}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\defn}[2]{\textbf{#1#2}}

\renewcommand{\theenumi}{\alph{enumi}}
\renewcommand{\labelenumi}{\textnormal{(\theenumi)}}

\renewcommand{\theenumii}{\roman{enumii}}
\renewcommand{\labelenumii}{\textnormal{(\theenumii)}}

% set-theoretic relations:

\newcommand{\included}{\subseteq}      % [the name suggests the meaning here]
\newcommand{\nincluded}{\not\subseteq} % not included
\newcommand{\pincluded}{\subset}       % proper inclusion    
\newcommand{\includes}{\supseteq}

\newcommand{\stnd}[1]{\mathbb{#1}}
\newcommand{\N}{\stnd{N}}         % natural numbers
\newcommand{\varN}{\omega}        % my usual preference for this
\newcommand{\Zp}{\Z_{+}}          % positive integers
\newcommand{\Z}{\stnd{Z}}         % integers
\newcommand{\Q}{\stnd{Q}}         % rationals
\newcommand{\R}{\stnd{R}}         % reals
\newcommand{\C}{\stnd{C}}         % complex numbers

\newcommand{\scr}[1]{\operatorname{s}(#1)}
\newcommand{\pred}[1]{\operatorname{pred}(#1)}

%\usepackage{layout}

\begin{document}
  \maketitle

%These notes are for Elementary Number Theory I (Math 365 at METU).

Theorems about natural numbers have been known for
thousands of years.  Some of these theorems come down to us in Euclid's
\emph{Elements} \cite{MR1932864}, for example, or Nicomachus's
\emph{Introduction to Arithmetic} \cite{Nicomachus}.  However, the
\emph{foundations} on which the proofs of these theorems are
established were apparently not worked out until more recent
centuries.   

It turns out that all theorems about the natural numbers are logical
consequences of Axiom~\ref{axiom} below.  This axiom lists five
conditions that the natural numbers meet.  Richard Dedekind published
these conditions in 1888 \cite[II, \S~71, p.~67]{MR0159773}.  In 1889,
Giuseppe Peano \cite[\S~1, p.~94]{Peano}\nocite{MR0209111} repeated
them in a more symbolic form, along with some logical
conditions, making nine conditions in all, which he called axioms.  Of
these, the five
specifically number-theoretic conditions have come to be known as
the ``Peano Axioms.''  (Note however that Dedekind and Peano
treated the first natural number as $1$, not $0$; some writers
continue to do this today.)

The foundations of number-theory are often not well understood, even today.
Some books give the impression that all theorems about natural numbers
follow from the so-called ``Well-Ordering Principle''
(Theorem~\ref{thm:wo}).  Others suggest that the possibility of definition by
recursion (Theorem~\ref{thm:rec}) can be proved by induction
(Axiom~\ref{axiom}\eqref{part:ind}) alone.  These are mistakes about
the foundations of number-theory.  They are perhaps not really mistakes about
number-theory itself; still, they are mistakes, and it is better not
to make them.  This is why I have written these notes.  

When proofs of lemmas and theorems here are not supplied, I have left
them to the reader as exercises.  

An expression like ``$f\colon A\to B$'' is to
be read as the statement ``$f$ is a function from $A$ to $B$.''  This
means $f$ is a
certain kind of subset of the Cartesian product $A\times B$, namely
a subset that, for each $a$ in $A$, has exactly one element of the form
$(a,b)$; then one writes $f(a)=b$.  Finally, $f$ can also be written
as $x\mapsto f(x)$.

  \begin{axdef}\label{axiom}
    The set of \defn{natural numbers}, denoted by $\N$, meets the
    following five conditions.
    \begin{enumerate}
      \item\label{part:zero}
There is a \defn{first}{} natural number, called $0$ (\defn{zero}{}).
\item\label{part:s}
Every $n$ in $\N$ has a unique \defn{successor}, denoted (for now) by
$\scr n$.
\item\label{part:not}
Zero is not a successor: if $n\in\N$, then
$\scr n\neq0$.
\item\label{part:inj}
Distinct natural numbers have distinct successors: if
$n,m\in\N$ and $n\neq m$, then $\scr n\neq\scr m$.
\item\label{part:ind}
Proof by \defn{induction}{} is possible: Suppose
$A\included\N$, and two conditions are met, namely
\begin{enumerate}
  \item
the \defn{base}{} condition: $0\in A$, and
\item
the \defn{inductive}{} condition: if $n\in A$ (the \defn{inductive
  hypothesis}{}), then $\scr n\in A$.
\end{enumerate}
Then $A=\N$.
    \end{enumerate}
The natural number $\scr 0$ is denoted by $1$; the number $\scr 1$, by
$2$; \&c.
   \end{axdef}

  \begin{remark}
    Parts~\eqref{part:not}, \eqref{part:inj} and~\eqref{part:ind} of
    the axiom are
    conditions concerning a set with a first element and a
    successor-operation.  For each of those conditions, there is an
    example of such a set that meets that condition, but not
    the others.  In short, the three conditions are logically
    independent. 
  \end{remark}

  \begin{lemma}
    Every natural number is either $0$ or a successor. 
  \end{lemma}

  \begin{proof}
Let $A$ be the set comprising every natural number that is either $0$
    or a successor.  In particular, $0\in A$, and if $n\in A$, then
    (since it is a successor) $\scr n\in A$.
    Therefore, by induction, $A=\N$.
  \end{proof}

  \begin{theorem}[Recursion]\label{thm:rec}
    Suppose a set $A$ has an element $b$, and $f\colon A\to A$.
    Then there is a \emph{unique} function $g$ from $\N$ to $A$ such
    that
    \begin{enumerate}
      \item
$g(0)=b$, and
\item
$g(\scr n)=f(g(n))$ for all $n$ in $\N$.
    \end{enumerate}
  \end{theorem}

  \begin{proof}
The following is only a sketch.
One must prove existence and uniqueness of~$g$.  Assuming existence,
one can prove uniqueness by induction.  To prove existence,
let $\mathcal S$ be the set of subsets $R$ of $\N\times A$ such that
\begin{enumerate}
  \item
if $(0,c)\in R$, then $c=b$;
\item
if $(\scr n,c)\in R$, then $(n,d)\in R$ for some $d$ such that $f(d)=c$.
\end{enumerate}
Then $\bigcup\mathcal S$ is the desired function $g$.
  \end{proof}

  \begin{remark}
    In its statement (though not the proof), the Recursion Theorem
    assumes only parts~\eqref{part:zero} and~\eqref{part:s} of
    Axiom~\ref{axiom}.  The other parts can be proved as consequences
    of the Theorem.  Recursion is a method of \emph{definition;}
    induction is a method of \emph{proof.}  There are sets (with first
    elements and successor-operations) that allow proof by induction,
    but not definition by recursion.  In short, induction is logically
    weaker than recursion.
  \end{remark}

  \begin{definition}[Addition]\label{def:add}
    For each $m$ in $\N$, the operation $x\mapsto m+x$ on $\N$ is the
    function $g$ guaranteed by the Recursion Theorem when $A$ is $\N$ and
    $b$ is $m$ and $f$ is $x\mapsto\scr x$.  That is, 
    \begin{align*}
      m+0&=m,\\
m+\scr n&=\scr{m+n}.
    \end{align*}
  \end{definition}

  \begin{lemma}
    For all $n$ and $m$ in $\N$,
    \begin{enumerate}
      \item
$0+n=n$;
\item
$\scr m+n=\scr{m+n}$.
    \end{enumerate}
  \end{lemma}

  \begin{theorem}\label{thm:add}
    For all $n$, $m$, and $k$ in $\N$,
    \begin{enumerate}
      \item
$\scr n=n+1$;
\item
$n+m=m+n$;
\item
$(n+m)+k=n+(m+k)$;
    \end{enumerate}
  \end{theorem}

  \begin{remark}
    It is possible to prove by induction alone that an operation of
    addition with the properties described in
    \P\P\ref{def:add}--\ref{thm:add} exists uniquely. 
  \end{remark}

  \begin{definition}[Multiplication]\label{def:mul}
    For each $m$ in $\N$, the operation $x\mapsto m\cdot x$ on $\N$ is the
    function $g$ guaranteed by the Recursion Theorem when $A$ is $\N$ and
    $b$ is $0$ and $f$ is $x\mapsto x+m$.   That is,
    \begin{align*}
      m\cdot0&=0,\\
m\cdot(n+1)&=m\cdot n+m.
    \end{align*}
  \end{definition}

  \begin{lemma}
    For all $n$ and $m$ in $\N$,
    \begin{enumerate}
      \item
$0\cdot n=0$;
\item
$(m+1)\cdot n=m\cdot n+n$.
    \end{enumerate}
  \end{lemma}

  \begin{theorem}\label{thm:mul}
    For all $n$, $m$, and $k$ in $\N$,
    \begin{enumerate}
      \item
$1\cdot n=n$;
\item
$n\cdot m=m\cdot n$;
\item
$n\cdot(m+k)=n\cdot m+n\cdot k$;
\item
$(n\cdot m)\cdot k=n\cdot (m\cdot k)$;
    \end{enumerate}
  \end{theorem}

  \begin{remark}
As with addition, so with multiplication, one can prove by induction
    alone that it exists uniquely as described in
    \P\P\ref{def:mul}--\ref{thm:mul}.  However, the next
    theorem requires also
    Axioms~\ref{axiom}\eqref{part:not}--\eqref{part:inj}.  
  \end{remark}

  \begin{theorem}[Cancellation]
    For all $n$, $m$, and $k$ in $\N$, 
    \begin{enumerate}
      \item
if $n+k=m+k$, then $n=m$;
\item
if $n+m=0$, then $n=0$ and $m=0$;
\item
if $n\cdot m=0$, then $n=0$ or $m=0$;
\item
if $n\cdot k=m\cdot k$, then $n=m$ or $k=0$.
    \end{enumerate}
  \end{theorem}

  \begin{definition}[Exponentiation]
    For each $m$ in $\N$, the operation $x\mapsto m^x$ on $\N$ is the 
    function $g$ guaranteed by the Recursion Theorem when $A$ is $\N$ and
    $b$ is $1$ and $f$ is $x\mapsto x\cdot m$.  That is,
    \begin{align*}
      m^0&=1,\\
m^{n+1}&=m^n\cdot m.
    \end{align*}
  \end{definition}

  \begin{theorem}
    For all $n$, $m$, and $k$ in $\N$,
    \begin{enumerate}
      \item
$n^1=n$;
\item
$0^n=0$, unless $n=0$;
\item
$n^{m+k}=n^m\cdot n^k$;
\item
$(n\cdot m)^k=n^k\cdot m^k$;
\item
$(n^m)^k=n^{m\cdot k}$.
    \end{enumerate}
  \end{theorem}

  \begin{remark}
    In contrast with addition and multiplication, exponentiation
    requires more than induction for its existence.
  \end{remark}

  \begin{definition}[Ordering]
If $n,m\in\N$, and $m+k=n$ for some $k$ in $\N$, then this situation
is denoted by
$m\leq n$.  
That is,
\begin{equation*}
  m\leq n\iff \exists x\;m+x=n.
\end{equation*}
If also $m\neq n$, then we write $m<n$, and we say that
$m$ is a \defn{predecessor}{} of $n$.
  \end{definition}

  \begin{theorem}
For all $n$, $m$, and $k$ in $\N$,
    \begin{enumerate}
 \item
$0\leq n$;
\item
$m\leq n$ if and only if $m+k\leq n+k$;
\item
$m\leq n$ if and only if $m\cdot(k+1)\leq n\cdot(k+1)$.     
    \end{enumerate}
  \end{theorem}

  \begin{lemma}\label{lem:<}
For all $m$ and $n$ in $\N$,
\begin{enumerate}
  \item
$m<n$ if and only if $m+1\leq n$;
\item\label{item:leq}
$m\leq n$ if and only if $m<n+1$.
\end{enumerate}
  \end{lemma}

  \begin{theorem}
        The binary relation $\leq$ is a \defn{total ordering}: for
        all $n$, $m$, and $k$ in $\N$,
	\begin{enumerate}
	  \item
$n\leq n$;
\item
if $m\leq n$ and $n\leq m$, then $n=m$;
\item
if $k\leq m$ and $m\leq n$, then $k\leq n$;
\item
either $m\leq n$ or $n\leq m$.
	\end{enumerate}
  \end{theorem}

  \begin{theorem}[Strong Induction]
    Suppose $A\included\N$, and one condition is met, namely
    \begin{itemize}
      \item
if all predecessors of $n$ belong to $A$ (the \defn{strong inductive
  hypothesis}{}), then $n\in A$.
    \end{itemize}
Then $A=\N$.
  \end{theorem}

  \begin{proof}
    Let $B$ comprise the natural numbers whose predecessors belong to
    $A$.  As~$0$ has no predecessors, they belong to $A$, so $0\in
    B$.  Suppose $n\in B$.  Then all predecessors of $n$ belong to
    $A$, so by assumption, $n\in A$.  Thus, by
    Lemma~\ref{lem:<}\eqref{item:leq}, all
    of the predecessors of $n+1$ belong to $A$, so $n+1\in B$.  By
    induction, $B=\N$.  In particular, if $n\in \N$, then $n+1\in B$,
    so $n$ (being a predecessor of $n+1$) belongs to $A$.  Thus
    $A=\N$. 
  \end{proof}

  \begin{remark}
    In general, strong induction is a proof-technique that can be used
    with some \emph{ordered} sets.  By contrast, ``ordinary''
    induction involves sets with first elements and
    successor-operations, but possibly without orderings.  Strong
    induction does not follow from ordinary induction alone; neither
    does ordinary induction follow from strong induction.
  \end{remark}

  \begin{theorem}\label{thm:wo}
    The set of natural numbers is \defn{well-ordered}{} by $\leq$: that is,
    every non-empty subset of $\N$ has a least element with respect to
    $\leq$. 
  \end{theorem}
  
  \begin{proof}
    Use strong induction.  Suppose $A$ is a subset of $\N$ with no
    least element.  We shall show $A$ is empty, that is, $\N\setminus
    A=\N$.  Let $n\in\N$.  Then $n$ is not a least element of $A$.
    This means one of two things: either $n\notin A$, or else $n\in
    A$, but also $m\in A$ for some predecessor of $n$.  Equivalently,
    if no predecessor of $n$ is in $A$, then $n\notin A$.  In other
    words, if every predecessor of $n$ is in $\N\setminus A$, then
    $n\in\N\setminus A$.  By strong induction, we are done.
  \end{proof}

  \begin{remark}
    We have now shown, in effect, that if a total order $(A,\leq)$ admits
    proof by strong recursion, then it is well-ordered.  The converse
    is also true.
  \end{remark}

  \begin{theorem}[Recursion with Parameter]
    Suppose $A$ is a set with an element $b$, and $F\colon\N\times
    A\to A$.  Then there is a \emph{unique} function $G$ from $\N$ to
    $A$ such 
    that
    \begin{enumerate}
      \item
$G(0)=b$, and
\item
$G(n+1)=F(n,G(n))$ for all $n$ in $\N$.
    \end{enumerate}
  \end{theorem}

  \begin{proof}
 %   Adjust the proof of Theorem~\ref{thm:rec}.
Let $f\colon \N\times A\to\N\times A$,
where $f(n,x)=(n+1,F(n,x))$.  By recursion, there is a unique function
$g$ from
$\N$ to $\N\times A$ such that $g(0)=(0,b)$ and $g(n+1)=f(g(n))$.  By
induction, the first entry in $g(n)$ is always $n$.  The desired
function $G$ is given by $g(n)=(n,G(n))$.  Indeed, we now have
$G(0)=b$; also, $g(n+1)=f(n,G(n))=(n+1,F(n,G(n)))$, so
$G(n+1)=F(n,G(n))$.  By induction, $G$ is unique.
  \end{proof}

  \begin{remark}
    Recursion with Parameter allows us to define the set of
    predecessors of $n$ as $\pred n$, where $x\mapsto\pred x$ is the
    function $G$ guaranteed by the Theorem when $A$ is the set of
    subsets of $\N$, and $b$ is the empty set, and $F$ is
    $(x,Y)\mapsto\{x\}\cup Y$.  Then we can write $m<n$ if $m\in\pred
    n$ and prove the foregoing theorems about the ordering.
  \end{remark}

  \begin{definition}[Factorial]
    The operation $x\mapsto x!$ on $\N$ is the function $G$ guaranteed
    by the Theorem of Recursion with Parameter when $A$ is $\N$ and
    $b$ is $1$ and $F$ is $(x,y)\mapsto(x+1)\cdot y$.  That is,
    \begin{align*}
      0!&=1,\\
(n+1)!&=(n+1)\cdot n!
    \end{align*}
  \end{definition}

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

\def\cprime{$'$}
\begin{thebibliography}{1}

\bibitem{MR0159773}
Richard Dedekind.
\newblock {\em Essays on the theory of numbers. {I}:{C}ontinuity and irrational
  numbers. {II}:{T}he nature and meaning of numbers}.
\newblock Authorized translation by Wooster Woodruff Beman. Dover Publications
  Inc., New York, 1963.

\bibitem{MR1932864}
Euclid.
\newblock {\em Euclid's {\it {E}lements}}.
\newblock Green Lion Press, Santa Fe, NM, 2002.
\newblock All thirteen books complete in one volume, the Thomas L. Heath
  translation, edited by Dana Densmore.

\bibitem{Nicomachus}
Nicomachus of~Gerasa.
\newblock {\em Introduction to Arithmetic}, volume XVI of {\em University of
  Michigan Studies, Humanistic Series}.
\newblock University of Michigan Press, Ann Arbor, 1938.
\newblock First printing, 1926.

\bibitem{Peano}
Guiseppe Peano.
\newblock The principles of arithmetic, presented by a new method.
\newblock In Jean van Heijenoort, editor, {\em From {F}rege to {G}{\"o}del}.

\bibitem{MR0209111}
Jean van Heijenoort.
\newblock {\em From {F}rege to {G}\"odel. {A} source book in mathematical
  logic, 1879--1931}.
\newblock Harvard University Press, Cambridge, Mass., 1967.

\end{thebibliography}


%\layout


\end{document}