# Does the symmetric group on an infinite set have a minimal generating set?

To clarify the terms in the question above:

The symmetric group Sym($\Omega$) on a set $\Omega$ consists of all bijections from $\Omega$ to $\Omega$ under composition of functions. A generating set $X \subseteq \Omega$ is minimal if no proper subset of $X$ generates Sym($\Omega$).

This might be a difficult question, but perhaps the answer is known already?

-
Thank you for your answer drvitek, but the set you suggest only generates the finitary permutations on $\mathbb{N}$, i.e. any product of transpositions only moves finitely many points. –  Yann Peresse Jul 10 '14 at 15:42
@drvitek: On a countable set $\Omega$ there are $2^{\aleph_0}$ possible bijections. This implies non-countable generating set, if it exists. –  Michael Jul 10 '14 at 16:19
You are right Michael, we are looking for an uncountable set. In fact any generating set for Sym($\Omega$) has to have cardinality $2^{|\Omega|}$, the same as Sym($\Omega$) itself. –  Yann Peresse Jul 10 '14 at 16:28
Whoops, deleted the incorrect comment instead of editing it. I had suggested the construction (12), (23), ... or equivalent for a well-ordered set, which is incorrect for reasons mentioned above. –  drvitek Jul 10 '14 at 20:06

I think it follows from Theorem 1.1 of "Subgroups of Infinite Symmetric Groups" by Macpherson and Neumann (J. London Math. Soc. (1990) s2-42 (1): 64-84) that there is no minimal generating set of $S(\Omega)$for infinite $\Omega$.

The theorem states that any chain of proper subgroups of $S(\Omega)$ whose union is $S(\Omega)$ must have cardinality strictly greater than $|\Omega|$.

Now suppose $X$ is a minimal generating set. Let $C=\{x_0,x_1,\dots\}$ be a countable subset of $X$. If $$H_i=\langle X\setminus C,x_0,\dots,x_i\rangle$$ for $i\in\mathbb{N}$, then $H_0<H_1<\dots$ is a countable chain of proper subgroups whose union is $S(\Omega)$, contradicting the theorem.

