\documentstyle[11pt,twoside,amsfonts,amstex,psfig]{article}
\input{macros-course}

\newcommand{\cross}{\times}

\begin{document}

\handout{well-founded-posets}{Well-founded Posets -- Notes for Lecture 7 and
Tutorial 4}{February 25, 1999}

\section{Well-founded Orderings} The well-ordering principle on the
natural numbers can be generalized to partial orderings in a way which
turns out to provide a powerful proof technique.

\begin{defin}
A poset $(P,\preceq)$
is \emph{well-founded} iff every nonempty subset $S \subseteq P$ has a
\emph{minimal element}, namely, an element $m \in S$ such that if $s
\preceq m$, then $s = m$, for all $s \in S$.
\end{defin}

Note that a minim\emph{al} element need not be $\preceq$ all other
elements in $S$.  That is, it need not be a minum\emph{um} element.  For
example, with the coordinatewise partial order on the set of
length-three binary words, the set, $S$, of \emph{nonzero} words has three
minimal elements, namely, 100, 010, and 001, while it has no minimum
element.

Here's a simple application of well-founded posets.  Suppose we had a
robot positioned at some point with integer coordinates in the Northeast
(viz., nonnegative) quadrant of the plane, and suppose that every second
the robot must move a unit distance South or West until it can no longer
move without leaving the quadrant.  Then it's pretty obvious that
\begin{lemma}
Under these conditions, no matter where it starts and no matter how it
moves, the robot will eventually get stuck at the origin.  
\end{lemma}

\begin{proof}
The proof is based on the following fact:

\begin{fact}\label{nxn}
The set of pairs of natural numbers, partially ordered coordinatewise, is
well-founded.
\end{fact}

Assuming this for the moment, we can consider the set of positions the
robot occupies in the Northeast quadrant.  This set is nonempty ---
because we know the robot starts somewhere in the Northeast --- and
therefore has a minimal element $(m,n)$.  But if $m>0$, then the robot can
still move South to $(m-1,n)$ contradicting the coordinatewise minimality
of $(m,n)$.  Similarly $n>0$ yields a contradiction.  Hence $m = n =0$,
and so the robot does reach the origin, where it is stuck.
\end{proof}

Fact~\ref{nxn} above is a special case of another simple, very general,
fact:

\begin{lemma}\label{coord-wf}
Suppose  $(P_1, \leq_1)$ and $(P_2, \leq_2)$ are well-founded posets.
Then so is $P_1 \cross P_2$ under the coordinatewise partial order.
\end{lemma}

\begin{proof}
Say $\emptyset \neq S \subseteq P_1 \cross P_2$.  Then $\set{p_1 \in P_1
\mid (p_1,p_2) \in S \mbox{ for some } p_2 \in P_2}$ is a nonempty subset
of $P_1$, and so has a $\leq_1$-minimal element $m_1$.  Now $\set{p_2 \in
P_2 \mid (m_1,p_2) \in S}$ is a nonempty subset of $P_2$ and so has a
$\leq_2$-minimal element $m_2$.  It follows that $(m_1,m_2)$ is a
coordinatewise minimal element of $S$.
\end{proof}

Now we can deduce Fact~\ref{nxn}: since $(\naturals, \leq)$ is
well-ordered, it is certainly well-founded, and hence by the
Lemma~\ref{coord-wf}, $\naturals^2$ with the coordinatewise partial order
is also a well-founded poset.

There is another helpful way to characterize well-founded partial orders:
\begin{lemma}
\label{d-chain}
A poset is well-founded iff it has no infinite strictly descending chain.
\end{lemma}

Saying that the poset $(P, \preceq)$ has no ``infinite strictly descending
chain'' means there is no infinite sequence $p_1,p_2,\dots,p_n\dots$ of distinct
elements in $P$ such that
\[
p_1 \succeq p_2 \succeq \dots \succeq p_n \dots.
\]
(For convenience, we're using the notation ``$p \succeq q$'' to mean $q
\preceq p$.  That's so we can read the descending chain left to right, as
usual in English.)

\begin{proof}
($\Leftarrow$) (Contrapositive) If there was such an infinite decreasing
sequence, then the set of elements in the sequence itself would be a
nonempty subset without a minimal element.

($\Rightarrow$) (Contrapositive) Suppose $(P,\preceq)$ was not
well-founded.  So there is some set $S \subseteq P$ such that $S$ has at
least one element $p_1$, but $S$ has no minimal element.  In particular,
since $p_1$ is not minimal, there must be \emph{another} element $p_2 \in
S$ such that $p_1 \succeq p_2$.  Similarly, since $p_2$ is not minimal,
there must be still another element $p_3 \in S$ such that $p_2 \succeq
p_3$.  Continuing in this way, we can construct an infinite decreasing
chain in $P$.
\end{proof}

In the robot example, the successive positions of the robot from any
starting point form a decreasing chain, and so must eventually end.  In
fact, it's easy to see that if the robot starts at position $(m,n)$, then
it gets stuck at the origin after exactly $m+n$ seconds.

An immediate corollary of Lemma~\ref{d-chain} is
\begin{corollary}\label{fin-wf}
Every finite poset is well-founded.
\end{corollary}


OK, let's change the robot rules.  Staying within the Northeast quadrant,
the robot can still move a unit distance West or South.  In this case,
however, when it moves South, it can simultaneously jump any integer
distance East.  Now it's still true that the robot must eventually get
stuck at the origin.  The proof is really the same as for
the earlier robot motion rules.  Even so, this situation does introduce a
new feature: it is no longer the case that the successive positions of the
robot form a decreasing chain under coordinatewise partial order.

Being able to say that the robots positions get strictly ``smaller'' can
be helpful.  The positions do get strictly smaller at each move if,
instead of coordinatewise order, we use \emph{lexicographic} order.

\begin{defin}
Suppose $(P_1, \leq_1)$ and $(P_2, \leq_2)$ are posets.
\emph{Pairwise lexicographic order} is a binary relation, L, on $P_1 \cross P_2$
determined by the rule that $(p_1,p_2)\mbox{ L }(q_1,q_2)$ iff either $p_1 <_1
q_1$, or $p_1 = q_1$ and $p_2 \leq_2 q_2$.
\end{defin}

\begin{lemma}\label{lex-wf}
Suppose $(P_1, \leq_1)$ and $(P_2, \leq_2)$ are posets.  Then
\begin{enumerate}

\item\label{Lpo} so is $P_1 \cross P_2$ under pairwise lexicographic
partial order, L.  Moreover,

\item\label{Lto} if $(P_1, \leq_1)$ and $(P_2, \leq_2)$ are both totally
ordered, then so is $(P_1 \cross P_2,L)$, and

\item\label{Lwf} if $(P_1, \leq_1)$ and $(P_2, \leq_2)$ are both
well-founded, then so is $(P_1 \cross P_2,\mbox{ L})$
\end{enumerate}
\end{lemma}

\begin{proof}
Parts~\ref{Lpo} and~\ref{Lto} follow immediately from the definitions.
The proof of part~\ref{Lwf} is exactly the same as the proof of
Lemma~\ref{coord-wf}!
\end{proof}

Now it's easy to see that every move of the East-jumping robot decreases
the robot's position under pairwise lexicographic order.  But notice that,
for given any starting position besides the origin, there is \emph{no
finite bound} on the number of moves before the robot gets stuck --- even
though the positions get ``smaller'' at every move.

\end{document}
