1
$\begingroup$

Is the factorial of an uncountably infinite set also uncountably infinite? And, if so, is it a larger infinity?

For context, I'm working on a problem in which I need to find the number of permutations of a power set, ℘{F}. {F} is either finite or countably infinite. I understand the number of permutations, in this case, is equal to (2^|F|)!. So, I was wondering if (2^|F|)! is well-defined when |F| is countably infinite.

Thanks.

$\endgroup$
  • $\begingroup$ Welcome to math.se. Related, possibly just what you want: mathoverflow.net/questions/29475/… $\endgroup$ – Ethan Bolker Aug 19 '17 at 17:50
  • $\begingroup$ Instead of phrasing it as "the factorial of (the cardinality of) an uncountably infinite set" (we talk about factorials of numbers, not sets) you should phrase it as the number of bijections from an uncountably infinite set to itself. The answer to that should be clear that yes it is also uncountably infinite (let $a$ be an element of your set. Then for each $b$ different than $a$ define $f_b(x)=\begin{cases}b&\text{if}~x=a\\a&\text{if}~x=b\\x&\text{otherwise}\end{cases}$ As there are uncountably many choices for $b$, there are uncountably many such $f$, making a subset of what you want) $\endgroup$ – JMoravitz Aug 19 '17 at 18:30
  • $\begingroup$ I see. Yes, that makes sense. Thank you very much @JMoravitz $\endgroup$ – mjpcampbell Aug 19 '17 at 18:46
2
$\begingroup$

If $A$ is any infinite set, there are exactly as many permutations of $A$ as there are subsets of $A$. This is easy to see if you know

  1. That $|A|=|A\times A|$. This requires the axiom of choice in general, but if $A$ is equinumeraous to $\mathbb N$ or $\mathbb R$ there are elementary proofs that don't depend on AC.
  2. The Cantor-Bernstein theorem.

First, there are at least as many permutations of $A\times A$ as there are subsets of $A$. Namely, choose one nontrivial permutation $\sigma$ of $A$, and then for each subset $B\subseteq A$ we can consider the permutation $$ f_B(x,y) = \begin{cases} (x,\sigma(y)) & \text{if }x \in B \\ (x,y) & \text{otherwise} \end{cases}$$ It ought to be evident that different $B$ give different $f_B$.

Second, there are at least as many subsets of $A\times A$ as there are permutations of $A$. Namely, each permutation of $A$ is a subset of $A\times A$ (but not all such subsets are permutations).

$\endgroup$
0
$\begingroup$

There are $2^{\mathfrak c}$ permutations. The number of permutations is less than or equal to the number of continuum length sequences of reals, which is $\mathfrak c^{\mathfrak c}$. Given one permutation, which AC guarantees you exists as a well order, you can find $2^{\mathfrak c}$ by splitting it into pairs, taking all the binary strings of length $\mathfrak c$ and swapping pairs that correspond to $1$s.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.