(Note: There's a paper of Bigelow pointing out some unstated set-theoretic assumptions in Macpherson and Neumann's paper, but I don't think that affects the theorem I mention.)

-
Very good. By the way, the weak form of the Macpherson-Neumann theorem that you use, that $S(\Omega)$ is not the union of a countable chain of proper subgroups, has an easier proof than the general theorem; namely, it's a corollary of the fact that every countable subset of $S(\Omega)$ is contained in a finitely generated subgroup of $S(\Omega)$. –  bof Jul 10 '14 at 19:40
@bof Thanks. Is the proof of that very easy? I have a feeling it should be possible to distil a fairly short and simple complete answer to the question of the OP. –  Jeremy Rickard Jul 10 '14 at 20:06
It's Theorem 3.1 on p. 233 of Fred Galvin, Generating countable sets of permutations, J. London Math. Soc. (2) 51 (1995), 230-242: "Let $E$ be an infinite set. Every countable subset of $\operatorname{Sym}(E)$ is contained in a $4$-generator subgroup of $\operatorname{Sym}(E)$." Followed by Corollary 3.2: "A symmetric group is not the union of a countable chain of proper subgroups." The proof of Theorem 3.1 is a dozen lines; too long to quote in a comment, but not too long for an answer. –  bof Jul 10 '14 at 23:20
Nice. Thank you very much. This then also answers the same question for all the other groups/semigroups which are known to have uncountable cofinality. –  Yann Peresse Jul 10 '14 at 23:47
@JeremyRickard I've copied out the proof of Galvin's Theorem 3.1 from a reprint of his paper, and posted it as a comment-disguised-as-an-answer. Hope I didn't make too many typos. –  bof Jul 11 '14 at 0:50

Jeremy Rickard's answer uses the fact that a symmetric group is not the union of a countable chain of proper subgroups. The following easy proof of that fact is quoted from Fred Galvin, Generating countable sets of permutations, J. London Math. Soc. (2) 51 (1995), 230-242.

[. . .] permutations are regarded as right operators, and are composed from left to right. [. . .] The pointwise stabilizer of a subset $X$ of $E$ is the group $S_X=\{\pi\in\operatorname{Sym}(X):X\subseteq\operatorname{fix}(\pi)\}$.
We shall make heavy use of the following lemma, which was proved by Dixon, Neumann and Thomas [3, Lemma, p. 580] for the case $|E|=\aleph_0$, and generalized by Macpherson and Neumann [11, Lemma 2.1] to arbitrary infinite sets.

LEMMA 2.1. Let $E$ be an infinite set. If $E=A\cup B\cup C$ where $A,B,C$ are disjoint sets and $|A|=|B|=|C|$, then $\operatorname{Sym}(E)=S_AS_BS_A\cup S_BS_AS_B$.

Proof. Let $\kappa=|E|$. Consider a permutation $\pi\in\operatorname{Sym}(E)$. It is easy to see that $\pi\in S_AS_BS_A$ if (and only if) $|(B\cup C)\setminus A\pi^{-1}|=\kappa$. In particular, $\pi\in S_AS_BS_A$ if $|C\setminus A\pi^{-1}|=\kappa$; similarly, $\pi\in S_BS_AS_B$ if $|C\setminus B\pi^{-1}|=\kappa$. At least one of these alternatives must hold, since $C=(C\setminus A\pi^{-1})\cup(C\setminus B\pi^{-1})$.

[. . .]

THEOREM 3.1. Let $E$ be an infinite set. Every countable subset of $\operatorname{Sym}(E)$ is contained in a
$4$-generator subgroup of $\operatorname{Sym}(E)$.

Proof. We may assume that $E=\mathbb Z\times\mathbb Z\times T$, where $|T|=|E|=\kappa$. Let $E_0=\{0\}\times\{0\}\times T$. Choose $A\subset E_0$ with $|A|=|E_0\setminus A|=\kappa$; let $C=E_0\setminus A$ and let $B=E\setminus E_0$. Choose an involution $\varepsilon\in\operatorname{Sym}(E)$ so that $B\varepsilon=A$. Define $\alpha,\delta\in\operatorname{Sym}(E)$ by setting $(m,n,t)\alpha=(m+1,n,t),(0,n,t)\delta=(0,n+1,t)$, and $(m,n,t)\delta=(m,n,t)$ for $m\ne0$.

Let a countable set $H\subseteq\operatorname{Sym}(E)$ be given; we shall show that $H\subseteq\langle\alpha,\beta,\delta,\varepsilon\rangle$ for some $\beta\in\operatorname{Sym}(E)$. By Lemma 2.1, we may assume that $H\subseteq S_A\cup S_B$. Let $H'=(H\cap S_B)\cup\varepsilon(H\cap S_A)\varepsilon$. Then $H'$ is a countable subset of $S_B$; let $H'=\{\phi_i:i\in\mathbb Z\}$. Since $\operatorname{supp}(\phi_i)\subseteq E_0$, we can define $\hat\phi_i\in\operatorname{Sym}(T)$ so that $(0,0,t)\phi_i=(0,0,t\hat\phi_i)$ for $t\in T,i\in\mathbb Z$. Finally, define $\beta\in\operatorname{Sym}(E)$ by setting $$(m,n,t)\beta= \begin{cases} (m,n,t\hat\phi_m)&\text{if }n\ge0,\\ (m,n,t)&\text{if }n\lt0.\\ \end{cases}$$ Then $\phi_i=(\alpha^i\beta\alpha^{-i})\delta^{-1}(\alpha^i\beta^{-1}\alpha^{-i})\delta$ for each $i\in\mathbb Z$; thus we have $H'\subseteq\langle\alpha,\beta,\delta\rangle$ and $H\subseteq H'\cup\varepsilon H'\varepsilon\subseteq\langle\alpha,\beta,\delta,\varepsilon\rangle$.

COROLLARY 3.2. A symmetric group is not the union of a countable chain of proper subgroups.

[. . .]

THEOREM 3.3. Let $E$ be an infinite set. Every countable subset of $\operatorname{Sym}(E)$ is contained in a
$2$-generator subgroup of $\operatorname{Sym}(E)$.

Proof. [. . .]

-
I see no reason to delete this. It serves to complement the currently accepted answer, and provides a service for present and future students. Please keep it, or something closely resembling it. –  The Masked Avenger Jul 11 '14 at 0:58
@TheMaskedAvenger You may be right; I'm a newbie here and don't know much about the rules and culture of this site. I posted this with the idea that Jeremy Rickard might want to incorporate the argument into his answer to make it self-contained. –  bof Jul 11 '14 at 1:26
leave it up! it's good! –  Nick Gill Jul 11 '14 at 2:01