126 Chapter 11

Proof. (1) Since a ∼ a by reflexivity, it follows that a ∈ [a], and so [a] is definitely

nonempty.

(2) Suppose that x is a common element of [a] and [b]. So a ∼ x and also b ∼ x. To show

that [a] = [b], we shall show that [a] ⊆ [b] and conversely. To show this, suppose that

c ∈ [a]. So c ∼ a and, consequently, c ∼ x by transitivity. But since x ∼ b, we conclude

that c ∼ b by transitivity again. So c ∈ [b]. Thus, we have proved that [a] ⊆ [b]. An

essentially identical argument establishes that [b] ⊆ [a], and so they are equal: [a] = [b].

(3) Since a ∈ [a], the union of all the equivalence classes



a∈A

[a] includes every element

of A, and so it is equal to A.

Let us now consider the converse implication.

Theorem 93. Every partition on a set A is the set of equivalence classes for some equiva-

lence relation.

Proof. Suppose that F is a partition of A.SoF is a family of nonempty subsets of A,

which are pairwise disjoint and which union up to A. Let us define a binary relation ∼ on A

by saying that a ∼ b for a, b ∈ A if and only if there is some X ∈Fwith a, b ∈ X. In other

words, two points are ∼-equivalent if they belong in common to a piece of the partition.

Let us argue in detail that ∼ is an equivalence relation. First, I claim that ∼ is reflexive.

To see this, consider an arbitrary element a ∈ A. Since the union of the sets in F is all of

A, there must be some X ∈Fwith a ∈ X. In this case, a is in the same piece of F as itself,

and so a ∼ a. So the relation is reflexive. Symmetry is easy, since if a ∼ b, then there is

some X ∈Fwith a, b ∈ X, and the same X will witness that b ∼ a. Finally, for transitivity,

assume that a ∼ b and b ∼ c

. From a ∼ b we know that a, b ∈ X for some X ∈F. From

b ∼ c we know that b, c ∈ Y for some Y ∈F. Since b is in both X and Y, it follows that X

and Y are not disjoint, and so we must have X = Y since the sets in F are pairwise disjoint.

Thus, all three points are in the same piece of the partition a, b, c ∈ X = Y. In particular,

we know that a ∼ c, and so the relation is transitive.

Finally, we note that the partition F is exactly the collection of equivalence classes of ∼.

The reason is that if a ∈ X for some X ∈F, then every b ∈ X will be ∼-equivalent to a,

and only these, and so X = [a]. Thus, the original partition F is exactly the collection of

equivalence classes arising from ∼.

Define that one equivalence relation E refines another equivalence relation F on the

same domain A if aEbimplies aFbfor all a, b ∈ A. For example, the relation of

congruency of triangles in the Euclidean plane refines the relation of similarity of triangles,

since congruent triangles are necessarily similar. For another example, the relation of

congruency modulo 10 in the integers refines the relation of congruency modulo 5, because

if two numbers have the same remainder when dividing by 10, then they will also have the

same remainder when dividing by 5.