Is there an easy proof of the uncountability of bijections on natural numbers?
The proof that I have in mind is as follows -
$\text{Gal }(\overline{\mathbb Q}/\mathbb Q)$ is a proper uncountable subgroup of the group of permutations on countably many symbols, hence the latter is uncountable. .
But it needs a lot of jargon from topology and algebra. Is there a neat proof like Cantor's diagonal argument?
Indeed, Cantor's argument is readily adapted. Let $\pi_1,\pi_2,\pi_3, \ldots $ be any countable sequence of permutations of $\mathbb N$ ; let us show that this sequence does not exhaust all permutations, by constructing a permutation $\pi$ different from all the $\pi_i$. We first define $\pi$ on the even integers inductively, then define $\pi$ on the odd integers.
Let $X$ be any subset of $\mathbb N$ such that both $X$ and ${\mathbb N} \setminus X$
are infinite (e.g. the even integers, the prime numbers ...).
Set $\pi(0)$ to be an integer in $X$ different from $\pi_1(0)$. Set $\pi(2)$ to be an integer in $X$ not in $\lbrace \pi(0),\pi_2(2)\rbrace$. Set $\pi(4)$ to be an integer in $X$ not in $\lbrace \pi(0),\pi(2)\pi_3(4)\rbrace$. Continuing like this inductively, we define an injection from the even integers to $X$,
such that $\pi(2k-2) \neq \pi_k(2k-2)$ for any $k$ (and hence $\pi \neq \pi_k$).
Finally, the set A=${\mathbb N} \setminus \pi(2\mathbb N)$ is countably infinite ; setting $\pi(2k-1)=$ the $k$-th element of $A$ finishes the proof.
The fact that any conditionally convergent series [and that such exists] can be rearranged to converge to any given real number $x$ proves that there is an injection $P$ from the reals to the permutations of $\mathbb{N}$. The usual proof (pick positive terms until we exceed $x$, pick negative terms until we "deceed" $x$, repeat) is constructive; if we use a series consisting of easily computable rational numbers (the alternating harmonic series being the canonical example) and a real number $x$ for which we can decide $q<x$ or $q>x$ or $q=x$ for every rational number $q$, we may compute $P(x)(n)$ for every $n$.
Bijections of the natural numbers are equinumerous with functions $\mathbb{N} \to \mathbb{N}$, which are equinumerous with continued fraction expansions of positive irrational numbers.
Edit: Here's one proof of the first assertion. Clearly there are at most as many bijections $\mathbb{N} \to \mathbb{N}$ as functions $\mathbb{N} \to \mathbb{N}$. On the other hand, for any function $f : \mathbb{N} \to \mathbb{N}$ there exists a bijection with $f(i)$ cycles of length $i$. Now apply Cantor-Schroeder-Bernstein.
Consider the following map $\Phi$ from bijections of the natural numbers to subsets of the natural numbers: to each bijection $\sigma$, associate its fixed point set $S(\sigma) = \{x \in \mathbb{N} \ | \ \sigma(x) = x \}$.
It is easy to see that this map is almost surjective: the only subsets which are not in the image are those whose complement consists of a single element. Indeed, a subset of the natural numbers admits a fixed point free permutation iff it does not consists of a single element. In particular, the complement of the image of $\Phi$ is countable. Since the codomain of $\Phi$ is uncountable, so therefore is the image of $\Phi$.
This shows that the set of bijections is uncountable. By the usual Schroder-Bernstein argument, it follows that it has continuum cardinality.
I'm not sure what counts as an "easy" proof, but the following seems easy to me. Make a subtree of $\mathbb{N}^{<\mathbb{N}}$ by declaring that a sequence $\sigma$ is in the subtree if (1) $\sigma$ is injective and (2) whenever $\sigma(2n+2)$ is defined, it is equal to the least natural number not in the range of $\sigma \upharpoonright (2n+2)$. Then any path through this tree is a bijection of $\mathbb{N}$, and the tree is perfect because any sequence of even length has infinitely many immediate extensions in the tree (any number not already in the range is a candidate). So the tree has continuum-many paths.
Lets call the set of one to one functions from $\mathbb{N}$ to $\mathbb{N}$ $$\mathcal{F}=\{f:\mathbb{N}\rightarrow\mathbb{N}: f \text{ is one to one}\}$$ we know that $\vert\mathcal{P}(\mathbb{N})\vert>\vert\mathbb{N}\vert$ so it suffices to find an injection $$g:\mathcal{P}(\mathbb{N})\rightarrow\mathcal{F}$$ So the idea is that for every $A \subseteq\mathbb{N}$ you pick your $f\in\mathcal{F}$ such that for every element $n\in A$, $f(n)=n$ and if not then $f(n)\not=n$. So there is only one problem with this and it's that if you take that function $g$ from $\mathcal{P}(\mathbb{N})$ then it is not an injection because for every set $A$ such that $\mathbb{N}\backslash A=\{a\}$ the function $f=g(A)$ does not work, because it forces that $f(a)=a$ and our function does not work with that. But we can solve that. Now let $$C=\{A\subseteq\mathbb{N}:\vert \mathbb{N}\backslash A\vert=1\}$$ Clearly $C$ is countable because it has a one to one function to $\mathbb{N}$ so $\mathcal{P}(\mathbb{N})\backslash C$ remains not countable. Now lets restrict our function to that domain, so we got: $$g:\mathcal{P}(\mathbb{N})\backslash C\rightarrow\mathcal{F}$$ with the same rule of assigment from before, and now $g$ is clearly injective because every function $g(A)=f_A:\mathbb{N}\rightarrow\mathbb{N}$ has fixed points (points where $f(n)=n$) only on the elements of $A$.
$\textit{I just read the forum and someone used the same idea lol.}$
For each $\alpha >1$ define $f_\alpha: 2 \mathbb N \to \mathbb N$ via $$ f_\alpha(2n)= \lfloor 2n \alpha \rfloor $$
It is easy to argue that $f_\alpha = f_\beta \Leftrightarrow \alpha =\beta$.
Now, since $f_\alpha$ is one to one and its range has infinite complement in $\mathbb N$, it is easy to argue that it can be extended to a bijection on $\mathbb N$.
This allows us to embed $[1, \infty)$ into the set of bijections on $\mathbb N$.
Alternate construction
For each (binary) number $a=0.a_1a_2\ldots a_n \ldots \in [0,1)$ define $$ f_a(2n)=2n+a_1+a_2+\ldots +a_n $$ Extend this to a bijection.
