For the entire post, assume that $\mathbb N$ is any countable set. (One may assume it to be the set of natural numbers. ) Further, let

$\mathcal S = \{ f_1 \dots : \mathbb N \to \mathbb N, f \text{ is a bijection} \}$

It is a familiar proof (due to Cantor) that the set of all functions from $\mathbb N$ to $\mathbb N$ is uncountable. But can the same be said about bijections of $\mathbb N$? Here are three proofs:

• We mimic the Cantor’s diagonal argument. Suppose that $\mathcal S$ is countable and enumerate its elements as $f_1, f_2, \dots$. We produce a bijection $f$ different from the $f_i$‘s. Partition $\mathbb N$ into two (disjoint) infinite sets $X$ and $Y$. Define $f(2)$ to be any element of $X$ other than $f_1(2)$. Having defined $f(2), f(4), \dots, f(2n-2)$, define $f(2n)$ to be any element of

$X \backslash \{ f(2), f(4), \dots, f(2n-2), f_n(2n) \}$.

We need to fill in the odd places of $f$ so that it is a bijection. Let $Z = \{ X\backslash \{ f(2n) : n \in \mathbb N \} \}$. Notice that $Z$ is infinite since $Y\subseteq Z$. Now map $Z$ bijectively with odd places of $f$.

This is a contradiction to the countability of $\mathcal S$.

• The second proof needs some facts from higher algebra. $\mathbb Q$ is countable. So is $\bar{\mathbb Q}$, its algebraic closure. Hence, there is a bijection between $\mathbb N$ and $\bar{\mathbb Q}$. Now, the automorphisms of $\bar{\mathbb Q}$ that fix $\mathbb Q$ are, in fact, bijections of $\bar{\mathbb Q}$, or to bijections of $\mathbb N$. In fact,

$\text{Gal }(\bar{\mathbb Q})/\mathbb Q)$ is a subgroup of $\mathcal S$.

That the former is uncountable is a (deep but) standard result in Algebraic Number Theory.

• For the third proof, I quote a result (due to Riemann) on the rearrangements of a conditionally-convergent series, from Rudin’s Principles of Mathematical Analysis, weakened as required in this context.

Theorem: Let $\sum a_n$ be a series of real numbers which converges but not absolutely. Suppose that

$-\infty \leq \alpha \leq \infty$.

Then there exists a rearrangement $\sum a_n'$ with partial sums $s_n'$ such that

$\displaystyle\lim_{n\to\infty} s_n' = \alpha$.

Take $\displaystyle a_n = \frac{(-1)^n}{n}$; it is conditionally convergent. For every (extended) real number, we have a rearrangement of the $a_n$‘s. Further the uniqueness of a limit in the complete metric space $\mathbb R$ suggests that the map (given by the theorem) from $\mathbb R \to \mathcal S$ is injective. Q.E.D.