chap-1.2.tex

\section{Induction}
\label{Induction}

\index{induction|(}%
In the section, we consider several induction principles, i.e.,
methods for proving that every element $x$ of some set $A$ has a
property $P(x)$.

\subsection{Mathematical Induction}

We begin with the familiar principle of mathematical induction,
which is a basic result of set theory.

\index{mathematical induction}%
\index{induction!mathematical|see{mathematical induction}}%
\begin{theorem}[Principle of Mathematical Induction]
Suppose $P(n)$ is a property of a natural number $n$.
If
\begin{description}
\item[\quad(basis step)]
\begin{gather*}
P(0) \eqtxtl{and}
\end{gather*}
\item[\quad(inductive step)]
\begin{gather*}
\eqtxtr{for all}n\in\nats,
\eqtxt{if}\eqtxt{\rm(\dag)} P(n),\eqtxt{then}P(n+1),
\end{gather*}
\end{description}
then,
\begin{gather*}
\eqtxtr{for all}n\in\nats,\,P(n) .
\end{gather*}
\end{theorem}

We refer to the formula (\dag) as the \emph{inductive hypothesis}.
\index{inductive hypothesis!mathematical induction}%
\index{mathematical induction!inductive hypothesis}%
To use the principle to show that that every natural
number has property $P$, we carry out two steps.  In the basis step,
we show that $0$ has property $P$.  In the inductive step, we
assume that $n$ is a natural number with property $P$.  We then show
that $n+1$ has property $P$, without making any more assumptions about
$n$.

Next we give an example of a mathematical induction.

\begin{proposition}
\label{MathIndExamp}
For all $n\in\nats$, $3n^2 + 3n + 6$ is divisible by $6$.
\end{proposition}

\begin{proof}
We proceed by mathematical induction.

\begin{description}
\item[\quad(Basis Step)] We have that
$3\cdot 0^2 + 3\cdot 0 + 6 = 0 + 0 + 6 = 6 = 6\cdot 1$.  Thus
$3\cdot 0^2 + 3\cdot 0 + 6$ is divisible by $6$.

\item[\quad(Inductive Step)] Suppose $n\in\nats$, and assume the
inductive hypothesis: $3n^2 + 3n + 6$ is divisible by $6$.
Hence $3n^2 + 3n + 6$ = $6m$, for some $m\in\nats$.
Thus, we have that
\begin{align*}
3(n + 1)^2 + 3(n + 1) + 6
&= 3(n^2 + 2n + 1) + 3n + 3 + 6 \\
&= 3n^2 + 6n + 3 + 3n + 3 + 6 \\
&= (3n^2 + 3n + 6) + (6n + 6) \\
&= 6m + 6(n + 1) \\
&= 6(m + (n + 1)) ,
\end{align*}
showing that $3(n + 1)^2 + 3(n + 1) + 6$ is divisible by $6$.
\end{description}
\end{proof}

\begin{exercise}
Use Proposition~\ref{MathIndExamp} to prove, by mathematical induction,
that, for all $n\in\nats$, $n(n^2 + 5)$ is divisible by $6$.
\end{exercise}

\subsection{Strong Induction}

Next, we consider the principle of strong induction.

\index{strong induction}%
\index{induction!strong|see{strong induction}}%
\begin{theorem}[Principle of Strong Induction]
Suppose $P(n)$ is a property of a natural number $n$.
If
\begin{ctabbing}
for all $n\in\nats$, \\
if {\rm(\dag)} for all $m\in\nats$, if $m<n$, then $P(m)$, \\
then $P(n)$,
\end{ctabbing}
then
\begin{gather*}
\eqtxtr{for all}n\in\nats,\,P(n) .
\end{gather*}
\end{theorem}

We refer to the formula (\dag) as the \emph{inductive hypothesis}.
\index{inductive hypothesis!strong induction}%
\index{strong induction!inductive hypothesis}%
To use the principle to show that every natural number has property
$P$, we assume that $n$ is a natural number, and that
every natural number that is strictly smaller than $n$ has
property $P$.  We then show that $n$ has property $P$,
without making any more assumptions about $n$.

It turns out that we can use mathematical induction to prove the
validity of the principle of strong induction, by using a property
$Q(n)$ derived from $P(n)$.

\begin{proof}
Suppose $P(n)$ is a property, and assume
\begin{ctabbing}
(\ddag) \=\+ for all $n\in\nats$, \\
if for all $m\in\nats$, if $m<n$, then $P(m)$, \\
then $P(n)$.
\end{ctabbing}
Let the property $Q(n)$ be
\begin{center}
for all $m\in\nats$, if $m<n$, then $P(m)$.
\end{center}

First, we use mathematical induction to show that, for all
$n\in\nats$, $Q(n)$.
\begin{description}
\item[\quad(Basis Step)] We must show $Q(0)$.
Suppose $m\in\nats$ and $m<0$.  We must show
that $P(m)$.  Since $m<0$ is a contradiction,
\index{contradiction}%
we are allowed to conclude anything.  So, we conclude $P(m)$.

\item[\quad(Inductive Step)] Suppose $n\in\nats$, and assume
the inductive hypothesis: $Q(n)$.  We must show that $Q(n+1)$.
Suppose $m\in\nats$ and $m<n+1$.  We must show that
$P(m)$.  Since $m\leq n$, there are two cases to consider.
\begin{itemize}
\item Suppose $m<n$.  Because $Q(n)$, we have
that $P(m)$.

\item Suppose $m=n$.  We must show that $P(n)$.
By Property~(\ddag), it will suffice to show that
\begin{center}
for all $m\in\nats$, if $m<n$, then $P(m)$.
\end{center}
But this formula is exactly $Q(n)$, and so were are done.
\end{itemize}
\end{description}

Now, we use the result of our mathematical induction to show that, for
all $n\in\nats$, $P(n)$.  Suppose $n\in\nats$.  By our mathematical
induction, we have $Q(n)$.  By Property~(\ddag), it will suffice to show
that
\begin{center}
for all $m\in\nats$, if $m<n$, then $P(m)$.
\end{center}
But this formula is exactly $Q(n)$, and so we are done.
\end{proof}

As an example use of the principle of strong induction, we
will prove a proposition that we would normally take for granted:

\begin{proposition}
\label{NonemptyLeastProp}
Every nonempty set of natural numbers has a least element.
\end{proposition}

\begin{proof}
Let $X$ be a nonempty set of natural numbers.

We begin by using strong induction to show that, for all $n\in\nats$,
\begin{gather*}
\eqtxtr{if}n\in X,\eqtxt{then}X\eqtxtl{has a least element}.
\end{gather*}
Suppose $n\in\nats$, and assume the inductive hypothesis:
for all $m\in\nats$, if $m<n$, then
\begin{gather*}
\eqtxtr{if}m\in X,\eqtxt{then}X\eqtxtl{has a least element}.
\end{gather*}
We must show that
\begin{gather*}
\eqtxtr{if}n\in X,\eqtxt{then}X\eqtxtl{has a least element}.
\end{gather*}

Suppose $n\in X$.  It remains to show that $X$ has a least element.
If $n$ is less-than-or-equal-to every element of $X$, then we are
done.  Otherwise, there is an $m\in X$ such that $m<n$.
By the inductive hypothesis, we have that
\begin{gather*}
\eqtxtr{if}m\in X,\eqtxt{then}X\eqtxtl{has a least element}.
\end{gather*}
But $m\in X$, and thus $X$ has a least element.  This completes our
strong induction.

Now we use the result of our strong induction to prove that $X$ has a
least element.  Since $X$ is a nonempty subset of $\nats$, there is an
$n\in\nats$ such that $n\in X$.  By the result of our induction, we
can conclude that
\begin{gather*}
\eqtxtr{if}n\in X,\eqtxt{then}X\eqtxtl{has a least element}.
\end{gather*}
But $n\in X$, and thus $X$ has a least element.
\end{proof}
  
We conclude this subsection with one more proof using strong
induction.  Recall that a natural number is prime iff it
is at least $2$ and has no divisors other than $1$ and itself.

\begin{proposition}
For all $n\in\nats$,
\begin{displaymath}
\eqtxtr{if}n\geq 2,
\eqtxtr{then there are}m,l\in\nats\eqtxt{such that}n=ml\eqtxt{and}m
\eqtxtl{is prime.}
\end{displaymath}
\end{proposition}

\begin{proof}
We proceed by strong induction.  Suppose $n\in\nats$, and assume the
inductive hypothesis: for all $i\in\nats$, if $i<n$, then
\begin{displaymath}
\eqtxtr{if}i\geq 2,
\eqtxtr{then there are}m,l\in\nats\eqtxt{such that}i=ml\eqtxt{and}m
\eqtxtl{is prime.}
\end{displaymath}
We must show that
\begin{displaymath}
\eqtxtr{if}n\geq 2,
\eqtxtr{then there are}m,l\in\nats\eqtxt{such that}n=ml\eqtxt{and}m
\eqtxtl{is prime.}
\end{displaymath}
Suppose $n\geq 2$.  We must show that
\begin{displaymath}
\eqtxtr{there are}m,l\in\nats\eqtxt{such that}n=ml\eqtxt{and}m
\eqtxtl{is prime.}
\end{displaymath}
There are two cases to consider.
\begin{itemize}
\item Suppose $n$ is prime.  Then $n,1\in\nats$, $n=n1$ and $n$ is prime.

\item Suppose $n$ is not prime.  Since $n\geq 2$, it follows that $n=ij$ for
some $i,j\in\nats$ such that $1<i<n$.  Thus, by the inductive
hypothesis, we have that
\begin{displaymath}
\eqtxtr{if}i\geq 2,
\eqtxtr{then there are}m,l\in\nats\eqtxt{such that}i=ml\eqtxt{and}m
\eqtxtl{is prime.}
\end{displaymath}
But $i\geq 2$, and thus there are $m,l\in\nats$ such that
$i=ml$ and $m$ is prime.
Thus $m,lj\in\nats$, $n=ij=(ml)j=m(lj)$ and $m$ is prime.
\end{itemize}
\end{proof}

\begin{exercise}
Use strong induction to prove that, for all $n\in\nats$, if
$n\geq 1$, then there are $i,j\in\nats$ such that $n=2^i(2j + 1)$.
\end{exercise}

\subsection{Well-founded Induction}

We can also do induction over a well-founded relation.  A relation $R$
on a set $A$ is \emph{well-founded} iff every nonempty subset $X$ of
\index{relation!well-founded}%
\index{well-founded relation}%
$A$ has an $R$-minimal element, where an element $x\in X$ is
$R$-\emph{minimal in} $X$ iff
\index{relation!well-founded!minimal@$R$-eqtxt{minimal}}%
\index{well-founded relation!minimal@$R$-eqtxt{minimal}}%
there is no $y\in X$ such that $y\mathrel{R}x$.

Given a relation $R$ on a set $A$, and $x,y\in A$, we say that $y$
\emph{is a predecessor
\index{relation!well-founded!predecessor}%
\index{well-founded relation!predecessor}%
\index{predecessor}%
of} $x$ \emph{in} $R$ iff $y\mathrel{R}x$.  Thus $x\in X$ is
$R$-minimal in $X$ iff none of $x$'s predecessors in $R$ (there may
be none) are in $X$.

