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

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

%\newcommand{\power}{\mathcal{P}}              % The power set
%\newcommand{\R}{\mathop{\mbox{$R$}}\nolimits} % Is related to

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


A ``relation'' is a fundamental mathematical notion expressing a
relationship between elements of sets.

\begin{definition}
  A \emph{binary relation from a set~$A$ to a set~$B$} is a subset
  $R \subseteq A\times B$.
\end{definition}

So, $R$ is a set of ordered pairs. We often write $a\sim_R b$ or $a R
b$ to mean that $(a,b)\in R$.

Functions, for example, are a type of relation. The abstract notion of
a relation is useful both in mathematics and in practice for modeling
many different sorts of relationships. It's the basis of the
\emph{relational database} model, the standard data model for
practical data processing systems. 

Many times we will talk about a ``relation on the set $A$'', which means
that the relation is a subset of $A\times A$. We can also define a
\emph{ternary} relation on $A$ as a subset $R\subseteq A^3$ or, in
general, an $n$-ary relation as a subset $R\subseteq A^n$, or
$R\subseteq A_1\times A_2 \times\cdots\times A_n$ if the sets $A_i$
are different. In this class, we will focus only on binary
relations. Here are some examples:

\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\sim_R b$ iff $a\le b$.
  \item \label{finite} 
    Let $A=\power(\naturals)$ and define $a\sim_R b$ iff $a \cap b$ is finite.
  \item \label{dist} Let $A=\reals^2$ and define $a\sim_R b$ iff $d(a,b)=1$.
  \item \label{contain} Let $A=\power(\{1,\dots,n\})$ and define $a\sim_R b$ iff
    $a\subseteq b$.
\end{enumerate} 

\section{Properties of Relations}

Once we have modeled something abstractly as a relation, we can talk
about its properties without referring to the original problem
domain. For a relation on a set $A$ there are several standard
properties of relations that occur commonly. Later on we will use
these properties to classify different types of relations.

\begin{definition}
  A binary relation $R$ on $A$ is:
  \begin{enumerate}
  \item \emph{reflexive} if for every $a\in A$, $a\sim_R a$.

  % \item \emph{irreflexive} if for every $a \in A$, $a\nsim_R a$.

  \item \emph{symmetric} if for every $a,b\in A$, $a\sim_R b$ implies
    $b\sim_R a$.

  \item \emph{antisymmetric} if for every $a,b\in A$, $a\sim_R b$ and
    $b\sim_R a$ implies $a=b$.

  \item \emph{asymmetric} if for every $a,b\in A$, $a\sim_R b$ implies 
    $\neg(b\sim_R a)$.

  \item \emph{transitive} if for every $a,b,c\in A$, $a\sim_R b$ and
    $b\sim_R c$ implies $a\sim_R c$.

  \end{enumerate}
\end{definition}

The difference between antisymmetric and asymmetric relations is that
antisymmetric relations may contain pairs $(a,a)$, i.e., elements can
be in relations with themselves, while in an asymmetric relation this
is not allowed. Clearly, any asymmetric relation is also
antisymmetric, but not vice versa.

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} 

\section{Representation}

There are many different ways of representing relations. One way is to
describe them by properties, as we did above. For infinite sets,
that's about all we can do. But for finite sets, we usually use some
method that explicitly enumerates all the elements of the
relation. Some alternatives are lists, matrices and graphs. Why do we
have so many different ways to represent relations? Different
representations may be more efficient for encoding different problems
and also tend to highlight different properties of the relation.

\subsubsection{Lists}

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

\begin{example}  
  \label{ex:0123-abc}
  The relation from $\{ 0, 1, 2, 3 \}$ to $\{ a,b,c \}$
  defined by the list:

  $\{ (0,a), (0, c), (1, c), (2, b), (1,a) \}$.

\end{example}
\begin{example}
  The divisibility relation on natural numbers $\set{1,\dots,12}$ is
  represented by the list:
\begin{align*}
\{(1,1), (1,2), (1,3), (1,4), (1,5),
  (1,6), (1,7), (1,8), (1,9), (1,10), (1,11), (1,12), (2,2), (2,4), & \\ 
  (2,6), (2,8), (2,10), (2,12), (3,3), (3,6), (3,9), (3,12),
  (4,4), (4,8), (4,12), (5,5), (6,6), & \\ 
  (6,12), (7,7), (8,8), (9,9), (10,10), (11,11), (12,12) & \}.
\end{align*}

\end{example}

We can recognize certain properties by examining this representation:
\begin{description}

\item[Reflexivity:] Contains all pairs $(a,a)$.

\item[Symmetry:] Contains $(a,b)$ then contains $(b,a)$.

\item[Transitivity:] Contains $(a,b)$ and $(b,c)$ then contains $(a,c)$.
\end{description}

\subsubsection{Boolean Matrices}

Boolean matrices are a convenient representation for representing
relations in computer programs. The rows are for elements of $A$,
columns for $B$, and for every entry there is a $1$ if the pair is in
the relation, $0$ otherwise.
\begin{example}
  The relation from Example~\ref{ex:0123-abc} is represented by the
  matrix
  \begin{displaymath}
    \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{displaymath}
