MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $S_{\kappa}$ denote the symmetric group on some set of cardinality $\kappa$. Does there exist a generating set $X \subset S_{\kappa}$ such that $|X| < |S_{\kappa}|$ ($\stackrel{?}{=} 2^{\kappa}$)?

More specifically, does there exist a countable set of generators for $S_{\mathbb{N}}$? And if so, can it be constructed without the Axiom of Choice?

share|cite|improve this question

closed as too localized by Bill Johnson, Mark Sapir, Gjergji Zaimi, Alain Valette, Martin Brandenburg Nov 5 '11 at 14:50

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center.If this question can be reworded to fit the rules in the help center, please edit the question.

No: If a group has a countable generating set then it is countable. But there are uncountably many permutations of a countably infinite set. – Tom Goodwillie Nov 5 '11 at 1:13
And of course Tom's comment shows the general case, too (assuming AoC): a generating set of size $\omega$ gets you a group only as big as $\omega\cdot |\mathbb{N}|$. – Steve D Nov 5 '11 at 1:25
Why is a completely trivial question like this getting action? – Bill Johnson Nov 5 '11 at 4:06
This is not a research level question. Voted to close. – Mark Sapir Nov 5 '11 at 4:59
Just realised this myself. Sorry for wasting your internet. – Felix Denis Nov 5 '11 at 10:10
up vote 4 down vote accepted

It seems clear that the answer to the first and third questions is 'no'. Indeed, if a set of generators $X$ is of infinite cardinality $\alpha$, then the group so generated cannot have cardinality greater than $\alpha$, since it is a quotient of the free group generated by $X$, which in turn is a quotient of the free monoid generated by $X\cup \{x^{-1}:x\in X\}$, and this free monoid has cardinality $\sum_{n\geq0}\alpha^n = \alpha$.

Well, to finish the claim, we need to check that the symmetric group $S_\kappa$ has cardinality $2^\kappa$ (the second question). This is certainly true: suppose given a well-ordering of $\kappa$. Then there are $\kappa^\kappa$ many permutations $f$ where $f(\alpha)$, for "even" $\alpha < \kappa$, is the least ordinal in the set $\kappa-f(\{\beta<\alpha\})$, and for "odd" $\alpha<\kappa$ is any element in $\kappa-f(\{\beta<\alpha\})$. ("Even" means a limit ordinal plus an even finite ordinal, and mutates mutandis for "odd".)

share|cite|improve this answer
It took me forever to type out this comment on this damned iPad that I'm stuck with since power went out in Connecticut. – Todd Trimble Nov 5 '11 at 2:01
+1 for still answering MO questions, even when the power's out! – Steve D Nov 5 '11 at 2:23

If the set is infinite then $S_{\kappa}$ and $X$ have the same cardinality.

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.