Equivalence Classes – Foundations of Mathematics

I am he
as you are he
as you are me
and we are all together.

John Lennon and Paul McCartney, I Am the Walrus

You've actually dealt with modular arithmetic for most of your life: the clock face represents arithmetic with modulus 12. If you've ever served in the military or listened to the BBC World Service, you're familiar with arithmetic modulo 24 as well.

When we deal with time, we feel free to use the symbol $1:00$ to denote any time that is a multiple of 12 hours away from a particular 1 am or 1 pm. Notice that transitivity means we don't actually care which particular reference 1 am or 1 pm we choose -- but if you're worried about it, we could follow Bishop Ussher and say that our archetypal $1:00$ is 1 am on Sunday, 23 October 4004 BC. It is very useful to have a symbol for all of the one-o'clocks, a symbol for all of the two-o'clocks, etc., so that we can write things like

Seven hours after $8:00$ is $3:00$ .

The following definition makes this idea precise.

Definition. Let $R$ be an equivalence relation on the set $A$ , and let $a\in A$ . The equivalence class of $a$ under the equivalence $R$ is the set

$\begin{equation*} [a]_R=\left\{x\in A\middle| x\operatorname{R}a\right\} \end{equation*}$

of all elements of $A$ which are equivalent to $a$ .

E.g. Consider the relation on $\mathbb{R}$ given by $x\operatorname{R}y$ if $x^2=y^2$ . Then $[0]_R=\{0\}$ , $[1]_R=\{1,-1\}$ , etc.

E.g. Consider the equivalence relation $C$ on $\mathbb{R}\times\mathbb{R}$ given by $(x,y)\operatorname{C}(z,w)$ if $x^2+y^2=z^2+w^2$ . Then

$\begin{align*} [(0,0)]_C&=\left\{(z,w)\middle|z^2+w^2=0\right\}=\{(0,0)\}\\ [(0,1)]_C&=\left\{(z,w)\middle|z^2+w^2=1\right\}\\ &=\text{circle of radius }1\text{ at the origin}\\ [(1,1)]_C&=\left\{(z,w)\middle|z^2+w^2=2\right\}\\ &=\text{circle of radius }\sqrt{2}\text{ at the origin} \end{align*}$

and it's easy to see that all other equivalence classes will be circles centered at the origin. Note that we have $[(0,1)]=[(1,0)]$ .

Definition. Given an equivalence relation $R$ on $A$ , the set of all equivalence classes is called the {\em quotient of $A$ by $R$ }. We write

$\begin{equation*} A_{/R}=\left\{[a]_R\middle|a\in A\right\} \end{equation*}$

Notice that the quotient of $A$ by an equivalence relation is a set of sets of elements of $A$ .

E.g. Consider the relation on $\mathbb{R}$ given by $x\operatorname{R}y$ if $x^2=y^2$ . Then $\mathbb{R}_{/R}=\left\{\{a,-a\}\middle|\ a\in\mathbb{R}\right\}$

E.g. If $C$ is the equivalence relation on $\mathbb{R}\times\mathbb{R}$ given by $(x,y)\operatorname{C}(z,w)$ if $x^2+y^2=z^2+w^2$ , then $\mathbb{R}\times\mathbb{R}_{/C}$ is the set of circles centered at the origin.

E.g. $\mathbb{Z}_{/\equiv_{12}}$ has 12 elements:

$\begin{equation*} \begin{aligned} \mathbb{Z}_{/\equiv_{12}}=&\left\{\{0,12,24,\ldots\},\{1,13,25,\ldots\},\{2,14,26,\ldots\}, \right.\\ &\{3,15,27,\ldots\},\{4,16,28,\ldots\},\{5,17,29,\ldots\},\\ &\{6,18,30,\ldots\},\{7,19,31,\ldots\},\{8,20,32,\ldots\},\\ &\left.\{9,21,33,\ldots\},\{10,22,34,\ldots\},\{11,23,35,\ldots\}\right\}\\ \end{aligned} \end{equation*}$

A convenient way to represent them is $[0]$ , $[1]$ , $[2]$ , etc. Notice that the mathematical convention is to start at 0 and go up to 11, which is different from how clocks are numbered.

Theorem. Let $R$ be an equivalence relation on $A$ . Let $a,b\in A$ . $[a]_R=[b]_R$ iff $a\operatorname{R} b$ .

Proof. Suppose $[a]_R=[b]_R$ . Since $a\in[a]_R$ , we have $a\in[b]_R$ , so by definition of $[b]_R$ , we have $a\operatorname{R} b$ .

Suppose $a\operatorname{R}b$ . We'll show $[a]_R\subseteq[b]_R$ . Let $c\in[a]_R$ . Then $c\operatorname{R}a$ . Since $R$ is transitive, we have $c\operatorname{R}b$ . Since $R$ is symmetric, this means $b\operatorname{R}c$ , i.e. $c\in[b]_R$ .