\end{example}
\begin{example}
  The divisibility relation over $\{1,2,\dots,12\}$ is 
  represented by the enormous matrix
  \begin{displaymath}
    \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{displaymath}
\end{example}

Again, properties can by recognized by examining the representation:
\begin{description}

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

\item[Symmetry:] the matrix is clearly not symmetric across the major diagonal.

\item[Transitivity:] not so obvious\dots
\end{description}


\subsubsection{Digraphs} 

We can draw a picture of a relation $R \subseteq A \times B$ by
drawing a dot for every element of $A$, a dot for every element of
$B$, and an arrow from $a \in A$ to $b \in B$ iff $a R b$. Such a
picture is called a \emph{directed graph}, or \emph{digraph} for
short.
\begin{example}
  \begin{samepage}
    The relation from Example~\ref{ex:0123-abc} is represented by the digraph
    \begin{center}\includegraphics{figures/0123abc.mps}\end{center}
  \end{samepage}
\end{example}

Digraphs are mainly used for relations where $A = B$, i.e., for
relations on a finite set $A$. To represent such a relation as a
digraph we draw a dot (vertex) for each element of $A$, and draw an
arrow from first element to second element of each pair in the
relation. The digraph may contain self-loops, i.e. arrows from a dot
to itself, associated to the elements $a$ such that $(a,a)$ is in the
relation.

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

\begin{description}
\item[Reflexivity:] All nodes have self-loops.
\item[Symmetry:] all edges are bidirectional.
\item[Transitivity:] Short-circuits---for any sequence of consecutive
  arrows, there is a single arrow from the first to the last node.
\end{description}


\section{Operations on Relations}

\subsection{Inverse}

If $R$ is a relation on $A \times B$, then $R^{-1}$ is a relation on
$B\times A$ given by $R^{-1} = \set{(b,a) \mid (a,b) \in R}$.  It's
just the relation ``turned backwards.''
\begin{example}
  Inverse of ``is taking class'' (Relation~\ref{classes} in
  Example~\ref{ex:initial-relations}) is the relation ``has as a
  student'' on the set $\{\mbox{classes at
  MIT}\}\times\{\mbox{students at MIT}\}$; a relation from classes to
  students.
\end{example}

We can translate the inverse operation on relation to operations on the
various representations of a relation. Given the matrix for $R$, we
can get the matrix for~$R^{-1}$ by transposing the matrix for~$R$ (note
that the inverse of a relation is not the same thing as the inverse of
the matrix representation). Given a digraph for $R$, we get the graph
for~$R^{-1}$ by reversing every edge in the original digraph.


\subsection{Composition}

The \emph{composition} of relations $R_1 \subseteq A \times B$ and $R_2
\subseteq B \times C$ is the relation
\begin{displaymath}
  R_2 \circ R_1 =\{(a,c) \mid
  (\exists b) ((a,b) \in R_1) \wedge ((b,c) \in R_2)\}.
\end{displaymath}

In words, the pair $(a,c)$ is in $R_2\circ R_1$ if there exists an
element $b$ such that the pair $(a,b)$ is in $R_1$ and the pair $(b,c)$
is in $R_2$. Another way of thinking about this is that a ``path''
exists from element $a$ to $c$ via some element in the set
$B$\footnote{Notice that $R_2\circ R_1$ and $R_1\circ R_2$ are
different.  The symbol~$\circ$ is a source of eternal confusion in
mathematics---if you read a book you should always check how the
authors define~$\circ$---some of them define composition the other way
around.}.

\begin{example}
  The composition of the relation ``is taking class''
  (Relation~\ref{classes} in Example~\ref{ex:initial-relations}) with
  the relation ``has lecture in'' (Relation~\ref{lectures} in
  Example~\ref{ex:initial-relations}) is the relation ``should go to
  lecture in'', a relation from $\{\mbox{students at MIT}\}$ to
  $\{\mbox{rooms at MIT}\}$.
\end{example}
\begin{example}
  Composition of the parent-of relation with itself gives grandparent-of.
  Composition of the child-of relation with the parent-of relation gives
  the sibling-of relation. (Here we relax the meaning of sibling to include that a person is the sibling of him/herself.) Does composition of parent-of with child-of
  give married-to\slash domestic partners?  No, because that misses
  childless couples.
\end{example}
\begin{example}
  Let $B$~be the set of boys, $G$~be the set of girls, $R_1 \subseteq
  B \times G$ consist of all pairs $(b,g)$ such that $b$~is madly in
  love with~$g$, and $R_2 \subseteq G \times B$ consist of all pairs
  $(g,b)$ such that $g$~is madly in love with~$b$. What are the
  relations $R_2 \circ R_1$ and $R_1 \circ R_2$, respectively?
\end{example}


\subsubsection{Computing Composition and Path Lengths}
If we represent the relations as matrices, then we can compute the
composition by a form of ``boolean'' matrix multiplication, where $+$
is replaced by $\vee$ (Boolean OR) and $\times$ is replaced by $\wedge$
(Boolean AND).

