Reflexivity, Symmetry and Transitivity

Let R be a binary relation on a set A.
R is reflexive if for all x A, xRx.
R is symmetric if for all x,y A, if xRy, then yRx.
R is transitive if for all x,y, z A, if xRy and yRz, then xRz.
R is an equivalence relation if A is nonempty and R is reflexive, symmetric and transitive.
In terms of digraphs, reflexivity is equivalent to having at least a loop on each vertex; symmetry means any arrow from one vertex to another will always be accompanied by another arrow in the opposite direction; and transitivity is the same as saying there must be a direct arrow from one vertex to another if one can walk from that vertex to the other through a list of arrows, travelling always along the direction of the arrows.

Examples

  1. Let A={ 0,1,2,3} and a relation R on A be given by

    R={ (0,0), (0,1), (0,3), (1,0), (1,1), (2,2), (3,0), (3,3) } .

    Is R reflexive? symmetric? transitive?

    Solution We'll make use of the digraph for R on the right.

    (a)
    R is reflexive, i.e. there is a loop at each vertex.
    (b)
    R is symmetric, i.e. the arrows joining a pair of different vertices always appear in a pair with opposite arrow directions.
    (c)
    R is not transitive. This is because otherwise the arrow from 1 to 0 and arrow from 0 to 3 would imply the existence of an arrow from 1 to 3 (which doesn't exist). In other words (1,0) R, (0,3) R and (1,3) R imply R is not transitive.

    Note It is equally easy to show these properties without resorting to the digraph.

  2. Let m,n and d be integers with d 0. Then if d divides (m-n), denoted by d | (m-n), i.e. m-n=dk for some integer k, then we say m is congruent to n modulo d, written simply as m n (mod d). Let R be the relation of congruence modulo 3 on the set of all integers, i.e.

    m R n m n (mod) 3 3 | (m-n) .

    Show R is an equivalence relation.

    Solution We just need to verify that R is reflexive, symmetric and transitive.

    (a)
    Reflexive: for any n we have nRn because 3 divides n-n=0.
    (b)
    Symmetric: for any m,n if mRn, i.e. m n (mod 3) then there exists a k such that m-n =3k. This means n-m=3(-k), i.e. n m (mod 3), implying finally nRm. For example, 7R4 is equivalent to 4R7 can be seen from

    7R4 7 4 (mod 3) 7-4 =3 1 4-7 =3 (-1) 4 7 (mod 3) 4R7

    (c)
    Transitive: for any m,n,p , if mRn and nRp, then there exist r,s such that m-n =3r and n-p=3s. Hence m-p=(m-n)+(n-p)=3(r+s), i.e. mRp.
    We thus conclude that R is an equivalence relation.