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?
 A: 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$.
A: 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.
A: 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.    
A: 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.   
A: 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. 
A: I think there's an easier proof but I can't quite do every step.
Imagine the bijection from $f : A \longrightarrow A$ where $A = \{1,2,3\}$. 1 can be mapped to 3 numbers, 2 can be mapped to the remaining 2 numbers and 3 can be mapped to 1 number. Hence the size of the size of the bijection is the factorial of the size of the set being mapped, ie $|A|!$. 
Thus, the size of the bijection $f : \mathbb{N} \longrightarrow \mathbb{N}$ should be $|\mathbb{N}|!$ which is clearly bigger than $2^{|\mathbb{N}|}$, hence it is uncountable.
Can you let me know if this suffices?
