%!TEX root = proofs+concepts.tex



\chapter{Equivalence Relations} \label{EquivalenceRelationsChap}

\begin{quote}
\it 
An idea which can be used once is a trick. 
\\If it can be used more than once it becomes a method.
\par\raggedleft \small\rm\sf
George P\'olya (1887--1985) and G\'abor Szeg\H{o} (1895--1985), Hungarian mathematicians
\\ 
\emph{Problems and Theorems in Analysis}
\end{quote}

\medskip\noindent



\section{Binary relations} \label{sec.relation}


 Recall that, by definition, any function $f \colon A \to B$ is a set of ordered pairs. More precisely, each element of~$f$ is an ordered pair $(a,b)$, such that $a \in A$ and $b \in B$. Therefore, every element of~$f$ is an element of $A \times B$, so $f$~is a subset of $A \times B$.
\factoidbox{Every function from~$A$ to~$B$ is a subset of $A \times B$.}


\begin{eg} 
The function $\var{mother} \colon \var{PEOPLE} \to \var{PEOPLE}$ is represented by the set
	$$ \{\, (p,m) \in  \var{PEOPLE} \times \var{PEOPLE} \mid \text{$m$ is the mother of~$p$} \,\} .$$
\end{eg}


Many other relationships can also be represented by subsets of $\var{PEOPLE} \times \var{PEOPLE}$, even though they are not functions. For example, $\var{son}$ is not a function, because some people have more than one son (or because some people have no sons at all). However, we can represent this relation by the set
	$$ \{\, (p,s) \in  \var{PEOPLE} \times \var{PEOPLE} \mid \text{$s$ is a son of~$p$} \,\} .$$
In fact, any relationship that you can define between two people (or, to say this in the official language of logic, any binary predicate on the set $\var{PEOPLE}$) can be represented by a subset of $\var{PEOPLE} \times \var{PEOPLE}$. A few examples of possible relationships are:
	\begin{itemize}
	\item $x$ is a sister of~$y$
	\item $x$ knew $y$ in high school
	\item $x$ is taller than $y$
	\item $x$ and $y$ are in the same math class
	\item etc.
	\end{itemize}
In recognition of this, mathematicians simply \emph{define} a relation to be a set of ordered pairs; that is, a relation is any subset of $A \times B$. Unlike the case of functions, there are no restrictions --- every subset is a relation.


\begin{defn} Suppose $A$ and $B$ are sets. 
\begin{enumerate}
\item Any subset of $A \times B$ is called a \define[relation!from~$A$ to~$B$]{relation from~$A$ to~$B$}.
\item For the special case where $A = B$, any subset of $A \times A$ is called a \define[relation!binary]{binary relation} on~$A$.
\end{enumerate}
\end{defn}

We will mostly be concerned with binary relations, not relations from some set~$A$ to some other set~$B$.

\begin{eg} 
Some examples of binary relations on $\var{PEOPLE}$ are:
$\var{brother}$, $\var{sister}$, $\var{aunt}$, $\var{uncle}$, $\var{mother}$, $\var{father}$, $\var{grandfather}$, $\var{cousin}$, etc.
 \end{eg}

\begin{defn}
We can draw a picture to represent any given binary relation on any given set~$A$:
	\begin{itemize}
	\item Draw a dot for each element of~$A$.
	\item For $a,b \in A$, draw an arrow from $a$ to~$b$ if and only if $(a,b)$ is an element of the relation.
	\end{itemize} 
The resulting picture is called a \define{digraph}. (The word is pronounced ``DIE-graff'' --- it is short for ``directed graph\rlap.'') % We will see more on digraphs in \cref{BasicChap}. !!!
\end{defn}
 
 \begin{eg}
 Let $A =  \{1,2,3,4,5\}$. We can define a binary relation~$R$ on~$A$ by letting
 	$$ R = \{\, (x,y) \mid x^2 + y < 10 \,\} .$$
