\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{3, Mon}                    % !! start the paper

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

\begin{problem} 
Find the flaw in the following false proof, and give a counter-example
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}

\solution{

% {\em TA NOTES (comment out before solutions are published): 5
% minutes. The definitions are given in the appendix. You cannot derive
% one of the properties from the other two - the three properties are
% orthogonal. Hint: start by finding a counter-example.}

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.}
\end{problem}

%---------------------------------------------------------------
% Classification problem
% parts appear all over the place (Rad)

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

\begin{problemparts}

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

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


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

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

\problempart $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 transtive, and therefore an
equivalence relation. There is an equivalence class for each natural
number corresponding to bit strings with that number of 1s.}

\end{problemparts}
\end{problem}

%------------------------------------------------------------
% Directly From the notes

\begin{problem}
Let $R$ be an equivalence relation on the set $A$. For an element
$a\in A$, let $[a]$ denote the set $\{b\in A \mbox{ given } aRb\}$.
This set is the \emph{equivalence class of $a$ under $R$} and we call
$a$ a \emph{representative} of the set $[a]$.

Prove that the sets $[a]$ for all $a \in A$ constitute a partition of
$A$.  In other words, prove that for every $a,b\in A$, either
$[a]=[b]$ or $[a]\cap [b]=\emptyset$.

\solution{

% {\em TA NOTES (comment out before solutions are published): proof is
% in the notes. After students all feel comfortable that they know the
% proof, have one of them write it up on the board and others
% critique. One thing to point out is that all three properties of
% equivalence are needed in the proof - otherwise we would be proving
% something stronger. Ask them if they did need all three properties in
% their proof.}

\begin{proof}
  Consider some arbitrary $a,b\in A$. If either $[a]=[b]$ or $[a] \cap
  [b]=\emptyset$ then we are done, so suppose not.

  Let $c$ be any element that is in one of the sets but not the other.
  Without loss of generality we can assume that $c \in [b]-[a]$.  (We
  know that either $c \in [b]-[a]$ or $c \in [a]-[b]$. In the latter
  case we can simply swap $a$ and $b$ and reduce to the first case.)

  Let $d$ be any element in $d \in [a] \cap [b]$. We will get a
  contradiction by showing that $aRc$ and therefore that $c\in
  [a]$. First, $aRd$ because $d\in [a]$ (note that $d=a$ is a
  possibility but this is ok because $R$ is reflexive).  Second, $dRb$
  and $bRc$ because both $c,d\in [b]$ and $R$ is symmetric.  This
  implies, by transitivity, that $dRc$.  Finally, by transitivity,
  $aRc$ because $aRd$ and $dRc$.  Hence we have a contradiction. Also,
  we know that for every $a \in A$, $a$ is in its own equivalence
  class since $R$ is reflexive.  Therefore the union of all the
  equivalence classes gives us $A$, and thus the sets [$a$] for $a \in
  A$ constitute a parition of $A$.

  Note that all three properties of equivalence relations were used in
  this proof.  Checking that the proof uses all available assumptions
  is usually a good sanity check when writing proofs.  If one of the
  properties you assumed were not needed, you have either made a
  mistake or proven a much more strong theorem than you thought.  For
  example, if you didn't use transitivity anywhere in the proof of
  this problem, you would have falsely proven that any reflexive
  symmetric relation produces a partition.
\end{proof}
}

\end{problem}


\section*{Appendix}

A binary relation $R$ on a set $A$ is
\begin{itemize}

\item \emph{reflexive} if for every $a \in A$, $a \sim_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{itemize}
for all $x, y, z \in A$.

A binary relation $R$ on a set $A$ is
\begin{itemize}

\item an \emph{equivalence relation} iff it is reflexive, symmetric and
transitive.

%% \item a \emph{partial order} iff it is transitive and anti-symmetric.

%% \item a \emph{total order} iff it is a partial order and for all
%% $x \neq y \in A$ either $x R y$ or $yRx$.

\end{itemize}


\end{document}


