Georg Cantor’s mind-bending Diagonal argument.

Georg Cantor’s mind-bending Diagonal argument.

The argument itself is remarkably succinct, despite the fact that it constructively establishes the existence of “large infinities.”

We begin by considering the set of all infinite sequences of binary digits, called T.

Cantor’s argument shows that, for any list of these sequences (e.g. above, in black and red), there is always an s (in blue) that does not appear in the list.

To find s, we begin with the elements along the diagonal. We take the sequence of their complements (ones become zeros, zeros become ones) to be the digits of s.

Observe that s cannot appear anywhere on the list, since the nth digit of each s_n differs from that of s (as they are complementary). The first digit of s is different from the first digit of s_1, the second digit of s is different from that of s_2, etc.

No matter how we arrange a list, and no matter how large we make it, we can always find an element of T not on the list.

Even if we let our list contain (countably) infinite[ly] many terms, T contains all the elements of our list and s, so it is larger.

Thus, very loosely, there are infinite sets larger than other ones. 

A major consequence of Cantor’s results is that set of real numbers is “denser” than the integers.

Set theory is otherworldly. Mathematics is beautiful. <3

Do NOT follow this link or you will be banned from the site!