My friend and I were discussing infinity and stuff about it and ran into some disagreements regarding countable and uncountable infinity.
As far as I understand, the list of all natural numbers is countably infinite and the list of reals between 0 and 1 is uncountably infinite. Cantor's diagonal proof shows how even a theoretically complete list of reals between 0 and 1 would not contain some numbers.
My friend understood the concept, but disagreed with the conclusion. He said you can assign every real between 0 and 1 to a natural number, by listing them like so:
0, .1, .2, .3, .4, .5, .6, .7, .8, .9, .01, .11, .21, .31, .41, .51, .61, .71, .81, .91, .02…
Basically, take any natural number, reverse it, and put a decimal place at the beginning, and the result is the real at that index position. For instance, the real at index 628 is 0.826, and the real at index 1000 is 0.0001. This way, each natural number is paired with a real. Therefore, there are the same amount of real numbers in [0,1] as there are natural numbers.
It made sense to me at first, but we came up with two issues:
-
It appears that there is still no way to list ALL real numbers using this method, and thus the two types of infinity are still separate.
-
If you try to use Cantor's diagonal proof to generate a one-digit number not on the list, you can't because the first ten numbers on the list cover every one-digit possibility. If you use it to generate a two-digit number, you can't because the first 100 numbers on the list cover all possibilities. As you try to generate an N-digit number, you need 10^N numbers on the list to cover every possibility. Since N grows constantly but 10^N grows exponentially, I feel like it wouldn't work as you approach infinity.
We're obviously not math experts, so we're trying to seek out those who know more about the topic.
What is the accuracy of either of our claims, and why?
Best Answer
Your friend's method fails immediately for any number whose decimal expansion does not terminate. What is the index of $\pi $? For that matter, what is the index of $\frac13=0.333...$? In this sense, your friend's method fails for almost all rationals even.