# Equivalence relations and partitions: some core basic theorems

Suppose R is an equivalence relation on a set S. For each a in S, let [a] denote the set of elements of S to which a is related under R, that is, $[a] = \{ x: (a,x) \in R\}$

We call [a] the equivalence class of a in S under R. The collection of all such equivalence classes is denoted by S/R, that is, $S/R = \{ [a]: a \in S\}$. It is called the quotient set of S by R.

The fundamental property of an equivalence relation and its quotient set is contained in the following theorem:

Theorem I:

Let R be an equivalence relation on a set S. Then, the quotient set S/R is a partition of S. Specifically,

(i) For each $a \in S$, we have $a \in [a]$.

(ii) $[a]=[b]$ if and only if $(a,b) \in R$.

(iii) If $[a] \neq [b]$, then [a] and [b] are disjoint.

Proof of (i):

Since R is reflexive, $(a,a) \in R$ for every $a \in S$ and therefore $a \in [a]$.

Proof of (ii):

Assume: $(a,b) \in R$.

we want to show that $[a] = [b]$. That is, we got to prove, (i) $[b] \subseteq [a]$ and (ii) $[a] \subseteq [b]$.

Let $x \in [b]$; then, $(b,x) \in R$. But, by hypothesis $(a,b) \in R$ and so, by transitivity, $(a,x) \in R$. Accordingly, $x \in [a]$. Thus, $[b] \subseteq [a]$.

To prove that $[a] \subseteq [b]$, we observe that $(a,b) \in R$ implies, by symmetry, that $(b,a) \in R$. Then, by a similar argument, we obtain $[a] \subseteq [b]$. Consequently, $[a]=[b]$.

Now, assume $[a] = [b]$.

Then by part (i) of this proof that for each $a \in S$, we have $a \in [a]$. So, also, here $b \in [b]=[a]$; hence, $(a,b) \in R$.

Proof of (iii):

Here, we prove the equivalent contrapositive of the statement (iii), that is:

If $[a] \bigcap [b] \neq \emptyset$ then $[a] = [b]$.

if $[a] \bigcap [b] \neq \emptyset$ then there exists an element $x \in A$ with $x \in [a] \bigcap [b]$. Hence, $(a,x) \in R$ and $(b,x) \in R$. By symmetry, $(x,b) \in R$, and, by transitivity, $(a,b) \in R$. Consequently, by proof (ii), $[a] = [b]$.

The converse of the above theorem is also true. That is,

Theorem II:

Suppose $P = \{ A_{i}\}$ is a partition of set S. Then, there is an equivalence relation $\sim$ on S such that the set $S/\sim$ of equivalence classes is the same as the partition $P = \{ A_{i}\}$.

Specifically, for $a, b \in S$, the equivalence $\sim$ in Theorem I is defined by $a \sim b$ if a and b belong to the same cell in P.

Thus, we see that there is a one-one correspondence between the equivalence relations on a set S and the partitions of S.

Proof of Theorem II:

Let $a, b \in S$, define $a \sim b$ if a and b belong to the same cell $A_{k}$ in P. We need to show that $\sim$ is reflexive, symmetric and transitive.

(i) Let $a \in S$. Since P is a partition there exists some $A_{k}$ in P such that $a \in A_{k}$. Hence, $a \sim a$. Thus, $\sim$ is reflexive.

(ii) Symmetry follows from the fact that if $a, b \in A_{k}$, then $b, a \in A_{k}$.

(iii) Suppose $a \sim b$ and $b \sim c$. Then, $a, b \in A_{i}$ and $b, c \in A_{j}$. Therefore, $b \in A_{i} \bigcap A_{j}$. Since P is a partition, $A_{i} = A_{j}$. Thus, $a, c \in A_{i}$ and so $a \sim c$. Thus, $\sim$ is transitive.

Accordingly, $\sim$ is an equivalence relation on S.

Furthermore,

$[a] = \{ x: a \sim x\}$.

Thus, the equivalence classes under $\sim$ are the same as the cells in the partition P.

More later,

Nalin Pithwa.