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”

Author: Deepak Chahar

Leave a Reply

Your email address will not be published. Required fields are marked *