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?

The answers says:

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?

  • 1
    $\begingroup$ 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. $\endgroup$ – Lubin Jul 25 '14 at 13:31
  • $\begingroup$ To be clear, I was talking about infinite sets. Can it fail for infinite sets? $\endgroup$ – guest Jul 25 '14 at 13:33
  • 4
    $\begingroup$ 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. $\endgroup$ – hardmath Jul 25 '14 at 13:33
  • 1
    $\begingroup$ See this post for a similar discussion. $\endgroup$ – Mauro ALLEGRANZA Jul 25 '14 at 13:39
  • 1
    $\begingroup$ 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. $\endgroup$ – 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.

  • 3
    $\begingroup$ 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? $\endgroup$ – guest Jul 25 '14 at 14:16
  • 2
    $\begingroup$ @guest: Correct. $\endgroup$ – Asaf Karagila Jul 25 '14 at 14:24
  • $\begingroup$ Well you may be able to proof there is no bijection, and then you could apply xkcd.com/816 . $\endgroup$ – 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.

  • 2
    $\begingroup$ Or even $2^p3^q$ for $p\ge0$ and $2^{-p}3^q5$ for $p<0$, if you're an integer conservationist. $\endgroup$ – Charles Jul 25 '14 at 13:58
  • $\begingroup$ It's not clear to me why you're allowed to use the latter fact when proving this theorem. $\endgroup$ – djechlin Jul 25 '14 at 15:30
  • $\begingroup$ @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$. $\endgroup$ – zibadawa timmy Jul 25 '14 at 15:49
  • 1
    $\begingroup$ @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. $\endgroup$ – 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 ...


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

  • $\begingroup$ 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? $\endgroup$ – hmakholm left over Monica Nov 9 '17 at 9:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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