\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}{Relations}

\section{Introduction}
To a Mathematician, a \emph{Relation} is simply a set of $n$-tuples.  To a
Computer Scientist, a relation is a collection of ``records'' with the same
``fields.''  A relation with $n$ fields is called \emph{$n$-ary}.

For example, a computer file directory defines a relation between file
names, file owners, groups associated with a file, last edit dates, sizes,
and access privileges.  That is, the directory defines a 6-ary relation.
It's elements could be represented simply as set of 6-tuples that could be
read off the rows of a directory listing like:
\[\begin{array}{|c|c|c|c|c|c|}
\text{name} & \text{owner} & \text{group} & \text{date} & \text{size} &
\text{privileges}\\
\hline
\texttt{.emacs} & \texttt{meyer} & \texttt{meyerstf} & \text{Sep  3} & 17335 &
\texttt{-rw-rw-r--}\\
\hline\texttt{ln3.tex} & \texttt{meyer} & \texttt{ta6042} & \text{Sep 13} & 4096 &
\texttt{-rw-r--r--}\\
\hline
&&\dots&&&
\end{array}\]

\iffalse
Particularly important on this upcoming Election Day is the ternary (3-ary)
relation of \emph{Cambridge voter records} whose elements are triples
consisting of the name of a voter registered in Cambridge, the voter's
birthday, and the voter's address.  In planning where to campaign, a
mayoral candidate in Cambridge might want the street addresses of all the
registered voters in the city.  These are exactly the addresses that are
the third elements of all the Cambridge voter records.  A mathematician
would refer to this set of third elements as the \emph{projection on the
third coordinate} of the voter records.  The set of ``possible values''
for this third coordinate, called the \emph{domain} of the third
coordinate, might be the set of \emph{all} Cambridge street addresses.
The set of voter addresses is not equal to the domain because some
addresses in Cambridge have no registered voters living at them.
\fi

Computer representations of $n$-ary relations underlie relational database
management and associated query languages such as SQL (\cf Rosen \S7.2).
However, in these Notes we'll focus on \emph{binary} (2-ary) relations.
These are the most widely used kind of relation in Mathematics.

\emph{Equality} is the most familiar binary relation.  Other familiar
binary relations are \emph{membership} (of elements in sets), various
orderings (\emph{smaller than, younger than, cheaper than}), reachability
relations (\emph{connected to, accessible from}), logical relations
(\emph{implies, equivalent}), compatibility relations (\emph{likes,
matches, fits into}).

In particular, we'll highlight two especially important kinds of relations:
\emph{equivalence relations} and \emph{partial orders}.  We'll also develop
some basic operations on binary relations such as relational composition
and inverse---generalizations of function composition and inverse---and
we'll consider computational representation of relations by matrices,
graphs, and adjacency lists.


\section{Binary Relations}

\begin{definition}
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 the Cartesian product, $A \cross B$, that is called the
\emph{graph of $R$}.
\end{definition}

A relation whose domain is $A$ and codomain is $B$ is also 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$.

For example, a ``registered for'' relation, $G$, between MIT student id's
and MIT subject numbers, might have the domain $\set{0,1,\dots,9}^9$ of
nine-digit sequences, the codomain consisting of all the subject numbers
that have been used in the past ten years, and graph
\[
\set{(d,c) \suchthat d\text{ is the id of a student registered for subject } c}.
\]

A relation with the property that every codomain element is related to
some domain element is called a \emph{surjective} relation.  It is also
called an \emph{onto} relation.  The ``registered for'' relation, $G$, for
example, is \emph{not} surjective since in this Spring term, no students are
currently registered for Fall-term-only courses (also, lots of courses
taught in the past ten years are no longer offered at all).

The set of elements that appear as second coordinates of pairs in a binary
relation is called the \emph{range} of the relation.  That is,
\[
\range{R} \eqdef \set{b \suchthat a\, R\, b \text{ for some } a \in
\domain{R}}.
\]
So \emph{a relation is surjective iff its range equals its codomain}.

A relation with the property that every domain element is related to some
codomain element is called a \emph{total} relation.  The ``registered for''
relation, $G$, for example, is also \emph{not} total, since most nine-digit
sequences have yet to be assigned to students.

The set of elements that appear as first coordinates of a binary relation
is called the \emph{domain of definition} of the relation.  That is,
\[
\text{domain-of-definition}(R) \eqdef \set{a \suchthat
  a\,R\,b \text{ for some } b \in \codomain{R}}.
\]
So \emph{a relation is total iff its domain equals its domain of
definition.}

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.

\subsection{Adjacency Sets}

Let $R$ be a binary relation from $A$ to $B$.  For any set, $C$, 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*}
When $C \subseteq A$, the set $CR$ is called the set of \emph{elements
adjacent to $C$}.  When $C \subseteq B$, the set $RC$ is the set of
\emph{elements incident to $C$}.

For example, $\range{R} = AR$ and $\text{domain-of-definition}(R) = RB$.

It's customary to write $aR$ rather than $\set{a}R$ when $a\in A$;
likewise for $Rb$.  For example, if $f$ is a partial function, then $af =
\set{f(a)}$.

\begin{definition}
The identity function, $\ident{A}$, on a set, $A$, is defined by the rule:
\[
\ident{A}(a) \eqdef a
\]
for all $a \in A$.  The \emph{identity relation}, $I_A$, on $A$ is defined
by the rule:
\[
a\,I_A\, b \qiff a = b.
\]
\end{definition}
Technically, the identity function on $A$, the identity relation on $A$,
and the equality relation on $A$ are the same.  We use the different
notations as an informal indication of how the relation is going to be
used.

\section{Equivalence Relations}

Equality is the fundamental example of an equivalence relation.  More
generally, 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.  In this case, we consider
two objects with the same value for this property to be ``equivalent.''

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.

Abstractly, we imagine that there is some function, $f$, which gives the
property value of any element in some domain, $A$.  For example, $A$ might
be the triangles in the Euclidena plane, and $f(a)$ might be the
side-lengths of triangle $a$.  Now we consider elements with the same
$f$-value to be equivalent.
\begin{definition}\label{deqv}
A binary relation, $R$, on a set, $A$, is an \emph{equivalence relation}
iff there is a function, $f$, with domain $A$, such that
\begin{equation}\label{Rf}
a_1\, R\, a_2 \qiff f(a_1) = f(a_2)
\end{equation}
for all $a_1,a_2 \in A$.
\end{definition}

Given any function, $f$, with domain, $A$, define the binary
relation $\equiv_f$ on $A$ by the rule:
\[
a_1 \equiv_f a_2 \qiff f(a_1) = f(a_2).
\]
Then Definition~\ref{deqv} immediately implies:
\begin{lemma*}
A binary relation is an \emph{equivalence relation} iff it equals
$\equiv_f$ for some $f$.
\end{lemma*}

So congruence of triangles is an equivalence relation because it is
$\equiv_f$ for the side-lengths function, $f$, mentioned above.
Representation-equivalence on lists of numbers also is indeed an equivalence
relation because it is $\equiv_f$ where $f$ maps a representation to the
set it represents.  That is, the two lists \texttt{(3 4 -2 177 5)} and
\texttt{(177 -2 3 5 4)} are representation-equivalent because
\[
f(\texttt{(3 4 -2 177 5)}) = \set{-2, 3, 4, 5, 177} = f(\texttt{(177 -2 3 5 4)}).
\]

\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 $f:A\to B$ such that equality on
$A$ equals $\equiv_f$.


\subsection{Integers modulo \emph{m}}
Modular arithmetic plays a central role in Number Theory and more recently
in modern Cryptography.  In particular, modular arithmetic is central to
the definition and efficient implementation of the RSA encryption scheme,
which currently is the most widely used system for coding and decoding
private data that must be transmitted over public channels.

\begin{definition}
If $a,b,m \in \integers$ and $m \ge 2$, then \emph{$a$ is equivalent to $b$
modulo $m$} iff $m \divides (a-b)$.  We write
\[
a \equiv b \pmod m
\]
to indicate that $a$ is equivalent to $b$ modulo $m$.
\end{definition}
Recall that the notation $m \divides n$ means that $m$ \emph{divides} $n$,
namely, there is an integer, $k$, such that $n=km$.

We'll prove the basic properties of $\equiv \pmod m$ by recalling
definitions of \emph{quotients} and \emph{remainders}.
\begin{lemma}\label{qr}
For any integers, $a,m$ with $m>0$, there are unique integers $0\le r <m$
and $q$ such that $a = mq+r$.  Here $r$ is called the \emph{remainder},
$\remainder_m(a)$, and $q$ is called the \emph{quotient}, $\quotient_m(a)$,
of $a$ divided by $m$.
\end{lemma}
Lemma~\ref{qr} is a familiar fact about integers which we'll accept
without proof.  (The only hard part in proving Lemma~\ref{qr} is deciding
what more obvious properties of integers are ok to assume in the proof.)

\begin{theorem}
Equivalence modulo $m$ is an equivalence relation.

\begin{proof}
It's easy to check that $m \divides (a - b)$ iff $\remainder_m(a) =
\remainder_m(b)$.  This means that $\equiv \pmod m$ is the same as the
equivalence relation $\equiv_f$ where $f = \remainder_m$.
\end{proof}
\end{theorem}

Equivalence modulo $m$ interacts nicely with the basic arithmetic
operations.  Namely, it's easy to verify from the definitions that:
\begin{lemma*}
If $a_1 \equiv b_1 \pmod m$  and $a_2 \equiv b_2 \pmod m$, then
\begin{eqnarray}
a_1 + a_2 & \equiv & b_1 + b_2 \pmod m\label{mod+}\\
a_1 \cdot a_2 & \equiv & b_1 \cdot b_2 \pmod m.\label{mod*}
\end{eqnarray}

