Cantor's diagonal trick proves some infinities are bigger than others
Imagine someone claims to have listed every endless string of 0s and 1s. Build a new string by flipping the first digit of the first entry, the second digit of the second, and so on down the diagonal. Your string differs from every line of the list, so the list was never complete.
Georg Cantor published this argument in 1891. The idea is disarmingly short. Suppose the set of all infinite binary sequences could be counted, meaning paired off one-to-one with the natural numbers 1, 2, 3 and onward. Then its members could be written in an ordered list. Construct a sequence whose nth digit is the opposite of the nth digit of the nth entry. It belongs to the set, yet it disagrees with every entry somewhere, so it cannot appear on the list. The assumption collapses, and the set is uncountable: there is no way to number its elements, even with infinitely many counting numbers available.
Because binary sequences can be matched with real numbers, the same conclusion applies to the reals. There are, in a precise sense, more points on a line than there are whole numbers, even though both collections are infinite. Oddly, this was not Cantor's first proof of that fact; he had shown it by a different route back in 1874. The diagonal version became famous because its technique travels so well.
Cantor himself stretched it into a general theorem: for any set whatsoever, the collection of all its subsets is strictly larger than the set. No function from a set to its subsets can reach every subset, because one can always define the subset of elements not contained in their own image, which no element maps onto. That yields an endless ladder of ever larger infinities, the subject of the theory of cardinal numbers he founded.
The same self-referential twist powers some of the deepest results of the twentieth century, among them Gödel's first incompleteness theorem and Alan Turing's answer to the decision problem. It also sits behind paradoxes such as Russell's and Richard's, where diagonal reasoning produces contradictions instead of proofs.
Source: Cantor's diagonal argument
