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

\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}
%\renewcommand{\coursecopyrightyear}{2002}

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

\section{Introduction}
\emph{Relations} and \emph{functions} are two fundamental concepts of
Mathematics.  Functions map any element of their domain of definition to
an element of their range; anyone who has taken Math and Science courses
is certainly familiar with lots of functions.  The most familiar relation
is undoubtedly equality, but other familiar relations are membership (of
elements in sets), various orderings (smaller than\dots, younger
than\dots, cheaper than\dots), reachability relations (connected to\dots,
accessible from\dots, implies\dots), compatibility relations (likes\dots,
eats\dots).

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 might
look like:
\[\begin{array}{l}
(\texttt{.emacs},\ \texttt{meyer},\ \texttt{meyerstf},\ \text{Sep  3},\ 17335,\
\texttt{-rw-rw-r--}),\\
(\texttt{ln3.tex},\ \texttt{meyer},\ \texttt{ta6042},\ \text{Sep 13},\ 4096,\
\texttt{-rw-r--r--}),\\
\dots.
\end{array}\]

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.

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.
Binary relations are the most widely used kind of relation, and there is
little loss of generality in focussing on them.  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 Fall term, no students are
currently registered for Spring-term only courses (also, lots of courses
taught in the past ten years are no longer offered at all).

For binary relations, the projection on the second coordinate is called the
\emph{range} of the relation.  That is,
\[
\range{R} \eqdef \set{b \suchthat \exists a\ a\, R\, b}.
\]
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 projection on the first coordinate of a binary relation is called its
\emph{domain of definition}.  That is,
\[
\text{domain-of-definition}(R) \eqdef \set{a \suchthat
  \exists b\ a\,R\,b}.
\]
So \emph{a relation is total iff its domain equals its domain of
definition.}

A more mathematical example of a binary is 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$ called $f(a)$.

\subsection{Adjacency Sets}

Let $R$ be a binary relation from $A$ to $B$.  For any subsets, $A'
\subseteq A$ and $B' \subseteq B$, define
\begin{eqnarray*}
A'R &\eqdef & \set{b \in B \suchthat aRb \text{ for some } a \in A'},\\
RB' &\eqdef & \set{a \in A \suchthat aRb \text{ for some } b \in B'}.
\end{eqnarray*}
$A'R$ is called the set of \emph{elements adjacent to $A'$}, and $RB'$ is
the set of \emph{elements incident to $B'$}.

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

It's customary to write $aR$ for $a\in A$ rather than $\set{a}R$; likewise
for $Rb$.

\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 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 abstract data types.  For example,
the simplest way of representing a finite set of numbers is as an
unordered 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.

The general setup for defining an equivalence relation on a set, $A$, is
\begin{definition}\label{deqv}
Let $f:A \to B$ be a total function.  The binary relation $\equiv_f$ on $A$
is defined by the rule:
\[
[a_1 \equiv_f a_2] \qiff f(a_1) = f(a_2).
\]
A binary relation on $A$ is an \emph{equivalence relation} iff it equals
$\equiv_f$ for some $f$.
\end{definition}
The idea here is that the only property of an element, $a$, that we care
about is the value of $f(a)$, so we consider elements with the same
$f$-value to be equivalent.

For example, similarity of triangles is an equivalence relation because it
is $\equiv_f$ where $f$ maps a triangle to the set of sizes of its angles.
Representation-equivalence on lists of numbers 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$ is $\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$,
\viz there is an integer, $k$, such that $n=km$.

We'll prove the basic properties of $\equiv$ (mod $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$.
\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.)
Uniqueness of $q$ and $r$ justifies:
\begin{definition}
Given integers, $a,m$ with $m>0$, define $\remainder_m(a)$ and
$\quotient_m(a)$ to be the unique integers such that $0\le \remainder_m(a)
<m$ and
\[
a = m \cdot \quotient_m(a) + \remainder_m(a).
\]
\end{definition}

