# 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. Jul 25, 2014 at 13:31
• To be clear, I was talking about infinite sets. Can it fail for infinite sets? Jul 25, 2014 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. Jul 25, 2014 at 13:33
• See this post for a similar discussion. Jul 25, 2014 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, 2014 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? Jul 25, 2014 at 14:16
• @guest: Correct. Jul 25, 2014 at 14:24
• Well you may be able to proof there is no bijection, and then you could apply xkcd.com/816 . Jul 26, 2014 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. Jul 25, 2014 at 13:58
• It's not clear to me why you're allowed to use the latter fact when proving this theorem. Jul 25, 2014 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$. Jul 25, 2014 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. Jul 25, 2014 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 ...

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

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 , if it could, it cannot be enumerable, and hence $\mathbb R$ cannot. Q.E.D.

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

• This seems to be more of a quibble about what should be properly called "Cantor's argument". Certainly the diagonal argument is often presented as one big proof by contradiction, though it is also possible to separate the meat of it out in a direct proof that every function $\mathbb N\to\mathbb R$ is non-surjective, as you do, and it is commonly argued that the latter presentation has didactic advantages. Do you happen to know how Cantor himself phrased it? Nov 9, 2017 at 9:41