A Book of Abstract Algebra, Second Edition (1982)

Chapter 12. PARTITIONS AND EQUIVALENCE RELATIONS

Imagine emptying a jar of coins onto a table and sorting them into separate piles, one with the pennies, one with the nickels, one with the dimes, one with the quarters, and one with the half-dollars. This is a simple example of partitioning a set. Each separate pile is called a class of the partition; the jarful of coins has been partitioned into five classes.

Here are some other examples of partitions: The distributor of farm-fresh eggs usually sorts the daily supply according to size, and separates the eggs into three classes called “large,” “medium,” and “small.”

The delegates to the Democratic national convention may be classified according to their home state, thus falling into 50 separate classes, one for each state.

A student files class notes according to subject matter; the notebook pages are separated into four distinct categories, marked (let us say) “algebra,” “psychology,” “English,” and “American history.”

Every time we file, sort, or classify, we are performing the simple act of partitioning a set. To partition a set A is to separate the elements of A into nonempty subsets, say A₁, A₂, A₃ etc., which are called the classes of the partition. Any two distinct classes, say A_i and A_j are disjoint, which means they have no elements in common. And the union of the classes is all of A.

Instead of dealing with the process of partitioning a set (which is awkward mathematically), it is more convenient to deal with the result of partitioning a set. Thus, {A₁, A₂, A₃, A₄}, in the illustration above, is called a partitionof A. We therefore have the following definition:

A partition of a set A is a family {A_i: i ∈ I} of nonempty subsets of A which are mutually disjoint and whose union is all of A.

The notation {A_i: i ∈ I} is the customary way of representing a family of sets {A_i, A_j, A_k, …} consisting of one set A_i for each index i in I. (The elements of I are called indices’, the notation {A_i: i ∈ I} may be read: the family of sets A_i, as i ranges over I.)

Let {A_i: i ∈ I} be a partition of the set A. We may think of the indices i, j, k, … as labels for naming the classes A_i, A_j, A_k, .… Now, in practical problems, it is very inconvenient to insist that each class be named once and only once. It is simpler to allow repetition of indexing whenever convenience dictates. For example, the partition illustrated previously might also be represented like this, where A₁ is the same class as A₅, A₂ is the same as A₆, and A₃ is the same as A₇.

As we have seen, any two distinct classes of a partition are disjoint; this is the same as saying that if two classes are not disjoint, they must be equal. The other condition for the classes of a partition of A is that their union must be equal to A; this is the same as saying that every element of A lies in one of the classes. Thus, we have the following, more explicit definition of partition:

By a partition of a set A we mean a family {A_i: i ∈ I} of nonempty subsets of A such that

(i)If any two classes, say A_i and A_j, have a common element x (that is, are not disjoint), then A_i = A_j and

(ii)Every element x of A lies in one of the classes.

We now turn to another elementary concept of mathematics. A relation on a set A is any statement which is either true or false for each ordered pair (x, y) of elements of A. Examples of relations, on appropriate sets, are “x = y,” “x < y,” “x is parallel to y,” “x is the offspring of y,” and so on. An especially important kind of relation on sets is an equivalence relation. Such a relation, will usually be represented by the symbol ∼, so that x ∼ y may be read “x is equivalent to y.” Here is how equivalence relations are defined:

By an equivalence relation on a set A we mean a relation ∼ which is

Reflexive: that is, x ∼ x for every x in A;

Symmetric: that is, if x ∼ y, then y ∼ x; and

Transitive: that is, if x ∼ y and y ∼ z, then x ∼ z.

The most obvious example of an equivalence relation is equality, but there are many other examples, as we shall be seeing soon. Some examples from our everyday experience are “x weighs the same as y,” “x is the same color as y,” “x is synonymous with y,” and so on.

Equivalence relations also arise in a natural way out of partitions. Indeed, if {A_i: i ∈ I} is a partition of A, we may define an equivalence relation ∼ on A by letting x ∼ y iff x and y are in the same class of the partition.

In other words, we call two elements “equivalent” if they are members of the same class. It is easy to see that the relation ∼ is an equivalence relation on A. Indeed, x ∼ x because x is in the same class as x; next, if x and y are in the same class, then y and x are in the same class; finally, if x and y are in the same class, and y and z are in the same class, then x and z are in the same class. Thus, ∼ is an equivalence relation on A; it is called the equivalence relation determined by the partition {A_i: i ∈ I}.

