Page 20 - Discrete Structure II

R4 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)}
It is antisymmetric

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

R6 = {(3, 4)}
It is antisymmetric

Transitivity

Recall let a, b, c be three integers,

1. if a = b and b = c what can you say about a and c ? a and c are equal. It is said that the relation
“=” is transitive
2. if a > b and b > c, what can you say about a and c? a > c. “>” is said to be transitive

Definition

A relation R on a set A is said to be transitive if for all x, y, z ∈ A, if x R y and y R z then x R z

x, , ∈ A, x R y and y R z then x R z

Example

Which of the following relations of a set A = { 1, 2, 3, 4} is transitive

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

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

Answer:

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

(1, 1) ---- (1, 3) ----- (1,3)

(2,1) -----(1, 1)________> (2,1)
(2,1) -----(1, 3)--------- (2, 3)

(1,3) ---

(2,3) ----

3