Let R be a binary relation on a set A.
 R is reflexive, iff for all x Î A, (x,x) Î R, i.e. xRx is true.
 R is symmetric, iff for all x, y Î A, if (x, y) Î R, then (y, x) Î R
i.e xRy ® yRx is true  R is transitive iff for all x, y, z Î A, if (x, y) Î R and (y,z) Î R , then (x, z) Î R
i.e. (xRy L yRz) ® xRz is true
 Reflexive relations
 Definition
Let R be a binary relation on a set A.
R is reflexive, iff for all x Î A, (x,x) Î R, i.e. xRx is true.
Examples:



 Equality is a reflexive relation


for any object x, x = x is true.



 “less then” is not a reflexive relation. It is irreflexive.


for any number x, x < x is not true



 ” less then or equal to” is a reflexive relation


for any number x, x £ x is true



 A = {1,2,3,4}, R = {(1,1), (1,2), (2,2), (2,3), (3,3), (3,4), (4,4)}
 A = {1,2,3,4}, R = {(1,2), (2,3), (3,4), (4,1)} – not reflexive
(it is irreflexive)  A = {1,2,3,4}, R = {(1,1), (1,2), (3,4), (4,4)} – not reflexive
(it is neither reflexive nor irreflexive)


 Graph representation of reflexive relations
Rule: if xRx is true, there is a loop on node x.
Example:
R = “less then or equal to”
R = {(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)}
 Matrix representation of reflexive relations
The relation R in the above example would be represented thus:
1 2 3
1 1 0 0
2 0 1 0
3 0 0 1
 Reflexive and irreflexive relations
Compare the three examples below:



 A = {1,2,3,4}, R1 = {(1,1), (1,2), (2,2), (2,3), (3,3), (3,4), (4,4)}
 A = {1,2,3,4}, R2 = {(1,2), (2,3), (3,4), (4,1)}
 A = {1,2,3,4}, R3= {(1,1), (1,2), (3,4), (4,4)}


R1 is a reflexive relation. R2 ? R3 ?
R is irreflexive iff for all x Î A, (x,x) Ï R
R is neither reflexive, nor irreflexive iff
there is x Î A, such that (x, x) Î R, and there is y Î A such that (y, y) Ï R
Summary



 reflexive: for all x: xRx
 irreflexive: for no x: xRx
 neither: for some x: xRx is true, for some y: yRy is false


 Symmetric relations
 Definition
R is symmetric, iff for all x, y Î A, if (x, y) Î R, then (y, x) Î R,
i.e xRy ® yRx is true
This means: if two elements x and y are in relation R, then y and x are also in R,
i.e. if xRy is true, yRx is also true.
Examples:



 equality is a symmetric relation: if a = b then b = a
 “less than” is not a symmetric relation, it is antisymmetric.
 “sister” on the set of females is symmetric.
 “sister” on the set of all human beings is not symmetric.
(It is neither symmetric nor antisymmetric)  “friends” is symmetric: friend(a,b) ® friend(b,a)
 A = {1,2,3,4}, R1 = {(1,1), (1,2), (2,1), (2,3), (3,2), (4,4)}
The relation is symmetric.  A = {1,2,3,4}, R2 = {(1,1), (1,2), (2,3), (4,4)} – not symmetric
(it is antisymmetric)  A = {1,2,3,4}, R3 = {(1,1), (1,2), (2,1) , (2,3), (4,4)} – not symmetric
(it is neither symmetric nor antisymmetric)


 Graph representation of symmetric relations
Rule: if R is a symmetric relation, all links are bidirectional.
Example:
friend(x,y), x,y Î {Ann, Tim, Paul, Jane, Jim}
 Matrix representation of symmetric relations
Ann Tim Paul Jane Jim
Ann 0 1 0 0 0
Tim 1 0 1 0 0
Paul 0 1 0 0 0
Jane 0 0 0 0 1
Jim 0 0 0 1 0
 Symmetric and antisymmetric relations
Compare the relations:



 A = {1,2,3,4}, R1 = {(1,1), (1,2), (2,1), (2,3), (3,2), (4,4)}
 A = {1,2,3,4}, R2 = {(1,1), (1,2), (2,3), (4,4)}
 A = {1,2,3,4}, R3 = {(1,1), (1,2), (2,1) , (2,3), (4,4)}


R is antisymmetric if for all x, y Î A, x ¹ y, (x, y) Î R ® (y, x) Ï R.
i.e. for all pairs (x,y) in R, x ¹ y, the pair (y,x) is not in R.
it is not symmetric and not antisymmetric.
Summary



 symmetric: xRy ® yRx for all x and y
 antisymmetric: xRy and yRx ® x = y
 neither: for some x and y both xRy and yRx are true,
for others xRy is true, yRx is not true.


 Transitive relations
 Definition
Let R be a binary relation on a set A.
R is transitive iff for all x, y, z Î A, if (x, y) Î R and (y,z) Î R , then (x, z) Î R


 i.e.

(xRy L yRz) ® xRz


 is true

Examples:



 Equality is a transitive relation: a = b, b = c, hence a = c
 “less than” is a transitive relation: a < b, b < c, hence a < c
 mother(x,y) is not a transitive relation
 sister(x,y) is a transitive relation
 brother (x,y) is a transitive relation
 A = {1,2,3,4} R = {(1,1), (1,2), (1,3), (2,3), (4,3)} – transitive
 A = {1,2,3,4} R = {(1,1), (1,2), (1,3), (2,3), (3,4)} – not transitive


 Graph representation of transitive relations
Rule: if there is a link from a to b, and a link from b to c,
then there must be a link from a to c.
Example:
A = {1,2,3,4}
R = {(1,2), (1,3), (1,4),(2,3),(2,4),(3,4)}
This is the relation “less than”