subgroups部分群ぶぶんぐん and generation生成せいせい

Inside a group群ぐん, we often want to find a smaller part that still preserves the structure of a group. Such a subset is a subgroup部分群ぶぶんぐん.

A subgroup部分群ぶぶんぐん is not merely a subset. When elements are operated on, the result must remain inside, and inverse elements must also remain inside.

1Definition of a subgroup部分群ぶぶんぐん

A subset $$H\subseteq G$$H\subseteq G of a group $$G$$G is a subgroup部分群ぶぶんぐん if $$H$$H becomes a group using the operation inherited from $$G$$G.

In practice, it can be tested by the following criterion.

and for all $$a,b\in H$$a,b\in H,

If these hold, then $$H$$H is a subgroup部分群ぶぶんぐん.

This criterion may look like division, but it uses the inverse $$b^{-1}$$b^{-1} that exists in the ambient group $$G$$G. What must be proved is that inverses and products also remain in the smaller set $$H$$H.

2Concrete examples

Inside $$(\mathbb{Z},+)$$(\mathbb Z,+), the set of all even integers

is a subgroup部分群ぶぶんぐん. It contains 0, and the difference of two even integers is even.

On the other hand, the set of natural numbers $$\mathbb{N}$$\mathbb N is not a subgroup部分群ぶぶんぐん of $$(\mathbb{Z},+)$$(\mathbb Z,+). For example, it contains 3 but does not contain the inverse $$-3$$-3.

3Generators

Given a subset $$A$$A of a group $$G$$G, consider all finite products

Their set is the subgroup generated by $$A$$A. The empty product for $$r=0$$r=0 is defined to be the identity $$e$$e, so $$⟨A⟩=\left\{e\right\}$$\langle A\rangle=\{e\} when $$A=\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$A=\varnothing.

It is written

A group generated by one element $$a$$a,

is the cyclic subgroup generated by $$a$$a. Here $$a^0=e$$a^0=e and $$a^{-m}=(a^{-1}{)}^m$$a^{-m}=(a^{-1})^m for $$m>0$$m>0. A group $$G$$G is called cyclic when $$G=⟨a⟩$$G=\langle a\rangle for some $$a\in G$$a\in G.

4Example: cyclic groups of residue classes

In $$(\mathbb{Z}/6\mathbb{Z},+)$$(\mathbb Z/6\mathbb Z,+), the element $$\left[1\right]$$[1] generates the whole group.

are obtained by repeatedly adding $$\left[1\right]$$[1]. On the other hand, the subgroup部分群ぶぶんぐん generated by $$\left[2\right]$$[2] is

To verify that these are all its elements, write an arbitrary integer multiple of $$\left[2\right]$$[2] as $$k\left[2\right]$$k[2], and write $$k\in \mathbb{Z}$$k\in\mathbb Z as $$k=3q+r$$k=3q+r with $$r\in \{0,1,2\}$$r\in\{0,1,2\}. Then

which is one of $$\left[0\right],\left[2\right],\left[4\right]$$[0],[2],[4]. Conversely, taking $$q=0$$q=0 and $$k=r=0,1,2$$k=r=0,1,2 gives these three elements, respectively. Hence the displayed set equals $$⟨\left[2\right]⟩$$\langle[2]\rangle.

5What is preserved

In a subgroup部分群ぶぶんぐん, the operation, identity element単位元たんいげん, and inverses of the group are preserved as they are. What changes is the range of elements available. In generation, starting from a small number of specified elements, closure閉包性へいほうせい and inverses are used to build the smallest necessary subgroup部分群ぶぶんぐん.

6Proof supplement: subgroup部分群ぶぶんぐん criterion and minimality of generated subgroups部分群ぶぶんぐん

Let $$G$$G be a group and let $$H\subseteq G$$H\subseteq G be a nonempty subset. If

holds, then $$H$$H is a subgroup部分群ぶぶんぐん.

Proof. Since $$H$$H is nonempty, there exists $$h\in H$$h\in H. Then $$h{h}^{-1}=e\in H$$hh^{-1}=e\in H. Next let $$x\in H$$x\in H. Since $$e\in H$$e\in H, applying the condition to $$e,x$$e,x gives $$e{x}^{-1}=x^{-1}\in H$$ex^{-1}=x^{-1}\in H. Finally, if $$x,y\in H$$x,y\in H, we already know $$y^{-1}\in H$$y^{-1}\in H, so applying the condition to $$x,y^{-1}$$x,y^{-1} gives $$x(y^{-1}{)}^{-1}=xy\in H$$x(y^{-1})^{-1}=xy\in H. Thus $$H$$H contains the identity, inverses, and products. Associativity is inherited from the operation on $$G$$G, so $$H$$H is a group and hence a subgroup.

