We could continue forever discussing questions whose answers are frequently questioned; but let’s finish by looking at infinity itself. The concept is impossible to fully grasp, because we are finite, and all of our experience is finite. Mathematicians have worked out ways to deal with infinity, though, and the results are often counter-intuitive. That means people often have trouble believing what we say about it, and sometimes are convinced that we are simply wrong.
Can we count the infinite?
Let’s begin with the paragraph in our FAQ on infinity that makes the claim we’ll be looking at:
FAQ: Large Numbers and Infinity Now for the fun part! Even though infinity is not a number, it is possible for one infinite set to contain more things than another infinite set. Mathematicians divide infinite sets into two categories, countable and uncountable sets. In a countably infinite set you can 'number' the things you are counting. You can think of the set of natural numbers (numbers like 1,2,3,4,5,...) as countably infinite. The other type of infinity is uncountable, which means there are so many you can't 'number' them. An example of something that is uncountably infinite would be all the real numbers (including numbers like 2.34... and the square root of 2, as well as all the integers and rational numbers). In fact, there are more real numbers between 0 and 1 than there are natural numbers (1,2,3,4,...) in the whole number line!
The “numbers” that are used to identify the “size” (cardinality) of infinite sets are called transfinite numbers. The claim here is that the cardinality of the real numbers (or of any interval) is greater than the cardinality of the integers — it is uncountable.
For some initial ideas on how to “count” infinite sets (such as the rational numbers), see:
One-to-One Correspondence and Transfinite Numbers Infinite Sets Counting Rationals and Integers
More real numbers than integers?
Here is a 1997 question about the claim that there are more real numbers than integers:
Size of Infinity How can one infinity be bigger than another infinity? For example, the number of real numbers between 0 and 1 is infinite. The number of integers greater than 1 is also infinite. Yet the first infinity mentioned is bigger than the second one. I don't get it.
Doctor Rob replied:
This has puzzled many people over the years. It has to do with the way we count.
When you count objects, often you touch (or look at) one of them and say "One." Then you touch another and say "Two." You continue touching previously untouched objects until you run out of them. Then the last number you said is the number of objects.
In the abstract, what you are doing is setting up a one-to-one correspondence between the objects and a finite set of natural numbers of the form {n | 1 <= n <= N}. It is one-to-one because no number is used twice, and it is a correspondence because no object is used twice.
That is, one object corresponds to one number. We say that the cardinality of the set (that is, the cardinal number for it) is N, the last number used.
An extension of this can be used to "count" infinite sets. Again a one-to-one correspondence is set up between the set of all natural numbers and the set of objects. If all the objects correspond to a natural number, and all natural numbers correspond to an object, then the set of objects is said to have the same _cardinality_ as the set of natural numbers. The same procedure can be used for any two sets. If they can be put into one-to-one correspondence, then they are said to have the same cardinality. In the case of a finite set, the cardinality is just the number of objects. In the case of infinite sets, one might naively think that all of them would have the same cardinality, and call that "infinity."
That is, it feels natural to think of infinity (∞) as a “number” that counts any infinite set, even though we know that infinity can’t really be used as a number, because it doesn’t follow the usual laws. (For instance, ∞ + 1 = ∞, which is impossible for actual numbers.)
In fact, there are infinite sets A and B which cannot be put into one-to-one correspondence with each other, but A can be put into one-to-one correspondence with a subset of B. In this case, the cardinality of A is the same as that of the subset of B, but not the same as the cardinality of B. B is said to have larger cardinality than A. Notice that in the case of finite sets, the cardinality of a proper subset of a finite set is always smaller than the cardinality of the whole set, so the analogy is apt. Your example is like that: the natural numbers cannot be put into one-to-one correspondence with the real numbers between 0 and 1, although they can be put into correspondence with a subset (via n <-> 1/(n+1), for example).
We always have to be careful with infinity, though; the cardinality of an infinite subset of an infinite set can be the same as the cardinality of the whole set. An easy example to prove (though not to grasp) is that there are “just as many” even integers as there are integers. (To prove this, just let each integer n correspond to the even integer 2n. This matches …, -2, -1, 0, 1, 2, … with …, -4, -2, 0, 2, 4, … .)
Doctor Rob’s last paragraph matches the natural numbers 1, 2, 3, .. with the real numbers 1/2, 1/3, 1/4, … in the interval (0, 1).
The hard part is to *prove* that constructing a one-to-one correspondence is impossible in certain cases. That is done by contradiction, by making the assumption that one exists, and from that deducing a false statement. This means that the assumption had to be false to begin with, and the existence is therefore impossible. In this case, suppose there were such a correspondence. Make a table with the first column containing the natural numbers 1, 2, 3, 4, ..., and the second column containing the corresponding real numbers between 0 and 1, written out in decimal expansions. It would take the form: 1 0.*********... 2 0.*********... 3 0.*********... 4 0.*********... ... ...
Note that we are not claiming there actually is such a list; we are supposing that there was, and showing that something would go wrong. So don’t try too hard to imagine that list.
According to the assumption, all real numbers between 0 and 1 will appear in some row in the second column. Now we will construct one which doesn't appear, as follows. Consider the number D beginning "0." and continuing with the digits appearing on the *diagonal* of the array of digits in column 2 of the table. Now pick any number X whose digits *disagree* with D in every decimal place, but which contains no 0 or 9. (There are 7 or 8 choices for each digit of X, so this is easy to do.) Where could it appear on the list? For any natural number k, it cannot be in row k, because its k-th digit differs from the k-th digit of the number appearing in row k. This number is not on the list in any row. As a result, the assumed one-to-one correspondence doesn't exist. Notice that it did not matter in what order we put the numbers in column 2 above, the same construction works. Notice also that there are huge numbers of X's which can be constructed this way: at least 7^k possibilities for just the first k digits to the right of the decimal place; and *none* of them is on the list. (The funny business with 0 and 9 is to avoid the fact that some numbers have two decimal expansions: for example, .500000000... = .499999999... . The constructed X misses both of these representations whenever they exist.) I hope I haven't boggled your mind with this. Mostly it wasn't known until the time of Georg Cantor, in the 19th century.
Cantor’s diagonalization proof again
There are a couple tricky points in the proof, as a result of which it is very easy to give a form of the proof that leaves some loopholes (such as the 9’s). Here is another question about it, from 2001:
Orders of Infinity I recently read a book about infinity that set forth several arguments for why there are different sizes or orders of infinity. None of them seems convincing to me, and, since my ignorance of math is vast, I was wondering if you might fill me in on where my reasoning has gone wrong or provide more convincing lines of argument to me.
Doctor Luis answered; I’ll extract just the central part of his answer, and modify it according to a suggestion from a Professor Loewen, who wrote to us in 2010 to point out a typo that made the proof as originally given incorrect, and an additional modification (following Doctor Rob’s mention of 0 and 9 above) that would make it complete. Somehow this correction never made it into the archive. Here is the proof, as amended:
Cantor showed (via his famous "diagonalization" proof) that the set of real numbers is uncountable. He actually found a much more complicated proof first and he didn't convince many people, but years after having found that solution, he found a much more elegant proof. In fact, it's so simple that I'll reproduce it here, in case your book didn't.
First I'll start by noting that there are as many elements in the set of real numbers as there are elements in the set (0,1) = {x | 0<x<1 }. To see this, you need only find a bijection (one-to-one function) that takes (0,1) to R. For example: f(x) = Arctan(Pi*(2x-1))
Now assume that we can set up a one-to-one correspondence between the natural numbers and (0,1). Naturally, I'd expect to see an explicit listing of such a correspondence:
1 -> 0.0011213213111...
2 -> 0.8199191988110...
3 -> 0.8878181888108...
4 -> 0.3996771726507...
......
And so on, where each real number in (0,1) appears exactly once to the right of a unique natural number on the left. (Here, I'm implicitly asking for a single decimal representation for each real number, with no repeating 9's so that you don't get any duplicates on the right. Example: 0.499999... = 0.500000... This is clearly not much to ask of our listing, but you'll see why this point is important later on.) So far so good?
It was Cantor's genius to realize that such a listing is impossible.
"Why?" you ask. Well, we can start by observing that we've required every number to be on the list. Now, let's define a new real number y with the following property: The n-th decimal digit of y is either 7 or 8. We choose 7 whenever it is different from the n-th decimal digit of the n-th number in our list, and 8 whenever this doesn't work. So, given the list above, we would define
y = 0.7787...
Our real number y is clearly well-defined. You provide me with a listing of all real numbers in (0,1) and I'll be able to produce a number y. (That's why I required a single decimal representation for each real number, so that y could be defined properly. It's also why I chose to make y without ever using the digit 9.)
Now, here comes the key step. y is itself in (0,1), so it must have a corresponding entry in our listing. We did after all, list all real numbers. The problem is, what natural number m corresponds to y?
Well, m can't be 1, since by definition y differs from the first number in the first decimal digit. m can't be 2, since by definition y differs from the second number in the second decimal digit. In fact, if n is a natural number, then m can't be n since by definition y differs from the n-th number in our list by precisely the n-th decimal digit. (y is defined by the diagonal entries in our list, hence the term "diagonalization proof.")
We have produced a number that's not in our list! This is a glaring contradiction. A one-to-one correspondence between the natural numbers and (0,1) is impossible. Therefore the set (0,1), and by extension, the set of real numbers, is innumerable.
Attempts to list the real numbers
Now let’s move from the “how can this be?” questions to the “you’re wrong” responses.
Many claim to be able to list all the real numbers. The following came to us in 1997, not actually telling us we are wrong, but humbly asking where he is wrong:
Counting Infinities I was re-re-rereading Gamow's _1,2,3...Infinity_ and thought I found a flaw in the uncountability proof. My method of listing decimals was to enter the numbers in binary, writing them backwards: .0, .1, .01, .11, .001, .101, . . . I was thinking I would get all possible decimals. The counterproof of changing the numbers in the diagonal would produce .111111... = 1, which shouldn't be included anyway. Since I don't really think that aleph 1 > aleph 0 just because we have ten fingers, I decided that I must not really be including all decimals, but I still can't see why. For instance, I suspect that I don't have 1/3 in my table, but since I include the first 10, first 1000, and first googol digits of 1/3 somewhere (I could tell you which lines, but you don't really care, do you?) in my table, it seems, (by induction?) that I should get exactly 1/3 eventually, but I get myopic around a googolplex.
He has taken the binary numbers 0, 1, 10, 11, 100, 101, … and reversed them to get .0, .1, .01, .11, .001, .101, … . Others have suggested doing the same thing in decimal, turning the list 1, 2, 3, …, 10, 11, 12, 13, … into 0.1, 0.2, 0.3, …, 0.01, 0.11, 0.21, 0.31, … . Like Gene, Cantor used binary rather than decimal representations, which is more natural, mathematically (though doing so forced him to use a different approach than avoiding 9 and 0 in order to get past the double-representation problem).
Doctor Rob took this:
Even when the proof is given writing the numbers in decimal, you have to avoid .9999999.... = 1.0000000...., an artifact of all such positional numeral systems. The usual "diagonal construction" contains the provision that you pick for the n-th digit a digit other than the one in row n, column n, *and also different from 9*. That avoids the ambiguity. In binary, if you pick a digit other than the one in row n, column n, and also different from 1, you may have no choices left, as in your example. You could modify this slightly to use *pairs* of bits, avoiding the pair 11 and the pair occurring in row n and columns 2n-1 and 2n. This would fix up your construction. Since 1/3 = .01010101...., you can use this method to show that it cannot appear.
The important thing is that his list contains only terminating representations, so it doesn’t even include all rational numbers, not to mention irrationals:
As to the matter of 1/3, it is not in your list. The numbers in your list are just those of the form a/2^b, where a is 0 or odd, and b is positive. 1/3 cannot be written in this form, because of the Fundamental Theorem of Arithmetic (unique factorization into primes). If it could, 1/3 = a/2^b <==> 2^b = 3*a = n, and 2 and 3 prime, violates unique factorization of n. You do have excellent approximations to 1/3, as good as you like, but you don't have 1/3 itself. This is somewhat like the situation where the rational numbers do not contain sqrt(2), although they do contain excellent approximations, as good as you like.
Doesn’t the same proof apply to rationals?
Others have claimed that the method of proof fails, by showing that it produces nonsensical results when applied to other sets than the reals. Here is one from 2005, which was not archived:
Dear Dr. Math! There is a popular alleged proof of the fact that the irrational numbers are non-denumerable, which seems to me to allow for a parallel proof that the rational numbers are non-denumerable. ... What I simply DO NOT get is where the mistake is, if we replace all references to irrational numbers with references to rational numbers and then follow through with a parallel "proof" that if we assume that the rational numbers are denumerable, then we can create a new rational number not already in our list in the same way as before. I mean, the argument cannot be that we have independent proofs that the rationals are denumerable and that they are not (for then we might as well claim that the irrationals could some day be proven to be denumerable, which is a kind of reasoning that would demolish any idea that mathematical proofs proof something), nor that the rationals cannot be written as decimal expansions (which they obviously can!)?!
Doctor Jacques replied:
The proof does not work for rational numbers, because every decimal expansion does not necessarily represent a rational number. The decimal expansion of a rational number is either finite or periodic. If you try to use Cantor's argument with the rational numbers, you will end up with a decimal expansion that does not appear on the list, but you cannot derive a contradiction from this, because you cannot prove that the new string of digits is finite or periodic, i.e., that it corresponds to a rational number.
The proof for real numbers depends on the fact that any (non-terminating) decimal corresponds to a real number.
In fact, you can make a list of the rational numbers between 0 and 1 (see below). If you apply Cantor's argument, you will end up with a decimal expansion that is not on the list - this simply means that the corresponding real number is irrational. In the case of real numbers, you get a contradiction, because you assumed that all real numbers were on the list. To make a list of the rational numbers between 0 and 1, you can, for example, order them by increasing denominators first, and leaving out fractions that are not in lowest terms: 0, 1, 1/2, 1/3, 2/3, 1/4, 3/4, ...
Christian wrote back:
Thank You very much! I am a bit embarrassed that I did not see the central point - that no contradiction arises in the case of trying to create a new rational number since the newly created number cannot be proved to be rational - but I am also very thankful to you, for your swift and clear response. Thank You again so much!
Some others have tried to apply the diagonalization proof to integers; in that case, the new number is an “integer” with infinitely many digits, which (unlike numbers with infinitely many decimal places) is nonsense.
Pingback: More on Uncountable Irrationals – The Math Doctors
Pingback: Hilbert’s Cookie Jar: Little Kids, Big Ideas – The Math Doctors