Lesson 14: Infinity Infinities

In lesson 13 we established that there are at least two different kinds of infinities.  Now, we go on to see that there are in fact infinitely many different kinds of infinities.  If you’ve studied and understood the method of proof that we used in the last lesson, then the methods that we use in this lesson will be a breeze.  We will again use the method of proof by contradiction, and we’ll alsou use an idea very similar to the “diagonal slash” argument in the previous lesson.

Recall that this diagonal method (which is so famous that it is actually referred to in the biz as “Cantor’s Diagonal Slash”) involved supposing that there is a bijective correspondence between two infinite sets, and then finding an element in one of the sets that isn’t “hit” by the correspondence.  We found this element by going down the “diagonal” and defining our element in a way that ensures that it doesn’t show up anywhere in the correspondence.

So how do we show that there are infinitely many infinities?  Well, this is actually the same question as how one shows that there are infinitely many numbers.  We all know that there are infinitely many numbers because if the enemy hands me a number (and perhaps she claims it’s “the biggest number”), I know that I can always add 1 to it.  (In fact, I can add a million to it if I wanted to, but adding 1 is sufficient.)  In a similar way, I’ll now show that if the enemy hands me an infinite set, I can define a new infinite set whose cardinality is fundamentally bigger in the sense that we’ve been studying.  Since this new set will obviously also be infinite, I’ll be able to define another new, infinite, and larger set.  I then repeat, infinitely many times.  This is the analogue for “infinite numbers” of “adding 1”.  Let us see how this works.

We begin with the “smallest” infinity, which is infinity type 1.  (This is the “smallest” in the sense that any other infinite set can have a surjective function defined from it to the infinity type 1 set, but the converse is not necessarily true.  I.e., given two infinite sets A and B, where A has cardinality infinity type 1, and B’s cardinality is unknown (other than it being infinite), then we can always define a surjective function from B to A, but not necessarily from A to B.  This was precisely what we showed last lesson where and )  What is the analoge of “adding 1” to an infinite number, so that we get a brand new infinity that is truly larger than the previous one?  We’ve already seen the construction in lesson 3, and we defined it more rigorously in lesson 4—it is the construction of the power set.

Recall that if we have a set A, we can form its power set, which we denote by  whose elements are subsets of A.  We saw in lesson 3 that if A is a set with N elements, then is a set with elements (see lesson 3 for a description of the notation “”).  But regardless of whether or not A has finitely many elements, we can always define its power set.  Clearly, if A has infinitely many elements, so does .  This is easily seen by realizing that each element in A (of which there are infinitely many) defines a perfectly good 1-element subset of A, and therefore defines a perfectly good element in  What’s important to notice is that there are way more subsets than that, though!  We also have all of the two element subsets, and three element subsets, and four element subsets, and even all of the infinite element subsets!

Let’s now focus on the case .  There are the finite element subsets like , and there are infinite element subsets like .  Clearly, there are tons and tons and tons of distinct subsets.  But there were also tons and tons of fractions in FRAC, and we showed in lesson 12 that the cardinality of FRAC and A were the same.  So is that the case here?  The answer is no, and let us see why.

Again, we suppose that there is a bijective correspondence, call it F, between A and  I.e., F is a bijective function from A to   Now, if this were the case, then this would mean that F maps each positive whole number to some subset of the positive whole numbers.  We’d get infinitely many expressions of the form where is an entire subset of positive whole numbers (because it is an element in the power set of the positive whole numbers, whose elements are sets), as is and so on.

Using this infinitely long list of expressions of the form we can construct a subset of A that is not in the list.  We do this as follows.  We’ll call this new set T, and we define it similarly to our diagonal slash from last lesson.  Namely, if 1 is in (i.e, if 1 is in the subset which it labels under the mapping F), then we don’t put 1 in the set T, and if 1 is not in S1, then we do put 1 in T.  Then we move on to 2.  If 2 is in then we don’t put it in T, and if 2 is not in we do put it in T.  We then do this for all of the sets .  This defines a perfectly good subset of A, and is thus an element in But is T in our correspondence?  Clearly it isn’t, because it differs from by either having or not having the element 1 (according to whether or not does), and it differs from in the element 2, and from in the element 3, and so on, all the way down the list.  Since the list was supposed to have every element in (by assumption of the fact that F was bijective), we clearly have a contradiction!

Thus no bijective function can be defined from A to , and thus must have a fundamentally different cardinality.  Namely, it must be a different (and larger, since we can certainly define a surjective function from to A) infinity!

But now let’s suppose that A is any infinite set.  Any infinite set at all.  Then can we put A and (the power set of whatever this new A is) into a bijective correspondence?  The answer is no (again, for the experts, heavily relying on the Axiom of Choice), and the reason can be seen quite easily after the above argument is understood.  Namely, we suppose there is a bijective function F from A to P(A).  Then we define a new set T—a subset of A—as follows.  For each element “a” in A, we put “a” into T if and only if “a” is not in which is the subset of A that “a” is mapped to.  By the same logic as above, this new subset T cannot possibly be mapped to by any element in A because we’ve defined T to differ by every for any “a” in A (there is actually a cool parallel between this logic and that used in the paradox of lesson 5 for which the details are in the exercise below).  Thus no bijective function from A to  can be defined, and so must be a different (and larger) type of infinity than A.

