21
$\begingroup$

If you have an infinite set X of cardinality k, then what is the cardinality of Sym(X) - the group of permutations of X ?

$\endgroup$
7
  • $\begingroup$ Meaning how do you define infinite permutations? See also the related mathoverflow.net/questions/17653/infinite-permutations and mathoverflow.net/questions/1072/… $\endgroup$ Jun 11, 2010 at 5:53
  • 4
    $\begingroup$ A permutation is any bijection and the group operation is composition. What else? $\endgroup$ Jun 11, 2010 at 6:00
  • 1
    $\begingroup$ Well, there are other notions, some mentioned in the thread above. That is why I would have preferred the question "How many bijections are there $X\to X$?". $\endgroup$ Jun 11, 2010 at 6:14
  • $\begingroup$ A permutation is a bijection from a set to itself, not just any bijection. (Isn't it? After all, that's what makes it possible to speak of a group operation.) I once thought the convention of defining a permutation of a finite set as a linear order was excessively complicated by comparison to defining it simply as a bijection from the set to itself. But one sometimes wants to speak of the number of permutations of size $k$ from a set of size $n > k$ (and that number is a falling factorial). $\endgroup$ Jun 12, 2010 at 16:26
  • 1
    $\begingroup$ Now I'm remembering something: "A torsor is like a group that has forgotten its identity." Maybe one could allow bijections from a set to another set and speak of a "permutation torsor" rather than of a "permutation group". There's a group that acts on this set of permutations, and of course the group has an identity element, but then no permutation would have a distinguished role. $\endgroup$ Jun 12, 2010 at 16:28

4 Answers 4

26
$\begingroup$

$k^k$.

Easy that it's an upper bound. For lower bound split $X$ into two equinumerous subsets; there are $\ge k^k$ permutations swapping the two subsets.

$\endgroup$
5
  • 16
    $\begingroup$ Which equals $2^k$, the cardinality of the power set of k. $\endgroup$ Jun 11, 2010 at 9:33
  • 6
    $\begingroup$ Following Professor Gaillard's answer, I'm not sure I understand my argument either. An alternative way of exhibiting $k^k$ permutations of $X$ is to do this. Note that $|X|=|X\times X|$ so we only need to exhibit $k^k$ permutations of $X\times X$. Let $x_0\in X$. For each $f:X\to X$ there is an involution swapping each $(x,x_0)$ with $(x,f(x))$ and fixing everything else. There are $k^k$ of these. $\endgroup$ Jun 12, 2010 at 7:22
  • $\begingroup$ Now I understand. Very nice! $\endgroup$ Jun 12, 2010 at 7:58
  • 3
    $\begingroup$ Robin, I understood your original argument like this: once you split $X$ into two equinumerous pieces $A\cup B$, then every subset $Y\subset A$ determines a permutation: you apply the bijection $A\cong B$ only to the elements of $Y$ (and inversely to their images), and fix the rest. $\endgroup$ Jun 12, 2010 at 11:52
  • $\begingroup$ Same comment as above! $\endgroup$ Jun 12, 2010 at 17:20
17
$\begingroup$

As already mentioned, we have $$2^k\le k^k\le(2^k)^k=2^{kk}=2^k,$$ and thus $2^k=k^k$. The inequality $k!\le k^k$ is obvious. To check $2^k\le k!$, note that $2^k$ subsets of $X$ are the set of fixed points of some permutation. Conclusion: $k!=2^k$.

(I don't understand Robin Chapman's argument.)

$\endgroup$
2
  • 7
    $\begingroup$ Another way to see $2^k \le \factorial{k}$: split X into $k$ many pairs. For every pair we can either swap it or not, giving us k choices of 2, so at least $2^k$ many bijections. $\endgroup$ Jun 12, 2010 at 6:58
  • 1
    $\begingroup$ (My browser can't read your k!) I hesitated to give this argument. I told myself "the most naive way to attach a subset to a permutation is to form the set of fixed points" ... $\endgroup$ Jun 12, 2010 at 7:12
17
$\begingroup$

Since the comments on Steve0078's answer raise issues concerning the axiom of choice, let me point out that John Dawson and Paul Howard have shown that, in choiceless set theory, the number of permutations of an infinite set $X$ can consistently be related to the number of subsets of $X$ by a strict inequality in either direction; the two numbers can also be incomparable; and of course they can be equal as in the presence of choice. (Slogan: Without choice, nothing can be proved about those two cardinals.) The reference for this is "Factorials of Infinite Cardinals" in Fundamenta Mathematicae 93 (1976) pp. 186-195 (Math Reviews volume 55 #7779).

$\endgroup$
1
4
$\begingroup$

Here is another solution: $X$ is infinite and so there are two elements $x_1$ and $x_2$. Let $X'=X\setminus \lbrace x_1,x_2\rbrace$. I have that $|X|=|X'|$ and so $|P(X)|=|P(X')|$. Let $A$ be a subset of $X'$ and so $|X\setminus A|\ge 2$. Then there exist a permutation $f:X\setminus A \to X\setminus A$ without fixed points. Then I extend $f$ to $X$ leaving fixed the elements of $A$. The set of the points fixed by $f$ is then $A$. So I have a surjection $Sym(X) \to P(X')$. Hence $|Sym(X)| \ge |P(X')|=|P(X)|$. That $|Sym(X)| \le |P(X)|$ is easy.

$\endgroup$
4
  • $\begingroup$ Why is there a fixed-point-free permutation of $X\setminus A$ ? $\endgroup$
    – Ralph
    Jan 24, 2012 at 23:06
  • $\begingroup$ Assuming AC, X\A can be divided into subsets of size 2 or 3, and on each subset one has a cycle which has no fixed points. There may be Choice-free justifications as well. Gerhard "Ask Me About System Design" Paseman, 2012.01.24 $\endgroup$ Jan 24, 2012 at 23:10
  • $\begingroup$ @Gerhard: What I wanted to point out is that the existence of such a permutation isn't that obvious, but needs some reasoning. $\endgroup$
    – Ralph
    Jan 24, 2012 at 23:33
  • 1
    $\begingroup$ @Gerhard: If $X$ is strongly amorphous then every partition has only finitely many non-singletons; so there cannot be a completely choice free argument. $\endgroup$
    – Asaf Karagila
    Jan 25, 2012 at 0:52

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.