For example, in Proposition~\ref{NonemptyLeastProp}, we proved that
the strict total ordering $<$ on $\nats$ is well-founded.  On the other hand,
the strict total ordering $<$ on $\ints$ is \emph{not} well-founded, as $\ints$
itself lacks a $<$-minimal element.

Here's another negative example, showing that even if the underlying
set is finite, the relation need not be well-founded. Let
$A = \{0,1\}$, and $R = \{(0,1), (1,0)\}$. Then $0$ is the only
predecessor of $1$ in $R$, and $1$ is the only predecessor of $0$ in
$R$. Of the nonempty subsets of $A$, we have that $\{0\}$ and $\{1\}$
have $R$-minimal elements. But consider $A$ itself. Then $0$ is not
$R$-minimal in $A$, because $1\in A$ and $1\mathrel{R}0$. And $1$ is
not $R$-minimal in $A$, because $0\in A$ and $0\mathrel{R}1$. Hence
$R$ is not well-founded.

\index{well-founded induction}%
\index{induction!well-founded|see{well-founded induction}}%
\begin{theorem}[Principle of Well-founded Induction]
Suppose $A$ is a set, $R$ is a well-founded relation on $A$, and
$P(x)$ is a property of an element $x\in A$.
If
\begin{ctabbing}
for all $x\in A$, \\
if {\rm(\dag)} for all $y\in A$, if $y\mathrel{R}x$, then $P(y)$, \\
then $P(x)$,
\end{ctabbing}
then
\begin{gather*}
\eqtxtr{for all}x\in A,\,P(x) .
\end{gather*}
\end{theorem}