Now here’s the catch—the punchline, if you will.  We’ve just shown that if A is an infinite set, then is an infinite set of a fundamentally larger cardinality.  But what’s even more important is that is infinite (duh).  Thus, the same logic that was used above can be used on itself!  I.e., the power set of  which we obviously denote as (and which is read aloud as “the power set of the power set of A”) must have a fundamentally larger cardinality than since we can’t define a bijective function between the two!  Similarly, must be fundamentally “more infinite” than and must be fundamentally “more infinite” than !  We can hit each successive power set with another “” operation, thus defining another new level of infinity.  Clearly we can do this as many times if like. Namely, if you hand me some set and say it’s “the most infinite” set out there, then I can just hit it with a and obtain a fundamentally more infinite one.  Sound familiar?  It should!  We’ve just found a way to literally “add 1” to infinity in order to get different, larger infinities.  In fact, we get infinitely many of them!

Before ending this lesson and moving on to wildly different concepts for a while, let us introduce some of the ideas and unsolved problems that exist out there in the world of math. We will discuss these more in future lessons but it doesn’t hurt to introduce them now. And since this is just an introduction, we will not discuss these ideas in depth and so some confusion may arise. This is okay, though, as it will encourage us to keep moving forward into this amazing world of mathematics.

In the last this lesson we saw a way of “adding 1” to infinity, in order to get another, larger infinity. We compared the procedure of taking the power set of a finite set to the procedure of adding 1 to a normal, finite number. The natural next question to ask, then, is whether or not there is an analogue to adding one half to a normal, finite number. Namely, we know that we can add 1 to 1 to get 2, but we also know that if we allow for fractions then we can add to 1 to get The result of adding one to a number is to get a number that is truly in between the number itself, and the number that is obtained by adding 1. Namely, is truly in between 1 and 2, because it is greater than 1 and less than 2. Thus, we might ask whether or not there are any infinite sets that have a truly larger cardinality than and a truly smaller cardinality than

For this to be the case, we would need a set such that there is no bijective function from to either or so that the cardinality of does not equal the cardinality of either or Additionally, this set would need to be such that there was a surjective function from to (so that the cardinality of is truly larger than that of ), as well as a surjective from to (so that the cardinality of is truly smaller than that of ). If we could find such a set, then we will have found an infinity that is “between” the infinity of and that of . One natural guess for such a set would be since we already know that it has a larger cardinality than Therefore, if we could show that has a larger cardinality than we will have solved the problem, and the answer would be that there do exist sets whose cardinality is between and It turns out, however, that the cardinality of is the same as that of though we will not provide the proof of this statement here. This means, however, that we haven’t yet found a set whose cardinality is between that of and Let us therefore ask: Is there such a set at all?

This is a perfectly reasonable question to ask, but it turns out that no one knows the answer to it. Georg Cantor — the brilliant mathematician who developed this entire formalism regarding infinity — died before he could figure it out, and every other mathematician that has tried to figure it out is either still struggling over it or has also died before succeeding. Namely, there is a statement called the Continuum Hypothesis which states that there is not a set whose cardinality is between that of and that of but no mathematician has been able to prove that this is a true statement. Indeed, the Continuum hypothesis is unlike many other unsolved problems in math — the problem itself has a problem. It has in fact been shown that, using our standard system of mathematical axioms, the Continuum Hypothesis is actually unsolvable. What we mean by “unsolvable” is that even if it is true, we can’t prove that it is so. The possibility of fundamentally not being able to prove something within a given set of axioms comes from the remarkable result uncovered by the mathematician Kurt Godel, who proved what’s known as the Incompleteness Theorem (we will have more to say about the Incompleteness Theorem and its profound impact on math in a future lesson). The Incompleteness Theorem effectively tells us that in order to know whether or not the statement “there is no set whose cardinality is strictly larger than that of and strictly smaller than that of ” is true, we’ll have to change the very foundations of mathematics! This is most certainly not a small task to ask for, but the difficulty of a problem has not stopped mathematicians in the past!

Before ending this lesson we should note how all of this discussion about infinity is only the tip of a very large iceberg. To see this, let us recall yet again how we have constantly used various properties of the finite numbers to motivate various definitions in the infinite case. We saw that this analogy allowed us to define some very abstract notions of counting, and these definitions allowed us to uncover a remarkable organization and order within the realm of the infinite. It turns out that we can still do a lot more. Namely, there is a beautiful and abstract way to define addition, subtraction, multiplication, division, and exponentiation in such a way as to simultaneously incorporate the finite, as well as the infinite numbers. In doing so, we will have put all of the various infinities on essentially equal footing with all of the various finite numbers, thus extending our very notion of what a number is to a much larger class of numbers — a class of numbers which includes the previously mysterious notion of infinity.

In order to see all of this — i.e., the details of the Continuum Hypothesis, the implications of the Incompleteness Theorem, and the ways in which we can add, subtract, multiply, and divide infinite numbers just like finite ones — we must develop some more mathematical machinery. Along the way, we will see lots of other forms of mathematical beauty over a wide range of topics, so let us temporarily leave the world of the infinite behind us and move forward to develop more mathematical weaponry.

Next Lesson

Previous Lesson