Section 1.1 & 1.2: Types of Relations

Example
Show that the relation \(R\) in the set \(\mathbb{Z}\) of integers given by
\[ R = \{(a, b) : 2 \text{ divides } a - b\} \]
is an equivalence relation.

In the last example, note that all even integers are related to zero, as \((0, \pm 2), (0, \pm 4)\) etc., lie in \(R\) and no odd integer is related to \(0\), as \((0, \pm 1), (0, \pm 3)\) etc., do not lie in \(R\). Similarly, all odd integers are related to one and no even integer is related to one. Therefore, the set \(E\) of all even integers and the set \(O\) of all odd integers are subsets of \(\mathbb{Z}\) satisfying following conditions:

1. All elements of \(E\) are related to each other and all elements of \(O\) are related to each other.

2. No element of \(E\) is related to any element of \(O\) and vice-versa.

3. \(E\) and \(O\) are disjoint and \(\mathbb{Z} = E \cup O\).

The subset \(E\) is called the equivalence class containing zero and is denoted by \([0]\). Similarly, \(O\) is the equivalence class containing \(1\) and is denoted by \([1]\). Note that \[ [0] \ne [1],\quad [0] = [2r] \text{ and } [1] = [2r+1],\ r \in \mathbb{Z}. \] In fact, what we have seen above is true for an arbitrary equivalence relation \(R\) in a set \(X\). Given an arbitrary equivalence relation \(R\) in an arbitrary set \(X\), \(R\) divides \(X\) into mutually disjoint subsets \(A_i\) called partitions or subdivisions of \(X\) satisfying:

1. All elements of \(A_i\) are related to each other, for all \(i\).

2. No element of \(A_i\) is related to any element of \(A_j\), \(i \ne j\).

3. \(\bigcup A_i = X\) and \(A_i \cap A_j = \emptyset,\ i \ne j\).

The subsets \(A_i\) are called equivalence classes. The interesting part of the situation is that we can go reverse also. For example, consider a subdivision of the set \(\mathbb{Z}\) given by three mutually disjoint subsets \(A_1, A_2\) and \(A_3\) whose union is \(\mathbb{Z}\) with

\[ \begin{aligned} A_1 &= \{x \in \mathbb{Z} : x \text{ is a multiple of } 3\} = \{\ldots, -6, -3, 0, 3, 6, \ldots\} \\ A_2 &= \{x \in \mathbb{Z} : x-1 \text{ is a multiple of } 3\} = \{\ldots, -5, -2, 1, 4, 7, \ldots\} \\ A_3 &= \{x \in \mathbb{Z} : x-2 \text{ is a multiple of } 3\} = \{\ldots, -4, -1, 2, 5, 8, \ldots\} \end{aligned} \]

Define a relation \(R\) in \(\mathbb{Z}\) given by \(R = \{(a, b) : 3 \text{ divides } a - b\}\). Following the arguments similar to those used in Example 5, we can show that \(R\) is an equivalence relation. Also, \(A_1\) coincides with the set of all integers in \(\mathbb{Z}\) which are related to \(0\), \(A_2\) coincides with the set of all integers which are related to \(1\) and \(A_3\) coincides with the set of all integers in \(\mathbb{Z}\) which are related to \(2\). Thus, \(A_1 = [0]\), \(A_2 = [1]\) and \(A_3 = [2]\). In fact, \[ A_i = [3r + i],\ A_2 = [3r + 1] \text{ and } A_3 = [3r + 2],\ \text{for all } r \in \mathbb{Z}. \]

Example

Let \(R\) be the relation defined in the set \(A = \{1, 2, 3, 4, 5, 6, 7\}\) by \(R = \{(a, b) : \text{both } a \text{ and } b \text{ are either odd or even}\}\). Show that \(R\) is an equivalence relation. Further, show that all the elements of the subset \(\{1, 3, 5, 7\}\) are related to each other and all the elements of the subset \(\{2, 4, 6\}\) are related to each other, but no element of the subset \(\{1, 3, 5, 7\}\) is related to any element of the subset \(\{2, 4, 6\}\).

Solution

Given any element \(a\) in \(A\), both \(a\) and \(a\) must be either odd or even, so that \((a, a) \in R\). Further, \((a, b) \in R \Rightarrow\) both \(a\) and \(b\) must be either odd or even \(\Rightarrow (b, a) \in R\). Similarly, \((a, b) \in R\) and \((b, c) \in R \Rightarrow\) all elements \(a, b, c\) must be either even or odd simultaneously \(\Rightarrow (a, c) \in R\). Hence, \(R\) is an equivalence relation.

Further, all the elements of \(\{1, 3, 5, 7\}\) are related to each other, as all the elements of this subset are odd. Similarly, all the elements of the subset \(\{2, 4, 6\}\) are related to each other, as all of them are even. Also, no element of the subset \(\{1, 3, 5, 7\}\) can be related to any element of \(\{2, 4, 6\}\), as elements of \(\{1, 3, 5, 7\}\) are odd, while elements of \(\{2, 4, 6\}\) are even.