Subgroups

Definitions and Examples

As a reminder:

Definition

A subgroup of a group $(G,\ast )$ is a group $(H,\ast )$ such that $H\subseteq G$ and the operation on $H$ is the operation on $G$ restricted to $H$. We write $H\le G$ to mean that $H$ is a subgroup of $G$.

Standard sources of subgroups

Let $G$ be a group.

1. If $K\le H$ and $H\le G$, then $K\le G$.
2. If $\{H_{\alpha }{\}}_{\alpha \in A}$ is any collection of subgroups of $G$, then

$$\bigcap _{\alpha \in A}{H}_{\alpha }$$

is a subgroup of $G$.

3. If $f:G\to K$ is a group homomorphism and $H\le G$, then

$$f(H)=\{f(h)\mid h\in H\}$$

is a subgroup of $K$.

4. If $f:G\to K$ is a group homomorphism, then $\ker (f)\le G$.
5. The center

$$Z(G)=\{z\in G\mid zg=gz\text{ for all }g\in G\}$$

is a subgroup of $G$.

Proof

We prove the less immediate items with the one-step test.

For intersections, if the collection is empty, then the intersection is all of $G$. Otherwise, every subgroup $H_{\alpha }$ contains $e_G$, so the intersection is nonempty. If $x,y\in {\bigcap }_{\alpha \in A}{H}_{\alpha }$, then $x,y\in H_{\alpha }$ for every $\alpha$, so $x{y}^{-1}\in H_{\alpha }$ for every $\alpha$. Hence $x{y}^{-1}$ is in the intersection.

For images, note that $\mathrm{im}(f)$ is nonempty since it contains $f(e_G)=e_K$. If $x,y\in \mathrm{im}(f)$, then $x=f(a)$ and $y=f(b)$ for some $a,b\in G$, and

$$x{y}^{-1}=f(a)f(b{)}^{-1}=f(a{b}^{-1})\in \mathrm{im}(f).$$

This proves $\mathrm{im}(f)\le K$. The same argument applied to the restriction of $f$ to $H$ proves that $f(H)\le K$.

For kernels, if $x,y\in \ker (f)$, then

$$f(x{y}^{-1})=f(x)f(y{)}^{-1}=e_K{e}_K^{-1}=e_K,$$

so $x{y}^{-1}\in \ker (f)$.

Finally, suppose $x,y\in Z(G)$. Since $y$ commutes with every element of $G$, so does $y^{-1}$. For any $g\in G$, we have

$$(x{y}^{-1})g=x(y^{-1}g)=x(g{y}^{-1})=(xg)y^{-1}=(gx)y^{-1}=gx{y}^{-1}.$$

Thus $x{y}^{-1}\in Z(G)$, so $Z(G)\le G$.

The first item follows directly from the definition.

Exercise

Let $H$ and $K$ be subgroups of $G$. Prove that $H\cup K$ is a subgroup of $G$ if and only if $H\subseteq K$ or $K\subseteq H$.

Definition

Let $f:G\to K$ be a group homomorphism and let $L\le K$. The preimage of $L$ under $f$ is

$$f^{-1}(L)=\{g\in G\mid f(g)\in L\}.$$

Exercise

Prove that if $f:G\to K$ is a group homomorphism and $L\le K$, then $f^{-1}(L)\le G$.

Definition

Let $X$ be a subset of a group $G$. The subgroup generated by X, denoted $⟨X⟩$, is the intersection of all subgroups of $G$ which contain $X$:

$$⟨X⟩=\bigcap _{\begin{array}{c}H\le G\\ X\subseteq H\end{array}}H.$$

If $X=\{x\}$ has one element, we write $⟨x⟩$ instead of $⟨\{x\}⟩$ and call it the cyclic subgroup generated by x.

The subgroup $⟨X⟩$ really is a subgroup by Proposition Standard sources of subgroups. By construction, it is the smallest subgroup of $G$ containing $X$: every subgroup containing $X$ also contains $⟨X⟩$.

