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

\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

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

\begin{document}
\lecturenotes{4}{Binary Relations}

\section{Are We Related?}

Questions about how two things are related are bound to come up whatever
you're doing.  For two people, you might ask if they're related (as
family), if they know each other, if one is older than the other, if
they're the same sex, race, age,\dots.  For two countries, you might ask if
they trade with each other, if the first has a higher per capita income, if
a visa is required to visit one from the other,\dots.  In Mathematics or
Computer Science, if two variables are assigned values, we're used to
asking if the values are the same, if the first value is bigger than the
second (assuming both values are real numbers), if the values have a common
divisor (assuming both values are integers), if the first value is a member
of the second (assuming the second value is a set), if the first value is
the domain of the second (assuming the first is a set and the second is a
function).  These are all examples of \emph{binary relations}.

The concept of binary relation is as fundamental mathematically as the
concept of function or set.  In these Notes we'll define some basic
terminology for binary relations, and then we'll focus on two especially
important kinds of binary relations: \emph{equivalence relations} and
\emph{partial orders}.

\subsection{Relations and Functions}

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 look like
\begin{align*}
\{&(\texttt{Albert R. Meyer}, 6.042), (\texttt{David Shin}, 18.062),
(\texttt{Sayan Mitra}, 6.04),\\
\ & (\texttt{Albert R. Meyer}, 18.062), (\texttt{Charles E. Leiserson},
6.046),\\
\ & (\texttt{Donald Sadoway}, 3.091), \dots \}
\end{align*}

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$.  \iffalse With
this notation, we could have defined the range of $R$ simply as $AR$.\fi
Notice that if $R$ happened to be a function, the notation $R(C)$ from Week
3 Notes would also describe the image of $C$ under $R$.

The set $RC$ is called the \emph{inverse image} of $C$ under $R$.  Notice
the clash in notation when $R$ happens to be a function: $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$.

The Fall '05 ``is teaching relation'' relation above is not surjective
since none of the Spring term-only subjects are being taught.  It's not
total either, since not all the eligible teaching staff are actually
teaching this term.

\iffalse
A more mathematical example of a binary relation is, $L$, the
``less-than'' relation between complex numbers based on their moduli.
Here the domain and codomain are both equal to the set, $\complexes$, of
complex numbers, and
\[
(a+bi)\,L\,(c+di) \qiff \abs{a+bi} < \abs{c+di}.
\]
That is, $(a+bi)\,L\,(c+di)$ iff $a^2 + b^2 < c^2 + d^2$.  This relation, $L$,
is total, since there is always a larger modulus.  Its range is the set of
complex numbers with positive moduli, which means $L$ is not surjective,
because 0 is not in its range.  But if we define a relation, $L'$, with
the same domain and graph as $L$ but with codomain $\complexes - \set{0}$,
then $L'$ \emph{is} surjective.

The example of $L$ and $L'$ which have the same graph but different
codomains illustrates that the fact that properties like being surjective
or total depend on the codomain and domain of a relation, not just its
graph.  That's why we included its domain and codomain as part of a binary
relation.  However, it's common to ignore the distinction between a
relation and its graph when the domain and codomain are not needed or can
determined from context.  For example, we might say $R_1 \subseteq R_2$
instead of $\graph{R_1} \subseteq \graph{R_2}$.

Functions can be understood as a type of relation.  That is, a function,
$f:A \to B$, is a relation from $A$ to $B$ whose graph has the property
that for every $a$, there is \emph{at most one} $b$ such that $(a,b) \in
\graph{f}$.  This unique $b$ is called $f(a)$.

We mostly work with functions that are total relations, so we adopt the
convention that ``function'' means ``total function'' unless explicitly
stated otherwise.  We will refer to the full set of total and nontotal
functions as the \emph{partial} functions.  So (total) functions are a
special case of partial functions.
\fi

\section{Equivalence Relations}

An equivalence relation on a set of objects comes about when all we care
about is some property---say the size, shape, or color---of the objects
rather than the objects themselves.  We say two objects with the same
property value are ``equivalent.''  Of course this happens all the time,
which is why equivalence relations appear everywhere.

For example, two triangles in the plane are \emph{congruent} iff they have
the same three lengths of sides.  They are \emph{similar} iff they have the
same three sizes of angles.

\emph{Representation-equivalence} comes up in Computer Science as the
relation between representations of the same abstract data type.  For
example, the simplest way of representing a finite set of numbers is as an
unsorted list.  The two lists \texttt{(3 4 -2 177 5)} and \texttt{(177 -2
3 5 4)} are ``representation-equivalent'' because they represent the same
set.

\subsection{Equivalence by Function}

Abstractly, we assume there is some function that extracts the angles,
size, color, or whatever other property of elements we're interested in.
Two elements would be considered equivalent iff the function extracts the
same value for each.

For example, if $f_c$ is the function mapping a triangle to the lengths its
sides, then $f_c$ determines the congruence relation.  If $f_s$ is the
function mapping a triangle to the sizes of its angles, then $f_s$
determines the similarity relation.

\begin{definition}\label{deqv}
Given any total function, $f$, with domain $A$, define the binary relation
$\equiv_f$ on $A$ by the rule:
\begin{equation}\label{Rf}
a \equiv_f b \qiff f(a) = f(b)
\end{equation}
for all $a,b \in A$.

A binary relation is an \emph{equivalence relation} iff it equals
$\equiv_f$ for some $f$.
\end{definition}

So congruence of triangles is an equivalence relation because it is
$\equiv_{f_c}$, as is triangle similarity because it is $\equiv_{f_s}$.
Likewise representation-equivalence on number lists is an equivalence
relation because it is $\equiv_{f_r}$, where $f_r$ maps a representation to
the set it represents.

\textbf{Quick exercise:} Show that the equality relation on elements of a
set, $A$, is actually an equivalence relation according to
Definition~\ref{deqv} by describing an $I:A\to A$ such that equality is
$\equiv_I$.
\medskip

Congruence modulo $n$ is another equivalence that we will explore in detail
when we introduce elementary number theory and its role in modern
cryptography.  Integers $k$ and $m$ are \emph{congruent modulo} an integer
$n>1$, written
\[ 
m \equiv k \bmod n,
\]
iff $m$ and $k$ have the same remainder on division by $n$.  So congruence
modulo $n$ is the equivalence relation determined by the
remainder-on-division-by-$n$ function.  This relation is called a
\emph{congruence} because adding or multiplying equivalent integers yields
equivalent integers.  That is,
\begin{lemma}\label{mod}
If $m_1 \equiv k_1 \bmod n$ and $m_2 \equiv k_2 \bmod n$, then
\begin{eqnarray*}
m_1 + m_2 & \equiv & k_1 + k_2 \bmod n,\text{ and}\\
m_1 m_2 & \equiv & k_1 k_2 \bmod n.
\end{eqnarray*}
\end{lemma}
We leave the proof of Lemma~\ref{mod} as an easy exercise for the reader.