\begin{example}
Let $R_1$ be the relation from Example~\ref{ex:0123-abc}:
\[\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}
\]
Let $R_2$ be the relation from $\{ a, b, c \}$ to $\{ d,e,f \}$ given by:
\[\begin{array}{r|ccc}
& d&  e&  f\\
\hline  
a& 1&  1&  1\\
b& 0&  1&  0\\
c& 0&  0&  1
\end{array}
\]
Then $R_2 \circ R_1 = \{ (0,d), (0,e), (0,f), (1,d), (1,e), (1,f), (2,e) \}$, 
that 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}
\]
\end{example}

A relation on a set~$A$ can be composed with itself. The composition
$R \circ 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: $R^1 = R$, $R^n = R \circ R^{n-1}$.

\begin{example}
  \begin{samepage}
    Consider the relation $R = \{(a,b), (a,c),
    (b,d), (d,e)\}$ or:
    \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}
    $R^2$ will be:
    \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}
    $R^3$ will be:
    \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}

\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,a_{i+1}) \in R$ for every $i < k$.  We
  call $k$ the \emph{length} of the path.

\end{definition}
In the digraph model, a path is something you can trace out by following
arrows from vertex to vertex, without lifting your pen.  Note that a
singleton vertex is a length~0 path (this is just for convenience). A
\emph{simple path} is a path with no repeated vertices.

\begin{lemma}
  \label{lem:Rn-paths}
  $R^n = \{(a,b) \mid \mbox{there is a length $n$ path from $a$ to $b$
    in $R$}\}$
\end{lemma}

\begin{proof}
  By induction. Let
  \begin{displaymath}
    P(n) ::= \mbox{$R^n = \{(a,b) \mid \mbox{there is a length $n$ path
        from $a$ to $b$ in $R$}\}$}.
  \end{displaymath}

  The base case is clear. There is exactly one edge from $a$ to $b$
  for every $(a,b) \in R$. And there is exactly one pair $(a,b) \in R$
  for every edge from $a$ to $b$, $P(1)$~is true. Note that since the
  induction hypothesis is an equality we have to prove both sides.
  
  For the inductive step, suppose $P(n)$ is true.  

  First consider a path $a_0,\dots,a_{n+1}$ in $R$. This is a path
  $a_0,\dots,a_n$ in $R$ followed by a pair $(a_n,a_{n+1})$ of
  $R$. By the inductive hypothesis, we can assume that $(a_0,a_n) \in
  R^n$. And we have already mentioned that $(a_n,a_{n+1}) \in
  R$. Therefore $(a_0,a_{n+1}) \in R^{n+1}$ by the definition of
  composition. Thus, every path of length $n+1$ corresponds to a
  relation in~$R^{n+1}$.
  
  Now consider a pair $(a,b) \in R^{n+1}$. By the definition of
  composition, there exists a $c$ such that $(a,c) \in R^n$ and $(c,b)
  \in R$. By the inductive hypothesis, we can assume that $(a,c)$
  corresponds to a length $n$ path from $a$ to $c$, and since $(c,b)
  \in R$ there is an edge from $c$ to $b$. Thus, there is a length
  $n+1$ path from $a$ to $b$. To conclude, $P(n) \implies P(n+1)$.
\end{proof}



\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


\subsubsection{The transitive closure}

The transitive closure is a bit more complicated than the closures
above.
\begin{lemma}
  Let $R$ be a relation on the set $A$.
  The transitive closure of a relation $R$ is the set 
  \begin{displaymath}
    S = \{(a,b) \in A^2 \mbox{given there is a path from $a$ to $b$ in $R$}\}.
  \end{displaymath}
\end{lemma}
\begin{proof}
  Obviously, $R \subseteq S$.
  Next, we show that $S$ is transitive.  Suppose $(a,b)\in S$ and
  $(b,c) \in S$.  This means that there is an $(a,b)$ path and a
  $(b,c)$ path in $R$.  If we ``concatenate'' them (attach the end of
  the $(a,b)$ path to the start of the $(b,c)$ path, we get an $(a,c)$
  path.  So $(a,c) \in S$.  So $S$ is transitive.
  
  Finally, we need to show that $S$ is the smallest transitive
  relation containing $R$. So consider any transitive relation $T$
  containing $R$. We have to show that $S \subseteq T$. Assume for
  contradiction that $S \nsubseteq T$.  This means that some pair
  $(a,b) \in S$ but $(a,b) \notin T$.  In other words, there is a
  path $a_0,\dots,a_k=b$ in $R$ where $k \geq 1$ and $(a_0,a_k)
  \notin T$.  Call this a \emph{missing path}. Now let $M$ be the set
  of missing paths.
  
  Now we use well-ordering. We have just claimed that the set $M$ of
  missing paths is nonempty. So consider a shortest missing path
  $s_0,\dots,s_m$. We will derive a contradiction to this being the
  shortest missing path.
  
  Case 1: $m=1$. Then $s_0,s_1$ is a path in $R$, so $(s_0,s_1) \in
  R$. But we know $T$ contains $R$, so $(s_0,s_1)\in T$, a
  contradiction.
  
  Case 2: $m>1$. Then $s_1,\dots,s_{m-1}$ is a path in $R$ ($m-1 >
  0$). But it is shorter than our original shortest missing path, so
  cannot be missing. Thus $(s_1,s_{m-1}) \in T$. Also we have
  $(s_{m-1},s_m) \in T$ since $R \subseteq T$. Thus by transitivity
  of $T$, $(s_1,s_m)\in T$, a contradiction.
  
  We get a contradiction either way, so our assumption (that $S
  \nsubseteq T$) is false. This completes the proof.
\end{proof}
Wait a minute. Well-ordering is applied to sets of \emph{numbers}; we
applied it to a set of paths!  How?  Well, look at the set of
``lengths of missing paths''.  It is nonempty, so has a smallest
element. There is path that has this length---so it is a shortest
path.
\begin{example}
  \begin{samepage}
    The transitive 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 & 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}

\subsubsection{Computing the Transitive Closure}

With reflexive and symmetric closure, it is pretty clear how to
actually build them. But for transitive closure, how do we actually
find all the paths we need?

Let's start by finding paths of a given length. Recall the definition of
$R^n$ of $R$ composed with itself $n$ times.
We proved that
$R^n = \{(a,b) given
\mbox{there is a length $n$ path from $a$ to $b$ in $R$}\}$.
This means we can write the transitive closure of $R$ as $R \cup R^2
\cup R^3 \cup \cdots$.  Better---since we know how to do
composition---but still a problem: there are infinitely many terms!
\begin{lemma}
  Suppose $A$ has $n$ elements and that $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 $n$ from
  $a$ to $b$ in $R$.
\end{lemma}
\begin{proof}
  We'll use well-ordering (again).  Consider the shortest path
  $a=a_0,a_1,\dots,a_k$ from $a$ to $b$ (we know one exists, so by
  well-ordering there is a shortest one).  Suppose $k > n$.  Then
  some element of $A$ appears twice in the list (with more than $n$
  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>n$.
\end{proof}
So we don't need infinitely many terms.  It is enough to take paths of
length at most $n$, namely $R^1\cup R^2\cup\cdots\cup R^n$.

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


\section{Equivalence Relations and Partitions}

We can use properties of relations to classify them into different
types. We will be considering two important types of relations,
\emph{equivalence relations} and \emph{partial orders}. 

\begin{definition}
  An \emph{equivalence relation} is a relation that is reflexive,
  symmetric and transitive.
\end{definition}

For example, the ``roommates'' relation is an equivalence relation.
So is ``same size as'', and ``on same Ethernet hub''.  A trivial
example is the $=$ relation on natural numbers.  The hallmark of
equivalence relation is the word \emph{same}. It provides a way to
hide unimportant differences. Using an equivalence relation we can
actually partition the universe into subsets of things that are the
``same'', in a natural way.

\begin{definition}
  A \emph{partition} of a set $A$ is a collection of subsets
  $\{A_1,\dots,A_k\}$ such that any two of them are disjoint (for any
  $i\neq j$, $A_i\cap A_j=\emptyset$) and such that their union is
  $A$.
\end{definition}


Let $R$ be an equivalence relation on the set $A$. For an element
$a\in A$, let $[a]$ denote the set $\{b\in A \mbox{ given } a\sim_R
b\}$.  We call this set the \emph{equivalence class of $a$ under $R$}.
We call $a$ a \emph{representative} of $[a]$.

\begin{lemma}
  \label{lem:partition} The sets $[a]$ for $a\in A$ constitute a
  partition of $A$.  That is, for every $a,b\in A$, either $[a]=[b]$
  or $[a]\cap [b]=\emptyset$.
\end{lemma}

\begin{proof}
  Consider some arbitrary $a,b\in A$. If either $[a]=[b]$ or $[a] \cap
  [b]=\emptyset$ then we are done, so suppose not.  Let $c$ be any
  element that is in one of the sets but not the other.  Without loss
  of generality we can assume that $c \in [b]-[a]$.  (We know that
  either $c \in [b]-[a]$ or $c \in [a]-[b]$. In the latter case we can
  simply swap $a$ and $b$ and reduce to the first case.)  Let $d$ be
  any element in $d \in [a] \cap [b]$. We will get a contradiction by
  showing that $a\sim_R c$ and therefore that $c\in [a]$. First,
  $a\sim_R d$ because $d\in [a]$ (note that $d=a$ is a possibility but
  this is ok because $R$ is reflexive).  Second, $d\sim_R b$ and
  $b\sim_R c$ because both $c,d\in [b]$ and $R$ is symmetric.  This
  implies, by transitivity, that $d\sim_Rc$.  Finally, by
  transitivity, $a\sim_R c$ because $a\sim_R d$ and $d\sim_R c$.
\end{proof}

Note that all three properties of equivalence relations were used in
this proof. Checking that the proof uses all available assumptions if
usually a good sanity check when writing proofs---if one of the
properties you assumed were not needed, you have either made a mistake
or proven a much more strong theorem than you thought---\eg if you
didn't use transitivity anywhere in the proof of
Lemma \ref{lem:partition}, you would be proving that any reflexive
symmetric relation produces a partition, which is false.

\begin{lemma}
  Any partition $\{A_1,\dots,A_k\}$ of $A$ defines an equivalence
  relation by letting $a \sim_R b$ iff $a$ and $b$ are in the same
  $A_i$.
\end{lemma}

\begin{proof}
  Reflexivity: for all $a$ we know $a\in A_i$ for some $i$, by
  definition of partition. Clearly $a$ and $a$ are in the same $A_i$,
  \ie $a\sim_R a$.

  Symmetry: Assume $a\sim_R b$, that is $a$ and $b$ are in the 
  same $A_i$. Also $b$ and $a$ are in the same $A_i$
  and therefore $b\sim_R a$.

  Transitivity: Assume $a\sim_R b$ and $b\sim_R c$.
  By definition of $\sim_R$, $a$ and $b$ are in the same 
  $A_i$ for some $i$, and $b$ and $c$ are in the same $A_j$
  for some $j$.
  But by definition of partition $b$ cannot be in two different $A_i$'s.
  So, it must be $A_i=A_j$ and $a$ and $c$ are in the same 
  $A_i$, proving $a\sim_R c$.
\end{proof}
Therefore, we can look at partitions and at equivalence relations as
the same thing. 



\subsection{Integers modulo m}

A familiar and important equivalence relation on integers
(positive, negative and $0$) is:

\begin{definition}
  If $a$ and $b$ are integers, then we say that $a \equiv b \pmod m$
  if $m \divides (a-b)$.
\end{definition}

$a \equiv b \pmod m$ is pronounced ``$a$ is equivalent to $b$ modulo
$m$''. An equivalent formulation says that $a=b+km$ for some integer
$k$.

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

\begin{proof}
  We need to show that the relation is reflexive, symmetric, and
  transitive.

  Reflexive: Clearly $m \divides (a-a) = 0$, so $a \equiv a \pmod m$.

  Symmetric: If $a=b+km$ then $b=a+(-k)m$.
  
  Transitive: Suppose $a \equiv b \pmod m$ and $b \equiv c \pmod m$.
  Then $m \divides (a-b)$ and $m \divides (b-c)$.  So $(a-b)=k_1 m$
  and $(b-c)=k_2 m$.  So $(a-c)=(a-b)+(b-c)=(k_1+k_2)m$.  Therefore
  $m \divides (a-c)$.
\end{proof}
The equivalence class of $a$ is the set $[a] = \{ b \in
\integers \divides a \equiv b \pmod m \}$, or $\{ km + a \divides k
\in \integers\}$.

It turns out that we can extend a lot of standard arithmetic to work
modulo $m$.  In fact, we can define notions of sum and product for the
equivalence classes mod $m$.  For example, we define $[a]+[b]$, given
two equivalence classes mod $m$, to be the equivalence class $[a+b]$.
This is not as obvious as it seems: notice that the result is given in
terms of $a$ and $b$, two selected representatives from the
equivalence classes, but that it is supposed to apply to the
equivalence classes themselves.  To prove that this works, we have to
show that it doesn't matter which representatives of the equivalence
classes we choose:


\begin{lemma}
  If $a \equiv x \pmod m$ and $b \equiv y \pmod m$ then $(a+b) \equiv
  (x+y) \pmod m$.
\end{lemma}
\begin{proof}
  $m \divides (a-x)$ and $m \divides (b-y)$ so $m \divides ((a-x)+(b-y)) =
  (a+b)-(x+y)$,  
\end{proof}
It follows that if we are interested only the result of the addition
modulo $m$---which is the case, for example, in the RSA
cryptosystem---then we can at any time replace a given number with a
different number equivalent to it, without changing the value
(equivalence class) of the final answer. The same fact can be proven
for multiplication.  

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

\subsection{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

\section{Partial Orders}

Partial orders are another type of binary relation that is very
important in computer science. They have applications to task
scheduling, database concurrency control, and logical time in
distributed computing,

\begin{definition} 
  A binary relation $R \subseteq A \times A$ is a
  \emph{partial order} if it is reflexive, transitive, and
  antisymmetric.
\end{definition}

Recall that antisymmetric mean $a R b \wedge b R a \Rightarrow a=b$,
or $\forall a \neq b, a R b \Rightarrow \neg b R a$. In other words
this relation is \emph{never} symmetric! This single property is what
distinguishes it from an equivalence relation. The reflexivity,
antisymmetry and transitivity properties are abstract properties that
generally describe ``ordering'' relationships.

For a partial order relation we often write an ordering-style symbol
like $\preceq$, instead of just a letter like $R$, for a partial order
relation.  This lets us use notation similar to $\le$.  For example,
we write $a \prec b$ if $a \preceq b$ and $a \ne b$.  Similarly, we
write $b \succeq a$ as equivalent to $a \preceq b$. But this could be
misleading, note that $\geq$ is a partial order on natural numbers, as
well as $\leq$.  If we use the $\preceq$ symbol for $\geq$, things
look really funny.  In cases like this it is better to use $R$.

A partial order is always defined on some set $A$.  The set together
with the partial order is called a ``poset'':
\begin{definition}
  A set $A$ together with a partial order $\preceq$ is called a 
  \emph{poset}  $(A, \preceq)$.
\end{definition}
\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}



\subsection{Directed Acyclic Graphs}

A common source of partial orders in computer science is in ``task
graphs''.  You have a set of tasks $A$, and a relation $R$ in which
$aRb$ means ``$b$ cannot be done until $a$ is finished''.
Implicitly, ``if all the things that point at $b$ are done, I can do
$b$.''
This can be nicely drawn as a graph.  We draw an arrow from $a$ to
$b$ if $a R b$.
\begin{samepage}
  For example, below is a graphs that describes the order in which one
  would put on clothes. The set is of clothes, and the edges say what
  should be put on before what.
  \begin{center}\includegraphics{figures/clothes.mps}\end{center}
\end{samepage}


The ``depends on'' graph imposes an ordering on tasks. But what if I
add a relation edge from belt to underwear?  In that case my
dependency graph stops making sense: there is no way to get dressed!
What goes wrong?  A cyclic dependency.

\begin{definition}
  A \emph{cycle} is a path that ends where it started (\ie the last
  vertex equals the first).
\end{definition}

\begin{definition}
  A \emph{directed acyclic graph (DAG)} is a directed graph with no
  cycles.
\end{definition}

\begin{lemma}
  Any partial order is a DAG.
\end{lemma}
\begin{proof}
  Suppose the graph representation of a partial order $\preceq$ has a
  cycle $a_1,\dots,a_k,a_1$. Then by transitivity of $\preceq$
  (with an induction hiding inside) we have $a_1 \preceq a_k$. We
  also have $a_k \preceq a_1$. This violates the antisymmetry of
  $\preceq$, a contradiction.
\end{proof}

But is it a partial order?  No, because it isn't reflexive or
transitive.  But there is a natural extension: the reflexive
transitive closure \emph{is} a partial order.  It gives the relation
``must be done before.''

\begin{lemma}
  The transitive reflexive closure of a DAG is a partial order.
\end{lemma}
\begin{proof}
  Let the DAG be $R$ and its transitive reflexive closure $S$.
  $S$ is transitive and reflexive; we just need to prove that it is
  antisymmetric. We do so by contradiction. Suppose that there exists
  some $a,b$ such that $a \neq b$, $a \sim_S b$, and $b \sim_S a$. In
  other words, there is a path from $a$ to $b$ and a path from $b$
  to $a$ in $R$. If we attach these two paths, we get a path from $a$
  to $a$ in $R$, \ie $R$ contains a cycle. This contradicts the
  assumption that $R$ is acyclic.
\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{Partial vs. Total Orders}

A partial order is called \emph{partial} because it is not necessary
that an ordering exists between every pair of elements in the set.
\begin{example}
  Lshoe and Rshoe have no prescribed ordering between them.
\end{example}
\begin{example}
  For two sets, it's not necessary that either be a subset of the
  other.
\end{example}
When there is no prescribed order between two elements we say that they
are ``incomparable''. 
\begin{definition}
  We say that $a$ and $b$ are \emph{incomparable} if neither $a
  \preceq b$ nor $b \preceq a$, and that they are \emph{comparable} if
  $a \preceq b$ or $b \preceq a$.
\end{definition}
\begin{example}
  For subsets of $\naturals$, $\{ 1,2,3 \}$ and $\{ 2,3,4 \}$ are
  incomparable.
\end{example}
However, a partial order need not have incomparable elements.  As a
special case, we can have a partial order in which there is a
specified order between every pair of elements.
\begin{definition}
  A poset $(S, \preceq)$ is \emph{totally ordered} if $(\forall a,b
  \in S) [ a \preceq b \vee b \preceq a ]$.
\end{definition}

The DAG for a total order looks like a line.

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

Sometimes when we have a partial order, \eg of tasks to be
performed, we want to obtain a consistent total order.  That is, an
order in which to perform all the tasks, one at a time, so as not to
conflict with the precedence requirements. 

The task of finding an ordering that is consistent with a partial
order is known as \emph{topological sorting}---probably because the
sort is based only on the shape, \ie topology, of the poset, and not
on the actual values.
\begin{definition}
  A \emph{topological sort} of a finite poset $(A, \preceq)$ is a
  total ordering of all the elements of $A$, $a_1, a_2, \cdots, a_n$
  in such a way that for all $i < j$, either $a_i \preceq a_j$ or
  $a_i$ and $a_j$ are incomparable.
\end{definition}
For example, underwear, shirt, Lsock, Rsock, pants, sweater, Lshoe, Rshoe,
belt, jacket is a topological sort of how to dress.
One of the nice facts about posets is that such an ordering always
exists and is even easy to find:
\begin{theorem}
  \label{thm:topological}Every finite poset has a topological sort.
\end{theorem}
The basic idea to prove this theorem is to pick off a ``first''
element and then proceed inductively.
\begin{definition}
  A \emph{minimal} element $a$ in a poset $(A, \preceq)$ is one for
  which $(\forall b \in A) [a \preceq b \lor \mbox{$a$ and $b$ are
    incomparable}]$.  Equivalently, it is an element $a$ for which
  $(\nexists b \in A) [b \prec a]$.
\end{definition}
\begin{lemma}
  Every finite poset $(A,\preceq)$ has a minimal element.
\end{lemma}
\begin{proof}
  For every element $a \in A$, let $p_a = \{b \in A \mbox{ given } b \prec
  a\}$, \ie $p_a$ is the set of predecessors of $a$ according to the
  partial order. It is enough to show that there exists an $a \in A$
  such that $p_a = \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}

