Alas, we have finally gotten to the lesson where we’ll find a whole new kind of infinity! We’ve spent the last several lessons showing how infinite sets that seem different from are in fact the same as far as cardinality goes. But here, we’ll consider a set that is so large that it can’t be put into a bijective correspondence with no matter how hard we try.
Before we define this gigantic set, however, we need to first consider the elements that we’ll use to construct it. The elements in this set will be numbers that go by the technical name “real numbers”. Note that a real number is a technical object, and not the opposite of a “fake number”. What exactly is a real number? Well, there are actually many ways that we can motivate the definition of a real number, and all of which are currently beyond the tools that we have available to us. Thus, we’ll simply define a real number to be a number expressible as an infinite decimal. Let us therefore first remind ourselves of how decimals work.
A number like 1.5 or 12.6 should hopefully be relatively familiar to the reader. The digits to the left of the decimal point make up the “whole number part” of the real number, and the digits to the right of the decimal point make up the “fractional part” of the number. Thus, 1.5 is really just “1 and a half”, and 12.6 is just “12 and six tenths”, or equivalently “12 and 3 fifths”. A real number, however, is one in which the numbers to the right of the decimal go on forever. They are expressions like
where the “…” means, as usual, that this goes on forever. There doesn’t have to be any rhyme or reason to the numbers that are on the right of the decimal place.
Let us now make a few remarks about these numbers. The first remark is that any whole number can be written in this way, simply by letting the infinitely many numbers to the right of the decimal be zeros. Thus 1=1.0000000…, and -45=-45.000000000…. In a similar way, every fraction can be written as an infinite decimal. The general proof of this last statement is a little beyond us right now (and would not be particularly fun), but the intuitive reason for this is that every fraction either has a decimal expansion that “stops” eventually (i.e., has nothing but zeros forever after some point), or has a repeating pattern eventually (like ). I know the motto of this site is to be 100% rigorous about everything, but for this fact you’ll have to just take me on faith: every fraction is a real number (but not vice versa). The proof of this is really not important at all for what is to come.
The last thing that I’ll remark on, just so that you get the sense that these numbers are in fact “real”, is that these numbers actually have an extremely important role in mathematics. Namely, there are several extremely important numbers, such as “Pi” (which is the famous ) or the square root of 2, which simply cannot be written as a fraction and can only be written as a decimal that never ends and never repeats (the proof of the fact that the square root of 2 can’t be written as a fraction will come in a later lesson).
Let us now consider the set of all real numbers, which is commonly denoted in the business as . By the above remarks, this set has real mathematical utility and is in some sense “larger” than the set of fractions (and therefore larger than the set of whole numbers), because it contains this set as a subset. But as we’ve seen in the last couple of lessons, this does not mean that this set has a different cardinality. Let us now establish that indeed does have a different—and therefore larger—cardinality than FRAC (we know that if the cardinality is different, then it must be larger because contains FRAC). We will do this by showing that one cannot define a bijective function from to no matter how clever we are.
But how does one show that something cannot happen? Showing that something can happen is easy—you just do it. Showing that something can’t happen is more tricky, but luckily we have an extremely powerful tool for proofs of this type. Namely, we use the method of proof by contradiction. We will assume that we can define such a bijective function and then arrive at a logical contradiction, thus showing that this assumption is impossible to make (and thus showing that no such function can exist). The following argument is insanely beautiful and profoundly clever. It is the brainchild of one of the greatest mathematicians to ever walk this planet, who went by the name Georg Cantor.
Cantor’s Proof of the existence of a new infinity
Suppose that there is a bijective function from to . Let’s call this function F. Then we’d have a list of associations between elements in A and elements in such that every element in is “hit” by an element in A, using F. This is because we know F is surjective.
We’re now going to introduce a notation for real numbers that, although somewhat confusing at first, will make the proof extremely easy (don’t be scared of the notation—let me explain it first). We know that is some real number, so let’s denote this real number by where “” is a single whole number (positive, negative, or zero), the decimal place is there as usual, and each is some number between 0 and 9 (note that the ‘s are just abstract labels for individual digits). In other words, this is some generic decimal expansion for whichever real number is, where the is the “whole number part” and each is some part of the fractional part. Also, should not be thought of as “‘a’ subscript eleven” but rather “‘a’ subscript one one”, and should be thought of as “‘a’ subscript one two”, and so on. Thus, if we’d have and all the rest of the ‘s equal 0, forever. Similarly, we let where we just use the first number (which is “i”) in each “” as a bookmark for which element in the set A we’re talking about. I.e., where “i” is some element in I know this notation is confusing, but it’s the best I can do. Feel free to take a second to let it sink in. Once it sinks in, we’ll have a sword sharp enough to take this proof down in one thrust…
What we’ll do is find a real number that cannot possibly be “hit” by this function, which is impossible because the function was defined to hit every single real number! This is the contradiction we’re after.
Given such a hypothetical function F, we can construct the following infinitely long list:
and so on, forever. Remember, the expressions on the right hand side here are just bookmarks for whatever real number our function F takes us to. We now use this information to find a real number that can’t possibly be in our list, and we do this using the “diagonal argument”. Note that we can write any real number as , where B is a whole number and each is in (this is exactly the same as what we’ve done above, only without the extra index for keeping track of which element in we’re talking about). Let’s let , just for the hell of it. Now we let i.e., we take whatever numerical value has and add 1 to it (if equals 9, then we make it 0). Similarly, we let and so on all the way down the infinitely long list. Note that we’re going down the list along the diagonal and changing each digit on this diagonal by 1 (or changing it to 0 if it started out as 9). This defines for us a perfectly good real number () no matter what our function was, because this is a perfectly good infinite decimal. Let’s call this new number P, so that .
Let’s now ask where in our list P is. It must be somewhere, because P is a real number and our list contains all real numbers, by assumption. But P can’t be the first number because it differs from in the first decimal place ( does not equal because !). P also can’t be the second number in our list because it differs from in the second decimal place, and it can’t be the third number in our list because it differs from in the third decimal place. A little more thought will convince you that it can’t be in our list at all, because it differs from the element in our list (at least) in the decimal point!
Thus our function, which supposedly hits every real number, missed at least one real number! A contradiction!!!
Thus such a function can’t exist, and thus the set of real numbers cannot be put into a bijective correspondence with the positive whole numbers. We’ve found our new infinity!
Even though we’ve extended our number system by including “infinity type 1”, we still have sets that we can’t count. Accordingly, we call a set that is infinite and that can’t be put into bijection with an uncountable set. In the next lesson, we’ll see that there is even more to the story. Namely, there aren’t just two different kinds of infinities, but rather an entire infinitely tall tower of infinities, each “greater” than the one before it (in the sense that it can’t be put into bijection with the previous ones). For now, go celebrate that you made it to the end of this. It took some work, but I don’t doubt that the results are worth it (a lesson for life and for math)!