How Cantor Proved Real Numbers Are Uncountable
In 1891, mathematician Georg Cantor revolutionized set theory by proving that there are different sizes of infinity. This article provides a clear explanation of Cantor's famous diagonalization argument, demonstrating how he used a proof by contradiction to show that the set of real numbers is "uncountable" and therefore strictly larger than the set of natural numbers. By constructing a single missing number from an assumed complete list of decimals, Cantor proved that it is impossible to put all real numbers into a one-to-one correspondence with whole numbers.
Understanding Countable Infinity
To understand uncountability, you must first understand what makes an infinite set "countable." A set is countably infinite if you can list its elements one by one, pairing each item with a natural number (1, 2, 3, 4, and so on) without missing any.
Even though the natural numbers go on forever, you can count them. Cantor wanted to know if the real numbers—which include all whole numbers, fractions, and irrational numbers with infinite non-repeating decimals—could also be listed in this way.
The Setup: Proof by Contradiction
Cantor used a method called proof by contradiction. To prove that real numbers cannot be listed, he started by assuming that they can be listed.
To simplify the problem, Cantor focused only on the real numbers between 0 and 1, expressed as infinite decimals (for example, 0.5 is written as 0.500000...). If you cannot even list the real numbers between 0 and 1, you certainly cannot list all of them.
Assume a complete, infinite list of every real number between 0 and 1 exists. The start of this hypothetical list might look like this:
- Number 1: 0.492817...
- Number 2: 0.718293...
- Number 3: 0.005432...
- Number 4: 0.987654...
- Number 5: 0.111121...
- Number 6: 0.333338...
The Diagonalization Step
Cantor's goal was to prove this list is incomplete by building a brand-new real number between 0 and 1 that is nowhere on the list.
He did this by looking at the digits along the diagonal of the list—the first digit of the first number, the second digit of the second number, the third digit of the third number, and so on (bolded in the list above).
From the example list, the diagonal digits are:
- 1st digit of Number 1 is 4
- 2nd digit of Number 2 is 1
- 3rd digit of Number 3 is 5
- 4th digit of Number 4 is 6
- 5th digit of Number 5 is 2
- 6th digit of Number 6 is 8
This gives us a number based on the diagonal: 0.415628...
Constructing the Missing Number
Next, Cantor changed every single digit of this extracted diagonal number to create a new number. To keep the math simple and avoid a known mathematical quirk where 0.999... equals 1.000..., we can use a simple rule to change the digits: if a diagonal digit is 1, change it to 2. If the digit is anything other than 1, change it to 1.
Applying this rule to our diagonal digits (4, 1, 5, 6, 2, 8...), our new number becomes:
New Number: 0.121111...
The Contradiction
This newly constructed number is a valid decimal between 0 and 1. Because our original assumption was that the list contained every real number between 0 and 1, this new number must be on the list somewhere.
However, it cannot be on the list:
- It cannot be Number 1, because its first digit is 1, while Number 1's first digit is 4.
- It cannot be Number 2, because its second digit is 2, while Number 2's second digit is 1.
- It cannot be Number 3, because its third digit is 1, while Number 3's third digit is 5.
In fact, it cannot be the n-th number on the list, because by definition, we changed the n-th digit to be different from the n-th number's n-th digit.
The Conclusion
Because this new number differs from every number on the list in at least one decimal place, it is not on the list.
If you try to fix the list by adding this new number to it, you can simply run the diagonalization process again to generate another missing number. Therefore, no matter how you try to construct the list, it will always be incomplete.
This creates a logical contradiction: the list was assumed to be complete, yet it is provably missing a number. Thus, the initial assumption that you can list the real numbers is false. The real numbers cannot be paired one-to-one with the natural numbers, proving they are uncountable.