Example 1
Question: Let \ \( A = \{1, 2, 3, 4, 5, 6, 8, 9\} \). Define a relation R on A by \ \( R = \{(a, b) : a - b \text{ is divisible by } 3\} \). Show that R is an equivalence relation. Further, show that the elements of \ \( \{1, 4, 7\} \cap A = \{1, 4\} \), the elements of \ \( \{2, 5, 8\} \cap A = \{2, 5, 8\} \), and the elements of \ \( \{3, 6, 9\} \cap A = \{3, 6, 9\} \) are each mutually related within their own group, but no element from one group is related to any element from a different group.
Solution: We verify the three properties of an equivalence relation. Reflexivity: For any \ \( a \in A \), we have \ \( a - a = 0 \), and 0 is divisible by 3. Hence \ \( (a, a) \in R \) for all \ \( a \in A \). So R is reflexive. Symmetry: Let \ \( (a, b) \in R \). Then \ \( 3 \mid (a - b) \), which means \ \( a - b = 3k \) for some integer \ \( k \). Then \ \( b - a = 3(-k) \), so \ \( 3 \mid (b - a) \), giving \ \( (b, a) \in R \). So R is symmetric. Transitivity: Let \ \( (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 \). So R is transitive. Since R is reflexive, symmetric, and transitive, R is an equivalence relation. Now we identify the equivalence classes by remainder when divided by 3. Class 1 (remainder 1): \ \( \{1, 4\} \) — For any two elements \ \( a, b \) in this set, \ \( a - b \) is divisible by 3 (e.g., \ \( 4 - 1 = 3 \)), so all elements are mutually related. Class 2 (remainder 2): \ \( \{2, 5, 8\} \) — For any two elements \ \( a, b \) in this set, \ \( a - b \) is divisible by 3 (e.g., \ \( 8 - 2 = 6 \), \ \( 5 - 2 = 3 \)), so all elements are mutually related. Class 3 (remainder 0): \ \( \{3, 6, 9\} \) — For any two elements \ \( a, b \) in this set, \ \( a - b \) is divisible by 3 (e.g., \ \( 6 - 3 = 3 \), \ \( 9 - 3 = 6 \)), so all elements are mutually related. Cross-class check: Take \ \( a = 1 \) (Class 1) and \ \( b = 2 \) (Class 2). Then \ \( a - b = -1 \), which is not divisible by 3, so \ \( (1, 2) \notin R \). In general, if \ \( a \) and \ \( b \) belong to different classes, their remainders on division by 3 differ, so \ \( a - b \) is not divisible by 3, and hence \ \( (a, b) \notin R \). Thus no element of one class is related to any element of a different class.
Answer: R is an equivalence relation. The three equivalence classes are \( \{1, 4\} \), \( \{2, 5, 8\} \), and \( \{3, 6, 9\} \); elements within each class are mutually related, and no element from one class is related to any element from another class.
Example 2
Question: Let \ \( B = \{2, 4, 6, 8, 10, 12\} \). Define a relation R on B by \ \( R = \{(a, b) : \frac{a}{b} \text{ or } \frac{b}{a} \text{ is a power of } 2 \text{ (including } 2^0 = 1)\} \). Instead, consider the simpler relation: \ \( R = \{(a, b) : a + b \text{ is divisible by } 4\} \) on the set \ \( B = \{2, 4, 6, 8, 10, 12\} \). Show that R is an equivalence relation and identify the equivalence classes.
Solution: We check the three properties for R defined on \ \( B = \{2, 4, 6, 8, 10, 12\} \) by \ \( (a, b) \in R \) if and only if \ \( 4 \mid (a + b) \). Reflexivity: For any \ \( a \in B \), we need \ \( 4 \mid (a + a) = 2a \). The elements of B are all even, so \ \( a \in \{2, 4, 6, 8, 10, 12\} \). Check: \ \( 2a \in \{4, 8, 12, 16, 20, 24\} \). Each of these is divisible by 4. Hence \ \( (a, a) \in R \) for all \ \( a \in B \). R is reflexive. Symmetry: If \ \( (a, b) \in R \), then \ \( 4 \mid (a + b) \). Since \ \( a + b = b + a \), we also have \ \( 4 \mid (b + a) \), so \ \( (b, a) \in R \). 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: \ \( a + 2b + c = 4(k + m) \), so \ \( a + c = 4(k + m) - 2b \). For \ \( 4 \mid (a + c) \) we need \ \( 4 \mid 2b \), i.e., \ \( 2 \mid b \). Since all elements of B are even, \ \( b \) is even, so \ \( 2b \) is divisible by 4. Hence \ \( 4 \mid (a + c) \) and \ \( (a, c) \in R \). R is transitive. Since R is reflexive, symmetric, and transitive, R is an equivalence relation on B. Identifying equivalence classes by checking which pairs \ \( (a + b) \) are divisible by 4: For \ \( a = 2 \): \ \( 2 + 2 = 4 \checkmark \), \ \( 2 + 4 = 6 \) (no), \ \( 2 + 6 = 8 \checkmark \), \ \( 2 + 8 = 10 \) (no), \ \( 2 + 10 = 12 \checkmark \), \ \( 2 + 12 = 14 \) (no). So 2 is related to \ \( \{2, 6, 10\} \). For \ \( a = 4 \): \ \( 4 + 4 = 8 \checkmark \), \ \( 4 + 8 = 12 \checkmark \), \ \( 4 + 12 = 16 \checkmark \), others not divisible by 4. So 4 is related to \ \( \{4, 8, 12\} \). Thus the two equivalence classes are \ \( \{2, 6, 10\} \) and \ \( \{4, 8, 12\} \). Within \ \( \{2, 6, 10\} \): \ \( 2+6=8 \), \ \( 2+10=12 \), \ \( 6+10=16 \) — all divisible by 4, so all elements are mutually related. Within \ \( \{4, 8, 12\} \): \ \( 4+8=12 \), \ \( 4+12=16 \), \ \( 8+12=20 \) — all divisible by 4, so all elements are mutually related. Across classes: Take \ \( a = 2 \) and \ \( b = 4 \). Then \ \( a + b = 6 \), which is not divisible by 4, so \ \( (2, 4) \notin R \). In general, if \ \( a \in \{2, 6, 10\} \) and \ \( b \in \{4, 8, 12\} \), then \ \( a \equiv 2 \pmod{4} \) and \ \( b \equiv 0 \pmod{4} \), so \ \( a + b \equiv 2 \pmod{4} \), which is not divisible by 4. Hence no element of \ \( \{2, 6, 10\} \) is related to any element of \ \( \{4, 8, 12\} \).
Answer: R is an equivalence relation. The two equivalence classes are \( \{2, 6, 10\} \) and \( \{4, 8, 12\} \). Elements within each class are mutually related, and no element of one class is related to any element of the other class.