# 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$. Jun 25, 2010 at 6:52
• A more general question: mathoverflow.net/questions/27785/… Jun 25, 2010 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/… Jun 5, 2014 at 6:21
• Another related post on MO: mathoverflow.net/questions/27785/… Sep 2, 2016 at 6:33
• I'm impressed by the level of elaboration of proofs of such a trivial fact.
– YCor
Mar 29, 2020 at 14:04

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. Jun 25, 2010 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. Jun 25, 2010 at 11:25
• Awesome! Unfortunately I have already accepted an answer. Jun 26, 2010 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. Jun 25, 2010 at 19:56
• I am trying to understand your solution. But I stuck at the word "cycles of length". Could you please explain me the meaning of "cycles of length". Apologies for any inconvenience. Jun 25, 2017 at 18:12

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. Jun 25, 2010 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. Jun 25, 2010 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... Jun 26, 2010 at 5:42

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.

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?

• No, that doesn't suffice. The set of all bijections on natural numbers can be mapped one-to-one both with the set of all subsets of natural numbers and with the set of all functions on natural numbers. In fact consider the following: the set of all finite subsets of an n-element set has $2^n$ elements. Does it follow that the set of all finite subsets of natural numbers is uncountable? No; that set (unlike the set of all subsets of natural numbers) is countably infinite. Dec 17, 2020 at 10:54