Chapter 2: Mathematical Preliminaries );l, 41
EX-AMPLE 2.1
A relation R in Z can be defined by xKy if x > y.
Properties of Relations
(i) A relation R in S is ref7exive if xRx for every x in S.
(ii) A relation R in S is .n'l1lmetric if for x, y in S. ,'R, whenever xRy.
(iii) A relation R in S is transitive if for x, y and::: in S. xRz whenever xRy
and yR:::.
We note that the relation given in Example 2.1 is neither reflexive nor
symmetric. but transitive.
EXAMPLE 2.2
A relation R in {1, 2. 3. 4. 5. 6} is given by
{(l. 2). (2. 3), (3.4), (4. 4). (4, 5)}
This relation is not reflexive as 1R'L It is not symmetric as 2R3 but 3R'2. It
is also not transitive as 1R2 and 2R3 but 1R'3.
EXAMPLE 2.3
Let us define a relation R in {1. 2, .... 10} by aRb if a divides b. R IS
reflexive and transitive but not symmetric (3R6 but 6R'3).
EXAMPLE 2.4
If i, j, Il are integers we say that i is congruent to j modulo n (written as
i == j modulo Il or i == j mod 11) if i - j is divisible by 11. The 'congruence modulo
/1' is a relation which is reflexive and symmetric (if i - j is divisible by n, so
is j - i). If i == j mod 11 and j == k mod n, then \ve have i - j =an for some a
and j - k =bn for some b. So.
i - k = i - j + j - k = an + bn
which means that i == k mod n. Thus this relation is also transitive.
DefInition 2.3 A relation R in a set S is called an equivalence relation if it is
retlexive. symmetric and transitive.
Example 2.5 gives an equivalence relation in Z.