How many sizes of infinity are there?

“O God, I could be bound in a nutshell, and count myself a king of infinite space – were it not that I have bad dreams.”
Hamlet, Act 2, Scene 2. Lines 252-254.

Recently, a colleague asked me:

I know that there are different sizes of infinity, but what I want to know is how many different sizes of infinity there are?
-Curious Colleague

This is a great question! I tried to explain my answer at the time, but it came out garbled and I think I confused him more than I helped. So this post is an effort to remedy that and answer his question.

The basics

Here are some common things we will need to know:

Cantor’s Theorem. Let X be any set. The cardinality of the power set P(X), is always (strictly) larger than the cardinality of X.

Cantor’s Theorem (injection version). Let X be any set. There is no injection from P(X) into X.

This surprising theorem tells us “there are different sizes of infinity” and even further “no matter how large (in cardinality) a set you have, you can always find a larger (in cardinality) set”.

The standard proof of this uses a self-reference paradox which you can see here:

Definition: If X is a set, then the cardinality of P(X) is denoted by $2^{|X|}$ .

This suggestive notation comes from the finite case.

Set basics

A set is often thought of as an “atomic object” that is the foundation for all other objects. This was the project of logicians in the early 20th century: express all mathematical objects in terms of sets, and describe a small list of “self-evident” rules or axioms that sets respect.

This list of rules is called the ZFC axioms (for the mathematicians Ernst Zermelo, Abraham Fraenkel, and the special axiom of choice.) It contains 10 axioms (or really 8 axioms, and two schema or families of axioms).

Too big to be a set

ZFC is really focused on “small” sets, and doesn’t really give us many tools for working with very large things. Many of the axioms are of the form: If X is a set, then you can construct a new, related set X’. For example, the power set axiom says: If X is a set, then P(X) is a set.

We get into problems when we try to collect all objects of a given type. If these were sets, then they would just be “too big”. So if we really need to reference them, we call them “proper classes“. Here are some examples:

There is no set of all sets.
There is no set of all graphs (or vector spaces, groups, or whatever other algebraic structure you want)
There is no set of all cardinalities.

Proofs of these facts are interesting in their own right, so let me show them.

Photo by Polina Tankilevitch on Pexels.com

Theorem 1. There is no set of all sets.

Proof. Suppose not. Let X be the set of all sets.

Let $R = \{x \in X : x \notin x\}$ . This is a set by the axiom of specification (because X is set, and ‘ $a \notin b$ ‘ is a logical property).

We ask: Is $R \in R$ ?

If yes, then $R \notin R$ , a contradiction.

If no, then $R \in R$ , a contradiction.

Either way we get a contradiction, so the proof is complete.

Notice that the core of this argument is the construction of R. This is “Russel’s set” named after Bertrand Russel. This “paradoxical” set motivated a careful choice of axioms for set theory.

We can easily adapt this to show there is no set of all graphs. (Morally, we show that the two classes are equinumerous, but of course, that notion only holds if they were both sets.)

Theorem 2. There is no set of all graphs.

Proof. Suppose not. Let X be the collection of all graphs. Define the (forgetful) function F that takes in a graph as an input, and outputs the set of vertices that graph uses.

Now the range of this function must be a set (by the axiom of replacement, and using that X is a set), and we can see that the range must in fact be the set of all sets. (Given any set A, we can define the graph A’ with no edges on this set A.)

But Theorem 1 tells us there is no set of all sets.

Finally, we get to what my colleague was looking for.

Theorem 3. There is no set of all cardinalities. (i.e. it is a proper class)

The big idea in this proof is that if it is a set (called C), then we can define |C| which should act like a global max on sizes of infinity since C can see all sizes of infinity. But then Cantor’s theorem (applied to C) breaks that.

Proof. Suppose not. Let C be the set of all cardinalities. (Our goal is to contradict Cantor’s theorem.)

There must be an injection $f: C \to |C|$ . Now, $2^{|C|}$ is a cardinality, so all its elements must also be cardinalities*. Since $C$ is the set of all cardinalities, we must have $2^{|C|} \subseteq C$ . Thus $f$ restricts to an injection from $2^{|C|}$ into $|C|$ .

However, by Cantor’s theorem, there is no injection from $2^{|C|}$ into $|C|$ .

(*: I tried to avoid using this non-obvious fact about cardinalities, but I couldn’t see an easy way around it.)

An interesting thing to notice is that this theorem was a bit harder to prove than Theorems 1 and 2. Morally, Theorem 1 was our “base” result (where we used Russell’s clever idea) and Theorem 2 was an “easier” result than Theorem 1 (because morally there are “more” graphs than sets). However, the class of cardinalities is (morally) “smaller” than the class of all sets. This means we needed a new idea, and couldn’t just use a Russell-type paradox argument.

That being said, if you dig down into the argument we used, you may eventually find a Russell-type paradox buried inside of it.

The basics

Set basics

Too big to be a set

Share this:

Like this:

Related

Leave a Reply Cancel reply