Welcome to MathOverflow

Question

9

1

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

flag	asked Jun 11 2010 at 5:36 Roy Maclean 630●4●19

Meaning how do you define infinite permutations? See also the related mathoverflow.net/questions/17653/… and mathoverflow.net/questions/1072/… – Gjergji Zaimi Jun 11 2010 at 5:53

1

A permutation is any bijection and the group operation is composition. What else? – Michael Greinecker Jun 11 2010 at 6:00

1

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$?". – Gjergji Zaimi Jun 11 2010 at 6:14

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). – Michael Hardy Jun 12 2010 at 16:26

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. – Michael Hardy Jun 12 2010 at 16:28

show 1 more comment

Robin Chapman · Accepted Answer · 2010-06-11 06:00:30Z UTC

17

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

edited Jun 11 2010 at 6:00

answered Jun 11 2010 at 5:52

Robin Chapman
14.5k●2●29●50

13

Which equals $2^k$, the cardinality of the power set of k. – Henno Brandsma Jun 11 2010 at 9:33

2

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. – Robin Chapman Jun 12 2010 at 7:22

Now I understand. Very nice! – Pierre-Yves Gaillard Jun 12 2010 at 7:58

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. – Joel David Hamkins Jun 12 2010 at 11:52

Same comment as above! – Pierre-Yves Gaillard Jun 12 2010 at 17:20

Andreas Blass · Answer 2 · 2012-01-25 01:28:19Z UTC

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

Pierre-Yves Gaillard · Answer 3 · 2010-06-12 04:51:02Z UTC

7

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

answered Jun 12 2010 at 4:51

Pierre-Yves Gaillard
543●2●10●16

1

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. – Henno Brandsma Jun 12 2010 at 6:58

(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" ... – Pierre-Yves Gaillard Jun 12 2010 at 7:12

Ralph · Answer 4 · 2012-01-24 23:01:22Z UTC

1

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.

edited Jan 24 2012 at 23:01

Ralph

answered Jan 24 2012 at 22:00

Steve0078
11●1

Why is there a fixed-point-free permutation of $X\setminus A$ ? – Ralph Jan 24 2012 at 23:06

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 – Gerhard Paseman Jan 24 2012 at 23:10

@Gerhard: What I wanted to point out is that the existence of such a permutation isn't that obvious, but needs some reasoning. – Ralph Jan 24 2012 at 23:33

1

@Gerhard: If $X$ is strongly amorphous then every partition has only finitely many non-singletons; so there cannot be a completely choice free argument. – Asaf Karagila Jan 25 2012 at 0:52

Cardinality of the permutations of an infinite set

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

4 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.