We refer to the formula (\dag) as the \emph{inductive hypothesis}.
\index{inductive hypothesis!well-founded induction}%
\index{well-founded induction!inductive hypothesis}%
When $A=\nats$ and $R={<}$, this is the same as the principle
of strong induction.  But it's much more generally applicable than
strong induction. Furthermore, the proof of this theorem isn't
by induction.

\begin{proof}
Suppose $A$ is a set, $R$ is a well-founded relation on $A$,
$P(x)$ is a property of an element $x\in A$, and
\begin{ctabbing}
(\ddag) \=\+ for all $x\in A$, \\
if for all $y\in A$, if $y\mathrel{R}x$, then $P(y)$, \\
then $P(x)$.
\end{ctabbing}
We must show that, for all $x\in A$, $P(x)$.

Suppose, toward a contradiction, that it is not the case
that, for all $x\in A$, $P(x)$.  Hence there is an $x\in A$ such
that $P(x)$ is false.
Let $X=\setof{x\in A}{P(x)\eqtxtl{is false}}$.  Thus
$x\in X$, showing that $X$ is non-empty.
Because $R$ is well-founded on $A$, it follows that there is a $z\in X$
that is $R$-minimal in $X$, i.e., such that there is no $y\in X$ such that
$y\mathrel{R}z$.

