Mathematical Foundation of Computer Science

DHARM

DISCRETE THEORY, RELATIONS AND FUNCTIONS 11

xyz

x 111

y 11—

z 1—1

Fig. 1.4 Compatibility relation.

Example 1.3. Let N = {1, 2, 3, .....} then show that relation R = {(x, y)/(x – y) is divisible by 2 for
every x and y ∈ N} is an equivalence relation.
Sol. Since,
l For any x ∈ N, (x – x) is divisible by 2 therefore, relation R is reflexive.
l For any x, y ∈ N, if (x – y) is divisible by 2 then also (y – x) is divisible by 2 therefore,
relation R is symmetric.
l For any x, y, and z ∈ N, if (x – y) is divisible by 2 and (y – z) is divisible by 2 then also
(x – z) is divisible by 2; because (x – z) can be written as (x – y) + (y – z) and since both
(x – y) and (y – z) is divisible by 2 then also (x – z). Therefore, relation R is reflexive.
Hence, relation R is an equivalence relation.

Equivalence Class

Let R be an equivalence relation on set X, then equivalence class denoted by [x] is generated by
the elements y ∈ X such that,
[y] = {x/x ∈ X and (y, x) ∈ R}
Since, set [y] consists of all virtual of y in the set X. Hence, [y] ⊆ X. A family of equivalence
classes generated by the elements of X defines a partition of set X. Such partition is a unique
partition. So, we may say that equivalence classes generated by any two elements are either
disjoint or equal. e.g.
[y] ∩ [z] = ∅ or [y] = [z]
where [y] and [z] are equivalence classes respect to relation R.
Also, the unions of all the equivalence classes generated by the elements of set X (parti-
tions) respect to relation R return the set X.

Example 1.4. Consider a relation R = {(x, y)/x, y ∈ I+ and (x – y) is divisible by 3} where I+ is the
set of positive integers. Find the set of equivalence classes generated by the elements of set I+.
Sol. The equivalence classes are,
l [0] = {0, 3, 6, 9, .......} (when (x – y) % 3 = 0),
l [1] = {1, 4, 7, 10, ......} (when (x – y) % 3 = 1), and
l [2] = {2, 5, 8, 11, ......} (when (x – y) % 3 = 2)
See, unions of these equivalence classes return the set I+, i.e.
I+ = [0] ∪ [1] ∪ [2] = {0, 1, 2, .......}
Let x and y are two elements from the set of integers I+, then the relation R is said to be
congruent relation such that,
R = {(x, y)/x, y ∈ I and (x – y) is divisible by m(∈ I+)}
Hence, relation shown in example 1.4 is a congruent relation of modulo 3.