# Cantor's Diagonal Argument

Why Cantor's Diagonal Argument to prove that real number set is not countable, cannot be applied to natural numbers? Indeed, if we cancel the "0." in the proof, the list contains all natural numbers, and the argument can be applied to this set.

• After we cross out the "0." the list contains infinite-digit "natural" numbers. – Karl Kroningfeld Jun 21 '13 at 11:13
• Because there is no way to apply it. Exactly how are you going to try to use the argument? – Brian M. Scott Jun 21 '13 at 11:13
• What do you mean by "cancel the $0$"? – David Mitra Jun 21 '13 at 11:14
• For "why can't we", questions, you should at least do an effort to show the execution of the programme you propose. If you try to even vaguely formulate this you will see where you run into trouble. For one thing, the infinite sequence of digits one might hope to be produced does not match the format required for a natural number. – Marc van Leeuwen Jun 21 '13 at 11:17
• @user1: The list is composed of elements of the set one is trying to prove non-countable; in the proposed proof these would be natural numbers. These are not infinite. A first problem however is that number $i$ on the list need not have an $i$-th digit. – Marc van Leeuwen Jun 21 '13 at 11:22

## 4 Answers

The list contains all natural numbers, but also quite a few more. Natural numbers are terminating strings of digits, that is they are of finite length. Cantors diagonal argument enumerates all strings of digits, especially non-terminating ones. And yes, the set of those is uncountable, whereas the set of terminating strings is in indeed countable.

• I would suggest you be more careful with the wording in your last two sentences. A subset of the rationals where each member is a non-terminating string is countable (a subset of a countable set is countable). Thus it is not sufficiently the termination (or non-termination) aspect which characterizes countability. – r12 Jun 23 '13 at 4:54
• The important aspect is that real numbers canot be described with finite strings. – Denis Sep 16 '14 at 13:59

How about this slightly different (but equivalent) form of the proof? I assume that you already agree that the natural numbers $\mathbb{N}$ are countable, and your question is with the real numbers $\mathbb{R}$.

Theorem: Let $S$ be any countable set of real numbers. Then there exists a real number $x$ that is not in $S$.

Proof: Cantor's Diagonal argument. Note that in this version, the proof is no longer by contradiction, you just construct an $x$ not in $S$.

Corollary: The real numbers $\mathbb{R}$ are uncountable.

Proof: The set $\mathbb{R}$ contains every real number as a member by definition. By the contrapositive of our Theorem, $\mathbb{R}$ cannot be countable.

Note that this formulation will not work for $\mathbb{N}$ because $\mathbb{N}$ is countable and contains all natural numbers, and thus would be an instant counterexample for the hypothesis of the natural number version of our Theorem.

• I think Cantor's proof is wrong, because he defines a number that doesn't exist.Consider the following argument:define S={n\in\matchal{N} and n\in[1,10]}which is obviously countable, and write these number in a column without repetition, and let us call r_n the number in the n-th position.Define the natural number\in[1,10],that belongs to S and so it is in the column,with the property r_n=r_{n-1}. We reach to an absurd because this number cannot stay in any position. But the absurd is because the number with such property does not exist, not because u cannot write in a column the numbers in S. – La buba Jun 21 '13 at 13:07
• by the way I'm not a mathematician. I'm just trying to understand the logic of the proof. – La buba Jun 21 '13 at 13:08
• @Bob, I appreciate the comments. But the Cantor diagonal argument is not wrong, and your example is at best not relevant. Note in my version of the proof, if you wanted to do the natural number version, it is irrelevant that there is some countable set of naturals that does not contain all the naturals. What matters is that there is also a countable set of naturals that contains all the naturals, namely $\mathbb{N}$, and no, the diagonal argument cannot construct a missing natural on $\mathbb{N}$, because there are no missing naturals in $\mathbb{N}$ by definition! – user452 Jun 21 '13 at 15:10

Cantor's diagonal argument is one of contradiction. You start with the assumption that your set is countable and then show that the assumption isn't consistent with the conclusion you draw from it, where the conclusion is that you produce a number from your set but isn't on your countable list. Then you show that for any

If you wanted to do Cantor's diagonal argument, you'd start by assuming the Natural numbers are countable, then try to create a contradiction by producing a number that isn't on the countable list.

Suppose the natural numbers are countable, and we list them then perform Cantor's diagonal technique, producing a string of digits $x$. $x$ either has an infinite number of non-zero digits or $x$ has a finite number of non-zero digits.

If $x$ has a finite number of non-zero digits, then $x$ is on the list (and it's a Natural number), so there no contradiction. If $x$ has an infinite number of non-zero digits, then $x$ isn't a Natural number (and it isn't on the list), so there is no contradiction.

Either way, we can't find a contradiction by using Cantor's diagonal argument on the assumption that the Natural numbers are countable, so we can't conclude from that argument that the Natural numbers are uncountable.

The most important part here is to notice that any natural number must have a finite number of non-zero digits.

Make a list of natural numbers, put into separate rows, as in setup for the Cantor's argument. Applying the diagonal argument extract a new number different from each row. The main, or even maybe the only, reason why this does not disprove countability of natural numbers is that this new constructed number is not necessarily a natural number. True, you have found a new number not among your list, but it is not necessarily a new addition to natural numbers.

Here is an analogy:

Theorem: The set of sheep is uncountable.

Proof: Make a list of sheep, possibly countable, then there is a cow that is none of the sheep in your list. So, your list could not possibly have exhausted all the sheep!

What is wrong with this proof? (Unless you believe there are uncountably many sheep! :))