Making a Relation Transitive
📺 Video Explanation
📝 Question
Let \( A = \{1,2,3\} \) and
\[ R = \{(1,2),(1,1),(2,3)\} \]
Find the minimum number of ordered pairs to be added so that \( R \) becomes transitive.
✅ Solution
🔹 Step 1: Check Transitivity Condition
A relation is transitive if: \[ (a,b),(b,c) \in R \Rightarrow (a,c) \in R \]
🔹 Step 2: Identify Chains
Given: \[ (1,2), (2,3) \in R \]
So, we must have: \[ (1,3) \in R \]
But \( (1,3) \notin R \)
➡️ Add: \[ (1,3) \]
🔹 Step 3: Check New Relation
New relation: \[ R’ = \{(1,1),(1,2),(2,3),(1,3)\} \]
Now check all chains:
- \( (1,1),(1,2) \Rightarrow (1,2) \) ✔
- \( (1,1),(1,3) \Rightarrow (1,3) \) ✔
- \( (1,2),(2,3) \Rightarrow (1,3) \) ✔
No missing pairs.
✔ Relation is now transitive.
🎯 Final Answer
Minimum number of ordered pairs to be added = 1
Pair added: \[ (1,3) \]
🚀 Exam Insight
- Always check chains like (a,b) and (b,c)
- Add only required pairs → minimum condition
- After adding, recheck all chains