# Subgroup generated by a set

A subgroup generated by a set is defined as (from Wikipedia):

More generally, if S is a subset of a group G, then , the subgroup generated by S, is the smallest subgroup of G containing every element of S, meaning the intersection over all subgroups containing the elements of S; equivalently, is the subgroup of all elements of G that can be expressed as the finite product of elements in S and their inverses.

How does one prove that those statements are equivalent? If the answer is to broad to be presented here, I would appreciate pointers to relevant pages (or books).

-
Let $H$ be the set of all elements of $G$ that can be expressed as finite products of elements of $S$ and inverses of elements of $S$. You need to prove (1) that $H$ is a subgroup of $G$ and (2) that any subgroup of $G$ containing all of $S$ contains all of $H$. –  Chris Eagle May 15 '12 at 13:53

This is a typical top-down vs. bottom-up construction of a substructure. See the general discussion here.

Let $S\subseteq G$. We let $$K = \bigcap_{S\subseteq M\leq G}M$$ and $$H = \Bigl\{s_1^{\epsilon_1}\cdots s_m^{\epsilon_m}\mid m\geq 0,\ s_i\in S,\ \epsilon_i\in\{1,-1\}\Bigr\}.$$

We want to show that $K=H$.

Note that if $M$ is a subgroup of $G$, and $S\subseteq M$, then every element of $H$ must be in $M$, since $M$ is closed under products and inverses and contains every $s_i\in S$. Thus, $H\subseteq K$.

Conversely, to prove $K\subseteq H$, it suffices to show that $H$ is a subgroup of $G$ that contains $S$. To see that $S\subseteq H$, let $s\in S$. Letting $m=1$, $\epsilon_1=1$, and $s_1=s$ we have $s\in H$, so $S\subseteq H$.

To see that $H$ is a subgroup of $G$, note that $H$ is nonempty: selecting $m=0$ we obtain the empty product, which by definition is the identity of $G$. So $1\in H$.

Let $s_1^{\epsilon_1}\cdots s_m^{\epsilon_m}$ and $t_1^{\eta_1}\cdots t_n^{\eta_n}$, with $m,n\geq 0$, $\epsilon_i,\eta_j\in\{0,1\}$, and $s_i,t_j\in S$ be elements of $S$. Then $$\Bigl( s_1^{\epsilon_1}\cdots s_m^{\epsilon_m}\Bigr)\Bigl(t_1^{\eta_1}\cdots t_n^{\eta_n}\Bigr)^{-1} = r_1^{\chi_1}\cdots r_{n+m}^{\chi_{n+m}}$$ where \begin{align*} r_i &= \left\{\begin{array}{ll} s_i &\text{if }1\leq i\leq m\\ t_{n+m-i+1} & \text{if }m\lt i\leq n+m \end{array}\right.\\ \chi_i &= \left\{\begin{array}{ll} \epsilon_i &\text{if }1\leq i\leq m\\ -\eta_{n+m-i+1} & \text{if }m\lt i\leq n+m \end{array}\right. \end{align*} Note that $r_i\in S$ for each $i$, and $\chi_i\in\{1,-1\}$ for each $i$, so $r_1^{\chi_1}\cdots r_{n+m}^{\chi_{n+m}}$ is an element of $H$. Thus, $H$ is a subgroup of $G$ that contains $S$, and so is one of the subgroups being intersected in the definition of $K$. Hence, $K\subseteq H$.

Since we already had $H\subseteq K$, it follows that $H=K$, as desired.

-
Thank you for this answer, and for the link: both were very helpful. user1729's answer was also correct, although to be fair I only completely understood it after reading yours. Thank you both. –  wmnorth May 17 '12 at 13:32

This is covered in pretty much every introductory group theory text.

Let $H$ be the subset of all elements of $G$ that can be expressed as the finite product of elements in $S$ and their inverses, and let $K$ be the intersection over all subgroups containing the elements of S.

Firstly, note that $H$ is a subgroup of $G$, as the product of two words $U(S)$ and $V(S)$ of finite length gives another word of finite length, $W(S)=U(S)V(S)$, while if $U(S)\in H$ then $U^{-1}(S)$ by a simple inductive argument (the induction step is simply $(V(S)x)^{-1}=x^{-1}V(S)$).

Clearly $S\subseteq H$, so $K\leq H$ (because $K$ is got by intersecting all subgroups containing $S$). On the other hand, $S\subseteq K$ and $K$ must contain all elements of $G$ that can be expressed as the finite product of elements in $K$ and their inverses (because $K$ is closed under (finite) products and inverses), and so $H\leq K$.

Thus, $H=K$ and we're done.

-
To justify $K\le H$, you have to verify that $H$ is actually a group. –  Brian M. Scott May 15 '12 at 18:26
@Brian I have sorted this now. –  user1729 Aug 5 at 8:56