Equivalence relations

Definition 4.3.1   The relation $\mathcal{R}$ on $ES$ is an equivalence relation if it is reflexive, symmetric and transitive.

We often denote these properties by ``RST''; note that ``R'' (for reflexivity) concerns single elements, ``S'' (for symmetry) concerns pairs of elements, and ``T'' (for transitivity) concerns triples of elements. These are ``nice'' properties designed to make $\mathcal{R}$ behave something like $=$, with respect to some specific property of the elements of the set.

Example 4.3.2   Consider the set $\mathbb{Z}$ of all integers and the relation $\mathrel{\mathcal{R}}$ on $\mathbb{Z}$ defined as follows:

$$\forall m \in \mathbb{Z}, \; \forall n\in \mathbb{Z}, \; m \mathrel{\mathcal{R}}n \Longleftrightarrow m^2=n^2.$$

This relation is an equivalence relation on $\mathbb{Z}$:

(i)

R: $\forall m \in \mathbb{Z}, \; m^2=m^2$, thus $m \mathrel{\mathcal{R}}m$.

(ii)

S: $\forall m \in \mathbb{Z}, \; \forall n \in \mathbb{Z}, \; m^2=n^2 \Longrightarrow n^2=m^2$, i.e $m \mathrel{\mathcal{R}}n \Rightarrow n \mathrel{\mathcal{R}}m$.

(iii)

T: $\forall m \in \mathbb{Z}, \; \forall n \in \mathbb{Z}, \; \forall p \in \mathbb{Z},$

