SOLVER7 Study. Nothing Else.
Chapter 1 Examples Q24

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

Solution

👶 Simple Explanation

Simple Explanation

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.

📖 Equivalence Relations on {1,2,3} Containing (1,2) and (2,1)

Detailed Explanation

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.

Formula Used

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 \).

Solution

  1. Step 1: Apply reflexivity. Since \( R \) is an equivalence relation on \( A = \{1,2,3\} \), it must contain \( (1,1) \), \( (2,2) \) and \( (3,3) \). So every valid relation certainly contains these three pairs.
  2. Step 2: Include the required given pairs. We are told \( R \) must contain \( (1,2) \) and \( (2,1) \). So far every allowed relation must contain at least \[ \{(1,1),(2,2),(3,3),(1,2),(2,1)\}. \]
  3. Step 3: Check the smallest possibility. Take \[ R_1 = \{(1,1),(2,2),(3,3),(1,2),(2,1)\}. \] It is reflexive. It is symmetric because \( (1,2) \) and \( (2,1) \) both appear. It is transitive: the only new chain is \( (1,2),(2,1) \Rightarrow (1,1) \) which is present, and \( (2,1),(1,2) \Rightarrow (2,2) \) which is present. So \( R_1 \) is a valid equivalence relation.
  4. Step 4: Try to add a pair linking 3 to something else. Suppose we add \( (2,3) \). Then symmetry forces \( (3,2) \). Now transitivity: \( (1,2),(2,3) \Rightarrow (1,3) \), and symmetry forces \( (3,1) \). This drags in every pair, giving the full relation \[ R_2 = A \times A = \{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)\}. \]
  5. Step 5: Confirm no in-between relation exists. Element 3 is either kept separate from 1 and 2 (giving \( R_1 \)) or linked to them. The moment 3 is linked to either 1 or 2, symmetry and transitivity force ALL pairs, giving \( R_2 \). A partial link (for example only \( (1,3) \) without \( (3,1) \)) breaks symmetry, so it is not allowed. Hence only two relations are possible.

Final 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.

Common Mistake

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.

🪜 Step-by-step Solution

Step-by-step Solution

  1. Step 1: Identify the base set and the mandatory pairs. We work on \( A = \{1,2,3\} \), and we are told the relation \( R \) must include \( (1,2) \) and \( (2,1) \). — Reason: These two pairs are given as a condition that every valid equivalence relation must satisfy, so they are a fixed starting point.
  2. Step 2: Add reflexive pairs. Because \( R \) must be reflexive, it must contain \( (1,1) \), \( (2,2) \), and \( (3,3) \). Combining with the given pairs, every valid \( R \) must contain at least \[ \{(1,1),(2,2),(3,3),(1,2),(2,1)\}. \] — Reason: Reflexivity requires \( (a,a) \in R \) for every element \( a \) in \( A \); there is no flexibility here.
  3. Step 3: Verify the smallest candidate. Let \[ R_1 = \{(1,1),(2,2),(3,3),(1,2),(2,1)\}. \] Check reflexivity: \( (1,1),(2,2),(3,3) \in R_1 \). Check symmetry: \( (1,2) \in R_1 \) and \( (2,1) \in R_1 \), so symmetric. Check transitivity: the only non-diagonal chain is \( (1,2),(2,1) \Rightarrow (1,1) \), which is already in \( R_1 \). All three conditions hold, so \( R_1 \) is a valid equivalence relation. — Reason: We must confirm every property before accepting \( R_1 \) as an answer; skipping any check could lead to an incorrect conclusion.
  4. Step 4: Explore what happens when element 3 is linked to the others. Suppose \( (1,3) \in R \). By symmetry we must include \( (3,1) \). By transitivity, since \( (3,1) \in R \) and \( (1,2) \in R \), we need \( (3,2) \in R \); and since \( (2,1) \in R \) and \( (1,3) \in R \), we need \( (2,3) \in R \); and since \( (3,2) \in R \) and \( (2,3) \in R \), transitivity is already satisfied. — Reason: Once a single new link from 3 is introduced, symmetry and transitivity force a cascade of additional pairs.
  5. Step 5: Form the second candidate. Collecting all pairs forced by Step 4 gives \[ R_2 = \{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)\}. \] This is simply \( A \times A \), the universal relation on \( A \). Reflexivity, symmetry, and transitivity all hold trivially. — Reason: The universal relation on any set is always an equivalence relation, so \( R_2 \) is automatically valid.
  6. Step 6: Show no other equivalence relations are possible. The element 3 is either related to 1 and 2 or it is not. If it is not related to either (only \( (3,3) \) involving 3), we get \( R_1 \). If it is related to at least one of them, symmetry and transitivity force all cross-pairs, giving \( R_2 \). There is no intermediate option. — Reason: This case analysis covers every possibility, confirming that exactly two equivalence relations exist.

