GATE IT 2004 | Question: 4

Question

Let $R_{1}$ be a relation from $A = \left \{ 1,3,5,7 \right \}$ to $B = \left \{ 2,4,6,8 \right \}$ and $R_{2}$ be another relation from $B$ to $C = \{1, 2, 3, 4\}$ as defined below:

1. An element $x$ in $A$ is related to an element $y$ in $B$ (under $R_{1}$) if $x + y$ is divisible by $3.$
2. An element $x$ in $B$ is related to an element $y$ in $C$ (under $R_{2}$) if $x + y$ is even but not divisible by $3.$

Which is the composite relation $R_{1}R_{2}$ from $A$ to $C$?

• A. $R_{1}R_{2}  =  \{(1, 2), (1, 4), (3, 3), (5, 4), (7, 3)\} $
• B. $R_{1}R_{2} =  \{(1, 2), (1, 3), (3, 2), (5, 2), (7, 3)\} $
• C. $R_{1}R_{2} =  \{(1, 2), (3, 2), (3, 4), (5, 4), (7, 2)\} $
• D. $R_{1}R_{2}  =  \{(3, 2), (3, 4), (5, 1), (5, 3), (7, 1)\} $

Comments

Admins, please change the order of $R_1 \circ R_2$ to $R_2 \circ R_1$ as per below definition of composition from kenneth Rosen

---

@Ayush see the comment by warrior below... Difference between Composition of relation and function... Is it true?

---

.........................................................

C)

---

Question wrongly copied 
It is R2∘R1 not R1∘R2

---

Another way to look at the question:

An element x in B is related to an element y in C (under R2) if x+y is even but not divisible by 3.

Since the set B has all the even elements then each element of B has to be related to an even element of C, only then can be the sum even.

So how does that help? When it comes to the composite relation from A → C then each element of C has to be even which is satisfies only in option C.

---

Can someone please explain me this problem.
I have calculated R1 & R2 separately but how do we proceed further to R1.R2 ??
@Sachin Mittal 1 @Deepak Poonia Sir 

---

Refer this Comment

---

omg question should be clear it should be given like from b to c and c={1,2,3,4} then we can understand but how we understand from b to c={1,2,3,4} i got confused

---

@Harshit Dubey https://gateoverflow.in/3645/gate-it-2004-question-4?show=459960#c459960

Answer 1

The answer is $C$.

Explanation:

• $R_1=\{(1,2),(1,8),(3,6),(5,4),(7,2),(7,8)\}$
• $R_2=\{(2,2),(4,4),(6,2),(6,4),(8,2)\}$

So, $R_1R_2=\{(1,2),(3,2),(3,4),(5,4),(7,2)\}$

Comments

What will be the answer for R2.R1?

---

@rohan mishra very beautiful lecture it was !!

---

@Pranav Madhani 

Answer 2

R1 is a relation from A = {1, 3, 5, 7} to B = {2, 4, 6, 8} . Under R1, an element x in A is related to an element y in B if x + y is divisible by 3. 
Thus, R1 = {(1, 2), (1, 8), (3, 6), (5, 4), (7, 2), (7, 8)} 
R2 is a relation from B = {2, 4, 6, 8} to C = {1, 2, 3, 4} Under R2, an element y in B is related to an element z in C if y + z is even but not divisible by 3. 
Thus, R2 = {(2, 2), (4, 4), (6, 2), (6, 4), (8, 2)} 
 
Thus, R1R2 = {(1, 2), (3, 2), (3, 4), (5, 4), (7, 2)} 
 
Thus, option (C) is correct. 

Comments

is their any difference between composite relation AB and composition of A and B

Answer 3

R1 = {(1, 2), (1, 8), (3, 6), (5, 4), (7, 2), (7, 8)} 

R2 = {(2, 2), (4, 4), (6, 2), (6, 4), (8, 2)} 

 

To find the composite relation R1R2 from A to C, we just need to find all ordered pairs (x, z) where there exists an element y such that (x, y) ∈ R1 and (y, z) ∈ R2.

Therefore

R1R2 = {(1, 2), (3, 2), (3, 4), (5, 4), (7, 2)}

=====================

 

Hope my answer helps everyone here 

 

Comments

does (3,2) belong to R1?
Edit: I got it, just draw the mapping of relations (like in functions)
and you'll notice 1—>2—>2 (relation A—>B—>C),   3—>6—>4,   3—>6—>2  etc.
Therefore, (1,2), (3,4),(3,2), etc are in the correct option.
Hope it helps someone, better than any difficult definition.

Answer 4

Analysis

 

Step 1: Find all pairs in R₁ R₁ connects A = {1, 3, 5, 7} to B = {2, 4, 6, 8} if x + y is divisible by 3.

• 1+2=3 → (1, 2)

• 1+8=9 → (1, 8)

• 3+6=9 → (3, 6)

• 5+4=9 → (5, 4)

• 7+2=9 → (7, 2)

• 7+8=15 → (7, 8) So, R₁ = {(1, 2), (1, 8), (3, 6), (5, 4), (7, 2), (7, 8)}.

---

Step 2: Find all pairs in R₂ R₂ connects B = {2, 4, 6, 8} to C = {1, 2, 3, 4} if x + y is even but not divisible by 3. (Hint: For the sum to be even, an even number from B must be added to an even number from C).

• 2+2=4 (even, not div by 3) → (2, 2)

• 4+4=8 (even, not div by 3) → (4, 4)

• 6+2=8 (even, not div by 3) → (6, 2)

• 6+4=10 (even, not div by 3) → (6, 4)

• 8+2=10 (even, not div by 3) → (8, 2) So, R₂ = {(2, 2), (4, 4), (6, 2), (6, 4), (8, 2)}.

---

Step 3: Find the "Chains" to build R₁R₂ Now we look for (a, b) in R₁ and (b, c) in R₂ to form (a, c).

• (1, 2) ∈ R₁ and (2, 2) ∈ R₂ → (1, 2) is in the result.

• (1, 8) ∈ R₁ and (8, 2) ∈ R₂ → (1, 2) is in the result (again).

• (3, 6) ∈ R₁ and (6, 2) ∈ R₂ → (3, 2) is in the result.

• (3, 6) ∈ R₁ and (6, 4) ∈ R₂ → (3, 4) is in the result.

• (5, 4) ∈ R₁ and (4, 4) ∈ R₂ → (5, 4) is in the result.

• (7, 2) ∈ R₁ and (2, 2) ∈ R₂ → (7, 2) is in the result.

• (7, 8) ∈ R₁ and (8, 2) ∈ R₂ → (7, 2) is in the result (again).

---

Final Result 

Combining all the unique pairs, we get: R₁R₂ = {(1, 2), (3, 2), (3, 4), (5, 4), (7, 2)} This matches Option C.