This binary relation is represented by the following digraph:
\\ \centerline{\includegraphics{PDF/x2+y.pdf}}
For example, note that $(x,4) \in R$ iff $x \in \{1,2\}$, and the digraph has arrows from $1$ to~$4$ and from $2$ to~$4$.
\end{eg}
%texpreamble
%("  \usepackage{amsmath}
%");
%defaultpen(  fontcommand(''\normalfont'') + fontsize(11) ); 
%
%from graph access *;
%unitsize(1cm);
%
%real r = 2;
%
%pair v(real i){
%	return r*(sin(2*pi*(i-1)/5) , cos(2*pi*(i-1)/5) );
%	}
%
%void drawit( int i, int j , real e){
%	pair vi = v(i);
%	pair vj = v(j);
%	pair vf = (1 - e)*vi + e * vj;
%	draw( vi .. vf, linewidth(2), EndArrow(8) );
%	}
%
%void leftdrawit( int i, int j , real e){
%	pair vi = v(i);
%	pair vj = v(j);
%	pair dout = rotate(20)*( vj - vi );
%	pair din = rotate(-20)*( vj - vi );
%	pair vf = vj - e* din;
%	draw( vi{dout} .. {din}vf, linewidth(2), EndArrow(8) );
%	}
%
%void rightdrawit( int i, int j , real e){
%	pair vi = v(i);
%	pair vj = v(j);
%	pair dout = rotate(-20)*( vj - vi );
%	pair din = rotate(20)*( vj - vi );
%	pair vf = vj - e* din;
%	draw( vi{dout} .. {din}vf, linewidth(2), EndArrow(8) );
%	}
%
%void loopit( int i){
%	real e = 0.08;
%	pair v = v(i);
%	pair dout = v( i - 0.8);
%	pair din =  (-1)*v( i + 0.8);
%	draw( v{dout}..(1.5)*v..{din}(v - e*din), linewidth(2), EndArrow(8) );
%	}
%
%leftdrawit(1,2,0.07); rightdrawit(1,3, 0.04); drawit(1,4, 0.96); drawit(1,5, 0.93);
%
%leftdrawit(2,1,0.07); drawit(2,3, 0.93); drawit(2,4, 0.96); drawit(2,5, 0.96);
%
%loopit(1); loopit(2); 
%
%for (int i = 1; i < 6; ++i){
%	draw( v(i) , linewidth(10) ); // draw (v(i), linewidth(6)+white); 
%	label( string(i), 1.2* v(i) );
%	}


 \begin{exer} \label{DrawBinRelExer}
Let $B$ be the set consisting of you, your siblings, your parents, and your grandparents.  Draw a digraph that represents each of the following binary relations on~$B$. 
% In each case, state whether or not your digraph is connected, and whether or not it is strongly connected.
 \begin{enumerate}
 \item \label{DrawBinRelExer-name}
 The relation ``has ever had the same last name as\rlap.''
 \item \label{DrawBinRelExer-child}
 The relation ``is a child of\rlap.''
 \item \label{DrawBinRelExer-married}
 The relation ``has ever been married to\rlap.''
 \end{enumerate}
 \end{exer}
 

 \begin{eg} 
This book (like other mathematics textbooks) deals mainly with relations on sets of mathematical objects. Here are a few well-known examples:
 \begin{enumerate}
\item The less-than relation ``$<$'' is a binary relation on~$\real$. 
\\ That is, for any real numbers $x$ and~$y$, the assertion $x < y$ is either true or false.
\item The equality relation ``$=$'' is a binary relation on the entire universe of discourse~$\univ$.
\item The subset relation ``$\subset$'' is a binary relation on the collection of all sets in~$\univ$.
\item The relation ``$x$~is disjoint from~$y$'' is also a binary relation on the collection of all sets in~$\univ$.
\end{enumerate}
\end{eg}


\begin{notation}
Suppose $\rel$ is a binary relation on a set~$A$. For $a_1,a_2 \in A$:
\begin{enumerate}
\item To signify that $(a_1,a_2) \in \mathord{\rel}$, we may write $a_1 \rel a_2$.
\item To signify that $(a_1,a_2) \notin \mathord{\rel}$, we may write $a_1 \raise1pt\hbox{$\not$}\mkern-5.5mu\rel a_2$.
\end{enumerate}
\end{notation}


There are three basic properties that any given binary relation may or may not have:

\begin{defn} \label{RefSymmTransDefn}
Suppose $\rel$ is a binary relation on a set~$A$. 
\begin{enumerate}
\item We say that $\rel$ is \define[reflexive binary relation]{reflexive} iff \quad
	$ \forall a \in A, (a \rel a) \vphantom{\Bigr)}$.
\item We say that $\rel$ is \define[symmetric binary relation]{symmetric} iff \quad
	$ \forall a,b \in A, \bigl( (a \rel b) \eif (b \rel a) \bigr) \vphantom{\Bigr)}$.
\item We say that $\rel$ is \define[transitive binary relation]{transitive} iff \quad
	$ \forall a,b,c \in A, \Bigl( \bigl( (a \rel b) \eand (b \rel c) \bigr) \eif (a \rel c) \Bigr) $.
\end{enumerate}
\end{defn}


\begin{eg} \ 
\begin{enumerate}
\item ``$=$'' is reflexive, symmetric, and transitive.
\item ``$<$'' is transitive, but neither reflexive nor symmetric.
\item ``$\subset$'' is transitive and reflexive, but not symmetric.
\end{enumerate}
\end{eg}

%\begin{rem}
%Each of the properties in \cref{RefSymmTransDefn} corresponds to a property of the digraph that we can draw of the relation. 
%\begin{itemize}
%\item A binary relation is reflexive if and only if the corresponding digraph has a loop at every vertex.
%\item A binary relation is symmetric if and only if every arc is in a digon in the corresponding digraph. (In such a case, we generally replace every digon by an edge and model the relation using a graph rather than a digraph.)
%\item A binary relation is transitive if and only if the corresponding digraph has the property that whenever one arc $\vec{uv}$ ends at the start of another arc~$\vec{vw}$, the arc $\vec{uv}$ is also in the digraph.
%\end{itemize}
%\end{rem}

%\begin{exer} \label{SymmTrans->ConnExer}
%Prove that if a binary relation is reflexive, symmetric, and transitive, then the corresponding graph has the property that any two vertices joined by a walk are adjacent. (That is, if there is a walk from~$u$ to~$v$, then $u$ is adjacent to~$v$.  In other words, every connected component of the graph is a complete graph with a loop at every vertex.)
%\hint{Use induction on $n$ to show that if there is a walk of length $n$ from~$u$ to~$v$ in the graph, then the edge $uv$ is in the graph.}
%\end{exer}

%\begin{exers} Suppose $\rel$ is a binary relation on a set~$A$.
%\begin{enumerate}
%\item Show that $\real$ is reflexive iff for all $a \in A$, we have $(a,a) \in \rel$.
%\end{enumerate}
%\end{exers}


\begin{eg}
Consider the following binary relation~$\rel$  on $\{1,2,3\}$:
$$\mathord{\rel} = \bigl\{(1,1), (2,2), (3,3), (1,2), (2,1), (2,3), (3,2) \bigr\}$$

 $$ \includegraphics[scale=0.4]{PDF/GraphRel.pdf} $$
\begin{enumerate}
\item $\rel$ is reflexive, because $1 \rel 1$, $2 \rel 2$, and $3 \rel 3$.
\item $\rel$ is symmetric, because, for each $(a,b) \in \mathord{\rel}$, the reversal $(b,a)$ is also in~$\rel$.
\item $\rel$ is \emph{not} transitive, because $1 \rel 2$ and $2 \rel 3$, but $1 \not\rel 3$.
\end{enumerate}
\end{eg}