Final 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.

Common Mistake

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.

✍️ Exam-ready Answer

Exam-ready Answer

  1. Step 1: Reflexivity forces \( (1,1),(2,2),(3,3) \in R \). Given pairs add \( (1,2),(2,1) \). Minimum set: \[ R_1 = \{(1,1),(2,2),(3,3),(1,2),(2,1)\} \] Verify: reflexive, symmetric, transitive (chain \( (1,2),(2,1) \Rightarrow (1,1) \) already present). So \( R_1 \) is valid.
  2. Step 2: Check if 3 can be related to 1 or 2. Adding \( (1,3) \) forces \( (3,1) \) by symmetry, and transitivity gives \( (2,3),(3,2),(3,3) \). This yields the universal relation: \[ R_2 = \{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)\} \] Verify: reflexive, symmetric, transitive. So \( R_2 \) is valid.
  3. Step 3: No other cases exist: 3 is either unrelated to \( \{1,2\} \) (giving \( R_1 \)) or related to at least one of them (giving \( R_2 \)). Total valid equivalence relations \( = 2 \).

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.

➕ More Examples

More Examples

Example 1

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) \).

Example 2

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 \).

🎯 Try a Similar Question

Try a Similar Question

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.

Solution

  1. Step 1: Identify the mandatory pairs: Any equivalence relation R on \( A = \\{1, 2, 3, 4\\} \) must contain all reflexive pairs. So R must contain \( (1,1), (2,2), (3,3), (4,4) \). We are also told R must contain \( (1,2) \) and \( (2,1) \).
  2. Step 2: Understand what (1,2) and (2,1) force: Since \( (1,2) \in R \) and \( (2,1) \in R \), elements 1 and 2 are in the same equivalence class. So the equivalence class of 1 (and 2) is \( \\{1, 2\\} \) at minimum, i.e., at least \( \\{1,2\\} \subseteq [1] \).
  3. Step 3: Determine possible equivalence classes: The elements 3 and 4 must each be placed into equivalence classes. The key constraint is that 3 and 4 must NOT be in the same class (since \( (3,4) \notin R \) and \( (4,3) \notin R \)). We consider all ways to partition \( A \) into equivalence classes such that 1 and 2 are together, and 3 and 4 are in different classes.
  4. Step 4: List valid partitions: Since 1 and 2 must be in the same block, and 3 and 4 must be in different blocks, we consider where 3 and 4 can go. The possible partitions of \( \\{1,2,3,4\\} \) with 1 and 2 together and 3 separate from 4 are: \nPartition 1: \( \\{\\{1,2\\}, \\{3\\}, \\{4\\}\\} \)\nPartition 2: \( \\{\\{1,2,3\\}, \\{4\\}\\} \)\nPartition 3: \( \\{\\{1,2,4\\}, \\{3\\}\\} \) \nNote: The partition \( \\{\\{1,2,3,4\\}\\} \) would require \( (3,4) \in R \), which is forbidden. The partition \( \\{\\{1,2\\}, \\{3,4\\}\\} \) would require \( (3,4) \in R \), also forbidden.
  5. Step 5: Write out each equivalence relation: From Partition 1: \( \\{\\{1,2\\}, \\{3\\}, \\{4\\}\\} \), the equivalence relation is \[ R_1 = \\{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1)\\}. \] From Partition 2: \( \\{\\{1,2,3\\}, \\{4\\}\\} \), the equivalence relation is \[ R_2 = \\{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(1,3),(3,1),(2,3),(3,2)\\}. \] From Partition 3: \( \\{\\{1,2,4\\}, \\{3\\}\\} \), the equivalence relation is \[ R_3 = \\{(1,1),(2,2),(3,3),(4,4),(1,2),(2,1),(1,4),(4,1),(2,4),(4,2)\\}. \]
  6. Step 6: Verify the constraint for each: Check that none of \( R_1, R_2, R_3 \) contains \( (3,4) \) or \( (4,3) \). \nFor \( R_1 \): The pairs involving 3 are only \( (3,3) \). No \( (3,4) \). Valid.\nFor \( R_2 \): The pairs involving 4 are only \( (4,4) \). No \( (3,4) \). Valid.\nFor \( R_3 \): The pairs involving 3 are only \( (3,3) \). No \( (3,4) \). Valid. \nAll three are equivalence relations satisfying the given conditions.
  7. Step 7: Conclusion: There are exactly three equivalence relations on \( A = \\{1,2,3,4\\} \) that contain \( (1,2) \) and \( (2,1) \) but do not contain \( (3,4) \) or \( (4,3) \). These are \( R_1, R_2, \) and \( R_3 \) as listed above.

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)\\}. \]

Everything you get with Solver7

More questions in Relations and Functions