# Cardinality of the set of permutations of a set $A$

I've some trouble calculating the cardinality of the set of the permutations of a given set $A$. For notational purpose let $k = |A|$ and define $P_A = \{ f : A \to A | f \text{ is a bijective function } \}$

Clearly if $A$ is a finite set, the cardinality of $P_A$ is $k!$, but the interesting case is when $A$ is infinite. Again, it is obvious that $|P_A| \leq 2^k$. But i can't find neither a lower upper bound or the lower bound to conclude by Schroeder-Berstein. Any hints or corrections? Thanks in advance!

Following the hint given by Asaf Karagila, I worked out this answer:

I'll put [AC] where i used AC to prove the following fact

So starting from [AC] $k \cdot k = k$ [AC] there exists a family of $k$ pairwise disjoint subset of $A$ each of them of cardinality $k$. Let's call them $\{ B_i \}_{i \in k}$. Let $F := { f \colon k \to \{0, 1} | \text{ f is a function } \}$. Define $F^* := F \setminus \text{ costant functions }$. Note that $|F^*|= 2^k$. For each $f \in F^*$ let $J_f :=\{i \in k | f(i) =1\}$ and let $U_f := \{ \bigcup_{j \in J_f} B_j \}$. It is immediate to prove that for each $f$ we have $|U_f|=|U_f^c| =k$. So we have the $2^k$ partitions of $A$. With a little abuse of notations I denote with $2^k$ an index set of this size. For each $i \in 2^k$ let $(P1_i, P2_i)$ a partition of $A$. [AC] for each partition choose one bijection $g_i: P1_i \to P2_i$. Now we can define $2^k$ permutations in this way. For each $i\in 2^k$ let $h_i : A \to A$ with $h_i(a)=g_i(a)$ if $a \in P1_i$ otherwise $h_i = g^{-1}$. is is easy to see that it is a permutation.

• Sorry to be slow, but what's your obvious injection of $P_A$ into the powerset of $A$ getting $|P_A|\leq 2^k$? – Kevin Carlson Feb 3 '14 at 20:38
• @Kevin, $P_A\subseteq\mathcal P(A\times A)$. – Asaf Karagila Feb 3 '14 at 20:40
• @Asaf Karagila i was ispired by one of your (very good) answer (math.stackexchange.com/questions/191006/… ) when you say "there are $2^k$ way of enumerating a set in $[ A]^k$" so i supposed that if two functions "differ" by a permutation of the domain they enumerate the same subset – Riccardo Feb 3 '14 at 20:58
• And so tried to calculate the size of the set – Riccardo Feb 3 '14 at 20:59
• A (probably) silly question: by constant functions in $F$ do you mean $f_0(i) = 0, f_1(i) = 1, i \in k$? So $\text{card}~F^* = \text{card}~F - 2 = 2^k - 1 = 2^k$? – Andrey Surovtsev Aug 17 at 14:17

HINT: Prove that there are $2^k$ partitions of $A$ into equipotent two parts. Given such partition $\{A_1,A_2\}$ choose a bijection $f\colon A_1\to A_2$ and use $f$ to define a permutation of $A$.

Note the heavy use of the axiom of choice. It is needed.

Based on the suggested solution, here's a much better outline for a solution:

Fix a bijection $f\colon A\to A\times A$, and fix a permutation of $A$ which is not the identity, $\pi$. Now given $A'\subseteq A$ define a permutation of $A\times A$, $$\pi_A(a,b)=\begin{cases}(a,\pi b) & a\in A'\\ (a,b) & a\notin A'\end{cases}$$

This defines $2^{|A|}$ permutations of $A\times A$, and therefore of $A$.

• Ok, now I try to work it out the hints – Riccardo Feb 3 '14 at 21:43
• Mmmh it doesn't allow me to post long comments, I'll edit my question, can you please check the reasoning? I'm interested in quoting correctly when AC is needed – Riccardo Feb 3 '14 at 22:28
• @Steven: I think that it's provably never $|A|$. Also note that every set has a cardinality, it just doesn't have to be an $\aleph$ number. Some sets would have strictly more than $2^{|A|}$ permutations, but I'm not sure how well we can fine tunes these inequalities. Controlling power sets cardinality is one of the greatest challenges when creating models of set theory. – Asaf Karagila Feb 3 '14 at 22:48
• @Ric: No. Just any non-trivial permutation works. Try to see why! – Asaf Karagila Feb 4 '14 at 9:57
• @AndreySurovtsev: Yes, that's the idea. You're right about the subscript, but I think it's best to not make trivial edits like that on posts which are this old, so I'm just going to keep it this way for now. – Asaf Karagila Aug 18 at 8:31