Now for Cantor’s diagonal argument. Cantor showed that the natural numbers and the integers have the same cardinality, and even the natural numbers and the rational numbers. But what about the natural numbers and all the real numbers? Let’s say we wrote down the decimal representation of every single real number and corresponded them with a natural number. Heck, let’s just write down the real numbers between zero and one. A number can have more than one decimal representation, despite what five pages of .999…=1 discussion on Wikipedia will make you think. We can get around that, though. Now number all these numbers, starting from one and not stopping. We have something like this.
a1=0.c1 d1 e1 f1…
a2=0.c2 d2 e2 f2…
a3=0.c3 d3 e3 f3…
…
Now let’s take the nth digit from the nth number. Imagine a number x=0.x1x1x3… and let x1 be any number besides c1, x2 be any digit besides d2, and so on. Now x can’t be a1 because the first digit is different. It also can’t be a2 because the second digit is different. And so on and so on. So congratulations, we’ve found a number that isn’t in our list. This number should be on our list but isn’t. Therefore we’ve found a brand new number, and this number x doesn’t correspond to a natural number on our list. So the set of real numbers has a higher cardinality than the natural numbers.
That’s right. A higher infinity. Now if you really want your brain to hurt, think about the power set of the real numbers.