Then a relation on S and T is
{
}
R
a y c w c z d y
= ( , ), ( , ), ( , ), ( , )
The four ordered pairs in the relation is represented as shown in Fig. 2.
Equiv a lence Rela tion
A subset R of A A
× is called an equivalence relation on A if R satisfies the
following conditions:
(i) ( , )
a a R
∈ for all a A
∈ (R is reflexive)
(ii) If ( , )
a b R
∈ , then ( , )
b a R
∈ , then ( , )
a b R
∈ (R is symmetric)
(iii) If ( , )
a b R
∈ and ( , )
b c R
∈ , then ( , )
a c R
∈ (R is transitive)
Par tial Order ing Rela tions
A relation R on a set S is called a “Partial ordering” or a “Partial order”, if R is
reflexive, antisymmetric and transitive.
A set S together with a partial ordering R is called a “Partially ordered set”
or “Poset”.
Example: The relation ≤ on the set R of real numbers is reflexive,
antisymmetric and transitive. Therefore ≤ is a “Partial ordering”.
Par ti tion
A Partition P of S is a collection {A i } of nonempty subsets of S with the
properties:
(i) Each a S
∈ belongs to some A i ,
(ii) If A A
i
j
≠ , then A
A
i
j
∩
= ∅.
Thus a partition P of S is a subdivision of S into disjoint nonempty sets.
If R is an equivalence relation on a set S, for each ‘a’ in S, let [a] denote the
set of elements of S to which ‘a’ is related under R, i.e.
[ ] { : ( , )
}
a
x a x R
=
∈
Here [a] is the Equivalence class” of ‘a’ in S.
Introduction
9
a
b
c
d
e
w
x
y
z
Fig. 2 Rela tion R = {(a, y), (c, w), (c, w), (c, z), (d, y)}