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

\parskip1.5ex
\parindent0pt

\begin{document}

\handout{notes3}{Notes 3}{September 14, 1995}

\setcounter{section}{5}

What about those horses?

\section{Other Kinds of Induction}

\subsection{Strong Induction}

A variant of induction.  To prove $(\forall n \in N) P(n)$ 
\begin{itemize}
\item prove $P(1)$
\item prove $((\forall k < n)P(k))$ implies $P(n)$.
\end{itemize}

\begin{defin}
We say $a$ {\em divides} $b$ if there exists an integer $t$ such that
$a=bt$.  We write $a \mid b$.
\end{defin}
\begin{itemize}
\item $3 \mid 6$
\item $3\not |~7$
\end{itemize}

\begin{defin}
$p$ is {\em prime} if the only natural numbers dividing $p$ are $1$
and $p$.
\end{defin}

Thus, $n$ is {\em composite} if $n=ab$ for natural numbers $a,b \ne 1,n$.

\begin{theorem}
Every natural number has a prime divisor.
\end{theorem}
\begin{proof}
BASE CASE: The theorem is true for $n=2$.

INDUCTIVE STEP: Assuming the theorem true for all $2 \le k < n$,
consider the number $n$.  We proceed by cases:
\begin{enumerate}
\item $n$ is prime.  Then $n$ (a prime) divides $n$.
\item $n$ is composite.  Then $n=ab$ where $2 \le a < n$.  It follows
from the inductive hypothesis that $a$ has a prime divisor, ie that
$a=pt$ for a prime $t$.  Then $n=ptb$, meaning $p$ divides $n$.
\end{enumerate}
Since we proved the inductive step for both possible cases, we are
done.
\end{proof}

Note: we use a base case of 2.  This is fine, as long as we never
assume $n<2$.  

\subsection{Well Ordering Principle}

\begin{theorem}
Every nonempty set of natural numbers contains a least element.
\end{theorem}

Not true for integers, positive reals/rationals.

\begin{theorem}
Every natural number can be factored as a product of primes.
\end{theorem}
\begin{proof}
By well ordering.  Let $S$ be the set of all elements that cannot be
factored as a product of primes.  We assume $S \ne \emptyset$ and
derive a contradiction.  If $S$ is not empty, it has a least element
$n$ by well ordering.  If $n$ is prime, then it is a product of
primes, implying it shouldn't be in $S$.  So $n$ is composite---write
$n=ab$ where $a,b<n$.  It follows $a,b \notin S$.  In other words, $a$
can be written as a product of primes $p_1p_2\cdots p_k$ and $b$ as a
product of primes $q_1\cdots q_l$.  Therefore, $n=p_1\cdots p_k q_1
\cdots q_l$ can be written as a product of primes, contradicting the
claim that $n \in S$.  Our assumption that $S \ne \emptyset$ must
therefore false.
\end{proof}

Here's a fallacious argument: every number can be factored uniquely
into primes.  Apply the same proof as before, adding ``uniquely'' to
the inductive hypothesis.  The problem is that even if $n=ab$ and
$a,b$ have unique factorizations, it is still possible that $n=cd$ for
different $c$ and $d$, producing a different factorization of $n$.

The argument is false, but the claim is true and is known as the
fundamental theorem of arithmetic.

\begin{theorem}
(The division algorithm.)  Let $a,b$ be naturals.  $\exists! q,
0\le r < b$, such that $a=qb+r$.
\end{theorem}
\begin{proof}
To prove this theorem, we need to prove both that some $r$ exists and
that this $r$ is unique (this is typical of unique-existence proofs).
\begin{description}
\item[Existence:] We use well ordering.  Let $S=\{r \in \naturals \mid
(\exists q) a=qb+r\}.$  
\begin{itemize}
\item $S$ is nonempty since $a = 0b+a$ implies $a \in S$.  It follows
by well ordering that $S$ contains a least element $r_0$ such that
$a=q_0 b + r_0.$
\item Suppose $r_0 \ge b$.   Then $a=(q_0+1)b + (r_0-b)$, and $r_0-b
\ge 0$, implying $r_0-b \in S$, which contradicts the fact that
$r_0$ is the least element of $S$.  Thus $r_0 < b$.
\end{itemize}
\item[Uniqueness:] suppose $a=qb+r = q'b+r'$.  
Without loss of generality, suppose $r > r'$ (what we mean is, if
$r<r'$, then we can swap $(q,r)$ with $(q',r')$ to make the assumption
true).  Then $(q-q')b = (r-r')$ By assumption, $r,r' <b$.  Thus $0 \le
r-r' < b$, but $b\mid r-r'$, so $r-r' = 0$.  Thus $q-q' = 0$.
\end{description}
\end{proof}

\begin{defin}
In the theorem above, $r$ is the {\em remainder} on dividing $a$ by
$b$ and $q$ is the {\em quotient}.
\end{defin}

