If you have an infinite set X of cardinality k, then what is the cardinality of Sym(X) - the group of permutations of X ?
$\begingroup$
$\endgroup$
7
asked Jun 11, 2010 at 5:36
-
$\begingroup$ Meaning how do you define infinite permutations? See also the related mathoverflow.net/questions/17653/infinite-permutations and mathoverflow.net/questions/1072/… $\endgroup$– Gjergji ZaimiCommented Jun 11, 2010 at 5:53
-
4$\begingroup$ A permutation is any bijection and the group operation is composition. What else? $\endgroup$– Michael GreineckerCommented 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$– Gjergji ZaimiCommented 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$– Michael HardyCommented 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$– Michael HardyCommented Jun 12, 2010 at 16:28
|
Show 2 more comments
4 Answers
$\begingroup$
$\endgroup$
5
$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.
answered Jun 11, 2010 at 5:52
-
17$\begingroup$ Which equals $2^k$, the cardinality of the power set of k. $\endgroup$ Commented 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$ Commented Jun 12, 2010 at 7:22
-
$\begingroup$ Now I understand. Very nice! $\endgroup$ Commented 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$ Commented Jun 12, 2010 at 11:52
-
$\begingroup$ Same comment as above! $\endgroup$ Commented Jun 12, 2010 at 17:20
$\begingroup$
$\endgroup$
2
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
-
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$ Commented 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$ Commented Jun 12, 2010 at 7:12
$\begingroup$
$\endgroup$
1
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).
answered Jan 25, 2012 at 1:28
-
3$\begingroup$ Here is a link to the article: matwbn.icm.edu.pl/ksiazki/fm/fm93/fm93119.pdf $\endgroup$– Asaf Karagila ♦Commented Jan 25, 2012 at 8:52
$\begingroup$
$\endgroup$
4
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.
-
$\begingroup$ Why is there a fixed-point-free permutation of $X\setminus A$ ? $\endgroup$– RalphCommented 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$ Commented 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$– RalphCommented 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 ♦Commented Jan 25, 2012 at 0:52