29
$\begingroup$

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?

$\endgroup$
4
  • 11
    $\begingroup$ 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. $\endgroup$ Jul 10, 2014 at 15:42
  • $\begingroup$ @drvitek: On a countable set $\Omega$ there are $2^{\aleph_0}$ possible bijections. This implies non-countable generating set, if it exists. $\endgroup$
    – Michael
    Jul 10, 2014 at 16:19
  • $\begingroup$ 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. $\endgroup$ Jul 10, 2014 at 16:28
  • 2
    $\begingroup$ 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. $\endgroup$
    – dvitek
    Jul 10, 2014 at 20:06

3 Answers 3

35
$\begingroup$

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

$\endgroup$
7
  • 4
    $\begingroup$ 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)$. $\endgroup$
    – bof
    Jul 10, 2014 at 19:40
  • 1
    $\begingroup$ @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. $\endgroup$ Jul 10, 2014 at 20:06
  • 2
    $\begingroup$ 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. $\endgroup$
    – bof
    Jul 10, 2014 at 23:20
  • 1
    $\begingroup$ 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. $\endgroup$ Jul 10, 2014 at 23:47
  • 1
    $\begingroup$ @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. $\endgroup$
    – bof
    Jul 11, 2014 at 0:50
17
$\begingroup$

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. [. . . .]

$\endgroup$
4
  • 8
    $\begingroup$ 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. $\endgroup$ Jul 11, 2014 at 0:58
  • 2
    $\begingroup$ leave it up! it's good! $\endgroup$
    – Nick Gill
    Jul 11, 2014 at 2:01
  • $\begingroup$ I'm confused as to why Lemma 2.1 lets us assume $H\subseteq S_A \cup S_B$; can anyone explain that? Thanks! $\endgroup$ Apr 24, 2018 at 7:46
  • 1
    $\begingroup$ If $H\subseteq\operatorname{Sym}(E)=\langle S_A\cup S_B\rangle$ and $H$ is countable, then there is a countable set $\hat H\subseteq S_A\cup S_B$ such that $H\subseteq\langle\hat H\rangle.$ If $\hat H$ is contained in a $4$-generator subgroup of $\operatorname{Sym}(E)$ then so is $H.$ $\endgroup$
    – bof
    Apr 24, 2018 at 8:53
4
$\begingroup$

The canonical paper on the subject (don't be fooled by the publication date, it had been around for years before then) is George Bergman's gem:

Bergman, George M., Generating infinite symmetric groups., Bull. Lond. Math. Soc. 38, No. 3, 429-440 (2006). ZBL1103.20003.

$\endgroup$
3
  • $\begingroup$ To be precise, it appeared in 2004 on the arxiv; this 2-year shift sounds quite average. What do you mean by "the" canonical paper? the study of cofinality of groups has well preceded this (very nice) paper, whose main contribution is to emphasize a property stronger than having uncountable cofinality. $\endgroup$
    – YCor
    Apr 23, 2018 at 23:02
  • $\begingroup$ @YCor And to be really precise, it was on George Bergman's web page at Berkeley for a while before then. The paper defines the "Bergman property", which is the right property to define, which makes the paper canonical, in my opinion, and which many interesting groups can be shown to have. $\endgroup$
    – Igor Rivin
    Apr 24, 2018 at 1:59
  • $\begingroup$ Possibly: indeed papers relying on the notions introduced by Bergman were published as soon as 2005. Tolstykh's one appeared on arxiv in March 2004, 2 months after Bergman's, so possibly the paper circulated a few months earlier; probably not more. $\endgroup$
    – YCor
    Apr 24, 2018 at 8:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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