\subsection{Partitions}

Cutting up a set into a bunch of pieces is called \emph{partitioning} the
set.  The pieces are called \emph{blocks} of the partition (you'd think
the pieces would be called the \emph{parts} of the \emph{part}ition, but
no).  More formally,
\begin{definition}\label{part}
A \emph{partition} of a set, $A$, is a collection, $\mathcal{A}$, of
nonempty sets called the \emph{blocks of the partition} such that
\begin{enumerate}
\item $A = \lgunion_{B \in \mathcal{A}} B$, and\label{AU}
\item if $B_1 \neq B_2$ are blocks of $\mathcal{A}$, then $B_1$ and $B_2$
are disjoint\footnote{Two sets are said to be disjoint when they have no
elements in common, that is, their intersection is empty.}.\label{B1B2}
\end{enumerate}
\end{definition}

\begin{example}\label{part4}
We can partition the integers into four blocks according to
whether their remainder on division by 4 is 0, 1, 2, or 3:
\[
\begin{array}{l}
\set{0, 4, -4, 8, -8, 12,\dots}\\
\set{1, -3, 5, -7, 9, -11,\dots}\\
\set{2, -2, 6, -6, 10, -10,\dots}\\
\set{3, -1, 7, -5, 11, -9,\dots}.
\end{array}
\]
\end{example}

\begin{example}
We can partition the real line into blocks by cutting it at
integer points.  Namely, the $n$th block, $B_n$, would be $\set{r \in
\reals \suchthat n \le r < n+1}$.  So $B_n$ could also be described as the
set of real numbers $r$ that are $\equiv_f$ to $n$, where $f$ is the
\emph{floor} function: $f(r) = \floor{r}$, the largest integer $\le r$.
\end{example}

\begin{example}
We can partition the pixels in an image according to their color (so there
will be somewhere between 2 and several millions blocks depending on
whether the image is pure black and white or is ``true color.'' 
\end{example}

The relation of \emph{being in the same block} of a partition is an
equivalence relation.  This is the equivalence relation defined by the
function that maps each element to the block it's in.  More precisely,
suppose $\mathcal{A}$ partitions a set, $A$, and define
$[a]_{\mathcal{A}}$ be the block with $a$ in it.  Note that every $a \in
A$ belongs to some block by Definition~\ref{part}.\ref{AU}, and there is
only one such block by Definition~\ref{part}.\ref{B1B2}, so
$[a]_{\mathcal{A}}$ is unambigously defined for each element, $a$.  So
being-in-the-same-block is $\equiv_{\text{blk}}$, where $\text{blk}(a)
\eqdef [a]_{\mathcal{A}}$.

Conversely, an equivalence relation, $\equiv_f$, given by a total
function, $f$, on a set, $A$, determines a partition of $A$, where the
block containing $a \in A$ is $\set{a' \suchthat f(a') = f(a)}$.

For example, there are four equivalence classes of integers under
congruence mod 4.  These are exactly the blocks of the partition based on
remainder-by-4 of Example~\ref{part4}.

So we can extract an equivalence relation from any partition, and
conversely, we can define a partition determined by any equivalence
relation.  In fact, it's not hard to see that if you extract an
equivalence relation from a partition and then use the partition to
determine an equivalence relation, you get back to the partition you
started with.  Likewise, if you take the parition determined by an
equivalence relation and extract a partition from it, you also get back to
where you started.  So partitions and equivalence relations are really
interchangeable ways of talking about the same thing.

To summarize: the hallmark of equivalence relations is \emph{sameness} of
some property of objects.  An equivalence relation hides irrelevant
differences between objects, and lets us lump together into blocks all the
objects that are the ``same.''  Conversely, equivalence is captured by the
property of being in the same block.


\subsection{Properties of Equivalence Relations}

Equivalence relations have some obvious properties that occur so frequently
they merit names:

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

\item \emph{reflexive} iff for every $a\in A$,
\[
a\, R\, a,
\]

\item \emph{symmetric} iff for every $a,a'\in A$,
\[
a\, R\, a' \qimplies a'\, R\, a,
\]

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

\end{itemize}
\end{definition}

\begin{example}
Let $R_1$ be the less-than relation, $<$, on the natural numbers.  Then
$R_1$ is transitive (since [$j<k$ and $k<l$] implies $j<l$).  It is not
reflexive (since $0<0$ is false) and not symmetric (since $0<1$ but not
$1<0$).
\end{example}

\begin{example}
We know that if $A,B,C$ are sets and $A \subset B$ and $B \subset C$, then
$A \subset C$.  That is, the proper subset relation, $\subset$, is
transitive.  It is not reflexive (since a set is never a \emph{proper}
subset of itself) and not symmetric (for example, the empty set is a subset
of any nonempty set, but not vice versa).
\end{example}

\begin{example}\label{implies}
Let $R_2$ be the ``implies'' relation on the set of propositional formulas,
that is, define $p\, R_2\, q$ iff $p \implies q$ is propositionally valid.
Now $R_2$ is reflexive, since $p \implies p$ is valid.  It is also
transitive, since if $p \implies q$ and $q \implies r$ are valid, then $p
\implies r$ is valid.  However, it isn't symmetric, since, for example,
$\texttt{false} \implies \texttt{true}$ valid, but $\texttt{true} \implies
\texttt{false}$ is not.
\end{example}

\begin{example}\label{finite}
Let $R_3$ be the relation on sets, $C,D$ of natural numbers such that $C\,
R_3\, D$ iff $C \intersect D$ is finite.  Then $R_3$ is symmetric, but not
reflexive (for example $\naturals\, R\, \naturals$ is not true).

\textbf{Quick exercise:}  Explain why $R_3$ is not transitive.

\solution{Let $C$ be the even numbers, $D$ the odd numbers and $E$ the
multiples of 4.  So $C\, R_3\, D$, and $D\, R_3\, E$ but not $C\, R_3\, E$.}
\medskip

\end{example}

\begin{example}\label{dist}
Let $R_4$ be the relation on complex numbers such that $a\, R_4\, b$ iff the
distance from $a$ to $b$ in the complex plane is $\le 1$, that is, $\abs{a
- b} \le 1$.  Then $R_4$ is reflexive and symmetric, but not transitive
(because $1\,R_4\,2$ and $2\,R_4\,3$, but not $1\,R_4\,3$).
\end{example}

Notice that the equality relation on a set $A$ is reflexive, symmetric,
and transitive.  We won't prove this---it's an axiom.  These properties
of equality directly imply the corresponding properties for any
equivalence relation:

