Discrete Mathematics

Subgroups

Subgroups and subgroup tests: A subgroup of a group G is a subset of G which is a subgroup in its own right (with the same group operation).
There are two subgroup tests, resembling the two subring tests.
Proposition 3.9 (First Subgroup Test) A non-empty subset H of a group G is a subgroup of G if, for any h,k ∈ H, we have hk ∈ H and h−1 ∈ H.

Proof We have to show that H satisfies the group axioms. The conditions of the test show that it is closed under composition (G0) and inverses (G3). The associative law (G1) holds in H because it holds for all elements of G.

We have only to prove (G2), the identity axiom. We are given that H is non-empty, so choose h ∈ H. Then by assumption, h−1 ∈ H, and then (choosing k = h−1) 1 = hh−1 ∈ H. We can reduce the number of things to be checked from two to one:

Proposition 3.10 (Second Subgroup Test) A non-empty subset H of a group G is a subgroup of G if, for any h,k ∈ H, we have hk−1 ∈ H.
Proof Choosing k = h, we see that 1 = hh−1 ∈ H. Now using 1 and h in place of h and k, we see that h−1 = 1h−1 ∈ H. Finally, given h,k ∈ H, we know that k−1 ∈ H, so hk = h(k−1)−1 ∈ H. So the conditions of the First Subgroup Test hold.

Example Look back to the Cayley tables in the last chapter. In the first case, {e,y} is a subgroup. In the second case, {e,a}, {e,b} and {e,c} are all subgroups.
Cyclic groups: If g is an element of a group G, we define the powers gn of G (for n∈ Z) as follows: if n is positive, then gn is the product of n factors g; g0 = 1; and g−n = (g−1)n.
The usual laws of exponents hold: gm n = gm · gn and gmn = (gm)n.
A cyclic group is a group C which consists of all the powers (positive and negative) of a single element. If C consists of all the powers of g, then we write C = (g), and say that C is generated by g.
Proposition 3.11 A cyclic group is Abelian.
Proof Let C = hgi. Take two elements of C, say gm and gn. Then
gm · gn = gm n = gn · gm.
Let C = (g). Recall the order of g, the smallest positive integer n such that
gn = 1 (if such n exists – otherwise the order is infinite).

Proposition 3.12 Let g be an element of the a group G. Then the set of all powers (positive and negative) of g forms a cyclic subgroup of G. Its order is equal to the order of g.

Proof Let C = {gn : n ∈ Z}. We apply the Second Subgroup test: if gm,gn 2 C, then (gm)(gn)−1 = gm−n ∈ C. So C is a subgroup. If g has infinite order, then no positive power of g is equal to 1. It follows that all the powers gn for n 2 Z are different elements. (For if gm = gn, with m > n, then gn−m = 1.) So C is infinite.

Suppose that g has finite order n. We claim that any power of g is equal to one of the elements g0 = 1,g1 = g, . . . ,gn−1. Take any power gm. Using the division algorithm in Z, write m = nq r, where 0  r  n−1. Then
gm = gnq r = (gn)q · gr = 1 · gr = gr.
Furthermore, the elements 1,g, . . . ,gn−1 are all different; for if gr = gs, with 0  r < s  n−1, then gs−r = 1, and 0 < s−r < n, contradicting the fact that n is the order of g (the smallest exponent i such that gi = 1).

Cosets: Given any subgroup H of a group G, we can construct a partition of G into “cosets” of H, just as we did for rings. But for groups, things are a bit more complicated.