By (\ddag) and since $z\in X\sub A$, we have that
\begin{ctabbing}
if for all $y\in A$, if $y\mathrel{R}z$, then $P(y)$, \\
then $P(z)$.
\end{ctabbing}
Because $z\in X$, we have that $P(z)$ is false.
Thus, to obtain a contradiction, it will suffice to
show that
\begin{ctabbing}
for all $y\in A$, if $y\mathrel{R}z$, then $P(y)$.
\end{ctabbing}
Suppose $y\in A$, and $y\mathrel{R}z$. We must show that $P(y)$.
Because $z$ is $R$-minimal in $X$, it follows that $y\not\in X$.
Thus $P(y)$.

Because we obtained our contradiction, we have that,
for all $x\in A$, $P(x)$, as required.
\end{proof}

We conclude this subsection by considering three ways of building
well-founded relations.  The first is by taking a subset of
a well-founded relation:

\begin{proposition}
\label{WellFoundedSubset}
Suppose $R$ is a well-founded relation on a set $A$.  If $S\sub R$,
then $S$ is also a well-founded relation on $A$.
\end{proposition}

\begin{proof}
Suppose $R$ is a well-founded relation on $A$, and $S\sub R$.  Let
$X$ be a nonempty subset of $A$.  Let $x\in X$ be $R$-minimal in $X$.
Suppose, toward a contradiction, that $x$ is not $S$-minimal in $X$.
Thus there is a $y\in X$ such that $y\mathrel{S}x$.  But $S\sub R$,
and thus $y\mathrel{R}x$---contradiction.  Thus $x$ is $S$-minimal
in $X$, as required.
\end{proof}