%
%\begin{eg}
%Let $G$ be a simple graph with edge set $E$.
%Consider the relation $\sim$ defined on the vertex set of $G$ by $u \sim v \eiff uv \in E$.
%This relation:
%\begin{enumerate}
%\item is \emph{not} reflexive, because simple graphs are not allowed to have loops (edges from a vertex to itself);
%\item is symmetric, because if $uv \in E$ then $vu \in E$ is the same edge, looked at from the other end;
%\item may or may not be transitive, depending on the graph $G$.
%\end{enumerate}
%\end{eg}

%
%\begin{eg}
%Let $G$ be a simple digraph with arc set $A$.
%Consider the relation $\sim$ defined on the vertex set of $G$ by $u \sim v \eiff \vec{uv} \in A$.
%This relation:
%\begin{enumerate}
%\item is \emph{not} reflexive, because simple digraphs are not allowed to have loops (arcs from a vertex to itself);
%\item is symmetric only if every arc is part of a digon;
%\item may or may not be transitive, depending on the digraph $G$.
%\end{enumerate}
%\end{eg}


\begin{exer} \label{BinRelSomePropsEx}
Find binary relations on $\{1,2,3\}$ that are:
\begin{enumerate}
\item \label{BinRelSomePropsEx-symmonly}
symmetric, but neither reflexive nor transitive.
\item \label{BinRelSomePropsEx-refonly}
 reflexive, but neither symmetric nor transitive.
\item \label{BinRelSomePropsEx-transandsymm}
transitive and symmetric, but not reflexive.
\item \label{BinRelSomePropsEx-none}
neither reflexive, nor symmetric, nor transitive.
\end{enumerate}
(\emph{Express each relation as a set of ordered pairs, draw the corresponding digraph, and briefly justify your answers.})
\end{exer}

%\begin{exer} \label{EvenLengthRelExer}
% \ 
% \begin{enumerate}
%\item \label{EvenLengthRelExer-walk}
% Is the relation ``has a walk of even length'' between two vertices of a graph reflexive? symmetric? transitive?  Justify your answers.
%\item \label{EvenLengthRelExer-path}
%  Is the relation ``has a path of even length'' between two vertices of a graph reflexive? symmetric? transitive?  Justify your answers.
%\end{enumerate}
%\end{exer}



\section{Definition and basic properties of equivalence relations} \label{EquivalenceRelationsDefnSect}

People often need to sort through a collection of objects, putting similar objects together in a group. 

\begin{eg} \label{EquivRelZooEg}
When making an inventory of the animals in a zoo, we may wish to count the number of antelopes, the number of baboons, the number of cheetahs, and so forth. In this case, all of the animals of the same species might be grouped together. Mathematically speaking, we would define a binary relation $S$ on the set of animals in the zoo by 
	$$ \text{$x \mathrel{S} y$ \quad iff \quad $x$ and $y$ are in the same species} .$$
\end{eg}

When $x$ and~$y$ are placed in the same group (that is, when $x \mathrel{S} y$ in the above example), we may say that $x$ is ``equivalent'' to~$y$. This means that $x$ and~$y$ are the same in all respects that are of interest to us. (In the above example, we are interested only in the species of an animal, not its weight, or its age, or anything else.) We call the corresponding binary relation an ``equivalence relation\rlap.'' Thus, the binary relation~$S$ in the above example is an equivalence relation.


\begin{eg} \label{MoreEquivRelEgs}
Here are additional examples:
\begin{enumerate}
\item \label{MoreEquivRelEgs-name}
 If we are interested only in first names, we could define an equivalence relation~$\mathrel{N}$ on the set of all people by 
	$$ \text{$x \mathrel{N} y$ iff $x$~has the same first name as~$y$. } $$
\item Suppose a candy store has bins for different kinds of candy that they sell. To an employee restocking the bins, all pieces of candy that go into the same bin are the same, so he or she is dealing with an equivalence relation on the set of candy.
\item In geometry, one is often interested only in the shape of a triangle, not its location (or its colour, or anything else). Therefore, mathematicians define an equivalence relation $\cong$ on the set of all triangles by 
	$$ \text{$T_1 \cong T_2$ iff $T_1$ is {congruent} to~$T_2$.} $$
%\item For any $n \in \natural^+$, \cref{CongEquivRel} tells us  that congruence modulo~$n$ is reflexive, symmetric, and transitive, so it is an equivalence relation on~$\integer$.
\end{enumerate}
\end{eg}


\begin{rem}
Suppose $\sim$ is an equivalence relation. (That is, we have $x \sim y$ iff $x$ and~$y$ are the same in all respects that are of interest to us.) Then we would expect:
\begin{enumerate}
\item $\sim$ is reflexive ($x$ is the same as~$x$),
\item $\sim$ is symmetric (if $x$ is the same as~$y$, then $y$ is the same as~$x$),
and
\item $\sim$ is transitive (if $x$ is the same as~$y$, and $y$~is the same as~$z$, then $x$~is the same as~$z$).
\end{enumerate}
This motivates the following definition:
\end{rem}


\begin{defn}
An \define[equivalence!relation]{equivalence relation} on a set~$A$ is a binary relation on~$A$ that is reflexive, symmetric, and transitive.
\end{defn}


\begin{rem}
Instead of representing an equivalence relation by a letter, it is traditional to use the symbol~$\sim$%
\nindex{$\sim$}
(or sometimes~$\equiv$%
\nindex{$\equiv$}
or~$\cong$).%
\nindex{$\cong$}
\end{rem}

\begin{eg}
For any $n \in \integer$, we know that congruence modulo~$n$ is reflexive, symmetric, and transitive (see \cref{CongEquivRel}). Therefore, congruence modulo~$n$ is an equivalence relation.
\end{eg}


