12
$\begingroup$

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:

  1. 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.

  2. 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?

$\endgroup$
  • 10
    $\begingroup$ Ask your friend where 1/3 and $1/\sqrt 2$ appear on his list. $\endgroup$ – DanielWainfleet Nov 5 '15 at 2:40
  • 1
    $\begingroup$ The method does not provide a bijection from $\mathbb{N}$ to the real interval $[0,1]$. Every natural number indeed has an image in $[0,1]$, but not every real number in $[0,1]$ has a pre-image in $\mathbb{N}$. For example, what natural number corresponds to the real number $\frac{\pi}{10}=0.314159265...$? You're excluding infinitely many real numbers! $\endgroup$ – Corellian Nov 5 '15 at 2:40
  • 2
    $\begingroup$ Cantor's proof can't result in a one-digit number, but that's why it is a diagonal proof. It is certainly possible to list all numbers that have finite decimal digits, as your friend has noticed. You need all the digits to get a larger infinity. $\endgroup$ – Thomas Andrews Nov 5 '15 at 2:43
  • 2
    $\begingroup$ Tell your friend to avoid becoming a Cantor Crank. Cantor is right and one needs to understand Cantor's proof before trying to come up with a "list of real number". $\endgroup$ – cr001 Nov 5 '15 at 2:44
  • 9
    $\begingroup$ Too early to think about anybody being a crank, @cr001. Lots of us had confusion the first time we encountered Cantor, for a variety of reasons. $\endgroup$ – Thomas Andrews Nov 5 '15 at 2:47
17
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ While I agree with the sentiment saying "almost all" seems ill advised. In terms of cardinality the size of the sets is the same obviously and there is even an extremely natural bijection when one thinks about the sets in terms of decimal expansions. I suppose you can think of the types of fractions allowable, in which case any fraction in minimal form where the denominator has a factor distinct from 5 or 2 is uncovered, but that still abuses the notion of almost all in my opinion. $\endgroup$ – DRF Nov 5 '15 at 9:15
  • 1
    $\begingroup$ @DRF 'Almost all' has a well-defined meaning (or rather meanings – depending on a field of mathematics), and Théophile used it correctly. See en.wikipedia.org/wiki/Almost_all for more info. $\endgroup$ – CiaPan Nov 5 '15 at 9:17
  • 1
    $\begingroup$ @CiaPan Yes I know that almost all has a well defined meaning which is exactly why I disagree. In the way he presents the claim none of the standard definitions work. You could argue for the Number theoretic version but then you have to give some encoding for rationals in integers first for that approach to make sense. (And you can certainly create an encoding for which you don't get almost all). $\endgroup$ – DRF Nov 5 '15 at 9:22
  • 2
    $\begingroup$ @DRF Fix a denominator $N$. What is the probability that $a/N$ terminates, for a randomly chosen $a \in [1,N]$? What happens as $N \to \infty$? $\endgroup$ – Théophile Nov 5 '15 at 17:47
  • 1
    $\begingroup$ @DRF I apologize. I had little time when I wrote my comment, so I was aiming for brevity, not for condescension. The limit I mentioned indeed does not exist; what I meant to write was this: Fix $N$, then choose a denominator $b \in [1,N]$ and a numerator $a \in [1,b]$. Then the probability that $a/b$ terminates approaches $0$ as $N \to \infty$. There are two natural ways to choose $a$ and $b$, either by choosing $b$ uniformly and then $a$ next, or by choosing $(a,b)$ uniformly from legal pairs. In both cases, the probability approaches $0$, and it seems to me that this justifies "almost all". $\endgroup$ – Théophile Nov 8 '15 at 17:22
2
$\begingroup$

(Migrated from the comments.)

Since you only have terminating decimals, you could just as well end each of them with an infinite string of zeroes. This does not change the value of any of the numbers that you had included, so if you had them all, then you will still have them all!

(For example: $0.31$ would become $0.31000\ldots$)

Once you have re-written the numbers as above, you can essentially apply Cantor's diagonal argument to these decimal representations to produce a number that is not found in your list.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.