\begin{proof}
Suppose $m \divides (a_1-b_1)$ and $m \divides (a_2-b_2)$.  So
$m \divides x(a_1-b_1) + y(a_2-b_2)$ for all $x,y \in \integers$.

Letting $x=y=1$, we have that $m\divides (a_1-b_1)+(a_2-b_2) =
(a_1+a_2)-(b_1+b_2)$, proving~(\ref{mod+}).

Letting $x=a_2, y=b_1$, we have that $m\divides a_2(a_1-b_1)+b_1(a_2-b_2)
= a_1a_2-b_1b_2$, proving~(\ref{mod*}).
\end{proof}

\end{lemma*}

It follows that if we have a series of additions and multiplications of
integers, and we are only interested in knowing the remainder of the
result after division by $m$---which is the case, for example, in the RSA
cryptosystem---then at any stage we can replace an intermediate result
with an equivalent number modulo $m$, without changing the remainder of
the final answer.

An equivalence relation that interacts with operations in this way is
called a \emph{congruence} for these operations.  That's why equivalence
$\mod m$ is also referred to as ``congruence'' $\pmod m$.

% removed because did not cover RSA before this, also
% briefly talked about it in class
\iffalse
This is the basis of the fast exponentiation algorithm presented in
the next subsection.

\subsubsection{Fast Exponentiation}

Recall that for RSA we wanted to compute the remainder of $x^a$\ on
division by $b$---that is, the equivalence class $\bmod b$ of $x^a$.

In the section on recursive algorithms, we already saw how to reduce
the number of multiplications substantially.  But there is still a
problem: $x^a$ is a really big number.  It is bigger than $2^a$, so
has $2^{2^{128}}$ bits if we use a 128-bit key $a$.  It will take a
long time to write this number down (if we could find a place to fit
it).  

But notice that we only care about the remainder modulo $b$.  So using
modular arithmetic we can solve the large-number problem.  Whenever
the number we are computing gets too big, replace it with a smaller
representative of the same equivalence class.  What is the smallest
representative?  The remainder on division by $b$.  We've argued that
switching representatives doesn't change the answer.  But now all our
math is done on number smaller than $b$, that is, 128-bit numbers.
\fi


\subsection{Partitions}

A division of a set into a collection of nonempty, nonoverlapping
pieces is called a \emph{partition} of the set.  The pieces are called
\emph{blocks} of the partition.  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, that is, $B_1 \intersect B_2 = \emptyset$.\label{B1B2}
\end{enumerate}
\end{definition}

For example, we can partition the reals, $\reals$, 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 ``floor'' function mapping $r$ to the largest integer $\le r$.

\begin{example}\label{part4}
Similarly, 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}

Note that if $\mathcal{A}$ partitions $A$, then
Definition~\ref{part}.\ref{AU} implies that every element $a \in A$
belongs to some block, and Definition~\ref{part}.\ref{B1B2} implies that
this block is \emph{unique}.  Let $[a]_{\mathcal{A}}$ be the unique block
with $a$ in it.

The relation of \emph{being in the same block} is obviously an equivalence
relation.  That is,
\begin{definition}
For any partition, $\mathcal{A}$, of a set, $A$, define the relation
$\text{mkequiv}(\mathcal{A})$ on $A$ by the rule:
\[
a_1\, \text{mkequiv}(\mathcal{A})\, a_2  \qiff [a_1]_{\mathcal{A}} =
[a_2]_{\mathcal{A}}.
\]
\end{definition}

\begin{theorem}\label{mke}
Let $\mathcal{A}$ be a partition of a set, $A$, and let $E \eqdef
\text{mkequiv}(\mathcal{A})$.  Then $E$ is an equivalence 
relation on $A$.

\begin{proof}
The relation, $E$, is simply $\equiv_f$, where $f(a) \eqdef
[a]_\mathcal{A}$.
\end{proof}
\end{theorem}

Conversely, any equivalence relation, $E$, on a set, $A$, can be used
to partition $A$ into blocks.
\begin{definition}
Let $E$ be an equivalence relation on a set, $A$.  Define
\[
\text{mkpartition}(E) \eqdef \set{aE \suchthat a \in A}.
\]
The set $aE$ is called the \emph{equivalence class of $a$ under $E$}.  An
alternative notation for the equivalence class, $aE$, is ``$[a]_E$.''
\end{definition}

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

\begin{theorem}\label{mkp}
If $E$ is an equivalence relation on a set, $A$, then
$\text{mkpartition}(E)$ is a partition of $A$.

\begin{proof}
Let $\mathcal{A} \eqdef \text{mkpartition}(E)$.  We want to verify that
$\mathcal{A}$ is a partition of $A$.

Since $E$ is an equivalence relation on $A$, there is a function,
$f$, such that $E$ is $\equiv_f$.  That is, $a\,E\,a'$ iff $f(a)=f(a')$, so
\begin{equation}\label{aEf}
aE = \set{a' \suchthat f(a) = f(a')},
\end{equation}
and we conclude immediately from~(\ref{aEf}) that
\begin{equation}\label{fa1}
f(a_1) = f(a_2)  \qimplies a_1E = a_2E.
\end{equation}

But from~(\ref{aEf}), we have $a \in aE$ because $f(a) = f(a)$.  This
implies that each set $B \in \mathcal{A}$ is nonempty and that
$\lgunion_{B \in \mathcal{A}}B = A$.  So we need only show that if
$a_1E$ and $a_2E$ are not disjoint, then $a_1E = a_2E$.

So suppose $a_1E$ and $a_2E$ are not disjoint, that is, there is an $a \in
a_1E \intersect a_2E$.  Now since $a \in a_1E$, we have from~(\ref{aEf})
that $f(a_1) = f(a)$; likewise $f(a_2) = f(a)$.  So $f(a_1) = f(a_2)$, and
from~(\ref{fa1}) we conclude $a_1E = a_2E$.
\end{proof}
\end{theorem}

So Theorem~\ref{mke} implies that we can start with a partition, and use
it to define an equivalence, and Theorem~\ref{mkp} implies that we can
start with an equivalence and use it to define a partition.  Together,
these results reveal that equivalence relations and partitions are
different ways of describing the same concept.  Formally, we observe that
these constructions are inverses of each other and so determine an exact
correspondence (a bijection) between equivalence realtions and partitions:

\begin{corollary}\label{AEA}
Let $\mathcal{A}$ be a partition and $E$ and equivalence relation.  Then,
\begin{eqnarray*}
\text{mkequiv}(\text{mkpartition}(E)) &=&  E,\\
\text{mkpartition}(\text{mkequiv}(\mathcal{A})) &=&  \mathcal{A}.
\end{eqnarray*}
\end{corollary}

\begin{problem}
Prove Corollary~\ref{AEA}.
\end{problem}

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.


