# 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?

Firstly I'm not saying that I don't believe in Cantor's diagonalization arguments, I know that there is a deficiency in my knowledge so I'm asking this question to patch those gaps in my understanding.

From my understanding of Cantor's Diagonalization argument, if you apply diagonalization to a mapping from one set of numbers to another, you will always obtain a number that is not in the mapping. So this works to prove that the reals aren't countable because if you have a mapping from the naturals to the reals then you can use diagonalization to obtain a number that's not in the mapping, and this number is a real obviously, so the mapping isn't a surjection. We're not allowed to assume that the mapping from the naturals to the reals is a bijection to begin with.

But when people explain why the diagonalization process doesn't produce a rational from a mapping from naturals to rationals we are allowed to assume that the mapping is a bijection to begin with? In the questions asked here:

Why does Cantor's diagonal argument not work for rational numbers?

To be precise, the procedure does not let you guarantee that the number you obtain has a periodic decimal expansion (that is, that it is a rational number), and so you are unable to show that the "diagonal number" is a rational that was not in the original list. In fact, if your original list is given explicitly by some bijection, then one is able to show just as explicitly that the number you obtain is not a rational.

Why are we allowed to assume that the original list is a bijection? Is there some way to prove that the mapping from the naturals to the rationals is a bijection that is not susceptible to diagonalization? If we can assume that the mapping from naturals to rationals is an undiagonalizable bijection why can't we do the same for the mapping from naturals to reals?

-
Your sentence starting, “From my understanding of…” is wrong. Whether the process of enumeration (not diagonalization) fails or succeeds depends on the two sets involved. – Lubin Jul 25 '14 at 13:31
To be clear, I was talking about infinite sets. Can it fail for infinite sets? – guest Jul 25 '14 at 13:33
You are really asking two questions, perhaps without realizing it. First, how do we know a bijection between naturals and rationals exists? (This is possible to show pretty constructively, by enumerating the ordered pairs of natural numbers and considering the (positive) rationals as ratios of such pairs.) The second question is why Cantor's diagonalization argument doesn't apply, and you've already identified the explanation: the diagonal construction will not produce a periodic decimal expansion (i.e. rational number), so there's no contradiction. It gives a nonrational, not on the list. – hardmath Jul 25 '14 at 13:33
See this post for a similar discussion. – Mauro ALLEGRANZA Jul 25 '14 at 13:39
Here's another relevant discussion: Should a Cantor diagonal argument on a list of all rationals always produce an irrational number?. I think my answer there may be helpful. – MJD Jul 25 '14 at 15:11

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.

-
Okay, so you can't construct a bijection from naturals to reals due to the diagonalization argument. But the proof of a bijection from naturals to rationals is independent of diagonalization, right? – guest Jul 25 '14 at 14:16
@guest: Correct. – Asaf Karagila Jul 25 '14 at 14:24
Well you may be able to proof there is no bijection, and then you could apply xkcd.com/816 . – PyRulez Jul 26 '14 at 0:26

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

-
Or even $2^p3^q$ for $p\ge0$ and $2^{-p}3^q5$ for $p<0$, if you're an integer conservationist. – Charles Jul 25 '14 at 13:58
It's not clear to me why you're allowed to use the latter fact when proving this theorem. – djechlin Jul 25 '14 at 15:30
@djechlin This was just dealing with a bijection $\mathbb Q \to \mathbb N$. The other answers address the confusion with the use of proof by contradiction to show there is no bijection $\mathbb R \to \mathbb N$. – zibadawa timmy Jul 25 '14 at 15:49
@djechlin There's no need to assume that every infinite set of integers has the same cardinality. $\mathbb{N}\subset\mathbb{Q}$, so $|\mathbb{N}|\leq|\mathbb{Q}|$; the injection in the answer shows that $|\mathbb{Q}|\leq|\mathbb{N}|$ and we're done. – David Richerby Jul 25 '14 at 23:59

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

-
sorry if my missing brackets threw anyone off. – user254665 Aug 11 '15 at 20:08
@user254665: How would that be a comment to my post? – String Aug 11 '15 at 21:22

Let me answer the last part of your question. Cantor's bijection between naturals and rationals has been accepted to prove that a list of all rational numbers is possible such that the diagonal number must be irrational. But recently there has been shown another way to disprove this. It is mentioned in the answer to Do we need the diagonal argument to show that not all real numbers between 0 and 1 are in the Cantor-list? but not fully worked out.

Assume a list of all rational numbers of the real interval (0, 1). Replace every digit beyond the diagonal digit $d_{nn}$ by zero and every other digit by 1. This procedure does not change the number of entries. It produces a triangular list

$0.100000...$
$0.110000...$
$0.111000...$
...

Without having changed the number of entries the list now contains only a proper subset of the rational numbers of the real interval (0, 1). It cannot have contained all rational numbers before.

If you want to insert any missing fraction, you will have to remove one of the residing fractions. Since no pair of identical entries is existing, the list remains incomplete.

If you simply wish to append further fractions or insert them between the rows, you may do so. But please don't forget to apply the above procedure to the modified list again. Also in the original diagonal argument you are not allowed to append the constructed diagonal number to the list without diagonalizing it again.

-

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

-