Factorial of Infinite Cardinal

Question

I have been thinking about the following problem:

Let $A$ be a set of cardinality $k$ and denote $\sum_A$ the set of all bijection from $A$ to $A$.

Also denote $k! = \mathrm{card}\left(\sum_A \right)$. Prove that $k!=2^k$.

My proof consists of finding a bijection $F:\sum_A\to P(A)$ which associates each bijection from the left to the set of its fixed points. Then the result would follow. ($P(A)$=the power set of $A$).

Since this proof seems quite easy I am afraid it is wrong. Can someone enlighten me? Thank you very much!

Answer 1

Hint:

• Every on $A$ bijection is a function from $A$ to $A$.
• Every function from $A$ to $A$ is a relation on $A\times A$.
• A relation on $A\times A$ is just a subset of $A\times A$.
• What's the cardinality of $A\times A$ when $A$ is infinite?

Answer 2

First of all, unless you limit yourself to infinite sets this statement is wrong. It is wrong because for $k=3$ we have $3!=6<8=2^3$.

For infinite sets, assuming the axiom of choice, this is true. To see why note that $f\colon A\to A$ means that $f\subseteq A\times A$, so $\Sigma_A\subseteq\mathcal P(A\times A)$.

Assuming the axiom of choice $|A|=|A\times A|$ and therefore $|\Sigma_A|\leq 2^k$. You still have to show the other direction holds as well. In order to show that, you need to find $2^k$ distinct bijections from $A$ to itself.

Hint: There are $2^k$ different pairs $A_1,A_2\subseteq A$ such that $\{A_1,A_2\}$ is a partition of $A$ and $|A_1|=|A_2|$. For every such pair we define a unique $f\colon A\to A$ which sends $A_1$ to $A_2$ and vice versa, conclude the wanted equality of cardinals.