Let the \emph{predecessor} relation $\pred_\nats$ on $\nats$ be
$\setof{(n,n+1)}{n\in\nats}$.
\index{relation!well-founded!predecessor relation}%
\index{well-founded relation!predecessor relation}%
\index{predecessor relation}%
\index{relation!well-founded!predecessor@$\pred_\nats$}%
\index{well-founded relation!predecessor@$\pred_\nats$}%
\index{predecessor@$\pred_\nats$}%
Thus, for all $n,m\in\nats$, $m\mathrel{\pred_\nats}n$ iff $m$ is
exactly one less than $n$.  Because ${\pred_\nats}\sub{<}$, and $<$ is
well-founded on $\nats$, Proposition~\ref{WellFoundedSubset} tells us
that $\pred_\nats$ is well-founded on $\nats$.  $0$ has no
predecessors in $\pred_\nats$, and, for all $n\in\nats$, $n$ is the
only predecessor of $n+1$ in $\pred_\nats$. Consequently, if a
zero/non-zero case analysis is used, a proof by well-founded induction on
$\pred_\nats$ will look like a proof by mathematical induction.

Suppose $A$ and $B$ are sets, $S$ is a relation on $B$, and $f\in
A\fun B$.  Then the \emph{inverse image of the relation} $S$
\emph{under} $f$, $f^{-1}(S)$, is the relation $R$ on $A$ defined
\index{function!inverse image of relation under}%
\index{function! inverse image of relation under@$\cdot^{-1}(\cdot)$}%
\index{ inverse image of relation under@$\cdot^{-1}(\cdot)$}%
by: for all $x,y\in A$, $x\mathrel{R}y$ iff $f\,x\mathrel{S}f\,y$.

\begin{proposition}
\label{InverseImageWellFounded}
Suppose $A$ and $B$ are sets, $S$ is a well-founded relation on $B$,
and $f\in A\fun B$.  Then $f^{-1}(S)$ is a well-founded relation on $A$.
\end{proposition}

\begin{proof}
Let $R=f^{-1}(S)$.  To see that $R$ is well-founded on $A$, suppose
$X$ is a nonempty subset of $A$.  We must show that there is an
$R$-minimal element of $X$.  Let $Y=f(X)=\setof{f\,x}{x\in X}$.
Thus $Y$ is a nonempty subset of $B$.  Because $S$ is well-founded
on $B$, it follows that there is an $S$-minimal element $y$ of $Y$.
Hence $y=f\,x$ for some $x\in X$.
Suppose, toward a contradiction, that $x$ is not $R$-minimal in $X$.
Thus there is an $x'\in X$ such that $x'\mathrel{R}x$.  Hence $f\,x'\in
Y$ and $f\,x'\mathrel{S}f\,x=y$, contradicting the $S$-minimality of
$y$ in $Y$.  Thus $x$ is $R$-minimal in $X$.
\end{proof}

For example, let $R$ be the relation on $\ints$ such that, for all
$n,m\in\ints$, $n\mathrel{R}m$ iff $|n|<|m|$ (where we're writing
$|\cdot|$ for the absolute value of an integer).  Since $<$ is
well-founded on $\nats$, Proposition~\ref{InverseImageWellFounded}
tells us that $R$ is well-founded on $\ints$.  If we do a well-founded
induction on $R$, when proving $P(n)$, for $n\in\ints$, we can make
use of $P(m)$ for any $m\in\ints$ whose absolute value is strictly
less than the absolute value of $n$.  E.g., when proving $P(-10)$, we
could make use of $P(5)$ or $P(-9)$.

If $R$ and $S$ are relations on
sets $A$ and $B$, respectively, then the \emph{lexicographic relation of}
\index{relation!well-founded!lexicographic order}%
\index{well-founded relation!lexicographic order}%
\index{relation!well-founded!lexicographic@$\cdot\lex\cdot$}%
\index{well-founded relation!lexicographic@$\cdot\lex\cdot$}%
$R$ \emph{and then} $S$, $R\lex S$, is the relation on $A\times B$ defined
by: $(x,y)\mathrel{R\lex S}(x',y')$ iff
\begin{itemize}
\item $x\mathrel{R}x'$, or

\item $x = x'$ and $y\mathrel{S}y'$.
\end{itemize}

\begin{proposition}
\label{LexWellFounded}
Suppose $R$ and $S$ are well-founded relations on sets $A$ and
$B$, respectively.  Then $R\lex S$ is a well-founded relation on
$A\times B$.  
\end{proposition}

\begin{proof}
Suppose $T$ is a nonempty subset of $A\times B$.  We must show that
there is an $R\lex S$-minimal element of $T$.  By our assumption,
$T$ is a relation from $A$ to $B$.  Because $T$ is nonempty, it
follows that $\domain\,T$ is a nonempty subset of $A$.  Since
$R$ is a well-founded relation on $A$, it follows that there
is an $R$-minimal $x\in\domain\,T$.  Let $Y=\setof{y\in B}{(x,y)\in T}$.
Because $Y$ is a nonempty subset of $B$, and
$S$ is well-founded on $B$, there exists an $S$-minimal $y\in Y$.
Thus $(x,y)\in T$.

Suppose, toward a contradiction, that
$(x,y)$ is not $R\lex S$-minimal in $T$.  Thus there are
$x'\in A$ and $y'\in B$ such that $(x',y')\in T$ and
$(x',y')\mathrel{R\lex S}(x,y)$.  Hence, there are two cases to
consider.
\begin{itemize}
\item Suppose $x'\mathrel{R}x$.  Because $x'\in\domain\,T$, this
contradicts the $R$-minimality of $x$ in $\domain\,T$.

\item Suppose $x'=x$ and $y'\mathrel{S}y$.  Thus $(x,y')=(x',y')\in T$,
so that $y'\in Y$.  But this contradicts the $S$-minimality of $y$
in $Y$.
\end{itemize}
Because we obtained a contradiction in both cases, we have
an overall contradiction.  Thus $(x,y)$ is $R\lex S$-minimal in $T$.
\end{proof}

For example, if we consider the strict total ordering $<$ on $\nats$,
then ${<}\lex{<}$ is a well-founded relation on $\nats\times\nats$.
If we do a well-founded induction on ${<}\lex{<}$, when proving that
$P((x,y))$ holds, we can use $P((x',y'))$, whenever $x'<x$ or $x=x'$
but $y'<y$.

Just as we abbreviate $A\times(B\times C)$ to $A\times B\times C$,
and abbreviate $(x,(y,z))$ to $(x,y,z)$, we abbreviate $R\lex(S\lex T)$
to $R\lex S\lex T$.
If $R$, $S$ and $T$ are well-founded relations on sets $A$, $B$ and
$C$, respectively, then $R\lex S\lex T$ is the well-founded relation
on $A\times B\times C$ such that, for all $x\in A$, $y\in B$ and $z\in
C$: $(x,y,z)\mathrel{R\lex S\lex T}(x',y',z')$ iff
\begin{itemize}
\item $x\mathrel{R}x'$, or
\item $x=x'$ and $y\mathrel{S}y'$, or
\item $x=x'$, $y=y'$ and $z\mathrel{T}z'$.
\end{itemize}
And we can do the analogous thing with four or more well-founded
relations.
\index{induction|)}%

\subsection{Notes}

A typical book on formal language theory doesn't introduce well-founded
relations and induction.  But this material, and our treatment of
well-founded recursion in the next section, will prove to be useful
in subsequent chapters.

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: "book"
%%% End: