Discrete MathematicsbySection 6.5
and Its Applications 4/EKenneth RosenTP 1 Section 6.5
Equivalence RelationsNow we group properties of relations together to define
new types of important relations.
___________
Definition: A relation R on a set A is an equivalence
relation iff R is
? reflexive
? symmetric
and
? transitive
_______
It is easy to recognize equivalence relations using
digraphs.
? The subset of all elements related to a particular
element forms a universal relation (contains all possible
arcs) on that subset. The (sub)digraph representing the
subset is called a complete (sub)digraph. All arcs are
present.
? The number of such subsets is called the rank of the
equivalence relation
______
Discrete MathematicsbySection 6.5
and Its Applications 4/EKenneth RosenTP 2 Examples:
A has 3 elements:rank = 3rank = 2
Discrete MathematicsbySection 6.5
and Its Applications 4/EKenneth RosenTP 3rank = 2rank = 2rank = 1
Discrete MathematicsbySection 6.5
and Its Applications 4/EKenneth RosenTP 4 ___________
? Each of the subsets is called an equivalence class.
? A bracket around an element means the equivalence
class in which the element lies.
[x] = {y |

is in R}
? The element in the bracket is called a representative
of the equivalence class. We could have chosen any one.
________
Examples:abc[a] = {a, c}, [c] = {a, c}, [b] = {b}.
rank = 2
________
An interesting counting problem:
Discrete MathematicsbySection 6.5
and Its Applications 4/EKenneth RosenTP 5 Count the number of equivalence relations on a set A with
n elements. Can you find a recurrence relation?
The answers are
? 1 for n = 1
? 3 for n = 2
? 5 for n = 3
How many forn = 4?
____________
Definition: Let S
1, S
2, . . ., S
n be a collection of subsets
of A. Then the collection forms a partition of A if the
subsets are nonempty, disjoint and exhaust A:
? S
i ¹ Æ? S
iÇS
j = Æ if i ¹ j
? U S
i = A
Discrete MathematicsbySection 6.5
and Its Applications 4/EKenneth RosenTP 6ASSS234SS15___________
Theorem: The equivalence classes of an equivalence
relation R partition