\begin{lemma}\label{rstlem}
Every equivalence relation is reflexive, symmetric, and transitive.

\begin{proof}
Consider any equivalence relation, $\equiv_f$, determined by some function,
$f$ with domain $A$.

Since $f(a) = f(a)$, it follows trivially that $\equiv_f$ is reflexive.
LIkewise, if $f(a) = f(a')$, then $f(a') = f(a)$, which implies that
$\equiv_f$ is symmetric.  Finally, if $f(a) = f(b)$ and $f(b) = f(c)$, than
obviously $f(a) = f(c)$, which implies that $\equiv_f$ is transitive.
\end{proof}
\end{lemma}

\subsection{Equivalence by Axioms}

The properties of reflexivity, symmetry, and transitivity actually
provide an elegant axiomatic characterization of equivalence relations.
(In fact, most authors \emph{define} equivalence relations using these
axiomas, but we think our approach makes more sense.)

\begin{theorem}\label{rst}
Any relation on a set that is reflexive, symmetric and transitive is
an equivalence relation on the set.

\begin{proof}
Suppose $R$ is a relation on a set, $A$, and $R$ is reflexive, symmetric,
and transitive.  Define the function, $f$, with domain, $A$, by the rule
\[
f(a) \eqdef \set{a}R.
\]

We will prove that $R$ is $\equiv_f$, and hence $R$ is an equivalence
relation.  That is, we have to show that
\begin{equation}\label{a1R}
 a\, R\, b  \qiff \set{a}R = \set{b}R 
\end{equation}
for all $a,b \in A$.

First we prove~(\ref{a1R}) from right to left.  Namely, suppose $\set{a}R =
\set{b}R$.  Since $R$ is \textbf{reflexive}, we have $b \in \set{b}R$.
This means $b \in \set{a}R = \set{b}R$.  So $a\,R\,b$ holds by definition
of $\set{a}R$, which completes the proof from right to left.

To prove the converse, suppose
\begin{equation}\label{arb}
a\, R\, b.
\end{equation}
We'll first prove that
\begin{equation}\label{brsub}
\set{b}R \subseteq \set{a}R.
\end{equation}
To do this, let $c$ be an element of $\set{b}R$; we must show that $c \in
\set{a}R$.  But by definition of $\set{b}R$, we know that
\begin{equation}\label{brc}
b\, R\, c.
\end{equation}
But~\eqref{arb} and~\eqref{brc} together imply $a\, R\, c$ because $R$ is
\textbf{transitive}.  So $c \in \set{a}R$ by definition of $\set{a}R$.
This proves~\eqref{brsub}.

Finally,~\eqref{arb} implies $b\, R\, a$, because $R$ is
\textbf{symmetric}.  So the same argument used to prove~\eqref{brsub}, we
can conclude that
\[
\set{a}R \subseteq \set{b}R.
\]
But this together with~\eqref{brsub} implies that $\set{a}R = \set{b}R$,
completing the proof of~\eqref{a1R} from left to right.
\end{proof}

\end{theorem}

We have highlighted where each of the three properties of equivalence
relations were used in this proof.  Verifying that a proof uses all
available assumptions is a good ``sanity check''---if one of the assumed
properties was not used in the proof, then you have either made a mistake
or proven a stronger theorem than you thought.  For example, if you didn't
use reflexivity anywhere in the proof of Theorem~\ref{rst}, you would have
proved that any symmetric, transitive relation is an equivalence relation,
which is false.  So a proof that failed to use reflexivity must be
mistaken.

\iffalse

\textbf{Quick exercise:}  Give an example of a symmetric, transitive
relation on a set, $A$, that is not an equivalence relation.

\solution{The relation with graph $\set{(1,1)}$ and domain $\set{1,2}$.}
\medskip

\fi

These axioms are helpful in at least a couple of ways.  First, there are
situations where it's hard to find a function, $f$, that characterizes an
equivalence relation.  Theorem~\ref{rst} lets us show that the relation is
an equivalence by verifying that the relation is reflexive, symmetric, and
transitive.

\begin{notesproblem}
Define two positions of the pieces in the game of
chess to be \emph{mutually reachable} if it is possible to start at either
one and get to the other one by a sequence of legal chess moves.  We don't
see any useful way to describe a function, $f$, such that mutual
reachability equals $\equiv_f$.  Prove that mutual reachability is an
equivalence relation anyway.
\end{notesproblem}
\medskip

Second, to prove that a relation is \emph{not} an equivalence just from
the definition, we would have to show that the relation is not equal to
$\equiv_f$ for any possible function, $f$.  Off hand, this requires a
daunting analysis in order to rule out all possible functions.  But
Theorem~\ref{rst} implies we can always show that a relation is not an
equivalence simply by finding two or three elements of the domain where
the axioms fail to hold.

\section{Partial Orders}%\label{ordrs}

Partial orders are another class of binary relations that are particularly
important in Computer Science, with applications that include task
scheduling, database concurrency control, and proving that computations
terminate.

A general example of a partial order is the subset relation, $\subset$, on
sets.  In fact, we will \emph{define} partial orders via the subset
relation in much the same way we defined equivalence relations.  Namely,
for any element, $a$, we think of a function, $g$, such that $g(a)$ is the
\emph{set} of properties that $a$ has.  Then we relate different elements
according to how their properties compare.  All partial orders will arise
in this way.

\iffalse  NEED BETTER EXAMPLE

For example, $a$ might be a list of responses to successive
questions on a course registration questionnaire and $g(a)$ might be the
set of actual answers in the list.  Then if $a$ is
\begin{quote}
(``Sanjay Duda'', 6-2, sduda@mit.edu, --, 2/4/86, --, 6.001, --)
\end{quote}
where ``--'' indicates no response, we would take $g(a)$ to be
\[
\set{\text{2/4/86, 6.001, 6-2, ``Sanjay Duda'', sduda@mit.edu}}
\]
We consider one such list of responses to be ``less complete'' than
another when every response on the first list is matched by the second
list, but the second list has some additional responses to questions that
were not responded to on the first list.  That is $a$ is a less complete
response list than $b$ iff $g(a) \subset g(b)$.
\fi

\subsection{Partial Order by Function}

For partial orders we'll often use the symbols $\prec$ or $\preceq$
because they resemble the symbols used for subset and less-or-equal, which
are the most common partial orders.  (General relations are usually
denoted by a letter like $R$ instead of a cryptic squiggly symbol, so
$\preceq$ is kind of like Prince.)

