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

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

\begin{document}

%% TUTORIAL 3: Relations, Equivalence (Rad, Fall01)
\ifshowsolutions
  \tutsol{3}{September 20, 2001}{\stamp}
\else
  \tutprobn{3}{September 20, 2001}{\stamp}
\fi

\begin{problems}

%-----------------------------------------------------------------%
% source: Velleman 4.3.10 (in problemRepository)
% topic: relations, false proof

% Presentation Note: students may not remember the definition of
%  reflexiveness, so one way is to give them a counter example and ask
%  them why it is not reflexive

\problem Find the flaw in the following false proof, and give a
counterexample to the claim.

\begin{claim*}
Suppose $R$ is a relation on $A$.  If $R$ is symmetric and transitive, 
then $R$ is reflexive.
\end{claim*}

\begin{falseproof}
Let $x$ be an arbitrary element of $A$.  Let $y$ be any element of $A$
such that $xRy$.  Since $R$ is symmetric, it follows that $yRx$.  Then
since $xRy$ and $yRx$, we conclude by transitivity that $xRx$.  Since
$x$ was arbitrary, we have shown that $\forall x \in A\; (xRx)$, so
$R$ is reflexive.
\end{falseproof}

\solnospace{
The flaw is assuming that $y$ exists.  It is possible that there is an
$x \in A$ that is not related by $R$ to anything.  No such $R$ will be
reflexive.  The simplest such $R$ that is also symmetric and
transitive is the empty relation on any nonempty set $A$. We can
easily construct other examples, such as 

$R = \{	(a,a),(a,b),(b,a),(b,b) \}$ 

on the set $A \eqdef \set{a,b,c}$, which is not reflexive because $(c,c)$
is not in $R$. These relations are counterexamples to the claim. 

Note that the theorem can be fixed: $R$ restricted to its domain of
definition is reflexive, and hence an equivalence relation.}

%-----------------------------------------------------------------%
% source: Fall 99 tutorial? (in problemRepository)
% topic: equivalence classes
% similar problem as Rosen 6.5.10

\problem
Define $(a,b) \sim (c,d)$ iff $a+d = b+c$.


\problempart  
Prove that $\sim$ is an equivalence relation on
$\integers\cross\integers$.  

\solnospace{
\begin{itemize}
\item 
{\em Reflexivity}. 
$(a,b) \sim (a,b)$ since $a + b = b + a$.
\item 
{\em Symmetry}.
$(a,b) \sim (c,d) \implies (c,d) \sim (a,b)$ 
since $a + d = b + c \implies c + b = d + a$.
\item 
{\em Transitivity}. 
Assume $(a,b) \sim (c,d)$, i.e., $ a + d = b + c$.
And, $(c,d) \sim (e,f)$, i.e., $c + f = d + e$. Adding we get 
$a + d + c + f = b + c + d + e$ or $a + f = b + e$, i.e., 
$(a,b) \sim (e,f)$.  Hence 
$(a,b)\sim(c,d)\wedge(c,d)\sim(e,f)\implies(a,b)\sim(e,f)$. 
\end{itemize}

Since $\sim$ is reflexive, symmetric, and transitive, it is an 
equivalence relation.
}


\problempart  
Partition the set $\set{0,1,2} \cross \set{0,1,2}$ into the
distinct equivalence classes under $\sim$.

\solnospace{
The trick is to rewrite $(a,b) \sim (c,d)$ iff $a+d = b+c$ as
$(a,b) \sim (c,d)$ iff $a-b = c -d$.  This shows that with any
equivalence class ${\cal C}$ we can associate a 
{\em difference~$d\in\ints$} such that 
$(a,b) \in {\cal C} \iff a - b = d$.  This gives us an easy way 
to list the equivalence classes of $\set{0,1,2} \cross \set{0,1,2}$.
\begin{itemize}
\item $d = -2$: $\{(0,2)\}$.
\item $d = -1$: $\{(0,1),(1,2)\}$.
\item $d = 0$:  $\{(0,0),(1,1),(2,2)\}$.
\item $d = 1$:  $\{(1,0),(2,1)\}$.
\item $d = 2$:  $\{(2,0)\}$.
\end{itemize}
}


\problempart 
How many distinct equivalence classes under $\sim$ are there on the
set $\set{0,1,\dots, n} \cross \set{0,1,\dots, n}$? You do not need to
prove your answer. 

\solnospace{
$2n+1$, since the difference can be any value in $\{-n,\ldots, n\}$.
}





