\documentclass[12pt]{article}
\usepackage{latex-macros/course}

\begin{document}

\paper{wo}{Supplementary Notes~1}{The Well Ordering Principle}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\textbox{
\centerline{
Every \emph{non-empty} set of \emph{natural} numbers 
has a \emph{minimum} element. 
}}

\noindent
Do you believe this statement? Seems obvious, right? Well, it is. But
don't fail to realize how tight it is. Crucially, it talks about a
\emph{non-empty} set ---otherwise, it would clearly be false. And it
also talks about \emph{natural} numbers ---otherwise, it might again
be false: think for example what would happen with the integers, or 
even the positive rational numbers.

This statement has a name, it is called \textbf{the well-ordering
principle}. And, as most things we give names to, it's important. Why? 
Because it is equivalent to induction. 
\begin{center}
\emph{Something can be proved by induction iff it can be proved
by the well-ordering principle.}
\end{center}
We could go on and give a general proof of this, but we
won't. Instead, we'll just convince ourselves of it by going through
an example. We'll reprove something that in the Notes (see Course
Notes for Week~3, Theorem~4.1) was proved by induction. Read the next
page.

\noindent
For reference, here is the outline that a proof by the well-ordering
principle has. (Compare it with the corresponding outline of a proof
by strong induction given in Section~4.1 of the Notes.)

\textbox{
To prove that ``$P(n)$ is true for all $n\in\mathbb{N}$'' using the
well-ordering principle:  
\begin{itemize}
\item Use proof by contradiction.
\item Assume that $P(n)$ has \emph{counterexamples}. 
      I.e., that $P(n)$ is false on at least one $n$.
\item Define the set of counterexamples 
      $C=\{n\in\mathbb{N}\mid \neg P(n)\}$. 
\item Invoke the well-ordering principle to select the minimum
      element $c$ of $C$.
\item Since $c$ is \emph{the smallest counterexample} to $P(n)$,
      conclude that both $\neg P(c)$ and $P(0),P(1),\dots,P(c-1)$. Use
      these to arrive at a contradiction. Watch out: the list
      $0,1,\dots,c-1$ will contain no numbers at all if $c=0$.
\item Conclude that $P(n)$ must have no counterexamples. Namely, that
      $(\forall n) P(n)$.
\end{itemize}
}

\newpage

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

\begin{proof}
By contradiction. Assume that the theorem is
\emph{false}. Then, some natural numbers 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 \tfrac{n(n+1)}{2}
        \:\bigr\}.
$$
By our assumption that the theorem admits counterexamples, $C$ is a
non-empty set of natural numbers. 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 \tfrac{c(c+1)}{2}.
$$
Since $c$ is the smallest counterexample ($c$ minimum of $C$), we
know the theorem holds for all natural numbers 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) = \tfrac{(c-1)c}{2}.
$$
But then, adding $c$ to both sides we get
$$
1 + 2 + 3 + \cdots + (c-1) + c 
        = \tfrac{(c-1)c}{2} + c \\\qquad
        = \tfrac{c^2 - c + 2c}{2} \\
        = \tfrac{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 natural number 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}


\end{document}

