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

\newcommand{\implies}{\Rightarrow}

\begin{document}

\handout{induction}{The equivalence of weak induction, strong induction,
and well-ordering}{February 8, 1994}

\bigskip

This handout should clear up the confusion that arose last
week in proving the equivalence of weak and strong induction.

Last week, we stated in class that 
\[
\mbox{Strong induction} \implies \mbox{Weak induction.}
\]
Although we did not say so explicitly, we meant ``$\implies$'' 
to have the usual meaning of logical implication---%
if strong induction is true, then weak induction must be true.
Equivalently, if strong induction is accepted as an axiom, 
then weak induction may be proved.
That is, strong induction is a ``stronger'' axiom
(actually, ``at least as strong'')---if a theorem
can be proved using weak induction, then certainly it can be proved 
using strong induction.
Stated in logical notation: for any predicate $P$ defined on $\nat$,
\begin{eqnarray*}
& \left[ \rule{0pt}{13pt} \left( P(0) \land 
		\left( \forall n \:  P(0) \land P(1) \land \cdots \land P(n-1)
			\implies P(n) \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-1) \implies P(n) 
						\rule{0pt}{10pt}\right)\right)
	\implies \forall n \: P(n) \right] .
\end{eqnarray*}


The question that arose was whether ``Strong $\implies$ Weak'' 
or the reverse, ``Weak $\implies$ Strong'', is ``trivial''.
(Of course, both are true since we know that in fact 
Strong and Weak are equivalent.)

The first direction, ``Strong $\implies$ Weak'', is ``trivial''.
To see this, let us abbreviate 
$A=\left[
	\forall n \:  P(0) \land P(1) \land \cdots \land P(n-1) \implies P(n)
\rule{0pt}{10pt}\right]$
and 
$B=\left[\forall n \: P(n-1) \implies P(n)\rule{0pt}{10pt}\right]$.
Clearly, $B\implies A$:  if $P(n)$ follows from merely $P(n-1)$,
then certainly it follows from the stronger hypothesis
$P(0) \land P(1) \land \cdots \land P(n-1)$.
We want to show that if $P(0) \land A \implies \forall n \: P(n)$,
then $P(0) \land B \implies \forall n \: P(n)$.
That is, if $P(0) \land A \implies \forall n \: P(n)$ and 
we know $P(0) \land B$, does it follow that $\forall n \: P(n)$?
Well, we have 
$P(0) \land B \implies P(0) \land A$,
and $ P(0) \land A \implies \forall n \: P(n)$;
we can therefore conclude that $P(0) \land B \implies \forall n \: P(n)$.

\medskip

%	\begin{quotation} \small
%	\noindent {\em A note on proof technique:}\\
To prove that weak induction, strong induction, and well-ordering are
equivalent, we show
\begin{eqnarray*}
\mbox{Strong induction} & \implies & \mbox{Weak induction,} \\
\mbox{ Weak induction} & \implies & \mbox{Well-ordering,} \\
\mbox{ and }\mbox{ Well-ordering} & \implies & \mbox{Strong induction.}
\end{eqnarray*}
By the transitivity of implication, the resulting cycle 
proves that any one statement implies any other statement and 
thus that all the statements are equivalent.
This strategy is useful in general 
for showing that several statements are equivalent.

\end{document}


