Cantor's diagonal trick proves some infinities are bigger than others
In short: 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.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: Cantor's diagonal argument
To cite this card, link to https://intellectplus.co.uk/app/science-cantor-s-diagonal-argument.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?
Related
More in Basics · More in Science · Latest · A–Z · All topics