Hello all,
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?
Think about it the other way - take a subset of , call it . This subset corresponds to an element of the group, with . Take a different subset of , call it , and this correspond to an element . Suppose these elements are the same, then . Re-arranging, we get that . By minimality of our generating set we have that . Similarly, we also have that for all and for all . Thus , a contradiction.
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:
Let .
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.
We have and . Apply the inductive assumption to . Then note that you can just pin onto the end of every element of to get a new element of . These elements are all unique (as if ). Thus we have new elements in to add to the elements we already have. How many elements does this give us?
(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.
Tonio