Page 634 - Discrete Mathematics and Its Applications

9.5 Equivalence Relations 613

A 2
A 1
A 3
A 4
A 7 A 5
A
A 8 6
A 9

FIGURE 1 A Partition of a Set.

and

A i = S.
i∈I

(Here the notation i∈I A i represents the union of the sets A i for all i ∈ I.) Figure 1 illustrates
the concept of a partition of a set.

EXAMPLE 12 Suppose that S ={1, 2, 3, 4, 5, 6}. The collection of sets A 1 ={1, 2, 3}, A 2 ={4, 5}, and
A 3 ={6} forms a partition of S, because these sets are disjoint and their union is S. ▲

We have seen that the equivalence classes of an equivalence relation on a set form a partition
of the set. The subsets in this partition are the equivalence classes. Conversely, every partition
of a set can be used to form an equivalence relation. Two elements are equivalent with respect
to this relation if and only if they are in the same subset of the partition.
To see this, assume that {A i | i ∈ I} is a partition on S. Let R be the relation on S consisting
of the pairs (x, y), where x and y belong to the same subset A i in the partition. To show that R
is an equivalence relation we must show that R is reflexive, symmetric, and transitive.
We see that (a, a) ∈ R for every a ∈ S, because a is in the same subset as itself. Hence, R
is reflexive. If (a, b) ∈ R, then b and a are in the same subset of the partition, so that (b, a) ∈ R
as well. Hence, R is symmetric. If (a, b) ∈ R and (b, c) ∈ R, then a and b are in the same
subset X in the partition, and b and c are in the same subset Y of the partition. Because the subsets
of the partition are disjoint and b belongs to X and Y, it follows that X = Y. Consequently, a
and c belong to the same subset of the partition, so (a, c) ∈ R. Thus, R is transitive.
It follows that R is an equivalence relation. The equivalence classes of R consist of subsets
of S containing related elements, and by the definition of R, these are the subsets of the partition.
Theorem 2 summarizes the connections we have established between equivalence relations and
partitions.

THEOREM 2 Let R be an equivalence relation on a set S. Then the equivalence classes of R form a partition
of S. Conversely, given a partition {A i | i ∈ I} of the set S, there is an equivalence relation
R that has the sets A i , i ∈ I, as its equivalence classes.

Example 13 shows how to construct an equivalence relation from a partition.

EXAMPLE 13 List the ordered pairs in the equivalence relation R produced by the partition A 1 ={1, 2, 3},
A 2 ={4, 5}, and A 3 ={6} of S ={1, 2, 3, 4, 5, 6}, given in Example 12.