\begin{eg}
Define a binary relation~$\sim$ on~$\real$ by $x \sim y$ iff $x^2 = y^2$. Then $\sim$ is an equivalence relation.

\begin{proof}
We wish to show that $\sim$ is reflexive, symmetric, and transitive.

(reflexive) Given $x \in \real $, we have $x^2 = x^2$, so $x \sim x$.

(symmetric) Given $x,y \in \real$, such that $x \sim y$, we have $x^2 = y^2$. Since equality is symmetric, this implies $y^2 = x^2$, so $y \sim x$.

(transitive) Given $x,y,z \in \real$, such that $x \sim y$ and $y \sim z$, we have $x^2 = y^2$ and $y^2 = z^2$. Therefore $x^2 = y^2 = z^2$, so $x^2 = z^2$. Hence $x \sim z$.
\end{proof}
\end{eg}



\begin{eg} \label{NxNEquivRelEg}
Define a binary relation~$\sim$ on~$\natural \times \natural$ by $(a_1,b_1) \sim (a_2,b_2)$ iff $a_1 + b_2 = a_2 + b_1$. Then $\sim$ is an equivalence relation.

\begin{proof}
We wish to show that $\sim$ is reflexive, symmetric, and transitive.

(reflexive) Given $(a,b) \in \natural \times \natural$, we have $a + b = a + b$, so $(a,b) \sim (a,b)$.

(symmetric) Given $(a_1,b_1) , (a_2,b_2) \in \natural \times \natural$, such that $(a_1,b_1) \sim (a_2,b_2)$, the definition of~$\sim$ tells us that $a_1 +b_2 = a_2 + b_1$. Since equality is symmetric, this implies $a_2 + b_1 = a_1 + b_2$, so $(a_2,b_2) \sim (a_1,b_1)$.

(transitive) Given $(a_1,b_1) , (a_2,b_2) , (a_3,b_3) \in \natural \times \natural$, such that 
	$$ \text{$(a_1,b_1) \sim (a_2,b_2)$ \ and \  $(a_2,b_2) \sim (a_3,b_3)$} ,$$
we have 
\begin{equation} \label{NxNEquivRelEgEqn}
	\text{$a_1 + b_2 = a_2 + b_1$ and $a_2 + b_3 = a_3 + b_2$.}
\end{equation}
Therefore 
	\begin{align*}
	(a_1 + b_3) + (a_2 + b_2)
		&= (a_1 + b_2) + (a_2 + b_3) && \text{(rearrange terms)}
		\\&= (a_2 + b_1) + (a_3 + b_2) && \text{\pref{NxNEquivRelEgEqn}}
		\\&= (a_3 + b_1) + (a_2 + b_2) && \text{(rearrange terms)} .
	\end{align*}
Subtracting $a_2 + b_2$ from both sides of the equation, we conclude that $a_1 + b_3 = a_3 + b_1$,
so $(a_1,b_1) \sim (a_3,b_3)$.
\end{proof}
\end{eg}


\begin{exers} \label{EquivRelShowEx}
Show that each of these binary relations is an equivalence relation.
\begin{enumerate}
\item \label{EquivRelShowEx-x2min3x}
A binary relation $\sim$ on $\real$ is defined by $x \sim y$ iff $x^2 - 3x = y^2 - 3y$.
\item \label{EquivRelShowEx-xminyinZ}
A binary relation $\sim$ on $\real$ is defined by $x \sim y$ iff $x - y \in \integer$.
\\ \hint{You may assume (without proof) that the negative of any integer is an integer, and that the sum of any two integers is an integer. For transitivity, notice that $x - z = (x - y) + (y - z)$.}
\item \label{EquivRelShowEx-ab=ab}
A binary relation $\sim$ on $\natural^+ \times \natural^+$ is defined by $(a_1,b_1) \sim (a_2,b_2)$ iff $a_1 b_2 = a_2 b_1$.
\\ \hint{Similar to the proof in \cref{NxNEquivRelEg}, but with multiplication in place of addition.}
\end{enumerate}
\end{exers}


Any time we have a function, we can use it to make an equivalence relation on the domain of the function:

\begin{eg} \ 
\begin{enumerate}
\item Every animal has only one species, so $\var{Species}$ is a function that is defined on the set of all animals. The equivalence relation~$S$ of \cref{EquivRelZooEg} can be characterized by
	$$ \text{$x \mathrel{S} y$ \quad iff \quad $\var{Species}(x) = \var{Species}(y)$} .$$
\item If we assume that every person has a first name, then $\var{FirstName}$ is a function on the set of all people. The equivalence relation~$N$ of \fullcref{MoreEquivRelEgs}{name} can be characterized by
	$$ \text{$x \mathrel{N} y$ \quad iff \quad $\var{FirstName}(x) = \var{FirstName}(y)$} .$$
\end{enumerate}
\end{eg}


The following result generalizes this idea to all functions.
\begin{exer} \label{EquivRelFromFuncEx}
Suppose $f \colon A \to B$. If we define a binary relation~$\sim$ on~$A$ by
	$$ \text{$a_1 \sim a_2$ \quad iff \quad $f(a_1) = f(a_2)$} ,$$
then $\sim$ is an equivalence relation.
\end{exer}

\begin{exer} \label{EquivRel=6}
Show that if $\sim$ is an equivalence relation on~$\real$, then there exist $a,b \in \real$, such that $a \sim b$ and $a + b = 6$.
\end{exer}



 \section{Equivalence classes} \label{EquivalenceRelationsClassesSect}

If we are interested in first names (as in \fullcref{MoreEquivRelEgs}{name}),
then we may also be interested in the set of all people who have the same first name as you. This is called your ``equivalence class\rlap.''
 
 \begin{defn}
 Suppose $\sim$ is an equivalence relation on a set~$A$. For each $a \in A$, the \define[equivalence!class]{equivalence class} of~$a$ is the following subset of~$A$:
 	$$ [a] = \{\, a' \in A \mid a' \sim a \,\} 
	\nindex{$[a]$}
	.$$
