Infinity comes in all sorts of sizes. The counting numbers are a humble countable infinity (by definition), while last time we showed that the real numbers1 (between 0 and 1) are a much more respectable uncountable infinity.
Can we go biggerer?
The next bigger infinity is not as familiar as the numbers between 0 and 1. A natural choice would be all the points on the plane (i.e., in a 2-dimensional space, versus the 1-dimensional space of the real numbers.) But as we mentioned last time, you can show that the cardinality (or size) of these two sets is the same.2
We’re going to need to introduce a new idea to come up with a bigger set. This idea is power sets.
No, Superman, it’s not.
A subset of a set is some smaller collection of the elements in the set. So, for example, is a subset of . The power set of a set is simply the set of all subsets.
Yeah, okay, we need some examples.
Let’s start with the set . The easy subsets are and . However, we also need to count two other subsets: the subset of nothing (the empty set3, which is denoted ) and the subset of everything (the original set .) So, the power set of is .
The notation for the power set comes from the name power set, but it looks a bit weird. The “power set of ” is written as . While there is some reason for this notation (see the Wikipedia page), it is still kind of weird, but at least explains the name “power set.”
Our goal with the power set is to come up with bigger sets and, so far, we’ve succeeded. We started with , which has cardinality two (i.e., has two elements), but ended with a set with cardinality four.4
For any finite set, we get a bigger one. For instance, , so we go from three elements to eight elements.
Do infinite sets get bigger?
They do! And the principle for proving it is essentially the same as we used to prove that the real numbers are uncountable.
Let’s prove this for the counting numbers. I’m going to be briefer than in the last post, so if you haven’t read that one, you probably should. Recall that two sets are the same size (have the same cardinality) if there is a one to one correspondence between them.
In the last post, we tried to make a list of the real numbers. Here, we want this proof to work for any infinite set, so I’m going to avoid making a list, since for any bigger infinite set, you can’t write down a list for the set.
As before, let’s assume the power set of the counting numbers is countable. This means we can set up a one-to-one correspondence (bijection) between the counting numbers and the set of subsets.5 Each number has a corresponding subset.
Again, we are assuming there is a correspondence of numbers with subsets of numbers. Or, in other words, we have made number-subset pairs for each and every subset of the counting numbers.
Our goal is to find something not represented in this correspondence, just like we tried to find a real number not in the list of numbers (between 0 and 1) in the last post. We are trying to find a subset of the (counting) numbers that is not paired with any number.
If we can find a subset of the counting numbers that is different from each of the subsets in the correspondence, something is wrong with our assumption that we have a correspondence at all, and so the power set must have larger cardinality!
Can we construct such a subset?
In order to build a subset of the counting numbers, we need to go number by number and decide whether or not it is in the new subset we are constructing. Is 1 in the set? Is 2? Is 138?
In order to decide, we look at each number-subset pair in the correspondence. (Remember this correspondence?)
If the number in the number-subset pair is in the subset, we don’t put that number in our new subset. If the number is not in the subset, we do put that number in our new subset.
For instance, if the number was 17 and the subset was , then we would not put 17 in our new subset. If the number was 18 and the subset was (the empty set), then we would put 18 in the subset.
In this way, the new subset is different! For instance, using the example above, it doesn’t have 17 in it, and so the new subset can’t be , but it does contain 18, so it can’t be .
Thus, the power set has larger cardinality.6
This lets us create an infinite series of infinite sizes, each larger than the last. If your set isn’t large enough for your tastes, just look at its power set, and it will be even larger!
What names do we give these new sizes of infinities? This turns out to be an interesting question in its own right!
For most purposes, it suffices to just differentiate between countable infinity and uncountable infinity, and so these bigger infinities can be lumped together as uncountable infinity. But in the post on the size of infinity we gave the cardinality of the counting numbers the special name , aleph null.
What is ?
The cardinality is, by definition, the cardinality that is just bigger than . In other words, there are no infinite cardinalities between and .
It would seem reasonable that should be the cardinality of the real numbers and/or the cardinality of the power set of the counting numbers.7 This is called the “continuum hypothesis,” where continuum is another name for the real numbers.
Georg Cantor, the inventor of all these ideas, tried to prove this hypothesis in the late 1800’s. David Hilbert, a famous mathematician, listed it in 1900 as one of the most important mathematical questions for the following century. In the 1930’s, Kurt Gödel managed to prove that you can’t prove the hypothesis false. Then, finally, in 1963 Paul Cohen proved that, using the standard rules for sets, the continuum hypothesis cannot be proven true either. One can decide for oneself.8
There is a similar question on whether the cardinality of the power set of the reals is , i.e., the next bigger infinity. But whether it is or not, there is a infinite series of these cardinalities. After is . And, for fun, after all of those infinite cardinalities, we have . Because who wouldn’t want the infinity-eth infinity?9
That’s all I’ll be talking about infinity, at least for now.
Starting next week, I’ll be moving onto some geometry! (Don’t worry. It’s super cool.)
- The real numbers are any number that isn’t imaginary, so this includes both rational and irrational numbers. ↩
- The proof using a space-filling curve that I mentioned last time requires the axiom of choice, which some find distasteful. (I’m sure I’ll eventually have a post discussing why, but, in short, the axiom of choice produces all sorts of counterintuitive results.) But there are other proofs, like Cantor’s original proof of “interleaving digits.” The basic idea isn’t too bad (take 0.12345… and compare it to the point (0.135…, 0.246…)), but the devil is in the details. It’s explained in some detail here, though the description is somewhat technical. ↩
- The idea of the empty set is weird, but just as important as the idea of zero. The empty set is the set with nothing in it. It is something, namely the empty set, but it contains nothing. For example, the set of the empty set is not the empty set; the set contains one element, the empty set. ↩
- You may notice that . This is not a coincidence. It turns out that for any finite set with cardinality , its power set has cardinality . Pretty cool, eh? The notation was useful! ↩
- The subsets here could be finite, like , or infinite, like . ↩
- This theorem, that the power set always has larger cardinality, is called Cantor’s theorem. ↩
- Though not obvious, it does turn out that the real numbers and the power set of the counting numbers have the same cardinality. This site has a proof, relatively near the bottom. ↩
- Actually, there’s some debate about that. Some mathematicians think that you can just choose one way or another, at your leisure, and you just get slightly different logic systems. Paul Cohen was of this family. Others, like Kurt Gödel, felt that you should be able to prove the continuum hypothesis true (or false) by adding a number of additional, justifiable axioms. You can read more here. ↩
- And past that, you have and so on and so forth. This ladder never ends. ↩