## An even biggerer infinity

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?

We can!

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.

subset of a set is some smaller collection of the elements in the set. So, for example, $\{1,3,5\}$ is a subset of $\{1, 2, 3, 4, 5\}$. 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 $\{1, 2\}$. The easy subsets are $\{1\}$ and $\{2\}$. However, we also need to count two other subsets: the subset of nothing (the empty set3, which is denoted $\emptyset$) and the subset of everything (the original set $\{1, 2\}$.) So, the power set of $\{1, 2\}$ is $\{\emptyset, \{1\}, \{2\}, \{1, 2\}\}$.

The notation for the power set comes from the name power set, but it looks a bit weird. The “power set of $\{1, 2\}$” is written as $2^{\{1, 2\}}$. 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 $\{1, 2\}$, 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, $2^{\{1, 2, 3\}} = \{\emptyset,\{1\}, \{2\}, \{3\}, \{1, 2\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}\}$, 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 $\{1, 2, 3, \cdots\}$ 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 $\{\textrm{all odd numbers}\}$, then we would not put 17 in our new subset. If the number was 18 and the subset was $\emptyset$ (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 $\{\textrm{all odd numbers}\}$, but it does contain 18, so it can’t be $\emptyset$.

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_0$, aleph null.

What is $\aleph_1$?

The cardinality $\aleph_1$ is, by definition, the cardinality that is just bigger than $\aleph_0$. In other words, there are no infinite cardinalities between $\aleph_0$ and $\aleph_1$.

It would seem reasonable that $\aleph_1$ 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 $\aleph_2$, i.e., the next bigger infinity. But whether it is $\aleph_2$ or not, there is a infinite series of these cardinalities. After $\aleph_2$ is $\aleph_3$. And, for fun, after all of those infinite cardinalities, we have $\aleph_\omega$. 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.)

1. The real numbers are any number that isn’t imaginary, so this includes both rational and irrational numbers.
2. 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.
3. 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 $\{\emptyset\}$ is not the empty set; the set contains one element, the empty set.
4. You may notice that $2^2 = 4$. This is not a coincidence. It turns out that for any finite set with cardinality $n$, its power set has cardinality $2^n$. Pretty cool, eh? The notation was useful!
5. The subsets here could be finite, like $\{1, 7, 138\}$, or infinite, like $\{\textrm{all even numbers}\}$
6. This theorem, that the power set always has larger cardinality, is called Cantor’s theorem.
7. 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.
8. 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
9. And past that, you have $\aleph_{\omega+1}$ and so on and so forth. This ladder never ends.

## A bigger infinity

Infinity is weird, and always will be. I mean, you can’t do something infinitely many times or have infinity dollars, no matter what Scrooge McDuck thinks.

Even mathematicians are not immune to thinking vaguely about infinity.

Georg Cantor was one of the first mathematicians to really sit down and investigate infinity. Until his work in the late 1800s, the conception of infinity, even among mathematicians, was really no deeper than a school child’s; infinity was the thing bigger than all the numbers.

But infinity is larger and deeper than that.

In the last post, we talked about how to determine the size of a set: if we can make a one to one correspondence between two different sets of objects, then those sets are the same size. This is easy if we’re comparing, say, the set consisting of a triangle, a square and a pentagon to the set $\{1, 2, 3\}$.

However, using this same idea, we showed (using ideas from our friend, Georg Cantor) the surprising fact that the set of all rational numbers1 are only the same size as the set of the counting numbers $\{1, 2, 3, \cdots\}$.

In other words, both sets have the same cardinality, which we defined to be $\aleph_0$. We also called this size countably infinite, since, if we order the rationals in a clever way, we can count them.

Since there are infinitely many rational numbers between 0 and 1, but somehow there are only as many as you can count, it begs the question:

Can we go bigger?

It turns out we can! Just as there are countably infinite sets, there are also uncountably infinite sets.2

Let’s look at all the numbers3 between 0 and 1. (This includes numbers like 1/3 and 1/4 and 12358/342893, but also irrational numbers4, like $\sqrt{2}/2$ or $\pi-3 = .1415\cdots$.) There are a lot of numbers hanging out between 0 and 1, but it isn’t immediately clear that there are more of them than there are in a countable set, is it?

It turns out that the set of numbers between 0 and 1 is bigger than the set of counting numbers, i.e., that they are uncountable. We’ll prove it.