\begin{definition}
\label{po-def}
Given any total function, $g$, from a set, $A$, to a collection of sets,
define the binary relation $\prec_g$ on $A$ by the rule:
\begin{equation}\label{po-eqn}
a \prec_g b \qiff g(a) \subset g(b)
\end{equation}
for $a, b \in A$.  A binary relation, $R$, on a set, $A$, is a
\emph{partial order} iff there is a $g$ such that $R$
agrees with $\prec_g$ for every pair of distinct elements.  That is,
\begin{equation}
\label{po-lem}
a\, R\, b \qiff a \prec_g b
\end{equation}
for all $a \neq b \in A$.
\end{definition}

An immediate consequence of Definition~\ref{po-def} is that the subset
relation itself is a partial order.  Specifically, if $A$ is any
collection of sets, then the proper subset relation, $\subset$, is a partial
order on $A$.  To prove this, we let $I_A$ be the identity
function on $A$.  Then $\prec_{I_A}$ is the same relation as
$\subset$, and so trivially satisfies the condition~\eqref{po-eqn} on $R$.
The contained-in-or-equal subset relation, $\subseteq$, is also a partial
order, since it agrees with $\prec_{I_A}$ for $a \neq b$.

The most familiar examples of partial orders are ``less than'' relations,
for example, the relation, $<$, on real numbers.  To see that $<$ is
indeed a partial order, just define $h(r) \eqdef \set{q \in \rationals
\suchthat q<r}$.  Since there is a rational number between any two real
numbers (to see why, think about where their decimal expansions first
differ), it follows that $<$ is simply $\prec_h$.  Likewise, the
relation, $\le$, is a partial order because it agrees with $\prec_h$ for
all pairs of distinct real numbers.

Our general definition of partial order leaves unspecified whether elements
are related to themselves.
\begin{definition}
A partial order is called \emph{weak} iff it is reflexive.
\end{definition}
So, for example, the relation $\le$ on the real numbers, and the relation
$\subseteq$ on sets, are weak partial orders.

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

A partial order is \emph{strict} iff it is irreflexive.
\end{definition}

The $<$-relation on the reals and the proper subset relation, $\subset$, are
strict partial orders.  In general, a partial order may be neither weak nor
strict; this happens when some elements are related to themselves and
others are not.

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.
\begin{proof}
Define $p(a) \eqdef \bar{a}$, where $\bar{a}$ is the complement of
$a$, and note that
\[
[a\, R\, b] \qiff [a \supset b] \qiff [\bar{a} \subset
\bar{b}] \qiff [p(a) \subset p(b)].
\]
So $R$ equals $\prec_p$ and so is a partial order.  It is strict since no
set is a proper subset of itself.
\end{proof}
\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 natural numbers.
\begin{proof}
Let $v(n) \eqdef \text{ the set of natural numbers that divide } n$.  Then
divides is $\prec_v$, and so is a partial order.  Since $m \divides m$, it
is a weak partial order.
\end{proof}

\end{example}

\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
orders}\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.}:
\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 generally \emph{not} total: any two distinct finite
sets of the same size will be incomparable under $\subseteq$.

\subsection{Properties of Partial Orders}

We've already observed that the subset relation is transitive, which
implies that any relation, $\prec_g$, is transitive.  So by
Definiton~\ref{po-lem}:
\begin{lemma}
Every partial order is transitive.
\end{lemma}

One additional property of the subset relation is enough to completely
characterize partial orders.
\begin{definition}\label{antis}
A binary relation, $R$, on a set, $A$, is \emph{antisymmetric} if
\[
a\, R\, b \qimplies \neg(b\, R\, a)
\]
for all $a \neq b \in A$.
\end{definition}

\begin{lemma}
Every partial order is antisymmetric.
\begin{proof}
Suppose $R$ is a partial order on $A$.  So there is a set-valued total
function, $g$, with domain $A$ and $R$ agrees with $\prec_g$ on pairs of
distinct elements in $A$.

We want to show that $a R b$ and $b R a$ cannot both hold for elements $a
\neq b$.  But if they did both hold, then~\eqref{po-eqn} would imply that
$g(a)$ and $g(b)$ are proper subsets of each other, which is impossible.
\end{proof}
\end{lemma}

\subsection{Partial Orders by Axioms}
The properties of transitivity and antisymmetry provide an axiomatic
characterization of partial orders:
\begin{theorem}\label{po-th}
A binary relation is a partial order iff it is transitive and
antisymmetric.

\begin{proof}
Let $R$ be a binary relation on a set $A$.  Then the preceding two Lemmas
imply the left to right direction of Theorem~\ref{po-th}.

To prove the Theorem in the right to left direction, assume $R$ is
transitive and antisymmetric.  Define
\begin{equation}\label{ga}
g(a) \eqdef R\set{a} \union \set{a}.
\end{equation}
We claim that $R$ is a partial because it agrees with $\prec_g$ on distinct
elements of $A$.  That is, if $a \neq b \in A$, then
\begin{equation}\label{rgb}
a\, R\, b  \qiff  g(a) \subset g(b).
\end{equation}

To prove~(\ref{rgb}) from right to left, note that
\begin{align*}
g(a) \subset g(b)
    & \qimplies a \in g(b) & \text{because $a \in g(a)$ by~\eqref{ga}},\\
    & \qimplies a \in R\set{b} \union \set{b} & \text{by def.\ of~$g(b)$},\\
    & \qimplies a \in R\set{b} & \text{since $a \neq b$},\\
    & \qimplies a\,R\,b & \text{by def of $R\set{b}$}.
\end{align*}

The proof of~(\ref{rgb}) from left to right also follows routinely from
the definitions by a somewhat longer, but not specially informative
argument, which we omit.

\iffalse

we suppose $a\, R\, b$ and prove that $g(a) \subset g(b)$.

Our supposition that $a\, R\, b$ means that $a \in R\set{b}$ and so
\begin{equation}\label{agb}
a \in g(b)
\end{equation}
by definition of $g(b)$.

Next we show that
\begin{equation}\label{gag}
g(a) \subseteq g(b).
\end{equation}
To do this, we suppose 
\begin{equation}\label{apa}
a' \in g(a),
\end{equation}
and prove that
\begin{equation}\label{apb}
a' \in g(b).
\end{equation}

From~\eqref{agb}, we know that\eqref{apb} holds if $a' = a$, so we may
assume $a'\neq a$.  But in this case,~\eqref{apa} and the definition of
$g(a)$ imply that $a' \in R\set{a}$.  In other words,
\begin{equation}\label{apr}
a'\,R\,a.
\end{equation}
Now since $R$ is \textbf{transitive},~\eqref{apr} and our supposition $a\,
R\, b$ together imply that $a'\,R\, b$, and hence $a' \in R\set{b} \subseteq
g(b)$, as claimed.  This proves~\eqref{gag}.

