Example 1
Question: Let X be a non-empty set and P(X) be its power set. Define a relation R on P(X) by: for subsets A, B in P(X), ARB if and only if A and B are disjoint, i.e., \( A \cap B = \emptyset \). Determine whether R is an equivalence relation on P(X). Justify your answer.
Solution: We check the three properties — reflexivity, symmetry, and transitivity — for R defined by \( A \cap B = \emptyset \). Step 1: Reflexivity For any subset A in P(X), we ask whether ARA holds, i.e., whether \( A \cap A = \emptyset \). Now \( A \cap A = A \), so the condition \( A \cap A = \emptyset \) holds only if \( A = \emptyset \). If we take any non-empty subset A of X, then \( A \cap A = A \ne \emptyset \), so ARА does NOT hold. Therefore R is NOT reflexive. Step 2: Symmetry Suppose ARB, i.e., \( A \cap B = \emptyset \). Since intersection is commutative, \( B \cap A = A \cap B = \emptyset \), which means BRA also holds. Therefore R IS symmetric. Step 3: Transitivity We look for a counterexample. Let \( X = \{1, 2, 3\} \). Take \( A = \{1\} \), \( B = \{2\} \), \( C = \{1, 3\} \). Check ARB: \( A \cap B = \{1\} \cap \{2\} = \emptyset \), so ARB holds. Check BRC: \( B \cap C = \{2\} \cap \{1, 3\} = \emptyset \), so BRC holds. Check ARC: \( A \cap C = \{1\} \cap \{1, 3\} = \{1\} \ne \emptyset \), so ARC does NOT hold. Therefore R is NOT transitive. Conclusion: Since R is neither reflexive nor transitive (even though it is symmetric), R is NOT an equivalence relation on P(X).
Answer: R is NOT an equivalence relation on P(X) because it fails reflexivity (any non-empty set A satisfies \( A \cap A \ne \emptyset \)) and transitivity (as shown by the counterexample).
Example 2
Question: Let \( X = \{1, 2, 3\} \) and P(X) be its power set. Define a relation R on P(X) by: for subsets A, B in P(X), ARB if and only if \( |A| = |B| \) (i.e., A and B have the same number of elements). Is R an equivalence relation on P(X)? Justify your answer.
Solution: We verify reflexivity, symmetry, and transitivity for R defined by \( |A| = |B| \). Step 1: Reflexivity For any subset A in P(X), we have \( |A| = |A| \), which is always true. Hence ARА holds for every A in P(X). Therefore R is reflexive. Step 2: Symmetry Suppose ARB, i.e., \( |A| = |B| \). Then trivially \( |B| = |A| \), so BRA also holds. Therefore R is symmetric. Step 3: Transitivity Suppose ARB and BRC, i.e., \( |A| = |B| \) and \( |B| = |C| \). From these two equalities it follows directly that \( |A| = |C| \), so ARC holds. Therefore R is transitive. Verification with P(X) for \( X = \{1,2,3\} \): P(X) contains the subsets: \( \emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\} \) with cardinalities 0, 1, 1, 1, 2, 2, 2, 3 respectively. For example, \( \{1\} R \{2\} \) because \( |\{1\}| = |\{2\}| = 1 \); \( \{1,2\} R \{1,3\} \) because both have cardinality 2. One can check all three properties hold throughout. Conclusion: Since R is reflexive, symmetric, and transitive, R IS an equivalence relation on P(X). The equivalence classes under R are: Class of \( \emptyset \): \( \{ \emptyset \} \) (cardinality 0). Class of \( \{1\} \): \( \{ \{1\}, \{2\}, \{3\} \} \) (cardinality 1). Class of \( \{1,2\} \): \( \{ \{1,2\}, \{1,3\}, \{2,3\} \} \) (cardinality 2). Class of \( \{1,2,3\} \): \( \{ \{1,2,3\} \} \) (cardinality 3).
Answer: R IS an equivalence relation on P(X) because it is reflexive (\( |A| = |A| \) always), symmetric (\( |A| = |B| \Rightarrow |B| = |A| \)), and transitive (\( |A| = |B| \) and \( |B| = |C| \Rightarrow |A| = |C| \)).