Now, even though we want to prove the real numbers are uncountable, we’re going to prove it by assuming the opposite: that they are countable. By the definition of countable, that means we can set up a one to one correspondence with the counting numbers. In other words, we can count all those numbers between 0 and 1.

Counting them is the same as saying that we can put all of them in a list, since they are countable, or, rather, because we assumed they are countable.

So, if we can find a number between 0 and 1 that is not on the list, then something is wrong with the assumption we made about our set being countable. And since it can’t be countable, therefore it is uncountable5. Still with me?

In order to explain how to find this number, we need to talk a bit about decimal representations. Every number can be expressed as an infinite decimal. So, 1/3 = 0.33333333333…, and $\pi-3$ = 0.141592652589…, and 1/4 = 0.2500000…

These representations are unique… unless we have a repeated nine. For instance, 0.499999999… = .5, for the same reason that 0.999999… = 1. 6 In order to avoid this, let’s outlaw repeated nines.

In order to find a number not on the list, we just need to find a decimal representation that is different than all of those in the list (and make sure it doesn’t accidentally have repeated nines.)

While our assumption that the numbers between 0 and 1 are countable does not mean we know what the list actually is, let’s pretend we have such a list, like this one:

Don’t worry that there is no rhyme or reason to this list. The main argument below should work for any list that we could think up, whether it is reasonable or random.

How can we construct a number not on the list? Well, in order for our new, constructed number to be different than any given number on the list, it has to differ by at least one digit.

We will ensure that our new number is different than any number already on the list by making sure that the first digit of the new number is different than the first digit of the first number on the list, the second digit of the new number is different than the second digit of the second number, the third digit of the new number is different than the third digit of the third number, the fourth digit of the new number is different than the fourth digit of the fourth number, and so on and so forth.

So, we make the first digit different than 8. Let’s start by saying the first digit of our new number is 6, giving us 0.6.

We also need it different from the second number. We’ve already decided on the first digit, but we can make the second digit 6 as well, since 6 is different than 7. This gives us 0.66.

For the third digit, we can’t use 6, but 5 would work instead, so the third digit of our new number is 5. Our new number is 0.665.

For the fourth digit, we’ll again pick 6, since 6 is different than 3.

So far, our new number is 0.6656. It is clearly different than the first four numbers on the list, since they each differ by (at least) a single digit.

And this pattern is easy to continue. If the n-th digit of the n-th number on the list is anything but a 6, we make the n-th digit of our new number a 6. If it is a 6, we’ll make the n-th digit a 5. We do this infinitely many times to define the new number.7

Since our new number is different than every number in our list, it can’t be in the list!8

And thus, the numbers between 0 and 1 are uncountable.

So we now have countable infinity, and the bigger uncountable infinity. Can we go biggerer?

We can!

You might first be tempted to guess that the set of all numbers (from $-\infty$ to $\infty$) would be even bigger than the set of numbers between 0 and 1, but it turns out these two sets have the same cardinality, i.e. are the same size.

What’s more surprising is that all the points in the plane also have the same cardinality. I won’t prove this here, but the idea is to make a “curve” that goes through every point in the plane. You can do this in any dimension.

So how do you come up with a bigger(er) infinity?

In the next post, we’ll discuss power sets.

1. As a reminder, rational numbers are the numbers that can be written as a fraction of integers, like 2/3 or -7/18.
2. “Uncountable” is not just the negation of countable. It’s the technical term for any set of larger cardinality than $\aleph_0$
3. I mean real numbers. In other words, we’re not talking about imaginary numbers, but any other number will do.
4. Irrational numbers are just any number that can’t be written as a rational number, i.e., as a fraction.
5. This method of proof is called “proof by contradiction,” and is a standard method in mathematics. In this method, you assume that something is true, and then use it to show that something that is “obviously” false is true.
6. If you take two different representations, the representations have to differ by at least one digit. So, if you subtract the two, you have some (non-zero) difference between them, so they aren’t the same number. The only exception to this working is for repeated 9’s, as mentioned. This is because it isn’t immediately obvious what $0.5 - 0.4999...$ should be. However, those two numbers happen to be the same. (In case you haven’t seen this, let $x = 0.99...$. Then $10x = 9.99...$, and so $9x = 10x-x = 9.99... - 0.99... = 9$. Dividing by $9$, we get $x = 1$, and so $.99... = 1$.)
7. This argument is called “Cantor diagonalization.” It shows that infinity is not a monolithic concept or size. I’m planning on writing a short extra post about Cantor. He was an interesting person.
8. How’s that for a tautology?