\section{Properties of 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,b\in A$,
\[
a\, R\, b \qimplies b\, 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 (since $\emptyset \subset \set{0}$ but
$\set{0} \not\subset \emptyset$).
\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$.  This relation is
reflexive since $p \implies p$.  It is also transitive, since if $p
\implies q$ and $q \implies r$, then $p \implies r$.  However, it isn't
symmetric, since, for example, $\texttt{false} \implies \texttt{true}$, but
not $\texttt{true} \implies \texttt{false}$.
\end{example}

\begin{example}\label{finite}
Let $R_3$ be the relation on sets 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$.}

\end{example}

\begin{example}\label{dist}
Let $R$ be the relation on complex numbers such that $a\, R\, b$ iff the
distance from $a$ to $b$ in the complex plane is $\le 1$, that is, $\abs{a
- b} \le 1$.  Then $R$ is reflexive and symmetric, but not transitive
(because $1\,R\,2$ and $2\,R\,3$, but not $1\,R\,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*}
Every equivalence relation is reflexive, symmetric, and transitive.

\begin{proof}
Suppose $E$ is $\equiv_f$ for some function, $f$ with domain $A$.

To show that $E$ is transitive, suppose $a\, E\, b$ and $b\, E\, c$.  This
implies that $f(a) = f(b)$ and $f(b)=f(c)$.  It follows (from transitivity
of equality) that $f(a) = f(c)$, which means that $a\, E\, c$.

The proofs of reflexivity and symmetry follow the same format.
\end{proof}
\end{lemma*}

It's useful to know that these three properties completely characterize
equivalence relations.  The following Theorem provides an elegant,
axiomatic characterization of equivalence relations.  In fact, equivalence
relations are usually \emph{defined} as relations satisfying
Theorem~\ref{rst}---for example, Rosen uses this definition.

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

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

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_1R = a_2R \qiff a_1\, R\, a_2
\end{equation}

So first suppose $a_1R = a_2R$.  Since $R$ is \textbf{reflexive}, we have
$a \in aR$ for all $a \in A$.  In particular, $a_2 \in a_2R$.  But $a_1R =
a_2R$, we have $a_2 \in a_1R$, that is, $a_1\,R\,a_2$ by definition of
$a_1R$.  This proves~(\ref{a1R}) from left to right.

Conversely, suppose $a_1\, R\, a_2$.  Now let $a$ be an element of $a_2R$,
so by definition, $a_2\, R\, a$.  Since $R$ is \textbf{transitive}, we
have $a_1\, R\, a$, which implies that $a \in a_1R$, by definition.
Since $a$ was an arbitrary element of $a_2R$, we conclude that $a_2R
\subseteq a_1R$. 
But since $a_1\, R\, a_2$ and $R$ is \textbf{symmetric}, we also have
$a_2\, R\, a_1$.  Repeating the previous argument, we similarly conclude
that $a_1R \subseteq a_2R$.  Therefore, $a_1R = a_2R$.  This
proves~(\ref{a1R}) from right to left.
\end{proof}

\end{theorem}

Note that all 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 much stronger
theorem than you thought, for example, if you didn't use reflexivity anywhere in
the proof of Theorem~\ref{rst}, you would be proving that any symmetric,
transitive relation is an equivalence relation, which is false.  So a
proof that failed to use reflexivity must be mistaken.

\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

The 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.

\textbf{Quick exercise:} 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.  Prove
that mutual reachability is an equivalence relation.  Can you describe a
function, $f$, such that mutual reachability equals $\equiv_f$?
\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 \emph{every} function, $f$.  Off hand, this requires a
daunting analysis in order to rule out all possible functions.  But
Theorem~\ref{rst} lets us show a relation is not an equivalence simply by
finding two or three elements of the domain where the conditions of
Theorem~\ref{rst} 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.

The most general example of a partial order is essentially the subset
relation, $\subset$ or $\subseteq$, on sets.  (Here, $S \subseteq T$ means
that $S$ is a subset of $T$ including the case that $S = T$, while $S
\subset T$ means $S$ is a subset of $T$ and $S \neq T$.)  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 $g(a)$ as the \emph{set} of particular, interesting properties that $a$
has.  Then we relate different elements according to how their interesting
properties compare.

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

Any relation that arises in this way is called a partial order.

\begin{definition}\label{po-def}
A relation, $R$, on a set, $A$, is a \emph{partial order} providing there
is a function, $g$, from $A$ to a collection of sets, such that
\begin{equation}\label{po-eqn}
a_1Ra_2 \qiff g(a_1) \subset g(a_2)
\end{equation}
for all $a_1 \neq a_2 \in A$.
\end{definition}

Given any function, $g$, from $A$ to a collection of sets,
define the binary relation $\prec_g$ on $A$ by the rule:
\[
a_1 \prec_g a_2 \qiff g(a_1) \subset g(a_2),
\]
for all $a_1, a_2 \in A$.  Then Definition~\ref{po-def} immediately
implies:

\begin{lemma}\label{po-lem}
A binary relation, $R$, on a set, $A$, is a \emph{partial order} iff there
is a function, $g$, such that $R$ agrees with $\prec_g$ for every pair of
distinct elements.  That is,
\[
a_1\, R\, a_2 \qiff a_1 \prec_g a_2
\]
for all $a_1 \neq a_2 \in A$.
\end{lemma}

Another immediate consequence of Definition~\ref{po-def} is that the
subset relation itself is a partial order.  Specifically, if $\mathcal{A}$
is any collection of sets, then the proper subset relation $\subset$ is a
partial order on $\mathcal{A}$.  To prove this, we let $g$ be the identity
function on $\mathcal{A}$.  Then $\prec_g$ is the same relation as
$\subset$, and so trivially satisfies the condition~(\ref{po-eqn}) on $R$.
The ordinary subset relation, $\subseteq$, is also a partial order, since
it agrees with $\prec_g$ for $a_1 \neq a_2$.

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 $g(r) \eqdef \set{t \in \reals \suchthat t<r}$.
It follows that
\[
r_1 < r_2 \qiff g(r_1) \subset g(r_2),
\]
so $<$ satisfies the condition~(\ref{po-eqn}) on $R$ that defines partial
orders.  Likewise, the relation, $\le$, is a partial order because
\[
r_1 \le r_2 \qiff g(r_1) \subset g(r_2),
\]
for all reals $r_1 \neq r_2$.

Notice that our general definition of partial order leaves unspecified
whether elements are related to themselves.  For example, every real
number is $\le$ to itself, that is, $\le$ is a reflexive relation.

\begin{definition}
A partial order is called \emph{weak} iff it is reflexive.
\end{definition}

Of course $<$ has the opposite property: no element is strictly less than
itself.

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

So the $<$-relation and the $\subset$-relation are strict partial orders,
while $\le$ and $\subseteq$ are weak partial orders.  In an arbitrary
partial order, some elements may be related to themselves and some not, so
it may be neither weak nor strict.
\begin{problem}
\bparts

\ppart Prove that a relation, $R$, on a set, $A$, is a \emph{strict}
partial order providing there is a function, $g$, from $A$ to a collection
of sets, such that
\begin{equation}\label{str-eqn}
a_1\,R\, a_2 \qiff g(a_1) \subset g(a_2)
\end{equation}
for all $a_1, a_2 \in A$ (even if $a_1 = a_2$).

\ppart Remember that a partial function, $g$, is an injection iff
\[
g(a_1) = g(a_2) \qimplies a_1 = a_2
\]
for all $a_1,a_2$ in the domain of definition of $g$.

Prove that a relation, $R$, on a set, $A$, is a \emph{weak} partial order
providing there is an \emph{injection}, $g$, from $A$ to a collection of
sets such that
\begin{equation}\label{wk-eqn}
a_1\,R\, a_2 \qiff g(a_1) \subseteq g(a_2)
\end{equation}
for all $a_1, a_2 \in A$.

\ppart Give an example showing that the result of the previous part would
not hold if the condition that $g$ is an injection was dropped.

\solution{
Let $A = \set{1,2}$ and suppose $g(1)=g(2)$.  Then by~(\ref{wk-eqn}), we
have that $1R2$ and $2R1$, but $1 \neq 2$, so $R$ is not antisymmetric and
hence is not a partial order.
}

\eparts

\end{problem}

Two more examples of partial orders are worth mentioning:

\begin{example}\label{supset}
Let $A$ be some family of sets and define $a_1 \prec a_2$ iff $a_1
\supset a_2$.  Then $\prec$ is a strict partial order.
\begin{proof}
Define $g(a) \eqdef \bar{a}$, where $\bar{a}$ is the complement of
$a$, and note that
\[
[a_1 \prec a_2] \qiff [a_1 \supset a_2] \qiff [\bar{a_1} \subset
\bar{a_2}] \qiff [g(a_1) \subset g(a_2)].
\]
\end{proof}
\end{example}

\begin{example}\label{divides}
Let $A$ be the set of natural numbers and define $m \preceq n$ iff $m
\divides n$.  Then $\preceq$ is a weak partial order.
\begin{proof}
Let $g(a) \eqdef\text{ the set of natural numbers that divide } a$.
\end{proof}
\end{example}

\textbf{Warning:} Rosen defines ``partial order'' to mean weak partial
order.  He would not consider $<$~or~$\subset$ to be partial orders.


\subsection{Total Orders}

The familiar numerical ordering relations have an important special property:
given any two real numbers, one will be at least as large as the other.
That is, any two elements are ``comparable:''
\begin{definition}
Let $R$ be a binary relation on a set, $A$, and let $a_1 \neq a_2$ be two
elements of $A$.  Then $a_1$ and $a_2$ are \emph{comparable} with respect
to $R$ iff ($a_1\, R\, a_2\text{ or } a_2\, R\, a_1$).  The elements $a_1$ and
$a_2$ are said to be \emph{incomparable} iff they are not comparable.
A partial order under which every two elements are comparable is called a
\emph{total order}.\footnote{The word ``total'' used in reference to a
partial order is different from its use in reference to total relations.
For example, any reflexive partial order is a total relation but need not
be a total order.}
\end{definition}
So $<$ and $\le$ are total orders on $\reals$.  On the other hand, the
subset relation is generally \emph{not} total: $\set{0,1}$ and $\set{1,2}$
are incomparable under $\subseteq$ since neither is a subset of the other.

\subsection{Properties of Partial Orders}

We've already observed that $\subset$ is transitive, which implies that
any relation $\prec_g$ is transitive.  So Lemma~\ref{po-lem}
immediately implies:
\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 function $g$ on $A$
satisfying condition~(\ref{po-eqn}).  Then for $a \neq b \in A$, we have
$a R b \conj b R a$ iff $g(a) \subset g(b) \conj g(b) \subset g(a)$, which
is impossible.  So $a R b \conj b R a$ can hold only if $a=b$.
\end{proof}
\end{lemma}

These two properties 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 right to left direction, assume $R$ is transitive and
antisymmetric.  Define
\begin{equation}\label{ga}
g(a) \eqdef Ra \union \set{a}.
\end{equation}
We will show that $R$ satisfies condition~(\ref{po-eqn}) that defines
partial order, that is, we will show that if $a \neq b \in A$, then
\begin{equation}\label{rgb}
aRb  \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~(\ref{ga})},\\
    & \qimplies a \in Rb \union \set{b} & \text{by def of~$g(b)$},\\
    & \qimplies a \in Rb & \text{since $a \neq b$},\\
    & \qimplies aRb & \text{by def of $Rb$}.
\end{align*}

To prove~(\ref{rgb}) from left to right, we suppose $a\, R\, b$.  This means that
$a \in Rb$ and so $a \in g(b)$.

Now we show first that $g(a) \subseteq g(b)$.  Since $a \in g(b)$, we need
only show that if $a \neq a'$ and $a' \in g(a)$, then $a' \in g(b)$.  But
if $a' \in g(a) \eqdef Ra \union \set{a}$, then because $a'\neq a$, we
have that $a' \in Ra$, that is, $a'Ra$.  Now since $R$ is
\textbf{transitive}, we conclude from $a'Ra$ and $aRb$ that $a'Rb$, and
hence $a' \in Rb \subseteq g(b)$, as claimed.