The proof that $[b]_R\subseteq[a]_R$ is similar. $\Box$ .

Theorem. $\mathbb{Z}_{/\equiv_p}$ consists of exactly the elements $[0]$ , $[1]$ , \ldots, $[p-1]$ .

Proof. We are asked to show set equality. It is clear that each $[k]$ for $0\leq k<p$ is an equivalence class, so we have one set inclusion.

To get the other set inclusion, suppose $S\in \mathbb{Z}_{/\equiv_p}$ is an equivalence class. Then there is some $k\in \mathbb{Z}$ with $[k]=S$ . We apply the Division Algorithm to write

$\begin{equation*} k=q\cdot p + r \end{equation*}$

where $0\leq r<p$ . Then $k-r$ is a multiple of $p$ , so $k\equiv_pr$ . Thus $S=[k]=[r]$ , and since $0\leq r<p$ , we have shown that $S$ is on our list of equivalence classes. $\Box$ .

An important property of equivalence classes is they ``cut up" the underlying set:

Theorem. Let $A$ be a set and $R$ be an equivalence relation on $A$ . Then:

No equivalence class is empty.
The equivalence classes cover $A$ ; that is, $A\subseteq \displaystyle\bigcup_{a\in A}[a]_R$ .
Equivalence classes do not overlap.

Proof. The first two are fairly straightforward from reflexivity.

Any equivalence class is $[x]_R$ for some $x\in A$ . Since $R$ is reflexive, $x\operatorname{R}x$ , i.e. $x\in[x]_R$ . So $[x]_R$ is nonempty.
Let $x\in A$ . We need to show that $x\in\displaystyle\bigcup_{a\in A}[a]_R$ . That is, we need to find some $a\in A$ for which $x\in[a]_R$ . Using $a=x$ and the observation above, we have $x\in[x]_R$ .

The third clause is trickier, mostly because we need to understand what it means. Consider the case of $A=\mathbb{Z}$ , $R=\equiv_{12}$ . Then $[3]_{\equiv 12}$ and $[15]_{\equiv 12}$ certainly overlap--they both contain $-9$ , for example. So if we take ``equivalence classes do not overlap" too literally it cannot be true.

But notice that $[3]_{\equiv 12}$ and $[15]_{\equiv 12}$ not only overlap, but in fact are equal. So we'll amend

equivalence classes do not overlap

distinct equivalence classes do not overlap

that is,

Theorem. If $[x]_R\neq [y]_R$ then $[x]_R\cap[y]_R=\varnothing$ .

Proof. We'll prove the contrapositive: if $[x]_R\cap[y]_R\neq\varnothing$ , then $[x]_R=[y]_R$ .

Assume $[x]_R\cap[y]_R$ is nonempty. Then there is some $z\in[x]_R\cap[y]_R$ . So $z\operatorname{R}x$ and $z\operatorname{R}y$ .

Since $R$ is symmetric, $x\operatorname{R}z$ .

Since $R$ is transitive, $x\operatorname{R} y$ . So $[x]_R=[y]_R$ . $\Box$ .

This theorem shows, for example, that there are in no redundancies on the list $[0]$ , $[1]$ , \ldots, $[p-1]$ of equivalence classes modulo $p$ .

An example from arithmetic: rational numbers

Exercise. Consider the relation on $\mathbb{Z}\times\left(\mathbb{Z}\setminus\{0\}\right)$ given by: $(m,n)\operatorname{CP}(r,s)$ if $ms=nr$ . Show that $CP$ is an equivalence relation. Do not use fractions in your proof.

What are the equivalence classes under the relation $CP$ ?

Claim. $[(0,1)]$ is the set of all pairs of the form $(0,k)$ .

Proof. First we show that every $(0,k)\in[(0,1)]$ . This is equivalent to showing $(0,k)\operatorname{CP}(0,1)$ . But by definition of $CP$ , all we need to show is $0\cdot 1 = k\cdot 0$ --which is clear since both sides are $0$ .

Now we show that if $(m,n)\in[(0,1)]$ , then it must be the case that $m=0$ . $(m,n)\in[(0,1)]$ means that $(m,n)\operatorname{CP}(0,1)$ , i.e. that $m=m\cdot 1=n\cdot 0=0$ . $\Box$ .

Exercise. Show that $[(1,1)]$ is the set of all pairs of the form $(k,k)$ .

We write $\frac{m}{n}$ for the equivalence class $[(m,n)]_{CP}$ , and we define:

Definition. The set of rational numbers $\mathbb{Q}$ is $\left(\mathbb{Z}\times\left(\mathbb{Z}\setminus\{0\}\right)\right)_{/CP}$ . That is, a rational number is an equivalence class of pairs of integers.