\documentclass[11pt,twoside]{article}    
\usepackage{latex-macros/course}% !! use the macros 

%\backwardscompatibility        % !! use for backwards compatibility
%\showsolutions                 % !! use to force solutions & skip query
%\hidesolutions                 % !! use to force no solutions & skip query
%\renewcommand{\coursecopyrightnames}{Prof.~Albert~R.~Meyer}

\begin{document} 
\inclassproblems{4, Mon.}                    % !! start the paper

\begin{problem}
In each case, say whether or not $R$ is a equivalence relation on
$A$. If it is an equivalence relation, what are the equivalence
classes and how many equivalence classes are there?

% \solution{
% {\em TA NOTES (comment out before publishing). Removed
% partial orders part, will cover that wed. Make sure they can prove why
% something is/is not an equivalence relation.}}

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

\solution{
$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 $R \eqdef \set{(x,y) \in W \times W \suchthat \text{ the
words $x$ and $y$ have at least one letter in common} }$.

\solution{ $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 = \{(x,y) \in W \times W$ and the word $x$ comes
before the word $y$ alphabetically\}.

\solution{$R$ is not reflexive but it is transitive and
antisymmetric. It is not an equivalence relation, but it is a partial
order.}

\ppart $R=\{(x,y) \in \reals \times \reals \mbox{ and } |x|\leq
|y|\}$.

\solution{$R$ is reflexive and transitive. It is not symmetric. It is
not antisymmetric either. As a counterexample, $|-3| \leq |3|, |3|
\leq |-3|$, but $3 \neq -3$.}

\ppart $R=\{(x,y) \in B \times B$, where B is the set of all bit
strings and x and y have the same number of 1s.\}

\solution{$R$ is reflexive, symmetric and transitive, and therefore an
equivalence relation. There is an equivalence class for each natural
number corresponding to bit strings with that number of 1s.}

\eparts
\end{problem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem} 

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

\bparts
\ppart Give a counter-example to the claim.

\solution{The simplest counterexample is to let $R$ be the empty relation
on some nonempty set $A$.  This $R$ is vacuously symmetric and
transitive, but obviously not reflexive.

A slightly less trivial example is
\[
R \eqdef \set{(a,a),(a,b),(b,a),(b,b)}
\]
on the set $A \eqdef \set{a,b,c}$.  It is not reflexive because $(c,c)$ is
not in $R$.}

\ppart Find the flaw in the following proof of the 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}

\solution{
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.

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

\instatements{\newpage}
\begin{problem}
Verify that each of the following relations is a partial order by
describing a function, $g$, such that the relation is defined by $g$
according to the Definition~\ref{po-def} in the Appendix.
%following added 9/21/05
For each, is it a total order?

\bparts

\ppart The relation, $<$, on $\reals$.

\solution{Define $g(r) \eqdef \set{t \in \reals \suchthat t<r}$.  It
follows that
\[
r_1 < r_2 \qiff g(r_1) \subset g(r_2)
\]
so $<$ satisfies the condition~(\ref{po-eqn}) on $R$ that defines partial
orders.  Likewise, the relation, $\le$, is a partial order because
\[
r_1 \le r_2 \qiff r_1 < r_2,
\]
for all reals $r_1 \neq r_2$.
}

\ppart The superset relation, $\supseteq$, on $\power(B)$ for a set, $B$.

\solution{Define $g(a) \eqdef \bar{a} \eqdef B - \{a\}$, and note that
for $a_1 \neq a_2 \in \power(B)$,
\begin{align*}
a_1 \supseteq a_2 &\qiff a_1 \supset a_2 & \text{(since $a_1 \neq a_2$)}\\
&\qiff \bar{a_1} \subset \bar{a_2} & \text{(basic set theory)}\\
& \qiff g(a_1) \subset g(a_2) & \text{(def of $g$)}.
\end{align*}
}

\ppart The ``divides'' relation on natural numbers.
\solution{
Let $g(a) \eqdef\text{ the set of natural number  that divide } a$.
}

\eparts

\end{problem}


%\begin{problem}
%Show that none of the following relations is an equivalence by identifying
%a relevant relational property it does not have.  Which ones are partial
%orders? total orders?
%
%\bparts
%
%\ppart The relation, $\le$, on $\naturals$.
%
%\solution{It's transitive (since [$j\le k$ and $k\le l$] implies $j\le
%l$), and reflexive (since $r\le r$), but not symmetric (since $0\le 1$ but
%not $1 \le 0$).}
%
%\ppart The ``implies'' relation on propositional formulas.
%
%\solution{
%This relation is reflexive since $p \implies p$.  It is also transitive,
%since if $p \implies q$ and $q \implies r$, then $p \implies r$.  However,
%it isn't symmetric, since, for example, $\texttt{false} \implies
%\texttt{true}$, but not $\texttt{true} \implies \texttt{false}$.
%}
%
%\ppart The relation $R$ defined over the domain $A=\reals$ as
 %$R=\{(x,y) \in \reals \times \reals \mbox{ and } |x| < |y|$ or $x=y\}$.
%
%\solution{
 %$R$ is reflexive, transitive, and antisymmetric.  It is not symmetric.  
 %Therefore, $R$ is not an equivalence relation, but it is
 %a partial order on $A$. , $R$ is not a total order on $A$. As a
 %counterexample, if x = 5, y = -5, then none of the following holds: $x
 %= y, |x| < |y|, |y| < |x|$.}
%
%\ppart The relation $R$ defined over the domain $A=\reals$ as
%$A=\reals, R=\{(x,y) \in \reals \times \reals \mbox{ and }
%|x|\leq |y|\}$.
%
%\solution{
 %$R$ is reflexive and transitive. However, it is not
 %symmetric or antisymmetric. As a counterexample, $|-3| \leq |3|, |3| \leq |-3|$,
 %but $3 \neq -3$.  Thus it is not an equivalence relation or a partial
 %order.
%}
%


%\ppart The relation, $R$, on sets of natural numbers such that $C\,
%R\, D$ iff $C \intersect D$ is finite.
%
%\solution{
%$R$ is symmetric, but not
%reflexive (for example $\naturals\, R\, \naturals$ is not true).
%$R$ is also not transitive:
%let $C$ be the even numbers, $D$ the odd numbers and $E$ the
%multiples of 4.  So $C\, R\, D$, and $D\, R\, E$ but not $C\, R\, E$.}
%
%\eparts
%
%\end{problem}
%


\begin{problem}
Suppose you are given the description of an equivalence relation and want to cut
down on the number of pairs that are stored without losing any information.
For example, here are the pairs of an equivalence
relation on a set of integers:
\[
G \eqdef  \set{11, 33, 44, 55, 66, 77, 13, 31, 45, 54, 47, 74, 57, 75}.
\]
where for readability, we've written "$mk$" to designate the pair $(m,k)$.
 
To start, we know that if we have $mk$, then we necessarily also 
have $km$, so there's no need to keep both.  This lets us cut 
down to: 

\[ 
\set{11,33,44,55,66,77,13,45,47,57}.  
\] 
Also, if we have 45 and 57, we don't need 47, since that will necessarily 
be there (by transitivity),  so we can further cut down to 
\[ 
\set{11,33,44,55,66,77,13,45,57} 
\] 
In addition, as long as we keep some pair in which $k$ appears, we don't 
need the pair $kk$.  This lets us cut down to the pairs 
\begin{equation}\label{min} 
\set{66,13,45,57}.  
\end{equation} 
These pairs are all that are needed to determine the entire original equivalence
relation, $G$.  Moreover, the set~\eqref{min} of these pairs is \emph{minimal} with 
this property; this means that if any pair was removed from the set, it 
wouldn't determine the relation any more.  
\bparts 
\ppart Describe another couple of minimal sets of pairs that determine the relation.  
\solution{ 
\[ 
\set{66,31,45,57}, \set{66,13,47,57},\text{ and lots more} \dots.  
\] 
} 
\ppart Here are the pairs that are left after some unnecessary pairs 
have been removed from the description of an equivalence relation, $E$.  
What is the domain of $E$?  What are the equivalence classes of $E$?  
\[ 
15,20,40,57,68,79,9a,bb,c3 
\] 
\solution{                                      
\begin{align*} 
\text{ domain of } E & =  \set{0123456789abc}\\ 
\text{ equivalence classes of } E & = \set{024} \set{1579a} \set{3c} 
\set{68} \set{b}.  
\end{align*} 
} 
\ppart On a domain of $n$ elements, what is the smallest number of 
pairs that could determine an equivalence relation?  
\solution{$\ceil{n/2}$ by having all blocks of size 2, except for one 
block of size 1 if $n$ is odd.} 

\ppart  Suppose you have an equivalence relation on a domain of size $n$ 
with $k$ equivalence classes, with no classes of just one element.  Then 
every minimal set of pairs has the same size.  What is that 
size?  Explain.  
\solution{It takes $n-k$ pairs.  We'll let you convince yourself that 
$c-1$ is the 
minimum number of pairs to ``connect up'' all the elements and thereby 
determine an equivalence class of size $c>1$.  (We'll prove this carefully 
in couple of weeks when we study tree structures.)  So if there are $k$ 
classes of sizes $c_1, \dots, c_k$, you need 
\[ 
(c_1-1)+ (c_2 - 1) + \cdots + (c_k -1) = (c_1 + c_2 + \cdots + c_k) - k 
= n-k 
\] 
pairs.} 
\eparts \end{problem}

\instatements{\newpage}
\section*{Appendix}

\subsection*{Equivalence}
\begin{definition}\label{deqv}
A binary relation, $R$, on a set, $A$, is an \emph{equivalence relation}
iff there is a function, $f$, with domain $A$, such that
\begin{equation}\label{Rf}
a_1\, R\, a_2 \qiff f(a_1) = f(a_2)
\end{equation}
for all $a_1,a_2 \in A$.
\end{definition}

\begin{theorem*}
A relation is an equivalence iff it is reflexive, symmetric and transitive.
\end{theorem*}

\subsection*{Partial Order}

\begin{definition}\label{po-def}
A relation, $R$, on a set, $A$, is a \emph{partial order} providing there
is a function, $g$, from $A$ to some collection of sets such that
\begin{equation}\label{po-eqn}
a_1\, R\, a_2 \qiff g(a_1) \subset g(a_2),
\end{equation}
for all $a_1 \neq a_2 \in A$.
\end{definition}

\begin{theorem*}
A relation is a partial order iff it is transitive and antisymmetric.
\end{theorem*}


\subsection*{Relational Properties}
A binary relation, $R$, on a set, $A$, is
\begin{itemize}

\item \emph{reflexive} if $a R a$ for every $a \in A$,

\item \emph{irreflexive} if $a R a$ holds for no $a \in A$,

\item \emph{symmetric} if for every $a,b\in A$, $aR b$ implies
    $bR a$,

\item \emph{antisymmetric} if for every $a \neq b\in A$, $aR b$ implies 
    $\neg(bR a)$,

\item \emph{asymmetric} if for every $a,b\in A$, $aR b$ implies 
    $\neg(bR a)$,

\item \emph{transitive} if for every $a,b,c\in A$, $aR b$ and
    $bR c$ implies $aR c$.

\end{itemize}

\end{document}
