\section{Induction versus Well Ordering}\label{versusWO}

The induction axiom looks nothing like the Well Ordering Principle, but
these two proof methods are closely related.  In fact, we can take any
Induction proof and reformat it into a Well Ordering proof.

Here's how: suppose that we have a proof by Induction with induction
hypothesis $P(n)$.  Then we start a Well Ordering proof by assuming the
set of counterexamples to $P$ is nonempty.  Then by Well Ordering there is
a smallest counterexample, $s$, that is, a smallest $s$ such that $P(s)$
is false.

Now we use the proof of $P(0)$ that was part of the Induction proof to
conclude that $s$ must be greater than 0.  Also since $s$ is the smallest
counterexample, we can conclude that $P(s-1)$ must be true.  At this point
we reuse the proof of the inductive step in the Induction proof, which
shows that since $P(s-1)$ true, then $P(s)$ is also true.  This
contradicts the assumption that $P(s)$ is false, so we have the
contradiction needed to complete the Well Ordering Proof that $P(n)$ holds
for all $n \in \naturals$.

\begin{notesproblem}
  Conversely, use Strong Induction to prove the Well Ordering Principle.
  \hint Prove that if a set of nonnegative integers contains an integer,
  $n$, then it has a smallest element.
\end{notesproblem}

\iffalse
Now check how this template is followed as we prove again
Theorem~\ref{th:sum-to-n}. 

\begin{theorem*}
For all $n\in\mathbb{N}$:\quad
$
1 + 2 + 3 + \cdots + n = n(n+1)/2
$.
\end{theorem*}

\begin{proof}
By contradiction. Assume that the theorem is
\emph{false}. Then, some nonnegative integers serve as
\emph{counterexamples} to it. Let's collect them in a set: 
$$
C =     \bigl\{\: 
        n\in\mathbb{N} 
        \:\:\mid\:\:
        1 + 2 + 3 + \cdots + n \neq \frac{n(n+1)}{2}
        \:\bigr\}.
$$
By our assumption that the theorem admits counterexamples, $C$ is a
nonempty set of nonnegative integers. So, by the Well Ordering Principle,
$C$ has a minimum element, call it~$c$. That is, $c$ is the
\emph{smallest counterexample} to the theorem.  

\noindent
Since $c$ is a counterexample ($c\in C$), we know that 
$$
        1 + 2 + 3 + \cdots + c \neq \frac{c(c+1)}{2}.
$$
Since $c$ is the smallest counterexample ($c$ minimum of $C$), we
know the theorem holds for all nonnegative integers smaller than
$c$. (Otherwise, at least one of them would also be in $C$ and would
therefore prevent $c$ from being the minimum of $C$.) [$\ast$] In
particular, the theorem is true for $c-1$. That is, 
$$
        1 + 2 + 3 + \cdots + (c-1) = \frac{(c-1)c}{2}.
$$
But then, adding $c$ to both sides we get
$$
1 + 2 + 3 + \cdots + (c-1) + c 
        = \frac{(c-1)c}{2} + c \\\qquad
        = \frac{c^2 - c + 2c}{2} \\
        = \frac{c(c+1)}{2},
$$
which means the theorem does hold for $c$, after all! That is, $c$ is
not a counterexample. But this is a contradiction. And we are done.

\noindent
Well, almost. Our argument contains a bug. Everything we said
after~[$\ast$] bases on the fact that $c-1$ actually exists. That is,
that there is indeed some nonnegative integer smaller than $c$. How do we
know that? How do we know that $c$ is not~0? Fortunately, this can be
fixed. We know $c\neq 0$ because $c$ is a counterexample whereas $0$
is not, as $0=0(0+1)/2$.
\end{proof}
\fi

Mathematicians commonly use the Well Ordering Principle because it can
lead to shorter proofs than induction.  On the other hand, well ordering
proofs typically involve proof by contradiction, so using it is not always
the best approach.  The choice of method is really a matter of style---but
style does matter.

\endinput