Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 seems to be a bit of the contradiction....

Thanks!

share|improve this question
    
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. –  Michael Chen Apr 26 '11 at 0:36
1  
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. –  usul Apr 26 '11 at 1:11
    
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. –  Val Aug 15 '13 at 17:17
add comment

2 Answers

up vote 24 down vote accepted

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

share|improve this answer
1  
I was thinking about your first paragraph... what if you reordered the natural numbers such that the diagonal wasn't straight zeroes? –  Michael Chen Apr 26 '11 at 0:45
1  
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$. –  Thomas Andrews Apr 26 '11 at 0:57
1  
@Michael: I don't mean that all entries will necessarily be $1$, but there will necessarily be infinitely many $1$s. –  Matt E Apr 26 '11 at 0:58
1  
@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. –  Michael Chen Apr 26 '11 at 1:23
2  
@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. –  joriki Apr 26 '11 at 4:49
show 4 more comments

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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