% transitive closure - concerned that this is misdefined
% n >= 2 on bottom of page 10
% minimal elements on top?

\documentclass[12pt,twoside]{article}
\usepackage{light}

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

%  Custom macros.

\newcommand{\mfigure}[3]{\bigskip\centerline{\resizebox{#1}{#2}{\includegraphics{#3}}}\bigskip}
\newcommand{\edge}[2]{#1\text{---}#2}
\newcommand{\arc}[2]{#1\!\longrightarrow\!#2}

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

\begin{document}

\lecture{Relations}{October 7, 2004}

\section{Relations}

A ``relation'' is a mathematical tool used to describe relationships
between set elements.  Relations are widely used in computer science,
especially in databases and and scheduling applications.

Formally, a \term{relation} from a set $A$ to a set $B$ is a subset $R
\subseteq A \times B$.  For example, suppose that $A$ is a set of
students, and $B$ is a set of classes.  Then we might consider the
relation $R$ consisting of all pairs $(a, b)$ such that student $a$ is
taking class $b$:
%
\[
R = \set{ (a, b) \mid \text{student $a$ is taking class $b$} }
\]
%
Thus, student $a$ is taking class $b$ if and only if $(a, b) \in R$.
There are a couple common, alternative ways of writing $(a, b) \in R$
when we're working with relations: $aRb$ and $a \sim_R b$.  The
motivation for these alternative notations will become clear shortly.

\subsection{Relations on One Set}

We're mainly going to focus on relationships between elements of a
single set; that is, relations from a set $A$ to a set $B$ where $A =
B$.  Thus, a \term{relation} on a set $A$ is a subset $R \subseteq A
\times A$.  Here are some examples:

\begin{itemize}

\item Let $A$ be a set of people and the relation $R$ describe who
likes whom; that is, $(x, y) \in R$ if and only if $x$ likes $y$.

\item Let $A$ be cities.  Then we can define a relation $R$ such that
$xRy$ if and only if there is a nonstop flight from city $x$ to city
$y$.

\item Let $A = \mathbb{Z}$, and let $xRy$ hold if and only if $x
\equiv y \pmod 5$.

\item Let $A = \mathbb{N}$, and let $xRy$ hold if and only if $x \mid
y$.

\item Let $A = \mathbb{N}$, and let $xRy$ hold if and only if $x \leq
y$.

\end{itemize}

\noindent The last examples clarify the reason for using $xRy$ or $x
\sim_R y$ to indicate that the relation $R$ holds between $x$ and $y$:
many common relations ($<$, $\leq$, $=$, $\mid$, $\equiv$) are
expressed with the relational symbol in the middle.

\subsection{Relations and Directed Graphs}

A relation can be modeled very nicely with a directed graph.  For
example, the directed graph below describes the ``likes'' relation on
a set of three people:

\mfigure{!}{1.25in}{likes-digraph}

From this directed graph, we can conclude that:
%
\begin{itemize}
\item Julie likes Bill and Bob, but not herself.
\item Bill likes only himself.
\item Bob likes Julie, but not himself.
\end{itemize}
%
In fact, everything about the ``likes'' relation is conveyed by this
graph, and nothing more.  This is no coincidence; a set $A$ together
with a relation $R$ is precisely the same thing as a directed graph $G
= (V, E)$ with vertex set $V = A$ and edge set $E = R$.

\section{Properties of Relations}

Many relations that arise in practice possess some standard
properties.  A relation $R$ on set $A$ is:

\begin{enumerate}

\item \term{reflexive} if $xRx$ for all $x$ in $A$.

(Everyone likes themself.)

\item \term{symmetric} if for all $x, y \in A$, $xRy$ implies $yRx$.

(If $x$ likes $y$, then $y$ likes $x$.)

\item \term{antisymmetric} if for all $x, y \in A$, $xRy$ and $yRx$
imply that $x = y$.

(If $x$ likes $y$ and $y$ likes $x$, then $x$ and $y$ are the same
person.)

\item \term{transitive} if for all $x, y, z \in A$, $xRy$ and $yRz$
imply $xRz$.

(If $x$ likes $y$ and $y$ likes $z$, then $x$ also likes $z$.)

\end{enumerate}

Let's see which of these properties hold for some of the relations
we've considered so far:

\begin{tabular}{ccccc}
 & reflexive? & symmetric? & antisymmetric? & transitive? \\
$x \equiv y \pmod{5}$ & \text{yes} & \text{yes} & \text{no} & \text{yes} \\
$x \mid y$ & \text{yes} & \text{no} & \text{yes} & \text{yes} \\
$x \leq y$ & \text{yes} & \text{no} & \text{yes} & \text{yes}
\end{tabular}

The two different yes/not patterns in this table are both extremely
common.  A relation with the first pattern of properties (like
$\equiv$) is called an ``equivalence relation'', and a relation with
the second pattern (like $\mid$ and $\leq$) is called a
``partially-ordered set''.  The rest of this lecture focuses on just
these two types of relation.

\section{Equivalence Relations}

A relation is an \term{equivalence relation} if it is reflexive,
symmetric, and transitive.  Congruence modulo $n$ is a excellent
example of an equivalence relation:

\begin{itemize}

\item It is reflexive because $x \equiv x \pmod{n}$.

\item It is symmetric because $x \equiv y \pmod{n}$ implies $y \equiv
x \pmod{n}$.

\item It is transitive because $x \equiv y \pmod{n}$ and $y \equiv z
\pmod{n}$ imply that $x \equiv z \pmod{n}$.

\end{itemize}

\noindent There is an even more well-known example of an equivalence
relation: equality itself.  Thus, an equivalence relation is a
relation that shares some key properties with $=$.

\subsection{Partitions}

There is another way to think about equivalence relations, but we'll
need a couple definitions to understand this alternative perspective.

Suppose that $R$ is an equivalence relation on a set $A$.  Then the
\term{equivalence class} of an element $x \in A$ is the set of all
elements in $A$ related to $x$ by $R$.  The equivalence class of $x$
is denoted $[x]$.  Thus, in symbols:
%
\[
[x] = \set{y \mid xRy}
\]

For example, suppose that $A = \mathbb{Z}$ and $xRy$ means that $x
\equiv y \pmod{5}$.  Then:
%
\[
[7] = \set{ \ldots, -3, 2, 7, 12, 17, 22, \ldots }
\]
%
Notice that 7, 12, 17, etc. all have the same equivalence class; that
is, $[7] = [12] = [17] = \ldots$.

A \term{partition} of a set $A$ is a collection of disjoint, nonempty
subsets $A_1, A_2, \ldots, A_n$ whose union is all of $A$.  For
example, one possible partition of $A = \set{a, b, c, d, e}$ is:
%
\begin{align*}
A_1 & = \set{a, c} &
A_2 & = \set{b, e} &
A_3 & = \set{d}
\end{align*}
%
These subsets are usually called the \term{blocks} of the
partition.\footnote{I think they should be called the \term{parts} of
the partition.  Don't you think that makes a lot more sense?}

Here's the connection between all this stuff: there is an exact
correspondence between \textit{equivalence relations on $A$} and
\textit{partitions of $A$}.  We can state this as a theorem:

\begin{theorem}
The equivalence classes of an equivalence relation on a set $A$ form a
partition of $A$.
\end{theorem}

We won't prove this theorem (too dull even for us!), but let's look at
an example.  The congruent-mod-5 relation partitions the integers into
five equivalance classes:
%
\begin{gather*}
\set{\ldots, -5, 0, 5, 10, 15, 20, \ldots} \\
\set{\ldots, -4, 1, 6, 11, 16, 21, \ldots} \\
\set{\ldots, -3, 2, 7, 12, 17, 22, \ldots} \\
\set{\ldots, -2, 3, 8, 13, 18, 23, \ldots} \\
\set{\ldots, -1, 4, 9, 14, 19, 24, \ldots}
\end{gather*}
%
In these terms, $x \equiv y \pmod{5}$ is equivalent to the assertion
that $x$ and $y$ are both in the same block of this partition.  For
example, $6 \equiv 16 \pmod{5}$, because they're both in the second
block, but $2 \not\equiv 9 \pmod{5}$ because 2 is in the third block
while 9 is in the last block.

In social terms, if ``likes'' were an equivalence relation, then
everyone would be partitioned into cliques of friends who all like
each other and no one else.

\section{Partial Orders}

A relation is a \term{partial order} if it is reflexive,
\underline{anti}symmetric, and transitive.  In terms of properties, the
only difference between an equivalence relation and a partial order is
that the former is symmetric and the latter is antisymmetric.  But
this small change makes a big difference; equivalence relations and
partial orders are very different creatures.

An an example, the ``divides'' relation on the natural numbers is a
partial order:

\begin{itemize}

\item It is reflexive because $x \mid x$.

\item It is antisymmetric because $x \mid y$ and $y \mid x$ implies $x = y$.

\item It is transitive because $x \mid y$ and $y \mid z$ implies $x
\mid z$.

\end{itemize}

\noindent The $\leq$ relation on the natural numbers is also a partial
order.  However, the $<$ relation is not a partial order, because it
is not reflexive; no number is less than itelf.~\footnote{Some sources
omit the requirement that a partial order be reflexive and thus would
say that $<$ \textit{is} a partial order.  The convention in this
course, however, is that a relation \textit{must} be reflexive to be a
partial order.}  

Often a partial order relation is denoted with the symbol $\preceq$
instead of a letter, like $R$.  This makes sense from one perspective
since the symbol calls to mind $\leq$, which is one of the most common
partial orders.  On the other hand, this means that $\preceq$ actually
denotes the \textit{set} of all related pairs.  And a set is usually
named with a letter like $R$ instead of a cryptic squiggly symbol.
(So $\preceq$ is kind of like Prince.)

Anyway, if $\preceq$ is a partial order on the set $A$, then the pair
$(A, \preceq)$ is called a \term{partially-ordered set} or
\term{poset}.  Mathematically, a poset \textit{is} a directed graph
with vertex set $A$ and edge set $\preceq$.  So posets can be drawn
just like directed graphs.

An an example, here is a poset that describes how a guy might get
dressed for a formal occasion:

\mfigure{!}{2in}{getting-dressed}

\noindent In this poset, the \textit{set} is all the garments and the
\textit{partial order} specifies which items must precede others when
getting dressed.  Not every edge appears in this diagram; for example,
the shirt must be put on before the jacket, but there is no edge to
indicate this.  This edge would just clutter up the diagram without
adding any new information; we already know that the shirt must
precede the jacket, because the tie precedes the jacket and the shirt
precedes the tie.  We've also not not bothered to draw all the
self-loops, even though $x \preceq x$ for all $x$ by the definition of
a partial order.  Again, we know they're there, so the self-loops
would just add clutter.

In general, a \term{Hasse diagram} for a poset $(A, \preceq)$ is a
directed graph with vertex set $A$ and edge set $\preceq$ minus all
self-loops and edges implied by transitivity.  The diagram above is
\textit{almost} a Hasse diagram, except we've left in one extra edge.
Can you find it?

\subsection{Directed Acyclic Graphs}

Notice that there are no \term{directed cycles} in the getting-dressed
poset.  In other words, there is no sequence of $n \geq 2$ distinct
elements $a_1, a_2, \ldots, a_n$ such that:
%
\[
a_1 \preceq a_2 \preceq a_3 \preceq \ldots \preceq a_{n-1} \preceq a_n \preceq a_1 
\]
This is a good thing; if there were such a cycle, you could never get
dressed and would have to spend all day in bed reading books and
eating fudgesicles.  This lack of directed cycles is a property shared
by all posets.

\begin{theorem}
\label{th:nocycle}
A poset has no directed cycles other than self-loops.
\end{theorem}

\begin{proof}
We use proof by contradiction.  Let $(A, \preceq)$ be a poset.
Suppose that there exist $n \geq 2$ distinct elements $a_1, a_2,
\ldots, a_n$ such that:
%
\[
a_1 \preceq a_2 \preceq a_3 \preceq \ldots \preceq a_{n-1} \preceq a_n \preceq a_1 
\]
%
Since $a_1 \preceq a_2$ and $a_2 \preceq a_3$, transitivity implies
$a_1 \preceq a_3$.  Another application of transitivity shows that
$a_1 \preceq a_4$ and a routine induction argument establishes that
$a_1 \preceq a_n$.  Since we also know that $a_n \preceq a_1$,
antisymmetry implies $a_1 = a_n$ contradicting the supposition that
$a_1, \ldots, a_n$ are distinct and $n \geq 2$.  Thus, there is no
such directed cycle.
\end{proof}

Thus, deleting the self-loops from a poset leaves a directed graph
without cycles, which makes it a \term{directed acyclic graph} or
\term{DAG}.

\subsection{Partial Orders and Total Orders}

A partially-ordered set is ``partial'' because there can be two
elements with no relation between them.  For example, in the
getting-dressed poset, there is no relation between the left sock and
the right sock; you could put them on in either order.  In general,
elements $a$ and $b$ of a poset are \term{incomparable} if neither $a
\preceq b$ nor $b \preceq a$.  Otherwise, if $a \preceq b$ or $b
\preceq a$, then $a$ and $b$ are \term{comparable}.

A \term{total order} is a partial order in which every pair of
elements is comparable.  For example, the natural numbers are totally
ordered by the relation $\leq$; for every pair of natural numbers $a$
and $b$, either $a \leq b$ or $b \leq a$.  On the other hand, the
natural numbers are \textit{not} totally ordered by the ``divides''
relation.  For example, 3 and 5 are incomparable under this relation;
3 does not divide 5 and 5 does not divide 3.  The Hasse diagram of a
total order is distinctive:

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

A total order defines a complete ranking of elements, unlike other
posets.  Still, for every poset there exists some ranking of the
elements that is consistent with the partial order, though that
ranking might not be unique.  For example, you can put your clothes on
in several different orders that are consistent with the
getting-dressed poset.  Here are a couple:

\begin{center}
\begin{tabular}{ccc}
underwear    & \hspace{1in} & left sock \\
pants        && shirt \\
belt         && tie \\
shirt        && underwear \\
tie          && right sock \\
jacket       && pants \\
left sock    && right shoe \\
right sock   && belt \\
left shoe    && jacket \\
right shoe   && left shoe
\end{tabular}
\end{center}

A total order consistent with a partial order is called a
``topological sort''.  More precisely, a \term{topological sort} of a
poset $(A, \preceq)$ is a total order $(A, \preceq_T)$ such that:
%
\[
x \preceq y \qquad \text{implies} \qquad x \preceq_T y
\]
%
So the two lists above are topological sorts of the getting-dressed
poset.  We're going to prove that \textit{every} finite poset has a
topological sort.  You can think of this as a mathematical proof that
you \textit{can} get dressed in the morning (and then show up for
6.042 lecture).

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

We'll prove the theorem constructively.  The basic idea is to pull the
``smallest'' element $a$ out of the poset, find a topological sort of
the remainder recursively, and then add $a$ back into the topological
sort as an element smaller than all the others.

The first hurdle is that ``smallest'' is not such a simple concept in
a set that is only partially ordered.  In a poset $(A, \preceq)$, an
element $x \in A$ is \term{minimal} if there is no other element $y
\in A$ such that $y \preceq x$.  For example, there are \textit{four}
minimal elements in the getting-dressed poset: left sock, right sock,
underwear, and shirt.  (It may seem odd that the minimal elements are
at the top of the Hasse diagram rather than the bottom.  Some people
adopt the opposite convention.  If you're not sure whether minimal
elements are on the top or bottom in a particular context, ask.)
Similarly, an element $x \in A$ is \term{maximal} if there is no other
element $y \in A$ such that $x \preceq y$.

Proving that every poset \textit{has} a minimal element is extremely
difficult, because this is actually false.  For example the poset
$(\mathbb{Z}, \leq)$ has no minimal element.  However, there is at
least one minimal element in every \textit{finite} poset.

\begin{lemma}
\label{lem:poset-min}
Every finite poset has a minimal element.
\end{lemma}

\begin{proof}
Let $(A, \preceq)$ be an arbitrary poset.  Let $a_1, a_2, \ldots, a_n$
be a maximum-length sequence of distinct elements in $A$ such that:
%
\[
a_1 \preceq a_2 \preceq \ldots \preceq a_n
\]
%
The existence of such a maximum-length sequence follows from the
well-ordering principle and the fact that $A$ is finite.  Now $a_0
\preceq a_1$ can not hold for any element $a_0 \in A$ not in the
chain, since the chain already has maximum length.  And $a_i \preceq
a_1$ can not hold for any $i \geq 2$, since that would imply a cycle
%
\[
a_i \preceq a_1 \preceq a_2 \preceq \ldots \preceq a_i
\]
%
and no cycles exist in a poset by Theorem~\ref{th:nocycle}.
Therefore, $a_1$ is a minimal element.
\end{proof}

Now we're ready to prove Theorem~\ref{th:topsort}, which says that
every finite poset has a topological sort.  The proof is rather
intricate; understanding the argument requires a clear grasp of all
the mathematical machinery related to posets and relations!

\begin{proof} (of Theorem~\ref{th:topsort})
We use induction.  Let $P(n)$ be the proposition that every
$n$-element poset has a topological sort.

\textit{Base case.}  Every 1-element poset is already a total order
and thus is its own topological sort.  So $P(1)$ is true.

\textit{Inductive step.}  Now we assume $P(n)$ in order to prove
$P(n+1)$ where $n \geq 1$.  Let $(A, \preceq)$ be an $(n+1)$-element
poset.  By Lemma~\ref{lem:poset-min}, there exists a minimal element
$a \in A$.  Remove $a$ and all pairs in $\preceq$ involving $a$ to
obtain an $n$-element poset $(A', \preceq')$.  This has a topological
sort $(A', \preceq'_T)$ by the assumption $P(n)$.  Now we construct a
total order $(A, \preceq_T)$ by adding back $a$ as an element smaller
than all the others.  Formally, let:
%
\begin{align*}
\preceq_T  & \quad = \quad \preceq'_T \cup \set{(a, z) \mid z \in A}
\end{align*}
%
All that remains is the check that this total order is consistent with
the original partial order $(A, \preceq)$; that is, we must show that:
%
\[
x \preceq y \qquad \text{implies} \qquad x \preceq_T y
\]
%
We assume that the left side is true and show that the right side
follows.  There are two cases:

\underline{Case 1}: If $x = a$, then $a \preceq_T y$ holds, because $a
\preceq_T z$ for all $z \in A$.

\underline{Case 2}: If $x \neq a$, then $y$ can not equal $a$ either,
since $a$ is a minimal element in the partial order $\preceq$.  Thus,
both $x$ and $y$ are in $A'$ and so $x \preceq' y$.  This means $x
\preceq'_T y$, since $\preceq'_T$ is a topological sort of the partial
order $\preceq'$.  And this implies $x \preceq_T y$, since $\preceq_T$
contains $\preceq'_T$.

Thus, $(A, \preceq_T)$ is a topological sort of $(A, \preceq)$.  This
shows that $P(n)$ implies $P(n+1)$ for all $n \geq 1$.  Therefore,
$P(n)$ is true for all $n \geq 1$ by the principle of induction, which
prove the theorem.
\end{proof}

\end{document}