Finally, we 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
Ra \union \set{a}$.  Then because $a \neq b$, we conclude that $b \in Ra$,
that is, $bRa$.  So $bRa$ and $aRb$ 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.
\end{proof}
\end{theorem}

In the literature, partial orders are usually \emph{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.

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

Strict partial orders also have their own axiomatic characterization.

\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, $R$, on a set $A$ is a strict partial order iff it is
transitive and asymmetric.
\end{theorem}

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

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

For weak partial orders, we often write an ordering-style symbol like
$\preceq$ instead of a letter symbol like $R$.  Likewise, we use $\prec$
to indicate a strict partial order.  This lets us write $b \succeq a$ to
mean $a \preceq b$ and likewise for $\succ$.

\begin{problem}
Let $R$ be a binary relation on a set, $A$.
\bparts

\iffalse
\ppart Verify that $R$ is antisymmetric iff
\[
[a \neq b \text{ and } a\, R\, b] \qimplies \neg[b\, R\, a],
\]
for all $a,b\in A$.  Conclude that asymmetry implies antisymmetry.
\fi

\ppart Prove that $R$ is a strict partial order iff it is transitive and
irreflexive.

\ppart Prove that if $R$ is a partial order, then $R - I_A$ is a strict
partial order.

\eparts

\end{problem}

We'll continue discussing partial orders after we examine some of the ways
to represent and operate on relations.

\section{Representation}

There are a several standard ways of representing relations.  The
different representations tend to highlight different properties of the
relation.  For computations involving relations, different representations
typically offer differing efficiencies.  For finite relations, we usually
use some method that explicitly enumerates the graph of the relation such
as lists of pairs, adjacency lists, matrices, and graphs.

\subsection{Lists of pairs}


A finite relation from set $A$ to set~$B$ can be represented by a list of
all the pairs in its graph.

\begin{example} \label{ex:0123-abc}
Let $N$ be the relation from the set of integers $\set{0, 1, 2, 3}$ to the
set of characters $\set{\texttt{a,b,c}}$ with graph
\[
\set{(0,\texttt{a}), (0, \texttt{c}), (1, \texttt{c}), (2, \texttt{b}),
(1,\texttt{a})}.
\]
Then $N$ would be represented by the list
\begin{quote}
\texttt{((0 a) (0 c) (1 c) (2 b) (1 a))}.
\end{quote}
\end{example}

\begin{example}
The divisibility relation on natural numbers $\set{1,\dots,12}$ is
represented by the list:
\[\begin{array}{l}
\texttt{((1 1) (1 2) (1 3) (1 4) (1 5) (1 6) (1 7) (1 8) (1 9)}\\
\texttt{ (1 10) (1 11) (1 12) (2 2) (2 4) (2 6) (2 8) (2 10) (2 12)}\\
\texttt{ (3 3) (3 6) (3 9) (3 12) (4 4) (4 8) (4 12) (5 5) (5 10)}\\
\texttt{ (6 6) (6 12) (7 7) (8 8) (9 9) (10 10) (11 11) (12 12))}xo
\end{array}\]
\end{example}

The relational properties we have defined all have straightforward
descriptions in terms of the list representation.  For example,
to test if a relation is reflexive, we can check its list representation
to be sure its list contains every pair of the form $(a\ a)$.  We can
describe symmetry and transitivity similarly:

\begin{description}

\item[Reflexivity:] The list contains all pairs $(a\ a)$ for $a \in A$.

\item[Symmetry:] If the list contains $(a\ b)$ then it also contains $(b\ a)$.

\item[Transitivity:] If the list contains $(a\ b)$ and $(b\ c)$ then it
contains $(a\ c)$.
\end{description}

\subsection{Adjacency Lists}

In an adjacency list representation, we list, for each element in the
domain, the elements in the codomain that it is related to.
\begin{example}
Let $N$ be the relation from Example~\ref{ex:0123-abc}.
Then $N$ would be represented by the adjacency list
\begin{quote}
\texttt{((0 (a c)) (1 (c a)) (2 (b)) (3 ()))}
\end{quote}
\end{example}

Note that the adjacency list representation of a relation, $R$, is 
simply the list-of-pairs representation of the function on the domain of
$R$ that maps $a$ to the set $aR$.

\subsection{Connection Matrices}

Connection matrices are Boolean (0-1-valued) matrices that provide a
convenient computer representation for binary relations.  The
\emph{connection matrix} for a relation, $R$, from $A$ to $B$ has rows
labelled with the elements of $A$, columns labelled with elements of $B$,
and there is a 1 in row $a$, column $b$, iff $a\, R\, b$.  Otherwise the
$(a,b)$ entry is~0.
\begin{example}
The relation, $N$, from Example~\ref{ex:0123-abc} is represented by the
matrix
\[
\begin{array} {r|ccc}
& \texttt{a}& \texttt{b}&  \texttt{c} \\ 
\hline
0&1& 0&  1\\
1&1& 0&  1\\
2&0& 1&  0\\
3&0& 0&  0
\end{array}
\]
\end{example}

\begin{example}\label{divis12}
The divisibility relation over $\{1,2,\dots,12\}$ is 
represented by the matrix
\[
\begin{array}{r|cccccccccccc}
        &1  &2  &3  &4  &5  &6  &7  &8  &9 &10 &11 &12\\
      \hline
      1 &1  &1  &1  &1  &1  &1  &1  &1  &1  &1  &1  &1\\
      2 &0  &1  &0  &1  &0  &1  &0  &1  &0  &1  &0  &1\\
      3 &0  &0  &1  &0  &0  &1  &0  &0  &1  &0  &0  &1\\
      4 &0  &0  &0  &1  &0  &0  &0  &1  &0  &0  &0  &1\\
      5 &0  &0  &0  &0  &1  &0  &0  &0  &0  &1  &0  &0\\
      6 &0  &0  &0  &0  &0  &1  &0  &0  &0  &0  &0  &1\\
      7 &0  &0  &0  &0  &0  &0  &1  &0  &0  &0  &0  &0\\
      8 &0  &0  &0  &0  &0  &0  &0  &1  &0  &0  &0  &0\\
      9 &0  &0  &0  &0  &0  &0  &0  &0  &1  &0  &0  &0\\
      10&0  &0  &0  &0  &0  &0  &0  &0  &0  &1  &0  &0\\
      11&0  &0  &0  &0  &0  &0  &0  &0  &0  &0  &1  &0\\
      12&0  &0  &0  &0  &0  &0  &0  &0  &0  &0  &0  &1\\
    \end{array}
\]
\end{example}

Again, the relational properties we have defined can be described in terms
of the matrix representation for relations.  Namely, we look for the
following matrix properties:
\begin{description}

\item[Reflexivity:] 
The major (upper-left to lower-right) diagonal is all 1.
\item[Symmetry:] 
The matrix is unchanged by reflection about the major diagonal.
\item[Transitivity:] 
Not so obvious\dots
\end{description}


\subsection{Digraphs} 

A \emph{directed graph}, or \emph{digraph} for short, is exactly the same
as the graph of a binary relation, $R$, from $A$ to $B$, but we picture
the digraph geometrically by assuming there are different points on a
plane for the different elements of $A$ and $B$, with an arrow from the
point for $a$ to the point for $b$ exactly when $a\, R\, b$.

\begin{example}
Let $N$ be the relation from Example~\ref{ex:0123-abc}.  Then $N$ is
pictured by the following digraph:
\begin{center}\includegraphics{figures/0123abc.mps}\end{center}
\end{example}

Digraph pictures are mainly used for relations on a finite set $A$.

\begin{example}
\begin{samepage}
The divisibility relation over $\set{1,2,\dots,12}$ from
Example~\ref{divis12} is represented by the digraph
\begin{center}
\includegraphics{figures/divide12.mps}
\end{center}
\end{samepage}
\end{example}

Again, relational properties have natural explanations as geometric
properties.  For example:
\begin{description}

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

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

\item[Symmetry:] 
All edges are bidirectional.

\item[Transitivity:] 
Short-circuits---for any path (sequence of consecutive arrows) through
the graph, there is a single arrow from the first to the last node.
\end{description}


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

\begin{definition}
A \emph{path in a relation}, $R$, is a sequence $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 as a digraph, a path $a_0,\dots,a_k$ in $R$ 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).  A \emph{point-simple
path} is a path with no repeated points.  Likewise, an \emph{edge-simple
path} is a path in which no edge is used twice.  We usually just say
``simple path'' when we mean point-simple path (though Rosen uses ``simple
path'' to mean edge-simple.)

We can define some new relations based on paths.  Let $R$ be a relation on
a set, $A$.  For $n \in \naturals$ and $a,b \in A$, define relations
$R^{(n)}$, $R^{(\le n)}$, $R^+$, and $R^*$ on $A$ by the conditions that
\begin{eqnarray*}
a\, R^{(n)}\, b &\eqdef& \exists\mbox{ a path in $R$ from $a$ to $b$ of length $n$},\\
a\, R^{(\le n)}\, b &\eqdef& \exists\mbox{ a path in $R$ from $a$ to $b$ of
length $\le n$},\\
a\, R^+\, b &\eqdef& \exists\mbox{ a path in $R$ from $a$ to $b$ of length
$\ge 1$},\\
a\, R^*\, b &\eqdef& \exists\mbox{ a path in $R$ from $a$ to $b$}.\\
\end{eqnarray*}

Notice that $R^{(0)} = I_A$ because of the length-zero paths.  Also, $R =
R^{(1)}$ by definition of length-one path.

$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 contains $R$ (because of the length-one
paths).  $R^+$ is called the \emph{positive-length path relation}; it also
contains $R$ and is transitive.


