Not all infinite sets are the same size; and you can prove it mathematically!
The nicest way that I’ve heard this explained is Georg Cantor’s diagonalization argument. Here is my layman’s attempt to summarise it:
- Imagine you have a pen and an infinitely long piece of lined paper, and you write down every natural number, one per line.
- Now, next to each natural number, you write down a real number in the 0-1 range. Imagine you do this an infinite number of times, until you have written a different real number next to each natural number.
The question posed by Cantor is as follows: when you are finished writing down all of these numbers, would you expect there to be a 1:1 correspondence between the natural numbers and the real numbers? Or, to put it differently, would your piece of paper contain every single natural number, and every real number in the 0-1 range?
You might think that the answer would be yes. I certainly did; I thought the set of natural numbers would match up 1:1 with the set of real numbers, given that there are an infinite number of each.
This is intuitive. It is also wrong!
Cantor’s argument tells us how it is in fact possible to construct a new real number in the 0-1 range:
- Take the first digit after the decimal place of the first natural number on your piece of paper, and increment it by 1 (and if the digit is 9, change it to 0 instead). The new digit will form the start of the new number that you are about to construct a. For example, if you had written down 6.249, it would become 6.349. Similarly, 4.3 would become 4.4; 9.00041 would become 9.10041; and 4.91 would become 4.01
- Now take the second digit after the decimal place of the second natural number on your paper, and do the same; increment it by 1, or change it to 0 if it is a 9. This digit will form the second decimal place in your newly constructed number
- Repeat this process for the third post-decimal digit of the third number in your list, and follow the pattern for each subsequent number in your list until you’ve done it for all of them
Finally, write down a new (infinitely long) number consisting of each new decimal from steps 1-3. This number is guaranteed to differ from every single original number on your piece of paper by the digit that you incremented.
Congratulations; you have just proved that the infinite set of real numbers between 0-1 is larger than the infinite set of natural numbers. I find this quite amazing!