Sequences and convergence
We saw earlier that the rational numbers Q are much more versatile than the natural numbers N for doing a wide variety of mathematical operations. However, there is still one thing the rational numbers cannot do adequately: it is possible to construct sequences of rational numbers that do not converge to a rational number. In formal terms, the rational numbers are not complete.
Why does this seemingly obscure mathematical quirk matter? Because this is the foundation of calculus. The ideas of sequences and limits are fundamental to calculus, and if such limits don't exist meaningfully, then neither does calculus. But there is another, intuitive reason for why completeness matters.
Take the sequence {1, 1/2, 1/3, 1/4, …}. It should be intuitively obvious that this set of numbers is getting smaller and smaller, and that although it does not contain the value 0, it is inexorably heading towards it. But if you take a sequence like {1, 1.4, 1.41, 1.414, 1.4142, …}, then we "know" intuitively that this sequence converges to the number √2, which we have proven to be irrational. This suggests that there are lots of "holes" in the set of rational numbers, making them incomplete and even discontinuous, in an intuitive sense. (In terms of topology, this intuition is expressed by the idea that the rational numbers are totally disconnected, which roughly means that between every two rational numbers there is at least one irrational number, so that if we tried to walk along the number of rational numbers, we would be forced to jump constantly from one rational number to another.)
When we faced similar problems with N and with Z, we extended them by adding all sorts of missing numbers. We can do the same thing now with Q, extending it to the set of real numbers R, although the mathematical details are not very pretty. The usual non-rigorous method is say that rational numbers have decimal expansions that are either terminating (like 0.3158) or at least repeating (like 0.333... for 1/3), whereas irrational numbers have non-terminating, non-repeating decimal expansions (like 1.4142… for √2). (For those who don't have queasy stomachs, there are at least three different ways of constructing R that are often taught: the easy way by constructing equivalence classes of Cauchy sequences of rational numbers, the standard way by constructing Dedekind cuts, and the coolest way—at least in my book—by continued fractions.)
These details don't really matter; the twofold point is that we can construct the set of real numbers R so that it is complete (i.e., doesn't have any "holes" the way Q does) and that we have a nice decimal representation for every real number. (In formal terms, completeness can be described in a few different ways, one way being that every sequence of real numbers whose terms get closer and closer to each other—every Cauchy sequence, to be precise—will eventually converge to a real number.) To return now to our initial question: how large is R?
Cantor's Diagonalization Proof
By now, all our intuitions about comparing the sizes of sets have been utterly trashed. We no longer really have a good intuition for how large R must be, and it would be entirely forgivable to suppose that R is also countably infinite, just like N. We would be utterly wrong.
The mathematician Georg Cantor offered a beautiful proof of the uncountability of R using the idea of diagonalization. The full-blown version of the proof is a bit tricky, as always, but here I will sketch out a proof of the fact that there are in fact far more irrational numbers between just 0 and 1 than there are natural numbers in their entirety. (Clearly, if this is true, then all of R must also be strictly larger than all of N.)
As with our proof of the irrationality of √2, we will achieve this by contradiction. So let us suppose that the irrational numbers between 0 and 1 are countable; that is, we can enumerate them in a list indexed by the natural numbers N. Now, since we know that irrational numbers have non-terminating, non-repeating decimal expansions, we simply go ahead and write down all the irrational numbers in a list, which would look something like this:
1—0.548574930…
2—0.353495364…
3—0.579473594…
4—0.123534967…
5—0.432874239…
6—0.549412390…
and so on. This is possible because we have supposed that the irrational numbers are countable.
Here is where the diagonalization part comes in. We now essentially have a table of numbers that comprises of all the digits of all the irrational numbers between 0 and 1. So now, let's take a separate, infinitely long piece of paper, and let's walk down the diagonal of the table, writing down the first digit of the first number, the second digit of the second number, …, the ith digit of the ith number, … until infinity. (We're assuming we have an infinite amount of time, so this doesn't matter! Gotta love math.) So based on the table we have up here, we will have the number (let's call it x) 0.559572…
We then take a second infinitely long piece of paper and copy down the digits of x, with one key difference: we add 1 to every digit after the decimal point. (As a convention, we can suppose that if x contains a 9 somewhere, then we write down 0 instead, but this is just really a minor thing.) Let's call this new number y; in our case this is going to be the number 0.660681…
So what's so great about what we've done so far? Here is the kicker, the awesome punchline, the crazy part: y is an irrational number that is not part of our list at all!
Uncountable Sets
But wait! There is more. Let us now define one more mathematical term: the open interval (a, b), which is sometimes written as ]a, b[ to avoid ambiguity, is the set of all real numbers x that lie between a and b but are not equal to them. In formal mathematical notation, (a, b) = {x ∈ R | a < x < b}. So, using this notation, we can say that we just proved that the size of the set of irrational numbers in the open interval (0, 1) is strictly larger than the size of the set of natural numbers. (Just so we are clear, the open interval (0, 1) contains all the real numbers between 0 and 1, which means it contains all the irrational numbers and all the rational numbers between 0 and 1.)
Just as we looked first at the natural numbers N and then compared them to the even numbers 2N, we can now look at a subinterval of the open interval (0, 1) and see how it stacks up in size with the bigger interval. Let's take the open interval (0, 1/2). This is clearly half as "long" as the open interval (0, 1)—but does it contain "half" as many elements?
Now that we are talking about sets strictly larger than N, we can no longer establish size by naïvely counting all the elements. However, we can certainly use the formalized intuition of counting that we have developed, which is to say, the idea of the bijection. In other words, we can still compare the size of two sets by checking to see if it possible to construct a way to uniquely map every element of one set to exactly one unique element of the other, and vice versa.
There is a very simple bijection between (0, 1/2) and (0, 1):
We saw earlier that the rational numbers Q are much more versatile than the natural numbers N for doing a wide variety of mathematical operations. However, there is still one thing the rational numbers cannot do adequately: it is possible to construct sequences of rational numbers that do not converge to a rational number. In formal terms, the rational numbers are not complete.
Why does this seemingly obscure mathematical quirk matter? Because this is the foundation of calculus. The ideas of sequences and limits are fundamental to calculus, and if such limits don't exist meaningfully, then neither does calculus. But there is another, intuitive reason for why completeness matters.
Take the sequence {1, 1/2, 1/3, 1/4, …}. It should be intuitively obvious that this set of numbers is getting smaller and smaller, and that although it does not contain the value 0, it is inexorably heading towards it. But if you take a sequence like {1, 1.4, 1.41, 1.414, 1.4142, …}, then we "know" intuitively that this sequence converges to the number √2, which we have proven to be irrational. This suggests that there are lots of "holes" in the set of rational numbers, making them incomplete and even discontinuous, in an intuitive sense. (In terms of topology, this intuition is expressed by the idea that the rational numbers are totally disconnected, which roughly means that between every two rational numbers there is at least one irrational number, so that if we tried to walk along the number of rational numbers, we would be forced to jump constantly from one rational number to another.)
When we faced similar problems with N and with Z, we extended them by adding all sorts of missing numbers. We can do the same thing now with Q, extending it to the set of real numbers R, although the mathematical details are not very pretty. The usual non-rigorous method is say that rational numbers have decimal expansions that are either terminating (like 0.3158) or at least repeating (like 0.333... for 1/3), whereas irrational numbers have non-terminating, non-repeating decimal expansions (like 1.4142… for √2). (For those who don't have queasy stomachs, there are at least three different ways of constructing R that are often taught: the easy way by constructing equivalence classes of Cauchy sequences of rational numbers, the standard way by constructing Dedekind cuts, and the coolest way—at least in my book—by continued fractions.)
These details don't really matter; the twofold point is that we can construct the set of real numbers R so that it is complete (i.e., doesn't have any "holes" the way Q does) and that we have a nice decimal representation for every real number. (In formal terms, completeness can be described in a few different ways, one way being that every sequence of real numbers whose terms get closer and closer to each other—every Cauchy sequence, to be precise—will eventually converge to a real number.) To return now to our initial question: how large is R?
Cantor's Diagonalization Proof
By now, all our intuitions about comparing the sizes of sets have been utterly trashed. We no longer really have a good intuition for how large R must be, and it would be entirely forgivable to suppose that R is also countably infinite, just like N. We would be utterly wrong.
The mathematician Georg Cantor offered a beautiful proof of the uncountability of R using the idea of diagonalization. The full-blown version of the proof is a bit tricky, as always, but here I will sketch out a proof of the fact that there are in fact far more irrational numbers between just 0 and 1 than there are natural numbers in their entirety. (Clearly, if this is true, then all of R must also be strictly larger than all of N.)
As with our proof of the irrationality of √2, we will achieve this by contradiction. So let us suppose that the irrational numbers between 0 and 1 are countable; that is, we can enumerate them in a list indexed by the natural numbers N. Now, since we know that irrational numbers have non-terminating, non-repeating decimal expansions, we simply go ahead and write down all the irrational numbers in a list, which would look something like this:
1—0.548574930…
2—0.353495364…
3—0.579473594…
4—0.123534967…
5—0.432874239…
6—0.549412390…
and so on. This is possible because we have supposed that the irrational numbers are countable.
Here is where the diagonalization part comes in. We now essentially have a table of numbers that comprises of all the digits of all the irrational numbers between 0 and 1. So now, let's take a separate, infinitely long piece of paper, and let's walk down the diagonal of the table, writing down the first digit of the first number, the second digit of the second number, …, the ith digit of the ith number, … until infinity. (We're assuming we have an infinite amount of time, so this doesn't matter! Gotta love math.) So based on the table we have up here, we will have the number (let's call it x) 0.559572…
We then take a second infinitely long piece of paper and copy down the digits of x, with one key difference: we add 1 to every digit after the decimal point. (As a convention, we can suppose that if x contains a 9 somewhere, then we write down 0 instead, but this is just really a minor thing.) Let's call this new number y; in our case this is going to be the number 0.660681…
So what's so great about what we've done so far? Here is the kicker, the awesome punchline, the crazy part: y is an irrational number that is not part of our list at all!
- y is irrational because it is non-terminating and non-repeating. This may not be obvious right at the start, because it is of course possible to imagine that we somehow randomly happen to pick an infinite number of numbers which set up an infinite diagonal of 9s, which would then make the decimal expansion of y contain an infinite number of 0s and thus terminate. However, if this happens, then we can quite easily reorder our original list so that our diagonal is no longer comprised of 9s. (Remember that when we count, it does not matter which particular element gets indexed to which natural number; the only thing that matters is that it can be done. So such a reordering is totally legitimate.)
- y is not on our list because, well, it differs from every number on our list at one position, at the very least! This is the neat part: we have consciously constructed y so that the ith digit of y is different from the ith digit of the ith number on our list.
Uncountable Sets
But wait! There is more. Let us now define one more mathematical term: the open interval (a, b), which is sometimes written as ]a, b[ to avoid ambiguity, is the set of all real numbers x that lie between a and b but are not equal to them. In formal mathematical notation, (a, b) = {x ∈ R | a < x < b}. So, using this notation, we can say that we just proved that the size of the set of irrational numbers in the open interval (0, 1) is strictly larger than the size of the set of natural numbers. (Just so we are clear, the open interval (0, 1) contains all the real numbers between 0 and 1, which means it contains all the irrational numbers and all the rational numbers between 0 and 1.)
Just as we looked first at the natural numbers N and then compared them to the even numbers 2N, we can now look at a subinterval of the open interval (0, 1) and see how it stacks up in size with the bigger interval. Let's take the open interval (0, 1/2). This is clearly half as "long" as the open interval (0, 1)—but does it contain "half" as many elements?
Now that we are talking about sets strictly larger than N, we can no longer establish size by naïvely counting all the elements. However, we can certainly use the formalized intuition of counting that we have developed, which is to say, the idea of the bijection. In other words, we can still compare the size of two sets by checking to see if it possible to construct a way to uniquely map every element of one set to exactly one unique element of the other, and vice versa.
There is a very simple bijection between (0, 1/2) and (0, 1):
- We can map any x in the interval (0, 1/2) to the number 2x, which is clearly in the interval (0, 1),
- We can map any y in the interval (0, 1) to the number y / 2, which is clearly in the interval (0, 1/2).
- Given any x in the interval (0, 1), we can map it to the number a + (b - a)x, which must lie precisely inside the interval (a, b).
- Given any y in the interval (a, b), we can map it to the number (y - a) / (b - a), which must lie inside the interval (0, 1).
Well, for something more (which I guess you're planning to cover in the next post, or maybe you weren't), Cantor's diagonalisation proof generalises: just as R, which is 2^N (the power set of N, alternatively denoted P(N)), is larger than N, so is 2^R larger than R, 2^(2^R) larger than 2^R, and in general, for any set X, 2^X (that is, P(X)) is larger than X, so you have an infinite tower of infinities. :-)
ReplyDeleteYou stole my thunder :D My next post is in fact going to be about power sets!
ReplyDeleteI also eventually want to talk about measures, the Cantor set, and fat Cantor sets, since I've already touched upon the ideas of dense sets and totally disconnected sets.
Oh sorry; I saw "If this does not blow your mind, nothing can" and jumped the gun. :-) Nice series of posts, please do continue.
ReplyDeleteTo make up for that, here's a nice result on something you've already covered. The rationals are countable, and there's a procedure for enumerating them. But most accounts do not give an explicit such bijection, being content instead to only say "if you follow this procedure, skipping over fractions not in reduced form, etc., you will find each rational number". In a beautiful, extremely readable paper hardly four pages long, Calkin and Wilf gave an explicit enumeration in 1999 (showing new fundamental mathematics is still possible even now!), breathing new life into an old topic, and there have since been other constructions, efficient algorithms, and so on.