\section{Induction, Strong Induction, and Well-Ordering}

\forstudents{
\subsection{Induction vs. strong induction}

Strong induction looks like a more powerful proof method than ordinary
induction, because it allows more information to be assumed in the
inductive step\.
But it's not really stronger---anything that can be proved with strong
induction can also be proved with ordinary induction\. 
Here's an example.

Recall the proof that every natural number $\geq 2$ can be written as
product of primes (factored into primes)\.
We used strong induction, where $P(n)$ was the predicate ``$n$ can be
factored into primes''\. 
The inductive step involved writing $n+1 = a b$, and using $P(a)$ and
$P(b)$ to get factorizations for $a$ and $b$, then multiplying
them\. 

Now we'll change this to an ordinary inductive proof\.
Define a new predicate $Q(n)$ to be $\forall i, 2 \leq i \leq n$
($i$ can be factored)\.  We'll
prove $Q(n)$ by ordinary induction: \\
\\
$Q(2)$:  Same as $P(2)$, use same proof. \\
\\
$Q(n) \Rightarrow Q(n+1)$: \\
Our goal is now to show: $\forall i, 2 \leq i \leq n+1$ ($i$ can be
factored). \\
What we can assume is: $\forall i, 2 \leq i \leq n$ ($i$ can be factored). \\
\\
This means that all that needs to be shown is that $n+1$ can be factored
(the others are already assumed)\. 
And we can assume factorizations of all smaller numbers\. 
So the old strong induction step can be used to show this\. 
\\
This idea is quite general\.
We  can always convert a strong inductive proof of $\forall n \geq k
(P(n))$ to an ordinary inductive proof\. 
Just define $Q(n)$ to be $\forall i, k \leq i \leq n (P(i))$, that is,
$P(k) \wedge P(k+1) \wedge \cdots \wedge P(n)$.

\begin{description}
\item[Base case:]
Show $Q(k)$, same as $P(k)$, which has already been shown as
part of the strong induction proof. 
\item[Inductive step:]
Show $Q(n) \Rightarrow Q(n+1)$, in other words,
$P(k) \wedge P(k+1) \wedge \cdots \wedge P(n) \Rightarrow
 P(k) \wedge P(k+1) \wedge \cdots \wedge P(n) \wedge P(n+1)$. 

This really amounts to showing
$P(k) \wedge P(k+1) \wedge \cdots \wedge P(n) \Rightarrow P(n+1)$\. 
But this has already been shown in the strong induction proof.
\end{description}

Of course, any ordinary inductive proof {\bf is} a strong induction
proof has well\.  We are allowed to assume $P(1),\ldots,P(n)$ to prove
$P(n+1)$, but all we actually use is $P(n)$.

Induction and strong induction are said to be ``equivalent'' proof
rules, in that each can prove the same things (in the context of some
standard number axioms and logical deduction rules). 
}

\subsection{Well-ordering}


There is another variation of induction that is sometimes useful:
well-ordering.  The well-ordering axiom looks nothing like the
induction axiom:

\begin{axiom*}
Every nonempty subset $S \subseteq \naturals$ has a smallest element.
\end{axiom*}

The well-ordering axiom is often called the well-ordering principle\.
It may seem obvious and useless!

As for obvious, note that this axiom would be false if the set of
natural number, ${\cal N}$, were replaced by, say, the set of rational
numbers\.  The subset $S$ consisting of positive rational numbers has
no smallest element.

As for useless, it turns out the well-ordering is just as powerful as
our very best weapon, strong induction!

For example: we can prove the theorem about $3$-cycles using
well-ordering instead of induction. 

\begin{theorem}
Any tournament that contains a cycle contains a $3$-cycle.
\end{theorem}
\begin{proof}
Assume tournament $T$ contains a cycle\.
Let $n$ be the smallest cycle length (there is some smallest, by
well-ordering)\. 
$n$ must be at least $3$\.  
If it's $3$, then we're done\. 
So suppose $n \ge 4$\.  Consider a cycle with this length\.
Now consider $p_1$ and $p_3$ as before\. 
Whichever way the arrow goes, we can use it in constructing a shorter
cycle in $T$ (as we did before)\. 
This is a contradiction, since we assumed that $n$ is the smallest
cycle length\.  Since we got a contradiction to our assumption that
$n\ge 4$, we must have $n=3$ as claimed.
\end{proof}

This proof is really very similar to the other one\.  In general,
well-ordering is equivalent to induction (and strong induction), in
that they can be used to prove the same theorems.  Again the
transformation is standard\.  Given an induction proof for proposition
$P(n)$, we can build a well ordering proof as follows\.  Suppose for
the purpose of contradiction that $P(n)$ is \emph{not} true for every
$n$\.  That means it is false for some $n$\.  So consider the set of
elements $n$ for which $P(n)$ is false\.  We've just assumed this set
is nonempty\.  So by well ordering it has a smallest element, say
$k$\.  This means $P(k-1)$ is true (else $k-1$ would be in our set)\.
But in our original inductive proof for $P(n)$, we showed that $P(k-1)
\implies P(k)$\ (this is the inductive step).  So $P(k)$ must be
true\.  This is a contradiction to our choice of $k$, which shows that
our original assumption (that $P(n)$ is false for some $n$) is false.

Mathematicians like well-ordering, because it is often ``prettier''
(fewer symbols) than an induction proof\.  On the other hand, as it
often involves proof by contradiction, well ordering is easier to get
confused about.

As we mentioned above, well ordering is exactly as powerful as
induction\.  To see this, consider some predicate $P(n)$ for which we
have proven the necessary pieces of an inductive proof: $P(0)$, and
$(\forall n \in \naturals) P(n) \implies P(n+1)$\.  Without using the
induction rule, we will use well ordering to deduce that $(\forall n)
P(n)$.

We use a proof by contradiction\.  Suppose that $(\forall n )P(n)$ is
false\.  In other words, $(\exists n) \neg P(n)$.  Let $S$ be the set
\[
S= \{n \mid \neg P(n)\}.
\]
By the existence claim above, $S$ is nonempty\.  By well ordering, $S$
contains a least element, say $n_0$.  By definition of $S$, $\neg
P(n_0)$ holds.  We now consider two cases\.  If $n_0=0$, we have a
contradiction since we know $P(0)$ is true\.  On the other hand, if
$n_0 \ne 0$, consider $n_0-1$, another natural number\.  Since $n_0-1
< n_0$, we know $n_0-1 \notin S$ (since $n_0$ is the smallest element
of $S$)\.  It follows that $P(n_0-1)$ is true\.  But we know that
$P(n_0-1) \implies P(n_0)$\.  It follows that $P(n_0)$ must be true
(modus ponens)\.  So $n_0 \notin S$.  This is a contradiction\.

We have shown that either case on $n_0$ is a contradiction, so our
assumption (that $S$ is nonempty) must be false\.  We deduce $(\forall
n)P(n)$ is true.

We can also prove the opposite direction:


\begin{theorem}
Induction implies well-ordering.
\end{theorem}

\begin{proof}
We must show that every nonempty set contains a smallest element. \\
We can assume either kind of induction axiom, since they are
equivalent, so we'll use strong induction, since that gives us more power. 

Define predicate $P(n)$: 
Every set containing $n$ contains a smallest element. \\

If we prove that $P(n)$ is true for all $n$, then we have well-ordering 
since a nonempty set has to contain {\em some} least element $n$. \\


Prove this by strong induction: \\
Basis: $P(0)$: \\
If a set contains $0$, then $0$ is its smallest element. \\
Follows from basic ordering properties. \\

Inductive step: \\
Assume $(\forall k < n)P(k)$, and prove $P(n)$. \\
Consider a set containing $n$.  \\
If it contains no smaller element, then $n$ is the smallest element and
we are done.  \\
On the other hand, if it does contain a smaller element $k < n$, \\
then by the inductive hypothesis, it contains a smallest element and
again we are done. 
\end{proof}
