


\section{Relations}

A ``relation'' is a fundamental mathematical notion expressing a
relationship between elements of sets\.
It's an abstract notion useful in practice for modeling many
different sorts of relationships\.
It's the basis of the \emph{relational data base} model, the standard
data model for practical data processing systems.

\subsection{Cartesian products}

Another important set operation is the \emph{Cartesian product}\.  For
sets $A$ and $B$ define $A\times B=\{(a,b)\given a\in A \land b\in
B\}$\.  Here, $(a,b)$ is considered an \emph{ordered} pair so that
$(a,b)\neq (b,a)$.
\begin{example}
  If $A=\{0,1\}$ and $B=\{x,y\}$ then $A\times
  B=\{(0,x),(0,y),(1,x),(1,y)\}$.
\end{example}
Order is important!
In the above example, $(a,0) \notin A \times B$, though $(a,0) \in B
\times A$\.
We can generalize Cartesian products to apply to more than 2 sets and define 
$A_1 \times \cdots \times A_n 
= \prod_{i=1}^n A_i 
= \{(a_1,\cdots,a_n) \given a_i\in A_i \hbox{ for   }1\le i \le n\}$\.
Also, we write $A^n$ for $\prod_{i=1}^n A$.

Examples: 
\begin{itemize}
\item $\{0,1\}^n$ is the set of all $n$-tuples of 0's and 1's. 
Or, length $n$ strings of $0$'s and $1$'s.
\item $\reals^2 = \reals\times \reals$ is the real plane.
\end{itemize} 

\subsection{Definitions}

\begin{definition}
  A \emph{binary relation from a set~$A$ to a set~$B$} is a subset
  $R\subseteq A\times B$.\\
  A \emph{binary relation on a set~$A$} is a subset $R\subseteq A^2$
  (I.e., a relation from $A$ to $A$).  
\end{definition}
We often write $a\sim_R b$ or $a \R b$ instead of  $(a,b)\in R$\.
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.
\begin{example}
  \label{ex:initial-relations}
  Relations are used to model many different things:
  \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,\cdots,n\})$ and let $a\sim_R b$ if
    $a\subseteq b$.
\end{enumerate} 
\end{example}

\subsection{Properties of Relations}

There are several standard properties that are satisfied by (some)
relations\.
These occur commonly enough that they are worth identifying\.
Sometimes interesting things can be deduced just from the abstract
properties.
\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}
There's no sense to the specific negative prefixes; they just need to
be remembered\. 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\ldots\ 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} 

\subsection{Representation}

There are different ways of representing relations, e.g., for handling
them in a computer program\.
One way is to describe them by properties, as we did above\.
That's about all we can do, for infinite sets\.
But for finite sets, we usually use some method that explicitly
enumerates all the elements of the relation\.
Some alternatives are: Lists, Matrices, Graphs. 


\subsubsection{Lists}

To represent a finite relation from set $A$ to set~$B$, just
list 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 $\{1,\ldots,12\}$
  is represented by the list:
  $\{(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{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}

These are used for binary relations on finite sets $A$, $B$\.
Rows are for elements of $A$, columns for $B$\.
We put a $1$ in a position 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,\ldots,12\}$ is 
  represented by the 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 symmetric around major diagonal\.

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


\subsubsection{Digraphs} 

To draw a picture of a relation $R \subseteq A \times B$, we can draw
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$ if $a \sim_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,\ldots,12\}$
    is represented by the digraph
    \begin{center}\includegraphics{figures/divide12.mps}\end{center}
  \end{samepage}
\end{example}

Recognizing properties:
\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}

