Bridge to Abstract Mathematics: Mathematical Proof and Structures

7.3 EQUIVALENCE CLASSES AND PARTITIONS 241

Condition (i) states that each cell is nonempty. Condition (ii) asserts that
any two cells are either identical or disjoint (or equivalently that any two
distinct cells are disjoint; recall from Chapter 2 that p v q and -p -+ q are
equivalent). Condition (iii) requires that every element of A fall within at
least one of the cells. The division of the real numbers into positive and
negative numbers and zero is an example of a "three-celled" partition of
R. Cells consisting of all rational and all irrational numbers provide a two-
celled partition of R, whereas the odd and even integers yield a two-
celled partition of Z. Any set A can be partitioned into a collection of sin-
gleton cells by '$3 = { {x) 1 x E A). If A is infinite, the latter will constitute a
partition with infinitely many cells. Another example of a partition having
infinitely many cells is the partition v1 = ((01, (- 1, 11, (-2,2},.. .} of

2. Even small sets, such as A = {1,2,3,4,5), have a large number of par-
   titions, for example, {(l,5), {3,4), (2)) and {{l,2, 3, 51, (4)). Determin-
   ing the number of partitions of an n-element set is a difficult counting
   problem.
   One connection between partitions and equivalence relations lies in the
   fact that any partition Clg of a set A yields, in a canonical (i.e., standard)
   way, a corresponding equivalence relation.

THEOREM 1

Let A be a nonempty set and '$I a partition of A. Define a relation - on A by

the rule x -- y if and only if there exists a cell X E '$ such that x E X and y~ X.

Then -- is an equivalence relation on A.

Proof We must prove that - is reflexive, symmetric, and transitive.

(R) Let x E A be given. By (iii) of Definition 1, x lies in some cell

of the partition. Clearly x lies in the same cell as itself so that x - x.

(S) Given x, y E A, suppose x - y so that x and y lie in some cell of

v. Clearly then y and x lie in that same cell of Clg, so that y - x, as

desired.

(T) Given x, y, z E A, suppose that x - y and y - z. To prove x - z,

we must show that there is some cell X E '$3 such that x E X and z E X.

Now since x - y, then there is a cell XI of '$3 such that both x and y are

elements of XI. Since y -- z, there is a cell X, containing both y and z.

Since y E X1 n X2, then X1 = X,, by (ii) of Definition 1. Let X be this

set XI (=X,) and note that x and z lie in X, as desired. 17

Because the equivalence relation - of Theorem 1 is derived from a given

partition 9 of A in a canonical way, we label it by the symbol Alp, and

call it the equivalence relation determined by the partition v.

EXAMPLE 1 Given the partition ']P = ((21, (1,3,4), (5)) of the set A =

{1,2, 3,4, 51, list explicitly the ordered pairs in the corresponding equiva-

lence relation Alp.