56
$\begingroup$

For any set X, let SX be the symmetric group on X, the group of permutations of X.

My question is: Can there be two nonempty sets X and Y with different cardinalities, but for which SX is isomorphic to SY?

Certainly there are no finite examples, since the symmetric group on n elements has n! many elements, so the finite symmetric groups are distinguished by their size.

But one cannot make such an easy argument in the infinite case, since the size of SX is 2|X|, and the exponential function in cardinal arithmetic is not necessarily one-to-one.

Nevertheless, in some set-theoretic contexts, we can still make the easy argument. For example, if the Generalized Continuum Hypothesis holds, then the answer to the question is No, for the same reason as in the finite case, since the infinite symmetric groups will be characterized by their size. More generally, if κ < λ implies 2κ < 2λ for all cardinals, (in another words, if the exponential function is one-to-one, a weakening of the GCH), then again Sκ is not isomorphic to Sλ since they have different cardinalities. Thus, a negative answer to the question is consistent with ZFC.

But it is known to be consistent with ZFC that 2κ = 2λ for some cardinals κ < λ. In this case, we will have two different cardinals κ < λ, whose corresponding symmetric groups Sκ and Sλ nevertheless have the same cardinality. But can we still distinguish these groups as groups in some other (presumably more group-theoretic) manner?

The smallest instance of this phenomenon occurs under Martin's Axiom plus ¬CH, which implies 2ω = 2ω1. But also, if one just forces ¬CH by adding Cohen reals over a model of GCH, then again 2ω = 2ω1.

(I am primarily interested in what happens with AC. But if there is a curious or weird counterexample involving ¬AC, that could also be interesting.)

$\endgroup$
10
  • 6
    $\begingroup$ The normal subgroups of $S(X)$ are the subgroup of elements which move finitely many points and its subgroup of even permutations, and the subgroups $S_\kappa(X)$ of permutations which move at most $\kappa$ points; this is the Schreier–Ulam–Baer theorem. By looking at the order type of the lattice of normal subgroups (which is a chain) maybe you can guess the cardinal of $X$. $\endgroup$ Jan 25, 2010 at 16:14
  • 20
    $\begingroup$ there are no finite examples ... um, 0! = 1!, right? $\endgroup$ Jan 25, 2010 at 18:07
  • 2
    $\begingroup$ @Gerald: Yes, I should ask about nonempty sets X, Y. $\endgroup$ Jan 25, 2010 at 18:30
  • 5
    $\begingroup$ @Michael: What could be more natural than mapping the identity of one group to the identity of another, especially when the groups have no other elements? $\endgroup$ Jan 25, 2010 at 19:40
  • 3
    $\begingroup$ @Scott: What canonical map of permuation groups are you thinking about? I don't know any and a have no idea how to turn a general map $X\to Y$ into a map $S(X)\to S(Y)$. Injective maps work, okay. But what is with the general case? $\endgroup$ Mar 18, 2010 at 13:22

6 Answers 6

55
$\begingroup$

According to the Schreier–Ulam–Baer theorem, the nontrivial normal subgroups of $S(X)$ are (i) the subgroup $S_\mathrm{fin}(X)$ of permutations of $X$ of finite support, (ii) the subgroup $A_\mathrm{fin}(X)$ of $S_\mathrm{fin}(X)$ of even permutations, and (iii) for each cardinal $\kappa$ the subgroups $S_{<\beta}(X)$ and $S_{\leq\beta}(X)$ of permutations which move strictly less than $\beta$ points and at most $\beta$ points, respectively.

Since, as you said, a cardinal is determined by the order type of the set of cardinals below it, looking at the lattice of normal subgroups of $S(X)$, then, lets you guess the cardinal of $X$.

$\endgroup$
1
  • 16
    $\begingroup$ Thanks for the great answer! But it seems a funny way to me to make the list, for it is redundant in several ways. First, item (i) is included in the first part of item (iii) in the case beta=omega as S_{<omega}. Also, the second part of item (iii) is a special case of the first part, since S_{\leq\beta}(X)=S_{<\beta+}(X). So I think you can omit item (i) and the second part of (iii) completely, and have the same subgroups. (Also, you have a typo, since \kappa should be \beta.) $\endgroup$ Jan 25, 2010 at 23:30
45
$\begingroup$

The following seems simpler than the answers given earlier. I apologize if this answer (or a simpler one) is already in one of the links and I overlooked it.

I claim that, for any infinite set $X$, the cardinality $|X|$ can be obtained from the symmetric group Sym$(X)$ as the smallest cardinality of any conjugacy class other than the trivial class $\{1\}$. First, there is a conjugacy class of size $|X|$, for example, the class of those permutations that just interchange two elements of $X$ while fixing everything else.

