# 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?

-
There are $2^{\aleph_0}$ permutations $\pi$ of $\mathbb{N}$ with the property that for each $n$ either $\pi(2n-1)=2n-1$ and $\pi(2n)=2n$, or $\pi(2n-1)=2n$ and $\pi(2n)=2n-1$. –  Robin Chapman Jun 25 '10 at 6:52
A more general question: mathoverflow.net/questions/27785/… –  Pierre-Yves Gaillard Jun 25 '10 at 9:26
There are also several posts on MSE about cardinality of the set of all bijections $\mathbb N\to\mathbb N$, for example: math.stackexchange.com/questions/87902/… and math.stackexchange.com/questions/367194/… –  Martin Sleziak Jun 5 '14 at 6:21

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$.

-
Elegant! I wish I'd thought of this. –  John Stillwell Jun 25 '10 at 10:21
One set of reals x for which you can decide which of q < x or q > x or q=x holds is the set of irrationals, when reals are represented as either Cauchy sequences or Dedekind cuts. However, there is no single algorithm that takes an arbitrary convergent Cauchy sequence x of rationals and a rational q and tells whether q < x. –  Carl Mummert Jun 25 '10 at 11:25
Awesome! Unfortunately I have already accepted an answer. –  Abhishek Parab Jun 26 '10 at 7:03

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.

-
@Qiaochu: Of course your first statement is true, but some justification seems necessary. –  Pete L. Clark Jun 25 '10 at 19:56

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.

-

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 see now that I am essentially copying Pierre-Yves Gaillard's answer to the question he links to in the comments above. –  Pete L. Clark Jun 25 '10 at 20:09
@Pete That's basically the arguement I tried to give below,Pete-except I used the indicator map on the power set of N.I think it gives a similar result.Thanks for stating it more carefully then I did. –  Andrew L Jun 25 '10 at 22:31
@Andrew: I was among the readers who did not understand your argument. If I may offer advice: your posts come off as logically disorganized and have spelling and punctuation mistakes. Many (most?) mathematicians take these things seriously: for my part, I remember explaining to two undergraduates that they would have gotten a higher grade on their final project on the theorem on arithmetical progressions in the primes if they had spelled Professor Tao's first name correctly. (I allowed them to fix it.) Probably you don't want to get "points taken off" for such avoidable errors... –  Pete L. Clark Jun 26 '10 at 5:42

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?

-