\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}{Dr.~Radhika~Nagpal}

\begin{document} 
\inclassproblems{3W}                    % !! 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 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}

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

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

\begin{problem}
Define $(a,b) R (c,d)$ iff $a+d = b+c$.

\begin{problemparts}
\problempart  
Prove that $R$ is an equivalence relation on
$\integers\cross\integers$.  

\solution{

\begin{itemize}
\item 
{\em Reflexivity}. 
$(a,b) R (a,b)$ since $a + b = b + a$.
\item 
{\em Symmetry}.
$(a,b) R (c,d) \implies (c,d) R (a,b)$ 
since $a + d = b + c \implies c + b = d + a$.
\item 
{\em Transitivity}. 
Assume $(a,b) R (c,d)$, i.e., $ a + d = b + c$.
And, $(c,d) R (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) R (e,f)$.  Hence 
$(a,b)R(c,d)\wedge(c,d)R(e,f)\implies(a,b)R(e,f)$. 
\end{itemize}

Since $R$ 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 $R$.

\solution{
The trick is to rewrite $(a,b) R (c,d)$ iff $a+d = b+c$ as
$(a,b) R (c,d)$ iff $a-b = c -d$.  This shows that with any
equivalence class ${\cal C}$ we can associate a 
{\em difference~$d\in\integers$} 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 $R$ are there on the
set $\set{0,1,\dots, n} \cross \set{0,1,\dots, n}$? Explain why.

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

\end{problemparts}
\end{problem}

\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 } aR
b\}$.  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 $a \in A$ constitute a partition of $A$.
That is, for every $a,b\in A$, either $[a]=[b]$ or $[a]\cap
[b]=\emptyset$.

\solution{

From the notes:

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

\end{document}
