Show that the number of equivalence relation in the set \(\{1, 2, 3\}\) containing \((1,2)\) and \((2,1)\) is two.
CBSE Class 12 Maths · Relations and Functions
CBSE Class 12 Maths · Relations and Functions
Imagine three friends: 1, 2, and 3. We want to make a "buddy list" where 1 and 2 are already listed as buddies. Every person must be their own buddy too. We check: can 3 be left out of the buddy group, or must 3 join? It turns out 3 can stay separate, giving one buddy list. Or 3 can join everyone, giving a second buddy list. No other arrangements work without breaking the rules. So there are exactly two valid buddy lists possible.
Answer: The only equivalence relations on \( \{1,2,3\} \) containing \( (1,2) \) and \( (2,1) \) are \[ R_1 = \{(1,1),(2,2),(3,3),(1,2),(2,1)\} \] and \[ R_2 = \{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)\}. \] Therefore the number of such equivalence relations is exactly two.
A relation \( R \) on a set \( A \) is called an equivalence relation if it satisfies three properties. It is reflexive, meaning \( (a,a) \in R \) for every \( a \in A \). It is symmetric, meaning if \( (a,b) \in R \) then \( (b,a) \in R \). It is transitive, meaning if \( (a,b) \in R \) and \( (b,c) \in R \) then \( (a,c) \in R \). Here the set is \( A = \{1,2,3\} \), and we are told the relation must contain the pairs \( (1,2) \) and \( (2,1) \). Our job is to build every possible equivalence relation obeying these conditions and show there are exactly two of them.
An equivalence relation \( R \) on \( A \) must satisfy: reflexive \( (a,a) \in R \ \forall a \in A \); symmetric \( (a,b) \in R \Rightarrow (b,a) \in R \); transitive \( (a,b),(b,c) \in R \Rightarrow (a,c) \in R \).
The only equivalence relations on \( \{1,2,3\} \) containing \( (1,2) \) and \( (2,1) \) are \[ R_1 = \{(1,1),(2,2),(3,3),(1,2),(2,1)\} \] and \[ R_2 = \{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)\}. \] Therefore the number of such equivalence relations is exactly two.
A common mistake is adding a single pair like \( (1,3) \) without its symmetric partner \( (3,1) \), or forgetting that transitivity then forces even more pairs. Students often think many relations are possible, but symmetry and transitivity together lock the answer to just two.
The only equivalence relations on \( \{1,2,3\} \) containing \( (1,2) \) and \( (2,1) \) are \[ R_1 = \{(1,1),(2,2),(3,3),(1,2),(2,1)\} \] and \[ R_2 = \{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)\}. \] Therefore the number of such equivalence relations is exactly two.
One common mistake: students forget to check transitivity for chains involving the newly added pairs — for example, after adding \( (1,2) \) and \( (2,1) \), they overlook that \( (1,2) \) followed by \( (2,1) \) requires \( (1,1) \) to already be present, and incorrectly declare a relation transitive without verifying every applicable chain.
Answer: The only equivalence relations on \( \{1,2,3\} \) containing \( (1,2) \) and \( (2,1) \) are \[ R_1 = \{(1,1),(2,2),(3,3),(1,2),(2,1)\} \] and \[ R_2 = \{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)\}. \] Therefore the number of such equivalence relations is exactly two.
Question: Find the number of equivalence relations on the set \( A = \{1, 2, 3, 4\} \) that contain the pairs \( (1, 2) \) and \( (2, 1) \). List all such relations.
Solution: We need every equivalence relation R on \( A = \{1, 2, 3, 4\} \) that must contain \( (1,2) \) and \( (2,1) \). Step 1: Identify the mandatory pairs. Since R must be reflexive, it must contain \( (1,1), (2,2), (3,3), (4,4) \). Since \( (1,2) \in R \) and \( (2,1) \in R \) are given, reflexive pairs are also required. So the minimum required set is: \[ R_0 = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1)\} \] Step 2: Check that \( R_0 \) is an equivalence relation. Reflexive: all diagonal pairs are present. Symmetric: \( (1,2) \) and \( (2,1) \) are both present, all others are self-pairs. Transitive: \( (1,2),(2,1) \Rightarrow (1,1) \) ✓; \( (2,1),(1,2) \Rightarrow (2,2) \) ✓. No violations. So \( R_0 \) is a valid equivalence relation. This corresponds to the partition \( \{\{1,2\},\{3\},\{4\}\} \). Step 3: Explore enlargements by adding elements 3 and/or 4 to the equivalence class of 1 and 2. Case A: Merge 3 into the class \( \{1,2\} \), keeping 4 separate. The equivalence class becomes \( \{1,2,3\} \) and \( \{4\} \). We must add all pairs from \( \{1,2,3\} \times \{1,2,3\} \): \[ R_1 = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(1,3),(3,1),(2,3),(3,2)\} \] This satisfies reflexivity, symmetry, and transitivity. Valid. Case B: Merge 4 into the class \( \{1,2\} \), keeping 3 separate. The equivalence class becomes \( \{1,2,4\} \) and \( \{3\} \). We must add all pairs from \( \{1,2,4\} \times \{1,2,4\} \): \[ R_2 = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(1,4),(4,1),(2,4),(4,2)\} \] Valid. Case C: Merge both 3 and 4 into the class of \( \{1,2\} \). The single class is \( \{1,2,3,4\} \), giving: \[ R_3 = A \times A \] (all 16 pairs). Valid. Case D: Keep 3 and 4 in separate classes from \( \{1,2\} \), but merge 3 and 4 together. Classes would be \( \{1,2\} \) and \( \{3,4\} \). We must add \( (3,4) \) and \( (4,3) \): \[ R_4 = \{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(3,4),(4,3)\} \] Check transitivity: \( (1,2),(2,1) \Rightarrow (1,1) \) ✓; \( (3,4),(4,3) \Rightarrow (3,3) \) ✓. No cross-class issues. Valid. Step 4: Are there any other cases? All possible partitions of \( \{1,2,3,4\} \) that keep 1 and 2 in the same block have been enumerated: - \( \{\{1,2\},\{3\},\{4\}\} \to R_0 \) - \( \{\{1,2,3\},\{4\}\} \to R_1 \) - \( \{\{1,2,4\},\{3\}\} \to R_2 \) - \( \{\{1,2,3,4\}\} \to R_3 \) - \( \{\{1,2\},\{3,4\}\} \to R_4 \) No other partitions keep 1 and 2 together. Therefore there are exactly 5 equivalence relations.
Answer: There are 5 equivalence relations on \( \{1,2,3,4\} \) containing \( (1,2) \) and \( (2,1) \).
Question: Show that the number of equivalence relations on the set \( B = \{a, b, c\} \) that contain the pair \( (a, c) \) is exactly two. List both relations explicitly.
Solution: We need every equivalence relation R on \( B = \{a, b, c\} \) that contains \( (a, c) \). Step 1: Identify mandatory pairs. Since R is reflexive, it must contain: \[ (a,a),\ (b,b),\ (c,c) \] Since \( (a,c) \in R \) and R is symmetric, we also need: \[ (c,a) \in R \] So the minimum base set is: \[ R_0 = \{(a,a),(b,b),(c,c),(a,c),(c,a)\} \] Step 2: Verify \( R_0 \) is an equivalence relation. Reflexive: \( (a,a),(b,b),(c,c) \) all present. ✓ Symmetric: \( (a,c) \) and \( (c,a) \) both present; self-pairs are trivially symmetric. ✓ Transitive: Check all compositions. \( (a,c),(c,a) \Rightarrow (a,a) \) ✓ \( (c,a),(a,c) \Rightarrow (c,c) \) ✓ No pair involving \( b \) with \( a \) or \( c \) exists, so no new pairs needed. ✓ Thus \( R_0 \) is valid. It corresponds to the partition \( \{\{a,c\},\{b\}\} \). Step 3: Explore larger equivalence relations. We can extend \( R_0 \) only by merging \( b \) into the class \( \{a,c\} \), giving the single class \( \{a,b,c\} \). This forces us to add all remaining pairs: \[ R_1 = B \times B = \{(a,a),(b,b),(c,c),(a,b),(b,a),(a,c),(c,a),(b,c),(c,b)\} \] Check: Reflexive: all diagonal pairs present. ✓ Symmetric: for every \( (x,y) \), \( (y,x) \) is also present. ✓ Transitive: since every element is related to every other, transitivity holds trivially. ✓ So \( R_1 \) is valid. It corresponds to the partition \( \{\{a,b,c\}\} \). Step 4: Check if any other partition is possible. The only partitions of \( B \) that keep \( a \) and \( c \) in the same block are: - \( \{\{a,c\},\{b\}\} \to R_0 \) - \( \{\{a,b,c\}\} \to R_1 \) We cannot separate \( a \) and \( c \) into different blocks since \( (a,c) \) is required. No other partitions exist. Therefore, the number of equivalence relations on \( \{a, b, c\} \) containing \( (a,c) \) is exactly two: \[ R_0 = \{(a,a),(b,b),(c,c),(a,c),(c,a)\} \] and \[ R_1 = B \times B \]
Answer: There are exactly 2 equivalence relations on \( \{a, b, c\} \) containing \( (a, c) \): one corresponding to the partition \( \{\{a,c\},\{b\}\} \) and one being \( B \times B \).
Question: Find the number of equivalence relations on the set \( A = \\{1, 2, 3, 4\\} \) that contain the pairs \( (1, 2) \) and \( (2, 1) \) but do NOT contain \( (3, 4) \) or \( (4, 3) \). List all such equivalence relations.
Answer: There are exactly 3 equivalence relations on \( \\{1,2,3,4\\} \) containing \( (1,2) \) and \( (2,1) \) but not containing \( (3,4) \) or \( (4,3) \). They are: \[ R_1 = \\{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1)\\}, \] \[ R_2 = \\{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(1,3),(3,1),(2,3),(3,2)\\}, \] \[ R_3 = \\{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(1,4),(4,1),(2,4),(4,2)\\}. \]