Clarification about Cantor's Diagonal argument compared to Natural Numbers

Question

I'm not a mathematician but I am a software engineering student. From what I've understood so far, the Cantor diagonal argument proves that the real numbers are infinite and uncountable. My biggest confusion arose from that I thought:

"Why aren't the natural numbers uncountable? They continue forever?" or "What's stopping us from replacing the diagonal numbers with natural numbers, and then creating a new natural number which isn't on the list? How do the two things differ?"

But after a decent amount of thinking, googling, asking and watching videos, what I gathered is that they differ because the 0.000001... will always be a fraction of a number regardless of how long or infinite after the decimal point, whereas the natural numbers will just become illogical strings of numbers.

My question is - is this the logic behind it? Am I missing anything? Please explain in easy to understand ways.

Cantor's Diagonal Argument Image

Answer 1

The diagonal argument Cantor uses to prove the uncountability of the reals cannot be applied to the naturals. That’s because every natural number has but finitely many digits, but the thing produced by the diagonal approach has infinitely many digits, so it cannot be a natural number (let alone a natural number missing from the list).

Besides, the definition of countabilty of a set S does not mean that a person or device can count the elements of S (rattle off the sequence “1, 2, 3, …” while pointing out successive members of S) in a finite time, it requires only that it be possible to associate each element of S with a unique natural number. That’s what’s at the heart of @ThomasAndrews’ comment, because one can simply associate each natural number with itself. Cantor’s argument shows that any way you associate each natural number to a real, there will always be a real that’s left out, that doesn’t receive any natural number.

Answer 2

Cantor's Diagonal Argument is almost always taught incorrectly, in several ways. Some are immaterial; for example, he used it on infinite-length binary strings, not real numbers. It works the same on both, but only one is what Cantor did. But some important steps are glossed over, one is the source of your confusion. Another is a logical mistake that intuitive students will sense, but be told (incorrectly) that their intuition is faulty.

Here is an outline of the argument as Cantor used it, including the correction these flaws. I'll add notes along the way, in parentheses, pointing out the differences between it, and what is usually taught.

First off, "0.123000..." is not a real number, it is an infinite-length string of characters. The decimal representation of a real number in [0,1] is such a string. This becomes significant since "0.5000..." and 0.4999..." are different strings that represent the same real numbers. That's one reason why Cantor used strings.

1. Let T be the set of all infinite-legnth binary strings. (Examples are "0000...", "1111...", and "0101...".)
2. Let S(n) be an infinite list of such strings. (Cantor did not assume that this list included every such string.)
3. Let s0 be a string whose nth character is the opposite character to the nth character of s(n).
4. Show that s0 is an infinite-length binary string, and so must be a member of T. (This is the flaw that bothers you. It is necessary for the proof.)
5. This proves the proposition that any listing of members of T that can exist must be missing the string s0, that we can construct from the listing.
6. From this proposition, it follows immediately that a full listing cannot exist. Otherwise, the string s0 would both be a member of T, but also not be a member of T.

Answer 3

Yes your intuition is right about decimals going 'infinitely after the decimal point' making a difference. The problem with the natural numbers is that every natural number must 'end' whereas decimals do not.

Let's say that you did write out the list of all the natural numbers and tried to use Cantor's diagonal argument. I move along the list switching the $1^{st}$ digit of the $1^{st}$ natural number and the $2^{nd}$ digit of the $2^{nd}$ natural number and so on to create a new number. Since natural numbers can have any number of digits you would like, this new number will never have an 'end' despite every natural number in your list having an 'end'. So the new number that you created will not be a natural number at all, let alone a new one! However, decimals will 'go on forever' which is why you do in fact create a new decimal number in Cantor's diagonal argument.

With regard to your question of 'Why aren't the natural numbers uncountable?', I can try and offer an intuitive answer rather than a mathematically rigorous one. Countable just means you can list them off in a systematic way (1,2,3,4,...) so that you will definitely reach every number at some point. This can be done with the rational numbers (fractions) as well. It does not mean that there have to be finitely many numbers. But try to list off the all the real numbers (decimal numbers). Where do you start? And which number comes next?

Answer 4

Roughly, countable sets can be put in a list.

Of course, any finite set works.

The naturals meet this criterion:

$$1,2,3,4,\dots.$$

None is skipped (they're all there).

Also, $\Bbb Z$ is countable:

$$0,1,-1,2,-2,3,-3,\dots .$$

Cantor's diagonal argument shows that the reals cannot be put in a list. It does this by taking an arbitrary list of real numbers, and showing that there will always be at least one missing.

The very clever trick is to produce such a missing real by changing a digit (along the diagonal) of the decimal representations of the numbers in the list.

Since the constructed number differs from each number in the list, we are done. (Of course, we need to get rid of duplicate decimal representations, like $0.2$ and $0.1\bar9,$ at the outset.)

---

One application is that the countable union of countable sets is countable. To prove it simply arrange them in an infinite array, and wind your way back and forth from the upper left hand corner to put them in a list.

In this connection, see "Cantor's pairing function".

Answer 5

The usual presentation of the diagonal argument takes place on the interval $(0,1)$ (we later construct a bijection from $(0,1)$ to $\mathbb{R}$, like $x\mapsto\tan(\pi x-\pi/2)$). The crucial part of the argument is that, given a number $0.a_1a_2a_3...\in(0,1)$ (and all numbers from this interval are of this form), where $a_i\in\{0,1,2,...,9\},\forall i\in\mathbb{N}$, if $f(n)=x_n$, where $f$ is our supposed bijection from $\mathbb{N}$ to $(0,1)$, then we can construct a number $y=0.b_1b_2b_3...$ by making $b_n$ different than $c_{nn}$ (and preferably different than $9$), where $c_{nn}$ is the $n$-th number in the decimal expansion of $x_n=0.c_{n1}c_{n2}c_{n3}...$ In such case, $y\in(0,1)$ and $y\not=f(n)\forall n\in\mathbb{N}$ (because they differ at least in one place), which is the contradiction we wanted. Notice, however, that we needed the assumption that the $n$-th digit always existed.

That is, it makes sense to speak of the $n$-th digit in the decimal expansion of any number in that interval, and it makes sense for such a number to have all digits different than zero (provided they aren't all nines). Natural numbers, however, do not enjoy this same property, since any natural number can be written as a finite sum of ones, even if you were to think of them as having infinite digits (to the left), only a finite amount of them would be different than zero. Therefore, for our "$y$" to be different than every $f(n)$ at least once, it will have "infinite non-zero digits", in which case it's not a natural number. To see this, note that, if $y$ where to have finite non-zero digits, that is, $y=A_kA_{k-1}...A_2A_1;$ $A_i\in\{0,1,2,...,9\}\forall i\land A_k\not=0$, then it wouldn't be different than the number $A_kA_{k-1}...A_2A_1$ which is in the image $f(\mathbb{N})$ by assumption.