Proposition

Let $X$ be a subset of a group $G$. Then

$$⟨X⟩=\{x_1^{n_1}\cdots x_m^{n_m}\mid m\ge 0,x_i\in X,n_i\in \mathbb{Z}\}.$$

Here the product with $m=0$ is defined to be the identity element.

Proof

Let

$$S=\{x_1^{n_1}\cdots x_m^{n_m}\mid m\ge 0,x_i\in X,n_i\in \mathbb{Z}\}.$$

Since $⟨X⟩$ is a subgroup containing $X$, it must contain all finite products of elements of $X$ and their inverses. Thus $S\subseteq ⟨X⟩$.

Conversely, $S$ contains $e_G$ by allowing the empty product. If $a,b\in S$, say

$$a=x_1^{n_1}\cdots x_m^{n_m}\text{and}b=y_1^{r_1}\cdots y_{\ell }^{r_{\ell }},$$

then

$$a{b}^{-1}=x_1^{n_1}\cdots x_m^{n_m}{y}_{\ell }^{-r_{\ell }}\cdots y_1^{-r_1}\in S.$$

Hence $S\le G$ by the one-step test, and $X\subseteq S$. Since $⟨X⟩$ is the smallest subgroup containing $X$, we have $⟨X⟩\subseteq S$.

If $⟨S⟩=G$, we say that $S$ generates $G$, or that $S$ is a set of generators for $G$.

Exercise

Let $f:G\to H$ be a group homomorphism and let $A\subseteq G$. Prove that

$$f(⟨A⟩)=⟨f(a)\mid a\in A⟩.$$

Deduce that if $A$ generates $G$, then $f(A)$ generates $\mathrm{im}(f)$.

Exercise

Prove that the set of rotations in $D_n$ is a subgroup of $D_n$. Prove that this subgroup is isomorphic to $\mathbb{Z}/n\mathbb{Z}$.

Exercise

Let

$$D_n=⟨r,s\mid r^n=e,s^2=e,srs=r^{-1}⟩.$$

For an integer $k$, prove that

$$⟨s,r^{k}s⟩=⟨s,r^k⟩.$$

Determine the order of this subgroup in terms of $\gcd (n,k)$.

Exercise

Prove that $S_n$ is generated by the adjacent transpositions

$$(12),(23),\dots ,(n-1n).$$

Generators and Relations

Now that generated subgroups are defined, we can use them to talk about groups with chosen generating sets.

Definition

A group $G$ is called cyclic if it can be generated by a single element. A group $G$ is finitely generated if it can be generated by a finite set of elements.

Example

The group $\mathbb{Z}$ has one generator, the element $1$, since every integer is a sum of copies of $1$ and $-1$. Thus $\mathbb{Z}=⟨1⟩$.

Example

The group $\mathbb{Z}/n\mathbb{Z}$ is cyclic: $\mathbb{Z}/n\mathbb{Z}=⟨\overline{1}⟩$. This means every residue class is obtained by adding $\overline{1}$ to itself some number of times.

Definition

For an element $x$ in a group $G$, define the order of $x$ to be the smallest positive integer $n$ such that $x^n=e$. We denote this integer $|x|$. If no such positive integer exists, we say that $x$ has infinite order.

Example

The order of $-1$ in ${\mathbb{Q}}^{\times }$ is $2$, since $(-1{)}^2=1$ and there is no smaller positive integer $n$ such that $(-1{)}^n=1$. The order of $1$ in $\mathbb{Z}$ is infinite.

Note that any element of a finite group has finite order. The proof is: consider an infinite sequence $1,g,g^2,\dots$. Since the group is finite, there must be some repetition in this sequence. That is, there exist integers $m>n\ge 0$ such that $g^m=g^n$. Thus $g^{m-n}=e$, and so $g$ has finite order.

Exercise

Prove that every cyclic group is abelian.

Exercise

Prove that $(\mathbb{Q},+)$ and ${\mathrm{GL}}_2({\mathbb{Z}}_2)$ are not cyclic groups.