\section{Operations on Relations}

\subsection{Set operations}
Since relations, more precisely their graphs, are sets, we automatically
inherit various operations on relations from set operations.  For example, 
the intersection, $R_1 \intersect R_2$ of relations $R_1, R_2$ is defined
to be the relation with
\begin{eqnarray*}
\graph{R_1 \intersect R_2} &\eqdef& \graph{R_1} \intersect \graph{R_2},\\
\domain{R_1 \intersect R_2} &\eqdef& \domain{R_1} \intersect
\domain{R_2},\\ \codomain{R_1 \intersect R_2} &\eqdef& \codomain{R_1}
\intersect \codomain{R_2}.
\end{eqnarray*}
A similar definition holds for $R_1 \union R_2$.

Intersections preserve several of the relational properties we have
considered.  It follows immediately from the definitions that if $R_1$ and
$R_2$ are both transitive, then so is $R_1 \intersect 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 \intersect R_2$.
Likewise for being an equivalence relation.

Closely related to intersection is \hyperdef{def}{restrictrel}{the
restriction of a relation}.  If $R$ is a binary relation, on a set, $A$,
and $A_0 \subseteq A$ is a subset of $A$, then the \emph{restriction, $R
\restrict A_0$, of $R$ to $A_0$} is the binary relation with domain $A_0$
in which the elements of $A_0$ are related as they were under $R$.
Formally, the restriction is simply given by
\[
\graph{R \restrict A_0} \eqdef \graph{R} \intersect (A_0 \cross A_0).
\]

Restrictions also preserve transitivity, symmetry, reflexivity, and
antisymmetry, and so if $R$ is a partial order, so is any restriction of
$R$; likewise for being an equivalence relation.

\begin{problem}
Show that restrictions preserve the property of being a total order.  Show
that intersections do not always preserve totality.
\end{problem}



The union operation allows us to write an equation that describes the
obvious connection between the path relations $R^+$ and $R^*$ and the
length-$n$ path relations, $R^{(n)}$.  Namely,
\begin{eqnarray}
R^* &=& R^{(0)} \union  R^{(1)} \union R^{(2)} \union \cdots,\label{R*u}\\
R^+ &=&                 R^{(1)} \union R^{(2)} \union \cdots.\label{R+u}
\end{eqnarray}

The complement, $\bar{R}$, of a relation, $R$ is defined to be the
relation with the same domain and codomain as $R$ such that
\[
\graph{\bar{R}} \eqdef \domain{R}\cross\codomain{R} - \graph{R}.
\]

We similarly inherit relations on relations.  For example, the
\emph{containment relation} on relations is defined by the rule that $R_1$
is contained in $R_2$, in symbols, $R_1 \subseteq R_2$, iff the domain,
codomain and graph of $R_1$ are subsets, respectively, of the domain,
codomain and graph of $R_2$.  Sometimes the assertion ``$R_1$ implies
$R_2$'' is used to mean that $R_1$ is contained in $R_2$.  The reason is
that if $R_1 \subseteq R_2$, then
\[
a\, R_1\, b \text{  implies  } a\, R_2\, b.
\]

For example, we can now characterize $R^+$ as the \emph{smallest} (under
$\subseteq$) relation with the properties that
\begin{enumerate}
\item $R \subseteq R^+$,
\item $R^+$ is transitive.
\end{enumerate}
For this reason, $R^+$ is called the \emph{transitive closure} of $R$.
Similarly, the path relation, $R^*$, is called the \emph{reflexive,
transitive closure} of $R$.

