Do the subsets of a generator of the symmetric group $S_n$ generate all subgroups of $S_n$?

Question

Let us assume that $A \subseteq S_n$ is such that $\langle A \rangle = S_n$. Does it then hold true that for every subgroup $H$ of $S_n$ there exists an $A' \subseteq A$ such that $\langle A' \rangle = H$?

The claim is obviously true if $A = S_n$. I was wondering whether it remains valid for any generator $A$ of $S_n$ (and any $n$). Pardon me if the question is trivial to answer but I am not really an expert in group theory and a search across the internet was not helpful either. Any help would be greatly appreciated.

Answer 1

No. Let $A$ be the set of all transpostions. Then $\langle A\rangle=S_n$, but not subset of $A$ generates $A_n$, since no transposition belongs to $A_n$.

Answer 2

Answer : no, of course not. For example $\sigma=(1,2,\ldots,n)$ and $\tau=(1,2)$ together generate $S_n$, but the subsets of $A=\lbrace \sigma, \tau \rbrace$ only give four subgroups of $S_n$, and there are many more subgroups.

Answer 3

One famous generating set of $S_n$ is $$A = \{ (1,2), (1,2,3,4,\ldots, n)\}.$$

The proof that this sets generates the whole group is basically the proof of correctness for the bubble sort algorithm. Now you can only generate four subgroups from subsets of this set, the trivial one, the whole group and two cyclic groups; but of course $S_n$ has much more subgroups in general.

Looking at two other famous generating sets, this will also not work: $$A_1 = \{ (i,j) \mid i < j\}, \,\,\, A_2 = \{(i,i+1) \mid 1 \leq i < n\}.$$ The first one is the set of all transpositions, the second one are the so called Coxeter generators of $S_n$. Both will not be able to generate the alternating group from subsets, as the alternating group does not contain any transpositions.

Answer 4

Certainly not for any set of generators.

For instance, one knows that $S_n$ is generated by (some) cycles of lngth 2 and not all subgroups have the same property.

Answer 5

Given a prime number $p$, $S_p$ is always generated by a transposition and a $p$ cycle. There is no way to find a subst of this set that generates $A_n$.

Answer 6

Generating sets can be very small. So small, in fact, that the number of subsets of $A$ can be dwarfed by the number of subgroups of $G$. As others have pointed out, the symmetric group $S_n$ is generated by $2$ elements.

Here's a family of abelian examples inspired by geometry. As a vector space, we know $\mathbb{R}^2$ is spanned by the two basis vectors $(1,0)$ and $(0,1)$, but of course not every line is spanned by a basis vector. In the context of finite groups, or vector spaces over finite fields, the elementary abelian group $(\mathbb{Z}/p\mathbb{Z})^n$ has as a generating set the coordinate tuples, but not every subspace/subgroup is generated by coordinate tuples - for instance, the set of all tuples for which $x_1+\cdots+x_n=0$ doesn't contain a single basis tuple, nor the span of $(1,\cdots,1)$.

Notice that coordinate subspaces of $\mathbb{R}^n$ are very rectilinear, and there will be (infinitely) more subspaces that are "tilted" / "skewed" / "angled" in between them. This is an intuition you can carry over into finite groups, even though of course finite groups are much more complicated.