Equivalence Relations
A binary relation over a set S is called an
equivalence relation if it has following properties
1. Reflexivity: for all element xS, x x
2. Symmetry: for all elements x and y, x y if and
only if y x
3. Transitivity: for all elements x, y and z, if x y and
y z then x z
The relation “is related to” is an equivalence
relation over the set of people
Lecture No.34
Data Structure
Dr. Sohail Aslam
Equivalence Relations
The relationship is not an equivalence
relation.
It is reflexive, since x x,
and transitive, since x y and y z
implies x z,
it is not symmetric since x y does not
imply y x.
Equivalence Relations
Electrical connectivity, where all connections are
by metal wires, is an equivalence relation.
It is clearly reflexive, since any component is
connected to itself.
It is symmetric because if component a is
connected to component b then b must be
electrically connected to a.
It is transitive, since if component a is connected
to component b and b is connected to c then a is
connected to c.
The Disjoint Sets View
An equivalence relation over a set S
can be viewed as a partitioning of S into
disjoint sets.
Each set of the partition is called an
equivalence class of (all elements that
are related).