Let ∼ be an equivalence relation on A and x an element of A. The set of all the elements equivalent to x is called the equivalence class of x, and is denoted by [x]. In symbols,

[x] = {y ∈ A: y ∼ x}

A useful property of equivalence classes is this:

Lemma If x∼ y, then [x] = [y].

In other words, if two elements are equivalent, they have the same equivalence class. The proof of this lemma is fairly obvious, for if x ∼ y, then the elements equivalent to x are the same as the elements equivalent to y.

For example, let us return to the jarful of coins we discussed earlier. If A is the set of coins in the jar, call any two coins “equivalent” if they have the same value: thus, pennies are equivalent to pennies, nickels are equivalent to nickels, and so on. If x is a particular nickel in A, then [x], the equivalence class of x, is the class of all the nickels in A. If y is a particular dime, then [y] is the pile of all the dimes; and so forth. There are exactly five distinct equivalence classes. If we apply the lemma to this example, it states simply that if two coins are equivalent (that is, have the same value), they are in the same pile. By the way, the five equivalence classes obviously form a partition of A; this observation is expressed in the next theorem.

Theorem If ∼ is an equivalence relation on A, the family of all the equivalence classes, that is, {[x]: x ∈ A), is a partition of A.

This theorem states that if ∼ is an equivalence relation on A and we sort the elements of A into distinct classes by placing each element with the ones equivalent to it, we get a partition of A.

To prove the theorem, we observe first that each equivalence class is a nonempty subset of A. (It is nonempty because x ∼ x, so x ∈ [x].) Next, we need to show that any two distinct classes are disjoint—or, equivalently, that if two classes [x] and [y] have a common element, they are equal. Well, if [x] and [y] have a common element u, then u ∼ x and u ∼ y. By the symmetric and transitive laws, x ∼ y. Thus, [x] = [y] by the lemma.

Finally, we must show that every element of A lies in some equivalence class. This is true because x ∈ [x]. Thus, the family of all the equivalence classes is a partition of A.

When ∼ is an equivalence relation on A and A is partitioned into its equivalence classes, we call this partition the partition determined by the equivalence relation ∼.

The student may have noticed by now that the two concepts of partition and equivalence relation, while superficially different, are actually twin aspects of the same structure on sets. Starting with an equivalence relation on A, we may partition A into equivalence classes, thus getting a partition of A. But from this partition we may retrieve the equivalence relation, for any two elements x and y are equivalent iff they lie in the same class of the partition.

Going the other way, we may begin with a partition of A and define an equivalence relation by letting any two elements be equivalent iff they lie in the same class. We may then retrieve the partition by partitioning A into equivalence classes.

As a final example, let A be a set of poker chips of various colors, say red, blue, green, and white. Call any two chips “equivalent” if they are the same color. This equivalence relation has four equivalence classes: the set of all the red chips, the set of blue chips, the set of green chips, and the set of white chips. These four equivalence classes are a partition of A.

Conversely, if we begin by partitioning the set A of poker chips into four classes according to their color, this partition determines an equivalence relation whereby chips are equivalent iff they belong to the same class. This is precisely the equivalence relation we had previously.

A final comment is in order. In general, there are many ways of partitioning a given set A; each partition determines (and is determined by) exactly one specific equivalence relation on A. Thus, if A is a set of three elements, say a, b, and c, there are five ways of partitioning A, as indicated by the accompanying illustration. Under each partition is written the equivalence relation determined by that partition.

Once again, each partition of A determines, and is determined by, exactly one equivalence relation on A.

EXERCISES

A. Examples of Partitions

Prove that each of the following is a partition of the indicated set. Then describe the equivalence relation associated with that partition.

1 For each integer r ∈ {0, 1, 2, 3, 4}, let A_r be the set of all the integers which leave a remainder of r when divided by 5. (That is, x ∈ A_r iff x = 5q + r for some integer q.) Prove: {A₀, A₁, A₂, A₃, A₄} is a partition of .

# 2 For each integer n, let A_n = {x ∈ : n ≤ x < n + 1}. Prove {A_n: n ∈ } is a partition of .

3 For each rational number r, let A_r = {(m, n) ∈ × *: m/n = r}. Prove that {A_r: r ∈ } is a partition of × *, where * is the set of nonzero integers.

4 For r ∈ {0, 1, 2, …, 9}, let A_r be the set of all the integers whose units digit (in decimal notation) is equal to r. Prove: {A₀, A₁, A₂, …, A₉} is a. partition of .