\end{defn}


\begin{eg}
For the equivalence relation~$N$ described in \fullcref{MoreEquivRelEgs}{name}, we have
	$$ [\var{Justin Timberlake}] = \{\, x \in \var{People} \mid \var{FirstName}(x) = \var{FirstName}(\var{Justin Timberlake}) \,\} .$$
In other words, $[\var{Justin Timberlake}]$ is the set of all people whose first name is Justin.
\end{eg}


\begin{warn}
The notation $[a]$ does not tell us which equivalence relation is being used. This can be confusing if more than one equivalence relation is under consideration.
\end{warn}


\begin{eg} \label{EquivClassEg}
Suppose $A = \{1,2,3,4,5\}$ and 
	$$R = \left\{ \begin{matrix} (1,1), (1,3), (1,4), (2,2), (2,5), (3,1), (3,3), \\
		(3,4), (4,1), (4,3), (4,4), (5,2), (5,5)
		\end{matrix}
		 \right\} .$$
One can verify that $R$ is an equivalence relation on~$A$. The equivalence classes are:
$$ [1] = \{1,3,4\},
\qquad [2] = \{2,5\} ,
\qquad [3] = \{1,3,4\} 
$$
$$[4] = \{1,3,4\} ,
\qquad [5] = \{2,5\} .$$
\end{eg}



 
  


\begin{exers} \label{EquivClassEasyEx}
\emph{You do not need to show your work.}
\begin{enumerate}
\item \label{EquivClassEasyEx-set}
Let $B = \{1,2,3,4,5\}$ and 
	$$S = \left\{ \begin{matrix} (1,1), (1,4), (2,2), (2,3), (3,2), \\
		(3,3), (4,1), (4,4), (5,5)
		\end{matrix}
		 \right\} .$$
Find the equivalence class of each element of~$B$. (You may assume without proof that $S$ is an equivalence relation on~$B$.)


\item \label{EquivClassEasyEx-x+y}
Let $C = \{1,2,3,4,5\}$ and define $T$ by 
	$$ \text{$x \mathrel{T} y$ iff $x + y$ is even.} $$
Find the equivalence class of each element of~$C$. (You may assume without proof that $T$ is an equivalence relation on~$C$.)
\end{enumerate}
\end{exers}

The following theorem presents some very important properties of equivalence classes:

\begin{thm} \label{EquivRelProps}
Suppose $\sim$ is an equivalence relation on a set~$A$. Then:
\begin{enumerate}
\item \label{EquivRelProps-aIn[a]}
 For all $a \in A$, we have $a \in [a]$.
\item \label{EquivRelProps-nonempty}
 For all $a \in A$, we have $[a] \neq \emptyset$.
\item \label{EquivRelProps-union}
 The union of the equivalence classes is all of~$A$. That is, we have $A = \bigcup_{a \in A} [a]$, where
	$$ \bigcup_{a \in A} [a] = \bigset{ x }{ \exists a \in A, \bigl(x \in [a] \bigr)} .$$
%Every element of~$A$ is in some equivalence class.
\item \label{EquivRelProps-equal}
 For any $a_1,a_2 \in A$, such that $a_1 \sim a_2$, we have $[a_1] = [a_2]$.
\item \label{EquivRelProps-disjoint}
 For any $a_1,a_2 \in A$, such that $a_1 \not\sim a_2$, we have $[a_1] \cap [a_2] = \emptyset$.
\end{enumerate}
\end{thm}

\begin{exer} \label{EquivRelPropsPfEx}
Prove \cref{EquivRelProps}.
\\ \hint{Use the fact that $\sim$ is reflexive, symmetric and transitive.}
\end{exer}


\begin{rem}
Suppose $\sim$ is an equivalence relation on a set~$A$. The above theorem implies  that any two equivalence classes are either equal or disjoint; that is, either they have exactly the same elements, or they have no elements in common. 

\begin{proof}[{\normalfont\sffamily Proof}]
Given two equivalence classes $[a_1]$ and~$[a_2]$ that are not disjoint, we wish to show $[a_1] = [a_2]$. Since the equivalence classes are not disjoint, their intersection is nonempty, thus, there is some $a \in [a_1] \cap [a_2]$. Hence, $a \in [a_1]$ and $a \in [a_2]$. By definition of the equivalence classes, this means $a \sim a_1$ and $a \sim a_2$. Hence, \fullcref{EquivRelProps}{equal} tells us that $[a] = [a_1]$ and $[a] = [a_2]$. Therefore $[a_1] = [a] = [a_2]$, as desired.
\end{proof}
\end{rem}



\section{Modular arithmetic} \label{EquivalenceRelationsModArithSect}

Suppose, as usual, that $\sim$ is an equivalence relation on a set~$A$. Writing $a \sim b$ means that $a$ is ``equivalent'' to~$b$. In this case, we may want to think of~$a$ as being \emph{equal} to~$b$. But that would not be right, because $a$ and~$b$ are (probably) two different things. However, we have the following fundamental property of equivalence classes:
\factoidbox{$a \sim b$ \quad iff \quad $[a] = [b]$.}
Thus, by putting square brackets around $a$ and~$b$, we can turn mere equivalence into true equality. That is what makes equivalence classes so important. A good example is provided by congruence modulo~$n$.


\subsection{The integers modulo \texorpdfstring{$3$}{3}}

For any $n \in \integer$, we know that congruence modulo~$n$ is an equivalence relation (see \cref{CongEquivRel}). As an example, let us consider the case where $n = 3$. To emphasize the fact that $n = 3$, we will include a subscript~${}_{\textstyle3}$ in the notation for an equivalence class: we write $[k]_3$, instead of~$[k]$.


