An easy proof of the uncountability of bijections on natural numbers? - MathOverflow

An easy proof of the uncountability of bijections on natural numbers?

2010-06-25T06:47:53Z

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?

Answer by Ewan Delanoy for An easy proof of the uncountability of bijections on natural numbers?

2010-06-25T07:07:19Z

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.

Answer by villemoes for An easy proof of the uncountability of bijections on natural numbers?

2010-06-25T09:30:21Z

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

Answer by Carl Mummert for An easy proof of the uncountability of bijections on natural numbers?

2010-06-25T11:32:50Z

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.

Answer by Qiaochu Yuan for An easy proof of the uncountability of bijections on natural numbers?

2010-06-25T15:06:04Z

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.

Answer by Pete L. Clark for An easy proof of the uncountability of bijections on natural numbers?

2010-06-25T20:02:33Z

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.

Answer by Adam Kapelner for An easy proof of the uncountability of bijections on natural numbers?

2012-11-27T17:16:01Z

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?