To complete the proof that $g(a) \subset g(b)$, we need only show that
$g(a) \neq g(b)$.  In particular, we show that $b \notin g(a)$.  To do
this, assume to the contrary that $b \in g(a) \eqdef R\set{a} \union
\set{a}$.  Then because $a \neq b$, we conclude that $b \in R\set{a}$, that
is, $b\, R\, a$.  So $b\, R\, a$ and $a\, R\, b$ both hold, and
\textbf{antisymmetry} of $R$ implies $a=b$, a contradiction.  This proves
$b \notin g(a)$ and hence $g(a) \neq g(b)$ as claimed.
\fi

\end{proof}
\end{theorem}

In the literature, partial orders are usually defined axiomatically
as in Theorem~\ref{po-th}, and then the possibility of representing
partial orders as $\prec_g$ is proved as a theorem.  Since the two
characterizations imply each other, it is a matter of taste which one to
use as the definition.

Strict partial orders have an even simpler axiomatic characterization.

\iffalse

\begin{definition}
A binary relation, $R$, on a set, $A$, is \emph{asymmetric} iff
\[
a\, R\, b \qimplies \neg(b\, R\, a)
\]
for all $a,b\in A$ (even if $a = b$).
\end{definition}

\begin{theorem}\label{trnasym}
A binary relation on a set is a strict partial order iff it is transitive
and asymmetric.
\end{theorem}

\begin{notesproblem}
Prove Theorem~\ref{trnasym}.
\end{notesproblem}

\begin{example}\label{dict}
Let $A$ be the finite strings of characters from the Roman alphabet, and
define $s \prec t$ iff $s$ would appear before $t$ in a dictionary.  Then
$\prec$ is a strict total order.
\end{example}

\fi

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

\begin{notesproblem}
Prove Theorem~\ref{tir}.  \hint Show that transitivity and irreflexivity
imply antisymmetry.
\end{notesproblem}

For weak partial orders, we often write an ordering-style symbol like
$\preceq$ instead of a letter symbol like $R$.  Likewise, we generally use
$\prec$ 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$.

\subsection{Products and Restrictions of Relations}

Product and restriction are two ways of constructing new relations from
old ones that will be useful.

\subsubsection{Products}

\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 symmetry,
reflexivity, and antisymmetry.  This implies that if $R_1$ and $R_2$ are
both partial orders, then so is $R_1 \cross R_2$.  Likewise for being an
equivalence relation.

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

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.  For example, the age 240 months, height 68
inches pair, (240,68), and the pair (228,72) are incomparable under $Y$.

\subsubsection{Restrictions}

We usually think of a single ``less-than'' relation, $<$, on real numbers,
or rational numbers, or integers.  Technically, these a different
relations because they have different domains and graphs, but there is an
obvious connection: the $<$ order on, say, the rationals is gotten by
restricting the real order to the subset of rationals.

\begin{definition}\label{restr}
Let $R$ be a relation on a set, $A$, and let $B$ be a subset of $A$.  The
\emph{restriction} of $R$ to $B$ is the relation on $B$ whose graph is
$\graph{R} \intersect (B \cross B)$.
\end{definition}

Restrictions preserve many relational properties.  For example,
restriction preserves transitivity, that is, if $R$ is transitive, then so
is any restriction of $R$.  Restriction also preserves symmetry,
antisymmetry, asymmetry, reflexivity, and irreflexivity.  This implies
that the restriction of an equivalence relation is an equivalence
relation, and the restriction of a partial order is a partial order.

But restriction doesn't preserve all the relational properties we've
considered.  For example, being a surjective relation is not preserved by
restriction, nor is being a total relation.

We'll leave the proofs of these claims to the reader; they're all easy.

\section{Digraphs} 

A \emph{directed graph} (\emph{digraph} for short) is formally the same as
a binary relation on a set, $A$, but we picture the digraph geometrically
by representing elements of $A$ as points on the plane, with an arrow from
the point for $a$ to the point for $b$ exactly when $a\, R\, b$.  The
elements of $A$ are referred to as the \emph{vertices} of the digraph.

\begin{example}
\begin{samepage}
The divisibility relation on $\set{1,2,\dots,12}$ is represented by the
digraph:
\begin{center}
\includegraphics{figures/divide12.mps}
\end{center}
\end{samepage}
\end{example}

\subsection{Paths in Digraphs}\label{paths}

\begin{definition}
A \emph{path in a digraph}, $R$, is a sequence of vertices $a_0,\dots,a_k$
with $k \ge 0$ such that $a_i\, R\, a_{i+1}$ for every $0 \le i < k$.  The
path is said to \emph{start} at $a_0$, to \emph{end} at $a_k$, and the
\emph{length} of the path is defined to be $k$.
\end{definition}

Pictured with points and arrows, a path $a_0,\dots,a_k$ looks like a line
that starts at the point $a_0$ and follows arrows between successive points
on the path to end at $a_k$.  Note that a single point counts as a length
zero path (this is just for convenience).

Many of the relational properties have geometric descriptions in terms of
digraphs.  For example:
\begin{description}

\item[Reflexivity:] All vertices have self-loops (a \emph{self-loop} at a
vertex is an arrow going from the vertex back to itself).

\item[Irreflexivity:] No vertices have self-loops.

\item[Symmetry:] 
All edges are bidirectional.

\item[Transitivity:] Short-circuits---for any path through the graph, there
is an arrow from the first vertex to the last vertex on the path.
\end{description}

We can define some new relations based on paths.  Let $R$ be a digraph
with vertices, $A$.  Define relations $R^*$ and $R^+$ on $A$ by the
conditions that
\begin{eqnarray*}
a\, R^*\, b &\eqdef& \mbox{there is a path in $R$ from $a$ to $b$},\\
a\, R^+\, b &\eqdef& \mbox{there is a positive length path in $R$ from $a$ to $b$}.
\end{eqnarray*}

$R^*$ is called the \emph{path relation} of $R$.  It follows from the
definition of path that $R^*$ is transitive.  It is also reflexive
(because of the length-zero paths) and it contains the graph of $R$
(because of the length-one paths).  $R^+$ is called the
\emph{positive-length path relation}; it also contains $\graph{R}$ and is
transitive.

\subsection{Directed Acyclic Graphs}\label{sec:dag}

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 represent the
task by vertices and a constraint that task $a$ must finish before task $b$
can start by an arrow from $a$ to $b$.

\begin{samepage}
\begin{example}\label{cloth}
Here is a graph that describes the order in which you could put on
clothes.  The tasks are the clothes to be put on, and the edges say what
should be put on before what.
\begin{center}\includegraphics{figures/clothes.mps}\end{center}
\end{example}
\end{samepage}