Exercise

We can define an equivalence relation on rational numbers by declaring two rational numbers to be equal whenever they differ by an integer. We denote the set of equivalence classes by $\mathbb{Q}/\mathbb{Z}$.

1. For each $n$, prove that $\mathbb{Q}/\mathbb{Z}$ has a subgroup of order $n$.
2. Prove that $\mathbb{Q}/\mathbb{Z}$ is a divisible group: that is, if $x$ is an element of $\mathbb{Q}/\mathbb{Z}$ and $n$ is an integer, there exists an element $y$ of $\mathbb{Q}/\mathbb{Z}$ such that $ny=x$.
3. Prove that $\mathbb{Q}/\mathbb{Z}$ is not finitely generated. (Hint: prove that if $x_1,\dots ,x_d$ is a finite subset of $\mathbb{Q}/\mathbb{Z}$, the subgroup generated by $x_1,\dots ,x_d$ is finite.)
4. Conclude that $\mathbb{Q}$ is not finitely generated.

Exercise

Let $G$ be a group and let $S\subseteq G$. The directed Cayley graph $\mathrm{Cay}(G,S)$ has vertex set $G$, with a directed edge

$$g⟶gs$$

for every $g\in G$ and every $s\in S$. In additive notation, the edges are $g\to g+s$.

Draw the directed Cayley graphs of $\mathbb{Z}/6\mathbb{Z}$ with respect to each of the following subsets:

$$\{\overline{1}\},\{\overline{2}\},\{\overline{2},\overline{3}\},\{\overline{2},\overline{5}\}.$$

Which of these subsets generate $\mathbb{Z}/6\mathbb{Z}$? What feature of the graph detects whether the subset generates the group?

Another way to organize the information of a group is by giving a presentation. For now this is only a preview; presentations become much more natural after quotient groups.

Definition

A presentation for a group is a way to specify a group in the following format:

$$G=⟨\text{set of generators}|\text{set of relations}⟩.$$

A relation is an identity that holds between the generators. We usually record just enough relations so that every other valid equality between the generators can be deduced from these relations.

Example

The group $\mathbb{Z}$ has one generator, the element $1$, which satisfies no relations. So we can write $\mathbb{Z}=⟨1⟩$.

Example

The following is a presentation for the group $\mathbb{Z}/n\mathbb{Z}$:

$$\mathbb{Z}/n\mathbb{Z}=⟨a|a^n=e⟩.$$

In general, given a presentation, it is very difficult to prove that certain expressions are not actually equal to each other. In fact, there is no algorithm that, given a group presentation as input, can decide whether the group is actually the trivial group with one element.

More strikingly, there exists a finite presentation whose triviality is independent of the usual axioms of set theory.

Cyclic Groups in Detail

Recall that a group $G$ is cyclic if $G=⟨x⟩$ for some element $x\in G$. In this case we call $x$ a generator of $G$. In this section, we do our first classification task of groups: we classify all cyclic groups up to isomorphism.

Theorem

Let $G=⟨x⟩$ be a cyclic group.

1. If $x$ has infinite order, then $G$ is infinite and the elements

$$\dots ,x^{-2},x^{-1},e,x,x^2,\dots$$

are all distinct. In particular, $G\cong \mathbb{Z}$.

2. If $x$ has finite order $n$, then

$$G=\{e,x,x^2,\dots ,x^{n-1}\}$$

and $|G|=|x|=n$. In particular, $G\cong \mathbb{Z}/n\mathbb{Z}$.

Proof

First suppose $x$ has infinite order. Since $G=⟨x⟩$, every element of $G$ has the form $x^m$ for some $m\in \mathbb{Z}$. If $x^a=x^b$ with $a>b$, then $x^{a-b}=e$, contradicting the assumption that $x$ has infinite order. Thus all powers of $x$ are distinct. The map

$$\mathbb{Z}\to G,m\mapsto x^m$$

