Relations
1 Properties of relations
Example 1 (Reflexive and non-reflexive relations on the real numbers) On \(\mathbb{R}\), the relation \(=\) is reflexive, since \(a = a\) for every real number \(a\). The relation \(\le\) is also reflexive, since \(a \le a\) for every real number \(a\). The relation \(<\) is not reflexive, since \(2 < 2\) is false.
2 Equivalence relations
Example 3 (Integers with an even difference) On the integers, define the relation \(\sim\) by \(a \sim b\) when \(a - b\) is even. For example, \(7 \sim 3\), since \(7 - 3 = 4 = 2 \cdot 2\), but \(7 \not\sim 4\), since \(7 - 4 = 3\) is odd. The relation \(\sim\) is an equivalence relation.
Reflexive. For every integer \(a\), \(a - a = 0 = 2 \cdot 0\), so \(a \sim a\).
Symmetric. Suppose \(a \sim b\), so \(a - b = 2k\) for some integer \(k\). Then
\[ \begin{aligned} b - a &= -(a - b) && \text{(negate the difference)} \\ &= -2k && \text{(} a - b = 2k \text{)} \\ &= 2(-k), && \text{(factor out } 2 \text{)} \end{aligned} \]
and \(-k\) is an integer, so \(b \sim a\).
Transitive. Suppose \(a \sim b\) and \(b \sim c\), so \(a - b = 2j\) and \(b - c = 2k\) for some integers \(j\) and \(k\). Then
\[ \begin{aligned} a - c &= (a - b) + (b - c) && \text{(the } b \text{ terms cancel)} \\ &= 2j + 2k && \text{(} a - b = 2j \text{ and } b - c = 2k \text{)} \\ &= 2(j + k), && \text{(distributive law)} \end{aligned} \]
and \(j + k\) is an integer, so \(a \sim c\).
Definition 4 (Equivalence class) Let \(\sim\) be an equivalence relation on a set \(S\), and let \(a \in S\). The equivalence class [4] of \(a\) is the set of elements of \(S\) related to \(a\):
\[ [a] \stackrel{\text{def}}{=}{\mathopen{}\left\{b \in S : b \sim a\right\}\mathclose{}}. \]
Example 4 (Equivalence classes of integers with an even difference) Let \(\sim\) be the equivalence relation of Example 3 on the integers. The equivalence class \([0]\) holds the integers \(b\) with \(b - 0\) even, which are the even integers: \([0] = \mathopen{}\left\{\ldots, -4, -2, 0, 2, 4, \ldots\right\}\mathclose{}\). The class \([1]\) holds the integers \(b\) with \(b - 1\) even, which are the odd integers: \([1] = \mathopen{}\left\{\ldots, -3, -1, 1, 3, 5, \ldots\right\}\mathclose{}\). The class \([2]\) is the same set as \([0]\), since \(2 \sim 0\).