What is aleph_0 factorial?

Question

In other words, what is the cardinality of the set of all permutations of the natural numbers?

Clearly, aleph_0 < aleph_0! <= aleph_0^aleph_0 = 2^aleph_0 = c,
but can it be proven that aleph_0! = c?

Ben's answer helped me see that there is an injection from 2^aleph_0 to aleph_0!. Any set S in P(N) maps to the permutation which sends any point in N\S to itself, and swaps every consecutive pair of points in S, starting with the smallest two. Forget about singleton sets because they are countable.

So aleph_0! = c (not aleph_1 unless CH!)

Answer 1

Edit: D'oh! I forgot that c is not necessarily the same as Aleph_1 ...

aleph_0! = 2^aleph_0 = c

Here is why. Using your reasoning above, we know that alphe_0! <= c

aleph_0! = aleph_0*(aleph_0 - 1)* ... *2*1 >= 2^aleph_0 = c

Thus aleph_0! = c

If you prefer an injection style argument, you can show an injection from the power set of aleph_0 to the set of permutations of aleph_0 by mapping any set S to the permutation that sends all x in N\S to x, and sends all x in S to the next larger element in S (or the smallest element if x is the largest in S).

Edit: D'oh, why can't a do a clean mapping any more, yes you are right my mapping maps all singleton sets to the identity permutation. If you like, then map the set {x} to the 3-cycle permutation (x x-1 x+1), that is x -> x-1, x-1 -> x+1, x+1 -> x, which is not the same as any of the other permutations in the image of my above mapping, since in the previous mapping {x-1,x, x+1) maps to the three cycle (x-1 x x+1).

Answer 2

My bad... I thought about it some more and read this link again and I've got to agree it would be c.

http://www.sjsu.edu/faculty/watkins/reals.htm

Good question.