is therefore a bijective homomorphism from $(\mathbb{Z},+)$ to $G$.

Now suppose $|x|=n$. The elements

$$e=x^0,x,x^2,\dots ,x^{n-1}$$

are distinct: if $x^i=x^j$ with $0\le i<j<n$, then $x^{j-i}=e$ with $0<j-i<n$, contradicting the minimality of $n$.

Finally, every integer $m$ can be written as $m=qn+r$ with $0\le r<n$, and then

$$x^m=x^{qn+r}=(x^n{)}^q{x}^r=x^r.$$

Thus the displayed list contains every element of $G$.

It remains to prove the isomorphism statement. Define

$$\varphi :\mathbb{Z}/n\mathbb{Z}\to G,\varphi (\overline{m})=x^m.$$

Its easy to check this is well-defined and a homomorphism. It is surjective because every element of $G$ is a power of $x$. It is injective because if $\varphi (\overline{m})=e$, then $x^m=e$, so $n$ divides $m$ by the minimality of $n=|x|$. Hence $\overline{m}=\overline{0}$. Thus $\varphi$ is an isomorphism, so $G\cong \mathbb{Z}/n\mathbb{Z}$.

So up to isomorphism, the only cyclic groups are $\mathbb{Z}$ and $\mathbb{Z}/n\mathbb{Z}$ for $n\ge 1$. More than this: every subgroup of these are also cyclic.

Exercise

Let $G$ be a group and let $g\in G$. Define

$${\phi }_g:\mathbb{Z}\to G,{\phi }_g(n)=g^n.$$

1. Prove that ${\phi }_g$ is a group homomorphism.
2. Prove that $\mathrm{im}({\phi }_g)=⟨g⟩$.
3. Determine $\ker ({\phi }_g)$ when $g$ has finite order $m$.
4. Determine $\ker ({\phi }_g)$ when $g$ has infinite order.

Proposition

Every subgroup of a cyclic group is cyclic.

Proof

Let $G=⟨x⟩$ be a cyclic group, and let $H\le G$. If $H=\{e\}$, then $H$ is cyclic. Otherwise, let $n$ be the smallest positive integer such that $x^n\in H$. We claim that $H=⟨x^n⟩$.

Since $x^n\in H$, we have $⟨x^n⟩\le H$. Conversely, take any element $x^m\in H$. Write $m=qn+r$ with $0\le r<n$. Then

$$x^r=x^{m-qn}=x^m(x^n{)}^{-q}\in H.$$

By the minimality of $n$, we must have $r=0$, so $x^m\in ⟨x^n⟩$. Thus $H=⟨x^n⟩$.

But which subgroups of a cyclic group are there? The answer is that they correspond to the divisors of the order of the group.

Lemma

Let $G$ be a group and let $x\in G$ have finite order $n$. If $x^m=e$ for some integer $m$, then $n$ divides $m$.

Proof

By the division algorithm, write

$$m=qn+r$$

with $0\le r<n$. Since $x^n=e$ and $x^m=e$, we have

$$e=x^m=x^{qn+r}=(x^n{)}^q{x}^r=x^r.$$

By the minimality of $n=|x|$, this forces $r=0$. Hence $n$ divides $m$.

Theorem

Let $G=⟨x⟩$ be a cyclic group of order $n$. For any integer $k$,

$$|x^k|=\frac{n}{\gcd (n,k)}.$$

In particular,

$$⟨x^k⟩=G\text{if and only if}\gcd (n,k)=1.$$

Proof

Set $d=\gcd (n,k)$, and write $n=da$ and $k=db$ with $\gcd (a,b)=1$. Let $y=x^k$. Then

$$y^a=x^{ka}=x^{dba}=x^{nb}=e,$$

so $|y|$ divides $a$ by Lemma finite order divides exponent.

On the other hand, $y^{|y|}=e$, so $x^{k|y|}=e$. Again by Lemma finite order divides exponent, $n$ divides $k|y|$. Substituting $n=da$ and $k=db$, we get $da\mid db|y|$, and hence $a\mid b|y|$. Since $\gcd (a,b)=1$, it follows that $a\mid |y|$.