\subsection{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
\land a_2\, R_2\, b_2.
\end{eqnarray*}

\begin{example}
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.

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

\subsection{Inverse}

The inverse, $R^{-1}$, of a relation, $R$, from $A$ to $B$ is just $R$
``turned backwards.''  Namely, $R^{-1}$ the relation from $B$ to $A$ such that
\[
b\, R^{-1}\, a \qiff a\, R\, b.
\]

The inverse operation has simple explanations in terms of the various
representations for relations.  For example, the connection matrix for
$R^{-1}$ is simply the \emph{transpose} (reflection around the major
diagonal) of the connection matrix for~$R$.  Note that the inverse of a
relation is not the same thing as the inverse of the matrix
representation.

The digraph picture for $R^{-1}$ is simply the picture for~$R$ with every
arrow reversed in direction.

\iffalse
If a function $f:A\to B$ is a bijection (\cf Rosen), then
it has an unique inverse function, $f^{-1}: B \to A$ defined by the rule
that
\[
f(a) = b \qiff f^{-1}(b) = a.
\]
\fi


Inverse also preserves several of the relational properties we have
considered.  Namely, if $R$ is transitive, so is $R^{-1}$.  Likewise for
symmetry, reflexivity, and antisymmetry.  This implies that if $R$ is a
partial order, then so is $R^{-1}$.


\subsection{Composition}

Composition of relations generalizes composition of functions.  If
$R_1$ is a relation from $A$ to $B$ and $R_2$ is a relation from $B$ to
$C$, then the composition of $R_1$ and $R_2$ corresponds to using $R_1$ to
get from $A$ to $B$ and then $R_2$ to get from $B$ to $C$.

More precisely, the \emph{composition}, $R_2 \compose R_1$, of $R_1$ and
$R_2$---note the reversal in the order of $R_1$ and $R_2$
here\footnote{The symbol~$\compose$ is a constant source of confusion---if
you read a book you should always check how the authors define~$\compose$---
some of them define composition the other way around.}---is defined to be
the relation from $A$ to $C$ such that
\begin{displaymath}
a\, (R_2 \compose R_1)\, c  \qiff \exists b\, [a\, R_1\, b \land b\, R_2\, c].
\end{displaymath}

It's helpful to describe composition in terms of length-two paths in a
digraph.  Namely, $a\, (R_2 \compose R_1)\, c$ iff there is a length-two path
from $a$ to $c$ using an arrow from the point for $a$ in the digraph for
$R_1$, followed by an arrow to $c$ in the digraph for $R_2$.


\subsubsection{Relational Composition and Matrix Multiplication}

There is a lovely way to explain composition of relations using connection
matrices.  Namely, the connection matrix for the composition of two
relations $R_1$ and $R_2$ can be obtained by performing matrix
multiplication of the connection matrices of $R_2$ and $R_1$, except that
where the standard definition of matrix product calls for adding numbers,
we combine them with $\disj$ (Boolean OR).  This is called the \emph{Boolean
product} of the matrices.

That is, in ordinary matrix multiplication, the $(i,j)$th entry of the
matrix product is obtained by multiplying successive elements of the $i$th
row of the first matrix by the successive elements of $j$th column of the
second matrix, and adding up the resulting products of these pairs of
numbers.  If the original matrices are 0-1-valued, these products of
pairs will also be 0-1-valued, so it will make sense to $\lor$ them
together instead of adding them.

\begin{example}
Let $N$ be the relation from Example~\ref{ex:0123-abc}.  Its connection
matrix is
\[\begin{array}{r|ccc}
& \texttt{a}&  \texttt{b}&  \texttt{c}\\
\hline  
0& 1&  0&  1\\
1& 1&  0&  1\\
2& 0&  1&  0\\
3& 0&  0&  0
\end{array}
\]
Let $R$ be the relation from $\set{\texttt{a, b, c}}$ to
$\set{\texttt{d,e,f}}$ given by the connection matrix
\[\begin{array}{r|ccc}
& \texttt{d}&  \texttt{e}&  \texttt{f}\\
\hline  
\texttt{a}& 1&  1&  1\\
\texttt{b}& 0&  1&  0\\
\texttt{c}& 0&  0&  1
\end{array}
\]

The boolean product of these matrices is the matrix with rows labelled 0,
1, 2, 3 and columns labelled \texttt{d,e,f}.  To compute the
$(2,\texttt{e})$th entry in the product matrix, we take the 2-row of the
matrix for $N$:
\[
(0\ 1\  0)
\]
and the \texttt{e}-column of R:
\[
\left(\begin{array}{c}
1\\
1\\
0
\end{array}\right)
\]
and multiply corresponding entries to get the three products $0\cdot1, 1
\cdot 1$, and $0 \cdot 0$ and compute their disjunction:
\[
(0\cdot1) \disj (1 \cdot 1) \disj (0 \cdot 0) = 0 \disj 1 \disj 0 = 1.
\]
So the $(2,\texttt{e})$ entry is 1.  The complete product matrix is
\[\begin{array}{r|ccc}
& \texttt{d} &  \texttt{e} &  \texttt{f} \\
\hline  
0& 1&  1&  1\\
1& 1&  1&  1\\
2& 0&  1&  0\\
3& 0&  0&  0
\end{array}
\]
which is the connection matrix for $R \compose N$.
\end{example}

When $R$ is a relation on a set, $A$, it can be composed with itself.  The
composition $R \compose R$ of $R$ with itself is written $R^2$.  Similarly
$R^n$ denotes $R$ composed with itself $n$ times.  $R^n$ can be
recursively defined:
\begin{eqnarray*}
R^0 & \eqdef & I_A,\\
R^{n+1} & \eqdef & R \compose R^{n}.
\end{eqnarray*}


\begin{example}
\begin{samepage}
Consider the relation $R$ with graph $\set{(a,b), (a,c), (b,d), (d,e)}$.
The connection matrix and digraph for $R$ are:
    \begin{center}
      \begin{tabular}[b]{r|ccccc}
            &$a$&$b$&$c$&$d$&$e$ \\
        \hline
        $a$ & 0 & 1 & 1 & 0 & 0  \\
        $b$ & 0 & 0 & 0 & 1 & 0  \\
        $c$ & 0 & 0 & 0 & 0 & 0  \\
        $d$ & 0 & 0 & 0 & 0 & 1  \\
        $e$ & 0 & 0 & 0 & 0 & 0
      \end{tabular}
      \hfil
      \includegraphics{figures/tinyrel.mps}
    \end{center}    
  \end{samepage}
  \begin{samepage}
   For $R^2$ we have:
    \begin{center}
      \begin{tabular}[b]{r|ccccc}
            &$a$&$b$&$c$&$d$&$e$ \\
        \hline
        $a$ & 0 & 0 & 0 & 1 & 0  \\
        $b$ & 0 & 0 & 0 & 0 & 1  \\
        $c$ & 0 & 0 & 0 & 0 & 0  \\
        $d$ & 0 & 0 & 0 & 0 & 0  \\
        $e$ & 0 & 0 & 0 & 0 & 0
      \end{tabular}
      \hfil
      \includegraphics{figures/tinyrel2.mps}
    \end{center}
  \end{samepage}
  \begin{samepage}
   For $R^3$ we have:
    \begin{center}
      \begin{tabular}[b]{r|ccccc}
            &$a$&$b$&$c$&$d$&$e$ \\
        \hline
        $a$ & 0 & 0 & 0 & 0 & 1  \\
        $b$ & 0 & 0 & 0 & 0 & 0  \\
        $c$ & 0 & 0 & 0 & 0 & 0  \\
        $d$ & 0 & 0 & 0 & 0 & 0  \\
        $e$ & 0 & 0 & 0 & 0 & 0
      \end{tabular}
      \hfil
      \includegraphics{figures/tinyrel3.mps}
    \end{center}
  \end{samepage}
\end{example}

We claim that $R^n$ describes the length $n$ path relation of $R$.  That
is, $a\, R^n\, b$ iff there is a path in $R$ from $a$ to $b$ of
length $n$.  In other words:
\begin{lemma}\label{lem:Rn-paths}
\[
R^n = R^{(n)}
\]
\end{lemma}

\begin{proof}
By induction on $n$ with the statement of the Lemma as the induction
hypothesis, $P(n)$.

\textbf{Base case} $n=0$: We have that $a\, R^0\, b$ iff $a = b$ by
definition of $R^0$.  Also there is a length 0 path from $a$ to $b$ iff $a
= b$ by definition of length 0 path.  So $a\, R^0\, b$ iff there is a
length 0 path from $a$ to $b$.  That is, $R^0 = R^{(0)}$.

\textbf{Inductive step:} Suppose $P(n)$ holds for some $n\ge 0$.  We want
to prove $P(n+1)$.

First consider a length $n+1$ path $a=a_0,\dots,a_n,a_{n+1}=b$ in $R$.  By
induction hypothesis, we can assume that $a\, R^n\, a_n$.  Also, we have
by definition of path in $R$ that $a_n\, R\, b$.  Therefore,
\[
a\, (R \compose R^n)\, b
\]
by the definition of composition.  So $a\, R^{n+1} b$ by the recursive
definition of $R^{n+1}$.  This shows that $R^{(n+1)} \subseteq R^{n+1}$.

Conversely, suppose $a\, R^{n+1}\, b$.  By the definition of $R^{n+1}$,
there exists a $b'$ such that $a\, R^n\, b'$ and $b'\, R\, b$.  By the
inductive hypothesis, we can assume that there is a length $n$ path in $R$
from $a$ to $b'$.  But since $b'\, R\, b$, we can add $b$ to the end of
the path and obtain a length $n+1$ path from $a$ to $b$.  This shows that
$R^{n+1} \subseteq R^{(n+1)}$.

Hence, $R^{n+1} = R^{(n+1)}$, which is the statement $P(n+1)$, completing
the proof by induction.
\end{proof}

\subsubsection{Computing the Transitive Closure}

How do we actually find all the paths needed to compute the path relation
of a relation, say from its graph or connection matrix?  From
equation~(\ref{R*u}) and Lemma~\ref{lem:Rn-paths} we have
\[
R^* = R^0 \union  R^1 \union R^2 \union \cdots
\]

This helps since we know how to compute the composition $R^n$, but there
is still a problem: there are infinitely many terms!  When $A$ is finite,
however, we need only compute the first $\card{A}$ terms.

\begin{lemma}
Suppose $R$ is a relation on $A$.  Let $a$ and $b$ be elements of $A$ and
suppose that there is a path from $a$ to $b$ in $R$.  Then there is a path
of length at most $\card{A}-1$ from $a$ to $b$ in $R$.
\end{lemma}

\begin{proof}
We'll use the Least Number Principle.

Consider the shortest path $a=a_0,a_1,\dots,a_k=b$ from $a$ to $b$ (we
know one exists, so by the LNP there is a shortest one).  Suppose $k \ge
\card{A}$.  Then some element of $A$ appears twice in the list (with at
least $\card{A}+1$ list entries, one must be a repeat).  This means the
path is at some point circling back to where it was before.  We can cut
out this cycle from the path and get a shorter path.  This contradicts
that we had a shortest path.  So we cannot have $k \ge \card{A}$.
\end{proof}

\begin{corollary}
If $R$ is a relation on a set of size $n$, then
\[
R^* = \lgunion_{k=0}^{n-1} R^k.
\]
\end{corollary}

\begin{problem}
Prove that if $R$ is a relation on a finite set, $A$, then
\[
R^* = (R \union I_A)^{\card{A}}.
\]
\end{problem}

\subsection{Algebra of Relations}

With all these operations, there are no end of identities and other
connections among operations and properties of relations.  We don't really
need to develop these algebraic properties in this course, but we mention
without proof a small sample of algebraic facts about relational operators
just to offer a hint of the possibilities:
\begin{eqnarray*}
(R \union S)^{-1} & = & R^{-1} \union S^{-1},\\
(R \compose S)^{-1} & = & S^{-1} \compose R^{-1}\\
(R^*)^* & = & R^*\\
(R^{-1})^{-1} & = & R\\
(R^*)^{-1} & = & (R^{-1})^*\\
(R \intersect S) \cross T & = & (R \intersect T) \cross (S \intersect T)\\
(R \intersect S) \compose T & \subseteq & (R \compose T) \intersect (S \compose T)
\end{eqnarray*}


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

``Task graphs'' are a common source of partial orders: there is a set,
$A$, of tasks represented by points in the plane with an arrow from the
point for a task $a$ to the point for a task $b$ indicating that ``task
$a$ has to finish before task $b$ can begin.''

\begin{samepage}
\begin{example}\label{cloth}
Here is a graph that describes the order in which you could put on clothes.
The task 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 point.  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
dependency relation we care about is defined by the positive length paths
in the task graph, that is, by transitive closure of the DAG.  The
\emph{dependency relation} of the DAG 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, so we just need to prove that it is
asymmetric.  We do so by contradiction.

Suppose that there exists $a,b$ such that $a\, D^+\, b$ and $b\, D^+\,
a$.  In other words, there is a path of positive length from $a$ to $b$
and also a path of positive length from $b$ to $a$ in $D$.  If we attach
these two paths, we get a path from $a$ to $a$ in $D$, that is, $D$
contains a cycle.  This contradicts the fact that $D$ has no cycles.
\end{proof}

\begin{problem}
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{problem}


\begin{problem}
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 $D$ and $G$ are DAG's with the same transitive
closure, then they have the same set of covering edges.

\ppart Describe two graphs with nodes $\set{1,2,3}$ which have the same
transitive closure, 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 transitive closure,
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 transitive
closure.

\ppart Show that the previous result is not true in general for infinite
DAG's. \hint An example of this kind has appeared several times in these
Notes.

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

\eparts
\end{problem}


\iffalse

\subsubsection{Hasse Diagrams}

If we draw the graph of a poset, we may get
\emph{lots} of edges (consider the $\le$ order on some natural
numbers).  But a lot of those edges are ``implicit'' from the
transitivity of the order. We can get a much less messy picture by
leaving out these arrows.

Consider the clothing example.  Under the transitive closure,
underwear precedes belt.  But we don't need to see that edge to know
it is there.
Similarly loops (which express reflexive relationships) aren't shown.
\begin{definition}
  A \emph{Hasse diagram} for a poset $(A,\preceq)$ is a graph: \\
 ---whose vertices are the elements of $A$, \\
 ---whose edges (arrows) represent pairs $(a,b)$, where $a \prec b$, \\
 ---if $ a \prec b$, the $a$ vertex is below the $b$ vertex, \\
 ---that contains no ``transitive edges'', \\
 ---for which all pairs in $\preceq$ are obtainable by transitivity from
  edges in the diagram.
\end{definition}
It's a ``transitive disclosure'' of the poset.
To convert the diagram above to an ``official form'' Hasse diagram,
we must remove the pants $\rightarrow$ jacket arrow:
\begin{center}\includegraphics{figures/clotheshasse.mps}\end{center}
\begin{samepage}
  The divisibility relation over $\{1,2,\dots,12\}$, represented by
  the digraph
  \begin{center}\includegraphics{figures/divide12.mps}\end{center}  
\end{samepage}
\begin{samepage}
  has the following Hasse diagram:
  \begin{center}\includegraphics{figures/divide12hasse.mps}\end{center}
\end{samepage}
\fi


% Examples:
% \begin{itemize}
% \item $S=\naturals, \preceq = \leq$,
% \item $S=\naturals, \preceq = \divides$, NOT because neither
%   $3\divides5$ nor $5\divides3$
% \item $S=P(\naturals), \preceq = \subseteq$, NOT because neither $\{3\}
%   \subseteq \{5\}$ nor $\{5\} \subseteq \{3\}$ 
% \item Lexicographic order on pairs of natural numbers, defined by:
%   $(a_1,a_2) \preceq (b_1,b_2)$ if and only if either $a_1 < b_1$,
%   or else $a_1 = b_1$ and $a_2 \leq b_2$. \\
%   $(2,37) \preceq (2,38) \preceq
%     (3,2)$.  ``Lexicographic'' because like dictionary.
% \end{itemize}

% This has been the basic material. \\
% Book has a bit more: \\
% lower bounds, upper bounds (for a subset---$\leq$ everything in the
% subset, or $\geq$) \\
% lub, glb, \\
% lattices. \\
% Read these parts. 

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

A total order can be represented by a DAG looks like a single line.

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, so as not
to conflict with the precedence requirements.  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 \text{   implies   } 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 a topological sort of the partial order of dressing tasks given by the
DAG of Example~\ref{cloth}.

One of the nice facts about partial orders on finite sets is that such an
ordering is easy to construct.  The basic idea is to pick off a
``first'' element and then proceed inductively.

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

\begin{definition}
Let $\preceq$ be a partial order on a set, $A$.  An element $a \in A$
is \emph{minimal} iff
\[
\forall b\, [b \preceq a \qimplies b = a].
\]
\end{definition}

Notice that there can be more than one minimal element.  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$.  But every nonempty
finite partially ordered set will have one, because in a finite set you
can't keep going down indefinitely.

\iffalse Here is a more precise proof:

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

\begin{proof}
The proof is by contradiction.

Suppose $\card{A} = n > 0$ and no element of $A$ is minimal.  That means
every element, $a$, has an element $b \neq a$ such that $b \preceq a$.

Since $A$ is nonempty, there is some some element $a_0 \in A$.  Since $a_0$
is not minimal, there must be an $a_1 \neq a_0$ such that $a_1 \preceq a_0$.
Similarly, since $a_1$ is also not minimal, there must be an $a_2 \neq a_1$
such that $a_2 \preceq a_1$.  Continuing in this way we obtain a sequence
$a_n \preceq a_{n-1} \preceq \dots \preceq a_1 \preceq a_0$.  But
since there are $n+1$ elements in this sequence, some element must
occur twice, and since consecutive elements are different, the two
occurrences of the repeated element must have a different element
between them.  That is, we have $a_i \neq a_j \neq a_k = a_i$ for some
$i > j > k$.  But that means we have $a_i \preceq a_j$ and $a_j
\preceq a_i$ and $a_i \neq a_j$, contradicting the antisymmetry of the
partial order. 
\end{proof}
\end{lemma}
\fi

\iffalse
\begin{proof}
For every element $a \in A$, let $[a]_{\succeq} \eqdef \set{b \suchthat a
\succeq b}$.  That is, $[a]_{\succeq}$ is the set of elements $\preceq a$.
It is enough to show that there exists an $a \in A$ such that $ =
\emptyset$; to accomplish this, we use well-ordering.
  
Let $P = \{p_a \mbox{ given } a \in A\}$. Now let $a'$ be an element
corresponding to a set $p_{a'}$ of minimum cardinality. We now that such
an $a'$ exists by applying the well-ordering principle to the subset
$\{|p| : p \in P\}$ of $\naturals$. There can be several sets in $P$ of
minimum cardinality, but that doesn't matter---we pick $p_{a'}$ to be one
of the sets. We now prove by contradiction that $p_{a'} = \emptyset$.
  
Suppose that $|p_{a'}| > 0$, that is, that $p_{a'} \neq \emptyset$.  Then there
exists some $b' \in A$ such that $b' \prec a'$. Consider the set
$p_{b'}$. We now claim that $p_{b'} \subset p_{a'}$. Since $c \in p_{b'}$
implies that $c \prec b'$, we obtain, by transitivity, that $c \in p_{b'}$
implies that $c \prec a'$, that is, every element in $p_{b'}$ is also an
element of $p_{a'}$, or, equivalently, $p_{b'} \subseteq
p_{a'}$. Furthermore, $b' \in p_{a'}$ since $b' \prec a'$, but $b' \notin
p_{b'}$ since $b' \nprec b'$. Thus $p_{b'} \subset p_{a'}$. But this
contradicts our assumption that $p_{a'}$ is a set of minimum
cardinality. Thus, $p_{a'} = \emptyset$.
\end{proof}

If you don't like well-ordering, there is a proof by induction in
Velleman (\S 6.2). For comparison, we also show you a third proof
below:

\begin{proof}
  Suppose no element of $A$ is minimal. So every element has
  one preceding it.  We derive a contradiction.  Take some element $a
  \in A$ and define the following sequence recursively.  $a_0=a$, and
  for $i > 0$, $a_i$ is some element that precedes $a_{i-1}$.

  This definition is a bit odd because it is nondeterministic.  But it
  doesn't matter which preceding element you pick at each step.  The
  key is that it defines some $a_i$ for every $i$.
  
  Now note that the sequence $a_{n+1},\dots,a_0$ is a walk of length
  $n+1$.  This means some element is repeated: $a_i=a_j$ for some $i
  < j$.  But this means $a_i,\dots,a_j$ is a cycle, which is
  impossible in a poset.  So we have a contradiction.
\end{proof}
\fi 

\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.  \iffalse By
Lemma~\ref{minel},\fi We've observed that $A$ must have a minimal element,
$u$.  The set $A-\set{u}$ is still partially ordered by $\preceq$.  So by
the inductive hypothesis, $A-\set{u}$ 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 = u$].  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 besides picking
successive minimal elements.  \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 And the set need not be finite: we won't prove
it, but in fact \emph{all} partial orders, even infinite ones, have
topological sorts.

\subsection{Parallel Task Scheduling}

When elements of a partially ordered set are tasks that need to be done and the
partial order is precedence constraints, topological sorting provides
us with a legal way to execute tasks sequentially, that is, without
violating any precedence constraints.  But what if we have the
ability to execute more than one task at the same time?  For example,
say tasks are programs, 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 use partial order
concepts to analyze this problem.

On 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 sequence like this is called a
chain.

\begin{definition}
A \emph{chain} in a partial order, $\preceq$, is a sequence of elements of
the domain, each of which is strictly smaller ($\preceq$ and $\neq$) than
the next in the sequence.
\end{definition}

Note that a chain is simply a path in the DAG of the 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.  \iffalse (This is ``obvious,'' but is formalized as an
application of the ``pigeonhole principle'' we will study shortly.)\fi But
by definition of chains, this violates the precedence 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:

\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
precedence requirements, because all tasks that must precede a task 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 = \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~(\ref{RA1}).

Now suppose $1 <i \le t$, and assume for the sake of contradiction
that~(\ref{RAi}) does not hold.  That is, there is an $a \in B_i$ and a $b$
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} is a set of elements such that any two elements are
incomparable.
\end{definition}

\begin{corollary}\label{cor:parallel}
If the largest chain in a partially ordered set, $A$, is of size, $t$,
then $A$ 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 now claim that the elements in those sets are
incomparable.  Suppose that there exists $a,b \in B_i$ such that $a \neq b$
and $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}

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.
\]
We let the domain of the partial order be the set of pairs $(i, a_i)$ for
$1 \le i \le n$.  The ordering will be the product ordering of $<$ on
$\set{i \suchthat 1 \le i \le n}$ and $<$ on $\set{a_i \suchthat 1 \le i
\le n}$; let $\prec$ denote this partial ordering.  So
\[
(i, a_i) \prec (j,a_j) \qiff  i < j \land a_i < a_j.
\]

Now a $\prec$-chain will be a sequence
\[
(i_1, a_{i_1}) \prec (i_2, a_{i_2}) \prec \cdots \prec (i_k, a_{i_k})
\]
where the $i_j$'s and the $a_{i_j}$'s both increase from left to right.
That is, 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 form a subsequence 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.
}

