In Cantor's Diagonalization Argument, why are you allowed to assume you have a bijection from naturals to rationals but not from naturals to reals?

Solution 1:

When you say "we're not allowed to assume that the mapping from the naturals to the reals is a bijection to begin with", what you're referencing is the nature of the proof by contradiction; we did assume that the mapping was a bijection, and we derived a contradiction by producing a number that was missed by the map. Hence, we proved that no such bijection can possibly exist. In the strictest sense, you're "allowed" to assume a bijection between the naturals and the reals; you'll just find that you can derive a contradiction from that assumption via Cantor's diagonalization argument.

Similarly, you might try and take the same approach of assuming there is a bijection between the natural numbers and the rational numbers. You could try and apply Cantor's diagonalization argument to prove that it can't be surjective, but as your quoted answer explains, this doesn't work. Moreover, a bijection between the natural numbers and rational numbers can, in fact, be constructed. This means that, try as you might, if you do everything correctly, you'll never be able to derive a contradiction from this assumption.

Solution 2:

$${p\over q} \mapsto 2^{p+|p|}3^{|p|}5^{q}͵$$ for $p\over q$ any rational in reduced form, with $q>0$, gives an injection from the rationals to the natural numbers. Since all infinite sets of integers have the same cardinality, we are done.

Solution 3:

As I see it, the core of the problem here is to understand what exactly the diagonal argument shows and what can be concluded from it. Let $S\subseteq\mathbb R$ be any subset of real numbers

1. Assume we have found an enumeration of all the elements of $S$ using the natural numbers

2. Apply Cantor's diagonal argument to construct a number $x$ not in the list

Now, the assumption in 1. may be true or not true. If it is false we may find a contradiction in 2.

Regarding 2. it will always be possible, since the diagonal argument is constructive and always works. BUT all we know is that the constructed diagonal number $x$ is some real number that is not in the list. The construction itself reveals nothing about whether $x$ belongs to $S$ or not.

We can only arrive at a contradiction if we also know (or show) that $x$ belongs to $S$. But since all we know about $x$ is that it belongs to $\mathbb R$ the contradiction will only work for $S=\mathbb R$ and be inconclusive for other sets $S\subseteq \mathbb R$ unless some additional arguments are added. The latter is the case for the rationals. Other arguments provides a bijection between the naturals and the rationals, but that is an independent and different story ...

Solution 4:

For each rational $q$ there is are unique integers $F(q)$ and $G(q)$ where

1. $G(q)>0$
2. $q=\dfrac{F(q)}{G(q)}$ and
3. gcd$(F(q),G(q))=1$.

For convenience, let $H(q)=G(q)+|F(q)|$.

Let $<$ denote the usual order on $\Bbb Q$, and for rationals $q_1$ and $q_2$, define $$q_1<^*q_2 \iff \text{ either } H(q_1)<H(q_2) \text{ or } [H(q_1)=H(q_2) \text{ and } q_1<q_2]$$

Let $J(q)$ be the NUMBER of rationals $p$, that satisfy $p<^*q$.... $J$ is a bijection from $\Bbb Q$ to $\Bbb N$.

Solution 5:

The question is meaningless, since Cantor's argument does not involve any bijection assumptions.

Cantor argues that the diagonal, of any list of any enumerable subset of the reals $\mathbb R$ in the interval 0 to 1, cannot possibly be a member of said subset, meaning that any such subset cannot possibly contain all of $\mathbb R$; by contraposition [1], if it could, it cannot be enumerable, and hence $\mathbb R$ cannot. Q.E.D.

[1] contraposition is a consequence of 'proof of negation': $(A\to\bot)\equiv\neg A$