Equivalence relation

Naive set theory: Relations

Equivalence relation

Equivalence Relation

Equivalence Relation

An equivalence relation on a set is a binary relation that is reflexive, symmetric, and transitive.

In most cases, we denote the relation with the $\boldsymbol{\sim}$ symbol and sometimes with the $\boldsymbol{\equiv}$ symbol.

Thus, for a set $X$ , $\sim$ is an equivalence relation on $X$ if

For every $x\in X$ : $x\sim x$ ;
For all $x,y\in X$ : if $x\sim y$ , then $y\sim x$ ;
For all $x,y,z\in X$ : if $x\sim y$ and $y\sim z$ , then $x\sim z$ .

Examples

Equality on a certain set

Similarity of triangles

Parallelism or equality of lines in the plane

Congruence of integers modulo a fixed chosen natural number $m$ defined by $a\equiv b\; (\mathrm{mod\;}m)$ if and only if $a-b$ is divisible by $m$ .

The relation on $\mathbb{Z}\times \bigl(\mathbb{N}\backslash\{0\}\bigr)$ defined by $(p,q)\sim(r,s)$ if and only if $p\cdot s=r\cdot q$ . If you think of $(p,q)$ as the quotient $p/q$ , then the equivalence relation is a way to identify fractions with the same numerical value.

Equivalence Class

Equivalence Class

Given an equivalence relation $\sim$ on a set $X$ , we define the equivalence class $E_x$ of an element $x\in X$ as the set $E_x=\{y\in X\mid x\sim y\}$ .

Other common notations for the equivalence class of $x\in X$ with respect to the equivalence relation $\sim$ are $[x]_{\sim}$ (or simply $[x]$ ) and $x/{\sim}$ .

Examples

We consider the equivalence relation on $\mathbb{R}$ defined by $x\sim y$ if and only if $x-y\in \mathbb{Z}$ . Then: $E_0=\{x\mid x-0\in \mathbb{Z}\} =\mathbb{Z}$ , $E_{\pi}=\{x\mid x-\pi\in \mathbb{Z}\}=\{\pi+k\mid k\in \mathbb{Z}\}$ .

We consider the equivalence relation on $\mathbb{N}$ defined by $x\sim y$ if and only if $x+y$ is even. Then there are 2 equivalence classes: $E_0=\{0,2,4,\ldots\}$ and $E_1=\{1,3,5,\ldots\}$ .

We consider the equivalence relation on $\mathbb{N}$ defined by $x\sim y$ if and only if $x-y$ is a multiple of 3. Then there are 3 equivalence classes: $E_0=\{0,3,6,\ldots\}$ , $E_1=\{1,4,7,\ldots\}$ , and $E_2=\{2,5,8,\ldots\}$ .

Let $\sim$ be an equivalence relation on a non-empty set $X$ . For every $x,y\in X$ for which $E_x\cap E_y\neq \emptyset$ , it holds that $E_x=E_y$ . A direct consequence is that

Let $z\in E_x$ , i.e., $x\sim z$ . Since $E_x\cap E_y\neq \emptyset$ , there exists a $w\in E_x\cap E_y$ . Since $w\in E_x$ , it follows that $x\sim w$ . Since $w\in E_y$ , it follows that $y\sim w$ . Since an equivalence relation is symmetric, it follows that $w\sim x$ and $w\sim y$ . Since an equivalence relation is transitive, from $y\sim w$ , $w\sim x$ , and $x\sim z$ , it follows that $y\sim z$ and thus $z\in E_y$ . Conclusion: $E_x\subset E_y$ . Similarly, we can show that $E_y\subset E_x$ . Therefore, $E_x=E_y$ .

Partition of a non-empty set

Partition

A partition of a nonempty set $X$ is a set $\mathcal{A}$ of subsets of $X$ satisfying the following three conditions:

every set $A\in \mathcal{A}$ is non-empty;
$\cup_{A\in \mathcal{A}}A = X$ ;
For all $A,B\in\mathcal{A}$ : if $A\cap B\neq \emptyset$ , then $A=B$ .

Examples

$\mathcal{A}=\bigl\{\mathbb{Z}^{-},\{0\},\mathbb{Z}^{+}\bigr\}$ is a partition of $\mathbb{Z}$ .

Using interval notation:
$\mathcal{A}=\bigl\{[n,n+1) \mid n\in \mathbb{Z}\bigr\}$ is a partition of $\mathbb{R}$ .

Suppose that $\sim$ is an equivalence relation on a nonempty set $X$ . Then the indexed set $\{E_x\mid x\in X\}$ is a partition of $X$ . This is also called the quotient set $X/\!\sim$ of $X$ with respect to $\sim$ .

Conversely, if $\mathcal{A}$ is a partition of a nonempty set $X$ and we define for $x,y\in X$ the relation $x\sim y$ if and only if $x,y\in A$ for some $A\in \mathcal{A}$ , then $\sim$ is an equivalence relation on $X$ .

The proof boils down to examining the three properties of a partition.

Because an equivalence relation is reflexive, $x\sim x$ for each $x\in X$ . Therefore, $x\in E_x$ and $E_x\neq \emptyset$ for each $x\in X$ .
Suppose $x\in X$ , then $x\in E_x$ . From this it follows: $X\subset\cup_{y\in X}E_y$ . The inverse inclusion $\cup_{y\in X}E_y\subset X$ follows from the fact that $E_y\subset X$ for each $y\in X$ . Thus: $X=\cup_{y\in X}E_y$ .
Let $x,y\in X$ be such that $E_x\cap E_y\neq \emptyset$ , then $E_x=E_y$ because according to the above statement $\{E_x\mid x\in X\}$ is a partition on $X$ .

In $X=\{1,2,3,4\}$ we define the equivalence relation $\sim$ by $1\sim 1,\quad 2\sim 2,\quad 3\sim 3,\quad 4\sim 4,\quad 1\sim 3,\quad 3\sim 1\text.$ Then we have the following equivalence classes $[1] = \{1,3\},\quad [2] = \{2\},\quad [3] = \{1,3\},\quad [4] = \{4\}\text.$ Note that $[1] = [3]$ .

$X/\!\sim\; = \bigl\{[1], [2], [4]\bigr\}$ is a partition of $X$ and so this is the quotient set $X/\!\sim$ .
We could also have used $\bigl\{[2], [3], [4]\bigr\}$ ; it doesn't matter.

We define the equivalence relation on $\mathbb{Z}$ by $m\sim n\text{ if and only if }m-n\text{ deelbaar is door }3\text.$ Then we have the following equivalence classes $\begin{aligned}\; [0] &= \{\ldots, -6, -3, 0, 3, 6, \ldots\},\\[0.25cm] [1] &= \{\ldots, -5, -2, 1, 4, 7, \ldots\},\\[0.25cm] [2] &= \{\ldots, -4, -1, 2, 5, 7, \ldots\}\end{aligned}$ $\mathbb{Z}/\!\sim\;= \bigl\{[0], [1], [2]\bigr\}$ is a partition of $\mathbb{Z}$ and so this is the quotient set $\mathbb{Z}/\!\sim$ .
In mathematics, this set is usually denoted as $\mathbb{Z}_3$ .