\begin{problem}
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{problem}

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

\iffalse

\subsection{Closure}

A closure ``extends'' a relation to satisfy some property.  But
extends it as little as possible.
\begin{definition}
  The \emph{closure} of relation $R$ with respect to property $P$ is
  the relation $S$ that 

  (i) contains $R$,\\

  (ii) has property $P$, and\\

  (iii) is contained in \emph{any} relation satisfying (i) and (ii).\\

  That is, $S$ is the ``smallest'' relation satisfying (i) and (ii).
\end{definition}

As a general principle, there are two ways to construct a closure of
$R$ with respect to property $P$: We can either start with $R$ and add
as few pairs as possible until the new relation has property $P$; or
we can start with the largest possible relation (which is $A \times A$
for a relation on $A$) and then remove as many not-in-$R$ pairs as
possible while preserving the property $P$. 

% There might be no one relation satisfying the definition; in that case
% the closure is not defined.

\subsubsection{The Reflexive Closure}

\begin{lemma}
  Let $R$ be a relation on the set $A$.  The reflexive closure of $R$
  is $S=R \cup \set{(a,a), \forall a \in A}$.
\end{lemma}
\begin{proof}
  It contains $R$ and is reflexive by design.  Furthermore (by
  definition) any relation satisfying (i) must contain $R$, and any
  satisfying (ii) must contain the pairs $(a,a)$, so any relation
  satisfying both (i) and (ii) must contain $S$.
\end{proof}

\begin{example}
Let $R = \{(a,b) (a,c) (b,d) (d,e)\}$, then the reflexive closure of $R$
is
\[
\set{(a,b) (a,c) (b,d) (d,e) (a,a) (b,b) (c,c) (d,d) (e,e)}.
\]
\end{example}

