# Why Doesn't Cantor's Diagonal Argument Also Apply to Natural Numbers?

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!

-
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. – bo1024 Apr 26 '11 at 1:11

## 3 Answers

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

-

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

-

Why can an infinite list of 0's and 1's not present a natural number? Because it does not suite us?

Suppose we code a natural number n and from the kth position, only 0's will show up. Then n<2^k, so n is limited. But if you think that you can have an infinite set of natural number, than you allow code sequences with infinite length which do not end in only 0's (otherwise they were finite).

-

1
Huh?${}{}{}{}{}$ – Asaf Karagila Apr 26 at 19:17
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 9, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9353590607643127, "perplexity_flag": "head"}