\iffalse
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}
\begin{remark}
  Notice that there can be more than one minimal element. There are
  four in the clothes example: Lsock, Rsock, underwear, and shirt.
\end{remark}
\begin{remark}
  An infinite poset might have no minimal element. Consider $\integers$.
\end{remark}
Now we can prove the existence of the topological sort.
\begin{proof}[Proof of Theorem \ref{thm:topological}]
  Let $P(n)$ be ``any poset with $n$ elements has a topological
  sort''.  Base case: for a poset with one element the one element
  makes a topological sort.

  Inductive step: Assume $P(n)$. Consider a poset of $n+1$ elements.
  By the previous lemma it has a minimal element $u$.  Consider the
  same relation on $A-\{u\}$.  It is easy to check that it is still
  reflexive, transitive, and anti-symmetric.  So by the inductive
  hypothesis, $A-\{u\}$ has a topological sort.  We put $u$ first and
  now have a topological sort on the whole thing.  (According to the
  definition of topological sort, $u$ can't be in the wrong order
  w.r.t. any of the later elements.)

  Thus every finite poset has a topological sort, by induction.
\end{proof}
\fi

\begin{example}
  Consider the dressing example.  Construct an ordering by picking
  one item at a time.  At each step, look at the poset formed by the
  remaining elements.  Lsock, shirt, sweater, Rsock, underwear,
  pants, Lshoe, belt, jacket, Rshoe