Thus $|y|$ divides $a$ and $a$ divides $|y|$, so

$$|x^k|=|y|=a=\frac{n}{\gcd (n,k)}.$$

The final statement follows because $x^k$ generates $G$ exactly when $|x^k|=|G|=n$.

Example

In $\mathbb{Z}/n\mathbb{Z}$, the element $\overline{k}$ generates the whole group if and only if $\gcd (n,k)=1$. For example, the generators of $\mathbb{Z}/12\mathbb{Z}$ are $\overline{1},\overline{5},\overline{7},$ or $\overline{11}$.

Exercise

Let $x,y\in G$ commute, and suppose $|x|=m$, $|y|=n$, and $\gcd (m,n)=1$. Prove that $|xy|=mn$. Give an example showing the coprime hypothesis cannot simply be omitted.

Proposition

Let $G=⟨x⟩$ be a finite cyclic group. The subgroups of $G$ are in bijection with the positive divisors of $|G|$:

$$d⟼⟨x^{|G|/d}⟩.$$

Proof

Let $n=|G|$. If $d$ is a positive divisor of $n$, then by Theorem order of power in cyclic group,

$$|x^{n/d}|=\frac{n}{\gcd (n,n/d)}=\frac{n}{n/d}=d.$$

Therefore $⟨x^{n/d}⟩$ is a subgroup of $G$ of order $d$. Since different divisors give subgroups of different orders, the assignment is injective.

It remains to show that every subgroup appears this way. Let $H\le G$. By Proposition subgroups of cyclic groups, $H$ is cyclic, so $H=⟨x^k⟩$ for some integer $k$. Set $d=|H|$. Again by Theorem order of power in cyclic group,

$$d=|x^k|=\frac{n}{\gcd (n,k)}.$$

Set $s=\gcd (n,k)=n/d$. Then $k=sb$ and $n=sd$ for some integer $b$ with $\gcd (b,d)=1$. Inside the cyclic group $⟨x^s⟩$ of order $d$, the element

$$x^k=(x^s{)}^b$$

is a generator. Hence

$$H=⟨x^k⟩=⟨x^s⟩=⟨x^{n/d}⟩.$$

Thus every subgroup is in the image, so the assignment is a bijection.

Exercise

List all subgroups of $\mathbb{Z}/18\mathbb{Z}$.

Exercise

Show that if a finite group $G$ has a unique subgroup of order $d$ for each positive divisor $d$ of $|G|$, then $G$ is cyclic.

Exercise

Prove that the following groups are not cyclic: $\mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}/2\mathbb{Z}$, $\mathbb{Z}/2\mathbb{Z}\times \mathbb{Z}$, and $\mathbb{Z}\times \mathbb{Z}$.

Exercise

Prove that $\mathbb{Z}/m\mathbb{Z}\times \mathbb{Z}/n\mathbb{Z}$ is cyclic if and only if $\gcd (m,n)=1$. When it is cyclic, exhibit a generator.

This completes a classification of cyclic groups and their subgroups. For a general finite group, the divisors of $|G|$ do not control subgroups so cleanly. The main Sylow theorem is the strongest general substitute: if

$$|G|=p^{r}m\text{with}p\nmid m,$$

then $G$ has a subgroup of order $p^r$; all such subgroups are conjugate; and the number of such subgroups divides $m$ and is congruent to $1$ modulo $p$. We will not prove this theorem here, but it is one of the main tools for understanding finite groups beyond the cyclic case.

Exercise

Let $p$ be a prime and let $n$ be a positive integer. Show that if $x$ is an element of the group $G$ such that $x^{p^n}=e$, then $|x|=p^m$ for some integer $m\le n$.

Exercise

Show that $(\mathbb{Z}/2^n\mathbb{Z}{)}^{\times }$ is not cyclic for $n\ge 3$.