\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$ (mod $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 we can at any time replace an intermediate result
with any 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 often also referred to as ``congruence mod $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$, \ie 128-bit numbers.
\fi

\subsection{Partitions}

A division of a set into such 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 \mathcal{A}$, and\label{AU}
\item if $B_1 \neq B_2$ are blocks of $\mathcal{A}$, then $B_1$ and $B_2$
are disjoint, \ie $B_1 \intersect B_2 = \emptyset$.\label{B1B2}
\end{enumerate}
\end{definition}

For example, we can partition of real line, $\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}$.  The $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
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
\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
partition $A$ into blocks.
\begin{definition}\label{mkp}
Let $E$ is 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$
(mod 4).  These are exactly the blocks of the partition based on
remainder-by-4 of Example~\ref{part4}.

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

\begin{proof}
Since $E$ is an equivalence relation on $A$, there is a total 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}

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

But from~(\ref{aEf}), we have $a \in aE$ because $f(a) = f(a)$.  This
implies that each set in $\mathcal{A}$ is nonempty and that $\lgunion
\mathcal{A} = 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.  In fact, these
constructions are inverses of each other:

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

Put less formally, Corollary~\ref{AEA} shows that equivalence relations and
partitions are different ways of describing the same concept.  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 in blocks all the objects that are the ``same.''

\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}\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$, the $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.
\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 important 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 this
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 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 transitive, we have $a_1\,
R\, a$, which 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 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.  Checking 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, \eg 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:}  Given 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}$.}

\section{Partial Orders}\label{ordrs}

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

The most familiar example of partial orders are ``less than or equal''
relations, \eg the relation, $R$, on real numbers such that $r_1\, R\, r_2$
iff $r_1 \le r_2$.  This relation has the special property that given any
two, 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 \disj 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}.
\end{definition}
So $\le$ on $\reals$ is a total order.

The most general example of a partial order is the subset relation,
$\subseteq$, on sets.  The subset relation is \emph{not} total, \eg
$\set{0,1}$ and $\set{1,2}$ are incomparable under $\subseteq$ since
neither is a subset of the other.
\begin{definition}\label{wpo}
Let $R$ be a binary relation on a set, $A$.  Then $R$ is a \emph{weak
partial order} providing
\begin{enumerate}
\item $Ra \subseteq Rb \qiff a\, R\, b$, and\label{wpo1}
\item $Ra = Rb \qimplies a = b$.\label{wpo2}
\end{enumerate}
for all $a,b \in A$.
\end{definition}

Weak partial orders by definition inherit some basic properties of the
subset relation.  For example, every weak partial order must be a reflexive
by Definition~\ref{wpo}.\ref{wpo1}, because $Ra \subseteq Ra$.  Likewise, the
transitivity of every weak partial order follows from
Definition~\ref{wpo}.\ref{wpo1} and the transitivity of $\subseteq$.  So we
have
\begin{lemma}
Every partial order is reflexive and transitive.
\end{lemma}

One final property of the subset relation characterizes all partial orders:
\begin{definition}\label{antis}
A binary relation, $R$, on a set, $A$, is \emph{antisymmetric} providing
that
\[
[a\, R\, b \text{ and } b\, R\, a] \qimplies a = b.
\]
for all $a,b\in A$.
\end{definition}

\begin{lemma}
Every partial order is antisymmetric.
\begin{proof}
Suppose $R$ is a partial order on $A$.  Then
\begin{align*}
a\, R\, b \conj b\, R\, a
    &\qiff Ra \subseteq Rb \conj Rb \subseteq Ra
          & \text{by Def.~\ref{wpo}.\ref{wpo1}}\\
    &\qiff Ra = Rb & \text{Def. of $\subseteq$}\\
    & \qiff a = b & \text{by Def.~\ref{wpo}.\ref{wpo2}}.
\end{align*}
\end{proof}
\end{lemma}

These three properties provide an axiomatic characterization of partial
orders:
\begin{theorem}
A binary relation, $R$, on a set $A$ is a \emph{weak partial order} iff it
is reflexive, transitive, and antisymmetric.

\begin{proof}
The preceding Lemmas imply the left to right direction of the Theorem.  To
prove the right to left direction, assume $R$ is reflexive, transitive, and
antisymmetric.

We first prove that condition of Definition~\ref{wpo}.\ref{wpo1} from left
to right:
\begin{align*}
Ra \subseteq Rb
    & \qimplies a \in Rb  & \text{because $a \in Ra$ by reflexivity}\\
    & \qimplies a\, R\, b & \text{by Def. of $Rb$}.