\end{example}
\begin{example}
  Subsets of $\{ 1,2,3,4 \}$:

  $\emptyset$ is the unique minimal element, then we have choices, \eg do: \\
  $\{ 1 \}$, $\{ 2 \}$, $\{ 1,2 \}$,
  $\{ 3 \}$, $\{ 1,3 \}$, $\{ 2,3 \}$, $\{ 1,2,3 \}$, \\
  $\{ 4 \}$, $\{ 1,4 \}$, $\{ 2,4 \}$, $\{ 3,4 \}$, 
  $\{ 1,2,4 \}$, $\{ 1,3,4 \}$, $\{ 2,3,4 \}$, $\{ 1,2,3,4 \}$
\end{example}


\subsection{Parallel Task Scheduling}

When elements of a poset 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 poset 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
(Lsock, Rsock, 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 Lshoe, Rshoe, 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 poset is a sequence of elements of the domain,
  each of which is smaller than the next in the partial order
  ($\preceq$ and $\neq$). The \emph{length} of a chain is the number
  of elements in the chain.
\end{definition}

Note that a chain is just a path in the corresponding graph.

Clearly, the parallel time is at least length of any chain.  For if we
used less time, then two tasks in the chain would have to be done at
the same time.  (This is ``obvious,'' but is formalized as an
application of the ``pigeonhole principle'' we will study shortly.)
But by definition of chains this violates precedence constraints.  A
longest chain is also known as a \emph{critical path}.  So we need at
least $t$ steps, where $t$ is the length of the longest chain.
Fortunately, it is always possible to use only $t$:

\begin{theorem}
  \label{thm:parallel}
  Given any finite poset $(A, \preceq)$ for which the longest chain
  has length $t$, it is possible to partition $A$ into $t$ subsets,
  $A_1, A_2, \cdots, A_t$ such that 
  \begin{displaymath}
    (\forall i \in \{1,2,\dots,t\})
    (\forall a \in A_i) 
    (\forall b \prec a) 
    \bigl[b \in A_1 \cup A_2 \cup \cdots \cup A_{i-1} \bigr].
  \end{displaymath}
\end{theorem}
That is, we can divide up the tasks into $t$ groups so that for each
group $A_i$, all tasks that have to precede tasks in $A_i$ are in
smaller-numbered groups.
\begin{corollary}
  For $(A, \preceq)$ and $t$ as above, it is possible to schedule all
  tasks in $t$ steps.
\end{corollary}
\begin{proof}
  For all $i$, schedule all 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 = length of longest chain
\end{corollary}
So it remains to prove the partition theorem:
\begin{proof}[Proof of Theorem \ref{thm:parallel}]
  Construct the sets $A_i$ as follows:
  \begin{displaymath}
    A_i = \{a \in A \mbox{ given longest chain ending in $a$ has length $i$}\}.
  \end{displaymath}
  This gives just $t$ sets, because the longest chain has length $t$.
  Also, each $a \in A$ belongs to exactly one $A_i$.
  To complete the proof, we also need to show
  \begin{displaymath}
    (\forall i \in \{1,2,\dots,t\})
    (\forall a \in A_i) 
    (\forall b \prec a) 
    \bigl[b \in A_1 \cup A_2 \cup \cdots \cup A_{i-1} \bigr].
  \end{displaymath}
  The proof is by contradiction. Assume that $a \in A_i$ and that
  there exists a $b \notin A_1 \cup A_2 \cup \cdots \cup A_{i-1}$ such
  that $b \prec a$. Then there is a chain of length exceeding $i-1$ ending
  in $b$. This means, since $b \prec a$, that there is a chain of
  length $>i$ ending in $a$, which means that $a \notin A_i$.
\end{proof}
So with an unlimited number of processors, the time to complete all
the tasks is the length of the longest 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 incomparable elements.
\end{definition}
\begin{corollary}
  \label{cor:parallel}
  If $t$ is the length of the longest chain in a poset $(A, \preceq)$
  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. Then either $a \prec
  b$ or $b \prec a$, which---again by the proof of
  Theorem \ref{thm:parallel}---contradicts the assumption that $a$
  and $b$ are in the same $A_i$.
\end{proof}

\subsubsection{Dilworth's Theorem}

We can use the above corollary to prove a famous result about posets:
\hyperdef{rule}{Dilworth}{\begin{theorem}[Dilworth]
  \label{thm:Dilworth}
  For all $t$, every poset with $n$ elements must have either a chain
  of size greater than $t$ or an antichain of size at least $n / t$.
\end{theorem}
}

\begin{proof}
  Assume there is no chain of length greater than $t$.
  So, longest chain has length at most $t$.
  Then by Corollary \ref{cor:parallel}, the $n$ elements can be
  partitioned into at most $t$ antichains.
  Let $\ell$ be the size of the largest antichain.
  Since there are at most $t$ antichains, every antichain contains
  at most $\ell$ elements, and an element belongs
  to exactly one antichain, $\ell t \geq n$.
  So there is an antichain with at least $n / t$ elements.
\end{proof}
\begin{corollary}
  \label{cor:Dilworth}
  Every poset with $n$ elements has a chain of length greater
  than $\sqrt{n}$ or an antichain of size at least $\sqrt{n}$.
\end{corollary}
\begin{proof}
  Set $t = \sqrt{n}$ in Theorem \ref{thm:Dilworth}.
\end{proof}
\begin{example}
  In the dressing poset, $n = 10$.
  Try $t = 3$.  Has a chain of length $4$.
  Try $t = 4$.  Has no chain of length $5$, but has an antichain of size 
  $4 \geq 10 / 4$.
\end{example}
Posets arise in all sorts of contexts, and when they do, Dilworth's
theorem can have interesting implications.



\subsubsection{Increasing and Decreasing Sequences}

\begin{theorem}
  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{theorem}
\begin{example}
  $\langle6,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}
We can prove this using Dilworth's theorem; the trick is to define the 
appropriate poset.
The domain is the set of values in the sequence.
For the ordering, define $a \preceq b$ if either $a = b$, or else
($a < b$ and $a$ comes before $b$ in the sequence).
You should check that this is reflexive (stated explicitly), 
transitive, and antisymmetric.
A chain corresponds to a sequence that increases in value and moves to
the right, that is, an increasing sequence.
But what does an antichain correspond to?
\begin{lemma}
  If $a$ and $b$ are incomparable (under the partial order) and $a > b$ (as
  numbers) then $a$ precedes $b$ in the 
  sequence.
\end{lemma}
\begin{proof}
  By contradiction.
  Assume $b$ precedes $a$ in the sequence.
  Then $b < a$ and $b$ precedes $a$ in the sequence, so $b \preceq a$
  in the partial order.
  This contradicts our assumption that $a$ and $b$ are incomparable.
\end{proof}
We extend this lemma to more than 2 elements:
\begin{lemma}
  If $a_1, a_2, \cdots , a_t$ are incomparable and $a_1 > a_2 > \cdots
  > a_t$ then $a_1, a_2, \cdots a_t$ form a decreasing subsequence.
\end{lemma}
\begin{proof}
  For all $i$, the fact that $a_i > a_{i+1}$ implies that $a_i$
  precedes $a_{i+1}$ in the sequence, by the previous lemma.
\end{proof}
So given an antichain, arrange the elements so that they are in
decreasing order and the ``left of'' relation follows, giving a
decreasing subsequence.
Dilworth's theorem implies that there is either a chain of size 
greater than $\sqrt{n}$ or an antichain of size at most $\sqrt{n}$.
By the analysis above, this yields either an increasing sequence of
length greater than $\sqrt{n}$
or a decreasing subsequence of length at most $\sqrt{n}$. 


% \end{document}

% \endinput

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

\end{document}
