
\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}
In the matrix representation, we get the matrix for~$R^{-1}$ by
transposing the matrix for~$R$\.
In the graph representation, we get the graph for~$R^{-1}$ by
reversing every edge in the graph for~$R$.



\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}
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\. 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}
Composition of relations is equivalent to matrix multiplication, with
$+$ replaced by $\vee$ (Boolean or) and $*$ replaced by $\wedge$.
\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}
This is the same as matrix multiply, using the Boolean operations
``and'' and ``or''\. 
Relational composition is associative---just like matrix multiplication.
\begin{theorem*}[4.2.5 in Velleman]
  $R_1 \circ (R_2 \circ R_3) = (R_1 \circ R_2) \circ R_3$.
\end{theorem*}
Relations on some set~$A$ can be composed with themselves\.
The composition $R \circ R$ of $R$ with itself is written $R^2$\.
Similarly $R^n$ denotes $R$ composed with itself $n$ times\.
Its recursive definition:
$R_1 = R$, $R^n = R \circ R^{n-1}$\.
Actually, can define $R_0 = \{ (a,a) \mid a \in R \}$ as base case\.
We'll just use~$1$ as the base case, as the book does.
\begin{definition}
  A \emph{path} in a relation $R$ is a sequence $a_0,\ldots,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 graph 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).
\begin{definition}
  A \emph{simple path} is a path with no repeated vertices.
\end{definition}
\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{example}
  \begin{samepage}
    Before we start the proof 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{proof}[Proof of Lemma~\ref{lem:Rn-paths}]
  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---since there is an edge from $a$ to~$b$ for
  every $(a,b) \in R$ and one pair $(a,b) \in R$ for every edge
  from~$a$ to~$b$, $P(1)$~is true\.
  
  For the inductive step, suppose $P(n)$~is true\.  First consider a
  path $a_0,\ldots,a_{n+1}$ in~$R$\. This is a path $a_0,\ldots,a_n$
  in $R$ followed by a tuple $(a_n,a_{n+1})$ of $R$\. By the inductive
  hypothesis, $(a_0,a_n) \in R^n$, thus $(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 relation $(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, $(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}
There might be no one relation satisfying the definition; in that case
the closure is not defined.

As a general principle, there are two ways 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 result has property~$P$; or we can
start with the largest possible relation (which is $A \times A$ for a
relation on~$A$) and remove as many not-in-$R$ pairs as possible while
preserving the property~$P$.



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



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



\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 \given \mbox{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,\ldots,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,\ldots,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,\ldots,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}
If you don't like well-ordering, it is also possible to construct a
proof using normal induction (Velleman, \S~6.5).

Another way to construct the transitive closure is to take the
intersection of all relations that are transitive and contain~$R$
(Velleman, \S~4.5).



\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,\ldots,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$.

