Page 19 - Discrete Structure II

Example

Let A = { 1, 2, 3} which of the following relations on A is antisymmetric?

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

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

Answer

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

Yes, it is antisymmetric

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

No it is not antisymmetric because (2, 1,) and (1, 2) belong to R2 1 is not equal to 2
R3 = { (1, 1,) ( 2, 2), (3, 3), ( 3, 1) } it antisymmetric

R4 = { (1, 1,) ( 2, 2), (3, 3), ( 3, 1), (1, 3) } it not antisymmetric because (3,1) and (1, 3) belong to R4 and 1
is not equal to 3

Exercise

Which of the following relations is antisymmetric?

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 antisymmetric because (1, 2) and (2, 1) are R1 and 1 is not equal to 2

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

It is not antisymmetric because (1, 2) and (2, 1) are R1 and 1 is not equal to 2

R3 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}
It is not antisymmetric because (1, 2) and (2, 1) are R1 and 1 is not equal to 2

2