$$\begin{cases} m \mathrel{\mathcal{R}}n \\ n \mathrel{\mathc... ...trightarrow \begin{cases} m^2 =n^2 \\ n^2 = p^2 \end{cases}$$

It follows that$m^2 =p^2$, i.e. $m \mathrel{\mathcal{R}}p$.

Example 4.3.3   The binary relation given in Example 2.6 is an equivalence relation.

Definition 4.3.4   If $\mathcal{R}$ is an equivalence relation on the set $E$ and $a \in E$, then

$$[a]_\mathcal{R}= [a] = \{ b \in E \; \vert \; a \mathrel{\mathcal{R}}b \}.$$

is called the equivalence class of $a$.

Example 4.3.5   In Example 2.6, each possible eye color determines an equivalence class.

Definition 4.3.6   Let $E$ be a set. A collection $A_1, A_2, \dots, A_n$ of non empty subsets of $E$ form a partition of $E$ if the following conditions hold:

(i)

$\underset{k=1}{\overset{n}{\bigcup}} A_k = E$.

(ii)

If $i \neq j$, then $A_i \cap A_j = \emptyset$.

For example, the set of odd integers and the set of even integers form a partition of $\mathbb{Z}$.

Theorem 4.3.7   If $\mathcal{R}$ is an equivalence relation then the equivalence classes form a partition of $S$.

Proof.     

(i)

If $a \in S$ then $a \in [a]$, so the classes cover all of $S$.

(ii)

If $[a] \cap [b] \neq \emptyset$ then $\exists c \in [a] \cap [b]$. Now $a \mathrel{\mathcal{R}}c$ and $b \mathrel{\mathcal{R}}c \Rightarrow c \mathrel{\mathcal{R}}b$. Thus $a \mathrel{\mathcal{R}}b$ and $b \in [a]$. If $d \in [b]$ then $b \mathrel{\mathcal{R}}d$ so $a \mathrel{\mathcal{R}}d$ and thus $[b] \subseteq [a]$. We can similarly show that $[a] \subseteq [b]$ and thus $[a] = [b]$.

$\qedsymbol$

The converse of this is true: if we have a partition of $S$ we can define an equivalence relation on $S$ by $a \mathrel{\mathcal{R}}b$ iff $a$ and $b$ are in the same part.

Remark 4.3.8 (For algebraists only)   An application of this is the proof of Lagrange's Theorem. The idea is to show that being in the same (left/right) coset is an equivalence relation.

Definition 4.3.9   Given an equivalence relation $\mathcal{R}$ on $E$, the set of all equivalence classes is called the quotient set and is denoted by $E/\mathcal{R}$.

Example 4.3.10   On the set $\mathbb{R}$ of all the real numbers we define the following relation:

$$\forall x \in \mathbb{R}, \; \forall y \in \mathbb{R}, \; x \sim y \Longleftrightarrow \; \exists k \in \mathbb{Z}\; \vert \; y-x=2k \pi.$$

Th relation $\sim$ is an equivalence relation on $\mathbb{R}$ (the proof is very similar to the proof in example 3.11). The equivalence class of the real number $x_0$ is the set $\{ x_0+2k \pi, \; k \in \mathbb{Z}\}$, and any equivalence class contains a single element in the interval $[0, 2 \pi )$. Thus the unit circle in the plane is graphical representation of the quotient set: every point on the circle determines a single angle with the positive semi-$x$-axis, i.e. a single element of $[0, 2 \pi )$.

Example 4.3.11 (Congruences in $\mathbb{Z}$)   This example is very important, both in Algebra and in Number Theory. Let $n$ be a positive integer. We define a binary relation in $\mathbb{Z}$, called congruence modulo $n$ as follows:

$$\forall x \in \mathbb{Z}, \; \forall y \in \mathbb{Z}, \; x \eq... ... \; (\mod n) \Longleftrightarrow \exists k \in \mathbb{Z}\; \vert \; y-x = kn.$$

Congruence modulo $n$ is an equivalence relation on $\mathbb{Z}$:

• R: For any integer $x$, we have:

  $$x-x=0=0 \cdot n$$

  
  
  i.e. $x \equiv x \; (\mod n)$.
• S: For any integers $x$ and $y$, we have:

  $$x \equiv y \; (\mod n) \Longleftrightarrow \exists k \in \mathbb{Z}\; \vert \; y-x = kn$$

  
  
  It follows that $x-y=(-k)n$, thus $y \equiv x \; (\mod n)$.
• T: For any integers $x$, $y$ and $z$, we have:

  $$\begin{cases} x \equiv y \; (\mod n)\\ y \equiv z \; (\mod ... ...\\ \exists q \in \mathbb{Z}\; \vert \; z-y = qn \end{cases}$$

  
  
  It follows that $z-x=pn+qn=(p+q)n$, i.e. $x \equiv z \; (\mod n)$.

Let us describe the equivalence classes for various values of the positive integer $n$:

1. If $n=1$, we have:

   $$\forall x \in \mathbb{Z}, \forall y \in \mathbb{Z}, \; y-x=1 \cdot \underbrace{(y-x)}_{\in \mathbb{Z}}$$

   
   
   i.e. every integer is congruent to every integer modulo $1$. There is only one equivalence class modulo $1$ (therefore this congruence is not so interesting!).
2. If $n=2$, there are two equivalence classes: the one contains all the even numbers, the other one contains all the odd numbers.
3. If $n=3$, there are three equivalence classes, namely:

   $$[0] = \{ \dots, -6,-3,0,3,6,9, \dots \}$$

   $$[1] = \{ \dots, -5,-2,1,4,7,,10 \dots \}$$

   $$[2] = \{ \dots, -4,-1,2,5,8,11, \dots \}.$$

   
   

These examples are particular cases of a general result:

Theorem 4.3.12   Let $n$ be a positive integer. There are exactly $n$ congruence classes of integers modulo $n$.

Proof. Let us use the Euclidean Division (v.i. Proposition 2.18 in Chapter 6): for any $x \in \mathbb{Z}$, there exists a unique pair $(q,r)$, where $q \in \mathbb{Z}$, $0 \leq r < n$ and $x=nq+r$. The integer $q$ is called the quotient and $r$ is the remainder. We have: $x-r=qn$, i.e. $x \equiv r \mod n$. By transitivity, two integers are congruent modulo $n$ if, and only if, they have the same remainder in division by $n$. Therefore, the equivalence classes are completely determined by the integers $r$ verifying the double inequality $0 \leq r < n$, i.e. there are exactly $n$ equivalence classes. $\qedsymbol$

Returning to a general relation $\mathcal{R}$, for each $k \in \mathbb{N}$ we define

$$\mathcal{R}^{(k)} = \{ (a,b) : k a b \}.$$

$\mathcal{R}^{(1)} = \mathcal{R}$ and $\mathcal{R}^{(\infty)} = t(R)$, the transitive closure of $\mathcal{R}$. $\mathcal{R}^{(\infty)}$ is defined as $\bigcup_{i \ge 1} \mathcal{R}^{(i)}$.