This ``depends on'' graph imposes a partial ordering on tasks.  But what
if we add a relation edge from belt to underwear?  In that case the
dependency graph stops making sense: there is no way to get dressed!  What
goes wrong is that the added edge creates a ``cyclic'' dependency.

\begin{definition}
A \emph{cycle} is a positive length path in a digraph that begins and ends
at the same vertex.  A \emph{directed acyclic graph (DAG)} is a directed
graph with no cycles.
\end{definition}

So a task graph had better be a DAG for its tasks to be doable in an order
that respects task dependencies.

We use DAG's as an economical way to represent the dependency relation.
Usually a task-graph DAG itself is not a transitive relation because it
includes only the edges showing ``direct'' dependencies.  Rather, the
\emph{dependency relation} we care about is defined by the positive length
path relation, $R^+$, in the task graph.  The dependency relation will
always be a partial order:

\begin{lemma}
If $D$ is a DAG, then $D^+$ is a strict partial order.
\end{lemma}

\begin{proof}
We know that $D^+$ is transitive.  Also, a positive length path from a
vertex to itself would be a cycle, so there are no such paths.  This means
$D^+$ is irreflexive, and so by Theorem~\ref{tir}, it is a strict partial
order.
\end{proof}

\iffalse

\begin{notesproblem}
Verify that any strict partial order is a DAG.

\solution{
Suppose the graph representation of a partial order $\prec$ has a cycle
$a_1,\dots,a_k,a_1$.  Then by transitivity of $\prec$ (with an induction
hiding inside) we have $a_1 \prec a_k$.  We also have $a_k \prec a_1$.
This violates the asymmetry of $\prec$, a contradiction.
}
\end{notesproblem}


\begin{notesproblem}
If $a$ and $b$ are distinct nodes of a digraph, then $a$ is said to
\emph{cover} $b$ if there is an edge from $a$ to $b$ and there is no other
path from $a$ to $b$.  If $a$ covers $b$, the edge from $a$ to $b$ is
called a covering edge.

\bparts

\ppart Show that if two DAG's have the same positive path relation, then
they have the same set of covering edges.

\ppart Describe two graphs (necessarily not DAG's) with vertices
$\set{1,2,3}$ which have the same positive path relation, but not the same
set of covering edges.

\solution{In the graphs $\set{(1,2), (2,1), (2,3), (3,2)}$ and
$\set{(1,2),(2,3),(3,1)}$ all edges are covering edges.}

\ppart For any digraph, $D$, let $\widehat{D}$ be the subgraph of $D$
consisting of only the covering edges.  Show that if $D$ is finite and has
no self-loops, then $D$ and $\widehat{D}$ have the same positive path
relation, that is $D^+ = \widehat{D}^+$.
 
\ppart Conclude that if $D$ is a finite DAG, then $\widehat{D}$ has the
smallest number of edges among all digraphs with the same positive path
relation.

\ppart Show that the previous result is not true in general for the infinite
DAG corresponding to the total order on the real numbers.

\solution{In the DAG for $<$ on the reals, there are no covering edges, so
$\widehat{<}$ has no edges.}

\eparts
\end{notesproblem}
\fi


\subsection{Topological Sorting}

In a DAG for a partial order, incomparable elements appear as vertices
with no path between them in either direction.  So in the partial order on
clothes from Example~\ref{cloth} ``left shoe'' and ``right shoe'' are
incomparable.  If the order is total, there are no incomparable elements,
and the order can be represented by a DAG looks like a line:

\mfigure{!}{1.5in}{figures/total-hasse}

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
the DAG of Example~\ref{cloth}; there are several other possible sorts as
well.

Topological sorts for finite DAG's 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.  (An infinite partially ordered set might have no
minimal element: consider $\le$ on the $\integers$.)

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

\begin{proof}
Let $R$ be a partial order on a set, $A$.  For any element, $a \in A$, let
$g(a)$ be the set of elements ``less than or equal to $a$'', that is,
\[
g(a) \eqdef R\set{a} \union \set{a}.
\]
Now if $b\, R\, a$, then transitivity of $R$ implies that $g(b) \subseteq
g(a)$.  Also, if $b\, R\, a$ and $b \neq a$, then $a \notin g(b)$ since
$R$ is antisymmetric, and so $g(b) \subset g(a)$.  So if $a$ is not
minimal, then there is some $b$ such that $g(b) \subset g(a)$.  If $A$ is
finite, this implies that $\card{g(b)} < \card{g(a)}$.

So if $A$ is finite, the Well Ordering Principle implies that there must
be an $a_0$ such that $g(a_0)$ has minimum size.  So no $g(b)$ can be
smaller than $g(a_0)$, which means $a_0$ must be minimal.
\end{proof}
\end{lemma}

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

\begin{proof}
We prove Theorem~\ref{thm:topological} by induction on $n$ with hypothesis
\[
P(n) \eqdef \text{[any partial order on a set with $n$ elements has a
topological sort]}.
\]

\textbf{Base case} $n=1$: a topological sort of a set with one element
is simply that element.

\textbf{Inductive step:} Assume $P(n)$.  Consider a partial order,
$\preceq$ on a set, $A$, with $n+1$ elements.  By Lemma~\ref{finmin}, $A$
must have a minimal element, $a_0$.  Now the restriction of $\preceq$ to
the set $A-\set{a_0}$ is also a partial order.  So by the inductive
hypothesis, $A-\set{a_0}$ has a topological sort $\sqsubseteq_n$.  Now
define $\sqsubseteq$ on $A$ by the rule that $a\, \sqsubseteq\, b$ iff
[$a\, \sqsubseteq_n\, b$ or $a = a_0$].  It's now easy to check that
$\sqsubseteq$ is the required topological sort of $A$.  This proves
$P(n+1)$, completing the proof by induction.
\end{proof}

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 the partial order of dependencies among task, 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 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}

An alternative definition is that a chain in a partial order is a set,
$C$, domain elements such that the restriction of the partial order to $C$
is a total order.

Note that vertices on any path in the DAG of the partial order is a chain.
In general, a chain only contains vertices on a path but may skip some
vertices on it.  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\footnote{Picky point: the
\emph{length} of a chain $a_0 \prec a_1 \dots \prec a_k$ is $k$,
corresponding to the number of arrows it traverses.  The \emph{size} of
the chain is the number of elements in it, namely, $k+1$.}  of a largest
chain.  Fortunately, it is always possible to use only $t$ parallel steps:

\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 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:
\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{center}\includegraphics{figures/clothesparallel.mps}\end{center}

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

So it remains to prove Theorem~\ref{thm:parallel}:
\begin{proof}
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}

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}

\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.
}
\medskip

\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.)

\section{Undirected Graphs}

