Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
10  
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 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 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 at 16:28
1  
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 at 20:06

2 Answers 2

up vote 28 down vote accepted

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.)

share|improve this answer
4  
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 at 19:40
1  
@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 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 at 23:20
1  
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 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 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. [. . .]

share|improve this answer
5  
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 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 at 1:26
1  
leave it up! it's good! –  Nick Gill Jul 11 at 2:01

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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