Example 1
Question: Let \( X = \{1, 2, 3, 4, 5, 6, 7, 8\} \). Let \( R_1 \) be a relation on \( X \) defined by \( R_1 = \{(x, y) : x - y \text{ is divisible by } 4\} \) and let \( R_2 \) be another relation on \( X \) defined by \( R_2 = \{(x, y) : \{x, y\} \subseteq \{1, 5\} \text{ or } \{x, y\} \subseteq \{2, 6\} \text{ or } \{x, y\} \subseteq \{3, 7\} \text{ or } \{x, y\} \subseteq \{4, 8\}\} \). Show that \( R_1 = R_2 \).
Solution: We will show \( R_1 \subseteq R_2 \) and \( R_2 \subseteq R_1 \). First, note that divisibility by 4 partitions \( X = \{1,2,3,4,5,6,7,8\} \) into residue classes modulo 4. The residue classes are: Residue 1: \( \{1, 5\} \) (since \( 1 \equiv 1 \pmod{4} \) and \( 5 \equiv 1 \pmod{4} \)) Residue 2: \( \{2, 6\} \) (since \( 2 \equiv 2 \pmod{4} \) and \( 6 \equiv 2 \pmod{4} \)) Residue 3: \( \{3, 7\} \) (since \( 3 \equiv 3 \pmod{4} \) and \( 7 \equiv 3 \pmod{4} \)) Residue 0: \( \{4, 8\} \) (since \( 4 \equiv 0 \pmod{4} \) and \( 8 \equiv 0 \pmod{4} \)) Proof that \( R_1 \subseteq R_2 \): Let \( (x, y) \in R_1 \). Then \( 4 \mid (x - y) \), which means \( x \equiv y \pmod{4} \). So \( x \) and \( y \) belong to the same residue class modulo 4. Examining the four classes above: If \( x \equiv y \equiv 1 \pmod{4} \), then \( \{x, y\} \subseteq \{1, 5\} \), so \( (x, y) \in R_2 \). If \( x \equiv y \equiv 2 \pmod{4} \), then \( \{x, y\} \subseteq \{2, 6\} \), so \( (x, y) \in R_2 \). If \( x \equiv y \equiv 3 \pmod{4} \), then \( \{x, y\} \subseteq \{3, 7\} \), so \( (x, y) \in R_2 \). If \( x \equiv y \equiv 0 \pmod{4} \), then \( \{x, y\} \subseteq \{4, 8\} \), so \( (x, y) \in R_2 \). In every case \( (x, y) \in R_2 \), hence \( R_1 \subseteq R_2 \). Proof that \( R_2 \subseteq R_1 \): Let \( (x, y) \in R_2 \). Then \( \{x, y\} \) is contained in one of the four subsets listed in the definition of \( R_2 \). Case 1: \( \{x, y\} \subseteq \{1, 5\} \). Then \( x, y \in \{1, 5\} \), so \( x - y \in \{0, 4, -4\} \), each divisible by 4. Hence \( (x, y) \in R_1 \). Case 2: \( \{x, y\} \subseteq \{2, 6\} \). Then \( x - y \in \{0, 4, -4\} \), divisible by 4. Hence \( (x, y) \in R_1 \). Case 3: \( \{x, y\} \subseteq \{3, 7\} \). Then \( x - y \in \{0, 4, -4\} \), divisible by 4. Hence \( (x, y) \in R_1 \). Case 4: \( \{x, y\} \subseteq \{4, 8\} \). Then \( x - y \in \{0, 4, -4\} \), divisible by 4. Hence \( (x, y) \in R_1 \). In every case \( (x, y) \in R_1 \), hence \( R_2 \subseteq R_1 \). Since \( R_1 \subseteq R_2 \) and \( R_2 \subseteq R_1 \), we conclude \( R_1 = R_2 \).
Answer: R1 = R2, since both relations group elements of X into the same four equivalence classes: {1,5}, {2,6}, {3,7}, and {4,8}, determined by congruence modulo 4.
Example 2
Question: Let \( Y = \{1, 2, 3, 4, 5, 6\} \). Define a relation \( R_1 \) on \( Y \) by \( R_1 = \{(x, y) : x - y \text{ is divisible by } 2\} \) and another relation \( R_2 \) on \( Y \) by \( R_2 = \{(x, y) : \{x, y\} \subseteq \{1, 3, 5\} \text{ or } \{x, y\} \subseteq \{2, 4, 6\}\} \). Show that \( R_1 = R_2 \).
Solution: We will show \( R_1 \subseteq R_2 \) and \( R_2 \subseteq R_1 \). Observe that divisibility by 2 partitions \( Y = \{1, 2, 3, 4, 5, 6\} \) into two residue classes modulo 2: Odd (residue 1): \( \{1, 3, 5\} \) Even (residue 0): \( \{2, 4, 6\} \) Proof that \( R_1 \subseteq R_2 \): Let \( (x, y) \in R_1 \). Then \( 2 \mid (x - y) \), so \( x \equiv y \pmod{2} \). This means \( x \) and \( y \) have the same parity. If both are odd, then \( x, y \in \{1, 3, 5\} \), so \( \{x, y\} \subseteq \{1, 3, 5\} \) and \( (x, y) \in R_2 \). If both are even, then \( x, y \in \{2, 4, 6\} \), so \( \{x, y\} \subseteq \{2, 4, 6\} \) and \( (x, y) \in R_2 \). In both cases \( (x, y) \in R_2 \), so \( R_1 \subseteq R_2 \). Proof that \( R_2 \subseteq R_1 \): Let \( (x, y) \in R_2 \). Then \( \{x, y\} \) is contained in one of the two subsets listed. Case 1: \( \{x, y\} \subseteq \{1, 3, 5\} \). Both \( x \) and \( y \) are odd, so \( x - y \) is even, i.e., \( 2 \mid (x - y) \). For example, the possible differences are \( 1-1=0, 1-3=-2, 1-5=-4, 3-1=2, \) etc., all divisible by 2. Hence \( (x, y) \in R_1 \). Case 2: \( \{x, y\} \subseteq \{2, 4, 6\} \). Both \( x \) and \( y \) are even, so \( x - y \) is even. For example, \( 2-4=-2, 4-6=-2, 2-6=-4 \), all divisible by 2. Hence \( (x, y) \in R_1 \). In both cases \( (x, y) \in R_1 \), so \( R_2 \subseteq R_1 \). Since \( R_1 \subseteq R_2 \) and \( R_2 \subseteq R_1 \), we conclude \( R_1 = R_2 \).
Answer: R1 = R2, since both relations partition Y into exactly the same two equivalence classes: the odd numbers {1,3,5} and the even numbers {2,4,6}, corresponding to congruence modulo 2.