Let \( A =\{1, 2, 3\}.\) Then show that the number of relations containing \((1,2)\) and \((2,3)\) which are reflexive and transitive but not symmetric is three.
CBSE Class 12 Maths · Relations and Functions
CBSE Class 12 Maths · Relations and Functions
Imagine three friends numbered 1, 2, and 3. We want to make a list of pairs showing who is connected to whom. Two connections are already given: 1 connects to 2, and 2 connects to 3. Every person must also connect to themselves. Because 1 connects to 2 and 2 connects to 3, fairness forces 1 to also connect to 3. After all these forced connections, only a tiny number of extra optional connections keep the list fair without making it perfectly two-way. It turns out exactly 3 such lists are possible.
Answer: There are exactly three such relations: \( R_0 = \{(1,1),(2,2),(3,3),(1,2),(2,3),(1,3)\} \), \( R_1 = R_0 \cup \{(2,1)\} \), and \( R_2 = R_0 \cup \{(3,2)\} \). Each is reflexive and transitive but not symmetric, so the required number of relations is \( 3 \).
A relation \( R \) on a set \( A \) is a subset of \( A \times A \). We are given \( A = \{1, 2, 3\} \) and we must build relations that always contain \( (1,2) \) and \( (2,3) \). We need them to be reflexive and transitive but NOT symmetric. Recall the definitions. Reflexive: every element must relate to itself, so \( (1,1), (2,2), (3,3) \) must all be in \( R \). Transitive: if \( (a,b) \in R \) and \( (b,c) \in R \), then \( (a,c) \in R \). Symmetric: if \( (a,b) \in R \) then \( (b,a) \in R \); we want the relation to fail this at least once. The strategy is to first put in all the pairs we are forced to include, then check which extra pairs transitivity demands, and finally count how many valid relations exist without becoming symmetric.
Reflexive: \( (a,a) \in R \) for all \( a \in A \). Transitive: \( (a,b) \in R \text{ and } (b,c) \in R \Rightarrow (a,c) \in R \). Symmetric: \( (a,b) \in R \Rightarrow (b,a) \in R \).
There are exactly three such relations: \( R_0 = \{(1,1),(2,2),(3,3),(1,2),(2,3),(1,3)\} \), \( R_1 = R_0 \cup \{(2,1)\} \), and \( R_2 = R_0 \cup \{(3,2)\} \). Each is reflexive and transitive but not symmetric, so the required number of relations is \( 3 \).
A common mistake is forgetting that transitivity forces \( (1,3) \) into the relation once \( (1,2) \) and \( (2,3) \) are present, or failing to verify transitivity after adding an extra pair. Students also often miscount by adding pairs that quietly make the relation symmetric (e.g. adding both \( (2,1) \) and \( (3,2) \)), which violates the 'not symmetric' condition.
There are exactly three such relations: \( R_0 = \{(1,1),(2,2),(3,3),(1,2),(2,3),(1,3)\} \), \( R_1 = R_0 \cup \{(2,1)\} \), and \( R_2 = R_0 \cup \{(3,2)\} \). Each is reflexive and transitive but not symmetric, so the required number of relations is \( 3 \).
One common mistake: students forget that adding an optional pair like \( (3,1) \) can trigger a chain of transitive closures that forces the relation to become fully symmetric — always re-check all transitivity consequences before accepting an optional pair.
Answer: There are exactly three such relations: \( R_0 = \{(1,1),(2,2),(3,3),(1,2),(2,3),(1,3)\} \), \( R_1 = R_0 \cup \{(2,1)\} \), and \( R_2 = R_0 \cup \{(3,2)\} \). Each is reflexive and transitive but not symmetric, so the required number of relations is \( 3 \).
Question: Let \( A = \{1, 2, 3\} \). Find the number of relations on \( A \) that contain the pairs \( (1,3) \) and \( (3,2) \), and are reflexive and transitive but NOT symmetric.
Solution: We work on the set \( A = \{1, 2, 3\} \). Step 1 — Mandatory pairs from reflexivity: Every reflexive relation must contain \( (1,1),\, (2,2),\, (3,3) \). Step 2 — Mandatory pairs from the given pairs: We are told \( (1,3) \in R \) and \( (3,2) \in R \). By transitivity, since \( (1,3) \in R \) and \( (3,2) \in R \), we must also have \( (1,2) \in R \). So the minimum mandatory set is: \[ R_{\min} = \{(1,1),(2,2),(3,3),(1,3),(3,2),(1,2)\} \] Step 3 — Optional pairs to consider: The remaining pairs not yet forced in or out are \( (2,1),(2,3),(3,1) \) and their effect on transitivity. We now list all possible extensions that keep transitivity: Case 1: No optional pair added. \[ R_1 = \{(1,1),(2,2),(3,3),(1,2),(1,3),(3,2)\} \] Check transitivity: All chains close. Check symmetry: \( (1,3) \in R_1 \) but \( (3,1) \notin R_1 \), so NOT symmetric. Valid. Case 2: Add \( (2,1) \). With \( (2,1) \in R \) and \( (1,3) \in R \), transitivity forces \( (2,3) \). With \( (2,3) \in R \) and \( (3,2) \in R \), transitivity forces \( (2,2) \) (already present) and \( (3,3) \) (already present). With \( (3,2) \in R \) and \( (2,1) \in R \), transitivity forces \( (3,1) \). With \( (3,1) \in R \) and \( (1,3) \in R \), forces \( (3,3) \) (already present). With \( (1,2) \in R \) and \( (2,1) \in R \), forces \( (1,1) \) (present). With \( (2,1) \in R \) and \( (1,2) \in R \), forces \( (2,2) \) (present). So: \[ R_2 = \{(1,1),(2,2),(3,3),(1,2),(1,3),(2,1),(2,3),(3,1),(3,2)\} \] This is the universal relation — it IS symmetric. Discard. Case 3: Add \( (2,3) \) only (without \( (2,1) \)). With \( (2,3) \in R \) and \( (3,2) \in R \), forces \( (2,2) \) (present) and \( (3,3) \) (present). No new pairs forced. Relation: \[ R_3 = \{(1,1),(2,2),(3,3),(1,2),(1,3),(2,3),(3,2)\} \] Check symmetry: \( (1,2) \in R_3 \) but \( (2,1) \notin R_3 \). NOT symmetric. Valid. Case 4: Add \( (3,1) \) only (without \( (2,1) \)). With \( (3,1) \in R \) and \( (1,3) \in R \), forces \( (3,3) \) (present). With \( (3,1) \in R \) and \( (1,2) \in R \), forces \( (3,2) \) (present). With \( (1,3) \in R \) and \( (3,1) \in R \), forces \( (1,1) \) (present). No new pairs. Relation: \[ R_4 = \{(1,1),(2,2),(3,3),(1,2),(1,3),(3,1),(3,2)\} \] Check symmetry: \( (1,2) \in R_4 \) but \( (2,1) \notin R_4 \). NOT symmetric. Valid. Case 5: Add both \( (2,3) \) and \( (3,1) \) (but not \( (2,1) \)). With \( (2,3) \) and \( (3,1) \), transitivity forces \( (2,1) \). This reduces to Case 2 (the full relation), which is symmetric. Discard. Case 6: Add both \( (2,1) \) and \( (3,1) \) — already shown in Case 2 to produce the full relation. Discard. Step 4 — Count valid relations: \( R_1,\, R_3,\, R_4 \) — exactly THREE relations.
Answer: There are exactly 3 relations on \( A = \{1,2,3\} \) containing \( (1,3) \) and \( (3,2) \) that are reflexive and transitive but not symmetric.
Question: Let \( B = \{a, b, c\} \). How many relations on \( B \) contain the pairs \( (a,b) \) and \( (b,c) \) and are reflexive and transitive but NOT symmetric? List all such relations explicitly.
Solution: Step 1 — Mandatory reflexive pairs: \( (a,a),\,(b,b),\,(c,c) \). Step 2 — Mandatory pairs from the given and transitivity: Given \( (a,b) \in R \) and \( (b,c) \in R \), transitivity forces \( (a,c) \in R \). Minimum set: \[ R_{\min} = \{(a,a),(b,b),(c,c),(a,b),(b,c),(a,c)\} \] Step 3 — Optional pairs: The remaining pairs not yet assigned are \( (b,a),(c,b),(c,a) \). We examine all subsets of these three optional pairs for transitivity closure: Case 1: Add none. \[ R_1 = \{(a,a),(b,b),(c,c),(a,b),(b,c),(a,c)\} \] Transitivity: All compositions are already covered. Symmetry check: \( (a,b) \in R_1 \) but \( (b,a) \notin R_1 \). NOT symmetric. Valid. Case 2: Add \( (b,a) \) only. With \( (b,a) \) and \( (a,b) \): forces \( (b,b) \) (present). With \( (b,a) \) and \( (a,c) \): forces \( (b,c) \) (present). With \( (c,c) \) and \( (b,a) \): no new. No further forcing. Relation: \[ R_2 = \{(a,a),(b,b),(c,c),(a,b),(b,c),(a,c),(b,a)\} \] Symmetry check: \( (b,c) \in R_2 \) but \( (c,b) \notin R_2 \). NOT symmetric. Valid. Case 3: Add \( (c,b) \) only. With \( (c,b) \) and \( (b,c) \): forces \( (c,c) \) (present). With \( (c,b) \) and \( (b,a) \): \( (b,a) \) is not present, so no forcing here. With \( (a,b) \) and... no new chain yet. No further forced pairs. \[ R_3 = \{(a,a),(b,b),(c,c),(a,b),(b,c),(a,c),(c,b)\} \] Symmetry: \( (a,b) \in R_3 \) but \( (b,a) \notin R_3 \). NOT symmetric. Valid. Case 4: Add \( (c,a) \) only. With \( (c,a) \) and \( (a,b) \): forces \( (c,b) \). Now \( (c,b) \) forces Case 3 conditions. With \( (c,b) \) and \( (b,c) \): forces \( (c,c) \) (present). With \( (c,a) \) and \( (a,c) \): forces \( (c,c) \) (present). So adding \( (c,a) \) forces \( (c,b) \) as well. \[ R_4 = \{(a,a),(b,b),(c,c),(a,b),(b,c),(a,c),(c,a),(c,b)\} \] Symmetry: \( (a,b) \in R_4 \) but \( (b,a) \notin R_4 \). NOT symmetric. Valid. Case 5: Add \( (b,a) \) and \( (c,b) \). With \( (c,b) \) and \( (b,a) \): forces \( (c,a) \). With \( (c,a) \) and \( (a,b) \): forces \( (c,b) \) (present). With \( (b,a) \) and \( (a,c) \): forces \( (b,c) \) (present). With \( (c,a) \) and \( (a,c) \): forces \( (c,c) \) (present). \[ R_5 = \{(a,a),(b,b),(c,c),(a,b),(b,c),(a,c),(b,a),(c,b),(c,a)\} \] This is the full relation on \( B \) — it IS symmetric. Discard. Case 6: Add \( (b,a) \) and \( (c,a) \). Adding \( (c,a) \) forces \( (c,b) \) (from Case 4). So this becomes Case 5 — the full relation. Discard. Case 7: Add \( (c,b) \) and \( (c,a) \) — same as Case 4 since adding \( (c,a) \) already forces \( (c,b) \). Reduces to \( R_4 \). Already counted. Case 8: Add all three \( (b,a),(c,b),(c,a) \) — full relation. Discard. Step 4 — Count valid relations: \( R_1,\, R_2,\, R_3,\, R_4 \) are the four valid reflexive-transitive-but-not-symmetric relations. Wait — let us recount carefully to ensure we have not missed any subset: Subsets of \( \{(b,a),(c,b),(c,a)\} \): \( \emptyset \to R_1 \) (valid), \( \{(b,a)\} \to R_2 \) (valid), \( \{(c,b)\} \to R_3 \) (valid), \( \{(c,a)\} \to R_4 \) (valid, forces \( (c,b) \)), \( \{(b,a),(c,b)\} \to \) forces \( (c,a) \), gives full relation (symmetric, discard), \( \{(b,a),(c,a)\} \to \) forces \( (c,b) \), gives full relation (discard), \( \{(c,b),(c,a)\} \to R_4 \) (already counted), \( \{(b,a),(c,b),(c,a)\} \to \) full relation (discard). So the distinct valid relations are \( R_1, R_2, R_3, R_4 \) — exactly FOUR relations.
Answer: There are exactly 4 relations on \( B = \{a,b,c\} \) containing \( (a,b) \) and \( (b,c) \) that are reflexive and transitive but not symmetric.
Question: Let \( A = \{1, 2, 3\} \). Find the number of relations on \( A \) that contain the pairs \( (1, 2) \) and \( (2, 2) \), and are reflexive and transitive but NOT symmetric. List all such relations explicitly.
Answer: There are exactly four such relations: \( R_0 = \{(1,1),(2,2),(3,3),(1,2)\} \), \( R_2 = \{(1,1),(2,2),(3,3),(1,2),(1,3)\} \), \( R_3' = \{(1,1),(2,2),(3,3),(1,2),(3,1),(3,2)\} \), and \( R_4' = \{(1,1),(2,2),(3,3),(1,2),(2,3),(1,3)\} \). Each is reflexive and transitive but not symmetric, so the required number of relations is \( 4 \).