Example 1
Question: Let \( A = \{1, 2, 3, 4, 5, 6\} \). Define a relation R on A by \( R = \{(a, b) : 3 \mid (a - b)\} \) (i.e., 3 divides \( a - b \)). Show that R is an equivalence relation. Also identify the equivalence classes and show that elements within each class are related to one another but no element of one class is related to any element of another class.
Solution: We check the three properties. Reflexivity: For any \( a \in A \), we have \( a - a = 0 \) and \( 3 \mid 0 \), so \( (a, a) \in R \). Hence R is reflexive. Symmetry: Suppose \( (a, b) \in R \). Then \( 3 \mid (a - b) \), so \( a - b = 3k \) for some integer \( k \). Then \( b - a = 3(-k) \), so \( 3 \mid (b - a) \), giving \( (b, a) \in R \). Hence R is symmetric. Transitivity: Suppose \( (a, b) \in R \) and \( (b, c) \in R \). Then \( a - b = 3k \) and \( b - c = 3m \) for integers \( k, m \). Adding: \( a - c = 3(k + m) \), so \( 3 \mid (a - c) \), giving \( (a, c) \in R \). Hence R is transitive. Since R is reflexive, symmetric, and transitive, R is an equivalence relation. Equivalence classes: We list the elements of A modulo 3. Class of 1: elements \( a \in A \) with \( 3 \mid (a - 1) \), i.e., \( a \equiv 1 \pmod{3} \): \( \{1, 4\} \). Class of 2: elements with \( a \equiv 2 \pmod{3} \): \( \{2, 5\} \). Class of 3: elements with \( a \equiv 0 \pmod{3} \): \( \{3, 6\} \). Within \( \{1, 4\} \): \( 4 - 1 = 3 \), so \( 3 \mid 3 \). Both \( (1,4) \) and \( (4,1) \) are in R. Similarly every pair in \( \{2, 5\} \) and \( \{3, 6\} \) satisfies the relation. Across classes: Take \( 1 \in \{1,4\} \) and \( 2 \in \{2,5\} \). Then \( 1 - 2 = -1 \) and \( 3 \nmid (-1) \), so \( (1,2) \notin R \). In general, if \( a \) and \( b \) belong to different classes they have different residues mod 3, so \( 3 \nmid (a - b) \) and \( (a, b) \notin R \). Hence no element of one class is related to any element of another class.
Answer: R is an equivalence relation. The three equivalence classes are \( \{1, 4\} \), \( \{2, 5\} \), and \( \{3, 6\} \). Elements within each class are mutually related; no element of one class is related to any element of a different class.
Example 2
Question: Let \( A = \{0, 1, 2, 3, 4, 5, 6, 7\} \). Define a relation R on A by \( R = \{(a, b) : 4 \mid (a - b)\} \). Show that R is an equivalence relation. Identify all equivalence classes and verify that elements within the same class are related to each other but no element of one class is related to any element of a different class.
Solution: We verify all three properties of an equivalence relation. Reflexivity: For any \( a \in A \), \( a - a = 0 \) and \( 4 \mid 0 \), so \( (a, a) \in R \) for every \( a \in A \). Hence R is reflexive. Symmetry: Let \( (a, b) \in R \). Then \( a - b = 4k \) for some integer \( k \). So \( b - a = 4(-k) \), which means \( 4 \mid (b - a) \), giving \( (b, a) \in R \). Hence R is symmetric. Transitivity: Let \( (a, b) \in R \) and \( (b, c) \in R \). Then \( a - b = 4k \) and \( b - c = 4m \) for integers \( k, m \). Adding these: \( a - c = 4(k + m) \), so \( 4 \mid (a - c) \), giving \( (a, c) \in R \). Hence R is transitive. Since R is reflexive, symmetric, and transitive, R is an equivalence relation. Equivalence classes (residues mod 4 within A): Class of 0: \( a \equiv 0 \pmod{4} \): \( \{0, 4\} \). Class of 1: \( a \equiv 1 \pmod{4} \): \( \{1, 5\} \). Class of 2: \( a \equiv 2 \pmod{4} \): \( \{2, 6\} \). Class of 3: \( a \equiv 3 \pmod{4} \): \( \{3, 7\} \). Verification within classes: In \( \{0, 4\} \): \( 4 - 0 = 4 \) and \( 4 \mid 4 \), so \( (0, 4) \in R \). Likewise for each pair in the other classes (e.g. \( 5 - 1 = 4 \), \( 6 - 2 = 4 \), \( 7 - 3 = 4 \)). All such pairs satisfy the relation. Verification across classes: Take \( 0 \in \{0, 4\} \) and \( 1 \in \{1, 5\} \). Then \( 0 - 1 = -1 \) and \( 4 \nmid (-1) \), so \( (0, 1) \notin R \). In general, elements from different classes have different residues mod 4, so their difference is never divisible by 4. Hence no element of one class is related to any element of another class. The four equivalence classes \( \{0,4\} \), \( \{1,5\} \), \( \{2,6\} \), \( \{3,7\} \) partition A completely, confirming the equivalence relation structure.
Answer: R is an equivalence relation. The four equivalence classes are \( \{0, 4\} \), \( \{1, 5\} \), \( \{2, 6\} \), and \( \{3, 7\} \). Elements within the same class are mutually related, while no element of one class is related to any element of a different class.