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 is a contradiction.


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

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

Source : Link , Question Author : usul , Answer Author : Matt E

Leave a Comment