\documentclass[11pt,twoside]{article}
\usepackage{latex-macros/course}

%\newcommand{\R}{\mathop{\mbox{$R$}}\nolimits} % Is related to
\newcommand{\prq}{\rightarrow}  %prerequisite


\begin{document}
\lecturenotes{3}{Relations; Induction}

\section{Binary Relations}

\emph{Relations} are another fundamental Mathematical data type.  Equality
and ``less than'' are the most familiar examples of Mathematical
relations.  These are called \emph{binary} relations because they relate
two objects -- are the objects equal?  is the first lees than the second?
In this section of Notes we'll define some basic properties of binary
relations and then focus on \emph{partial orders}, which are a class of
binary relations of particular importance in Computer Science, with direct
applications that include task scheduling, database concurrency control,
and proving that computations terminate.

\subsection{Binary Relations and Functions}
Binary relations are far more general than equality or less-than.
Here's the official definition:
\begin{definition}\label{reldef}
A \emph{binary relation}, $R$, consists of a set, $A$, called
the \emph{domain} of $R$, a set, $B$, called the \emph{codomain} of $R$, and
a subset of $A \cross B$ called the \emph{graph} of $R$.
\end{definition}

For example, we can define an ``is teaching relation'' for Fall '05 at MIT
to have domain equal to the names of all the teaching staff (faculty,
T.A.'s, \etc) and codomain equal to all the subject numbers in the current
catalogue.  Its graph would contain pairs like
\[\begin{array}{l}
(\texttt{Albert R. Meyer}, 6.042),\\
(\texttt{Christos Kapoutsis}, 18.062),\\
(\texttt{Sonya Cates}, 6.042),\\
(\texttt{Albert R. Meyer}, 18.062),\\
(\texttt{Eric Demaine}, 6.046),\\
(\texttt{Donald Sadoway}, 3.091),\\
\qquad \vdots
\end{array}\]

Notice that Definition~\ref{reldef} is exactly the same as the definition
of a \emph{function}, except that it doesn't require the functional
condition that, for each domain element, $a$, there is \emph{at most} one
pair in the graph whose first coordinate is $a$.  So a function is a
special case of a binary relation.

A relation whose domain is $A$ and codomain is $B$ is said to be
``between $A$ and $B$'', or ``from $A$ to $B$.''  When the domain and
codomain are the same set, $A$, we simply say the relation is ``on $A$.''
It's common to use infix notation ``$a\, R\, b$'' to mean that the pair
$(a,b)$ is in the graph of $R$.

\subsection{Images and Inverse Images}

Before we go any further, it's worth introducing some notation that we'll
get a lot of mileage out of.  If $R$ is a binary relation from $A$ to $B$,
and $C$ is any set, define
\begin{eqnarray*}
CR &\eqdef & \set{b \in B \suchthat cRb \text{ for some } c \in C},\\
RC &\eqdef & \set{a \in A \suchthat aRc \text{ for some } c \in C}.
\end{eqnarray*}

The set $CR$ is called the \emph{image} of $C$ under $R$.  With this
notation, we could have defined the \emph{range} of $R$ simply as $AR$.

The set $RC$ is called the \emph{inverse image} of $C$ under $R$.  Notice
the clash with
\href{http://theory.csail.mit.edu/classes/6.042/spring06/ln2.pdf#mapping.pointwise}
{pointwise application} notation from Notes 2 when $R$ happens to be a
function: $\widehat{R}(C) = CR$, not $RC$.  Sorry about that.

\subsection{Surjective and like that}

A relation with the property that every codomain element is related to some
domain element is called a \emph{surjective} (or \emph{onto}) relation
---again, the same definition as for functions.  More concisely, a
relation, $R$, between $A$ and $B$ is surjective iff $AR=B$.  Likewise, a
relation with the property that every domain element is related to some
codomain element is called a \emph{total} relation; more concisely, $R$ is
total iff $A=RB$.


\section{Partial Orders}

The prerequisite structure among MIT subjects provides a nice illustration
of partial orders.  Here is a table indicating some of the prequisites of
subjects in the Course 6 program:
\begin{center}
\begin{tabular}{|l|l|}
\hline
Direct Prerequisites & Subject\\ \hline
18.01 & 6.042\\ \hline
 18.01 & 18.02\\ \hline
 18.01 & 18.03\\ \hline
 8.01 & 8.02\\ \hline
 6.001 & 6.034\\ \hline
 6.042 & 6.046\\ \hline
 18.03, 8.02 & 6.002\\ \hline
 6.001, 6.002 & 6.004\\ \hline
 6.001, 6.002 & 6.003\\ \hline
 6.004 & 6.033\\ \hline
 6.033 & 6.857\\ \hline
 6.046 & 6.840\\ \hline
\end{tabular}
\end{center}

Since 18.01 is a direct prerequisite for 6.042, a student must take 18.01
before 6.042.  Also, 6.042 is a direct prerequisite for 6.046, so in fact,
a student has to take \emph{both} 18.01 and 6.042 before taking 6.046.  So
18.01 is also really a prerequisite for 6.046, though an implicit or
indirect one; we'll indicate this by writing
\[
18.01 \prq 6.046.
\]

This prerequisite relation has a basic property known as
\emph{transitivity}: if subject $a$ is an indirect prerequisite of subject
$b$, and $b$ is an indirect prerequisite of subject $c$, then $a$ is also
an indirect $c$.

In this table, a longest sequence of prerequisites is
\[
18.01 \prq 18.03 \prq 6.002 \prq 6.004 \prq 6.033 \prq 6.857
\]
so a student would need at least six terms to work through this sequence
of courses.  But it would take a lot longer to complete a Course 6 major
if the direct prerequisites led to a situation\footnote{MIT's Committee on
Curricula has the responsibility of watching out for such bugs that might
creep into departmental requirements.} where two subjects turned out to be
prerequisites of \emph{each other}!  So another crucial property of the
prerequisite relation is that if $a \prq b$, then it is not the case that
$b \prq a$.  This property is called \emph{asymmetry}.

Another basic example of a partial order is the subset relation,
$\subseteq$, on sets.  In fact, we'll see that every partial order can be
represented by the subset relation.

\subsection{Axioms for Partial Orders}

\begin{definition}
A binary relation, $R$, on a set $A$ is:
\begin{itemize}

\item \emph{transitive} iff 
\[
[a\, R\, b \text{ and } b\, R\, c] \qimplies  a\, R\, c,
\]
for every $a,b,c\in A$,

\item \emph{asymmetric} iff
\[
a\, R\, b \qimplies \neg(b\, R\, a)
\]
for all $a,b\in A$,

\item a \emph{strict partial order} iff it is transitive and asymmetric.
\end{itemize}

\end{definition}

So the prerequisite relation, $\prq$, on subjects in the MIT catalogue is
a strict partial order.  More familiar examples of strict partial orders
are the relation, $<$, on real numbers, and the proper subset relation,
$\subset$, on sets.

The subset relation, $\subseteq$, on sets and $\leq$ relation on numbers
are examples of \emph{reflexive} relations in which each element is
related to itself.  Reflexive partial orders called \emph{weak}:

\begin{definition}
A binary relation, $R$, on a set $A$, is
\begin{itemize}

\item \emph{reflexive} iff $a\, R\, a$ for all $a \in A$,

\item \emph{antisymmetric}\label{antis} if
\[
a\, R\, b \qimplies \neg(b\, R\, a)
\]
for all $a \neq b \in A$,

\item a \emph{weak partial order} iff it is transitive, reflexive and
antisymmetric.

\end{itemize}
\end{definition}

Some authors define partial orders to be what we call weak partial orders,
but we'll use the phrase ``partial order' to mean either a weak or strong
one.

For weak partial orders in general, we often write an ordering-style
symbol like $\preceq$ or $\sqsubseteq$ instead of a letter symbol like
$R$.  (General relations are usually denoted by a letter like $R$ instead
of a cryptic squiggly symbol, so $\preceq$ is kind of like Prince.)
Likewise, we generally use $\prec$ or $\sqsubset$ to indicate a strict
partial order.  We also write $b \succeq a$ to mean $a \preceq b$ and $b
\succ a$ to mean $a \prec b$.

Two more examples of partial orders are worth mentioning:

\begin{example}\label{supset}
Let $A$ be some family of sets and define $a R b$ iff $a
\supset b$.  Then $R$ is a strict partial order.
\end{example}

For integers, $m,n$ we write $m \divides n$ to mean that $m$ \emph{divides}
$n$, namely, there is an integer, $k$, such that $n=km$.

\begin{example}\label{divides}
The divides relation is a weak partial order on the nonegative integers.
\end{example}

\subsection{Representing Partial Orders by Set Containment}

When a class of objects are defined by axioms, like the axioms for partial
orders, it can help to have a way to ``represent'' them explicitly by
known objects.  Partial orders can be represented by the subset relation
on a collection of sets.  Namely, if $R$ is a weak partial order on a set,
$A$, we can let each element $a \in A$ correspond to the set $R\set{a}$.
Since
\begin{equation}\label{rgb}
a\, R\, b  \qiff  R\set{a} \subseteq R\set{b}
\end{equation}
holds for all $a,b \in A$, we have completely captured the weak partial
order $R$ by the subset relation on the corresponding sets.  A similar
correspondence shows that strict partial orders can be represented by the
proper subset relation, $\subset$.

\begin{notesproblem}
Prove the iff assertion~\eqref{rgb}.
\end{notesproblem}

\begin{notesproblem}
Verify that the relations in Examples~\ref{supset} and~\ref{divides} are
partial orders.
\end{notesproblem}

\begin{definition}
A relation, $R$, on a set, $A$, is \emph{irreflexive} iff for all $a \in
A$, it is \emph{not} true that $a\, R\, a$.
\end{definition}

\begin{notesproblem}\label{tir}
Prove that a binary relation is a strict partial order iff it is
transitive and irreflexive.
\end{notesproblem}

\iffalse

\textbf{Quick exercise:}  Why doesn't divisibility define a partial order
on the integers rather than the natural numbers?
\medskip
\fi

\subsection{Total Orders}

The familiar order relations on numbers have an important additional
property: given any two numbers, one will be bigger than the other.
Partial orders with this property are said to be
\emph{total}\footnote{``Total'' is an overloaded term when talking about
partial orders: being a total order is a much stronger condition that
being a partial order that is a total relation.  For example, any weak
partial order such as $\subseteq$ is a total relation.} \emph{orders}:

\begin{definition}
Let $R$ be a binary relation on a set, $A$, and let $a, b$ be elements
of $A$.  Then $a$ and $b$ are \emph{comparable} with respect to $R$ iff
($a\, R\, b\text{ or } b\, R\, a$).  A partial order under which
every two distinct elements are comparable is called a \emph{total order}.
\end{definition}

So $<$ and $\le$ are total orders on $\reals$.  On the other hand, the
subset relation is \emph{not} total, since, for example, any two distinct
finite sets of the same size will be incomparable under $\subseteq$.  The
prerequisite relation on Course 6 required subjects is also not total
because, for example, neither 8.01 nor 6.001 is a prerequisite of the
other.

\subsection{Products of Relations}

Taking the product of two relations is a useful way to construct new
relations from old ones.

\hyperdef{def}{productrel}{The product}, $R_1 \cross R_2$, of relations
$R_1$ and $R_2$ is defined to be the relation with
\begin{eqnarray*}
\domain{R_1 \cross R_2} &\eqdef& \domain{R_1} \cross \domain{R_2},\\
\codomain{R_1 \cross R_2} &\eqdef& \codomain{R_1} \cross \codomain{R_2},\\
(a_1,a_2)\, (R_1 \cross R_2)\, (b_1,b_2) &\text{iff}& [a_1\, R_1\, b_1
\text{ and } a_2\, R_2\, b_2].
\end{eqnarray*}

\begin{example}\label{Y}
Define a relation, $Y$, on age-height pairs of being younger \emph{and}
shorter.  This is the relation on the set of pairs $(y,h)$ where $y$ is a
natural number $\le 2400$ which we interpret as an age in months, and $h$
is a natural number $\le 120$ describing height in inches.  We define $Y$
by the rule
\[
(y_1,h_1)\, Y\, (y_2,h_2) \qiff y_1 \le y_2 \land h_1 \le h_2.
\]
That is, $Y$ is the product of the $\le$-relation on ages and the
$\le$-relation on heights.
\end{example}

Products preserve several of the relational properties we have considered.
Namely, it's not hard to verify that if $R_1$ and $R_2$ are both
transitive, then so is $R_1 \cross R_2$.  The same holds for reflexivity,
irreflexivity, and antisymmetry.  This implies that if $R_1$ and $R_2$ are
both partial orders, then so is $R_1 \cross R_2$.

\iffalse
\textbf{Quick Exercise:} Verify that if \emph{either} of $R_1$ or $R_2$ is
irreflexive, then so is $R_1 \cross R_2$.
\medskip
\fi

On the other hand, the property of being a total order is not preserved.
For example, the age-height relation $Y$ is the product of two total
orders, but it is not total: the age 240 months, height 68 inches pair,
(240,68), and the pair (228,72) are incomparable under $Y$.


\subsection{Topological Sorting}

Scheduling problems are a common source of partial orders: there is a set,
$A$, of tasks and a set of constraints specifying that starting a certain
task depends on other tasks being completed beforehand.  We can picture
the constraints by drawing labelled boxes corresponding to different
tasks, with an arrow from one box to another if the first box corresponds
to a task that must be completed before starting the second one.

\begin{samepage}
\begin{example}\label{cloth}
Here is a drawing describing the order in which you could put on clothes.
The tasks are the clothes to be put on, and the arrows indicate what should be
put on directly before what.
\begin{center}\includegraphics{figures/clothes.mps}\end{center}
\end{example}
\end{samepage}

When we have a partial order of tasks to be performed, it can be useful to
have an order in which to perform all the tasks, one at a time, while
respecting the dependency constraints.  This amounts to finding a total
order that is consistent with the partial order.  This task of finding a
total ordering that is consistent with a partial order is known as
\emph{topological sorting}. \iffalse probably because the sort is based
only on the topology (shape) of the poset and not on the actual values.\fi

\begin{definition}
A \emph{topological sort} of a partial order, $\prec$, on a set, $A$, is
a total ordering, $\sqsubset$, on $A$ such that
\[
a \prec b \qimplies a \sqsubset b.
\]
\end{definition}

For example,
\[
\text{shirt} \sqsubset \text{sweater} \sqsubset \text{underwear} \sqsubset \text{leftsock}
\sqsubset \text{rightsock} \sqsubset \text{pants} \sqsubset \text{leftshoe} \sqsubset
\text{rightshoe} \sqsubset \text{belt} \sqsubset \text{jacket},
\]
is one topological sort of the partial order of dressing tasks given by
Example~\ref{cloth}; there are several other possible sorts as well.

Topological sorts for partial orders on finite sets are easy to construct
by starting from \emph{minimal} elements:
\begin{definition}
Let $\preceq$ be a partial order on a set, $A$, and let $a$ be an element
of $A$.  Then $a$ is \emph{minimal} iff no other element is $\preceq a$.
Similarly, $a$ is \emph{maximal} iff no other element is $\succeq a$.
\end{definition}

In a total order, there can only be one minimal element, but in general
there can be more than one minimal element in a partial order.  There are
four in the clothes example: leftsock, rightsock, underwear, and shirt.
To construct a total ordering for getting dressed, we pick one of these
minimal elements, say shirt.  Next we pick a minimal element among the
remaining ones.  For example, once we have removed shirt, sweater becomes
minimal.  We continue in this way removing successive minimal elements
until all elements have been picked.  The sequence of elements in the
order they were picked will be a topological sort.  This is how the
topological sort above for getting dressed was contructed.

For this method of topological sorting to work, we need to be sure there
is always a minimal element.  This is sort of obvious, but noting that an
infinite partially ordered set might have no minimal element ---consider
$<$ on the $\integers$ ---it would be good to prove that minimal
elements exist.

\begin{lemma}\label{finmin}
Every partial order on a nonempty finite set has a minimal element.

\begin{proof}
Let $R$ be a strict partial order on a set, $A$.  Define the \emph{weight}
of an element $a \in A$ to be $\card{R\set{a}}$ ---the number of elements
in the set $R\set{a}$.  Since $A$ is finite, the weights of all elements
in $A$ are nonnegative integers, so there must be an $a_0 \in A$ with
minimum size weight.

Now suppose $\card{R\set{a_0}} \neq 0$.  Then there is an element $a_1 \in
R\set{a_0}$, which implies (by transitivity of $R$) that $R\set{a_1}
\subseteq R\set{a_0}$, and hence $\card{R\set{a_1}} \leq
\card{R\set{a_0}}$.  But since $R$ is strict, $a_1 \in R\set{a_0} -
R\set{a_1}$, so in fact $\card{R\set{a_1}} < \card{R\set{a_0}}$,
contradicting the minimality of $\card{R\set{a_0}}$.

This contradiction implies that $\card{R\set{a_0}} = 0$, which means that
no element is related by $R$ to $a_0$, that is, $a_0$ is minimal.

A similar argument works in the case that $R$ is a weak partial order.

\end{proof}
\end{lemma}

So our construction shows:

\begin{theorem}\label{thm:topological}
Every partial order on a finite set has a topological sort.
\end{theorem}

There are many other ways of contructing topological sorts.  \iffalse In
fact, any topological sort of a subset of a partially ordered set can be
extended to become a topological sort of the whole set.\fi In fact, the
domain of the partial order need not be finite: we won't prove it, but
\emph{all} partial orders, even infinite ones, have topological sorts.

\subsection{Parallel Task Scheduling}

For a partial order of task dependencies, topological sorting provides a
way to execute tasks sequentially without violating the dependencies.  But
what if we have the ability to execute more than one task at the same
time?  For example, say tasks are programs, the partial order indicates
data dependence, and we have a parallel machine with lots of processors
instead of a sequential machine with only one.  How should we schedule the
tasks?  Our goal should be to minimize the total \emph{time} to complete
all the tasks.  For simplicity, let's say all the tasks take the same
amount of time and all the processors are identical.

So, given a finite partially ordered set of tasks, how long does it take
to do them all, in an optimal parallel schedule?  We can also use partial
order concepts to analyze this problem.

In the clothes example, we could do all the minimal elements first
(leftsock, rightsock, underwear, shirt), remove them and repeat.  We'd need
lots of hands, or maybe dressing servants.  We can do pants and sweater
next, and then leftshoe, rightshoe, and belt, and finally jacket.

We can't do any better, because the sequence underwear, pants, belt,
jacket must be done in that order.  A set of asks that must be done in
sequence like this is called a \emph{chain}.

\begin{definition}
A \emph{chain} in a partial order is a set of elements such that any two
elements in the set are comparable.
\end{definition}

In other words, a chain is a totally ordered subset of the elements in a
partial order.  Clearly, the parallel time must be at least the size of
any chain.  For if we used less time, then two tasks in the chain would
have to be done at the same time, violating the dependency constraints.

A largest chain is also known as a \emph{critical path}.  So we need at
least $t$ steps, where $t$ is the size of a largest chain.  Fortunately,
it is always possible to use only $t$ parallel steps.  The idea is to let
$B_1$ be all the minimal elements and schedule them first.  Then remove
all the elements in $B_1$, let $B_2$ be the elements that now become
minimal, and schedule them next, and so on.  For getting dressed, here is
a picture of the schedule obtained in this way:

\begin{center}\includegraphics{figures/clothesparallel.mps}\end{center}

\begin{theorem}\label{thm:parallel}
Let $R$ be strict partial order on a set, $A$.  If the longest chain in
$A$ is of size $t$, then there is a partition\footnote{Partitioning
a set, $A$, means ``cutting it up'' into non-overlapping, nonempty
pieces.  The pieces are called the blocks of the partition.  More
precisely, a \emph{partition} of $A$ is a set $\mathcal{B}$ whose elements
are nonempty subsets of $A$ such that
\begin{itemize}
\item if $B,B' \in \mathcal{B}$ are distinct sets, then $B \intersect B' =
 \emptyset$, and
\item $\lgunion_{B\in \mathcal{B}} B = A$.
\end{itemize}}
of $A$ into $t$ blocks,
$B_1, B_2, \dots, B_t$, such that for each block, $B_i$, all tasks that
have to precede tasks in $B_i$ are in smaller-numbered groups.  That is,
\begin{eqnarray}
RB_1 & = & \emptyset,\text{ and}\label{RA1}\\
RB_i & \subseteq & B_1 \cup B_2 \cup \cdots \cup B_{i-1},\label{RAi}
\end{eqnarray}
for $1<i\le t$.
\end{theorem}

\begin{corollary}
For $R$ and $t$ as above, it is possible to schedule all tasks in $t$
steps.
\end{corollary}

\begin{proof}
Schedule all the elements of $B_i$ at time $i$.  This satisfies the
dependency requirements, because all the tasks that any task depends on
are scheduled at preceding times.
\end{proof}

\begin{corollary}
Parallel time = Size of largest chain.
\end{corollary}

So it remains to prove Theorem~\ref{thm:parallel}:
\begin{proof}
A chain is said to \emph{begin} with its smallest element and \emph{end}
with its largest element, if any.

Construct the sets $B_i$ as follows:
\[
B_i \eqdef \set{a \in A \suchthat \mbox{the largest chain ending in $a$ is of
    size $i$}}.
\]

This gives just $t$ sets, because the largest chain is of size $t$.  Also,
each $a \in A$ belongs to exactly one $B_i$.  To complete the proof,
notice that if $a \in B_1$, then $a$ must be minimal, and since $R$ is
strict we have $RB_1 = \emptyset$ proving~\eqref{RA1}.

Now suppose $1 <i \le t$, and assume for the sake of contradiction
that~\eqref{RAi} does not hold.  That is, there is an $a \in B_i$ and $b
\in A$ such that $b\, R\, a$, and $b \notin B_1 \cup B_2 \cup \cdots \cup
B_{i-1}$.  Then by definition of the $B_j$'s, there is a chain of size $>
i-1$ ending at $b$.  Also, since $R$ is strict, $a$ is not in the chain
ending at $b$.  So we can add $a$ to the end of the chain to obtain a
chain of size $>i$ ending in $a$, contradicting the fact that that $a \in
B_i$.
\end{proof}

So with an unlimited number of processors, the time to complete all the
tasks is the size of the largest chain.  It turns out that this theorem
is good for more than parallel scheduling.  It is usually stated as
follows.

\begin{definition}
An \emph{antichain} in a partial order is a set of elements such that any
two elements in the set are incomparable.
\end{definition}

\begin{corollary}\label{cor:parallel}
If the largest chain in a partial order is of size, $t$, then the domain
can be partitioned into $t$ antichains.
\end{corollary}

\begin{proof}
Let the antichains be the sets $B_i$ defined as in the proof of Theorem
\ref{thm:parallel}.

We should verify that each $B_i$ is an antichain, namely, if $a,b$ are
distinct elements of $B_i$, then they are incomparable.  But suppose to
the contrary that there exist two elements $a,b \in B_i$ such that $a$ and
$b$ are comparable, say $a\, R\, b$.  Then, as in the proof of Theorem
\ref{thm:parallel}, by adding $b$ at the end of the chain of size $i$
ending at $a$, we obtain a chain of size $i+1$ ending at $b$,
contradicting the assumption that $b\in B_i$.
\end{proof}

\subsection{Dilworth's Lemma}

We can use the Corollary~\ref{cor:parallel} to prove a famous
result\footnote{Lemma~\ref{lem:Dilworth} also follows from a more general
result known as Dilworth's Theorem which we will not discuss.} about
partially ordered sets:

\hyperdef{rule}{Dilworth}{
\begin{lemma}[Dilworth]\label{lem:Dilworth}
For all $t$, every partially ordered set with $n$ elements must have
either a chain of size greater than $t$ or an antichain of size at least
$n / t$.
\end{lemma}
}

\begin{proof}
Assume there is no chain of size greater than $t$, that is, the largest chain is
of size $\le t$.  Then by Corollary \ref{cor:parallel}, the $n$ elements
can be partitioned into at most $t$ antichains.  Let $\ell$ be the size of
the largest antichain.  Since every element belongs to exactly one
antichain, and there are at most $t$ antichains, there can't be more than
$\ell t$ elements, namely, $\ell t \geq n$.  So there is an antichain with at
least $\ell \geq n / t$ elements.
\end{proof}

\begin{corollary}\label{cor:Dilworth}
Every partially ordered set with $n$ elements has a chain of size greater
than $\sqrt{n}$ or an antichain of size at least $\sqrt{n}$.

\begin{proof}
  Set $t = \sqrt{n}$ in Lemma~\ref{lem:Dilworth}.
\end{proof}
\end{corollary}

\begin{example}
  In the dressing partially ordered set, $n = 10$.
  Try $t = 3$.  Has a chain of size $4$.
  Try $t = 4$.  Has no chain of size $5$, but has an antichain of size 
  $4 \geq 10 / 4$.
\end{example}

\begin{example}
Suppose we have a class of 101 students.  Then using the product partial
order, $Y$, from Example~\ref{Y}, we can apply Dilworth's Lemma to
conclude that there is a chain of 11 students who get taller as they get
older, or an antichain of 11 students who get taller as they get younger,
which makes for an amusing in-class demo.
\end{example}
\iffalse

As a curious consequence of Corollary~\ref{cor:Dilworth}, we have:
\begin{corollary}\label{sqrt}
In any sequence of $n$ different numbers, there is either an increasing
subsequence of length greater than $\sqrt{n}$ or a decreasing subsequence
of length at least $\sqrt{n}$.
\end{corollary}

\begin{example}The sequence
\[
\langle 6,4,7,9,1,2,5,3,8\rangle
\]
has the decreasing sequence $\langle6,4,1\rangle$ and the increasing
sequence $\langle1,2,3,8\rangle$.
\end{example}

\begin{proof}
We can prove Corollary~\ref{sqrt} using Dilworth's Lemma; the trick is to
define the appropriate partially ordered set.  Suppose the given sequence is
\[
a_1 < a_2 < \cdots < a_n.
\]
Let the domain of the partial order be the set of pairs $(i, a_i)$ for $1
\le i \le n$, and define
\[
(i, a_i) \prec (j,a_j) \qiff  i < j \land a_i < a_j.
\]
So $\prec$ is a strict partial order because it is a restriction of the
product of the $<$ relations on $\set{1,\dots,n}$ and
$\set{a_1,\dots,a_n}$

Now given a $\prec$-chain, if we arrange the elements
so that their first coordinates are in increasing order, their second
coordinates must also be in increasing order.  That is, if we have
\[
(i_1, a_{i_1}) \prec (i_2, a_{i_2}) \prec \cdots \prec (i_k, a_{i_k}),
\]
then the $i_j$'s and the $a_{i_j}$'s both increase from left to right.
This means that a \emph{chain} corresponds to an \emph{increasing}
subsequence.

But what does an antichain correspond to?  Well, suppose $i<j$ and
$(i,a_i) $ and $(j, a_j)$ are $\prec$-incomparable; then by definition, we
must have $a_i > a_j$.  So given an antichain, if we arrange the elements
so that their first coordinates are in increasing order, their second
coordinates are in decreasing order.  That is, an
\emph{antichain}, with its elements sorted on their first coordinates,
corresponds to a \emph{decreasing} subsequence.

Corollary~\ref{sqrt} now follows immediately from Dilworth's Lemma.
\end{proof}
\fi

\textbf{Quick Exercise:} What is the size of the longest chain that is
guaranteed to exist in any partially ordered set of $n$ elements?
What about the largest antichain?

\solution{
Chain size is 1 in the ``discrete'' partial order in which every two
distinct elements are incomparable.  Antichain size is 1 if the partial
order is total.
}

\iffalse
\begin{notesproblem}
Describe a sequence consisting of the integers from 1 to 10,000 in some
order so that there is no increasing or decreasing subsequence of size
101.
\end{notesproblem}

\textbf{Not So Quick Exercise:} Devise an efficient procedure for finding
the longest increasing and the longest decreasing subsequence in any given
sequence of integers.  (There is a nice one.)
\fi

\section{Induction}

Induction is by far the most powerful and commonly-used proof technique in
Discrete Mathematics and Computer Science.  In fact, the use of induction
is a defining characteristic of \emph{discrete} ---as opposed to
\emph{continuous} ---Mathematics.

to understand how induction works, suppose there is a professor who brings
to class a bottomless bag of assorted miniature candy bars.  She offers to
share in accordance with two rules.  First, she numbers the students 0, 1,
2, 3, and so forth for convenient reference.  Now here are the two rules:

\begin{enumerate}
\item Student 0 gets candy.
\item If student $n$ gets candy, then student $n + 1$ also gets candy, for
every $n \in \naturals$.
\end{enumerate}

You can think of the second rule as a compact way of writing a whole
sequence of statements, one for each natural value of $n$:

\begin{itemize}
\item If student 0 gets candy, then student 1 also gets candy.
\item If student 1 gets candy, then student 2 also gets candy.
\item If student 2 gets candy, then student 3 also gets candy.\\
\qquad \vdots
\end{itemize}

Now suppose you are student 17.  By these rules, are you entitled to a
miniature candy bar?  Well, student 0 gets candy by the first rule.
Therefore, by the second rule, student 1 also gets candy, which means
student 2 gets candy as well, which means student 3 get candy, and so
on.  So the professor's two rules actually guarantee candy for
\textit{every} student, no matter how large the class.  You win!

This kind of reasoning is an instance of
\textbox{
\textbf{The Principle of Induction.}  Let $P(n)$ be a predicate.  If

\begin{itemize}
\item $P(0)$ is true, and
\item for all $n \in \naturals$, $P(n)$ implies $P(n+1)$,
\end{itemize}

then $P(n)$ is true for all $n \in \naturals$.
}

Here's the correspondence between the induction principle and sharing
candy bars.  Suppose that $P(n)$ is the predicate, ``student $n$ gets
candy''.  Then the professor's first rule asserts that $P(0)$ is true, and
her second rule is that for all $n \in \naturals$, $P(n)$ implies
$P(n+1)$.  Given these facts, the induction principle says that $P(n)$ is
true for all $n \in \naturals$.  In other words, everyone gets candy.

The intuitive justification for the general induction principle is the
same as for everyone getting a candy bar under the professor's two rules.
So the Principle of Induction is universally accepted as an obvious, sound
proof method.  What's not so obvious is how much mileage we get by using
it.

\section{Using Induction}

Induction often works directly in proving that some statement about
natural numbers holds for all of them.  For example, here is a classic
formula:

\begin{theorem}
\label{th:sum-to-n}
For all $n \in \naturals$,
\begin{equation}\label{hyp}
1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}
\end{equation}
\end{theorem}

The left side of equation~\eqref{hyp} represents the sum of all the
numbers from 1 to $n$.  You're supposed to guess the pattern and mentally
replace the dots ($\cdots$) with the other terms.  We could eliminate the
need for guessing by rewriting the left side with \term{summation
notation}:
\[
\sum_{i=1}^n i
\qquad \text{or} \qquad
\sum_{1 \leq i \leq n} i
\qquad \text{or} \qquad
\sum_{i \in \set{1, \dots, n}} i
\]
Each of these expressions denotes the sum of all values taken on by
the expression to the right of the sigma as the variable, $i$, ranges
from 1 to $n$.  The meaning of the sum in Theorem~\ref{th:sum-to-n} is
not so obvious in a couple of special cases:

\begin{itemize}

\item If $n = 1$, then there is only one term in the summation, and so
$1 + 2 + 3 + \cdots + n = 1$.  Don't be misled by the appearance of 2
and 3 and the suggestion that $1$ and $n$ are distinct terms!

\item If $n \leq 0$, then there are no terms at all in the summation.  By
convention, the sum in this case is 0.

\end{itemize}

The dots notation is convenient, but watch out for these special cases
where the notation is misleading!

Now let's use the induction principle to prove Theorem~\ref{th:sum-to-n}.
Suppose that we define predicate $P(n)$ to be ``$1 + 2 + 3 + \cdots + n =
n(n+1)/2$''.  Recast in terms of this predicate, the theorem claims that
$P(n)$ is true for all $n \in \naturals$.  This is great, because the
induction principle lets us reach precisely that conclusion, provided we
establish two simpler facts:

\begin{itemize}
\item $P(0)$ is true.
\item For all $n \in \naturals$, $P(n)$ implies $P(n+1)$.
\end{itemize}

So now our job is reduced to proving these two statements.  The first
is true because $P(0)$ asserts that a sum of zero terms is equal to
$0(0+1)/2 = 0$.

The second statement is more complicated.  But remember the basic plan
for proving the validity of any implication: \textit{assume} the
statement on the left and then \textit{prove} the statement on the
right.  In this case, we assume $P(n)$:
\begin{equation}\label{Pn}
1 + 2 + 3 + \cdots + n  = \frac{n(n+1)}{2}
\end{equation}
in order to prove $P(n+1)$:
\begin{equation}\label{Pn1}
1 + 2 + 3 + \cdots + n + (n+1) = \frac{(n+1)(n+2)}{2}
\end{equation}
These two equations are quite similar; in fact, adding $(n+1)$ to both
sides of equation~\eqref{Pn} and simplifying the right side gives the
equation~\eqref{Pn1}:
\begin{align*}
1 + 2 + 3 + \cdots + n + (n+1)
    & = \frac{n(n+1)}{2} + (n+1) \\
    & = \frac{(n+2)(n+1)}{2}
\end{align*}
Thus, if $P(n)$ is true, then so is $P(n+1)$.  This argument is valid
for every natural number $n$, so this establishes the second fact
required by the induction principle.  In effect, we've just proved
that $P(0)$ implies $P(1)$, $P(1)$ implies $P(2)$, $P(2)$ implies
$P(3)$, etc., all in one fell swoop.

With these two facts in hand, the induction principle says that the
predicate $P(n)$ is true for all natural $n$, so the theorem is proved.

\subsection{A Template for Induction Proofs}

The proof of Theorem~\ref{th:sum-to-n} was relatively simple, but even
the most complicated induction proof follows exactly the same
template.  There are five components:

\begin{enumerate}

\item \textbf{State that the proof uses induction.}  This immediately
conveys the overall structure of the proof, which helps the reader
understand your argument.

\item \textbf{Define an appropriate predicate $P(n)$.}  The eventual
conclusion of the induction argument will be that $P(n)$ is true for all
natural $n$.  Thus, you should define the predicate $P(n)$ so that your
theorem is equivalent to (or follows from) this conclusion.  Often the
predicate can be lifted straight from the claim, as in the example above.
The predicate $P(n)$ is called the ``induction hypothesis''.  Sometimes
the induction hypothesis will involve several variables, in which case you
should indicate which variable serves as $n$.

\item \textbf{Prove that $P(0)$ is true.}  This is usually easy, as in the
example above.  This part of the proof is called the ``base case'' or
``basis step''.  (Sometimes the base case will be $n=1$ or even some
larger number, in which case the starting value of $n$ also should be
stated.)

\item \textbf{Prove that $P(n)$ implies $P(n+1)$ for every natural
number $n$.}  This is called the ``inductive step'' or ``induction
step''.  The basic plan is always the same: assume that $P(n)$ is true
and then use this assumption to prove that $P(n+1)$ is true.  These
two statements should be fairly similar, but bridging the gap may
require some ingenuity.  Whatever argument you give must be valid for
every natural number $n$, since the goal is to prove the implications
$P(0) \rightarrow P(1)$, $P(1) \rightarrow P(2)$, $P(2) \rightarrow
P(3)$, etc. all at once.

\item \textbf{Invoke induction.}  Given these facts, the induction
principle allows you to conclude that $P(n)$ is true for all natural
$n$.  This is the logical capstone to the whole argument, but many
writers leave this step implicit.

\end{enumerate}

Explicitly labeling the \textit{base case} and \textit{inductive step} may
make your proofs clearer.

\subsection{A Clean Writeup}

The proof of Theorem~\ref{th:sum-to-n} given above is perfectly valid;
however, it contains a lot of extraneous explanation that you won't
usually see in induction proofs.  The writeup below is closer to what
you might see in print and should be prepared to produce yourself.

\begin{proof}
We use induction.  The induction hypothesis, $P(n)$, will be
equation~\eqref{hyp}.

\textbf{Base case:} $P(0)$ is true, because both sides of
equation~\eqref{hyp} equal zero when $n=0$.

\textbf{Inductive step:} Assume that $P(n)$ is true, where
$n$ is any natural number.  Then
\begin{align*}
1 + 2 + 3 + \cdots + n + (n+1)
    & = \frac{n(n+1)}{2} + (n+1) & \text{by induction hypothesis}\\
    & = \frac{(n+1)(n+2)}{2}  & \text{by simple algebra}
\end{align*}
which proves $P(n+1)$.

So it follows by induction that $P(n)$ is true for all natural $n$.
\end{proof}

Induction was helpful for \textit{proving the correctness} of this
summation formula, but not helpful for \textit{discovering} the the first
place.  We'll show you some tricks for finding such formulas a few weeks.

\subsection{Powers of Odd Numbers}

A proof in class that $\sqrt[n]{2}$ is irrational used the ``obvious'':
\begin{fact*}
The $n$th power of an odd number is odd, for all nonnegative integers, $n$.
\end{fact*}
Instead of taking this fact for granted, we can prove it by induction.
The proof will require a simple Lemma.
\begin{lemma*}
The product of two odd numbers is odd.
\end{lemma*}
To prove the Lemma, note that the odd numbers are, by definition, the
numbers of the form $2k+1$ where $k$ is an integer.  But
\[
(2k+1)(2k'+1) = 2(kk' + k + k')+1,
\]
so the product of two odd numbers also has the form of an odd number,
which proves the Lemma.

Now we will prove the Fact using the induction hypothesis
\[
P(n) \eqdef \text{if $a$ is an odd integer, then so is $a^{n}$}.
\]

The base case $P(0)$ holds because $a^{0} =1$, and 1 is odd.

For the inductive step, suppose $n\geq 0$, $a$ is an odd number and $P(n)$
holds.  So $a^n$ is an odd number.  Therefore, $a^{n+1} = a^{n}a$ is a
product of odd numbers, and by the Lemma $a^{n+1}$ is also odd.  This
proves $P(n+1)$, and we conclude by induction that $P(n)$ holds for
nonnegative integers $n$.

\iffalse
An alternative proof of Lemma~\ref{finmin} that every partial order on a
nonempty finite set has a minimal element can be based on induction.  This
time there is no $n$ mentioned, so we better find one.

We'll use the induction hypothesis
\[
P(n) \eqdef \text{a strict partial order on a set of size $n$ has a minimal
  element}.
\]

As a base case, we'll use $n=1$.  Now $P(1)$ holds because in a
one-element partial order, the element is minimal (and maximal) by
definition.

For the inductive step, assume $P(n)$ holds and consider a strict partial
order, $R$, on a set, $A$, of size $n+1$ for $n \geq 1$.  We will prove
that $A$ has a minimal element.

Now $A$ has 2 or more elements, so pick one and call it $a_0$.  If $a_0$
is a minimal element, then we are done.  Otherwise, let $A'$ be the set $A
- \set{a_0}$ and $R'$ be the relation $R$ restricted to $A'$.

Now it's easy to check that $R'$ is a strict partial order on the size $n$
set $A'$.  So by induction, there is an $R'$-minimal element, $m \in A'$.
We claim that $m$ is also a minimal element of $A$.

Now there is no element $a' \in A'$ such that $a'\,R\,m$, so to prove
$m$ is minimal in $A$,  as long as it is not true that $a_0\,R\, m$

This element $m$ will also be minimal in $A$ unless

Since $a_0$ is not minimal, there is an element $a_1 \in A'$ such that
$a_1\,R\,a_0$.

\fi

\subsection{Courtyard Tiling}

Induction served purely as a proof technique in the preceding examples.
But induction sometimes can serve as a more general reasoning tool.

MIT recently constructed the Stata Center which houses the Computer
Science and AI Laboratory.  During development, the project went further
and further over budget, and there were some radical fundraising ideas.
One rumored plan was to install a big courtyard with dimensions $2^n
\times 2^n$:

\begin{center}
\begin{picture}(100,100)(-20,-20)
\put(40,-10){\makebox(0,0){$2^n$}}
\put(-10,40){\makebox(0,0){$2^n$}}
\put(0,0){\line(1,0){80}}
\put(0,10){\line(1,0){80}}
\put(0,20){\line(1,0){80}}
\put(0,30){\line(1,0){80}}
\put(0,40){\line(1,0){80}}
\put(0,50){\line(1,0){80}}
\put(0,60){\line(1,0){80}}
\put(0,70){\line(1,0){80}}
\put(0,80){\line(1,0){80}}
\put(0,0){\line(0,1){80}}
\put(10,0){\line(0,1){80}}
\put(20,0){\line(0,1){80}}
\put(30,0){\line(0,1){80}}
\put(40,0){\line(0,1){80}}
\put(50,0){\line(0,1){80}}
\put(60,0){\line(0,1){80}}
\put(70,0){\line(0,1){80}}
\put(80,0){\line(0,1){80}}
\end{picture}
\end{center}

One of the central squares would be occupied by a statue of a wealthy
potential donor.  Let's call him ``Bill''.  (In the special case $n = 0$,
the whole courtyard consists of a single central square; otherwise, there
are four central squares.)  A complication was that the building's
unconventional architect, Frank Gehry, supposedly insisted that only
special L-shaped tiles be used:

\begin{center}
\thicklines
\begin{picture}(50,50)
\put(0,0){\line(1,0){50}}
\put(50,0){\line(0,1){50}}
\put(50,50){\line(-1,0){25}}
\put(25,50){\line(0,-1){25}}
\put(25,25){\line(-1,0){25}}
\put(0,25){\line(0,-1){25}}
\thinlines
\put(25,25){\line(1,0){25}}
\put(25,25){\line(0,-1){25}}
\end{picture}
\end{center}

A courtyard meeting these constraints exists, at least for $n = 2$:

\begin{center}
\begin{picture}(100,100)
\thicklines
\put(0,0){\line(1,0){100}}
\put(25,25){\line(1,0){50}}
\put(25,75){\line(1,0){50}}
\put(0,100){\line(1,0){100}}
\put(0,50){\line(1,0){25}}
\put(75,50){\line(1,0){25}}
\put(0,0){\line(0,1){100}}
\put(25,25){\line(0,1){50}}
\put(75,25){\line(0,1){50}}
\put(100,0){\line(0,1){100}}
\put(50,50){\line(0,1){25}}
\put(50,50){\line(1,0){25}}
\put(50,0,){\line(0,1){25}}
\put(50,75){\line(0,1){25}}
\put(62.5,62.5){\makebox(0,0){\textbf{B}}}
\end{picture}
\end{center}

For larger values of $n$, is there a way to tile a $2^n
\times 2^n$ courtyard with L-shaped tiles and a statue in the center?
Let's try to prove that this is so.

\begin{theorem}\label{bill}
For all $n \geq 0$ there exists a tiling of a $2^n \times 2^n$
courtyard with Bill in a central square.
\end{theorem}

\begin{proof}
{\em (doomed attempt)} The proof is by induction.  Let $P(n)$ be the
proposition that there exists a tiling of a $2^n \times 2^n$ courtyard
with Bill in the center.

\textbf{Base case:} $P(0)$ is true because Bill fills the whole courtyard.

\textbf{Inductive step:} Assume that there is a tiling of a
$2^n \times 2^n$ courtyard with Bill in the center for some $n \geq
0$.  We must prove that there is a way to tile a $2^{n+1} \times
2^{n+1}$ courtyard with Bill in the center \dots.
\end{proof}

Now we're in trouble!  The ability to tile a smaller courtyard with Bill
in the center isn't much help in tiling a larger courtyard with Bill in
the center.  We haven't figured out how to bridge the gap between $P(n)$
and $P(n+1)$.

So if we're going to prove Theorem~\ref{bill} by induction, we're going to
need some \emph{other} induction hypothesis than simply the statement
about $n$ that we're trying to prove.  We'll discuss doing this in class
on Wednesday.

\iffalse

When this happens, your first fallback should be to look for a
\textit{stronger} induction hypothesis; that is, one which implies
your previous hypothesis.  For example, we could make $P(n)$ the
proposition that for \textit{every} location of Bill in a $2^n \times
2^n$ courtyard, there exists a tiling of the remainder.

This advice may sound bizzare: ``If you can't prove something, try to
prove something grander!''  But for induction arguments, this makes sense.
In the inductive step, where you have to prove $P(n) \implies P(n+1)$,
you're in better shape because you can {\em assume} $P(n)$, which is now a
more powerful statement.  Let's see how this plays out in the case of
courtyard tiling.

\begin{proof}
{\em (successful attempt)} The proof is by induction.  Let $P(n)$ be
the proposition that for every location of Bill in a $2^n \times 2^n$
courtyard, there exists a tiling of the remainder.

\textbf{Base case:} $P(0)$ is true because Bill fills the
whole courtyard.

\textbf{Inductive step:} Asume that $P(n)$ is true for some
$n \geq 0$; that is, for every location of Bill in a $2^n \times 2^n$
courtyard, there exists a tiling of the remainder.  Divide the
$2^{n+1} \times 2^{n+1}$ courtyard into four quadrants, each $2^n
\times 2^n$.  One quadrant contains Bill (\textbf{B} in the diagram
below).  Place a temporary Bill (\textbf{X} in the diagram) in each of
the three central squares lying outside this quadrant:

\begin{center}
\begin{picture}(148,148)(-20,-20)
\thinlines
\put(0,0){\line(1,0){128}}
\put(0,0){\line(0,1){128}}
\put(128,128){\line(-1,0){128}}
\put(128,128){\line(0,-1){128}}
\put(64,0){\line(0,1){128}}
\put(0,64){\line(1,0){128}}
\put(56,72){\makebox(0,0){\textbf{X}}}
\put(56,56){\makebox(0,0){\textbf{X}}}
\put(72,56){\makebox(0,0){\textbf{X}}}
\put(48,80){\line(1,0){16}}
\put(48,48){\line(1,0){32}}
\put(80,48){\line(0,1){16}}
\put(48,48){\line(0,1){32}}
\put(96,96){\framebox(16,16){\textbf{B}}}
\put(32,-10){\makebox(0,0){$2^n$}}
\put(96,-10){\makebox(0,0){$2^n$}}
\put(-10,32){\makebox(0,0){$2^n$}}
\put(-10,96){\makebox(0,0){$2^n$}}
\end{picture}
\end{center}

Now we can tile each of the four quadrants by the induction
assumption.  Replacing the three temporary Bills with a single
L-shaped tile completes the job.  This proves that $P(n)$ implies
$P(n+1)$ for all $n \geq 0$.  The theorem follows as a special case.
\end{proof}

This proof has two nice properties.  First, not only does the argument
guarantee that a tiling exists, but also it gives an algorithm for
finding such a tiling.  Second, we have a stronger result: if Bill
wanted a statue on the edge of the courtyard, away from the pigeons,
we could accommodate him!

Strengthening the induction hypothesis is often a good move when an
induction proof won't go through.  But keep in mind that the stronger
assertion must actually be \textit{true}; otherwise, there isn't much
hope of constructing a valid proof!  Sometimes finding just the right
induction hypothesis requires trial, error, and insight.  For example,
mathematicians spent almost twenty years trying to prove or disprove
the conjecture that ``Every planar graph is
5-choosable''\footnote{5-choosability is a slight generalization of
5-colorability.  Although every planar graph is 4-colorable and
therefore 5-colorable, not every planar graph is 4-choosable.  If this
all sounds like nonsense, don't panic.  We'll discuss graphs,
planarity, and coloring in two weeks.}.  Then, in 1994, Carsten
Thomassen gave an induction proof simple enough to explain on a
napkin.  The key turned out to be finding an extremely clever
induction hypothesis; with that in hand, completing the argument is
easy!
\fi


\subsection{A Faulty Induction Proof}

\begin{falsethm*}
All horses are the same color.
\end{falsethm*}

Notice that no $n$ is mentioned in this assertion, so we're going to have
to reformulate it in a way that makes an $n$ explicit.  In particular,
we'll (falsely) prove that

\begin{falsethm}\label{horses}
In every set of $n \geq 1$ horses, all are the same color.
\end{falsethm}

This a statement about all integers $n \geq 1$ rather $\geq 0$, so it's
natural to use a slight variation on induction: prove $P(1)$ in the base
case and then prove that $P(n)$ implies $P(n+1)$ for all $n \geq 1$ in the
inductive step.  This is a perfectly valid variant of induction and is
{\em not} the problem with the proof below.

\begin{proof}
The proof is by induction.  The induction hypothesis, $P(n)$, will be
\begin{equation}\label{horsehyp}
\text{In every set of $n$ horses, all are the same color.}
\end{equation}

\textbf{Base case:} ($n=1$).  $P(1)$ is true, because in a set of horses
of size 1, there's only one horse, and this horse is definitely the same
color as itself.

\textbf{Inductive step:} Assume that $P(n)$ is true for some $n \geq 1$.
that is, assume that in every set of $n$ horses, all are the same color.
Now consider a set of $n+1$ horses:
%
\[
h_1,\ h_2,\ \dots,\ h_n,\ h_{n+1}
\]
%
By our assumption, the first $n$ horses are the same color:
%
\[
\underbrace{h_1,\ h_2,\ \dots,\ h_n,}_{\text{same color}}\ h_{n+1}
\]
%
Also by our assumption, the last $n$ horses are the same color:
%
\[
h_1,\ \underbrace{h_2,\ \dots,\ h_n,\ h_{n+1}}_{\text{same color}}
\]
%
So $h_1$ is the same color as the remaining horses besides $h_{n+1}$, and
likewise $h_{n+1}$ is the same color as the remaining horses besides
$h_1$.  So $h_1$ and $h_{n+1}$ are the same color.  That is, horses $h_1,
h_2, \dots, h_{n+1}$ must all be the same color, and so $P(n+1)$ is true.
Thus, $P(n)$ implies $P(n+1)$.

By the principle of induction, $P(n)$ is true for all $n \geq 1$.
\end{proof}

We've proved something false!  Is Math broken?  Should we all become
poets?

The error in this argument is in the sentence that begins, ``So $h_1$ and
$h_{n+1}$ are the same color.''  The ``$\dots$'' notation creates the
impression that there are some remaining horses besides $h_1$ and
$h_{n+1}$.  However, this is not true when $n = 1$.  In that case, the
first set is just $h_1$ and the second is $h_2$, and there are no
remaining horses besides them.  So $h_1$ and $h_2$ need not be the same
color!

This mistake knocks a critical link out of our induction argument.  We
proved $P(1)$ and we \emph{correctly} proved $P(2) \implies P(3)$, $P(3)
\implies P(4)$, etc.  But we failed to prove $P(1) \implies P(2)$, and so
everything falls apart: we can not conclude that $P(2)$, $P(3)$, etc., are
true.  And, of course, these propositions are all false; there are horses
of a different color.

Students sometimes claim that the mistake in the proof is because $P(n)$
is false for $n \geq 2$, and the proof assumes something false, namely,
$P(n)$, in order to prove $P(n+1)$.  You should think about how to explain
to such a student why this claim would get no credit on a 6.042 exam.

\section{Strong Induction}

\subsection{The Strong Induction Principle}

A useful variant of induction is called {\em strong induction}.  Strong
induction and ordinary induction are used for exactly the same thing:
proving that a predicate $P(n)$ is true for all $n \in \naturals$.

\textbox{
\textbf{Principle of Strong Induction. }  Let $P(n)$ be a predicate.  If

\begin{itemize}
\item $P(0)$ is true, and
\item for all $n \in \naturals$, $P(0)$, $P(1)$, \dots, $P(n)$
\emph{together} imply $P(n+1)$,
\end{itemize}

then $P(n)$ is true for all $n \in \naturals$.
}

The only change from the ordinary induction principle is that strong
induction allows you to assume more stuff in the inductive step of your
proof!  In an ordinary induction argument, you assume that $P(n)$ is true
and try to prove that $P(n+1)$ is also true.  In a strong induction
argument, you may assume that $P(0)$, $P(1)$, \dots, and $P(n)$ are
\textit{all} true when you go to prove $P(n+1)$.  These extra assumptions
can only make your job easier.

\subsection{Products of Primes}

As a first example, we'll use strong induction to prove one of those
familiar facts that is almost, but maybe not entirely, obvious:
\begin{lemma}\label{prim}
Every integer greater than 1 is a product of primes.
\end{lemma}
Note that, by convention, any number is considered to be a product
consisting of one term, namely itself.  In particular, every prime is
considered to be a product whose terms are all primes.

\begin{proof}

We will prove Lemma~\ref{prim} by strong induction, letting the induction
hypothesis, $P(n)$, be
\[
n+2 \text{ is a product of primes}.
\]
So Lemma~\ref{prim} will follow if we prove that $P(n)$ holds for all $n
\geq 0$.

\textbf{Base Case:} $P(0)$ is true because $0+2$ is prime, and so is a
product of primes by convention.

\textbf{Inductive step:} Suppose that $n \geq 0$ and that $i+2$ is a
product of primes for every natural number $i < n+1$.  We must show that
$P(n+1)$ holds, namely, that $n+3$ is also a product of primes.  We argue
by cases:

If $n+3$ is itself prime, then it is a product of primes by convention, so
$P(n+1)$ holds in this case.

Otherwise, $n + 3$ is not prime, which by definition means $n+3 = km$ for
some natural numbers $k,m$ such that $2 \leq k,m < n+3$.  So $k-2$ is a
natural number less than $n+1$, which means that $(k-2)+2$ is a product of
primes by induction hypothesis.  That is, $k$ is a product of primes.
Likewise, $m$ is a product of primes.  So $km = n+3$ is also a product of
primes.  Therefore, $P(n+1)$ holds in this case as well.

So $P(n+1)$ holds in any case, which completes the proof by strong
induction that $P(n)$ holds for all natural numbers, $n$.

\end{proof}

Despite the name, strong induction is actually no more powerful than
ordinary induction.  In other words, any theorem that can be proved with
strong induction could also be proved with ordinary induction (using a
slightly more complicated induction hypothesis).  But strong induction can
make some proofs a bit easier.  On the other hand, if $P(n)$ is easily
sufficient to prove $P(n+1)$, then it's better to use ordinary induction
for simplicity.

\subsection{Making Change}

The country Inductia, whose unit of currency is the Strong, has coins
worth 6S (6 Strongs), 10S and 15S.  Although the Inductians have some
trouble making small change like 11S or 29S, it turns out that they can
collect coins to make change for any number of Strongs greater than 29S.

Strong induction makes this easy to prove for $n+1 > 35$, because then
$(n+1)-6 > 29$, so by strong induction the Inductians can make change for
exactly $((n+1)-6)$S, and then they can add a 6S coin to get $(n+1)$S.  So
the only thing to do is check that they can make change for all the
amounts from 30 to 35, which is not too hard to do.

Here's a detailed writeup using the official format:

\begin{proof}

We prove the Inductians can make change for any amount greater than 29S by
strong induction.  The induction hypothesis, $P(n)$ will be:
\begin{quote}
If $n > 29$, then there is a collection of coins whose value is $n$
Strongs.
\end{quote}

Notice that $P(n)$ is an implication.  When the hypothesis of an
implication is false, we know the whole implication is true.  In this
situation, the implication is said to be \emph{vacuously} true.
So $P(n)$ will be vacuously true whenever $n \leq 29$.

We now proceed with the induction proof:

\textbf{Base case:} $P(0)$ is vacuously true.

\textbf{Inductive step:}  We assume $P(i)$ holds for all $i \leq n$, and
prove that $P(n+1)$ holds.  We argue by cases:

\textbf{Case} ($n+1 \leq 29$): $P(n+1)$ is vacuously true in this case.

\textbf{Case} ($n+1$ = 30): $P(30)$ holds because the Inductians can use
five 6S coins.

\textbf{Case} ($n+1$ = 31):  Use a 6S coin, a 10S coin and a 15S coin.

\textbf{Case} ($n+1$ = 32): Use two 6S coins, and two 10S coins.

\textbf{Case} ($n+1$ = 33):   Use three 6S coin, and a 15S coin.

\textbf{Case} ($n+1$ = 34): Use a four 6S coins, and a 10S coin.

\textbf{Case} ($n+1$ = 35): Use a two 10S coins and a 15S coin.

\textbf{Case} ($n+1 > 35$): Then $n \geq (n+1) -6 > 29$, so by the strong
induction hypothesis, the Inductians can make change for $((n+1)-6)$S.
Now by adding a 6S coin, they can make change for $(n+1)$S.

So in any case, $P(n+1)$ is true, and we conclude by strong induction that
for all $n > 29$, the Inductians can make change for $n$S.

\end{proof}


\subsection{Unstacking}

In class on Friday, you will see strong induction used to analyze the
properties of a simple game involving stacks of blocks.

\iffalse
Here is another exciting 6.042 game that's surely about to sweep the
nation!

You begin with a stack of $n$ boxes.  Then you make a sequence of
moves.  In each move, you divide one stack of boxes into two nonempty
stacks.  The game ends when you have $n$ stacks, each containing a
single box.  You earn points for each move; in particular, if you
divide one stack of height $a + b$ into two stacks with heights $a$
and $b$, then you score $ab$ points for that move.  Your overall score
is the sum of the points that you earn for each move.  What strategy
should you use to maximize your total score?

As an example, suppose that we begin with a stack of $n = 10$ boxes.
Then the game might proceed as follows:
%
\[
\begin{array}{cccccccccccl}
\multicolumn{10}{c}{\textbf{Stack Heights}} & \quad & \textbf{Score} \\
\underline{10}&&&&&&&&& && \\
5&\underline{5}&&&&&&&& && 25 \text{ points} \\
\underline{5}&3&2&&&&&&& && 6 \\
\underline{4}&3&2&1&&&&&& && 4 \\
2&\underline{3}&2&1&2&&&&& && 4 \\
\underline{2}&2&2&1&2&1&&&& && 2 \\
1&\underline{2}&2&1&2&1&1&&& && 1 \\
1&1&\underline{2}&1&2&1&1&1&& && 1 \\
1&1&1&1&\underline{2}&1&1&1&1& && 1 \\
1&1&1&1&1&1&1&1&1&1 && 1 \\ \hline
\multicolumn{10}{r}{\textbf{Total Score}} & = & 45 \text{ points}
\end{array}
\]
%
On each line, the underlined stack is divided in the next step.  Can
you find a better strategy?

\subsubsection{Analyzing the Game}

Let's use strong induction to analyze the unstacking game.  We'll prove
that your score is determined entirely by the number of boxes ---your
strategy is irrelevant!

\begin{theorem}
Every way of unstacking $n$ blocks gives a score of $n(n-1)/2$ points.
\end{theorem}

There are a couple technical points to notice in the proof:

\begin{itemize}

\item The template for a strong induction proof is exactly the same as
for ordinary induction.

\item As with ordinary induction, we have some freedom to adjust indices.
In this case, we prove $P(1)$ in the base case and prove that $P(1),
\dots, P(n)$ imply $P(n+1)$ for all $n \geq 1$ in the inductive step.

\end{itemize}

\begin{proof}
The proof is by strong induction.  Let $P(n)$ be the proposition that
every way of unstacking $n$ blocks gives a score of $n(n-1)/2$.

\textbf{Base case:} If $n = 1$, then there is only one
block.  No moves are possible, and so the total score for the game is
$1(1 - 1)/2 = 0$.  Therefore, $P(1)$ is true.

\textit{Inductive step:} Now we must show that $P(1)$,
\dots, $P(n)$ imply $P(n+1)$ for all $n \geq 1$.  So assume that
$P(1)$, \dots, $P(n)$ are all true and that we have a stack of $n+1$
blocks.  The first move must split this stack into substacks with
sizes $k$ and $n+1-k$ for some $k$ strictly between 0 and $n+1$.  Now the
total score for the game is the sum of points for this first move plus
points obtained by unstacking the two resulting substacks:
%
\begin{align*}
\text{total score}
    & = \text{(score for 1st move)} \\
    & \quad + \text{(score for unstacking $k$ blocks)} \\
    & \quad + \text{(score for unstacking $n +1 - k$ blocks)} \\
    & = k(n+1-k) + \frac{k(k-1)}{2} + \frac{(n+1-k)(n-k)}{2} \\
    & = \frac{2nk + 2k - 2k^2 + k^2 - k + n^2 - nk + n - k - nk + k^2}{2} \\
    & = \frac{(n+1)n}{2}
\end{align*}
%
The second equation uses the assumptions $P(k)$ and $P(n+1-k)$ and the
rest is simplification.  This shows that $P(1)$, $P(2)$, \dots,
$P(n)$ imply $P(n+1)$.

Therefore, the claim is true by strong induction.
\end{proof}
\fi

\section{The Well Ordering Principle}

Another proof method closely related to induction depends on the

\textbox{
\textbf{Well Ordering Principle.}
Every nonempty subset of natural numbers has a smallest element.
}

The Well Ordering Principle looks nothing like the induction axiom, and it
may seem obvious but useless.

But as for obvious, note that this axiom would be false if the set of
non-negative integers, $\naturals$, were replaced by, say, the set,
$\integers$, of \emph{all} integers, or the set, $\rationals^{+}$, of
positive rational numbers.  Neither of these sets has a least element.  So
the Well Ordering Principle is capturing something special about the
natural numbers.

As for useless, it turns out that there's a routine way to transform any
proof using the Well Ordering Principle into a proof using Strong
Induction, and vice-versa.  (We won't take the time to describe the
transformations, though they are not hard.)  So Well Ordering could have
been used instead of induction in all the previous proofs.

In fact, looking back, we took the Well Ordering Principle for granted in
the proving Lemma\ref{finmin} that every finite partial order has a
minimal element.  We even implicitly relied on the Well Ordering Principle
in the proof in Week 2 Notes that $\sqrt{2}$ is irrational.  That proof
assumed that any rational number, $q$, could be written as a fraction in
\textit{lowest terms}, that is, $q = m/n$ where $m$ and $n$ are integers
with no common factors.  How do we know this is always possible?

First, we can assume $m\geq 0$ (otherwise, replace $m/n$ by $-m/(-n)$), so
the set of natural numbers, $m$, such that $q = m/n$ for some integer,
$n$, is not empty.  Therefore, by Well Ordering, there must be a least
natural number, $m_0$, such that $q=m_0/n_0$ for some integer, $n_0$.  Now
if $m_0$ and $n_0$ had a common factor, $p>1$, then $(m_0/p)/(n_0/p)$
would be another way to express $q$ as a quotient of integers.  But since
$0 \leq (m_0/p) < m_0$. this contradicts the minimality of $m_0$.

We've using the Well-ordering Principle on the sly from early on!

Mathematicians commonly use Well Ordering because it often leads 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.

\end{document}





\end{document}

