Page 22 - Discrete Structure II

Which of the following relations is Transitive?

R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}
R2 = {(1, 1), (1, 2), (2, 1)}
R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}
R5 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}
R6 = {(3, 4)}

Answer:

R1 = {(1, 1), (1, 2), (2, 1), (2, 2), (3, 4), (4, 1), (4, 4)}
It is not transitive because (3, 4) and (4, 1) but (3, 1) is not R1
(1,1) and (1, 2) --------(1,2)
(1,2) and (2, 1) --------(1,1)
(1,2) and (2, 2)---------

R2 = {(1, 1), (1, 2), (2, 1)}

It is not transitive because (2, 1) and (1,2) belong to R 2 but (2, 2) is does not.

R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}

It is not transitive because (2, 1) and (1, 4) belong to R3, but (2, 4) does not.
R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}

It is transitive
R5 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)}

It is transitive

R6 = {(3, 4)}

It is transitive

R7 = {(3, 4), (4, 3)} not transitive

5