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.