2.6. EQUIVALENCE RELATIONS AND SET PARTITIONS
i
“bookmt” — 2006/8/8 — 12:58 — page 125 — #137
i
i
2.6. EQUIVALENCE RELATIONS AND SET PARTITIONS
125
(a) Show that the center of a group G is a normal subgroup of G.
(b) What is the center of the group S3?
2.5.14.
(a) What is the center of the group D4 of symmetries of the square?
(b) What is the center of the dihedral group Dn?
2.5.15. Find the center of the group GL.2; R/ of 2-by-2 invertible real matrices. Do the same for GL.3; R/. Hint: It is a good idea to go outside of the realm of invertible matrices in considering this problem. This is because it is useful to exploit linearity, but the group of invertible matrices is not a linear space. So first explore the condition for a matrix A to commute with all matrices B, not just invertible matrices. Note that the condition AB D BA is linear in B, so a matrix A commutes with all matrices if, and only if, it commutes with each member of a linear spanning set of matrices. So now consider the so-called matrix units Eij , which have a 1 in the i; j position and zeros elsewhere. The set of matrix units is a basis of the linear space of matrices. Find the condition for a matrix to commute with all of the Eij ’s. It remains to show that if a matrix commutes with all invertible matrices, then it also commutes with all Eij ’s. (The results of this exercise hold just as well with the real numbers R replaced by the complex numbers C or the rational numbers Q.)
2.5.16. Show that the symmetric group Sn has a unique subgroup of index 2, namely the subgroup An of even permutations. Hint: Such subgroup N is normal. Hence if it contains one element of a certain cycle structure, then it contains all elements of that cycle structure, according to Exercises 2.6.6 and 2.4.14. Can N contain any 2–cycles? Show that N contains a product of k 2–cycles if, and only if, k is even, by using Exercise Conclude N D An by Proposition 2.4.22.
2.6. Equivalence Relations and Set Partitions
Associated to the data of a group G and a subgroup H , we can define a binary relation on G by a b .modH / or a H b if, and only if, aH D bH . According to Proposition 2.5.3, a H b if, and only if, if b 1a 2 H . This relation has the following properties: 1. a H a.
2. a H b , b H a.
3. If a H b and b H c, then also a H c.
This is an example of an equivalence relation.
i
i
i
i
i
“bookmt” — 2006/8/8 — 12:58 — page 126 — #138
i
i
126
2. BASIC THEORY OF GROUPS Definition 2.6.1. An equivalence relation on a set X is a binary relation with the properties: (a) Reflexivity: For each x 2 X, x x.
(b) Symmetry: For x; y 2 X, x y , y x.
(c) Transitivity: For x; y; z 2 X, if x y and y z, then x z.
Associated to the same data (a group G and a subgroup H ), we also have the family of left cosets of H in G. Each left coset is nonempty, distinct left cosets are mutually disjoint, and the union of all left cosets is G. This is an example of a set partition.
Definition 2.6.2. A partition of a set X is a collection of mutually disjoint nonempty subsets whose union is X .
Equivalence relations and set partitions are very common in mathe matics. We will soon see that equivalence relations and set partitions are two aspects of one phenomenon.
Example 2.6.3.
(a) For any set X , equality is an equivalence relation on X . Two elements x; y 2 X are related if, and only if, x D y.
(b) For any set X , declare x y for all x; y 2 X. This is an equivalence relation on X .
(c) Let n be a natural number. Recall the relation of congruence modulo n defined on the set of integers by a b .mod n/ if, and only if, a b is divisible by n. It was shown in Proposition 1.7.2 that congruence modulo n is an equivalence relation on the set of integers. In fact, this is a special case of the coset equivalence relation, with the group Z, and the subgroup nZ D fnd W d 2 Zg.
(d) Let X and Y be any sets and f W X ! Y any map. Define a relation on X by x0 f x00 if, and only if, f .x0/ D f .x00/. Then f is an equivalence relation on X.
(e) In Euclidean geometry, congruence is an equivalence relation on the set of triangles in the plane. Similarity is another equivalence relation on the set of triangles in the plane.
(f) Again in Euclidean geometry, parallelism of lines is an equivalence relation on the set of all lines in the plane.
(g) Let X be any set, and let T W X ! X be an bijective map of X . All integer powers of T are defined and for integers m; n, we have T n ı T m D T nCm. In fact, T is an element of the group i
i
i
i
of all bijective maps of X , and the powers of T are defined as elements of this group. See the discussion preceding Definition 2.2.11.
For x; y 2 X, declare x y if there is an integer n such that T n.x/ D y. Then is an equivalence relation on X. In fact, for all x 2 X, x x because T 0.x/ D x. If x; y 2 X and x y, then T n.x/ D y for some integer n; it follows that T n.y/ D x, so y x. Finally, suppose that x; y; z 2 X, x y, and y z. Then there exist integers n; m such that T n.x/ D y and T m.y/ D z. But then T nCm.x/ D T m.T n.x// D T m.y/ D z, so x z.
An equivalence relation on a set X always gives rise to a distinguished family of subsets of X : Definition 2.6.4. If is an equivalence relation on X, then for each x 2
X , the equivalence class of x is the set Œx D fy 2 X W x yg: Note that x 2 Œx because of reflexivity; in particular, the equivalence classes are nonempty subsets of X .
Proposition 2.6.5. Let be an equivalence relation on X. For x; y 2 X, x y if, and only if, Œx D Œy.
Proof. If Œx D Œy, then x 2 Œx D Œy, so x y. For the converse, suppose that x y (and hence y x, by symmetry of the equivalence relation). If z 2 Œx, then z x. Since x y by assumption, transitivity of the equivalence relation implies that z y (i.e., z 2 Œy). This shows that Œx Œy. Similarly, Œy Œx. Therefore, Œx D Œy.
n
Corollary 2.6.6. Let be an equivalence relation on X, and let x; y 2 X.
Then either Œx \ Œy D ; or Œx D Œy.
Proof. We have to show that if Œx \ Œy ¤ ;, then Œx D Œy. But if z 2 Œx \ Œy, then Œx D Œz D Œy, by the proposition.
n
Consider an equivalence relation on a set X. The equivalence classes of are nonempty and have union equal to X, since for each x 2 X, x 2 Œx. Furthermore, the equivalence classes are mutually disjoint; this i
i
i
i
2. BASIC THEORY OF GROUPS means that any two distinct equivalence classes have empty intersection.
So the collection of equivalence classes is a partition of the set X .
Any equivalence relation on a set X gives rise to a partition of X by equivalence classes.
On the other hand, given a partition P of X , we can define an relation on X by x P y if, and only if, x and y are in the same subset of the partition. Let’s check that this is an equivalence relation. Write the partition P as fXi W i 2 I g. We have Xi ¤ ; for all i 2 I , Xi \ Xj D ; if i ¤ j , and [i2I Xi D X. Our definition of the relation is x P y if, and only if, there exists i 2 I such that both x and y are elements of Xi .
Now for all x 2 X, x P x because there is some i 2 I such that x 2 Xi . The definition of x P y is clearly symmetric in x and y. Finally, if x P y and y P z, then there exist i 2 I such that both x and y are elements of Xi , and furthermore there exists j 2 I such that both y and z are elements of Xj . Now i is necessarily equal to j because y is an element of both Xi and of Xj and Xi \ Xj D ; if i ¤ j . But then both x and z are elements of Xi , which gives x P z.
Every partition of a set X gives rise to an equivalence relation on X .
Suppose that we start with an equivalence relation on a set X , form the partition of X into equivalence classes, and then build the equivalence relation related to this partition. Then we just get back the equivalence relation we started with! In fact, let be an equivalence relation on X, let P D fŒx W x 2 Xg be the corresponding partition of X into equivalence classes, and let P denote the equivalence relation derived from P . Then x y , Œx D Œy , there exists a Œz 2 P such that both x and y are elements of Œz , x P y.
Suppose, on the other hand, that we start with a partition of a set X , form the associated equivalence relation, and then form the partition of X consisting of equivalence classes for this equivalence relation. Then we end up with exactly the partition we started with. In fact, let P be a partition of X , let P be the corresponding equivalence relation, and let P 0 be the family of P equivalence classes. We have to show that P D P 0.
Let a 2 X, let Œa be the unique element of P 0 containing a, and let A be the unique element of P containing a. We have b 2 Œa , b P a , there exists a B 2 P such that both a and b are elements of B. But since a 2 A, the last condition holds if, and only if, both a and b are elements of A. That is, Œa D A. But this means that P and P 0 contain exactly the same subsets of X .
The following proposition summarizes this discussion:
Proposition 2.6.7. Let X be any set. There is a one to one correspondence between equivalence relations on X and set partitions of X .
i
i
i
i
i
“bookmt” — 2006/8/8 — 12:58 — page 129 — #141
i
i
2.6. EQUIVALENCE RELATIONS AND SET PARTITIONS
129
Remark 2.6.8. This proposition, and the discussion preceding it, are still valid (but completely uninteresting) if X is the empty set. There is exactly one equivalence relation on the empty set, namely the empty relation, and there is exactly one partition of the empty set, namely the empty collection of nonempty subsets!
Example 2.6.9. Consider a group G and a subgroup H . Associated to these data, we have the family of left cosets of H in G. According to Proposition 2.5.4, the family of left cosets of H in G forms a partition of G. We defined the equivalence relation H in terms of this partition, namely a H b if, and only if, aH D bH . The equivalence classes of H are precisely the left cosets of H in G, since a H b , aH D bH , a 2 bH .
Example 2.6.10.
(a) The equivalence classes for the equivalence relation of equality on a set X are just the singletons fxg for x 2 X.
(b) The equivalence relation x y for all x; y 2 X has just one equivalence class, namely X .
(c) The equivalence classes for the relation of congruence modulo n on Z are fŒ0; Œ1; : : : ; Œn 1g.
(d) Let f W X ! Y be any map. Define x0 f x00 if, and only if, f .x0/ D f .x00/. The equivalence classes for the equivalence relation f are the fibers of f , namely the sets f 1.y/ for y in the range of f .
(e) Let X be any set, and let T W X ! X be an bijective map of X . For x; y 2 X, declare x y if there is an integer n such that T n.x/ D y. The equivalence classes for this relation are the orbits of T , namely the sets O.x/ D fT n.x/ W n 2 Zg for x 2 X.
Equivalence Relations and Surjective Maps
There is a third aspect to the phenomenon of equivalence relations and partitions. We have noted that for any map f from a set X to another set Y , we can define an equivalence relation on X by x0 f x00 if f .x0/ D f .x00/. We might as well assume that f is surjective, as we can replace Y by the range of f without changing the equivalence relation. The equivalence classes of f are the fibers f 1.y/ for y 2 Y . See Exercise 2.6.1.
On the other hand, given an equivalence relation on X, define X= to be the set of equivalence classes of and define a surjection of X onto X= by .x/ D Œx. If we now build the equivalence relation
i
i
i
i
i
“bookmt” — 2006/8/8 — 12:58 — page 130 — #142
i
i
130
2. BASIC THEORY OF GROUPS associated with this surjective map, we just recover the original equivalence relation. In fact, for x0; x00 2 X, we have x0 x00 , Œx0 D Œx00 , .x0/ D .x00/ , x0 x00.
We have proved the following result:
Proposition 2.6.11. Let be an equivalence relation on a set X. Then there exists a set Y and a surjective map W X ! Y such that is equal to the equivalence relation .
When do two surjective maps f W X ! Y and f 0 W X ! Y 0 deter mine the same equivalence relation on X ? The condition for this to happen turns out to be the following:
Definition 2.6.12. Two surjective maps f W X ! Y and f 0 W X ! Y 0 are similar if there exists a bijection s W Y ! Y 0 such that f 0 D s ı f .
f 0
X
qqqqq
Y 0
q qqqq f
∼ = s
qqqq
Y
Proposition 2.6.13. Two surjective maps f W X ! Y and f 0 W X ! Y 0 determine the same equivalence relation X if, and only if, f and f 0 are similar.
Proof. It is easy to see that if f and f 0 are similar surjections, then they determine the same equivalence relation on X .
Suppose, on the other hand, that f W X ! Y and f 0 W X ! Y 0 are surjective maps that define the same equivalence relation on X. We want to define a map s W Y ! Y 0 such that f 0 D s ı f . Let y 2 Y , and choose any x 2 f 1.y/. We wish to define s.y/ D f 0.x/, for then s.f .x// D s.y/ D f 0.x/, as desired. However, we have to be careful to check that this makes sense; that is, we have to check that s.y/ really depends only on y and not on the choice of x 2 f 1.y/! But in fact, if Nx is another element of f 1.y/, then x f Nx, so x f 0 Nx, by hypothesis, so f 0.x/ D f 0. Nx/.
i
i
i
i
i
“bookmt” — 2006/8/8 — 12:58 — page 131 — #143
i
i
2.6. EQUIVALENCE RELATIONS AND SET PARTITIONS
131
We now have our map s W Y ! Y 0 such that f 0 D s ı f . It remains to show that s is a bijection.
In the same way that we defined s, we can also define a map s0 W Y 0 !
Y such that f D s0 ı f 0. I claim that s and s0 are inverse maps, so both are bijective. In fact, we have f D s0 ı f 0 D s0 ı s ı f , so f .x/ D s0.s.f .x/// for all x 2 X. Let y 2 Y ; choose x 2 X such that y D f .x/. Substituting y for f .x/ gives y D s0.s.y//. Similarly, s.s0.y0// D y0 for all y0 2 Y 0.
This completes the proof that s is bijective.
n
Let us look again at our main example, the equivalence relation on a group G determined by a subgroup H , whose equivalence classes are the left cosets of H in G. We would like to define a canonical surjective map on G whose fibers are the left cosets of H in G.
Definition 2.6.14. The set of left cosets of H in G is denoted G=H . The surjective map W G ! G=H defined by .a/ D aH is called the canonical projection or quotient map of G onto G=H .
Proposition 2.6.15. The fibers of the canonical projection W G ! G=H
are the left cosets of H in G. The equivalence relation on G determined by is the equivalence relation H .
Proof. We have 1.aH / D fb 2 G W bH D aH g D aH . Furthermore, a b , aH D bH , a H b.
n
Conjugacy
We close this section by introducing another equivalence relation that is extremely useful for studying the structure of groups:
Definition 2.6.16. Let a and b be elements of a group G. We say that b is conjugate to a if there is a g 2 G such that b D gag 1.
You are asked to show in the Exercises that conjugacy is an equiva lence relation and to find all the conjugacy equivalence classes in several groups of small order.
Definition 2.6.17. The equivalence classes for conjugacy are called conjugacy classes.
i
i
i
i