Page 18 - Discrete Structure II

Relations


Reflexivity a  A, aRa
Symmetry a  , b A, aRb  bRa

Example
Which of the following relation on the set A = {1, 2, 3}, is reflexive? symmetric?

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

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

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

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

R1 is not reflexive because 3 is not in relation with 3, or (3, 3) does not belong to R 1

R1 is symmetric

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

R2 is reflexive and symmetric

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

R3 is reflexive and symmetric

Antisymmetry

What can say about two integers a and b, that are such that a a ≤ b b and b ≤ a ?

They must equal, ” ≤ “ is said to be antisymmetric.
In general a relation R on a set A is said to be antisymmetric if

a 
b 
,
,
( a ) R and b ) R if only if a = b for all a, b  A
(
in other terms
a R b and b R a iff a = b

1