5 For any rational number x, we can write x = q + n/m where q is an integer and 0 ≤ n/m < 1. Call n/m the fractional part of x. For each rational r ∈ {x:0 ≤ x < 1}, let A_r = {x ∈ : the fractional part of x is equal to r}. Prove: {A_r: 0 ≤ r < 1} is a partition of .

6 For each r ∈ , let A_r = {(x, y) ∈ × : x − y = r}. Prove: {A_r: r ∈ } is a partition of × .

B. Examples of Equivalence Relations

Prove that each of the following is an equivalence relation on the indicated set. Then describe the partition associated with that equivalence relation.

1 In , m ∼ n iff |m| = |n|.

2 In , r ∼ s iff r − s ∈ .

3 Let ⌈x⌉ denote the greatest integer ≤ x. In , let a ∼ b iff ⌈a⌉ = ⌈b⌉.

4 In , let m ∼ n iff m − n is a multiple of 10.

5 In , let a ∼ b iff a − b ∈ .

6 In (), let f ∼ g iff f(0) = g(0).

7 In (), let f ∼ g iff f(x) = g(x) for all x > c, where c is some fixed real number.

8 If C is any set, P_C denotes the set of all the subsets of C. Let D ⊆ C. In P_C, let A ∼ B iff A ∩ D = B ∩ D.

9 In × , let (a, b) ∼ (c, d) iff a² + b² = c² + d².

10 In *, let a ∼ b iff a/b ∈ , where * is the set of nonzero real numbers.

C. Equivalence Relations and Partitions of ×

In parts 1 to 3, {A_r: r ∈ } is a family of subsets of × . Prove it is a partition, describe the partition geometrically, and give the corresponding equivalence relation.

# 1For each r ∈ , A_r = {(x, y): y = 2x + r}.

2For each r ∈ , A_r = {(x, y): x² + y² = r²}.

3For each r ∈ , A_r = {(x, y): y = |x| + r}.

In parts 4 to 6, an equivalence relation on × is given. Prove it is an equivalence relation, describe it geometrically, and give the corresponding partition.

4(x, y) ∼ (u, υ) iff ax² + by² = au² + bυ² (where a, b > 0).

5(x, y) ∼ (u, υ) iff x + y = u + υ

6(x, y) ∼ (u, υ) iff x² − y = u² − υ.

D. Equivalence Relations on Groups

Let G be a group. In each of the following, a relation on G is defined. Prove it is an equivalence relation. Then describe the equivalence class of e.

1 If H is a subgroup of G, let a ∼ b iff ab⁻¹ ∈ H

2 If H is a subgroup of G, let a ∼ b iff a^−xb ∈ H. Is this the same equivalence relation as in part 1? Prove, or find a counterexample.

3 Let a ∼ b iff there is an x ∈ G such that a = xbx⁻¹.

4 Let a ∼ b iff there is an integer k such that a^k = b^k

# 5 Let a ∼ b iff ab⁻¹ commutes with every x ∈ G.

6 Let a ∼ b iff ab⁻¹ is a power of c (where c is a fixed element of G).

E. General Properties of Equivalence Relations and Partitions

1 Let {A_i: i ∈ I} be a partition of A. Let {B_j: j ∈ J} be a partition of B. Prove that {A, × B_j, (i, j) ∈ I × J} is a partition of A × B.

2 Let ∼_I be the equivalence relation corresponding to the above partition of A, and let ∼_J be the equivalence relation corresponding to the partition of B. Describe the equivalence relation corresponding to the above partition of A × B.

3 Let f: A → B be a function. Define ∼ by a ∼ b iff f(a) = f(b). Prove that ∼ is an equivalence relation on A. Describe its equivalence classes.

4 Let f: A → B be a function, and let {B_i: i ∈ I} be a partition of B. Prove that {f⁻¹(B_i): i ∈ I} is a partition of A. If ∼_I is the equivalence relation corresponding to the partition of B, describe the equivalence relation corresponding to the partition of A. [REMARK: For any C ⊆ B, f⁻¹C) = {x ∈ A: f(x) ∈ C}.]

5 Let ∼₁ and ∼₂ be distinct equivalence relations on A. Define ∼₃ by a ∼₃ b iff a ∼₁ b and a ∼₂ b. Prove that ∼₃ is an equivalence relation on A. If [x], denotes the equivalence class of x for ∼_i (i = 1, 2, 3), prove that [x]₃ = [x]₁ ∩ [x]₂.