We all know that when an integer is divided by~$3$, the remainder must be either $0$, $1$, or~$2$, so \fullcref{CongVsRemainderEx}{remainder} tells us that every integer is congruent (modulo~$3$) to either $0$, $1$, or~$2$. Thus,
\begin{itemize}
\item for every $k \in \integer$, the equivalence class~$[k]_3$ must be either $[0]_3$, $[1]_3$, or~$[2]_3$.
\end{itemize}
On the other hand, it is easy to check that no two of $0$, $1$, and~$2$ are congruent (modulo~$3$), so
\begin{itemize}
\item $[0]_3$, $[1]_3$, and~$[2]_3$ are three distinct equivalence classes.
\end{itemize}
Thus, we see that there are exactly three equivalence classes, namely, $[0]_3$, $[1]_3$, and~$[2]_3$. The set of these equivalence classes is called the  {\mathversion{bold}\define[modulo!integers modulo~3]{integers modulo~$3$}}. It is denoted~$\integer_3$.


\begin{notation}
The notation $[k]_3$ (or even just $[k]$) is rather cumbersome. For convenience, we may write $\class{k}$%
\nindex{$\class{\phantom{9}}$}
for the equivalence class of~$k$. Thus, 
	$$\integer_3 = \{ \class{0}, \class{1}, \class{2} \} .$$
\end{notation}


\begin{defn}
We can do arithmetic (add, subtract, and multiply) on these equivalence classes, just as we do for ordinary integers. This is called  {\mathversion{bold}\define[modulo!arithmetic modulo~$3$]{arithmetic modulo~$3$}}. The rules are:
\begin{itemize}
\item $[a]_3 + [b]_3 = [a+b]_3$ \qquad (or $\class{a} + \class{b} = \class{a + b}$),
\item $[a]_3 - [b]_3 = [a-b]_3$ \qquad (or $\class{a} - \class{b} = \class{a - b}$),
and
\item $[a]_3 \times [b]_3 = [ab]_3$\hphantom{${}\times{}$}
\qquad (or $\class{a} \times \class{b} = \class{a  b}$).
\end{itemize}
(Actually, we should write $+_3$, $-_3$, and~$\times_3$, to indicate that the arithmetic is being done modulo~$3$, but we will usually not bother.)
\end{defn}


\begin{eg}
We have $[1]_3 + [2]_3 = [1 + 2]_3 = [3]_3$. However, since $3 \equiv 0 \pmod{3}$, we have $[3]_3 = [0]_3$, so the above equation can also be written as $[1]_3 + [2]_3 = [0]_3$. Equivalently, $\class{1} + \class{2} = \class{0}$.
\end{eg}

This is an example of the following general principle:
$$ \text{%the result of any arithmetic operation (modulo~$3$) will be either $[0]_3$, $[1]_3$, or~$[2]_3$:
\it If $r$ is the remainder when $a + b$ is divided by\/~$3$, then $\class{a} \mathbin{+_3} \class{b} = \class{r}$.} $$


\begin{eg}
Here is a table that shows the results of addition modulo~$3$:
\begin{center} \begin{tabular}{c||c|c|c}
$+_3$&$\class{0}$&$\class{1}$&$\class{2}$ \\
\noalign{\hrule}
\noalign{\smallskip}
\noalign{\hrule}
$\class{0}$&$\class{0}$&$\class{1}$&$\class{2}$ \\
\noalign{\hrule}
$\class{1}$&$\class{1}$&$\class{2}$&$\class{0}$ \\
\noalign{\hrule}
$\class{2}$&$\class{2}$&$\class{0}$&$\class{1}$ \\
\end{tabular}
\end{center}
%\begin{center}
%\begin{tabular}{c||c|c|c}
%$+_3$&$[0]_3$&$[1]_3$&$[2]_3$ \\
%\noalign{\hrule}
%\noalign{\smallskip}
%\noalign{\hrule}
%$[0]_3$&$[0]_3$&$[1]_3$&$[2]_3$ \\
%\noalign{\hrule}
%$[1]_3$&$[1]_3$&$[2]_3$&$[0]_3$ \\
%\noalign{\hrule}
%$[2]_3$&$[2]_3$&$[0]_3$&$[1]_3$ \\
%\end{tabular}
%\end{center}
\end{eg}


\begin{exers} \label{Mod3TablesEx}
Make a table that shows the results of:
\begin{multicols}{2}
\begin{enumerate}
\item \label{Mod3TablesEx-subtraction}
subtraction modulo~$3$
\item \label{Mod3TablesEx-multiplication}
multiplication modulo~$3$
\end{enumerate}
\end{multicols}
\noindent (\emph{Write each of the entries of your table as either\/ $\class{0}$, $\class{1}$, or\/ $\class{2}$.})
\end{exers}



\subsection{The integers modulo \texorpdfstring{$n$}{n}}
The preceding discussion can be generalized to apply with any integer~$n$ in place of~$3$. This results in \define{modular arithmetic}.

\begin{defn}
Fix some nonzero natural number $n \in \natural^+$.
\begin{enumerate}
\item For any integer~$k$, we use $[k]_n$ to denote the equivalence class of~$k$ under congruence modulo~$n$. When $n$ is clear from the context, we may write~$\class{k}$, instead of $[k]_n$.
\item The set of these equivalence classes is called the {\mathversion{bold}\define[modulo!integers modulo~n@integers modulo~$n$]{integers modulo~$n$}}. It is denoted~$\integer_n$.


 
  

\item Addition, subtraction, and multiplication modulo~$n$ are defined by:
\begin{itemize}
\item $\class{a} \mathbin{+_n} \class{b} = \class{a + b}$,
\item $\class{a} \mathbin{-_n} \class{b} = \class{a - b}$,
and
\item $\class{a} \mathbin{\times_n} \class{b} = \class{a  b}$.
\end{itemize}
(When $n$ is clear from the context, we usually write $+$, $-$, and~$\times$, rather than $+_n$, $-_n$, and~$\times_n$.)
\end{enumerate}
\end{defn}