We actually left a hole in our proof that $\sqrt{2}$ is irrational: we
assumed that we could write a fraction in lowest terms.  Here is how
to actually prove that fact:

\begin{theorem}
Every rational number can be written in lowest terms.
\end{theorem}
\begin{proof}
Given a rational $q$, let $S=\{b \mid (\exists a) q=a/b\}$.  $S$ is
nonempty by the definition of $q$ being rational.  Therefore $S$ has a
least element $b$ and a corresponding $a$; $a/b$ is the lowest-terms
representation of $q$.
\end{proof}

\subsection{Nim}

The game of nim is defined as follows.  A bunch of sticks are placed
on the ground.  Two players take turns removing one, two, or three
sticks.  The player to remove the last stick loses.

\begin{theorem}
First player loses if the number of sticks $n$ is $4k+1$ for some $k$, and
wins otherwise.
\end{theorem}
\begin{proof}
By strong induction.  In class, I forgot to do the base case. 

BASE CASE: If $n=1$, clearly the first player loses.

INDUCTIVE STEP: Assume the theorem for $m < n$.  Suppose there are
$n$ sticks.  We work by cases.
\begin{itemize}
\item Suppose $n=4k+1$.  Then if the first player removes one stick,
the remainder is $n-1=4k+0$.  By the inductive hypothesis, the player
who plays at this point should win.  It follows that the player who
played first will lose.  Similarly, if the first player removes 2
sticks, then the remainder is $4(k-1)+3$, and he loses by the same
reasoning.  Same holds for removing $3$ sticks.  So however the first
player moves, he loses by the inductive hypothesis.  Note this is a
{\em strong} induction, since we rely on the previous three cases.
\item Suppose $n=4k+0$.  Then if we remove 3 sticks, we get $4(k-1)+1$
sticks to the second player, who loses by the inductive hypothesis.
\item The case $n=4k+2$ and $n=4k+3$ are handled the same way.
\end{itemize}
From the division algorithm, we know these are all the possible cases.
\end{proof}

\subsection{Equivalence of the three techniques}

\subsubsection{Weak implies Strong:}

In this case, we are allowed to assume weak induction.  In other words, 
for any predicate $P$, $(P(0) \wedge ((\forall n) P(n)\implies
P(n+1)))$ implies $(\forall n) P(n)$.  We want to prove that for any
predicate $Q$, if $Q(0)$ is true, and $(\forall n)((\forall k \le
n)Q(k)) \implies Q(n+1)$, then $(\forall n)Q(n)$ is true.  So let
$P(n)$ be the predicate $(\forall k \le n)Q(k)$.  If $Q(0)$ is true,
then by definition $P(0)$ is true.  Now suppose $(\forall n)((\forall
k \le n)Q(k)) \implies Q(n+1)$.  This can be rewritten as $(\forall
n)(P(n) \implies Q(n+1))$.  But certainly $P(n)\implies P(n)$.
Therefore, $(\forall n)(P(n) \implies (P(n) \wedge Q(n+1)))$.  But
$P(n)\wedge Q(n+1) \implies P(n+1)$.  Therefore, $P(n) \implies
P(n+1)$. Since $P(0)$ and $P(n)\implies P(n+1)$ hold, weak induction
tells us that $P(n)$ holds for all $n$.  But $P(n) \implies Q(n)$, so
$Q(n)$ holds for all $n$.

\subsubsection{Strong implies Well-Ordering}

We wish to prove: every nonempty set contains a least element.  We
formulate the following inductive hypothesis $P(n)$: every nonempty set
containing $n$ contains a least element.  If we prove this inductive
hypothesis, then we have proven well ordering since a nonempty set must
contain some element $n$ for which $P(n)$ implies the claim.  The base
case of the inductive step is easy: if a set of natural numbers
contains $0$ then $0$ is its least element.  Now suppose $(\forall k
\le n)P(k)$, and let us prove $P(n+1)$.  Consider a set containing
$n+1$.  If it contains no smaller element, then $n+1$ is the least
element and we are done.  If it contains a smaller element $k \le n$ then,
but the inductive hypothesis, it contains a least element and again we
are done.

\subsubsection{Well-Ordering implies Weak Induction}

Suppose $P(0)$ is true and $P(n) \implies P(n+1)$ is true.  Let
\[
S = \{n \mid \neg P(n)\}.
\]
Let us assume $S \ne \emptyset$ and derive a contradiction.
If $S$ is nonempty then, by well ordering, it contains a least element
$n$.  Clearly $n \ne 0$ since $P(0)$ is true.  Therefore $n-1$ is a
natural number not in $S$ (otherwise $n$ wouldn't be the least
element), meaning $P(n-1)$ is true. It follows from the inductive
hypothesis that $P(n)$ is true, which contradicts the claim that $n
\in S$.  We have derived a contradiction, meaning that our initial
assumption, that $S$ is nonempty, is false.  But if $S$ is empty, it
must be that $(\forall n) P(n)$ is true, which is what we wished to prove.

\end{document}
