37
$\begingroup$

In my understanding of Cantor's diagonal argument, we start by representing each of a set of real numbers as an infinite bit string.

My question is: why can't we begin by representing each natural number as an infinite bit string? So that 0 = 00000000000..., 9 = 1001000000..., 255 = 111111110000000...., and so on.

If we could, then the diagonal argument would imply that there is a natural number not in the natural numbers, which is a contradiction.

  • 0
    @AsafKaragila I agree. I was mainly focused on removing the thanks. I have an automated capitalization corrector setup, so I just used it. I agree with you it's a matter of taste but the general tradition - if you looked at the [highest voted questions](https://math.stackexchange.com/questions?sort=votes) - seems to be to use Sentence casing instead of Capital Case. It's fine though - I won't make such an edit again :/2018-09-02

2 Answers 2

40

If you represent a natural number as an infinite string, the string will become identically $0$ after a certain point. If you think it through, the "diagonal argument" in this case doesn't produce a natural number; it will produce a string with infinitely many $1$s.

On the other hand, you can consider possibly infinite binary strings --- i.e. strings in which there can be infinitely many $1$; this is one way to think of the set of $2$-adic numbers, which is indeed an uncountable extension of the set of natural numbers (as one sees using the precise diagonal argument that you suggest).

  • 0
    @ThomasAndrews. This Q from 2011 was edited today, which is why it appeared on my feed. Your comment exposes a fatal flaw in the posted answers (excluding the deleted ones). They do not explain (as you have) why it is impossible for the $n$th digit of the $n$th number to be $1$ for all sufficiently large $n$.2018-09-02
16

The reason is simply that natural numbers have a finite representation. (In set theory, Each one is a finite number of successions from 1, where the successor of n is n+1.) Your representation scheme essentially respects this, since for any natural number (which will be on the list), after some finite number of digits it becomes all zeros. Your diagonal element will either be one of these, and so on the list, or a sequence of ones and zeros which never 'zeros out'. This string is NOT a natural number; it corresponds to nothing in your representation scheme. The reason the diagonal argument works for real numbers is that they do not have a finite representation. In set theory they are represented as the limit of an infinite series.

  • 1
    This here is the easiest way to understand the difference. Natural numbers are countable and reals are not because each natural number has, by definition, finitely many digits, but real numbers do not have this restriction. Thanks!2016-08-01