% removed the picture examples
\iffalse
\begin{example}
  \begin{samepage}
    The reflexive closure of the relation
    \begin{center}
      \begin{tabular}[b]{r|ccccc}
            &$a$&$b$&$c$&$d$&$e$ \\
        \hline
        $a$ & 0 & 1 & 1 & 0 & 0  \\
        $b$ & 0 & 0 & 0 & 1 & 0  \\
        $c$ & 0 & 0 & 0 & 0 & 0  \\
        $d$ & 0 & 0 & 0 & 0 & 1  \\
        $e$ & 0 & 0 & 0 & 0 & 0
      \end{tabular}
      \hfil
      \includegraphics{figures/tinyrel.mps}
    \end{center}
  \end{samepage}
  \begin{samepage}
    is
    \begin{center}
      \begin{tabular}[b]{r|ccccc}
            &$a$&$b$&$c$&$d$&$e$ \\
        \hline
        $a$ & 1 & 1 & 1 & 0 & 0  \\
        $b$ & 0 & 1 & 0 & 1 & 0  \\
        $c$ & 0 & 0 & 1 & 0 & 0  \\
        $d$ & 0 & 0 & 0 & 1 & 1  \\
        $e$ & 0 & 0 & 0 & 0 & 1
      \end{tabular}
      \hfil
      \includegraphics{figures/tinyrelref.mps}
    \end{center}  
  \end{samepage}
\end{example}
\fi

\subsubsection{The Symmetric Closure}

\begin{lemma}
  Let $R$ be a relation on the set $A$.
  The symmetric closure of $R$ is $S=R \union R^{-1}$.  
\end{lemma}
\begin{proof}
  This relation is symmetric and contains $R$.  It is also the
  smallest such.  For suppose we have some symmetric relation $T$
  with $R \subseteq T$.  Consider $(a,b) \in R$. Then $(a,b) \in T$
  so by symmetry $(b,a) \in T$.  It follows that $R^{-1} \subseteq
  T$.  So $S=R \cup R^{-1} \subseteq T$.
\end{proof}

\begin{example}
Let $R = \set{(a,b) (a,c) (b,d) (d,e)}$, then the symmetric closure of $R$
is
\[
\set{(a,b) (a,c) (b,d) (d,e) (b,a) (c,a) (d,b) (e,d)}
\]
\end{example}

% removed the picture examples
\iffalse
\begin{example}
  \begin{samepage}
    The symmetric closure of the relation
    \begin{center}
      \begin{tabular}[b]{r|ccccc}
            &$a$&$b$&$c$&$d$&$e$ \\
        \hline
        $a$ & 0 & 1 & 1 & 0 & 0  \\
        $b$ & 0 & 0 & 0 & 1 & 0  \\
        $c$ & 0 & 0 & 0 & 0 & 0  \\
        $d$ & 0 & 0 & 0 & 0 & 1  \\
        $e$ & 0 & 0 & 0 & 0 & 0
      \end{tabular}
      \hfil
      \includegraphics{figures/tinyrel.mps}
    \end{center}
  \end{samepage}
  \begin{samepage}
    is
    \begin{center}
      \begin{tabular}[b]{r|ccccc}
            &$a$&$b$&$c$&$d$&$e$ \\
        \hline
        $a$ & 0 & 1 & 1 & 0 & 0  \\
        $b$ & 1 & 0 & 0 & 1 & 0  \\
        $c$ & 1 & 0 & 0 & 0 & 0  \\
        $d$ & 0 & 1 & 0 & 0 & 1  \\
        $e$ & 0 & 0 & 0 & 1 & 0
      \end{tabular}
      \hfil
      \includegraphics{figures/tinyrelsym.mps}
    \end{center}
  \end{samepage}
\end{example}
\fi

\section{Transitive Closure}

\begin{definition}
Let $R$ be a relation on a set, $A$.  The \emph{reflexive transitive
closure of $R$} is the relation, $R^*$, on $A$ defined by':
\[
R^* \eqdef \set{(a,b) \in A^2 \mbox{there is a path from $a$ to $b$ in
$R$}}.
\]
\end{definition}

Note that we have a path of length zero between every element and itself, so
the reflexive transitive closure of a relation is actually reflexive.

\begin{example}
  \begin{samepage}
    The transitive closure of the relation with connection matrix
    \begin{center}
      \begin{tabular}[b]{r|ccccc}
            &$a$&$b$&$c$&$d$&$e$ \\
        \hline
        $a$ & 0 & 1 & 1 & 0 & 0  \\
        $b$ & 0 & 0 & 0 & 1 & 0  \\
        $c$ & 0 & 0 & 0 & 0 & 0  \\
        $d$ & 0 & 0 & 0 & 0 & 1  \\
        $e$ & 0 & 0 & 0 & 0 & 0
      \end{tabular}
      \hfil
      \includegraphics{figures/tinyrel.mps}
    \end{center}
  \end{samepage}
  \begin{samepage}
    has connection matrix
    \begin{center}
      \begin{tabular}[b]{r|ccccc}
            &$a$&$b$&$c$&$d$&$e$ \\
        \hline
        $a$ & 0 & 1 & 1 & 1 & 1  \\
        $b$ & 0 & 0 & 0 & 1 & 1  \\
        $c$ & 0 & 0 & 0 & 0 & 0  \\
        $d$ & 0 & 0 & 0 & 0 & 1  \\
        $e$ & 0 & 0 & 0 & 0 & 0
      \end{tabular}
      \hfil
      \includegraphics{figures/tinyreltrans.mps}
    \end{center}
  \end{samepage}
\end{example}
\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


\iffalse
\begin{example} \label{ex:initial-relations}
  \begin{enumerate}
  \item \label{classes} 
    The relation ``is taking class'' as a subset of
    $\{\mbox{students at MIT}\}\times\{\mbox{classes at MIT}\}$.
    A relation from students to classes.
  \item \label{lectures} 
    The relation ``has lecture in'' as a subset of
    $\{\mbox{classes at MIT}\}\times\{\mbox{rooms at MIT}\}$.
    A relation from classes to rooms.
  \item \label{roommates} 
    The relation ``is living in the same room'' as a subset of
    $\{\mbox{students at MIT}\}\times\{\mbox{students at MIT}\}$.
    A relation on students.
  \item \label{reachable} 
    The relation ``can drive from first to second city''.
    (Not necessarily directly---just some way, on some roads.)
  \item \label{wire} 
    Relation on computers, ``are connected (directly) by a wire''
  \item \label{meet} ``meet one another on a given day''
  \item \label{likes}  ``likes''
  \item \label{le} 
    Let $A=\naturals$ and define $a\, R\, b$ iff $a\le b$.
  \item \label{finite} 
    Let $A=\power(\naturals)$ and define $a\, R\, b$ iff $a \cap b$ is finite.
  \item \label{dist} Let $A=\reals^2$ and define $a\, R\, b$ iff $d(a,b)=1$.
  \item \label{contain} Let $A=\power(\{1,\dots,n\})$ and define $a\, R\, b$ iff
    $a\subseteq b$.
\end{enumerate} 
\end{example}

Among our relations from Example~\ref{ex:initial-relations}
\begin{itemize}
\item Relation~\ref{roommates} is reflexive, symmetric, transitive. 
\item Relation~\ref{reachable} is reflexive, transitive.  Not
  necessarily symmetric, since roads could be one-way (consider
  Boston), but in actuality\dots.  But definitely not antisymmetric.
\item Relation~\ref{wire} is symmetric but not transitive.
Whether it is reflexive is open to interpretation.
\item Relation~\ref{meet} likewise. 
\item Relation~\ref{likes} is (unfortunately) not symmetric.  Not
antisymmetric.  Not transitive.  Not even reflexive!
\item Relation~\ref{le} is reflexive, antisymmetric, transitive.
\item Relation~\ref{finite} is not reflexive.  It is symmetric.  It is
not transitive.  $\{\mbox{even naturals}\} \cap \{\mbox{odd
naturals}\}$ is finite (empty), but not $\{\mbox{even naturals}\} \cap
\{\mbox{even naturals}\}$.
\item Relation~\ref{dist} is only symmetric.
\item Relation~\ref{contain} is reflexive, antisymmetric and transitive.
\end{itemize} 
\fi


\iffalse

\begin{example}
  Consider the following relations:
  \begin{itemize}
  \item $A=\naturals, R=\leq$, easy to check reflexive, transitive,
    antisymmetric
  \item $A=\naturals, R=\geq$, same.
  \item $A=\naturals, R=<$, \emph{not} because not reflexive
  \item $A=\naturals, R=|$ (divides), easy to check reflexive,
    transitive, antisymmetric
  \item $A=\power(\naturals), R=\subseteq$, check reflexive: $S
    \subseteq S$, transitive: $S \subseteq S' \wedge S' \subseteq S''
    \Rightarrow S \subseteq S''$, antisymmetric: $S \subseteq S'
    \wedge S' \subseteq S \Rightarrow S = S'$.
  \item $A=$ ``set of all computers in the world'', $R=$ ``is
    (directly or indirectly) connected to''.  \emph{not} a partial
    order because it is not true that $a R b \wedge b R a
    \Rightarrow a=b$.  In fact, it is symmetric and transitive.
    Equivalence relation.
  \item $A=$ ``set of all propositions'', $R=\Rightarrow$, {\bf not} because
    it's not antisymmetric. Not symmetric either, so not equivalence
    relation.
  \end{itemize}
\end{example}
\fi
