Theorem 21: the real numbers are uncountable

In my post about the countability of the rational numbers, I said that I’d come back to the topic and prove that the real numbers are uncountable.  That’s the plan for today.  If you’re not familiar with the definition of countability, please read that post first: this really is part two of that post.  I may as well state the theorem immediately, and then we’ll think about what it actually means.

Theorem The real numbers are uncountable.

What does this mean?  It means there’s no way of listing the real numbers (we saw last time that saying that a set is countable is the same as saying that the elements can be written in a list).  So our aim is to prove that it’s impossible to do something (write the real numbers in a list).  How could we possibly do that?

We’ve had a previous example of a proof that something is impossible, when we saw that the square root of 2 is irrational.  That is, we showed that it’s impossible to write \sqrt{2} as the ratio of two whole numbers.  There, our strategy was to use proof by contradiction.  We supposed that it is possible to write \sqrt{2} as the ratio of two whole numbers, and we went on to derive a contradiction from that: we got to something that was simply absurd.  That meant that the square root of 2 couldn’t possibly be rational, so it must be irrational.

We’re going to use a similar sort of strategy here.  We’re going to suppose that it is possible to list the real numbers.  Then we’ll somehow derive a contradiction from that, which will mean our original supposition must have been wrong.  That is, we’ll have shown that it’s impossible to list the real numbers.  Let’s go!

So, we’re supposing that we can list the real numbers.  In that case, we can certainly list the real numbers between 0 and 1.  Let’s imagine that we’ve done this, and we’ve written them all out in order, using their decimal expansions.  (Slightly annoyingly, some numbers have two expansions, since 0.99999999999999… = 1, but let’s say we always write the finite version rather than the one ending in infinitely many 9s.)  So they look something like

0.a_{1,1}a_{1,2}a_{1,3}a_{1,4}a_{1,5}...

0.a_{2,1}a_{2,2}a_{2,3}a_{2,4}a_{2,5}...

0.a_{3,1}a_{3,2}a_{3,3}a_{3,4}a_{3,5}...

0.a_{4,1}a_{4,2}a_{4,3}a_{4,4}a_{4,5}...

0.a_{5,1}a_{5,2}a_{5,3}a_{5,4}a_{5,5}...

Our plan is to derive a contradiction.  How are we going to do that?  We’re going to build another real number between 0 and 1, one that isn’t on our list.  Since our list was supposed to contain all such real numbers, that will be a contradiction, and we’ll be done.  So let’s think about how to build another real number between 0 and 1 in such a way that we can be sure it isn’t on our list.  Let’s say this new number will be 0.b_1 b_2 b_3 b_4 b_5 ..., where we’re about to define the digits b_i.

We want to make sure that our new number isn’t the same as the first number on our list.  So let’s do that by making sure they have different numbers in the first decimal place.  Say if a_{1,1} = 3 then b_1 = 7 and otherwise b_1 = 3.  (I really mean: define b_1 to be any digit apart from a_{1,1}, but I want to make sure that we don’t get a number that ends in infinitely many 9s, because of this irritating fact that 0.99999999999999… = 1, so I want to make sure we never choose b_1 to be 9.)

Now we want to make sure that our new number isn’t the same as the second number in our list.  We can do this by making sure that the second digit of our new number isn’t the same as the second digit of the second number.  So let’s put b_2 = 7 if a_{2,2} = 3 and b_2 = 3 otherwise.

And so on.  At each stage, we make sure that our new number isn’t the same as the nth number on the list, by making sure that b_n isn’t the same as a_{n,n}.

And that defines our new real number, one that is definitely not on our list (because we built it that way)!

Where next?

The argument we have just used is called Cantor‘s diagonal argument, because we worked our way down the diagonal.  It can be used in other proofs of uncountability too; the Wikipedia page talks more about this.

Having seen that the reals are uncountable, I think that two natural questions come to mind.  One is to ask how many reals there are, and the other is to wonder whether there are still larger sets (in the way that the set of reals is larger than the set of naturals).  Thinking about the second of those first, there certainly are still larger sets.  In fact, it turns out that for any set S, the set of all subsets of S is bigger than S.  (Wikipedia calls this Cantor’s theorem.  It can be proved using a version of the diagonal argument that we’ve just seen.)  So the set of all subsets of the reals is larger than the set of reals, and the set of all subsets of the set of all subsets of the reals is larger than the set of all subsets of the reals, and so on.  This gives an infinite chain of larger and larger infinities!   There’s a theory of cardinal numbers to help describe this sort of thing.

