\documentclass[12pt]{article}
\input{macros-course}

\newcommand{\relsub}[2]{\,#1_{#2}\,}

%% Latex asks whether or not to include solutions
\askaboutsolutions

\begin{document}

%% PSET 3: Relations, Equivalence (Rad, Fall01)
\ifshowsolutions
  \psetsol{3}{September 24, 2001}{\stamp}
\else
  \pset{3}{September 19, 2001}{Monday 9/24, beginning of lecture}{}
\fi

\ifshowsolutions
{} %
\else
\emph{Remember to include a \textbf{collaboration statement} and your
\textbf{TA's name} on the first page of your solutions.}
\fi

\textbf{Reading:} Rosen \S 6.1, 6.3-5 (ignore Warshall's algorithm in
 \S 6.4). \emph{Supplementary reading:} Velleman \S 4.2-4.3.

\begin{problems}

%-----------------------------------------------------------------%
% source: Velleman 4.6, Exercise 3.
% topic: equivalence relations
% last used Fall00 Problem Set 3 (in ProblemRepository)

\problem 

Which of the following relations are equivalence relations?  For those
that are equivalence relations, what are the equivalence classes? For
those that are not, give an example of how they fail.

\bparts
\ppart
$R \eqdef \set{(x,y) \in W \times W \suchthat \text{ the words $x$ and
$y$ start with the same letter} }$ where $W$ is the set of all words
in the 2001 edition of the Oxford English dictionary.

\solnospace{
$R$ is an equivalence relation since it is reflexive, symmetric, and
transitive.  The equivalence class of $x$ with respect to $R$ is the
set $[x]_R = $ the set of words $y$, such that $y$ has the same first
letter as $x$. There are 26 equivalence classes, one for each letter
of the English alphabet.
}

\ppart
$S \eqdef \set{(x,y) \in W \times W \suchthat \text{ the words $x$ and $y$
have at least one letter in common} }$.

\solnospace{
$S$ is reflexive and symmetric, but it is not transitive.  Therefore, $S$
is not an equivalence relation.  For example, let $w_1$ be the word
``scream,'' let $w_2$ be the word ``and,'' and let $w_3$ be the word
``shout.''  Then $w_3 S w_1$, and $w_1 S w_2$, but it is \textbf{not} the
case that $w_3 S w_2$.}

\ppart
$R \eqdef \set{(x,y) \in \reals \times \reals \suchthat x-y \in \rationals }$.

\solnospace{
$R$ is reflexive since, for any $x\in R$, $x-x=0$.  $R$ is symmetric
because if $(x-y)$ is rational, then $(y-x)=-(x-y)$ is rational as well.
Finally, $R$ is also transitive.  To see this, consider $(x,y)\in R$ and
$(y,z)\in R$.  We would like to know if $(x,z)$ is also in $R$.  We start
by noting that $(x-y)\in \rationals$ and $(y-z)\in \rationals$ by
definition of our relation $R$.  Now, we can express $(x-z) =
(x-y)+(y-z)$.  Since the sum of any two rational numbers is another
rational number, and we have written $(x-z)$ as such, we have shown that
$(x,z)\in \rationals$.  Therefore, $R$ is transitive.  Since $R$ is also
reflexive and symmetric, $R$ is an equivalence relations on $\reals$.

The equivalence class for x is
\[
[x]_R = \set{x + r \suchthat r \in \rationals}.
\]
}

\ppart
$R \eqdef \set{(x,y) \in \reals \times \reals \suchthat \exists n \in
\integers\; y=10^{n} x}$.

\solnospace{
$R$ is reflexive, since we can set $n=0$.  $R$ is symmetric because if
$y=10^k x$, for some $k\in \integers$, then $x=10^{-k}y$, so if
$(x,y)\in R$, then $(y,x)\in R$.  We can show that $R$ is transitive
as follows: consider pairs $(x,y)\in R$ and $(y,z)\in R$.  So $y=10^nx$
and $z=10^m y$, for $m,n\in \integers$.  Then, substituting, we have
that $z=10^{m}(10^{n} x) = 10^{m+n}x$.  Since $m+n \in \ints$, we conclude
that $(x,z) \in R$.

The equivalence class for x is 
\[
[x]_R = \set{10^{n}x \suchthat n\in \integers}.
\]
There is a distinct equivalence class for every real number in the
intervals $(-10,-1] \union \{0\} \union [1, 10)$.
}

\eparts

% %-----------------------------------------------------------------%
% % source: Velleman \S 4.6, Exercise 5.
% \problem {\em Potential alternative to Problem 2??} Let $T$ be the set
% of all triangles, and $S=\{(s,t)\in T\times T$ $|$ the triangles $s$
% and $t$ are similar$\}$ where two triangles are said to be
% \textit{similar} if they have three pairs of equal-degree vertices. Is
% $S$ is an equivalence relation? Explain.

% \medskip
% \medskip

% \solnospace{
% \textbf{Solution:}\\
% \textbf{Proof:} Yes. We can show that $S$ is reflexive,
% symmetric, and transitive.

% $S$ is reflexive because every triangle is similar to itself.  That
% is, every triangle $s$ has three angles of equivalent size to its own
% three angles.

% $S$ is symmetric because if $s$ is similar to $t$, then $s$ and $t$
% have vertices of the same size, so $t$ is similar to $s$ as well.

% Finally, $S$ is transitive because if triangle $s$ is similar to
% triangle $t$, and triangle $t$ is similar to triangle $r$ then
% triangles $s$ and $t$ have three pairs of equal-degree vertices, and
% triangles $t$ and $r$ also have three pairs of equal-degree vertices.
% $s$ and $r$ must share these three pairs of equal-degree vertices
% since triangles only have three vertices. $QED$. 
% } % end solution


%-----------------------------------------------------------------%
% source: Velleman \S 4.5 exercise 13
% Used first time, revised by ARM 9/11/01

\problem

The Bassethound Bus Company is trying to decide on \emph{one-way} bus
routes to run among the cities
\begin{quotation}\noindent
San Francisco, Chicago, Dallas, New York, and Washington D.C.
\end{quotation}
Bassethound wants to make sure that there is always some way to follow its
routes and get from any of the cities to any other.  We will represent
Bassethound's routes by a binary relation, $B$, on the set, $C$, of cities
above.

\bparts
\ppart Succinctly express the property that Bassethound wants $B$ to have
using relational and set operators on $B$ and $C$.

\solnospace{From every city $c \in C$ there should be a possible
series of bus routes to get to any other city $c' \in C$. This implies that
$\forall (c, c') \in C \cross C, (c,c') \in B^*$ (transitive closure
of B). In other words, $C \cross C \subseteq B^*$.

Note that, since we know that $B^* \subseteq C \cross C$, it
equivalent to require that $C \cross C = B^*$.}

\eparts

However, Bassethound wants to run as few bus routes as possible.  That is,
Bassethound wants the size, $\card{B}$, of $B$ to be as small as possible.

\bparts
\problempart What is the smallest possible value of $\card{B}$?
Explain.

\solnospace{5. We can connect the cities in a ring with one way edges
between them. So for example, $B$ could be the set $\set{(SF,C) ,
(C,D) , (D,NY), (NY,W) , (W, SF)}$.

5 is the minimum number of edges possible because for each city to be
accessible there must be at least one edge entering the city. Hence
$B$ can not have fewer than 5 edges.
}

\problempart
Is the smallest satisfactory $B$ unique?

\solnospace{No, since we could connect the cities in different orders.}

\ppart Unfortunately, Bassethound has a legacy problem.  They already have
a set of routes, $A$, that connect all the cities.  While they can cancel
routes easily, new routes are expensive, and they are reluctant to add
them.  Starting from $A$, can Bassethound arrive at a smallest size $B$
solely by cancelling routes?  Give a counterexample showing that it can't,
or explain how it can.

\solnospace{If $A$ has round trip direct from NY to each other city
(not unusual for these companies to have hubs), no route can be
cancelled and still maintain connectivity. But $A$ has 8 routes, not
the minimum number of 5. In general if a ring does not already exist
in the original $A$ digraph, there is no way to arrive at one.}

\eparts

%-----------------------------------------------------------------%
% Problem Repository, only used two parts (Rad)
% source: spring00 ps3, Velleman 4.3.9 
% topic: relations, compositions, reflexive, symmetric, transitive

\problem
Suppose $R$ and $S$ are binary relations on a set $A$.  For each part,
give either proofs or counterexamples to justify your answers.

\bparts

\problempart Suppose $R$ and $S$ are symmetric.  Must $R \intersect S$
be symmetric?  What about $R \union S$?  What about $R^{-1}$?  What
about $R \composition S$?

\solnospace{
$R \intersect S$: \textbf{Yes.} If $(x, y) \in R \intersect S$, we must
prove that $(y, x) \in R \intersect S$.  We have that $xRy$ (in which case
$yRx$ as well) and $xSy$ (in which case $ySx$ as well).  Since $yRx \land
ySx$, we have $(y, x) \in R \intersect S$.

$R \union S$: \textbf{Yes.} Suppose $(x, y) \in R \union S$.  Therefore,
either $xRy$ (in which case $yRx$ and $\therefore (y, x) \in R \union S$)
or $xSy$ (in which case $ySx$ and $\therefore (y, x) \in R \union S$).  So
by cases $(y, x) \in R \union S$.

$R^{-1}$: \textbf{Yes.} Suppose $(x, y) \in R^{-1}$.  By the definition of
inverse, this means that $yRx$.  But since $R$ is symmetric, this means
that $xRy$.  By the definition of inverse again, this means that $(y, x)
\in R^{-1}$.  So $R^{-1}$ is symmetric.

$R \composition S$: \textbf{No.}  Suppose $A = \{a,b,c\}$, $R = \{(b, c),
(c, b)\}$ , and $S = \{(a, b), (b, a)\}$ .  Then $R \composition S = \{(a,
c)\}$, which is not symmetric.

} %end solution

\problempart Suppose $R$ and $S$ are transitive.  Must $R \intersect
S$ be transitive?  What about $R \union S$?  What about $R^{-1}$?
What about $R \composition S$?

\solnospace{
$R \intersect S$: \textbf{Yes.} Suppose there is 
a walk from $x$ to $y$ in $R \intersect S$.  We need to prove $(x,y) \in
R \intersect S$.  In order for there to
be a walk from $x$ to $y$ in $R \intersect S$, there must have been a walk 
from $x$ to $y$ 
in both of $R$ and $S$ (otherwise, those walks would not appear in their 
intersection as walks).  Thus, $xRy$ and $xSy$, so $(x, y) \in R 
\intersect S$ as needed.

$R \union S$: \textbf{No.} Suppose $R = \{(a, b), (b, c), (a, c)\}$ and 
$S = \{(b, c), (c, a), (b, a)\}$.  Then $U = R \union S = \{(a, b), (b, a), 
(b, c), (c, a), (a, c)\}$, so that $cUa$ and $aUb$ but $\neg (cUb)$.

$R^{-1}$: \textbf{Yes.} Suppose $(a, b) \in R^{-1} \land 
(b, c) \in R^{-1}$.  We must prove that $(a, c) \in R^{-1}$.  
We know from the definition of inverse that
$bRa \land cRb$.  Furthermore, since $R$ is transitive, we have that $cRa$.  
By the definition of inverse again we have that $(a, c) \in 
R^{-1}$, as needed.

$R \composition S$: \textbf{No.} Suppose $R = \{(b, a), (b, c), (c, a)\}$ and 
$S = \{(a, b), (a, c), (b, c)\}$.  Then $(b, a) \in R \composition S$ and 
$(a, c) \in R \composition S$ but $(b, c) \notin R \composition S$.  
Transitivity fails for the composition. 

} % end{solution}
\eparts

%-----------------------------------------------------------------%
% From Problem Repository (Rad)
% topic: relations, transitive closures, symmetric relations
% source: Velleman 4.5.10

\problem Suppose $R$ is a relation on $A$, and let $S$ be the
transitive closure of $R$.  Prove that if $R$ is symmetric, then so is
$S$.  (Hint: Assume that $R$ is symmetric.  Prove that $R \subseteq
S^{-1}$ and $S^{-1}$ is transitive.  What can you conclude about $S$
and $S^{-1}$?)

\solnospace{
\begin{proof}
Assume that $R$ is symmetric.  We can prove that
$R \subseteq S^{-1}$.  Suppose arbitrary $(a, b) \in R$.  Because R is
symmetric, $(b, a) \in R$ as well.  $R \subseteq S$ by definition of
closure, therefore both $(a, b)$ and $(b, a)$ must be in $S$. However
by definition of inverse, $(b, a)$ and $(a, b)$ are also in $S^{-1}$.
Thus, $R \subseteq S^{-1}$.

We must now prove that $S^{-1}$ is transitive.  Suppose we choose an 
arbitrary three elements $a \in A$, $b \in A$, and $c \in A$ such that
$((a, b) \in S^{-1} \; \land (b, c) \in S^{-1})$.  This means that 
$(b, a) \in S \; \land (c, b) \in S$ by definition of inverse.  But 
since $S$ is transitive this means $(c, a) \in S$.  Thus, by definition
of inverse $(a, c) \in S^{-1}$.  This is the necessary condition to 
satisfy transitivity.  Thus, $S^{-1}$ is transitive.

Since $S$ was the transitive closure of $R$, it is the smallest set
such that $R \subseteq S$ and $S$ is transitive (definition of
transitive closure). Since $R \subseteq S^{-1}$ and $S^{-1}$ is a
transitive, $S^{-1}$ contains the transitive closure $S$ of $R$. So $S
\subseteq S^{-1}$. We also know that $|S| = |S^{-1}|$ by definition of
inverse, so in fact $S = S^{-1}$.  Therefore, since $S$ is the same
set as its inverse, $S$ is symmetric.
\end{proof}
} % end solution

\problem For any function $f:A \to B$, define a binary relation,
$\relsub{R}{f}$, on $A$ by the condition:
\[
a_1 \relsub{R}{f} a_2 \iff f(a_1) = f(a_2).
\]

\bparts

\ppart Show that $\relsub{R}{f}$ is an equivalence relation.

\solnospace{We first prove $\relsub{R}{f}$ is transitive.
\begin{proof}
Suppose $a_1 \relsub{R}{f}
a_2$ and $a_2 \relsub{R}{f} a_3$.  So $f(a_1) = f(a_2)$ and $f(a_2) =
f(a_3)$.  So $f(a_1) = f(a_3)$ (becuase equality is transitive, a basic
fact we can assume w/o proof).  That is, $a_1 \relsub{R}{f} a_3$.
\end{proof}
The proofs that $\relsub{R}{f}$ is reflexive and symmetric are equally
easy, and we omit them.}

\ppart (*) Show that for \emph{every} equivalence relation, $E$, on $A$,
there is a $B$ and an $f:A\to B$ such that $E = \relsub{R}{f}$.

\solnospace{Let $B$ be the blocks of the partition of $A$ defined by $E$, that
is,
\[
B \eqdef \set{[a]_{E} \suchthat a \in A}.
\]
Define $f:A\to B$ by the rule
\[
f(a) \eqdef [a]_{E}.
\]
So
\begin{eqnarray*}
a_1 \relsub{R}{f} a_2 & \iff & f(a_1) = f(a_2)\\
& \iff & [a_1]_{E} = [a_2]_{E}\\
& \iff & a_1 \,E\, a_2,
\end{eqnarray*}
which means that $\relsub{R}{f} = E$ as required.}
\eparts


\end{problems}

\end{document}                            
