Cantor’s Theorem and the Universal Set

Over the past six years I’ve had the pleasure of teaching CS103, one of the core CS classes in the Stanford Computer Science department. The course moves fast – it spends five weeks on discrete mathematics; four weeks on automata, languages, and computability theory; and one week on complexity theory. There are no prerequisites for the course, and so the course effectively functions as a combination of introduction to proofwriting and a quick survey of some of the major results from computability and complexity theory.

In the course of teaching CS103 I’ve curated and developed a bunch of discrete math and CS theory exercises that I give out in a number of problem sets, practice exams, and extra practice problems. I wanted to share a few of my favorite problems from that group here, along with a discussion of why I like those problems so much.

To kick things off, I thought I’d share this problem, which originated as an exam question and has since become a mainstay on the problem sets:

What happens if we take absolutely everything and throw it into a set? If we do, we would get a set called the universal set, which we denote 𝒰:

𝒰 = { x | x exists }

Absolutely everything would belong to this set: 1 ∈ 𝒰, ℕ ∈ 𝒰, philosophy ∈ 𝒰, CS103 ∈ 𝒰, etc. In fact, we’d even have 𝒰 ∈ 𝒰, which is strange but not immediately a problem.

Unfortunately, the set 𝒰 doesn’t actually exist, as its existence would break mathematics.

1. Prove that if A and B are arbitrary sets where AB, then |A| ≤ |B|. (Hint: Look at the Guide to Cantor’s theorem. Formally speaking, if you want to prove that |A| ≤ |B|, what do you need to prove? Your answer should involve defining some sort of function between A and B and proving that function has some specific property or properties.)

2. Using your result from (i), prove that if 𝒰 exists, then |℘(𝒰)| ≤ |𝒰|.

3. Using your result from (ii) and Cantor’s Theorem, prove that 𝒰 does not exist. Feel free to the following fact in the course of writing up your proof: for any sets A and B, if |A| ≤ |B| and |B| ≤ |A|, then |A| = |B|.

The result you’ve proven shows that there is a collection of objects (namely, the collection of  everything that exists) that cannot be put into a set. When this was discovered at the start of the twentieth century, it caused quite a lot of chaos in the math world and led to a reexamination of logical reasoning itself and a more formal definition of what objects can and cannot be gathered into a set. If you’re curious to learn more about what came out of that, take Math 161 (Set Theory) or Phil 159 (Non-Classical Logic).

This problem has a huge “whoa” factor for students. There is something really cool about proving that the very natural, intuitive concept of a set (a set is just a collection of things) somehow doesn’t quite work. I’ve had a lot of students tell me over the years that this result totally blew their minds.

I also really like the pedagogical value of the question. In the lectures leading up to this problem, I formally define the relations $|A| \le |B|$, $|A| < |B|$, and $|A| = |B|$ using injections, surjections, and bijections, then write up a rigorous proof of Cantor’s theorem using those definitions. Part (i) of this problem asks students to prove a result that, in most students’ minds, is probably “obvious,” that if $A \subseteq B$, then $|A| \le |B|$. The intent is to get students to engage with the formal definition of this relation and to find an injection $f : A \to B$. This pushes students to think about what that function might look like, given that there’s basically no information given about what $A$ and $B$ look like.

Part (ii) of the problem asks people to think about what the power set of the universal set 𝒰 looks like and how it related back to 𝒰. This hits on the difference between the element-of relation and the subset-of relation. Most students recognize that $\wp(\mathcal{U}) \in \mathcal{U}$, but it’s a second step to see why $\wp(\mathcal{U}) \subseteq \mathcal{U}$ holds as well. One of the major issues I see students struggle with when they’re just getting started with discrete mathematics is understanding how these two concepts relate to one another, and I’m always looking for more ways to get them to practice this.

Part (iii) of this problem combines everything together and asks students to think about how everything fits together. The real star here is Cantor’s theorem, which sets up a contradiction between $|\wp(\mathcal{U})| \le |\mathcal{U}|$ and $|\mathcal{U}| < |\wp(\mathcal{U})|$.

As an interesting technical aside, the “textbook” way you’d prove that the universal set doesn’t exist doesn’t proceed this way. Typically, you’d Russell’s paradox: use the axiom schema of specification to select from 𝒰 the set $S = \{ x | x \notin x \}$, and then prove that $S \in S$ if and only if $S \notin S$. There’s a diagonal-esque argument involved in Russell’s paradox (looking at objects that don’t contain themselves), which is still present in the proof route here (embedded in the proof of Cantor’s theorem). In fact, if you trace through the formal proof of Cantor’s theorem using the identity function, which is in a sense what this entire problem is all about, you’ll find that it ends up making precisely the same argument that gives rise to the Russell’s paradox contradiction.

I think this particular problem is one that could be adapted for use in other discrete math courses. The major prerequisites here are Cantor’s theorem and the formal definitions of the cardinality relations, which often come up in some form when talking about countable versus uncountable infinities. If you work through this problem, I think you’ll find that it’s actually not all that tricky and that the sticking points students will hit make for really good teaching moments (expanding out formal definitions, defining functions between sets, element-of versus subset-of, etc.).