The set of finite products contains the empty product $$e$$e. Listing the factors of two finite products in order gives their product, and reversing the factors while inverting each one gives the inverse. Associativity is inherited from $$G$$G, so this set is a subgroup.

The generated subgroup $$⟨S⟩$$\langle S\rangle can also be defined as the intersection of all subgroups that contain $$S$$S:

This intersection is a subgroup, because the identity lies in every such $$H$$H and products and inverses are closed in each $$H$$H. Also, since every such $$H$$H contains $$S$$S, the intersection contains $$S$$S. Moreover, any subgroup $$K$$K containing $$S$$S is one of those being intersected, so $$⟨S⟩\subseteq K$$\langle S\rangle\subseteq K. Therefore $$⟨S⟩$$\langle S\rangle is the smallest subgroup containing $$S$$S. The set of finite products defined earlier is itself a subgroup containing $$S$$S, so it contains this intersection. Conversely, every subgroup containing $$S$$S contains every finite product of elements of $$S$$S and their inverses. Thus the two definitions agree.

7Calculation supplement: the subgroup部分群ぶぶんぐん generated by $$\left[k\right]$$[k] in $$\mathbb{Z}/n\mathbb{Z}$$\mathbb Z/n\mathbb Z

Let $$n\text{[PARSE ERROR: Undefined("Command("ge")")]}1$$n\ge1 and $$k\in \mathbb{Z}$$k\in\mathbb Z. The order位数いすう of a finite group or subgroup is its number of elements. In the additive group $$(\mathbb{Z}/n\mathbb{Z},+)$$(\mathbb Z/n\mathbb Z,+), the elements of the subgroup generated by $$\left[k\right]$$[k] are

The first positive integer $$m$$m for which this sequence returns to $$\left[0\right]$$[0] is the smallest $$m$$m satisfying $$n\mid mk$$n\mid mk. Write $$d=\text{[PARSE ERROR: Undefined("Command("gcd")")]}(n,k)$$d=\gcd(n,k), $$n=d{n}^{\prime }$$n=dn', and $$k=d{k}^{\prime }$$k=dk'. Then $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(n^{\prime },k^{\prime })=1$$\gcd(n',k')=1 and

To justify the last equivalence, use Bezout's identity. Since $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(n^{\prime },k^{\prime })=1$$\gcd(n',k')=1, there are integers $$u,v$$u,v such that $$u{n}^{\prime }+v{k}^{\prime }=1$$un'+vk'=1. If $$n^{\prime }\mid m{k}^{\prime }$$n'\mid mk', then both terms on the right of $$m=mu{n}^{\prime }+mv{k}^{\prime }$$m=mun'+mvk' are divisible by $$n^{\prime }$$n', so $$n^{\prime }\mid m$$n'\mid m; the converse is immediate. Thus the least possible $$m$$m is $$n^{\prime }=n/d$$n'=n/d.

Moreover, if $$0\text{[PARSE ERROR: Undefined("Command("le")")]}i<j<m$$0\le i<j<m and $$\left[ik\right]=\left[jk\right]$$[ik]=[jk], then $$\left[\right(j-i\left)k\right]=\left[0\right]$$[(j-i)k]=[0], contradicting the minimality of $$m$$m because $$0<j-i<m$$0<j-i<m. Hence $$\left[0\right],\left[k\right],\dots ,\left[\right(m-1\left)k\right]$$[0],[k],\ldots,[(m-1)k] are distinct. Since $$\left[mk\right]=\left[0\right]$$[mk]=[0], the sequence then repeats with period $$m$$m. Therefore

For example, in $$\mathbb{Z}/12\mathbb{Z}$$\mathbb Z/12\mathbb Z, consider $$\left[8\right]$$[8]. Since $$\text{[PARSE ERROR: Undefined("Command("gcd")")]}(12,8)=4$$\gcd(12,8)=4, the generated subgroup部分群ぶぶんぐん has order位数いすう $$12/4=3$$12/4=3. Indeed,

8Exercise link

9Summary

A subgroup部分群ぶぶんぐん is obtained by restricting the elements while preserving the group structure. Generation生成せいせい builds the smallest subgroup from specified elements, and a cyclic group巡回群じゅんかいぐん is a group generated by one element.