\end{align*}

Conversely, suppose $a\, R\, b$.  Let $a'$ be any element of $Ra$, \ie
$a'\,R\, a$.  Then by transitivity, $a'\, R\, b$, \ie $a' \in Rb$.  This
shows that $Ra \subseteq Rb$, completing the proof of
Definition~\ref{wpo}.\ref{wpo1}.

Next we prove that the condition of Definition~\ref{wpo}.\ref{wpo2} holds.
Namely, suppose $Ra = Rb$.  Then $a \in Rb$ because $a \in Ra$ by
reflexivity.  That is, $aRb$ by definition of $Rb$.  Repeating this
argument with the roles of $a$ and $b$ reversed, we conclude that $bRa$.
Now antisymmetry of $R$ implies $a=b$.
\end{proof}
\end{theorem}

The requirement that a weak partial order be reflexive rules out ``strict''
orders like $<$ or $\subset$, where $\subset$ denotes the \emph{proper}
subset relation: $A \subset B$ iff [$A \subseteq B$ and $A \neq B$].  So we
drop the condition of reflexivity from the general definition of partial
order.  Namely, we call a relation a partial order if it becomes a weak
partial order when add all the pairs $(a,a)$ that are not already in its
graph.  More precisely,

\begin{definition}
A binary relation, $R$, on a set, $A$, is a \emph{partial order} providing
that $R \union I_A$ is a weak partial order (where $I_A$ be the identity
relation on the set, $A$).
\end{definition}

If $A$ is a family of sets and $R$ is the proper subset relation,
$\subset$, then $R \union I_{\mathcal{A}}$ is the same as $\subseteq$ on
$A$, and so the proper subset relation is indeed a partial order.
Likewise, if $R$ is the less-than relation, $<$, then $(R \union
I_{\reals}$ is simply the $\le$-relation, and therefore $<$ also counts as
a partial order.

We can also characterize partial orders axiomatically:
\begin{theorem}\label{po}
A relation is a partial order iff it is transitive and antisymmetric.
\end{theorem}

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

Actually, the less-than and proper subset relations have the stronger
property of being irreflexive:
\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$.  It is \emph{asymmetric} iff
$a\, R\, b$ implies $\neg(b\, R\, a)$ for all $a,b\in A$.

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

So the $<$-relation and the $\subset$-relation are strict partial orders.
Note that Rosen defines ``partial order'' to mean weak partial order, which
means that $<$ is not a partial order using Rosen's definition.

The only difference between strict, weak and arbitrary partial orders is
whether elements may be related to themselves, that is, whether $a\, R\, a$
holds for some elements, $a$.  In a strict partial order like, $<$, no $a$
is related to itself, that is, $a<a$ is not true for any $a$.  In a weak
partial order like $\le$, every $a$ is related to itself, that is, $a \le
a$ for all $a$.  Finally, in an arbitrary partial order, some elements may
be related to themselves and some not.

A few more examples of partial orders are worth mentioning:

\begin{example}\label{supset}
Let $A$ be some family of sets and define $a_1 \preceq a_2$ iff $a_1
\supseteq a_2$.  Then $\preceq$ is a weak partial order.
\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.
\end{example}

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

Strict partial orders also have an axiomatic characterization:
\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 partial 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

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

\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) (6 6)}\\
\texttt{ (6 12) (7 7) (8 8) (9 9) (10 10) (11 11) (12 12))}
\end{array}\]
\end{example}

The relational properties we have defined all have straightforward
descriptions in terms of the list representation.  For example,
\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)))}
\end{quote}
\end{example}

Note that the adjacency list representation of a relation, $R$, is the
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 the $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}
&a& b&  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, properties can be recognized by examining the representation:
\begin{description}

\item[Reflexivity] the major diagonal is all 1.

\item[Symmetry:] the matrix is unchanged by reflection about the major
(upper-left to lower-right) 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 set $A$, that is where
$A=B$, and usually where $A$ is finite.

\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, a \emph{self-loop} at a point is an arrow going
from the point back to itself.

\begin{description}
\item[Reflexivity:] All nodes have self-loops.

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

