I was solving the following exercise : Is $\mathfrak{S}(\mathbb{N})$ countable ? Here $\mathfrak{S}$ stands for the set of bijections from $\mathbb{N}$ to itself. A proof could be to build an surjection from $\mathfrak{S}(\mathbb{N}) \rightarrow \mathcal{P}(\mathbb{N})$ (the power set of $\mathbb{N})$. I nonetheless had an intuition that i struggle to formalize.
It is known that for $n \in \mathbb{N}^*$, $|\mathfrak{S}(\{0,1,...,n-1\})| = n!$, and that $|\mathcal{P}(\{0,1,...,n-1\})| = 2^n$ (where |.| denotes the cardinality function).
Note that the functions used in the previous paragraph are not the same as those defined on $\mathbb{N}$, their domain is some finite segment of $\mathbb{N}$.
It is clear that $n! > 2^n$ for $n \ge 4$, and the first one grows much faster than the second one. My question is the following : is there any result stating we can "go to the limit" and thus $|\mathfrak{S}(\mathbb{N})| \ge |\mathcal{P}(\mathbb{N})|$, solving the exercise (as the second one is not countable) ?
Thank you
No, the behavior of the finite segments doesn't tell you anything either way. It can't distinguish the full symmetric group from the subgroup of bijections that fix all but finitely many elements of $\mathbb{N}$, which is countable; similarly it can't distinguish the full powerset from the set of finite subsets of $\mathbb{N}$, which is also countable.
To my mind it's easier to write down an injection $P(\mathbb{N}) \to \text{Aut}(\mathbb{N})$. This can be done in many ways; for example given a subset $S \subseteq \mathbb{N}$ we can construct a permutation which has cycles of length $s$ for exactly $s \in S$ (this is even an injection from $P(\mathbb{N})$ into the set of conjugacy classes in $\text{Aut}(\mathbb{N})$).