Now the main point: Suppose $C$ is a non-trivial conjugacy class. Consider any element $\pi$ of $C$ and any element $x\in X$ moved by $\pi$. (Such an $x$ exists as $C$ isn't the trivial class.) For any element $y\in X-\{x\}$, consider the permutation that sends $\pi(x)$ and $y$ to each other and fixes everything else (including, in particular, $x$). Then $\sigma\pi\sigma^{-1}$ (also known as $\sigma\pi\sigma$) is a conjugate of $\pi$ that sends $x$ to $y$. So the $|X|$ different possible $y$'s give us $|X|$ different conjugates of $\pi$. Therefore, $|C|\geq|X|$, as claimed.

Remark: I used the Axiom of Choice twice here, first to say that the number of pairs from $X$ is $|X|$, and second to say that the number of possible $y$'s is also $|X|$. (The second fact follows easily from the first.) I don't know whether the result holds in the absence of the Axiom of Choice.

$\endgroup$
1
  • $\begingroup$ This is a very nice argument. I have a feeling that what it gives (with a little extra massaging) is not so far from the Schreier-Ulam-Baer theorem... $\endgroup$
    – Igor Rivin
    Apr 23, 2012 at 14:16
39
$\begingroup$

In an ancient paper with Saharon Shelah, I proved that if κ < λ, then Sym(λ) does not embed into Sym(κ). The proof is based on results in an even more ancient paper with John Dixon and Peter Neumann. The relevant papers are:

Saharon Shelah and Simon Thomas, Implausible subgroups of infinite symmetric groups. Bull. London Math. Soc. 20 (1988), no. 4, 313--318.

John D. Dixon, Peter M. Neumann and Simon Thomas, Subgroups of small index in infinite symmetric groups. Bull. London Math. Soc. 18 (1986), no. 6, 580--586.

$\endgroup$
1
  • 5
    $\begingroup$ Simon, Welcome to Math Overflow! I believe that you have a lot to contribute here, and the community will learn a lot from you. $\endgroup$ Mar 18, 2010 at 1:27
23
$\begingroup$

See exercises 4.6.5 - 4.6.8 in Dummit & Foote, 3rd edition. In particular, the Schreier-Ulam theorem is not needed.

Steve

$\endgroup$
1
  • 9
    $\begingroup$ +1: Wow, the newest edition of D&F is impressively comprehensive. Their proof goes by establishing part of B-S-U: namely that the index 2 alternating subgroup A of the subgroup of all permutations moving only finitely many elements is the unique nontrivial minimal normal subgroup of S(X). Since A and X have the same cardinality, this suffices. $\endgroup$ Jan 30, 2010 at 17:16
7
$\begingroup$

I figured out a solution that just takes some basic combinatorics, and doesn't use the axiom of choice at all; I'm surprised no one else posted something similar already.

Assume $X$ is not finite, since we can handle that case easily.

The transpositions in $S_X$ can be distinguished as follows: They are the conjugacy class $T$ consisting of elements of order 2 with the property that the set of products of pairs of elements of $T$ contains no more than one conjugacy class of order 2. To see that no other conjugacy class satisfies this property, observe that for any product $s$ of at least two disjoint transpositions (including possibly infinitely many), one can select a subset of two of them and interchange two of the letters to obtain $s'$ such that $ss'$ is a product of exactly two disjoint transpositions (using the Klein 4 group in $S_4$). If $s$ is a product of exactly 2 or 3 transpositions then we can multiply by a disjoint product of 2 or 3 transpositions to obtain another conjugacy class. If s is a product of 4 or more transpositions, then we can select another two transpositions in s to obtain $s''$ such that $ss''$ is a product of exactly four disjoint transpositions.

Next we aim to characterize letters as equivalence classes of pairs of elements of $T$ which multiply to an element of order 3, so that the pair $\{(a, b), (b, c)\}$ distinguishes $b$. We need to describe the equivalence relation on these pairs. We can express the transposition $(a, c)$ as a conjugate of one element of the pair by the other. Therefore when we have another pair $\{(a', b'), (b', c')\}$, we can express the condition that $\{a, c\}$ is disjoint from $\{a', c'\}$. In this case we say that the two pairs are related if multiplying any two of the four transpositions gives an element of order 3. Then we take the transitive closure of that relation.

So we have constructed a set from the abstract group $S_X$ which is in natural bijection with $X$. Note that the argument distinguishing $T$ works when $|X| \ge 12$, and the argument characterizing the equivalence relation works when $|X| \ge 7$. There's probably a clever way to adapt both arguments for fewer elements; this is just what I came up with. Note that the transpositions cannot be distinguished in $S_6$.

$\endgroup$
5
  • 2
    $\begingroup$ It's, in my opinion, the same degree of sophistication as some other previously given answers, e.g. in Andreas Blass' answer (which is related, since it also uses the conjugacy class of transpositions). $\endgroup$
    – YCor
    Sep 30, 2017 at 23:21
  • 1
    $\begingroup$ That answer and the D&F answer seem to depend on the axiom of choice though. $\endgroup$ Sep 30, 2017 at 23:26
  • 1
    $\begingroup$ Ah ok it depends on the meaning of "sophistication": avoiding AC does not always makes proofs simpler (especially when one wants to make "constructive" proofs about "non-constructive" objects; of course it's still of interest. $\endgroup$
    – YCor
    Oct 1, 2017 at 6:28
  • 1
    $\begingroup$ Btw part of the argument (defining $X$ from the set of transpositions and group structure) is what I did in mathoverflow.net/questions/280769/… $\endgroup$
    – YCor
    Oct 1, 2017 at 6:30
  • $\begingroup$ @YCor My mistake, I probably should have phrased that intro a bit better. $\endgroup$ Oct 1, 2017 at 14:01
4
$\begingroup$

Maybe too late as for a question asked 11 years ago, but I would like to inform that this paper contains a topological proof of the following theorem which is related to the answer of Mariano Suárez-Álvarez.

Theorem. For any cardinals $\kappa<\lambda$, the group $Alt(\lambda)$ of even finitely supported permutations of $\lambda$ is not isomorphic to a subgroup of the permutation group $Sym(\kappa)$.

$\endgroup$
7
  • 3
    $\begingroup$ This theorem was proved independently by Higman and De Bruijn in the 1950s: Higman, On infinite simple permutation groups. Publ. Math. Debrecen 3 (1954), 221–226 (1955); De Bruijn Embedding theorems for infinite groups. Nederl. Akad. Wetensch. Proc. Ser. A. 60 = Indag. Math. 19 1957 560–569. A proof can be found in W. Scott's Group theory book (1964), Theorem 11.2.5. McKenzie, 1971 more generally showed that any restricted direct product of $>\kappa$ non-abelian groups can't be embedded into $\mathrm{Sym}(\kappa)$ (DOI link). $\endgroup$
    – YCor
    Mar 28, 2021 at 9:38
  • $\begingroup$ @YCor Thank you for the comment. Unfortunately, it is too late. Our paper has been published in 2015 (as an answer to the question of Siegfried Bocherer exactly about the embeddability of symmetric groups). But I hope that the topological methods used in our proof are new anyway and do not reinvent what was known before. $\endgroup$ Mar 28, 2021 at 10:36
  • $\begingroup$ Actually the existence of a subgroup of a group $G$ that is a restricted direct product of $\lambda$ non-abelian subgroups implies that there is a chain of centralizer isomorphic to $\lambda$ as an ordinal. For $\lambda$ uncountable, this for instance already shows that $G$ doesn't embed in any separable metrizable group (including $\mathrm{Sym}(\omega)$ as a particular case). Possibly your work provides similar generalizations for $\kappa>\omega$? $\endgroup$
    – YCor
    Mar 28, 2021 at 11:03
  • $\begingroup$ For a space $X$, let $r(X)$ be the smallest cardinal $\alpha$ such that every closed subset in $X$ is the closure of a subset of cardinal $<\alpha$. Suppose that a group $G$ contains subgroups $(G_i)_{i\in I}$ such that for every $i$, the centralizer of $\bigcup_{j\neq i}G_j$ doesn't centralize $G_i$ (this exists in any restricted direct product of nonabelian groups indexed by $I$). Let $H$ be a Hausdorff topological group. Then $G$ doesn't embed in $H$ if $r(H)\le |I|$. (...) $\endgroup$
    – YCor
    Mar 28, 2021 at 11:54
  • $\begingroup$ (...) Indeed, if $G\subset H$, $\bigcup G_i$ has a dense subset of card $<|I|$, so $G_i$ is in the closure of $\bigcup_{j\neq i}$ for some $i$, so the centralizer of this union centralizes $H_i$, contradiction. Does this apply here? Is $r(H)$ known for $H=\mathrm{Sym}(\kappa)$ with its usual pointwise convergence topology? Is it equal to $\kappa^+$? $\endgroup$
    – YCor
    Mar 28, 2021 at 11:55

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.