Note that $\# \integer_n = n$. More precisely:

\begin{prop}
For any $n \in \natural^+$, we have 
	$$\integer_n = \{ \class{0}, \class{1}, \class{2}, \ldots, \class{n-1} \}$$
and\/ $\class{0}, \class{1}, \class{2}, \ldots, \class{n-1}$ are all distinct.
\end{prop}

\begin{eg}
Simplify $(\class{17} - \class{5}) \times (\class{21} +\class{11})$ in $\integer_7$.
\end{eg}

\begin{solution}
We have
	\begin{align*}
	(\class{17} - \class{5}) \times (\class{21} +\class{11})
	&=(\class{3} - \class{5}) \times (\class{0} +\class{4})
	=  (\class{3 - 5}) \times (\class{0 + 4})
	\\&= \class{-2} \times \class{4}
	= \class{5} \times \class{4}
	= \class{5 \times 4}
	= \class{20}
	= \class{6}
	. \end{align*}
\end{solution}


\begin{exers} \label{ModArithEx} \ 
\begin{problist}
\item \label{ModArithEx-mod5}
Simplify $(\class{17} - \class{5}) \times (\class{21} +\class{11})$ in $\integer_5$.
\item \label{ModArithEx-mod9}
Simplify $\class{32} + (\class{23} \times \class{16})$ in $\integer_9$. 
\item \label{ModArithEx-mod12}
Simplify $(\class{25} \times \class{35}) + (\class{18} -\class{12})$ in $\integer_{12}$.
\item \label{ModArithEx-tables} 
Make tables that show the results of:
\begin{enumerate}
\item \label{ModArithEx-tables-addition} 
addition modulo~$4$.
\item \label{ModArithEx-tables-subtraction} 
subtraction modulo~$5$.
\item \label{ModArithEx-tables-multiplication} 
multiplication modulo~$6$.
\end{enumerate}
\item  \label{ModArithEx-ZeroDiv}
Find $x,y \in \integer_{12}$, such that $x \neq \class{0}$ and $y \neq \class{0}$, but $x y = \class{0}$.
\end{problist}
\end{exers}




\section{Functions need to be well-defined} \label{EquivalenceRelationsWellDefSect}

The discussion of modular arithmetic ignored a very important point: the operations of addition, subtraction, and multiplication need to be \define{well-defined}. That is, if $\class{a_1} = \class{a_2}$ and $\class{b_1} = \class{b_2}$, then we need to know that
\begin{enumerate}
\item $\class{a_1} \mathbin{+_n} \class{b_1} = \class{a_2} \mathbin{+_n} \class{b_2}$,
\item $\class{a_1} \mathbin{-_n} \class{b_1} = \class{a_2} \mathbin{-_n} \class{b_2}$, 
and
\item $\class{a_1} \mathbin{\times_n} \class{b_1} = \class{a_2} \mathbin{\times_n} \class{b_2}$.
\end{enumerate}
Fortunately, these statements are all true. Indeed, they follow easily from \cref{CongRespectOpsEx}:
\begin{enumerate}
\item Since $\class{a_1} = \class{a_2}$ and $\class{b_1} = \class{b_2}$, we have $a_1 \equiv a_2 \pmod{n}$ and $b_1 \equiv b_2 \pmod{n}$, so \fullcref{CongRespectOpsEx}{sum} tells us that $a_1 + b_1 \equiv a_2 + b_2 \pmod{n}$. Therefore $\class{a_1 + b_1} = \class{a_2 + b_2}$, as desired.
\end{enumerate}
The proofs for $-_n$ and~$\times_n$ are similar.


\begin{eg}
One might try to define an exponentiation operation by:
	$$ \text{$\class{a} \mathbin{\wedge_n} {\class{b}} = \class{a^b}$ \quad for $\class{a}, \class{b} \in \integer_n$} .$$
Unfortunately, this does not work, because $\wedge_n$ is not well-defined:
\begin{exer} \label{ExpModNotWellDef}
Find $a_1,a_2,b_1,b_2 \in \integer$, such that $[a_1]_3 = [a_2]_3$ and $[b_1]_3 = [b_2]_3$, but $\left[a_1^{b_1}\right]_3 \neq \left[a_2^{b_2}\right]_3$.
\end{exer}
\end{eg}


\begin{exers}  \label{WellDefEx}
Assume $m,n \in \natural^+$.
\begin{enumerate}
\item  \label{WellDefEx-AbsVal}
 Show that if $n > 2$, then absolute value does \emph{not} provide a well-defined function from~$\integer_n$ to~$\integer_n$. That is, show there exist $a,b \in \integer$, such that $[a]_n = [b]_n$, but $\bigl[ |a| \bigr]_n \neq \bigl[ |b| \bigr]_n$.
\item  \label{WellDefEx-divide}
 Show that if $m \divides n$, then there is a well-defined function 
	$$ \text{$f \colon \integer_n \to \integer_m$, given by $f \bigl( [a]_n \bigr) = [a]_m$.} $$
\item  \label{WellDefEx-odd2}
 Show that if we try to define a function $g \colon \integer_3 \to \integer_2$ by $g \bigl( [a]_3 \bigr) = [a]_2$, then the result is \emph{not} well-defined.
\end{enumerate}
\end{exers}







\section{Partitions}  \label{EquivalenceRelationsPartitionsSect}

It often happens that someone divides up a set into several disjoint subsets. This is called a ``partition'' of the set.

\begin{center}
\begin{figure}[ht]
\includegraphics[scale=0.35]{PDF/partition.pdf}
\caption{A partition of~$A$ into subsets $A_1, \ldots, A_5$. 
(Each element of~$A$ is in one and only one of the subsets.)}
\end{figure}
\end{center}


