DHARM10 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCESimilarly the range set (range) of relation R denoted by R(R), contains all second compo-
nents of the ordered couples i.e.
R(R) = {y/(x, y) ∈ R}
Further, if R = X × Y then R(R) ⊆ Y.
For example,
l Let a relation R = {(x 1 , y 1 ), (x 1 , y 2 ), (x 2 , y 2 ), (x 3 , y 1 )} then its domain set and the range
set will be D(R) = {x 1 , x 2 , x 3 } and R(R) = {y 1 , y 2 } correspondingly.
l Let R = {( x, x}/x ∈ I+} where I+ = {1, 2, 3, ......} then
D(R) = {1, 23, , .....} and R(R) = {1, 2, 3, ......}.
l Let R = {(x, log 7 x}/x ∈ N 0 } where N 0 = {0, 1, 2, ......} then
D(R) = N 0 = {0, 1, 2, .....} and R(R) = { log 7 0, log 7 1, log 7 2, .......}.
If a relation is defined over same sets of objects then relation named as universal
relation i.e. if R 1 = X × X then R 1 is a universal relation over set X. A relation defines over
empty set named as void relation i.e. if R 2 = X × Y such that either X = ∅ or Y = ∅ or both X
= Y = ∅ then R 2 is a void relation.Example 1.2. Let X = {1, 2, 3, 4, 5} and Y = {7, 11, 13} are two sets.
(i) Consider a relation R i.e R = {(x, y)/x ∈ X and y ∈ Y and (y – x) is a perfect square}
then relation R contains the following ordered couples,
R = {(3, 7), (2, 11), (4, 13)}
(ii) Consider another relation R′ i.e. R′ = {(x, y)/x ∈ X and y ∈ Y and (y – x) is divisible by
6} then relation R’ will be,
R′ = {(1, 7), (5, 11), (1, 13)}
(iii)R ∪ R′ = {(1, 7), (1, 13), (2, 11), (3, 7), (4, 13), (5, 11)}.
(iv)R ∩ R′ = { } or ∅.
Properties of Binary Relation
Here we discuss the general properties hold by a binary relation such that reflexive, symmetric,
and transitive.
Let R be a binary relation defined over set X then
l Relation R is said to be reflexive if ordered couple (x, x) ∈ R for ∀x ∈ X. (Conversely,
relation R is irreflexive if (x, x) ∉ R for ∀x ∈ X).
l Relation R is said to be symmetric if, ordered couple (x, y) ∈ R and also ordered couple
(y, x) ∈ R for ∀x, ∀y ∈ X. (Conversely, relation R is antisymmetric if (x, y) ∈ R but (y,
x) ∉ R unless x = y).
l Relation R is said to be transitive if ordered couple (x, z) ∈ R whenever both ordered
couples (x, y) ∈ R and (y, z) ∈ R.
1.4.2 Equivalence Relation...........................................................................................
A binary relation on any set is said an equivalence relation if it is reflexive, symmetric, and
transitive. Further, if a relation is only reflexive and symmetric then it is called a compatibil-
ity relation. A table shown in Fig. 1.4 represents a compatibility relation. So, we can say that
every equivalence relation is a compatibility relation, but not every compatibility relation is
an equivalence relation.