Informally, an \emph{undirected graph}, or \emph{ugraph} for short, is a
bunch of dots connected by lines.  Here is an example of a graph:

\mfigure{!}{1.5in}{figures/graph-example}

Sadly, this definition is not precise enough for mathematical discussion.

\begin{definition}\label{graphdef}
A ugraph, $G$, consists of a set, $V$, called the \emph{vertices} of $G$,
and a collection, $E$, of two element subsets of $V$.  The elements of $E$
are called the \emph{edges} of $G$.
\end{definition}

The vertices correspond to the dots in the picture, and the
edges correspond to the lines.  Thus, the dots-and-lines diagram above
is a pictorial representation of the ugraph where:
\begin{eqnarray*}
V & = & \set{A, B, C, D, E, F, G, H, I} \\
E & = & \set{ \set{A, B}, \set{A, C}, \set{B, D}, \set{C, D},
              \set{C, E}, \set{E, F}, \set{E, G}, \set{H, I} }.
\end{eqnarray*}

It will be helpful to use the notation $\edge{A}{B}$ for the edge
$\set{A,B}$.  Note that $\edge{A}{B}$ and $\edge{B}{A}$ are different
descriptions of the same edge, since sets are unordered.

Two vertices in a graph are said to be {\em adjacent} if they are joined
by an edge, and an edge is said to be {\em incident} to the vertices it
joins.  The number of edges incident to a vertex is called the {\em
degree} of the vertex.  For example, in the graph above, $A$ is adjacent
to $B$ and $B$ is adjacent to $D$, and the edge $\edge{A}{C}$ is incident
to vertices $A$ and $C$.  Vertex $H$ has degree 1, $D$ has degree 2, and
$E$ has degree 3.

Ugraphs are essentially the same as symmetric relations or digraphs with a
reverse arrow for every arrow.  They have surprisingly many applications,
for example, in solving routing, schedule conflict, and molecular
structure problems.

In the remainder of this section, we'll refer to ugraphs simply as
\emph{graphs}.

\subsection{Some Common Graphs}

Some graphs come up so frequently that they have names.  The {\em complete
graph} on $n$ vertices, also called $K_n$, has an edge between every two
vertices.  Here is $K_5$:

\mfigure{!}{1.5in}{figures/complete-graph}

The {\em empty graph} has no edges at all.  Here is the
empty graph on 5 vertices:

\mfigure{!}{1.5in}{figures/empty-graph}

Another 5 vertex graph is $L_4$, the \emph{line graph} of length four:

\mfigure{!}{1in}{figures/path-graph}

And here is $C_5$, a \emph{simple cycle} with 5 vertices:

\mfigure{!}{1.5in}{figures/cycle}

\subsection{Isomorphism}

Two graphs that look the same might actually be different in a formal
sense.  For example, the two graphs below are both simple cycles with
4~vertices:

\mfigure{!}{1.5in}{figures/isomorphism}

But one graph has vertex set $\set{A, B, C, D}$ while the
other has vertex set $\set{1, 2, 3, 4}$.  If so, then the graphs are
different mathematical objects, strictly speaking.  But this is a
frustrating distinction; the graphs {\em look the same}!

Fortunately, we can neatly capture the idea of ``looks the same'' and
use that as our main notion of equivalence between graphs.  Graphs
$G_1$ and $G_2$ are {\em isomorphic} if there exists a one-to-one
correspondence between vertices in $G_1$ and vertices in $G_2$ such
that there is an edge between two vertices in $G_1$ if and only if
there is an edge between the two corresponding vertices in $G_2$.  For
example, take the following correspondence between vertices in the two
graphs above:
\[
\begin{array}{lll}
A \text{ corresponds to } 1 & \hspace{0.5in} & B \text{ corresponds to } 2 \\
D \text{ corresponds to } 4 & & C \text{ corresponds to } 3.
\end{array}
\]
Now there is an edge between two vertices in the graph on
the left if and only if there is an edge between the two corresponding
vertices in the graph on the right.  Therefore, the two graphs are
isomorphic.  The correspondence itself is called an {\em isomorphism}.

In more formal terms, if $G_1$ is a graph with vertices, $V_1$, and edges,
$E_1$, and likewise for $G_2$, then $G_1$ is {\em isomorphic} to $G_2$ iff
there exists a \textbf{bijective} function $f: V_1 \to V_2$ such that for
every pair of vertices $u, v \in V_1$:
\[
\edge{u}{v} \in E_1 \qiff \edge{f(u)}{f(v)} \in E_2.
\]
The function $f$ that defines the correspondence between
vertices is called an {\em isomorphism}.

Two isomorphic graphs may be drawn to look quite different.  For
example, here are two different ways of drawing $C_5$:

\mfigure{!}{1.5in}{figures/isomorphism-c5}

Isomorphism captures all the connection properties of a graph, abstracting
out what the vertices are called, what they are made out of, or where they
appear in a drawing of the graph.  So a property like ``having three
vertices of degree 4'' is preserved under isomorphism, while ``having a
vertex that is an integer'' is not preserved.  In particular, if one graph
has three vertices of degree 4 and another does not, they can't be
isomorphic.  Similarly, if one graph has an edge that is incident to
degree 8 vertex and a degree 3 vertex, then any isomorphic graph must also
have such an edge.

Looking for properties like these can make it easy to determine that two
graphs are not isomorphic, or to actually find an isomorphism between
them, if there is one.  In practice, this frequently makes the problem of
deciding if two graphs are isomorphic fairly easy.  However, no one has
yet found a \emph{general} procedure for determining whether two graphs
are isomorphic which is \emph{guaranteed} to run much faster than an
exhaustive (and exhausting) search through all possible bijections between
their sets of vertices.

Having an efficient isomorphism finding/testing procedure would, for
example, make it easy to search for a particular molecule in a database
given the molecular bonds.  On other hand, knowing there was no such
efficient procedure would also be valuable: it would justify the security
of a secure, reusable personal identification protocol that would be great
for internet commerce.  We'll explain this further in lecture on Friday.

\iffalse

Deleting some vertices and/or edges from a graph leaves a {\em subgraph}.
Formally, if a ugraphs, $G$, has vertices, $V$, and edges, $E$, then a
subgraph of $G$ is any ugraph with vertices $V' \subseteq V$ and edges $E'
\subseteq E \intersection (V' \cross V')$.

The computational problem of deciding whether two graphs are
isomorphic has a curious status.  The problem is usually easy in
practice and is suspected {\em not} to be NP-complete.\footnote{We'll
throw around the term {\em NP-complete} without defining it precisely.
The essential point is that no one has ever found an efficient
computational approach to any NP-complete problem.  Finding such an
approach or proving that none exists is the most famous open question
in computer science.} However, no one has yet found a provably
efficient way to determine whether two graphs are isomorphic.
\fi

