The proof that the set of real numbers is uncountably infinite is often concluded with a contradiction. In the following argument I use a similar proof by contradiction to show that the set of rational numbers can be shown to be uncontably infinite:

Let us assume that the set of rational numbers is countable. This implies that we can write all the rational numbers between 0 and 1 in a list. Let us say, it looks something like this:

$ 0.\color{red}0000000001000000...\\ 0.0\color{red}10000001110000...\\ 0.10\color{red}000001000000... \\ ....$

ans so on. Now, create a new number that picks $n^{th}$ digit from $n^{th}$ number and changes it to $0$ if it is $1$ and vice versa.

$0.101.... $

This number, say $x$, is between 0 and 1, and so it must appear in the list. Suppose it appears at the $n^{th}$ position in the list. However, based on how we constructed $x$, we know that the $n^{th}$ digit of $x$ is different from the $n^{th}$ digit of the $n^{th}$ number in the list. So, $x$ should be different from the $n^{th}$ number in the list at the $n^{th}$ digit and hence, this is a contradiction. We can conclude that such a list of the rational numbers does not exist and hence, the set of rational numbers is uncontably infinite.

I know that there is another mapping between the set of rational numbers and natural numbers that can show that there is one-to-one mapping between the two sets (http://www.homeschoolmath.net/teaching/rational-numbers-countable.php). However, the above proof in that sense is not really conclusive and that the set of real numbers might also be countably infinite and it is just that we are not yet aware of the mapping.

Please provide your comments if the above proof is somehow flawed for rational numbers or if I'm missing something.

  • 13
    $\begingroup$ You don't know that the number you constructed is rational. $\endgroup$ – Daniel Fischer May 10 '15 at 18:50
  • 1
    $\begingroup$ Thanks Daniel! Is it possible to address this by explicitly stating that each number on the list has non-zero digits till the $n^{th}$ place beyond which it can simply be appended with zeros i.e. each number on the list has a finite length. Not sure if this would lead to another flaw in the proof. $\endgroup$ – Priyanshu May 10 '15 at 19:06
  • $\begingroup$ It's not possible to fix the proof because what you are trying to prove is not true. I promise nobody has been lying to you, the rationals are countably infinite and hence can be written in a list, but the set of reals is uncountable and cannot. $\endgroup$ – Matt Samuel May 10 '15 at 19:13
  • 1
    $\begingroup$ each number on the list has a finite length - Not all rationals have finite length. $\endgroup$ – Lucian May 10 '15 at 19:49
  • $\begingroup$ Thanks Matt. Well I would have appreciated a more mathematical explanation of what exactly is wrong with what I mentioned. I'm totally convinced that the set of rational numbers is countably infinte and that the set of real numbers is not. $\endgroup$ – Priyanshu May 10 '15 at 19:50

The standard proof that the real numbers are uncountable does not need to be phrased as a proof by contradiction. To say that $\mathbb{R}$ is uncountable is to say that if $f : \mathbb{N} \to \mathbb{R}$ is a map, then it is not a bijection. The standard proof in fact proves that $f$ is not a surjection by explicitly exhibiting a real number which is not in the image of $f$.

As Daniel says in the comments, the problem with your proof is that there's no reason the number you want to write down has to be rational, and that's it. As I've said in several other answers recently, the problem with proofs by contradiction is that once you've made a mistake you think you're done. Generally it's better to prove things directly.

  • $\begingroup$ Thanks Qiaochu. Yes, I agree. $\endgroup$ – Priyanshu May 12 '15 at 6:09

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.