%-----------------------------------------------------------------%
% Source: Karger tutorial 3 Spring 01
% topic: relation composition using matrices
% editted the problem and solution to try and make it easier to
% understand (Rad)

% Lars Comment on original version (Spring '01):
% Maybe this problem was a bit too hard? I think that the problem of
% proving formally that the matrix representation of S o R is the
% product of M_R and M_S with \land instead of \times and \lor
% instead of + may be better. This makes the students understand
% what the composition is and it also introduces notation like
% \bigvee, which can be defined recursively, and we could make
% them prove something like "\bigvee_{x \in X} x = 1 \iff
% (\exists x \in X) [x = 1]" by induction.                     /Lars
%

\newcommand{\paritycomp}{\diamond} 

\problem 
Suppose that $A$, $B$ and~$C$ are finite sets and that $R$~is
a relation from $A$ to $B$ and $S$~is a relation from $B$ to $C$. 

The \emph{parity composition} of the relations $R$ and~$S$, denoted 
$S\paritycomp R$, is defined as follows:
\begin{align*}
  (a,c) \in S \paritycomp R & \iff \card{\set{b \in B \suchthat (a,b) \in
      R \land (b,c) \in S}} \text{is an odd number}.
\end{align*}
Let $M_R = [r_{ab}]$ be the matrix representing $R$.  \emph{Reminder}: this means
\begin{align*}
    r_{ab} & = \begin{cases}
      1 & \mbox{if $(a,b) \in R$,} \\
      0 & \mbox{otherwise,}
    \end{cases}
\end{align*}
for $a \in A, b \in B$.
Similarly, let $M_S = [s_{bc}]$ be the matrix representing $S$ and $M_{S
\paritycomp R} = [t_{ac}]$ be the matrix representing $M_{S \paritycomp
R}$.

Find a formula for $t_{ac}$ in terms of the $r$'s and $s$'s, and explain
why your formula is correct.

\solnospace{
\[
t_{ac} = \bigoplus_{b \in B} r_{ab} \cdot s_{bc},
\]
where $\bigoplus$ denotes mod 2 sum.

\begin{proof}
By the definition of parity composition,
\begin{displaymath}
      t_{ac} = \begin{cases}
        1 & \mbox{if there are an odd number of~$b \in B$ such that
          $(a,b) \in R$ and $(b,c) \in S$,} \\
        0 & \mbox{otherwise.}
      \end{cases}
\end{displaymath}
Using the matrix representation of $R$ and~$S$, respectively, we
can rewrite this as
\begin{displaymath}
      t_{ac} = \begin{cases}
        1 & \mbox{if there are an odd number of~$b \in B$ such that
          $r_{ab} \cdot s_{bc} = 1$,} \\
        0 & \mbox{otherwise.}
      \end{cases}
\end{displaymath}
Now, this is exactly the same thing as saying that
\begin{displaymath}
      t_{ac} = \bigoplus_{b \in B} r_{ab} \cdot s_{bc},    
\end{displaymath}
by the definition of~$\bigoplus$.
\end{proof}
}

%% Describes how to do count, eaiser than parity so should be before

% \problempart
% Consider the matrix $U_{R,S}=(u_{ac})$, whose $(a,c)$th entry is 
% \[
% u_{ac} \eqdef \card{\set{b\in B \suchthat (a,b)\in R \land (b,c)\in S$.
% \]
% Extending the ideas you have used for
% the first part of this problem, can you find a formula for~$u_{ac}$? 

% \solnospace{
% To calculate $u_{ac}$, we need to count the number of $b$'s in $B$ for
% which $(a,b)\in R$ and $(b,c)\in S$. Thinking as in the first part of
% the problem, we see that this is exactly the number of $b$'s in $B$
% for which $r_{ab}\wedge s_{bc}=1$. So, if we just sum up all
% $(r_{ab}\wedge s_{bc})$'s, we will get exactly this number (because,
% whenever a $(r_{ab}\wedge s_{bc})$ is not~1, it is~0). Hence, we can
% derive the formula of $u_{ac}$ from that of $t_{ac}$, by simply
% replacing the XOR operator with the summation operator:
% $$
% u_{ac} = \sum_{b\in B}  r_{ab}\wedge s_{bc} .
% $$
% Notice that this formula is identical to the one that we would get for
% $u_{ac}$ if $U_{R,S}$ were the ordinary matrix product of $M_R$ and
% $M_S$. Therefore, a more compact way to define $U_{R,S}$ is actually, 
% $$
% U_{R,S} = M_R \times M_S.
% $$
% }

\end{problems}

\end{document}
