%%%%
\documentclass[a4paper,landscape]{article}
\special{landscape} % apparently needed for gv to display file properly
\usepackage{amsmath,amsthm,amssymb,url,amscd}
%\usepackage{mathdots}
%\usepackage{/usr/TeX/texmf-local/tex/generic/mathdots}
%\usepackage{layout}
\usepackage[polutonikogreek,english]{babel}
\usepackage[oxonia]{psgreek}
\newcommand{\Gk}[1]{\selectlanguage{polutonikogreek}#1\selectlanguage{english}}
\usepackage{bm}
\usepackage{upgreek}
\usepackage{stmaryrd}
\usepackage{hfoldsty}

\usepackage{parskip}

\usepackage[nohead]{geometry}
\addtolength{\textheight}{30pt}
\usepackage{pstricks}
%\usepackage{graphics}
%\usepackage{wrapfig}

\usepackage{verbatim}

\newcommand{\structure}[1]{\mathbf{#1}}
\newcommand{\N}{\structure N}
\newcommand{\Z}{\structure Z}
\newcommand{\R}{\structure R}
\newcommand{\Q}{\structure Q}
\newcommand{\F}{\structure F}
\newcommand{\Din}{\mathrel{\mathfrak Z}}
\newcommand{\included}{\subseteq}
\renewcommand{\land}{\mathrel{\binampersand}}
\newcommand{\lto}{\mathrel{\Rightarrow}}
\renewcommand{\leq}{\leqslant}

%\newcommand{\ngt}[1]{\lnot#1}
\newcommand{\ngt}[1]{\mathop{\sim}#1}
\newcommand{\imp}[2]{(#1\lto#2)}

\newcommand{\bijection}{\rightarrowtail\mkern-18mu\twoheadrightarrow}
\newcommand{\size}[1]{\lvert#1\rvert}

\renewcommand{\theequation}{\fnsymbol{equation}}
\renewcommand{\descriptionlabel}[1]{\hspace{\labelsep}\makebox[2cm][l]{#1}}

\newtheorem*{theorem}{Theorem}

\begin{document}
%\thispagestyle{empty}

\huge

%David 
%\textbf{Induction and recursion,} David Pierce, Bern, 2008 
INDUCTION AND RECURSION\hfill\textsc{David Pierce}\hfill Bern, 2008
\vfill

Why do we learn and teach foundations wrongly?

\vfill

According to Spivak's \emph{Calculus} (2d ed., 1980):
\begin{description}
  \item[Ch.~1] 
\textbf{Numbers} have twelve ``simple and obvious
properties''.
\item[Ch.~27\quad]  
These are the defining properties of an \textbf{ordered field.}
\item[Ch.~1\quad] 
Without ordering, one cannot prove
$1+1\neq0$: consider $\F_2$.
\item[Ch.~8\quad] $\R$ has the \textbf{least upper bound property.}
\item[Ch.~28\quad]
$\R$ is constructed from $\Q$.
\item[Ch.~2\quad]
The \textbf{natural numbers} are $1$, $2$, $3$, \dots; these compose
$\N$.  

``Basic assumptions'' about the natural
numbers are the 
  \begin{itemize}
    \item
  principle of
  \textbf{mathematical induction,} 
%$A=\N$ if $1\in A$ and
%  \begin{equation*}
%    k\in A\implies k+1\in A;
%  \end{equation*}
\item
  \textbf{well-ordering} principle, and
\item
  principle of \textbf{``complete'' induction,} namely $A=\N$ if $1\in
  A$ and   
  \begin{equation*}
\{1,\dots,k\}\included A\implies k+1\in A.
%  \forall y\; (\{z\in\N\colon 1\leq z\leq y\}\in X\lto y+1\in X).
  \end{equation*}
  \end{itemize}

%\textbf{Recursive definitions} are ``closely related to proofs by induction.''

From each ``basic assumption,'' the others can be proved.\hfill\textbf{No!}

\end{description}

%\vfill

\newpage

The ``basic assumptions'' are \emph{not} {equivalent}.  
\begin{enumerate}
  \item
Induction is about $(\N, 1, x\mapsto x+1)$.
%a set with an initial element and a successor operation.
\item
Well-ordering is about $(\N,\leq)$.
\item
``Complete'' induction (\emph{\`a la} Spivak) is about
  $(\N,\leq,1,x\mapsto x+1)$. 
\end{enumerate}
Each is logically distinguishable from the others by
appropriate models (as $\F_2$ shows the field-axioms do not imply
$1+1\neq 0$):
\begin{itemize}
  \item
Only induction works in $\Z/(2)$: the transitive closure of
$x\mapsto x+1$ is not an ordering.
\item
The proper subset $\upomega$ of $\upomega+\upomega$ is closed under $0$ and
$x\mapsto x\cup\{x\}$, but the transitive closure of the latter is a
well-ordering. 
\end{itemize}
\vfill
Induction involves quantification over all subsets of $\N$.

Why not \emph{define} $\N$ by quantification over all supersets of
$\N$?  
That is,
\begin{equation*}
  \N=\bigcap\{X\included\R\colon 1\in X\land \forall y\;(y\in X\lto
  y+1\in X)\}. 
\end{equation*}
Then induction, well-ordering, and complete induction follow from
\emph{this.} %not (just) one another.

\newpage

Dedekind gets things straight in \emph{The Nature and Meaning of
  Numbers} (1887, 1893): 
\vfill
``59.  Theorem of \textbf{complete induction.}  In order to show that
the chain $A_o$ [that is, $\bigcap\{X\colon A\included
  X\land\phi[X]\included X\}$] is part of any system $\Sigma$\dots it
is sufficient 
to show,
\setlength{\leftmargini}{1.5cm}
%\setlength{\labelsep}{0.5cm}
\begin{enumerate}
  \item[\Gk{r.}] that $A\Din\Sigma$, and\hfill{}[$A\included\Sigma$]
\item[\Gk{s.}] that the transform of every common element of $A_o$ and
  $\Sigma$ is likewise element of
  $\Sigma$.''\hfill{}[$\phi[A_o\cap\Sigma]\included\Sigma$] 
\end{enumerate}
\vfill
``71\dots the essence of a \textbf{simply infinite system} $N$ consists in the
  existence of a transformation $\phi$ of $N$ and an element $1$ which
  satisfy the following conditions 
%$\alpha$, $\beta$, $\gamma$, $\delta$:
\Gk {a, b, g, d}:
\begin{enumerate}
  \item[\Gk{a.}] $N'\Din N$.\hfill{} [$\phi[N]\included N$]
\item[\Gk{b.}]  $N=1_o$.\hfill{}[$N=\bigcap\{X\included N\colon 1\in
  X\land\phi[X]\included X\}$] 
\item[\Gk{g.}]  The element $1$ is not contained in
  $N'$.\hfill{}[$1\notin\phi[N]$] 
\item[\Gk{d.}]  The transformation $\phi$ is similar.''\hfill{}[$\phi$
  is injective] 
\end{enumerate}
\vfill
These are the \textbf{`Peano axioms'} before Peano.

\newpage
``126.  Theorem of the \textbf{definition by induction.}
If there is given a\dots transformation $\theta$ of a system $\Omega$
into itself, and besides a determinate element $\omega$ in $\Omega$,
then there exists one and only one transformation $\psi$ of the
number-series $N$, which satisfies the conditions
\begin{enumerate}\renewcommand{\theenumi}{\Roman{enumi}}
  \item
$\psi(N)\Din\Omega$\hfill{}[$\psi[N]\included\Omega$]
\item
$\psi(1)=\omega$%\hfill{}[$\psi(1)=\omega$]
\item
$\psi(n')=\theta\psi(n)$, where $n$ represents every
  number.''%\hfill{}[$\psi(n+1)=\theta(\psi(n))$] 
\end{enumerate}
\vfill
That is, from $(\N,\phi,1)$ to $(\Omega,\theta,\omega)$ there is a unique
  homomorphism.

\vfill\vfill

``130.  Remark\dots
it is worth
while to call attention to a circumstance in which [\textbf{definition
    by induction} (126)] is essentially 
distinguished from the theorem of \textbf{demonstration by induction}
[(59)], however close may seem the relation between 
the former and the latter\dots''
\vfill
In particular,
\begin{itemize}
  \item
$\Z/(2)$ allows demonstration by
induction; but 
\item
there is no homomorphism from $\Z/(2)$ into $\Z/(3)$.
\end{itemize}
%Some writers are aware of this; others\dots?
\newpage

Peano (1889) acknowledges Dedekind.

For every $a$ in $\N$, there is a successor $a+1\in \N$.  Then Peano defines
\begin{equation}\label{eqn:+}
a+(b+1)=(a+b)+1.
\end{equation}
This defines \emph{instances} of
$a+(b+1)$; assuming:
\begin{enumerate}
  \item
that $b+1$ uniquely determines $b$;
\item
that $a+b$ is already defined;
\item\label{item:not}
that $a+(b+1)$ is \emph{not} already defined.
\end{enumerate}
By induction, all $a+b$
can be defined.  But it is not immediate
that~\eqref{eqn:+} holds for all $a$ and $b$ in $\N$, because
of~\eqref{item:not}. 

Dedekind's (126) gives addition satisfying~\eqref{eqn:+} immediately.

Following Kalm\'ar, Landau (1929) shows implicitly that addition
\emph{can} be defined with induction alone.  Hence it can be defined
on finite structures: 
\vfill
\begin{center}
  \begin{pspicture}(8,2)
%\psgrid
    \psset{linewidth=0.8mm, arrowsize=2mm 2}
    \psline(0,2)(7,2)
    \psline{->}(5.5,0.5)(5.5,1.7)
    \psarc(7,0.5){1.5}{180}{450}
    \psdots(0,2)(1,2)(2,2)(5.5,2)(6.5,2)
    \uput[u](0,2.1){$1$}
    \uput[u](1,2.1){$2$}
    \uput[u](2,2.1){$3$}
    \uput[ur](3,2.1){$\cdots$}
    \uput[u](5.5,2.1){$n$}
    \uput[ur](6.5,2.1){$n+1$}
  \end{pspicture}
\end{center}

\newpage

Likewise, the recursive definition of multiplication,
\begin{equation*}
  a\times 1=a,\qquad
a\times(b+1)=a\times b+a,
\end{equation*}
is justified by induction alone.  However:

\vfill

\begin{theorem}
  The identities
\begin{equation}\label{eqn:exp}
a^1=a,\qquad
a^{b+1}=a^b\times a
\end{equation}
hold on $\Z/(n)$ if and only if $\size n\in\{0,1,2,6\}$.
\end{theorem}
\vfill

In $\Z/(6)$: 
\hfill
\begin{math}
  \begin{array}{cccccc}
n&n^2&n^3&n^4&n^5&n^6\\\hline
%1&1&1&1&1&1\\
2&4&2&4&2&4\\
3&3&3&3&3&3\\
4&4&4&4&4&4\\
5&1&5&1&5&1\\
%6&6&6&6&6&6
  \end{array}
\end{math}
\hfill\hfill\hfill
In $\Z/(3)$:
\hfill
\begin{math}
  \begin{array}{ccc|cc}
n&n^2&n^3&n^3\times n&n^4\\\hline
2&1&2&1&2
  \end{array}
\end{math}
\begin{comment}
  



Applying~\eqref{eqn:exp} in $\Z/(3)$ yields
\begin{equation*}
  2^1=1,\qquad 2^2=2^1\times2=2,\qquad 2^3=2^2\times
  2= 1;
\end{equation*}
but $2^4=2^{3+1}=2^1=1$, which is not $2^3\times 2$.



\end{comment}

\vfill

\textsc{Alexandre Borovik:} Detecting a failure
of~\eqref{eqn:exp} \emph{modulo} $pq$ gives a~$1/4$ chance of
factorizing $pq$.  See \emph{A
  Dialogue on Infinity,} 
\begin{center}
\url{http://dialinf.wordpress.com/}
\end{center}

\newpage
Mac Lane \&\ Birkhoff, \emph{Algebra} (1st ed. 1967):
\vfill
\begin{description}
\item[P.~35] \textbf{ `Peano 
Postulates'} for $(\N,0,\sigma)$:
\begin{enumerate}\renewcommand{\theenumi}{\roman{enumi}}
\renewcommand{\labelenumi}{(\theenumi)}
  \item
$\sigma$ is injective;
\item
$0\notin\sigma_*(\N)$;
\item
if $0\in U$, and $n\in U\lto\sigma(n)\in U$, then $U=\N$.
\end{enumerate}
\vfill
\item[P.~36] Natural numbers index 
iterates of an operation $f$ on a set~$X$:
\begin{equation*}
  f^0=1_X,\qquad f^{\sigma n}=f\circ f^n.
\end{equation*}
\vfill
\item[P.~38] Any two of the Postulates have a model in which
the third fails.
\vfill
\item[P.~67]  The possibility of \textbf{recursive} definitions is
 the \textbf{Peano--Lawvere Axiom} (or \textbf{Dedekind--Peano
 Axiom} in Lawvere \&\ Rosebrugh 
 2003); this is logically equivalent to
 the three `Peano Postulates'.
\end{description}
\vfill
See also Burris, \emph{Logic for Mathematics and Computer Science}
(1998).

\begin{comment}
\vfill

(As said in the abstract, and shown implicitly by Landau, explicitly
by Henkin, induction alone does justify the recursive
definitions of addition and multiplication; but it does not alone
justify exponentiation.)
\end{comment}

\newpage
A more general setting: SENTENTIAL LOGIC

\emph{Cf.}\ Thomas Forster, \emph{Logic, Induction, and Sets} (2003).
\vfill
Let $\mathcal V$ be a set $\{P,P',P'',P''',\dots\}$ of
\textbf{sentential variables.}
\vfill
Let $\mathcal S$ be the set of \textbf{sentences} generated from
$\mathcal V$ by closing under
\begin{equation*}
X\overset{N}{\longmapsto} \ngt{X}\quad\text{ and }\quad
(X,Y)\overset{C}{\longmapsto} \imp XY.
\end{equation*}
Then $\mathcal S$ admits \textbf{proof by induction,} as
\emph{e.g.}\ in
showing that parentheses come in pairs.
\vfill
Moreover, $N$ and $C$ are injective, and 
\begin{equation*}
\mathcal S =
\mathcal V+ C[\mathcal S]+ C[\mathcal S\times\mathcal S]
\end{equation*}
(disjoint union).
Therefore $\mathcal S$ admits \textbf{definition by recursion.} 

For example, \textbf{truth assignments} are so defined:   If
$\phi\colon\mathcal V\to\F_2$, we extend to all of $\mathcal S$ by
\begin{equation*}
  \phi(\ngt X)=1+\phi(X),\qquad \phi(\imp XY)=1+\phi(X)+\phi(X)\phi(Y).
\end{equation*}
\vfill

\newpage


Also \textbf{Detachment} is given recursively by
\begin{align*}
  D(X,U)      &=U, \qquad\text{ if }U\in\mathcal V,\\
  D(X,\ngt Y) &=\ngt Y,\\
  D(X,\imp YZ)&=
  \begin{cases}
    Z,      &\text{ if }X=Y,\\
    \imp YZ,&\text{ otherwise.}
  \end{cases}
\end{align*}
\vfill

Let the set $\mathcal T$ of \textbf{theorems} be the
subset of $\mathcal S$ generated by closure under $D$ of some
\textbf{axioms,} perhaps 
\begin{gather*}
\imp X{\imp YX},\\
\imp{\imp{\ngt X}{\ngt Y}}{\imp YX},\\
\imp{\imp X{\imp YZ}}{\imp{\imp XY}{\imp XZ}}.
\end{gather*}

\vfill
Then $\mathcal T$ admits proof by
induction, but not definition of functions by recursion.
\vfill
Hence the non-triviality of decision problems.

\newpage
ALGEBRAIC CHARACTERIZATIONS
\vfill
Let $\Sigma$ be a set, and $n\colon\Sigma\to\upomega$.  

\vfill

An \textbf{algebra}
with \textbf{signature} $\Sigma$ is a pair 
\begin{equation*}
(A,s\mapsto s^{\mathfrak A})
\end{equation*}
or $\mathfrak A$, where 
$A$ is a nonempty set, $s$ ranges over $\Sigma$, and $s^{\mathfrak
  A}\colon A^{n(s)}\to A$.
\vfill
The \textbf{term algebra} on $B$ with
signature $\Sigma$ is the
set of strings obtained by closing $B$ under each function
\begin{equation*}
  (t_1,\dots,t_{n(s)})\mapsto st_1\dotsb t_{n(s)}.
\end{equation*}
  Call this algebra $\operatorname{Tm}_{\Sigma}(B)$. 
\vfill
An algebra $\mathfrak A$ with signature $\Sigma$ admits 
\begin{itemize}
  \item
\textbf{proof by induction,} if 
$\mathfrak A\cong\operatorname{Tm}_{\Sigma}(\varnothing)/\mathfrak I$
for some congruence $\mathfrak I$; 
\item
\textbf{definition by recursion,} if 
$\mathfrak A\cong\operatorname{Tm}_{\Sigma}(\varnothing)$.
\end{itemize}
\vfill
Again, \url{http://dialinf.wordpress.com/}
\end{document}

\layout