\magnification=\magstep1
\centerline{Mathematics 243 -- Algebraic Structures}
\centerline{Discussion 2 -- Equivalence Relations}
\centerline{September 27, 2006}
\bigskip
\noindent
{\it Background}
\bigskip
Recall that last time we defined a {\it relation} on a set $A$
to be a subset $R \subset A \times A$, and we write $a R b$ to mean 
$(a,b) \in R$.  A relation on $A$ is said to be an {\it equivalence relation}
if it satisfies all three of the following properties:
\bigskip
\item{$\bullet$} $R$ is {\it reflexive}:  $aRa$ is true for all $a \in A$.
\item{$\bullet$} $R$ is {\it symmetric}:  For all $a,b\in R$, if $aRb$ is true, 
then $bRa$ is also true.
\item{$\bullet$} $R$ is {\it transitive}: For all $a,b,c\in A$, if $aRb$ and
$bRc$ are true, then $aRc$ is also true.
\bigskip
\noindent
If $R$ is an equivalence relation, then the {\it equivalence class}
of an element $a \in A$ is the set:
$$[a] = \{ x \in A\ |\ a R x\}$$
(in words:  $[a]$ is the set of all elements of $A$ that are related to $a$). 
Today we want to practice using these ideas on some additional examples
and think about how the equivalence classes of an equivalence relation
partition the set $A$.
\bigskip
\noindent
{\it Discussion Questions}
\bigskip
\noindent
A)  Let $A = {\bf Z}$ be the set of integers.  For each of the following
relations on ${\bf Z}$, 
\item{1)}  What is the set $\{ x \in {\bf Z}\ |\ x R 1\}$?
\item{2)}  Determine which of the three properties of an
equivalence relation are satisfied.  Prove all your assertions.
\bigskip
\item{i)}  $x R y$ if and only if $x = 4y$.  
\item{ii)}  $x R y$ if and only if $x - y$ is an integer multiple of 6.
\item{iii)}  $x R y$ if and only if $x \ge y$.
\item{iv)}  $x R y$ if and only if $|x - y| \le 2$.  
\bigskip
\noindent
B)  Of the four relations in part A, only one satisfies all three properties
for equivalence relations.  For that one, determine all the distinct equivalence
classes, and show that they give a partition of ${\bf Z}$.
\bigskip
\noindent
C)  In this problem, you will show that the equivalence classes for 
an equivalence relation $R$ on the set $A$ form a partition of $A$.
\item{1)}  What happens if you take the union of {\it all} the equivalence
classes $[a]$ for all $a\in A$.  What set do you get?  Hint: Think about
what the reflexive property means!
\item{2)}  Now, assume that $[a]$ and $[b]$ are any two equivalence classes.
Prove that if there is any $x \in [a] \cap [b]$, then in fact $[a] = [b]$.
\item{3)}  Give the contrapositive form of the implication you proved in part 2.
(Recall the contrapositive of ``if p then q'' is ``if not q then not p''.  
There is nothing to prove for this part because the contrapositive is just
a logically equivalent restatement.)
\bigskip
\noindent
{\it Assignment}
\bigskip
Group writeups due Monday, October 2.
\bye
