\documentclass[11pt,twoside]{article}
\usepackage{graphics}
\usepackage{macros-course-lectures}

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

\begin{document}

\onlystudents

\lecture{notes5}{Relations}{February 22, 2000}

\forstudents{
\section{Sets}

\emph{This section was not covered in lecture, but summarized material
  from your background reading}

\subsection{Definitions}

A \emph{set} is a collection of objects (Collection, object are
undefined terms)\.

The order of elements is not important\. I.e., the sets 
$\{1,2\}$ and $\{2,1\}$ are considered the same set\.
Each element is included only once\. So, if we write
$\{a,b\}$ or $\{a,a,b\}$ they both denote the same set
and the element $a$ is considered to be present in the set 
only once. (repeating an element in the description of 
a set may be useful sometimes)\.

Here are some examples of sets: 
\begin{itemize}
\item $\{1,2,3\}$.  This is a simple finite set, obtained by
  enumerating all the elements.
\item $\emptyset$, the \emph{empty set}.  A special case of a finite
  set, with \emph{no} elements.
\item $\{\emptyset\}$.  This funny set is different from $\emptyset$\.
  It has one element, which is a set.
\item $\{1,\{1,2\}\}$.  This one contains two elements, one of which
  is a set itself\.  The set happens to contain the other element $1$,
  but that does not contradict the condition that an element is
  included only once.
\item $\{n\in \naturals \given n \hbox{ is even }\}$.  This is an
  infinite set, specified by giving a universal set (domain of
  discourse) and a property\.  In general, given a domain of discourse
  $D$ and a predicate $P$ over $D$, $\{x\in D \mid P(x)\}$ denotes the
  set of all $x$ in $D$ that satisfy predicate $P$.
\end{itemize} 
We write that $a\in A$ (``$a$ is in $A$'' or ``$a$ is an element of
$A$'') if $a$ is an object in the set $A$\.  The empty set satisfies
the proposition $(\forall x) x \notin \emptyset$\.

Sets can be defined by axioms and deduction rules, giving a very
formal \emph{axiomatic set theory}\.
But usually, people reason about sets less formally, using \emph{naive
set theory}\.
Either way, set theory can be used as the basis for defining almost
everything else in mathematics and is therefore
regarded as the most fundamental part of math\.

In fact natural numbers can be defined as certain kinds of sets (!)\.
For example we can represent the number $0$ by the empty set $\emptyset$,  
number $1$ by the set $\{\emptyset\}$, number $2$
by $\{\emptyset,\{\emptyset\}\}$, and so on.
In general, if $S_n$ is the set representing the number $n$,
the successor of $n$ can be represented by the set
$S_{n+1} = \{\emptyset\}\cup \{\{x\}\mid x\in S_n\}$.
Then the properties natural numbers can be \emph{proved as
theorems} of set theory, 
rather than being assumed\.

The axioms of set theory seem ridiculously obvious but aren't\.  Here
are some examples:
\begin{itemize}
\item The \emph{axiom of extensionality} says that two sets are equal
  if and only if they have the same elements\.  For example, the two
  sets $\{n\in \naturals \given \mbox{$2$ divides $n$}\}$ and $\{2n
  \mid n \in \naturals\}$ are defined in different ways\.  But they
  are ``equal'' as sets because they have exactly the same elements\.
\item The \emph{axiom of comprehension} says that we can form a new
  set by including all objects of a given set that share a common
  property\.  For example, $\{x \in \reals \given P(x)\}$ where
  $P(x)=\mbox{``x is rational''}$ denotes the set of all rational
  numbers. The axioms says that this is a set\.
\end{itemize}
The set building notation that we used above has given the universe of
discourse explicitly\.  Sometimes, when this seems obvious, we will
leave this out\.  Just like what we did for predicate quantifiers\.
E.g., we might write: $\{n \mid \mbox{$n$ is even}\}$ if the universe
$\naturals$ seems clear\.  (This \emph{could} be confusing---the
universe could alternatively be the integers, positive and negative.)
\begin{definition}
  We say that $A\subseteq B$ (``$A$ is a subset of $B$'' or 
  ``$A$ is contained in $B$'') if every
  element of $A$ is also an element of $B$ (that is, $(\forall x)(x\in
  A \implies x \in B)$).
\end{definition}
\begin{definition}
  We say that $A$ is a \emph{proper} subset of $B$
  ($A\subset B$) if $A\subseteq B$ and $A\neq B$.
\end{definition}
Note that $(\forall X) \emptyset \subseteq X$, i.e. the empty set 
is contained in any other set\.
\begin{example}
  Can we have both $A\in B$ and $A\subseteq B$? Yes, consider $\{ 1,
  \{ 1 \} \}$.
\end{example}
\begin{theorem}
  $A=B$ if and only if $A \subseteq B$ and $B \subseteq A$.
\end{theorem}
The proof is by the axiom of extensionality.  But we won't bother
giving it\.
This observation is very important as it provides a simple way to
prove that 2 sets are equal\.
\begin{example}
  Prove that the two sets $\{n\in \naturals \given \mbox{$2$ divides
    $n$}\}$ and $\{2n \mid n \in \naturals\}$ are equal.
  \begin{proof}
    We must show containment in both directions.
    
    $\subseteq$: We assume $x \in \naturals$ and $2 \mbox{ divides }
    n$, and show that there is some $y \in \naturals$ such that $x =
    2y$\.  This is true by definition of divisibility.
    
    $\supseteq$: Assume $x = 2y$.  Then $x$ is divisible by $2$, again
    by the definition of divisibility.
  \end{proof}
\end{example}
Here's a slightly more interesting one:
\begin{example}
  The set of evens $\geq 2$, i.e., $\{ 2n \mid n \in \naturals, n \geq
  1 \}$, is equal to $\{x \in \naturals \mid \exists y, z \mbox{ odd},
  x = y + z \}$.
  \begin{proof}
    Again, we have to show containment in both directions.
    
    $\subseteq$: If $x = 2n$, then write $x = 1 + (x - 1)$, sum of two
    odds.
    
    $\supseteq$: If $x = y + z$, where both $y$ and $z$ are odd, then
    write $y = 2a + 1$, $z = 2b + 1$\.  Then $x = 2(a+b+1)$, which is
    even.
  \end{proof}
\end{example}
The size of a set $A$ (the number of elements it contains) is written
$|A|$\.  
For example, the set $\{a,b,c\}$ has size 
$|\{a,b,c\}|=3$\. The empty set has size 
$|\emptyset|=0$\.
The size of a finite set is a natural number\.
Notice that for any two finite sets $A,B$, we have 
$|A\cup B| \leq |A|+|B|$\. Equality holds if and only if 
$A\cap B=\emptyset$\.



\subsection{Russell's paradox}

We might think that set theory is obvious, but this is not the case\.
Consider the set $S = \{x \given \mbox{$x$ is a set}\}$\.
This seems like a perfectly reasonable set (well, maybe a bit
strange---note $S \in S$)\.
If our set theory allows for such an entity, we get into trouble as
follows\.

Consider the set $Q = \{x \in S \given \mbox{$x$ is a set and $x
  \notin x$}\}$\.  If $S$ is a set, then so is~$Q$ by standard axioms
like comprehension\.  Note: $Q \subseteq S$.

Now note that some sets are in $Q$ and some aren't\.
For example,
the set $A = \{1,2,3\}$ is not an element of itself, so $A \in Q$\.
On the other hand,
The set 
$P = \{\mbox{all infinite sets}\}$ is a set (by comprehension from $S$)\.
Therefore, $P \in P$ as the set $P$ itself is infinite\.
So $P \notin Q$\.

The troublesome question is: is $Q\in Q$? 
\begin{enumerate}
\item If $Q \in Q$ then $Q \notin Q$, a contradiction.
\item If $Q \notin Q$ then $Q \in Q$ also a contradiction.
\end{enumerate} 

This is clearly a paradox\.  In fact, this paradox, at the time it was
discovered by Russell 1901, was a blow to the then current
attempts to formalize all of mathematics axiomatically\.
Mathematicians had to work very hard to find a consistent set of
axioms (note that a consistent set of axioms does not allow this
paradox to arise)\.

The problem with naive set theory is that you can form a set by
describing its members without referring to a starting set, as we did
for~$S$ above\.  Axiomatic set theory has a specific set of rules for
how you can form sets---rules that don't allow the set~$S$ above to be
specified, and therefore avoid the paradox\.

Fortunately, we'll be working naively, so this is a matter of only
theoretical interest.



\subsection{Basic set operations}

There are several standard operations on sets\.  In axiomatic set
theory, the claims that these operations yield new sets are axioms.
\begin{description}
\item[Union:] $A\cup B=\{x\given x\in A \lor x\in B\}$.
\item[Intersection:] $A\cap B=\{x\given x\in A \land x\in B\}$.
\item[Difference:] $A-B = \{x\given x\in A \land x \notin B\}$.
  This is also written as $A\setminus B$.
\item[Complement:] $A^c = \{x\given x\notin A\}$.
  This is also written as $\bar A$.
\item[Symmetric difference:] $A \oplus B = A \cup B - A\cap B$.
  This is also written as $A \mathop{\triangle} B$.
\end{description}
Sets and operations on sets can be represented using Venn diagrams
(see Rosen, sections 1.4, 1.5)\.
Union and intersection can be extended to apply to more than two sets\.  
Given a finite collection of sets $A_i$, $i=1,\ldots,n$,
\[
\bigcup_{i=1}^n A_i
\]
is the set of elements in at least one of the $A_i$, and  
\[
\bigcap_{i=1}^n A_i
\]
is the set of elements in all of the $A_i$\.
Both of these make sense if $i=1$---they reduce to just $A_1$\.
In fact, for $i = 0$, the appropriate thing is to  say the union of no
sets is $\emptyset$ and 
intersection of no sets is universal set\.
This definition of union and intersection of no sets might seem
arbitrary, but in fact it can be motivated in several ways\.
For example, if we want to define the union of a finite 
family of sets $A_1,A_2,\ldots, A_n$, we can define
$\bigcup_{i=1}^{1} A_1 = A_1$ and 
$\bigcup_{i=1}^{n+1}A_i = (\bigcup_{i=1}^{n} A_i)\cup A_{n+1}$.
If we want this recursive definition to work also for base case 
$n=0$ we must set $\bigcup \emptyset = \bigcup_{i=1}^0 A_i = \emptyset$\.
The analogue holds for intersection\. The recursive definition 
of  $\bigcap_{i=1}^{n+1}A_i = (\bigcap_{i=1}^{n} A_i)\cap A_{n+1}$
must have base case 
$\bigcap \emptyset = \bigcap_{i=1}^0 A_i = U$
if we want $\bigcap \{A_1\} = (\bigcap \emptyset)\cap A_{1} = A_1$\.

Instead of using an explicit index, we can just consider a set of sets\.
If $\mathcal{S}$ is a \emph{set of sets}, then 
\[
\bigcup \mathcal{S}
\] 
denotes the union of all the sets in $\mathcal{S}$, in any order\.
(One can prove that the order doesn't matter.) 
Likewise, 
\[
\bigcap \mathcal{S} 
\]
denotes the intersection of all the sets in $\mathcal{S}$\.

Complement is different from all the other operations, because it
assumes some universe $U$ from which we extract the things not in
$A$\.  All sets in question are supposed to be subsets of $U$\.  Given
a universal set $U$, the complement operation can be expressed as $A^c
= U - A$\.  The universe $U$ is often implicit, where there seems to
be little chance of confusion\.

There is a close correspondence between set operations and logical
operations: consider sets $A$, $B$ and $C$ defined by $A=\{x\mid
P(x)\}$, $B=\{x\mid Q(x)\}$, $C=\{x\mid R(x)\}$, where $P,Q,R$ are
predicates\.
\begin{description}
\item[set union vs. predicate or:]
 $A\cup B =  C$ if and only if 
 $P(x)\vee  Q(x) \equiv  R(x)$ 
\item[set intersection vs. predicate and:]
 $A\cap B =  C$ if and only if 
 $P(x) \wedge Q(x)\equiv R(x)$ 
\item[set difference vs. predicate ``non implication'':]
 $A - B = C$ if and only if 
 $\neg (P(x)\rightarrow Q(x)) \equiv R(x)$
\item[set complement vs. predicate not:]
 $A^c=B$ if and only if $\neg P(x) \equiv Q(x)$
\item[set symmetric difference vs. predicate exclusive or:]
 $A\oplus B = C$ if and only if $P(x)\oplus Q(x)\equiv R(x)$.
\end{description}
Predicates and sets often form alternative ways of looking at the same
notions\.
Given predicates $p$ and $q$, define 
\begin{align*}
P &= \{ x \mid p(x) \} \\
Q &= \{ x \mid q(x) \}
\end{align*}
Then $P \cup Q = \{ x \mid p(x) \vee q(x) \}$, and so on.



\subsection{Power set (set of all subsets)} 

Another very important operation on sets is that of the \emph{power
set} of a given set $A$\.
It is denoted by $\power(A)$ and consists of the set of all subsets
of $A$\.
In other words, $\power(A) = \{x\given x\subseteq A\}$\.
Note that for any set $A$,
$\emptyset\in\power(A)$ and $A\in \power(A)$.
\begin{example}
If $A=\{1,2\}$ then $\power(A)=\{\emptyset,\{1\},\{2\},\{1,2\}\}$.
\end{example}
\begin{theorem}
If $A$ has $n$ elements, then $P(A)$ has $2^n$ elements.
\end{theorem}
\begin{proof}
Ordinary Induction on $n$. 
Base case:  $n = 0$.  Then $P(A)$ has one element, $\emptyset$\.
Inductive step: We assume the theorem for $n$ and prove it for $n+1$\.
Pick one element, $a \in A$\.
The subsets can be divided into two groups---those containing $a$ and
those not containing $a$\.
Moreover, the set of subsets of $A$ not containing $a$ is 
$\power(A-\{a\})$, and the set of subsets of $A$ containing $a$
is the set $\{\{a\}\cup B \mid B\in \power(A-\{a\})$ which has 
the same number of elements as $\power(A-\{a\})$\.
By our induction hypothesis $\power(A-\{a\})$ has $2^{n-1}$
elements,
so the total is $2^{n-1} + 2^{n-1} = 2^n$.
\end{proof}
I did a base case of~$0$ here.  Does the inductive step from $0$
to~$1$ work correctly\?
Yes, it corresponds to the sets $\{\emptyset\}$ and $\{ a \}$\.

Because of this cardinality relationship, $\power(A)$ is sometimes
denoted by $2^A$.



\subsection{Set identities}

There are a large number of set identities involving relationships
among sets built using various operations\.
See p.~49 of Rosen\.
Here we just list some sample properties, and show how they can be
proved.
\begin{theorem}
[Distributivity:  Union distributes over intersection]
$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$
\end{theorem}
\begin{proof}
  We show the two sets are equal by proving that each is contained in the
  other.

  $A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C)$:

  Suppose $x \in A \cup (B \cap C)$\.   Then by definition, $x \in A$
  or $x \in (B \cap C)$. We argue by cases.  

  If $x \in A$, then by definition $x \in A \cup B$ and similarly $x
  \in A \cup C$\.  It follows by definition of intersection that $x$
  is in the intersection of these two sets, which is the RHS.

  On the other hand, if $x \in (B \cap C)$, then $x \in B$ and $x \in
  C$\.  Then by definition of union, $x \in A \cup B$ and $x \in A
  \cup C$\.  It again follows that $x$ is in the intersection.

  $A \cup (B \cap C) \supseteq (A \cup B) \cap (A \cup C)$:

  Suppose $x \in (A \cup B) \cap (A \cup C)$\.  It follows that $x \in
  A\cup B$ and $x \in A \cup C$\.  We argue by cases\.  If $x \in A$,
  then certainly $x \in A \cup (B \cap C)$\.  If $x \notin A$, then
  since $x \in A \cup B$, we know $x \in B$\.  Similarly, $x \in C$\.
  Therefore, $x \in B \cap C$\.  It follows that $x \in A \cup (B \cap
  C)$.
\end{proof}
\begin{theorem}
  De Morgan's rule: $(A\cup B)^c=A^c\cap B^c$.
\end{theorem} 
\begin{proof}
  We have to show that $(A\cup B)^c \subseteq A^c \cap B^c$ 
  and that $A^c \cap B^c \subseteq (A\cup B)^c$. 
  
  $(A\cup B)^c\subseteq A^c\cap B^c$: Let $x\in (A\cup B)^c$\.  Then
  by definition of complement, $x \notin A \cup B$\.  It follows
  (proof by contradiction) that $x \notin A$ and $x \notin B$\.
  Therefore, again by definition of complement, $x \in A^c$ and $x \in
  B^c$\.  Then by definition of intersection, $x \in A^c \cap B^c$.
  
  $A^c\cap B^c\subseteq (A\cup B)^c$: Let $x \in A^c \cap B^c$\.  Then
  $x$ is in $A^c$ and in $B^c$\.  Therefore, $x$ is in neither $A$ nor
  $B$ and therefore not in $A \cup B$\.  We conclude that $x \in (A
  \cup B)^c$.
\end{proof} 
The above two theorems have \emph{dual theorems} produced by swapping
$\cap$ and $\cup$\.  This is a general phenomenon---in Rosen, the
theorems are arranged in pairs\.  Duality can be applied to any
theorem that is true for \emph{all} sets\.  Each theorem in a pair can
be obtained from the other by swapping the operations $\cap$ and
$\cup$, and the sets $\emptyset$ and $U$\.  Notice that the complement
operations are not changed.
\begin{theorem}
  $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$.
\end{theorem}
\begin{theorem}
  $(A\cap B)^c=A^c\cup B^c.$
\end{theorem}



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


\clearpage
}

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


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


\end{document}
