67
$\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.

$\endgroup$
5
  • $\begingroup$ If you try the diagonal argument on any ordering of the natural numbers, after every step of the process, your diagonal number (that's supposed to be not a natural number) is in fact a natural number. Also, the binary representation of the natural numbers terminates, whereas binary representations of real numbers do no. That's the basics for why the proof doesn't work. $\endgroup$
    – Michael Chen
    Commented Apr 26, 2011 at 0:36
  • 2
    $\begingroup$ I don't think these arguments are sufficient though. For a) your diagonal number is a natural number, but is not in your set of rationals. For b), binary reps of the natural numbers do not terminate leftward, and diagonalization arguments work for real numbers between zero and one, which do terminate to the left. $\endgroup$
    – usul
    Commented Apr 26, 2011 at 1:11
  • 1
    $\begingroup$ I upvote this question because I had it too, despite I do not understand why do we need to stack at binary strings, since the method is normally demonstrated with decimal expansion. It is extra unnecessary requirement, IMO. $\endgroup$
    – Val
    Commented Aug 15, 2013 at 17:17
  • $\begingroup$ @Gaurang: Capitalizing every (or most) word in a title is a matter of style and taste. $\endgroup$
    – Asaf Karagila ♦
    Commented Sep 2, 2018 at 12:09
  • 1
    $\begingroup$ @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 - seems to be to use Sentence casing instead of Capital Case. It's fine though - I won't make such an edit again :/ $\endgroup$
    – Gaurang Tandon
    Commented Sep 2, 2018 at 12:32

2 Answers 2

Reset to default
49
$\begingroup$

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

$\endgroup$
12
  • 2
    $\begingroup$ I was thinking about your first paragraph... what if you reordered the natural numbers such that the diagonal wasn't straight zeroes? $\endgroup$
    – Michael Chen
    Commented Apr 26, 2011 at 0:45
  • 2
    $\begingroup$ You'd actually need the diagonal part to be identically 1 for digits large enough. If you have infinitely many zeros on the diagonal, then you still don't get a natural number. You'd need all but finitely many of the diagonals to be 1. But you can see that isn't possible, because if the $n$th binary digit of a number is 1, then that number is at least $2^n$. $\endgroup$
    – Thomas Andrews
    Commented Apr 26, 2011 at 0:57
  • 3
    $\begingroup$ @Michael: I don't mean that all entries will necessarily be $1$, but there will necessarily be infinitely many $1$s. $\endgroup$
    – Matt E
    Commented Apr 26, 2011 at 0:58
  • 2
    $\begingroup$ @b01024: but then since you have an enumerated list, you have to state where the numbers in between fall. The crux is that you can't have 1's everywhere on the diagonal, for then you have no place to put 1, 3, 5, 6, 7, etc. $\endgroup$
    – Michael Chen
    Commented Apr 26, 2011 at 1:23
  • 4
    $\begingroup$ @b01024: You should take a look at the theory of ordinals numbers (en.wikipedia.org/wiki/Ordinal_number). When you say "all powers of two first, increasing, then the rest of them", this can be made precise using ordinals, but the ordinal you get is not that of the natural numbers. To have a "list" in the sense of an enumeration to prove countability, the list has to be in bijection to the natural numbers; you can't have an infinite list of all powers of $2$ and then start over with other numbers; that doesn't assign the other numbers any well-defined index in the list. $\endgroup$
    – joriki
    Commented Apr 26, 2011 at 4:49
30
$\begingroup$

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.

$\endgroup$
2
  • 7
    $\begingroup$ 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! $\endgroup$
    – Ken Bellows
    Commented Aug 1, 2016 at 16:53
  • 3
    $\begingroup$ A number with infinite leading 1s is not a nature number. That explains it very nicely! $\endgroup$
    – Xi Wei
    Commented Dec 28, 2019 at 0:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .