1

Problem: Prove that the set of all bijective functions over the natural numbers is uncountable.

I have already seen a lot of answers to this problem and there seems to be always a part where the natural numbers are partitioned into two countable infinite subsets of $\mathbb{N}$. Am I missing something? I have come up with the following proof and I am suspicious that there might be a mistake somewhere.

I use the fact that there exists a bijection between the set of all bijective functions on $\mathbb{N}$ and the set of all permutations of $\mathbb{N}$. That part should not be the problem as far as I understand.

I use Cantor's diagonalization argument in the following way: Let $\pi_{i}$ be the i-th permutation in a list of all permutations on $\mathbb{N}$. The ability to list all permutations would give us a enumeration making the set countable, we therefore assume that such list exist and make a proof by contradiction:

Let the list of all permutations be $(\pi_{1},\pi_{2},\pi_{3},\pi_{4},...)$, we now define a permutation $\pi$ in the following way:

$\pi(0) \in $ $\mathbb{N} \backslash \{\pi_{1}(0)\} $
$\pi(1) \in $ $\mathbb{N} \backslash \{\pi(0), \pi_{2}(1)\} $
$\pi(2) \in $ $\mathbb{N} \backslash \{\pi(0), \pi(1), \pi_{3}(2)\} $
.
.
.
$\pi(k) \in $ $\mathbb{N} \backslash \{\pi(0), \pi(1), ...,\pi(k - 1), \pi_{k+1}(k)\} $

I would then conclude the proof by stating that above permutation is not in the list, which is a contradiction to our assumption and therefore the set of all permutations cannot be countable, therefore being uncountable. Is this correct? I appreciate the help.

Aaronzeller
  • 23
  • You haven´t proved that you can find the $\pi(k)$ in such a way that $\pi$ is a permutation (that is, that it´s bijective). – Saúl RM Jan 29 '21 at 16:04
  • @SaúlRodríguez Would work with induction or does the problem lay there? The proof does not have to be constructive, it should suffice to state that for any k the sum of all previous elements that are in the permutation is not yet in the permutation and can therefore be chosen as the next element. – Aaronzeller Jan 29 '21 at 16:10
  • I don´t think the problem will be very hard to solve, but some change have to be made. Imagine for example that $\pi_n(n+1)=1$ for all $n$, which can perfectly happen. Then you couldn´t have $\pi(k)=1$ for any $k$, so $\pi$ couldn´t be bijective (it wouldn´t be a permutation). – Saúl RM Jan 29 '21 at 17:09
  • That is absolutely true, is there a way around that? Maybe we could arrange the permutations in a way that that does not happen in general? – Aaronzeller Jan 29 '21 at 17:19
  • There may be ways to rearrange the permutations to do that. I´ll give other possible fix of the argument in an answer. – Saúl RM Jan 29 '21 at 17:55

1 Answers1

0

You have to assure that you can define $\pi$ in such a way that it is a permutation. Here is one way to do that. Let a list of all permutations be $(\pi_{1},\pi_{2},\pi_{3},\pi_{4},\dots)$. $\pi$ will also be defined recursively.

For every $n$, define $\pi(2n)$ to be the least natural number in $\mathbb{N} \backslash \{\pi(0), \pi(1), ...,\pi(2n - 1), \pi_n(2n)\}$. And define $\pi(2n+1)$ to be the least natural number in $\mathbb{N} \backslash \{\pi(0), \pi(1), ...,\pi(2n - 1), \pi(2n)\}$. $\pi$ will be injective, and the definition in the odd numbers forces it to be surjective. It is also different from all the $\pi_n$.

Saúl RM
  • 3,393