Chapter Three

Relations

3.1. Relations.

Relation is an important fundamental concept in the theory

of sets. Let recall that if x , y  . Then x  y means that y  x is
a non-negative numbers. If we have an ordered pair (x , y ) of real
numbers, then we can determine that x  y , we check if y  x is
non-negative. Hence the x  y describe a property of the order
pair (x , y ) . We call it R  of 2 defined as follows:
R   (x , y )  2
x  y   (x , y )  2
y  x is non-negative
The set R  determines the relationship between x and y
relative to the property less than or equal. Hence x  y if and
only if (x , y )  R  . Generalizing this we get the concept of
relation.

Definition 3.1. A relation R between a set A and a set B is a

subset of A  B , that is, R is a relation between A and B if and
only if R  A  B . We simply write (a, b )  R or aRb for
a  A , and b  B . R is not relation between A and B if and only if
R  A  B , that is (a , b )  R or a R b if and only if R  A  B . A
relation R on a set A is a subset of A 2  A  A . We note that if A
is a set with m elements and B is a set with n elements, then
there are 2mn relations from A to B .

Example 3.1. Let A  1, 2

and B  3, 4 . Then
A  B  (1,3), (1, 4), (2,3), (2, 4)
Then R  (2,3), (2, 4  A  B is a relation between the A and B .
Hence (2,3)  R (or 2R 3) and (2, 4)  R (or 2R 4) .

Example 3.2. Let A  1, 2 . Then A 2  (1,1), (1, 2), (2,1), (2, 2) . Since
A 2 has 4 elements, (A 2 ) has 24  16 subsets, thus 16 relations on
A  1, 2 . Here are several relations on A .

25
 R1  (1,1), (2, 2)
R 2  (1,1), (1, 2)
R 3  (1,1), (1, 2), (2, 2)
R 4  (1, 2)
R 5  (2,1), (2, 2)
Example 3.3. Let A  1, 2,3 and B  a , b  .
Then
R1  (1, a ), (1, b ), (2, a ), (2, b )
R 2  (3, a ), (3, b )
R 3  (1, a ), (1, b ), (3, a )
are relations from A to B . It is clear that 1R1a, and 1R 3a , but 1 R 2 a .

Definition 3.2. Let A be a set , and I A  (a, a ) a  A   A 2 . Then I A

is called the identity relation.

Example 3.5. Let A  1, 2,3 . Then I A  (1,1), (2, 2), (3,3)  A 2 is the
identity relation on A .

Definition 3.3. Every relation R from a set A to a set B has an

inverse relation R 1 from B to A which is defined by
R 1  (b , a ) (a, b )  R , a  A , b  B 

Example 3.6. Let A  1, 2,3 and B  a, b  . Then

R1  (1, a ), (1, b ), (2, a ), (2, b ) , and R11  (a,1), (b ,1), (a, 2), (b , 2)
R 2  (3, a ), (3, b ) , and R 21  (a,3), (b ,3)
R 3  (1, a ), (1, b ), (3, a ) , and R 31  (a,1), (b ,1), (a,3)
Then R11 , R 21 and R 31 are inverse relations from B to A .

3.2. Properties of relations

We continue our study of relations by looking to various

properties of relations.

Definition 3.4. A relation R on a set A is called reflexive if

aRa , that is (a, a )  R for all a  A . Hence every element is related
to itself.

26
 We note that the identity relation I A  (a, a ) a  A   A 2 is
reflexive.

Example 3.7. Let A  1, 2,3 . Then R1  (1,1), (1, 2), (2, 2), (2,3), (3,3) is
a reflexive relation, but R 2  (1,1), (1, 2) is not a reflexive relation.

Example 3.8. Let R be the relation on the real numbers

defined by the sentence x  y for all x , y  . Then R is not
reflexive, for x  x for any real number x .

Example 3.9. Let  be a family of sets, and let R be the

relation on  defined by the sentence A is a subset of B . Then
R is a reflexive relation on  , for every set is a subset of itself.

Definition 3.5. A relation R on a set A is called symmetric if

aRb implies that bRa , that is (a , b )  R implies (b , a )  R for all
a , b  A . Hence R is symmetric if a is related to b , then b is also
related to a . We note that R is a symmetric relation on A if and
only if R  R 1 , for if (a, b )  R , then (b , a )  R 1 .

Example 3.10. Let A  1, 2,3, 4 . Then R1  (1,3), (2, 4), (3,1), (4, 2) is
a symmetric relation, but R 2  (1,3), (2, 4), (3,1) is not a symmetric
relation, for (2, 4)  R 2 , but (4, 2)  R 2 .

Example 3.11. Let R be the relation on the natural numbers

which is defined by x divides y . Then R is not a symmetric
relation, since 2 divides 4 , but 4 does not divides 2 , that is
(2, 4)  R but (4, 2)  R .

Definition 3.6. A relation R on a set A is called transitive if

aRb and bRc implies that aRc , that is (a , b )  R and (b , c )  R
implies (a, c )  R for all a, b , c  A . Hence R is transitive if a is
related to b , and b is related to c , then a is also related to c .

27
Example 3.12. Let R be the relation on the real numbers
defined by the sentence x  y for all x , y  . Then R is
reflexive, for a  b , and b  c , then a  c .

Example 3.13. Let  be a family of sets, and let R be the

relation on  defined by the sentence A is a subset of B . Then
R is a transitive relation on  , for if A  B and B  C , then A  C
.

Example 3.14. Let A  1, 2,3, 4 . Then R1  (1,3), (3, 4), (1, 4) is a
transitive relation, but R 2  (1,3), (3, 4) is not a transitive relation,
for (1, 4)  R 2 .

Definition 3.7. A relation R on a set A is called anti-

symmetric if aRb and bRa imply a  b , that is (a, b )  R and
(b , a )  R imply a  b , for all a , b  A . Hence R is anti-symmetric if
a is related to b , and b is also related to a , then a  b . We note
that if a  b , then possibly a is related to b or possibly b is
related to , but never both.

Example 3.15. Let A  1, 2,3, 4 . Then R1  (1,1), (1,3), (3, 4), (4, 4) is
an anti-symmetric relation, but R 2  (1,3), (3,1), (3, 4) is not anti-
symmetric, since (1,3)  R 2 and (3,1)  R 2 , but 1  3 .

Example 3.16. Let  be a family of sets, and let R be the

relation on  defined by the sentence A is a subset of B . Then
R is an anti-symmetric relation on  , for if A  B and B  A ,
then A  B .

Definition 3.8. A relation R on a set A is called irreflexive if

a R a , that is (a, a )  R for a  A . Hence every element is not
related to itself.

Definition 3.9. A relation R on a set A is called asymmetric if

aRb imply b R a , that is (a , b )  R imply (b , a )  R , for all a , b  A .

28
Hence R is asymmetric if a is related to b imply b is not related
to a .

Example 3.17. Let A  1, 2,3 .Then the relation

R1  (1,1), (1, 2), (2,1), (2,3)
is neither reflexive, irreflexive, symmetric, asymmetric, anti-
symmetric, nor transitive.
Let consider the relation
R 2  (1,1), (2, 2), (1, 2), (3,3)
Then R 2 is reflexive, anti-symmetric, and transitive, but not
symmetric.

Definition 3.10. A relation R on a set A is called an

equivalence relation if
1. R is reflexive, that is aRa for all a  A .
2. R is symmetric, that is if aRb implies bRa ,for all a, b  A .
3. R is transitive, that is if aRb and bRc , then aRc for all
a, b , c  A .
If R is an equivalence relation on a set A , and aRb , then we
say that a is equivalent to b .

Example 3.18. An important example of an equivalence

relation is that of equality, for any elements in any set, we have
1. a  a
2. a  b  b  a .
3. a  b and b  c  a  c .

Example 3.19. Let A  1, 2,3, 4,5, 6 and consider the relation
R  (1,1), (2, 2), (3,3), (4, 4), (5,5), (6, 6), (2,3), (3, 2)
Then R is an equivalence relation on A .

Example 3.20. Let n be a fixed positive integer in . Define

the relation  n on by for all x , y  ,
[x  n y ]  [n (x  y )]
[x  n y ]  [x  y  kn , for some k  ]
[x  n y ]  [x  y  kn , for some k  ]

29
Sometimes, we write
[x  y (mod n )]  [n (x  y )]
[x  y (mod n )]  [x  y  kn , for some k  ]
[x  y (mod n )]  [x  y  kn , for some k  ]

Now, we show that  n is an equivalence relation on .

1. For all x  , we have x  x  0  0n , for 0  . Hence, for all
x  , we get x  n x . Thus,  n is a reflexive relation.

2. Let x , y  , and suppose that x n y . Then n (x  y ) , and

hence there exist k  such that x  y  kn . Thus
y  x  (k )n , and so n ( y  x ) , that is y  n x . Hence,  n is a
symmetric relation.

3. Let x , y ,z  , and suppose that x n y and y n z . Then

n (x  y ) and n ( y  z ) , and hence, there exist k , l  such
that x  y  kn , and y  z  ln .Thus x  z  (k  l )n , and so
n (x  z ) , for (k  l )  . Hence,  n is a transitive relation.
Therefore,  n is an equivalence relation on .

Definition 3.11. Let R be an equivalence relation on a set A ,

and let a  A . Then the set
a   a  b  A bRa
is called the equivalence class determine by a with respect to
R . The set of all equivalence classes is called A modulo R and
denoted by A R .

Definition 3.12. Let A be a set and P be a collection of

nonempty subsets of A . Then P is called a partition of A if the
following properties satisfied:
1. for all X ,Y  P , either X Y or X Y   .
2. A X .
X P

30
 Example 3.21. Let A  1, 2,3, 4,5, 6 . Let X  1 , Y  2, 4, 6 ,
and Z  3,5 . Then, X Y Z  , and A  X Y Z . So
P  X ,Y , Z  .

Theorem 3.1. Let R be an equivalence relation on the set .

Then
1. for all a  A , a   ,
2. if b  a , then a  b , where, a, b  A ,
3. for all a, b  A , either a  b or a b   ,
4. A a, that is, A is the union of all equivalence classes
aA

with respect to R .
5. The set P  a a  A  is a partition of A .
Proof.
1. Let a  A . Since R is reflexive, we have aRa Hence,
a  a  [a ] and so a   .
2. Let b  A such that b  a . Then bRa and by symmetric
property of R , we have aRb . Now, if x  a , then xRa .
But aRb and R is transitive for R is an equivalence
relation. Then xRb , and hence x  b . Therefore, a  b .
Similarly, x  b , then xRb . But bRa and R is transitive
for R is an equivalence relation. Then xRa , and hence
x  a . Therefore, b  a . Thus a  b for all a , b  R .
3. Let a, b  R and a b   . Then there exist x  a b and
hence, x  a and x  b . Thus xRa and xRb . Since R is
symmetric, we have bRx , and by transitivity, we have
bRa , and b  a . Hence, by (2), a  b .
4. Let a  A . Then a  a  a . Thus A  a . Also, a  A
aA aA aA

. Hence, A a .
aA

Example 3.22. Let n be a fixed positive integer in . Define

the relation  n on by for all x , y  ,
[x  n y ]  [n (x  y )]

31
As in Example 3.20. Let n 
 a a  . By Theorem 3.1, we have
n is a partition of . Then n  0,1, 2,..., n  1 , where,
0  0  kn  kn k  
1  1  kn k  
2  2  kn k  

n  1  (n  1)  kn k  
Suppose that n  5. Then
0  5k k    ..., 10, 5, 0,5,10,...   10  5  5  10 
1  1  6k k    ..., 9, 4,1, 6,11,...   9  4  6  11 
2  2  kn k    ..., 8, 3, 2, 7,12,...   8  3  7  12 
3  3  kn k    ..., 7, 2,3,8,13,...   7  2  8  13 
4  3  kn k    ..., 6, 1, 4,9,14,...   6  1  9  14 
Hence, 5  0,1, 2,3, 4 .Similarly, we find that 8  0,1, 2,3, 4,5, 6, 7 .
Example 3.23. Let A  1, 2,3, 4 . The
R  (1,1), (2, 2), (3,3)(4, 4), (4, 2), (2, 4) . Then R is an equivalence
relation on A . The distinct equivalence relations are
a  [a ]  x  A (a, x )  R 
1  [1]  x  A (1, x )  R   1
2  [2]  x  A (2, x )  R   2, 4  4
3  [3]  x  A (3, x )  R   3
Example 3.24. Let A  0,1, 2,3, 4 .Then
R  (0, 0), (1,1), (2, 2), (3,3), (4, 4), (0, 4), (1,3), (4, 0), (3,1)
is an equivalence relation, and the distinct equivalence classes
are:
a  [a ]  x  A (a, x )  R 
0  [0]  x  A (1, x )  R   0, 4  4
1  [1]  x  A (1, x )  R   1,3  3
2  [2]  x  A (2, x )  R   2
Example 3.25. Consider the set of all real numbers , and the
relation

R  (x , y )   x2y2 0 

32
1. We want to show that R is reflexive. Let x  . Then
0  x 2  x 2 . Thus (x , x )  R , that is xRx . Therefore, R is
reflexive.
2. Now, we show that R is symmetric. Let x , y  such that
(x , y )  R . Then x 2  y 2  0 , and this implies that y 2  x 2  0 .
Hence ( y , x )  R , that is yRx . Therefore, R is symmetric.
3. Finally, we show that R is transitive. Let x , y , z  such
that (x , y )  R and ( y , z )  R . Thus x 2  y 2  0 and y 2  z 2  0
.So x 2  y 2  y 2  z 2  0 , and x 2  z 2  0 . Thus (x , z )  R , that is
xRz . Therefore, R is transitive.
Therefore, R is reflexive, symmetric and transitive, and
hence, R is an equivalence relation. The equivalence classes
has the form
x  [x ]   y  yRx 
 y  (y , x )  R 


 y y 2 x 2  0 
 y  y2 x2 
 y  y  x 
  x , x 
For any x . If x  4 , then
4  [4]   y  ( y , 4)  R 
 y  y  4
 4, 4
Similarly, 3  [3]  3,3 .
Example 3.26. Let A be any set. Then the identity relation
I A  (a, a ) a  A   A 2
is an equivalence relation and the equivalence classes are
a  [a ]  b  A a I A b 
 b  A (a , b )  I A 
 b  A a  b 
 a
for any a  A . If a, b  A such that a  b , then a  b  , that is
a  b and the two classes are distinct.

33
 If A  1, 2,3, 4 , then the equivalence classes for the identity
relation I A are 1 , 2 , 3 , and 4 .

3.3. Domain and range of relations

Let R be a relation between a set A and a set B . Then
R  A  B . The domain of D R of the relation R is the set
D R  a  A (a, b )  R , b  B   A
The range Rang R of the relation R is the set
Rang R  b  B (a, b )  R , a  A   B
Example 3.27. Let A  1, 2,3, 4 , and B  5, 6, 7 . Consider the
relation R  (2,5), (4,5), (4, 7) between the set A and the set B .
Then the domain of R is D R  2, 4 and the range of R is
Rang R  5, 7 .
Also, R 1  (5, 2), (5, 4), (7, 4) is a relation between B and A .
The domain of R 1 is D R  5, 7 , and the range of R 1 is
1

Rang R  2, 4 .
1

Example 3.28. Let consider the relation


R  (x , y ) x , y  , 4x 2  9 y 2  36   

 (x , y ) x , y  ,9 y 2  36  4x 2 
 4 
 ( x , y ) x , y  ,y 2  4 x 2
 9 
 4 
 ( x , y ) x , y  ,y   4 x 2 
 9 
 4 
 ( x , y ) x , y  , 4  x 2  0
 9 
 4 2
 ( x , y ) x , y  ,4  x 
 9 

 (x , y ) x , y  , x 2  9 
 (x , y ) x , y  , x  [ 3,3]
Thus D R  [3,3] . Similarly,

34
 
R  (x , y ) x , y  , 4x 2  9 y 2  36   

 (x , y ) x , y  , 4x 2  36  9 y 2 
 9 2
 ( x , y ) x , y  ,x 2  9 y 
 4 
 9 2 
 ( x , y ) x , y  ,x   9 y 
 4 
 9 2 
 ( x , y ) x , y  ,9  y  0
 4 
 9 
 ( x , y ) x , y  ,9  y 2 
 4 

 (x , y ) x , y  , y 2  4 
 (x , y ) x , y  , y  [ 2, 2]
Thus, Rang R  [2, 2] . Furthermore,

R 1  (x , y ) x , y  ,9x 2  4 y 2  36 
Hence D R 1  [2, 2] , and Rang R 1  [3,3] .

Example 3.29. Let R be the relation defined on the natural

numbers such that
R  (x , y ) x , y  ,3x  y  15
(x , y ) x , y  , y  15  3x 
 (1,12), (2,9), (3, 6), (4,3)
R 1  (12,1), (9, 2), (6,3), (3, 4)
Note that x  5, y  0 is a solution for 3x  y  15 in general, but
(5,3)  R for 0 . Hence, D R  1, 2,3, 4  Rang R , and 1

Rang R  12,9, 6,3  D R 1 .

3.4. Partially and totally ordered sets

Definition 3.13. Let R be a relation on a set A . Then R is

called a partial order relation, if it satisfies the following
conditions:

1. R is reflexive, that is aRa for all aA .

35
2. Ris anti-symmetric, that is if aRb and bRa , then a  b for all
a, b  A .
3. R is transitive, that is if aRb and bRc , then aRc for all
a, b , c  A .

If a relation R on a set A defines a partial order on A , then

aRb is denoted by a b which reads a precedes b , and we
write (A , R )  (A , ) to denote the set A and the partial ordering
R  , and we call A is a partially ordered set (poset).

Example 3.30. Let consider the set . Define the relation on

, R   (x , y ) x , y  , x  y  . We know that  is reflexive, anti-
symmetric, and transitive. So R  is a partial order relation on
, that is (A , R  ) .

Example 3.31. Let  be a family of sets. Define the relation

on the set  , R   (A , B ) A , B , A  B  . We know that  is
reflexive, anti-symmetric, and transitive. Thus R  is a partial
order relation on  , that is (A , R  ) .

Example 3.32. Let consider the set of all real numbers .

Define the relation on , R   (x , y ) x , y  , x  y  . We know
that < is not reflexive. Thus R  is not a partial order relation
on .

Example 3.33. Let A  1, 2,3 , and the relation

R  (1,1), (2, 2), (3,3), (1, 2 on A . Thus R is reflexive, anti-
symmetric, and transitive, that is R  is a partial order
relation on A .

Example 3.34. Let A  l l is a line in the plane . Define

R   (l1 , l 2 ) l1 , l 2  A , l1  l 2 , that is l1 is perpendicular to l 2   A  A
Then R  is not a partial order on A , since any line can not be
a perpendicular to itself, that is (l , l )  R  , and hence R  is not
reflexive.

36
Definition 3.14. (i) Let R be a partially ordered relation on a
set A . Elements a, b  A are said to be comparable if and only
if either aRb or bRa . Otherwise, a and b are non-
comparable.
(ii) A partially ordered relation R on a set A is called a
totally order relation, if either aRb or bRa for any a, b  A .

Example 3.35. A partially ordered relation on any set A of

real numbers is a totally ordered set.

Example 3.36. Let A  1, 2,3, 4,5, 6 . Define the relation

R  (x , y ) x , y  A , x divieds y 


 (x , y ) x , y  A , x y 
 (1,1), (1, 2), (1,3), (1, 4), (1,5), (1, 6), (2, 2), (2, 4), (2, 6), (3,3), (3, 6), (4, 4), (5,5), (6, 6)
Then R is a partial order relation , but not a total order, since
(3,5)  R and (5,3)  R .

Solved Problems

1. Let A  1, 2,3, 4 , and B  1,3,5 . Define a relation R between

A and B by R  (x , y ) x  A , y  B ; x  y  . Write the relation
R.
Solution. R  (x , y ) x  A , y  B ; x  y   (1,3), (1,5), (2,3), (2,5), (3,5) .

2. Let A  2,3, 4,5 , and B  3, 6, 7,10 . Define a relation R

between A and B by R  (x , y ) x  A , y  B ; x y  . Write the
relation R , R 1 ,and find the domain and range R .
Solution. R  (x , y ) x  A , y  B ; x y   (2, 6), (2,10), (3,3), (3, 6), (5,10)
. Also R 1  (6, 2), (10, 2), ((3,3), (6,3), (10,5) . Then
D R  2,3,5  Rang R and Rang R  3, 6,10  D R .
1 1

3. Answer the following True (T) , or false (F):

37