\documentclass[a4paper,11pt,twoside,reqno]{amsart}
\title{On ``Numbers''}
\author{David Pierce}
\date{\today}
\usepackage{amssymb}
\usepackage{hfoldsty}
\usepackage{typearea}
\usepackage{parskip}
\usepackage{paralist}
\usepackage{url}
\newcommand{\stnd}[1]{\mathbb#1}
\newcommand{\N}{\stnd N}
\newcommand{\Z}{\stnd Z}
\newcommand{\Q}{\stnd Q}
\newcommand{\R}{\stnd R}
\usepackage{upgreek}
\newcommand{\vnn}{\upomega}
\newcommand{\on}{\mathbf{ON}}
\usepackage{mathrsfs} % for the following
\newcommand{\sig}{\mathscr S}
\renewcommand{\emptyset}{\varnothing}
\renewcommand{\theequation}{\fnsymbol{equation}}

\begin{document}
\maketitle
%\tableofcontents

This note is based on the paper called ``Numbers'', edition of January
12, 2010, available at
\url{http://metu.edu.tr/~dpierce/Mathematics/Numbers/}.  Writing that
paper was a way to record certain things I had noticed.  The writing
itself caused me to notice more things and put them in the paper.  Now
it is necessary to see where I have got with all of this.   

This note identifies the points of the paper, in order, that seem to
me most interesting or important.  They are not all original; some of
them appear only in footnotes of the paper; some are developed more
here than in the paper; other points could be dropped from a later
edition of the paper.  Sections here correspond to those of the
paper. 

The main point is that some mathematicians and logicians, even Peano
himself, have been confused about the 
distinction between induction and recursion on natural numbers.  In
trying to clarify these matters, I have observed that, for each
algebraic signature $\sig$, we can consider ``new'' kinds of sets,
which violate the Extension Axiom in the usual form; but with
these sets, we can build up a class $\vnn_{\sig}$ that behaves as $\vnn$
does in the ordinary universe of sets. 

In one sense, $\vnn_{\sig}$ is nothing new: it is isomorphic to the
algebra of closed terms in $\sig$.  But $\vnn_{\sig}$ is a subclass of
a class $\on_{\sig}$, which corresponds to the usual class $\on$ of
ordinals.  (In some cases of $\sig$ at least, a sort of ``generalized ordinal
arithmetic'' is possible in $\on_{\sig}$, though this will have to be
developed in a later edition of the paper.)

Because of the inconsistency of the full
Comprehension Axiom, which we have known about for over a century,
classes must be made into sets with care.  For
some reason, this care is not usually extended to the point of
establishing $\vnn$ as a class before declaring that it (or some other
model of the ``Peano axioms'') is a set.  However, this paper does not
generally require $\vnn$ to be a set. 

%\clearpage

\section*{Epigraph}

There is poetry in numbers and in their historical development.  

Regarding the historical development of numbers, one might liken the
various mistakes and infelicities (confusing induction and recursion;
the ``Comprehension Axiom''; letting succession in $\N$ be $x\mapsto
\{x\}$ rather than $x\mapsto x\cup\{x\}$) to, say, Agamemnon's
conflict with Achilles before the walls of Troy, or Romeo's not
getting Friar Laurence's letter about Juliet's faked death.  (The
analogy is strained; but after writing the paper, I read
\emph{Logicomix,} which develops an analogy between foundational
studies in mathematics and the \emph{Oresteia} of Aeschylus.) 
  
\setcounter{section}{-1}
\section{}

But also ``poetry'' in Greek means literally making; here after
studying the ``natural'' numbers I make a new kind of generalization
(not like the generalization from $\N$ to $\Z$ to $\Q$ to $\R$ to
\dots). 

This generalization arises from observing a correspondence:

\begin{compactenum}[1.]
\item
The initial natural number is like the empty set.
\item
A natural number has \textbf{one} successor, as there is \textbf{one}
kind of non-empty set. 
\item
A successor is a successor of \textbf{one} number, as a set has
\textbf{one} kind of element. 
\end{compactenum}
If we replace the natural numbers with an arbitrary free algebra, we
can obtain a corresponding set theory, in which that free algebra can
be constructed just as von Neumann constructs the natural numbers in
the usual set theory. 

\section{}

There are four properties of the natural numbers that are taught as
being equivalent, though they are not: induction, well-ordering,
strong induction, recursion. 

The confusion perhaps arises from a confusion between ``naturalistic''
and ``axiomatic'' mathematics.  [I don't know if anything like this
  distinction can be found in the literature; but it seems to be
  generally assumed that Euclid was trying to develop an axiomatic
  system, though he failed, because he overlooked some assumptions.  I
  don't think this claim is fair:] 

Euclid is naturalistic, but still, beginning students of mathematics
ought to read him as a model of how to do and present mathematics. 

Though I call Euclid's geometry ``naturalistic'', nature did not
\textbf{cause} Euclid to work out the Elements.  Herodotus traces of
the origins of geometry to land-surveying in Egypt, but this is
oversimplifying. 

Hilbert uses algebra to prove consistency of his geometry, although
one might take the existence of the Euclidean plane (or space) as
being more obvious or self-evident than the existence of an ordered
field that is closed under taking square roots. 

With set theory we can \textbf{construct} natural numbers; but since,
in our lives, counting is more fundamental than forming sets [or is
  it?], this construction tends to justify set theory more than set
theory justifies counting. 

\section{}

Although it is an excellent textbook, Spivak's Calculus makes the
errors about the properties of the natural numbers that I mentioned
above.  Logicians should take note, since Spivak is generally careful
about notational matters (such as distinguishing functions from their
values). 

\section{}

To fix terminology: \textbf{recursion} is a method of defining sets and functions; \textbf{induction} is a method of proof.

We can see the natural numbers as being defined recursively, so that they admit proofs by induction.

The definition is: $1$ is a natural number, and if $x$ is, then so is its ``successor''.  It is redundant to say ``nothing else is a natural number'', though some writers do this (just as they redundantly use ``iff'' in definitions).

Strictly, the recursive definition of the \textbf{set} of natural numbers is ``impredicative'', because it defines $\N$ in terms of a totality that contains it (namely the totality of sets that contain~$1$ and are closed under succession).

Similarly, Zermelo's proof of the Schr\"oder--Bernstein Theorem is impredicative.

But it is a good proof:
\begin{compactenum}[1.]
\item
It can be given in a ``heuristic'' fashion, though a better word, historically, than ``heuristic'' would be ``analytic'' [or now ``abductive''?].
\item
Unlike the more usual proof today, Zermelo's does not require making a recursive definion on $\N$: such a definition requires knowing more about $\N$ than that this set itself can be defined recursively.
\end{compactenum}

But let us assume for now that we can make recursive definitions on $\N$.
Skolem uses this possibility to define the properties of $\N$ and in particular its ordering.  He prefers not to define $m<n$ in terms of the existence of some $x$ such that $m+x=n$.  The recursive definition of ordering is used later in my paper.

Boole was inspired by the observation that, just as ``$P$ and $P$'' has the same truth-value---``true'' or ``false''---as $P$, so $x^2=x$ has the two solutions 1 and 0.

The ``recursive'' operations on $\N$ appearing in G\"odel's incompleteness paper are not recursively defined, individually; but the set of recursive operations is defined recursively.

\section{}

Henkin discusses the distinction between induction and recursion and observes that, unlike addition and multiplication, exponentiation on $\N$ requires more than induction to ensure its existence.

But Henkin starts his natural numbers with $0$.  If we start with $1$, we find that exponentiation on $\Z/(n)$ is well-defined just in case $n$ is $1$, $2$, $6$, $42$, or $1806$.

These numbers are the products of successive entries in the list $2$, $3$, $7$, $43$.  Each entry of this list is $1$ plus the product of the previous entries.  As Mazur points out, because we can continue this list indefinitely, we know, as Euclid does, the infinitude of the set of prime numbers.

However, Euclid does not exactly say there are ``infinitely many'' prime numbers, as if they compose a multitude that can be counted; rather, they cannot be counted.  [So Euclid does not use an Axiom of Infinity.]

Peano himself confused induction and recursion, as have other mathematicians and logicians since him; but Dedekind did not make this mistake.  [Should one conclude that being sensitive to logic does not necessarily lead to better mathematics?]

To prove that functions on $\N$ can be defined recursively, it is sufficient (as well as necessary) to assume that succession is injective, but not surjective, and that $\N$ admits proofs by induction.  This is the ``Recursion Theorem''.  There are two ways to prove this: we can obtain a recursively defined function on $\N$ as an intersection or a union---by ``cutting down'' or ``building up'', say.  But cutting down requires assuming $\N$ is a set, which one might prefer not to do.

\section{}

Dedekind claimed to \emph{prove} the existence of a ``simply infinite system'', that is, $\N$; but the consistency of the axioms for $\N$ is as self-evident as the consistency of Euclid's system (which, however, Hilbert thought should be proved).

The soundness of Zermelo's set-theory as a foundation for mathematics is more evident if, in this theory, $\N$ can be obtained as a class without assuming that it is a set.

An ``iterative structure'' (that is, an algebra in the signature $\{1,S\}$) can be said admit induction, even if the universe of the structure is a proper class.  [This would be a scheme of theorems in the formal theory.]

In setting up the formal theory, we use recursion to define formulas.  But one aim of the theory is to construct $\N$ and prove that it allows recursive definition of functions.  This is not a problem, since the theory does not strictly require there to be a \emph{set} of formulas on which functions are defined recursively.

If we try to obtain $\N$ as a \emph{union}---by ``building up'' as above---, so that $\N$ will be the closure of $\{\emptyset\}$ under $x\mapsto\{x\}$, we run into problems unless we make use of the Foundation Axiom, which was missing from Zermelo's original system.

Without the Axiom of Infinity, the ``class form'' of Foundation (strictly, an axiom scheme) is not implied by the set form (a single axiom).  [I just don't know whether this has been pointed out somewhere in the literature.]

Nothing can prevent a simply infinite system from containing an infinite descending sequence, as seen from outside.  (This happens in non-standard analysis.)

\section{}

The notion of recursion on an ordered set is often defined in rather complicated ways.  But it suffices to say $g$ is defined recursively on $(A,<)$ if there is a function $F$ such that 
\begin{equation}\label{g}
g(x)=F(\{g(y)\colon y<x\}).  
\end{equation}
[I don't know of a textbook that makes this observation, though I have not made an exhaustive search.]

On totally ordered sets, recursion is equivalent to induction and to being well-ordered; possibly this theorem has helped to perpetuate the confusion between induction and recursion on iterative structures.

The von Neumann definition of the ordinals is natural, arising as it does from letting $F$ in~\eqref{g} by the identity.  [This is my response to Poizat's claim that it takes ``a strangely warped mind'' to find the definition natural.]

From von Neumann's definition, we obtain $\vnn$ as a class.  Then the Axiom of Infinity can be expressed as, ``$\vnn$ is a set.''

Even Fraenkel \emph{et al.} seem to miss this point however, although they explicitly aim, where possible, to express the axioms for sets in such a form, as instances of the ``Comprehension Axiom''.

If an iterative structure is ordered so that $x<S(x)$, then the structure admits induction if and only if it is well-ordered and every element is $1$ or a successor.

Even if one prefers to use Zermelo's definition of $\N$, one can use the notion of well-ordering to build up this $\N$ as a class.

All of the Zermelo--Fraenkel axioms, with Choice, are consistent with axioms that, with the exception of Extension, are instances of Comprehension.

\section{}

The set $\vnn$ is used to give the general definition of a structure.  There is no need for the universe of a structure to be a set.

The Recursion Theorem can be formulated and proved for an arbitrary algebra.

In an arbitrary signature, one example of a free algebra is an algebra of strings: a ``term algebra''.  Proving that this is free is neglected in some logic texts.  

Proving that a term algebra admits induction uses the well-ordering of $\vnn$, which is the set of lengths of terms.

But we shall also obtain free algebras uniformly, without first obtaining $\vnn$, but rather defining each of them just as $\vnn$ is defined.

\section{}

One can prove directly that an arbitrary simply infinite system $\N$ (starting with $1$) is well-ordered by the relation given by
\begin{equation*}
x<y\iff \exists z\;x+z=y.
\end{equation*}
But this takes work.

Again, as von Neumann may have done in defining the ordinals, we may note that the set-theoretic universe is an iterative structure initial element $\emptyset$ and succession $x\mapsto x\cup\{x\}$.  The homomorphism from $\N$ to this universe is an embedding with image $\vnn$.

Then the isomorphism between $\N$ and $\vnn$ can be used to order the former.

Alternatively, we can define the ordering of $\N$ recursively (rather as Skolem did).  We use this definition as a paradigm for ordering an arbitrary free algebra, in an arbitrary signature $\sig$.  We get a characterization of free algebras of $\sig$ among all algebras of $\sig$.

As with $\N$, so with an arbitrary free algebra, we want to embed it in the set-theoretic universe.  To do this, we introduce a ``type'' of set for each symbol in $\sig$; each of these sets has a number of ``grades'' of elements, the grade corresponding to the ``arity'' of the type.  Then the free algebra does embed in the universe of these new sets, and the image, $\vnn_{\sig}$, is what corresponds to $\vnn$.

\section{}

But we can obtain $\vnn$, not as the image of some $\N$, but as a subclass of the class of all ordinals, so we can obtain $\vnn_{\sig}$ as a subclass of a larger class corresponding to the original class of ordinals.

\end{document}