While studying some facts about generating sets for groups, I came along the the following fact, but a proof was never given, as it should be somehow trivial.
Here the fact:
Let be a finite group. Then there exists a subset so that and
When proving this, I would start like this: By Cayley's theorem is isomorphic to some permutation group . Therefore it is enough to show the claim for
Now I know that is generated by n-1 transpositions, but I dont know how to apply this on subgroups of it. Anyone can help me with the proof?
Hey Tonio, thanks for your answer. Still I don't fully understand what you mean. A minimal generating set means, that when I take all possible products of elements of it, I get G. But how do they have a 1-1 correspondence with all possible subsets of S?
Thus, every subset of , our minimal generating set, corresponds to a unique element of . There are subsets, and so .
If I understand it correctly this is your induction base:
For n = 1, we have . So generates G, .
But I have absolutely no clue how to get to n+1 from n. I also don't understand how you can add 1 element to a group and get a new group of size n+1?
Please help me with this.
(Note that none of the "new" elements are in , as otherwise we can cancel to get that , a contradiction).
Take for instance , for some group . Then every elements of is the product of a finite string of elements of AND their inverses.
Among these elements we have
The above products are all in G, and they're in 1-1 correspondence with the subsets of .
Note that as elements of , ALL the above strings of elements of are different, otherwise the generating set wouldn't be minimal.