How Big are All Infinities Combined? (Cantor's Paradox)

Infinities come in different sizes.

There's a whole tower of progressively larger sizes of infinity.

So what's the right way to describe the size of that whole tower?

[MUSIC PLAYING] Talking about the sizes of infinite things is tricky, in part because the word infinite is often used in two distinct ways-- to refer on the one hand to the sets themselves, but also to refer to the sizes of those sets.

Now, in what follows, let's try to keep as sharp a distinction as we can between infinite sets on the one hand and infinite set sizes on the other, because doing so will let me highlight an especially paradoxical feature about infinite sizing that I don't think gets enough coverage.

Now, the technical term for a size, infinite or otherwise, is cardinality.

And I should probably use a term like numerousness or numerosity rather than size, because the idea that we're trying to generalize is the notion of how many.

Still, I'm going to say size a lot in this episode only because it's easier.

Now, once you get a handle on infinite sizing, you end up with some pretty counterintuitive results, like that the set of the natural numbers and the set of all integers agree in cardinality, while the cardinality of the real numbers is greater.

Kelsey discussed a lot of this in a previous episode about the hierarchy of infinities.

And it has good background information, so you might want to pause me and go check it out.

You'll notice in that episode that Kelsey never defined the cardinality of an infinite set, never said what cardinality actually is explicitly.

And I won't either, at least for today, for the simple reason that the arguments I want to lay out only require that we know how to compare the sizes of two sets, infinite or otherwise.

And it turns out that there's a way to do that without knowing what either of the two sizes actually is.

To borrow Kelsey's earlier analogy, suppose that there are some empty seats on a bus in which no one is standing.

Well, we know the quantity of people is less than the quantity of seats, even though we don't know how big either quantity is.

And if every seat is taken, then we know the quantities of people in seats are equal.

In more formal language, suppose that you have a mapping from people-- that's the input set-- to seats-- that's the output set-- such that different inputs correspond to different outputs, which means no two people in the same seat.

Mathematicians call this an injection.

Now, if in addition, every element of the output set gets something mapped onto it, i.e., if every seat ends up with a person sitting in it, then we say that the map is onto, or surjective.

Now, if the map is not onto, like when some seats ended up empty, then the cardinality of people, the input, is less than the cardinality of the seats.

But if the math is onto, which means no empty seats, then the map is a full-fledged one-to-one correspondence, also known as a bijection between the input and output sets, and the cardinalities of those sets have to be the same.

Now, notice in particular that if a set A is a subset of a set B, then A's cardinality has to be less than or equal to B's, since you can for sure inject A into B just by mapping each element of A to itself.

It's good to note that these comparison rules are just motivated by what we know about the behavior of finite sets.

And we're just stipulating obedience to these rules as a constraint on whatever ultimate definition we end up devising for cardinalities.

So armed with these tools and terminology, let's make some observations.

Notice that the size of the natural numbers has to be strictly greater than that of any finite set.

How come?

Because you can map each element of a finite set to a distinct natural number.

In other words, you can inject a finite set into the naturals.

But you will always have naturals left over when you do so.

The injection is not onto.

The cardinality of the natural numbers abbreviated with the symbol aleph-naught turns out to be the least infinite cardinality.

And yeah, I know some people pronounce this aleph-null.

I don't do that.

"To-may-to, to-mah-to."

There are also clever arguments due to Cantor that have been covered elsewhere on YouTube showing that the sizes of the even natural numbers, the odds, all the integers, the rational numbers, and even algebraic irrationals like the square root of 2 that all of those sets are equal in size to aleph-naught, even though the cardinality of the real numbers turns out to be greater than aleph-naught.

That's all fun stuff, but I want to focus on something more narrow today, namely how the cardinality of a set A compares to that of its power set.

The power set of A, which I'll denote P of A, is the set of all subsets of A, including A itself.

So for example, if A is a set that has three elements called x, y, and z, then its power set will consist of the following 2 to the third, or 8, subsets of it.

Now, if you play with a couple of more examples like this and if you take cardinality of finite sets just to mean quantity in the ordinary sense of the word, it becomes pretty clear that the cardinality of the power set is just 2 raised to the power of the cardinality of the original set.

Fine.

What's really cool is that even without explicitly defining cardinality for infinite sets, you can still show that the cardinality of the power set of A must be strictly greater than the cardinality of the original set A, even when it's infinite.

Now, for finite sets, that relation is obviously true.

We just showed it.

But to prove it for infinite sets, we're going to use a beautiful argument that was first made back in the day by Cantor.

I'm going to go through this in two stages.

The first thing to do is to show that the size of the set A has to be less than or equal to the size of its power set.

In order to do that, we just need to find a function that maps each element of A to a distinct subset of A, since, remember, the subsets of A are the elements of the power set, i.e., that's the output set in this case.

All right, how about a function that just maps each element of A to the subset of A containing only that element?

That operation definitely sends each element of A to a distinct element of the power set so that according to our comparison rules, the cardinality of the power set has to be at least the same as the cardinality of A.

Now for the second step, we'll show that equal size is not an option, namely that no function G from A to its power is onto.

There will always be leftovers in the power set.

Remember, inputs to G are elements of A, and the outputs of G are whole subsets of A.

So for instance, G might map this element to this subset or that element to that subset.

Fine.

Now consider a particular subset of A, namely the subset of elements, none of which are members of the subset that they get mapped to by G. Let's call this subset B.

To illustrate, suppose that element y is in B.

Then the G operation can't map y to this subset because y is part of that subset.

And it can't map y to B because y is also part of that subset.

But it could map y to this other subset that y isn't a part of.

OK, now I claim that the subset B will never be the output of G. Why?

Because what input would produce it?

I mean, we just saw that elements like y that are in B can't get mapped to B because of how we define B.

But what about an element like w that isn't in B?

Well, since w isn't in B, then w has to be an element of whatever subset G maps W to.

So G has to map W to a subset like this or like this, but it can map w to B because w isn't in B.

So the bottom line is that G can't map anything in B 2 B or anything that's not in B to B, which means B is never the output of the map G. But we didn't specify what rule G was, and our argument didn't depend on assuming that the set A was infinite versus finite, which means there's at least one subset of A, namely B, that no function that maps elements to subsets ever outputs, which means there's at least one element of the power set, B, that can never be spit out by such functions so that no mappings from A to its power set can ever be onto.

But that means there's no bijections between A and P of A, which means their sizes can't be equal.

Now, since we already saw that the size of A is less than or equal to that of P of A, the only remaining possibility is that the cardinality of P of A is strictly greater than that of A.

Boom.

So armed with this theorem, I want to consider the following specific never ending chain of infinite sets.

Let's start with the natural numbers N followed by the power set of N, and then the power set of that power set, and so forth.

Each link in this chain will have a cardinality that is strictly greater than that of all the previous ones, according to our theorem, which means there is no largest infinite size.

But there's something else interesting.

It looks like you can match up this list one to one with the naturals, which means that the cardinality of the totality of these cardinalities of that list is just aleph-naught.

And that's interesting, because is this list of infinite cardinalities complete?

If so, then the size of all infinities would be aleph-naught.

Alas, that's not the case, and here's why.

Let's go back to the original list of sets, not the sizes, the sets.

And let's form their union U.

In other words, I want to take all the elements of the set N, all the elements from the set P of N, and from P of P of N, et cetera, and I want to aggregate all those elements into one big set U.

Now, there has to be an injective map from any of the power sets in the chain into U.

Just send each element of that power set to its clone in U.

That means that the cardinality of U has to be greater than or equal to the cardinality of any of the power sets that were in the chain.

But now think about the power set of U itself.

That's also an infinite set.

So by our earlier theorem, the cardinality of that has to be strictly greater than the cardinality of U, which means by extension, it's greater than the cardinality of any of the original sets in our chain.

And that means that there's at least one infinite cardinality-- the size of the power set of U-- that our original list missed, which means that list wasn't complete, and that the cardinality of the true collection C of all infinite cardinalities, whatever that is, has to be greater than aleph-naught.

OK, so let's just push the question forward.

What's the cardinality of this true collection of all infinite cardinalities?

I'm not asking the size of the collection of the underlying sets, mind you.

I'm asking about the size of the collection of the sizes.

Let's just repeat our argument.

For every cardinality in that collection, let's pick some actual set A that happens to have that size.

And let's form the union U of those sets.

Now, the infinite cardinality of U has to be at least as great as that of any of the A's that we union together to make it, which means, once again, the cardinality of the power set of U will be strictly greater than all of those cardinalities.

But wait a minute.

The sizes of all the A's that we union together was supposed to be the totality of all infinite sizes.

And that means that the size of the power set of U, which is an infinite set, so that's some infinite size, that was supposed to be one of the things in that totality.

So we have a problem.

The size of the totality of all infinite sizes is somehow greater than itself.

That sounds highly problematic.

Reminiscent of something similar to Russell's paradox, but with a little bit of a different flavor.

We seem to have hit a bit of a logical snag, so let's recap the facts that we know.

Apparently, some infinite sets are bigger than others because some infinite cardinalities are larger than others.

Given any infinite set, you can always construct one of greater cardinality just by forming its power set over and over.

We showed that there have to be infinite sets that have even larger cardinalities than any of those.

But then when we ask, OK, how many infinite cardinalities are there altogether, the answer that we get back is nonsense, a contradiction.

Ruh-roh.

What just happened?

Did we encounter a logical problem with infinity itself, or is the size of all infinite sizes actually just meaningless, or did we do something else terribly wrong?

We're going to talk about all this the next time I see you, and maybe clarify what exactly cardinality is a little more carefully.

But in the meantime, I encourage you to go through the argument here again to see if you can figure out what's going on because it's subtle.