Equality on $A$ is also known as the \emph{identity relation}, $I_A$, on
$A$.  That is, $a\, I_A\, b$ iff $a = b$.

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, 

\hyperdef{def}{intersectrel}{the \emph{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 preserve being partially ordered and being an equivalence
relations.

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

\hyperdef{def}{complementrel}{The \emph{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.
\]

Using containment, 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}

\hyperdef{def}{inverserel}{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, \hyperdef{def}{composerel}{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}
& d&  e&  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*}
Where $I_A$ is the identity relation on $A$ defined in Section~\ref{paths}.

\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 well-ordering there is a shortest one).  Suppose $k
\ge n$.  Then some element of $A$ appears twice in the list (with at least
$n+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 n$.
\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}


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

\begin{lemma}
Any strict partial order is a DAG.
\end{lemma}
\begin{proof}
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{proof}

But is a DAG a partial order?  No, because it may not be transitive.  But
there is a natural extension: the transitive closure of the DAG is a strict
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 $R$, \ie $R$ contains a
cycle.  This contradicts the fact that $D$ has no cycles.
\end{proof}

\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

\subsection{DAGs for Partial vs.\ Total Orders}

The DAG for a total order looks like a line.

In the 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.


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

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, $\preceq$, on a set, $A$, is
a total ordering, $\sqsubseteq$, on $A$ such that
\[
a \preceq b \text{   implies   } a \sqsubseteq b.
\]
\end{definition}

For example,
\begin{quote}
shirt $\sqsubset$ sweater $\sqsubset$ underwear $\sqsubset$ leftsock
$\sqsubset$ rightsock $\sqsubset$ pants $\sqsubset$ leftshoe $\sqsubset$
rightshoe $\sqsubset$ belt $\sqsubset$ jacket,
\end{quote}
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 find construct.  The basic idea is to pick off a
``first'' element and then proceed inductively.

\begin{theorem}\label{thm:topological}
Every finite poset has a topological sort.
\end{theorem}

\begin{definition}
Let $\preceq$ be a partial order on a set, $A$.  An element $a \in A$
\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 wiil 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 finite
partially ordered set will have one.  This is obvious because in a finite
set you can't keep going down indefinitely.  Here is a more precise proof:

\hyperdef{rule}{minel}{
\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 \prec 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 \prec a_0$.
Similarly, since $a_1$ is also not minimal, there must be an $a_2 \neq a_1$
such that $a_2 \prec a_1$.  Continuing in this way we obtain a sequence
$a_n \prec a_{n-1} \prec \dots \prec a_1 \prec a_0$.  But since there are
$n+1$ elements in this sequence, some element of 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 \prec a_j$ and $a_j \prec a_i$ and $a_i \neq a_j$, contradicting
the antisymmetry of the partial order.

\end{proof}
\end{lemma}

\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$, \ie 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'$, \ie 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.  By Lemma~\ref{minel}, $A$
has a minimal element, $u$.  We know the restriction $\preceq \restrict
(A-\set{u})$ is also a partial order.  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 order, 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, \ie 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 the longest 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, $A_1,
A_2, \dots, A_t$, such that for each block, $A_i$, all tasks that have to
precede tasks in $A_i$ are in smaller-numbered groups:
\begin{eqnarray}
RA_1 & = & \emptyset,\text{ and}\label{RA1}\\
RA_i & \subseteq & A_1 \cup A_2 \cup \cdots \cup A_{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 $A_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 $A_i$ as follows:
\[
A_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 $A_i$.  To complete the proof, notice
that if $a \in A_1$, then $a$ must be minimal, and since $R$ is strict we
have $RA_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 A_i$ and a $b$
such that $b\, R\, a$, and $b \notin A_1 \cup A_2 \cup \cdots \cup
A_{i-1}$.  Then by definition of the $A_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 A_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 $A_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 A_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 A_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 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$, \ie the largest chain
is of size $\le t$.  Then by Corollary \ref{cor:parallel}, the $n$
elements can be partitioned into $t$ or fewer blocks, each of which is an
antichain.  Let $\ell$ be the size of the largest antichain.  Since the
partition has $t$ or fewer blocks, and each block has at most $\ell$
elements, there are at most $\ell t$ elements, \viz $n \leq \ell t$.  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}
Define 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, \eg 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
