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}\).

Quotient set of an equivalence relation 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\).

Example 1 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.

Example 2 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\).