The Unexpected Diagonal — Cantor's Proof

Cantor's diagonal proof: assume a complete list exists. Build D by changing the nth digit of the nth listed number. D is a real not on the list — contradiction. Therefore no complete listing of reals exists. The reals are uncountably infinite, strictly larger than the countably infinite natural numbers. WOW Moment: - Natural numbers: 1, 2, 3, 4, ... -> countably infinite (aleph-null). - Real numbers in (0,1): uncountably infinite (aleph-one). - Aleph-one > aleph-null. Some infinities are bigger than others. - There are infinitely many different sizes of infinity. Cantor proved this too. - Georg Cantor's contemporaries thought he was insane. Henri Poincaré called set theory 'a disease.' Cantor suffered severe depression and died in a sanatorium. Today, Cantor's work is the foundation of modern mathematics. - The man who proved infinity comes in different sizes was destroyed by the mathematics community for doing so. He was right.

Georg Cantor's diagonal argument (published in 1891) is a masterpiece of mathematical proof. It uses a proof by contradiction (reductio ad absurdum) to show that the infinity of the real numbers is strictly larger than the infinity of the natural numbers. The Proof: 1. Assume, for the sake of contradiction, that the set of all real numbers in the interval (0, 1) is countable. This means we can list them in a sequence: r1, r2, r3, r4, ... 2. We can write each of these real numbers in its infinite decimal expansion: r1 = 0. d11 d12 d13 d14 ... r2 = 0. d21 d22 d23 d24 ... r3 = 0. d31 d32 d33 d34 ... r4 = 0. d41 d42 d43 d44 ... where dij represents the jth decimal digit of the ith number in our list. 3. Now, we construct a new real number D = 0. x1 x2 x3 x4 ... by defining its digits as follows: - For the first digit x1: choose a digit that is different from d11 (e.g., if d11 = 5, set x1 = 6; otherwise set x1 = 5). - For the second digit x2: choose a digit different from d22. - For the nth digit xn: choose a digit different from dnn. 4. Is D a valid real number in the interval (0, 1)? Yes, it is an infinite decimal. 5. Is D on our list? - D cannot be r1, because they differ in the first decimal digit (x1 ≠ d11). - D cannot be r2, because they differ in the second decimal digit (x2 ≠ d22). - In general, D cannot be rn for any n, because they differ in the nth decimal digit (xn ≠ dnn). 6. Therefore, D is a real number in (0, 1) that is *not* on our list. 7. This contradicts our assumption that our list contained *all* real numbers in (0, 1). 8. Thus, the assumption must be false. The real numbers in (0, 1) cannot be listed. They are uncountable. To explain the WOW part: This proof shows that infinity is not a single, monolithic concept. There are different "orders" of infinity. The infinity of the counting numbers is called aleph-null (ℵ₀). The infinity of the real numbers is a strictly larger infinity, called the cardinality of the continuum (𝔠 or ℵ₁). Cantor went on to prove that you can take the power set of any infinite set to get an even larger infinity, meaning there is an infinite hierarchy of larger and larger infinities (ℵ₀ < ℵ₁ < ℵ₂ < ...), going on forever. This beautiful and daring idea was so revolutionary that it faced intense hostility from his contemporaries, leading to Cantor's mental breakdowns. Today, it is celebrated as one of the greatest achievements in human thought.