## The size of infinity

How can you tell how many things are in a set? You count them, of course! I bring this up because, believe it or not, it’s going to tell us how to tell how big infinity is.1

What do you do when you count? Let’s say we’re counting superheroes. (Ah, this is bringing me back to Sesame Street. Those were the days.)

For each superhero, we associate a number with it. One number, one super. One super, one number. Since we get up through the number 4 in this process, we know our set of superheroes has four elements.

I know this is what you do with a 4-year-old, but bear with me.

Note that here, we’re not using the numbers to represent the order of the superheroes, but rather how many of them there are. That means, in this case, the number 4 isn’t really an ordinal, like we talked about last week, but a cardinal, which is just fancy math talk for a symbol representing how many of something there is. The cardinality of our set of superheroes is four.

The correspondence of the superheroes with the set of numbers $\{1, 2, 3, 4\}$ is how we know the two sets are the same size. This correspondence is technically called a bijection, but really it just means that for each object in one set there’s another one in the second set, and vice versa. Two sets have the same size, or cardinality, if you can come up with a way to compare the sets, one for one.

Well, what is the size of infinity? Remember, we can’t just say “infinity,” since cardinality is all about sizes of sets.

So, a reasonable way to define the size infinity is to say that it’s the size of the set of all counting (natural) numbers, i.e., it’s the size of the set $\{1, 2, 3, 4, 5, \cdots\}$. And, so that we have a symbol for it, we’ll label this infinite size $\aleph_0$, which is aleph, the first letter of the Hebrew alphabet. 2 This is read “aleph null.”

Another super important name (get it?) for this is countable infinity. This name comes from the fact that making this correspondence between your set and the natural numbers (representing $\aleph_0$) is the same as counting your set. In other words, if you can put your set in an ordered (infinite) list, it has the same cardinality as the natural numbers, $\aleph_0$.

What other sets are countably infinite?

Let’s start with a simple example, similar to the hotel example we discussed in the last post. The set of numbers $\{0, 1, 2, 3, \cdots\}$ clearly has more elements than the counting numbers $\{1, 2, 3, 4, \cdots\}$, but it’s straightforward to find a bijection. Simply associate 0 with 1, 1 with 2, etc. So those sets are the same size.

Okay, a slightly less obvious example. Consider all the integers, so the set $\{\cdots, -2, -1, 0, 1, 2, \cdots\}$. If you tried to start with 0 with 1, 1 with 2, 2 with 3, etc, you would not get a bijection (i.e., a one-to-one correspondence) since you’d never get to -10, for example.

But with a bit more cleverness, we can associate 0 with 1, 1 with 2, -1 with 3, 2 with 4, -2 with 5, etc. We have to alternate, but the set of integers is really the same size as the set of natural numbers, even though it seems twice as big.

Alright, now for a difficult one.

rational number is a fraction with an integer on top or bottom. There are a lot of them. In fact, there are infinitely many of them between 0 and 1. No matter how close you look, there are always infinitely more of rational numbers squeezed into that gap.

Certainly there are more rational numbers than natural numbers, right?

Well, this one requires even more cleverness. We’ll just worry about positive rational numbers, but the same trick we did with the integers would work to get the negative ones, too. Let’s arrange all the positive numbers in a grid.

There are duplicates here (like 4/2 and 2/1), but that’s not so important. Now, if we tried to count straight down a column, we’d get lots of rational numbers, but we would never get all of them. Instead, we count the numbers in a zigzag fashion. Anytime we get to a duplicate, we can skip that one.

So, if we associate 1/1 with 1, 2/1 with 2, 1/2 with 3, etc., we will count all the rational numbers.

There are as many natural numbers as there are rational numbers!

This defies my expectation. This is definitely one of those cases where your intuition gets confused about infinity and you need to tread carefully.

There are even bigger sets that are still only countable. For instance, the set of all algebraic numbers, i.e., numbers that solve polynomial equations like $27x^7-23 x^5+17x + 1 = 0$, contains all the rational numbers, but is still only countable. In fact, the argument to show this is essentially the same as the one we just used for rational numbers.

With all that, you may be tempted to believe every infinity is the same size.

But math is more awesome than that.3

1. Dear twitching mathematicians: Don’t worry, I’ll be careful.
2. Most things in math are Greek, but occasionally, we do use other languages. I have one friend who is fond of using a Korean symbol for tree as a variable instead of $x$
3. We’ll be exploring larger infinities in the next post.