# Properties of Binary relation

Basic properties:

Let R be a binary relation on a set A.

1. R is reflexive, iff for all x Î A, (x,x) Î R, i.e. xRx is true.
2. R is symmetric, iff for all x, y Î A, if (x, y) Î R, then (y, x) Î R
i.e xRy ® yRx is true
3. 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:

1. Equality is a reflexive relation

for any object x,  x = x is true.

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

for any number x, x < x is not true

1. ” less then or equal to” is a reflexive relation

for any number x,  x £ x is true

1. A = {1,2,3,4}, R = {(1,1), (1,2), (2,2), (2,3), (3,3), (3,4), (4,4)}
2. A = {1,2,3,4}, R = {(1,2), (2,3), (3,4), (4,1)} – not reflexive
(it is irreflexive)
3. 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:

A:= {1,2,3}

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
```

There are 1’s on the diagonal

• Reflexive and irreflexive relations

Compare the three examples below:

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

R1 is a reflexive relation. R2 ? R3 ?

Definition:

Let R be a binary relation on a set A.
R is irreflexive iff for all x Î A, (x,x) Ï R
Definition:

Let R be a binary relation on a set A.
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

Thus R2 is irreflexive, while R3 is neither reflexive nor irreflexive.

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 are also in R,
i.e. if xRy is true, yRx is also true.

Examples:

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

• Graph representation of symmetric relations

Rule: if R is a symmetric relation, all links are bi-directional.

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
```

The matrix is symmetric.

• Symmetric and anti-symmetric relations

Compare the relations:

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

Definition:

Let R be a binary relation on a set A.
R is anti-symmetric 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.
Definition: R is neither symmetric nor anti-symmetric iff
it is not symmetric and not anti-symmetric.

Summary

• symmetric: xRy ® yRx for all x and y
• anti-symmetric: 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

1. i.e.

(xRy L yRz) ® xRz

1.  is true

Examples:

1. Equality is a transitive relation: a = b, b = c, hence a = c
2. “less than” is a transitive relation: a < b, b < c, hence a < c
3. mother(x,y) is not a transitive relation
4. sister(x,y) is a transitive relation
5. brother (x,y) is a transitive relation
6. A = {1,2,3,4} R = {(1,1), (1,2), (1,3), (2,3), (4,3)} – transitive
7. 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”  