THEORY OF COMPUTATION
Equivalence & Partial Order Relations
[MATHEMATICAL PRELIMINARIES]
Jabin T H
Asst. Professor,
Dept. of Computer Applications Reference:
MES Asmabi College, P Vemballur KLP Mishra, Theory of Computer Science, M Chandrasekaran, Third Edition. CSHYTC
Equivalence Relation 2
A Relation R on a set A is said to be an equivalent relation if and only if R is
Reflexive, Symmetric and Transitive.
A={1,2,3,4}
R={(1,1),(1,2),(2,2),(2,1),(3,3),(4,4)}
R is an example of Equivalence relation
Prove that congruence modulo n over the set of integers is an
equivalence relation 3
x y mod n
i.e.; x-y = divisible by n
xRy: x y mod n; x, y, n z+
We have to prove R is reflexive, symmetric and transitive
Proof:
4
Reflexive
For every x∈Z+, we have x-x=0
x x mode n
x-x divisible by n
i.e.; 0 divisible by n
Hence the relation is reflexive
Proof:
Symmetric 5
We have to prove (x,y) R (y,x) R
Assume (x,y) R
x y mod n
x-y = kn, k Z+
Putting minus sign on both sides
-(x-y) = -kn
y-x = -kn, k Z+
(y,x) R
Proof:
Transitive 6
We have to prove (x,y) R & (y,z) R (x,z) R
Assume (x,y) R
x y mod n
+
x-y = k1n, k1 Z ...................................... (1)
(y,z) R y z mod n
+
y-z = k2n k2 Z ……………………… (2)
(1) + (2) = x-y+y-z = k1n + k2n
+
x-z = (k1 + k2 )n x-z = k3n k3 Z
x z mod n (x,z) R, Hence the relation is Transitive
7
Congruence Modulo n relation is Reflective, Symmetric and Transitive.
Therefore it is an equivalence Relation.
Hence the proof.
Partial Order Relation
8
A relation R is said to be partial order relation if it is reflexive,
transitive and anti-symmetric.
E.g.: xRy : x y, x,y Z+
Proof:
Reflexive:
(x,x) R, x x
Hence the relation is reflexive
9
Proof:
Transitive
We have to prove (x,y)R & (y,z)R (x,z)R
(x,y)R x y ………………. (1)
(y,z)R y z ………………. (2)
From (1) & (2)
x y z x z (x,z) R
Hence the relation is transitive
Proof: 10
Antisymmetric:
We have to prove (x,y) R and (y,x) R x=y
(x,y) R x y …………………. (1)
(y,x) R y x …………………. (2)
From (1) & (2)
x=y
Hence the relation is antisymmetric
So the relation xRy : x y, x,y Z+ is reflexive, transitive and antisymmetric.
Hence the relation is a partial order relation.
11
