I haven’t had the need to read up on mathematical text for a long time. When I do find time to do so, I am usually impressed by the inexplicable beauty in the ideas presented. The following is my summary on the topic of set cardinality. I only assume that the reader understands elementary mathematical notation and vocabulary and nothing more.

Cardinality as an equivalence class

Back in school, we are told that |A| is the number of elements in A. This is fine until we start to think about the cardinalities of infinite sets. For example, the set of even numbers has the same cardinality as the set of natural numbers. Imagine someone coming up to you with a set and says, if you skip every other element in that set, you have a set with the same “size”. So size doesn’t mean much for infinite sets.

Let’s take a step back and think about what a number is. When we group together certain sets of things (3 iPhones, 3 books, etc.), we conceive of 3 as the thing common to all such sets. We are saying that any two of these sets can be matched up via a bijection. In fact, we could be concrete and define |X| to be the equivalence class of all sets whose cardinality is the same as that of X.

Hence, we say |A| = |B| if and only if there exists a bijection from A -> B.

Definitions and theorems

Let’s start with some definitions:

Countably infinite: |A| = |N|
Uncountable: if A is infinite and |N| =/= |A|
The cardinality of |N| is known as N_0 (pronounced ˈɑːlɛf)

Rather than working from first principles all the time, we can have some nice shortcuts.

Theorem: A set is countably infinite if and only if its elements can be arranged in an infinite list a0, a1, …

This means that whether a set is countably infinite or not depends on whether you are smart enough to come up with a way to list them. So go on and find a way to list the rational numbers because…

Theorem: The set Q of rational numbers is countably infinite.

If you are lazy, here is a proof without words to list elements of the set Q.

Theorem: The set R is uncountable.

Georg Cantor came up with a proof that uses the famous diagonalization argument. It goes like this:

Suppose for the sake of contradiction R is countably infinite. Then we can list them. List each number down a column and align their decimal point. Our goal is to construct the number 0.abcdef... and show that is does not belong to the list which supposedly contains all real numbers.

Choose a = 0 if the the first digit after the decimal of the first number is not 0, and choose a = 1 if it is. Similarly, choose b = 0 if the second digit after the decimal of the second number is not 0, and b = 1 if it is. Now for the aha moment. This number that we have constructed by going down diagonally in the list could not have appeared in this list, because it differs from every number in the list by at least one digit. So no bijection exists, and by definition, |R| is uncountable.

Theorem: |R| = |(0,1)|

Yet another proof without words. Try to unrevel the bijection.

Comparing cardinalities

We now know how to show |A| = |B|. What about |A| < |B|? We can prove that by showing that there is an injection A -> B but no surjection A -> B. Let’s put that to use and show that …

Theorem: Let A be any set, then |A| < |P(A)| where P(A) is the power set of A.

To show the injection A -> P(A), let’s construct one. Take an element in A, call it a, and make it a set, {a} which clearly belongs in P(A).

To show that there is no surjection, let’s borrow ideas from Russell’s well known paradox. Assume on the contrary that there is a surjection f. i.e. every subset of A has a preimage in A under f. Consider the following element in P(A)

$$ \{ x | x \notin f(x) \} $$

By our assumption, there is a corresponding element a that maps to this under f. a either belongs to the set or not. Suppose it does, then by definition of that set, a does not belong to f(a). That’s a contradiction! Suppose it is not, then by definition again, a belongs to the set f(a). Contradiction! This means that there is no such a, so f is not surjective.

Now we have come up with a method to construct an infinite chain of infinities:

$$|N| < |P(N)| < |P(P(N))| < …$$

Proving bijections via Cantor-Bernstein-Schroeder theorem

From the above example, we can see that injections are easier to find, and surjections can be somewhat cumbersome to prove. Recall that earlier, to show that the cardinalities of two sets are the same, we have to show that there exist an injection and surjection. If an injection from A to B implies that |A| <= |B|, then maybe if we can also find an injection from B to A that implies |B| <= |A|, then maybe |A| = |B|. Turns out this is actually true!

Theorem: If there is an injection A->B and an injection B->A then |A| = |B|.

The proof is more elaborate and the interested reader can look it up.

Let’s try to show R and P(N) have the same cardinality using this technique.

Injection R -> P(N). Let’s first use a known result |R| = |(0,1)|. Next, we want to find an injection from |(0,1)| into P(N). Map 0.abcd… -> {a * 10, b ** 100, c * 1000, …}.

Injection P(N) -> R. construct the number 0.abcdef… by setting a = 0 if 1 is in x and 0 if is not.

Since we have two injections, we know |R| = |P(N)|.

Continuum hypothesis

We now know that |N| < |R| but is there any set between |N| and |R|? The continuum hypothesis asserts that there is no such set.

Before we go further, we need to understand that Mathematics is like playing with Lego blocks. One starts with a set of basic blocks, and then builds complex structures by combining blocks based on some rules. In set theory, those basic blocks are axioms, and the collection of axioms mathematicians have settled upon is called Zermelo-Fraenkel axioms (ZF). This covers what can and cannot be regarded as a set to prevent paradoxes.

In 1931, the logician Kurt Godel proved that for any sufficiently strong and consistent axiomatic system, there exist statements which can neither be proved nor disproved within the system. He then proved that the negation of the continuum hypothesis cannot be proved within the ZF axioms.

Either the continuum hypothesis is false and cannot be proven false, or it is true.

In 1964, Paul Cohen proved an even stronger statement: the continuum hypothesis cannot be proven given the laws of logic and the axioms of set theory.

But what do we do with a statement, which has a truth value, but is proved to be unprovable? We are free to accept it either way! It is akin to having two different set of Lego blocks, and both can be used to build complex structures. Fortunately, for the most of us, this will not affect the day to day mathematical results. So pick a side and be proud of it!

Conclusion

By now you should be able to explain what the continuum hypothesis is about at your next party!