\begin{eg} \label{ToyPartitionEg}
Mary is leaving for university, and does not want her childhood toys any more, so she will divide them up among her younger siblings: Alice, Bob, and Cindy. Let 
\begin{itemize}
\item $T$ be the set of all of Mary's toys, 
and
\item $A$, $B$, and~$C$ be the set of toys that she will give to Alice, to Bob, and to Cindy, respectively.
\end{itemize}
Then $A$, $B$, and~$C$ are subsets of~$T$, and they should be chosen so that:
\begin{enumerate}
\item the union of $A$, $B$ and~$C$ is~$T$ (that is, $A \cup B \cup C = T$), so all of the toys are given away,
and
\item the sets $A$, $B$, and~$C$ are pairwise disjoint (that is, $A \cap B = \emptyset$, $A \cap C = \emptyset$, and $B \cap C = \emptyset$), so there will not be any confusion about who is the new owner of each toy.
\end{enumerate}
Thus, we see that Mary should partition~$T$ into three disjoint subsets. 
\end{eg}


\begin{defn}
A \define[partition of a set]{partition} of a set~$A$ is a collection of nonempty subsets of~$A$, such that each element of~$A$ is in exactly one of the subsets. In other words:
\begin{enumerate}
\item the union of the subsets in the collection is all of~$A$,
and
\item the subsets in the collection are pairwise disjoint.
\end{enumerate}
\end{defn}


\begin{eg}
In \cref{ToyPartitionEg}, the collection $\{A,B,C\}$ is a partition of~$T$.\footnote{Actually, this may not be correct, because, for a partition, we require the sets $A$, $B$, and~$C$ to be nonempty, but it is possible that one (or more) of Mary's siblings will not be given any toys.}
\end{eg}

%\begin{exer}
%Prove that a graph with vertex set $V$ is connected if and only if for every partition $V_1, V_2$ of $V$, there exists some edge with one end in $V_1$ and the other end in $V_2$.
%\end{exer}

%Equivalence classes give examples of partitions.


\begin{eg} \label{EquivClassPartEg}
In \cref{EquivClassEg}, the equivalence classes are $\{1,3,4\}$ and $\{2,5\}$. Since $1,2,3,4,5$ each belong to exactly one of these sets, we see that the set
	$$ \bigl\{ \{1,3,4\}, \{2,5\} \bigr\} $$
of equivalence classes is a partition of $\{1,2, 3,4,5\}$.
\end{eg}


The following result is an immediate consequence of \cref{EquivRelProps}. It says that equivalence classes always provide a partition.

\begin{cor} \label{EquivRel->Part}
Suppose $\sim$ is an equivalence relation on a set~$A$. Then 
	$$ \{\, [a] \mid a \in A \,\} $$
is a partition of~$A$.
\end{cor}

\begin{proof}
From parts \pref{EquivRelProps-nonempty}, \pref{EquivRelProps-union}, and~\pref{EquivRelProps-disjoint} of \cref{EquivRelProps}, we know that the equivalence classes are nonempty, that their union is~$A$, and that they are pairwise disjoint.
\end{proof}

\begin{rem}
\cref{EquivRel->Part} tells us that every equivalence relation gives us a partition. Conversely, the following result shows that any partition comes from an equivalence relation. Thus, equivalence relations and partitions are just two different ways of looking at the same thing.
\end{rem}


\begin{exer}\label{Part->EquivRel} % no solution !!!
Suppose $\mathcal{P}$ is a partition of a set~$A$. Define a binary relation $\sim$ on~$A$ by
	$$ \text{$a \sim b$ \quad iff \quad $\exists C \in \mathcal{P}, \ ( \text{$a \in C$ and $b \in C$} )$} .$$
Show that:
\begin{enumerate}
\item \label{Part->EquivRel-equiv}
 $\sim$ is an equivalence relation on~$A$,
and
\item \label{Part->EquivRel-classes}
 the set of equivalence classes is the partition~$\mathcal{P}$.
\end{enumerate}
\end{exer}



Recall that $\integer_n$ replaces integers $a$ and~$b$ that are congruent modulo~$n$ with objects~$\class{a}$ and~$\class{b}$ that are exactly equal to each other. This was achieved by letting $\integer_n$ be the set of all equivalence classes. The set $\integer_n$ applies only to congruence modulo~$n$, but the same thing can be done for any equivalence relation:

\begin{defn}
Suppose $\sim$ is an equivalence relation on a set~$A$. The set of all equivalence classes is called \define[modulo!$A$ modulo~$\sim$]{$A$ modulo~$\sim$}. It is denoted $A/\mathord{\sim}$.
\end{defn}

\begin{eg}
Suppose we define an equivalence relation~$\sim$ on~$\integer$ by $a \sim b$ iff $a \equiv b \pmod{n}$. Then $\integer/\mathord{\sim}$ is simply another name for~$\integer_n$.
\end{eg}

% should have some exercises !!!

%For example, \cref{EquivRel->Part} can be restated as the assertion that if $\sim$ is any equivalence relation on~$A$, then $A/\mathord{\sim}$ is a partition of~$A$.



 
  

\begin{summary}
\item Important definitions:
\begin{itemize}
\item relation, binary relation
\item reflexive, symmetric, transitive
\item equivalence relation
\item equivalence class
%\item connected components
\item modular arithmetic
\item integers modulo $n$
\item well-defined
\item partition
\end{itemize}
\item Modular arithmetic is an important example of the use of equivalence classes.
\item Functions must be well-defined.
\item Every binary relation can be drawn as a digraph.
\item Every partition gives rise to an equivalence relation, and vice versa.
\item Notation:
\begin{itemize}
\item $\sim$, $\cong$, or $\equiv$ are used for equivalence relations
\item $[a]$, or $\class{a}$
\item $\integer_n$
\end{itemize}
\end{summary}

 