Functions and Relations 125
But hang on. Elsewhere in this book, I have emphasized the mathematical habit of mind
that one should distinguish sharply between examples and proof. And surely it is a com-
mon mistake amongst beginners to confuse example with proof. Yet, the proof we have just
given of theorem 90 appears to have the character of giving examples rather than giving a
general argument. Have we made the beginner’s mistake? How can we have proved a the-
orem with an example? The answer is that, indeed, one cannot prove a universal statement
by providing an example, and most theorems in mathematics are universal assertions. Nev-
ertheless, theorem 90 is not a universal statement but an existential statement: it is stating
that certain kinds of binary relations exist. Such statements can of course be proved simply
by exhibiting a successful instance.
11.3 Equivalence classes and partitions
For each object a in the domain of an equivalence relation ∼, the equivalence class of a,
denoted by [a]orby[a]
∼
when one wants especially to clarify which equivalence relation
is being used, is the set of all objects equivalent to a:
[a] = {b | a ∼ b }.
If ∼ is an equivalence relation, then the set of equivalence classes form what is called a
partition of the domain.
A
[a]
[d]
Definition 91. A partition of a set A is a family of nonempty pairwise-disjoint subsets of
A, whose union is all of A.
To be pairwise disjoint means that if X and Y are distinct sets in the family, then X∩Y = ∅.
Thus, a partition is a dividing up of the set A into distinct nonoverlapping regions, each
containing part of A.
Theorem 92. Suppose that ∼ is an equivalence relation on a set A.
1. Every equivalence class [a] is nonempty.
2. If equivalence classes [a] and [b] have elements in common, then they are equal.
3. The union of all the equivalence classes is A.
Thus, the set of equivalence classes form a partition of A.