\end{document}




\iffalse

\subsubsection{Number of Comparisons for Database Setup and Searching}

Consider a database of records with (distinct) numerical keys.
Suppose when records are inserted, some comparisons of these keys
occur, and the database maintains a record of these comparisons.
\begin{example}
  At one extreme, database could be kept totally sorted.
  The other extreme, totally unsorted.  
\end{example}
Each comparison costs something---the time to perform it.
Now suppose that after this setup, a search is to be performed on the
database to determine if a record with a particular key $k$ appears
anywhere in the database.
The search is supposed to be based on comparisons only.
Then the worst-case number of comparisons it takes depends on the
database partial order.
\begin{example}
  If the database is totally sorted, we can compare with middle
  elements, then middle of halves, etc.
  Binary search.
  Approximately $\log n$ comparisons needed.  
\end{example}
\begin{example}
  If database totally unsorted, then in the worst case, have to compare
  with every element.
  This is because each comparison with an element in the database gives no
  information about whether the sought element might be any of the
  others in the database.
\end{example}
In fact, if there is an antichain of size $k$, then in the worst case,
the new key could be any of the elements of the antichain.
So in the worst case, have to compare with all $k$, since each one
gives no information about the others.

See what Dilworth's theorem says about the database partial order.
For any $t$, either have a chain of length $> t$, or an antichain of
size $\geq \frac{n}{t}$.
Setting up a chain of length $> t$ requires at least $t$ comparisons.
The antichain requires at least $\frac{n}{t}$ comparisons.
So this says that we have to pay the cost sometime,
either we do $> t$ comparisons while setting up the database, or at
least $\frac{n}{t}$ in the worst case to search the database.

More refined analysis is possible.
That's because reliably setting up a long chain, say length $t$, in
the database actually requires \emph{more} than $t$ comparisons.
Because in the worst case, the comparisons won't come out in the most
desirable way, setting up a linear chain.
\begin{example}
  Compare $a$ and $b$, find out $a > b$.  Then compare $b$ and $c$.
  Would be nice if we found out $b > c$.  But we might not---might get
  $c > b$.  Then we don't have a chain of length $3$, but still an
  antichain of size $2$.  To get a chain, need an additional
  comparison.
\end{example}



\subsection{Logical Time in Distributed Systems}

One last use of partially ordered sets.  No use of powerful theorems
here---just showing an important place where a partially ordered set is
used as a mathematical model for a real computational situation.

A distributed computation consists of a sequence of ``steps''
occurring at each of a collection of ``processes''.  In addition to
performing local steps, the processes can send messages to each other.
So, have send steps and receive steps.

The processes are mostly working independently.
The only interaction is by means of the messages.
So, the only dependence among steps (feeding data from one to another,
using results to make decisions, etc.) is by:
\begin{enumerate}
\item Successive steps of same process.
\item Send vs. receive of same message.
\end{enumerate}
Taking reflexive transitive closure leads to partial order describing
the dependence among the computation steps.

Basic theorem: Any topological sort of this partial order 
describes a possible
sequence in which all the distributed steps could occur.
(No changes in what happens based on reordering incomparable steps.)

Example of what one might do with this partial order: Assign ``logical
time'' to every step.  Instead of an actual real time.  The time is
just any assignment of real numbers to the steps that is consistent
with the partial order: when one step precedes another in the partial
order, it must have a smaller logical time.

Behaves like real time: Formally, can reorder the steps in logical time
order, still consistent with the partial order.  Then the system is
behaving as if the logical time were actually real time.  Can be
maintained by simple distributed algorithm.  (Piggybacks time on message,
adjusts local times in response to what is heard in some messages.)
Although logical time isn't the same as actual real time, for many
purposes, it can be used as an adequate substitute.  Logical time can be
used, for example, to timestamp files to keep updated copies consistent.

This notion of logical time was invented by Lamport.  In 2000, the
original (late 1970s) paper containing this idea won an award for the
most influential paper ever, in distributed computing theory.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


% Problems based on this lecture:

% 1. (Some basic p.o. defs---minimal and maximal elements, lower and
% upper bounds, etc.) Section 6.6, Problem 20 and/or Section 6.2,
% Problem 22

% 2. (Parallel task scheduling)
% Recall the theorem from class that says that if a task graph is 
% a partial order with maximum chain length $t$, then the
% whole set of tasks can be performed by an unlimited collection of
% parallel processors in time $t$.
% This theorem was only for the case where all tasks take the same
% amount of time, say $1$ time unit.
% (a) Apply this theorem to produce an optimal schedule for the
% following task graph.
% [[[give some graph.  Don't need to make up a cute story---just some
% letters will do]]]
% (b) Generalize the theorem to the case where some tasks take $1$ time
% unit and others take $2$ times units.
% [[[Seems this should work by splitting the time-$2$ tasks into two
% tasks, using this to come up with a new length measure for chains,
% then applying the old theorem. 
% Should take some arguing that everything works, but it seems nice.???]]]

% 3. This doesn't actually use Dilworth's theorem.
% But the students will get to think about chains and antichains.

% Suppose a database is stored using a partial order on keys.  
% Your job is to design a search strategy to determine if a new key $k$
% appears in the database.  
% The only thing you are allowed to do in the strategy is to compare two
% keys (either two within the database, or the new key $k$ vs. a key in
% the database).
% The result of such a comparison adds extra edges to the partial order.
% The results of earlier comparisons can be used to determine which
% comparisons are made later.

% For each of the partial orders given below, describe a strategy for
% searching for an arbitrary key $k$ in the database.
% Your strategy should be designed to use the minimum number you can
% achieve, of comparisons, in the worst case.
% Say how many comparisons it takes in the worst case, and explain why.

% (a) Consists of $2$ antichains $A$ and $B$, each with $5$ elements. 
% Each of the $5$ elements of $A$ is known to be less than each of the
% $5$ elements of $B$.
% [[[Can draw diagram]]]

% [[[I get 10 comparisons.  Can achieve by direct comparison of new key
% with each element.  Doesn't seem we can better than, though---every
% key needs to be compared to $k$ directly or indirectly.  If we assume
% $k$ is between all the elements of $A$ and all the elements of $B$,
% then it seems we get no help from the existing edges.  Re-think this
%---if it looks too hard, we could default to the simpler case where we
% are only allowed to compare $k$ to an element of the database.]]]

% (b) Consists of $2$ chains, each of length $5$.  No relationships are
% known between elements of the $2$ chains, however.
% [[[Can draw diagram]]]

% [[[Here I get $6$, by treating the two chains separately.]]]

\fi

