Let x y z N
, , ∈ . Then
(a) As x – x = 0 m., x x
≡ (mod m), for all x N
∈ . Therefore this
relation is reflexive
(b) x y
m
x y km
k
x = k m
y x
≡
⇒ − =
⇒
−
⇒ ≡
(
)
,
( )
(
mod
for integer
–
m
y
od m)
Therefore the relation is symmetric.
(c) x y
≡ (mod m) and y z
≡ (mod m)
⇒ − =
− =
⇒ − + − = +
x y km and y z lm
k l
x y
y z
k l m
for integers , .
(
) (
) (
)
⇒ − = +
⇒ ≡
+
(
) (
)
(mod )
x z
k l m
x z
m
k l
since
is also an integer
Therefore the relation is transitive.
Since the relation is reflexive, symmetric and transitive, the relation
“congruence modulo m” is an equivalence relation.
Ì Exam ple 0.1.13: Give examples of relations R on A = {1, 2, 3} with
(a) R being both symmetric and antisymmetric
(b) R being neither symmetric nor antisymmetric
Solu tion
A possible set of examples are:
(a)
{
}
R = ( , ), ( , )
11 2 2
(b)
{
}
R = ( , ), ( , ), ( , )
12 21 2 3
Ì Exam ple 0.1.14: Given the relation R in A as
{
}
R = (1,1), (2,2), (2,3), (3,2), (4,2), (4,4)
(a) Is R (i) reflexive (ii) symmetric (iii) transitive?
(b) Is R antisymmetric?
(c) Determine R
2 .
Solu tion
(a) (i) R is not reflexive because
3 ∈
/
A
R
but 3 3, i.e. ( , )
3 3 ∉ R
(ii) R is not symmetric because
4R2 but 2 4
/
R , i.e.,( , )
4 2 ∈ R but ( , )
2 4 ∉ R
(iii) R is not transitive because
4R2 and 2R3 but 4 3
/
R , i.e.,
( , )
, ( , )
4 2
2 3
∈
∈
R
R but ( , )
4 3 ∉ R
Introduction
11