12
$\begingroup$

Is there 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?

$\endgroup$
5

7 Answers 7

13
$\begingroup$

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.

$\endgroup$
60
$\begingroup$

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

$\endgroup$
3
  • 11
    $\begingroup$ Elegant! I wish I'd thought of this. $\endgroup$ Jun 25, 2010 at 10:21
  • 2
    $\begingroup$ 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. $\endgroup$ Jun 25, 2010 at 11:25
  • $\begingroup$ Awesome! Unfortunately I have already accepted an answer. $\endgroup$ Jun 26, 2010 at 7:03
4
$\begingroup$

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.

$\endgroup$
2
  • 4
    $\begingroup$ @Qiaochu: Of course your first statement is true, but some justification seems necessary. $\endgroup$ Jun 25, 2010 at 19:56
  • $\begingroup$ 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. $\endgroup$
    – Bumblebee
    Jun 25, 2017 at 18:12
3
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ I see now that I am essentially copying Pierre-Yves Gaillard's answer to the question he links to in the comments above. $\endgroup$ Jun 25, 2010 at 20:09
  • $\begingroup$ @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. $\endgroup$ Jun 25, 2010 at 22:31
  • 1
    $\begingroup$ @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... $\endgroup$ Jun 26, 2010 at 5:42
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

For each $\alpha >1$ define $f_\alpha: 2 \mathbb N \to \mathbb N$ via $$ f_\alpha(2n)= \lfloor 2n \alpha \rfloor $$

It is easy to argue that $f_\alpha = f_\beta \Leftrightarrow \alpha =\beta$.

Now, since $f_\alpha$ is one to one and its range has infinite complement in $\mathbb N$, it is easy to argue that it can be extended to a bijection on $\mathbb N$.

This allows us to embed $[1, \infty)$ into the set of bijections on $\mathbb N$.

Alternate construction

For each (binary) number $a=0.a_1a_2\ldots a_n \ldots \in [0,1)$ define $$ f_a(2n)=2n+a_1+a_2+\ldots +a_n $$ Extend this to a bijection.

$\endgroup$
-1
$\begingroup$

Lets call the set of one to one functions from $\mathbb{N}$ to $\mathbb{N}$ $$\mathcal{F}=\{f:\mathbb{N}\rightarrow\mathbb{N}: f \text{ is one to one}\}$$ we know that $\vert\mathcal{P}(\mathbb{N})\vert>\vert\mathbb{N}\vert$ so it suffices to find an injection $$g:\mathcal{P}(\mathbb{N})\rightarrow\mathcal{F}$$ So the idea is that for every $A \subseteq\mathbb{N}$ you pick your $f\in\mathcal{F}$ such that for every element $n\in A$, $f(n)=n$ and if not then $f(n)\not=n$. So there is only one problem with this and it's that if you take that function $g$ from $\mathcal{P}(\mathbb{N})$ then it is not an injection because for every set $A$ such that $\mathbb{N}\backslash A=\{a\}$ the function $f=g(A)$ does not work, because it forces that $f(a)=a$ and our function does not work with that. But we can solve that. Now let $$C=\{A\subseteq\mathbb{N}:\vert \mathbb{N}\backslash A\vert=1\}$$ Clearly $C$ is countable because it has a one to one function to $\mathbb{N}$ so $\mathcal{P}(\mathbb{N})\backslash C$ remains not countable. Now lets restrict our function to that domain, so we got: $$g:\mathcal{P}(\mathbb{N})\backslash C\rightarrow\mathcal{F}$$ with the same rule of assigment from before, and now $g$ is clearly injective because every function $g(A)=f_A:\mathbb{N}\rightarrow\mathbb{N}$ has fixed points (points where $f(n)=n$) only on the elements of $A$.

$\textit{I just read the forum and someone used the same idea lol.}$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.