\documentstyle[12pt,twoside,macpsfig]{article}
\input{macros-course}

\begin{document}

\handout{induction}{Weak induction, strong induction,
and the well-ordering principle}{February 8, 1994}

\bigskip

Last week in class, we stated the following theorem.
\begin{theorem}
Weak induction, strong induction, and the well-ordering principle are
equivalent.
\end{theorem}
Some confusion arose in the proof of the theorem, which we hope to
clear up with this handout.

The idea of the proof was to show the following:
\begin{eqnarray*}
\mbox{strong induction} & \implies & \mbox{weak induction}\\
\mbox{weak induction} & \implies & \mbox{well-ordering principle}\\
\mbox{well-ordering principle} & \implies & \mbox{strong induction}
\end{eqnarray*}
The meaning of ``$\implies$'' here is the usual meaning of logical
implication.  For example, the first statement says that if strong
induction is accepted as an axiom, then weak induction can be proved
as a consequent theorem.  By the transitivity of implication
(syllogism), the cycle of implications proves that any one statement
implies any other statement, and thus, that all the statements are
equivalent.  (This strategy is often useful for showing that several
statements are equivalent.)

The second and third cases were proved in class in some detail.  Some
confusion arose, however, when Professor Leiserson glibly stated that
the first case (strong induction $\implies$ weak induction) was
``trivial.''  His justification was that if a theorem can be proved
using weak induction, then it certainly can be proved using strong
induction.  A discussion ensued in which it was argued that this
justification was for the converse (weak induction $\implies$ strong
induction).

Professor Leiserson's justification is indeed correct, and what
follows is a proof that strong induction implies weak induction.
Indeed, the proof is more a lesson in logical reasoning than anything
having to do with induction or well ordering, in contrast with the
proofs of the other two cases.  The proof took the staff of
6.042J/18.062J many hours to produce and verify, and now, we are all
able to certify that it is indeed trivial. {\tt :-)}

Let us begin by stating clearly what we wish to show using logical
notation to resolve ambiguities.  In this case, we wish to show that
strong induction implies weak induction.  Thus, for any predicate $P$
defined on the natural numbers $\nat$, we must show that
\begin{eqnarray*}
& \left[ \rule{0pt}{13pt} \left( P(0) \land 
		\left( \forall n \:  P(0) \land P(1) \land \cdots \land P(n)
			\implies P(n+1) \rule{0pt}{10pt} \right) \right)
	\implies \forall n \: P(n) \right] \\
& \implies
\left[  \rule{0pt}{13pt} \left(P(0) \land 
		 \left( \forall n \: P(n) \implies P(n+1) 
						\rule{0pt}{10pt}\right)\right)
	\implies \forall n \: P(n) \right]\ .
\end{eqnarray*}
In this expression, the domain of the ``$\forall$'' is the
natural numbers~$\naturals$.

To help us reason about this rather imposing logical formula,
let us define
\[A=\left[
	\forall n \:  P(0) \land P(1) \land \cdots \land P(n) \implies P(n+1)
\rule{0pt}{10pt}\right]\]
and 
\[B=\left[\forall n \: P(n) \implies P(n+1)\rule{0pt}{10pt}\right]\ .\]
Thus, we wish to prove the validity of the formula
\[ 
\paren{ \rule{0pt}{10pt} P(0)\land A\implies \forall n\:P(n)}\implies 
\paren{ \rule{0pt}{10pt} P(0)\land B\implies \forall n\:P(n)}\ .
\]

Observe now that $B\implies A$, since $A$ has a stronger hypothesis
than $B$: if $P(n+1)$ follows from merely $P(n)$, then it follows from
the stronger (more restrictive) hypothesis $P(0) \land P(1) \land
\cdots \land P(n)$.  The rule of propositional logic that we are using
is essentially $(X \implies Z)\implies (X\land Y\implies Z)$, which
you can verify using the truth-table method.

Since $B\implies A$, we have $P(0) \land B \implies P(0) \land A$.  We
also have $P(0) \land A \implies \forall n \: P(n)$, since we are
assuming strong induction.  Using transitivity of implication, we
conclude that $P(0) \land B \implies \forall n \: P(n)$, which is the
statement of weak induction.  Thus, strong induction (together with
the rules of logic) implies weak induction.

\end{document}