Returning to the first question, how large are the reals?  Are there any infinite sets that are larger than the naturals but smaller than the reals?  The continuum hypothesis says there aren’t, but, remarkably, it turns out that this statement can neither be proved nor disproved using the usual axioms of mathematics.  Fascinating stuff, but this post is getting too long so I think I’m going to stop here!

Advertisements

22 Responses to “Theorem 21: the real numbers are uncountable”

  1. Theorem 36: the Cantor set is an uncountable set with zero measure « Theorem of the week Says:

    […] least as many points in the Cantor set as there are in this other uncountable set.  We know that there are uncountably many real numbers so how about trying to construct a surjection from the Cantor set to the real […]

  2. David Says:

    Very interesting

  3. Comet Says:

    Hmm let’s see, I’ll list the numbers (the … is a bunch of zeros, and I am using binary digits):
    … 0 0 0
    … 0 1 0
    … 0 1 1
    … 1 0 0
    … 1 0 1
    … 1 1 0
    … 1 1 1
    .
    .
    .
    (the vertical ellipses mean I can keep on listing numbers)

    Now I’ll follow the construction, creating a number whose nth digit (bit) is different than the corresponding bit in the nth number. (the … is a bunch of x’s, denoting digits I have yet to construct)

    … x x 1
    … x 0 1
    … 1 0 1
    etc.

    Even though every nth position of my constructed number has the nth digit different than the nth digit of the nth number, it isn’t obvious that I am constructing a number that is not on the list at all; perhaps it just means that the number I am constructing is greater than my nth original number, but since I have a countable infinity of original numbers, there are many numbers in my original list greater than my nth original number, no matter how large an n digit number you may choose to construct.

  4. theoremoftheweek Says:

    Remember that we are talking about numbers with infinitely many digits after the point. This is really important, and is genuinely different from listing natural numbers which have only finitely many digits (before the point).

    Whatever number you create, it can’t be on your list. Why? Suppose it’s the same as the 123456th number on your list. But it can’t be, because its 123456th digit is different from the 123456th digit of the 123456th number on your list. And so on.

    Does that help at all?

  5. ocularisabyssus Says:

    Thank you so much for this explanation! I’ve been working through a real analysis book and came upon this theorem and proof but wasn’t grasping the argument in the text. Your explanation made it crystal clear! Cardinality of sets is such an interesting topic.

  6. theoremoftheweek Says:

    Glad it helped!

  7. Sutton Trust summer school 2012 « Theorem of the week Says:

    […] irrational numbers than rational; that’s because the rationals are `countable’, whereas the irrationals are `uncountable’.  A couple of the problems on the examples sheet are related to the Chinese Remainder […]

  8. shishay Says:

    nice

  9. arpit mehrotra Says:

    understandable sOlutiOn

  10. Sciency Shit (@sciency_shit) Says:

    Beautiful post!
    This proof has been one of my favourite proofs of all time. I’ll be sure to follow your blog after this. 🙂

  11. Coconut Says:

    Can the diagonalisation proof be applied to the following ordering? I have seen people proposing this elsewhere referred to Cantor, as if that obviously discredits the argument, but I haven’t actually seen anyone come up with a number that is produced by the diagonalisation that would be omitted from this set. (And I think diagonalisation requires the set to be ‘square’, i.e. the number of digits must be infinite in each element, in which case it cannot even be attempted here?)

    We define the order as: 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9, 0.1, 0.11, 0.12 etc. The rule is ‘remove all trailing zeros, and the preceding decimal point, and map what remains to the equivalent integer’.

    I don’t think diagonalisation can be applied to that. There may be other issues with it though. I have seen it stated elsewhere that the above ordering misses infinite expansions like 1/3 = 0.3333…, but I have never seen a explanation for why that would be missed. This ordering would reach all numbers in the interval ‘eventually’ I think. The key point seems to be removing the arbitrary number of zeroes after the significant digits. (This is key difference between this and the Cantor binary expansion I think, since that has an infinite number of digits in each element.)

    Apologies for the long post. Naivety and thinking out loud on the internet are unhappy bedfellows…

  12. theoremoftheweek Says:

    Hi Coconut. Let me see whether I can help.

    Firstly, we can perfectly legitimately apply a diagonal argument even when the numbers seem to have finite decimal expansions (0.1, 0.25, 0.124245, etc.), because we just stick lots of 0s afterwards. If we think about it that way, then every number has an infinite decimal expansion.

    You’re right that your list is never going to include 1/3. As I understand it, you take each positive integer and turn it into a decimal. That’s fine, but there are no positive integers with infinitely many digits. We’re never going to reach 333…. (with infinitely many 3s) because it’s not an integer.

    I hope that might help. Feel free to post back if you have further questions, or if I’ve missed any from your first post.

  13. Ray Wong Says:

    I have always had issues with Cantor’s diagonal argument. Perhaps the way he constructed such a number is flawed. Let me list the set of natural numbers right justified by adding leading zeros to the front so that the digits are lined up by corresponding digits. Then construct a number the same way using Cantor’s diagonal method and we get a contradiction. But the set of the natural numbers is countable; wouldn’t this mean there is something wrong and such a number simply do not exist? To me, infinite is infinite and there will be enough numbers in the natural number to count all we wanted, power sets or whatever.

  14. theoremoftheweek Says:

    The crucial difference is that we can have a number with an infinite number of non-zero digits *after* the decimal point, but not before.

    Does that help?

  15. Ray Wong Says:

    At first, not so convinced, as the naturals, being infinite can be arbitrarily large as we want; though, we cannot get to 333…. just as we cannot have .3333 … = 1/3 in the decimal representation. In my earlier post, I shown a bijection N:-> N and constructed a number n that was not in N. Note that since I was using the digits before the decimal point, my list would be from bottom up and the diagonal would begin at the bottom right corner. It is that in Cantor’s diagonal method, numbers like 1/3, π, √2 … and the constructed number n can assume limiting values, for being real, of infinite digits. In my example, the number of digits can be arbitrarily large, but cannot be infinite as I can always add more. Thanks for your help.

  16. theoremoftheweek Says:

    I think you’re on the right track there. The point is precisely that we *can* have 0.3333…. but we can’t have 3333…

  17. shepherdmoon2013 Says:

    “I think you’re on the right track there. The point is precisely that we *can* have 0.3333…. but we can’t have 3333…”

    Why can’t we have 333… – isn’t that just an arbitrarily long natural number composed only of the digit 3?

  18. theoremoftheweek Says:

    Arbitrarily long with finitely many 3s would be fine, but it doesn’t make sense with infinitely many 3s before the decimal point, whereas we can define 0.333… (with infinitely many 3s after the decimal point) in a meaningful way.

  19. elcheuk Says:

    Hi, thanks for this. I’m having trouble on one point. I don’t see why this argument that you’ve laid out doesn’t apply to rationals just as much as reals?

    If you’re writing a decimal expansion, then you can write the number as a fraction of two integers.

    Of course the rationals are in fact countable, so there must be a flaw in my argument…

  20. theoremoftheweek Says:

    It’s great that you’re testing the argument by seeing what goes wrong when you try to apply it to the rationals, this is a very sensible thing to do.

    “If you’re writing a decimal expansion, then you can write the number as a fraction of two integers.”

    Unfortunately this is not quite right. A *finite* decimal expansion gives a rational number (a number that’s the ratio of two integers). Some, but not all, infinite decimal expansions also give rational numbers. In fact there’s a rather pretty way to tell whether a decimal expansion is rational or not (see https://en.wikipedia.org/wiki/Repeating_decimal ). But crucially some of them aren’t, e.g. \sqrt{2} is irrational (see https://theoremoftheweek.wordpress.com/2009/08/24/theorem-5-root-2-is-irrational/ ) and it has a decimal expansion.

    Does that help?

  21. Stop being so irrational - James Howard Says:

    […] We also understand the irrational numbers are uncountable. Here’s a proof from Theorem of the Week. […]

  22. Does infinity and zero really exist? - MathHub Says:

    […] R$ ! Somebody show me a set which is not countable in real world ? I mean in nature. (I know Cantor’s theorem, but it’s based on “infinity” concept! Which I can’t understand […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: