Page 633 - Discrete Mathematics and Its Applications

612 9 / Relations

Equivalence Classes and Partitions

Let A be the set of students at your school who are majoring in exactly one subject, and let R
be the relation on A consisting of pairs (x, y), where x and y are students with the same major.
Then R is an equivalence relation, as the reader should verify. We can see that R splits all
students in A into a collection of disjoint subsets, where each subset contains students with
a specified major. For instance, one subset contains all students majoring (just) in computer
science, and a second subset contains all students majoring in history. Furthermore, these sub-
sets are equivalence classes of R. This example illustrates how the equivalence classes of an
equivalence relation partition a set into disjoint, nonempty subsets. We will make these notions
more precise in the following discussion.
Let R be a relation on the set A. Theorem 1 shows that the equivalence classes of two
elements of A are either identical or disjoint.

THEOREM 1 Let R be an equivalence relation on a set A. These statements for elements a and b of A are
equivalent:
(i) aRb (ii) [a]=[b] (iii) [a]∩[b] =∅

Proof: We first show that (i) implies (ii). Assume that aRb. We will prove that [a]=[b] by
showing [a]⊆[b] and [b]⊆[a]. Suppose c ∈[a].Then aRc. Because aRb and R is symmetric,
we know that bRa. Furthermore, because R is transitive and bRa and aRc, it follows that bRc.
Hence, c ∈[b]. This shows that [a]⊆[b]. The proof that [b]⊆[a] is similar; it is left as an
exercise for the reader.
Second, we will show that (ii) implies (iii). Assume that [a]=[b]. It follows that
[a]∩[b] =∅ because [a] is nonempty (because a ∈[a] because R is reflexive).
Next, we will show that (iii) implies (i). Suppose that [a]∩[b] =∅. Then there is an
element c with c ∈[a] and c ∈[b]. In other words, aRc and bRc. By the symmetric
property, cRb. Then by transitivity, because aRc and cRb,wehave aRb.
Because (i) implies (ii), (ii) implies (iii), and (iii) implies (i), the three statements, (i), (ii),
and (iii), are equivalent.

We are now in a position to show how an equivalence relation partitions a set. Let R be an
equivalence relation on a set A. The union of the equivalence classes of R is all of A, because
an element a of A is in its own equivalence class, namely, [a] R . In other words,

[a] R = A.
a∈A
In addition, from Theorem 1, it follows that these equivalence classes are either equal or disjoint,
so
[a] R ∩[b] R =∅,

when [a] R =[b] R .
Recall that an index set is These two observations show that the equivalence classes form a partition of A, because
a set whose members they split A into disjoint subsets. More precisely, a partition of a set S is a collection of disjoint
label, or index, the nonempty subsets of S that have S as their union. In other words, the collection of subsets A i ,
elements of a set.
i ∈ I (where I is an index set) forms a partition of S if and only if
A i =∅ for i ∈ I,

A i ∩ A j =∅ when i = j,