One of the consequences of the Cantor’s Theorem is that . To prove this inequality we need to show that there cannot be a one-to-one correspondence between them. We would argue by contradiction, assuming that they are in fact the same size, and try to reach a contradiction along the way; that is, we will assume first that are equivalent.

What exactly does this mean?
From previous cases, we showed that there is a one-to-one correspondence if there is a bijective function from to This means that we can list all the real numbers in a singly-infinite list.

If one would use geometric argument, one can actually show that the interval (0,1) and the set are equinumerous. We presume that there really is an infinite list containing every real number in the interval (0,1).

Our next issue: what does it really mean to list a particular real number?

Writing down real number with decimal expansion is a big problem since in some way “most” real numbers between (0, 1) have infinitely long decimal expansion. And another unintuitive problem is that decimal expanded real numbers are not unique. For instance, there is really no difference between the finite expansion 0.5 and the infinitely long expansion .

How do we solve this non-uniqueness?

---

We are going to write the base-2 expansions of the real numbers in our list. So instead of writing something like and we are going to write

Special features of our binary version:

1. Every binary expansion corresponds to a unique real number
2. Every real number has a non-unique binary expansion, there are sometimes two different binary expansions that corresponds to the same real number

This representation conversion is simply not surjective. Whenever two different binary expansions represent the same real number, one of them is terminating expansions (it ends in infinitely many 0’s) and the other is an infinite expansion (it ends in infinitely many 1’s).

The gist of the argument is a proof by contradiction.

source

Instead of showing that the set of reals in (0,1) can’t be put in one-to-one correspondence with , what we’re going to do is show that their binary expansions can’t be put in one-to-one correspondence with We’ve seen that there is an infinite number of reals that can have two binary expansions.

Consider the listing of all the elements of the set of all possible infinitely-long binary sequences , then we would have an infinite list of things, in which each of this thing is an infinite list of 0’s and 1’s.

So what??

Cantor Diagonalization argument

---

What we’ve been edging towards, the listing of binary representation, is known as Cantor’s diagonalization argument. This listing looks like an enormous table of binary digits and the contradiction is deduced by looking at the diagonal of this infinite-by-infinite table.

diagonalization argument [CC BY-SA 3.0]

The diagonal in itself can be considered as another infinitely long binary string. If we take the complement (convert 0 to 1s and 1 to 0s) of these diagonal we will also have a string that is infinitely long that can’t be one of the ones in the list!
We started with a presumption that we can list all possible infinitely-long binary sequences, but then with the infinite-by-infinite table, we saw some infinitely, long string that could not be on the list! This is a contradiction.
'

What we’ve done is generally known as diagonal arguments. Diagonal arguments have been used to settle several important mathematical questions.

Cantor’s Theorem

---

If A is any set, and is its power set then . That is,

Cantor’s theorem guarantees that there is an infinite hierarchy of infinite cardinal numbers. People have sought a construction that, given an infinite set, could be used to create a strictly larger set.
Let’s look at the Cartesian product.

When our set is finite, is strictly bigger than . However, if is infinite this is not the case. The important message of Cantor’s theorem is that taking the power set of a set does create a set of larger cardinality, giving us an infinite tower of infinite cardinalities, starting with

Example:

Consider the following set, A = {x,y,z}. The power set of A is given by {{x,y,z},{x,y}{x,z},{y,z},{x},{y},{z},0}, consists of A, 3 singleton, 3 2-set combinations of the elements of A, and of course the null set.

CC BY-SA 3.0

It is easy to see that the cardinality of A is 3, while the cardinality of the power set of A, is 8 (2^3) (check this section why 2^3). This is a simple demonstration of Cantor’s theorem that .

Implications of Cantors Theorem

---

It has a tremendous importance in the field philosophy of mathematics. The power set of an infinite set makes a set that is larger from the starting point, this implies that there is no maximum cardinal number. This means that there is no largest infinity. ^[1]

Cantor’s theorem is closely related to Russel’s paradox. There's another mathematician who's using Cantor theorem to argue that the set of all truths does not exist.^[2]

^{Disclaimer: this is a summary of section 8.3 from the book A Gentle Introduction to the Art of Mathematics: by Joe Fields, the content apart from rephrasing is identical, most of the equations are screenshots of the book and the same examples are treated.}

1. A Gentle Introduction to the Art of Mathematics by Joe Field

---

Thank you for reading ...