# Why Cantor's diagonal proof applies to real but not to natural numbers (specific reason for repost)

I am aware that a very similar question was asked here before, but I still fail to understand the exact reason why Cantor's argument is applicable in one case and not in the other. In order to clarify my point, I wish to present two parallel attempted proofs - one more or less equivalent to Cantor's own (proving that the real numbers can't be listed) and one that will attempt to prove by an equivalent method that the natural numbers can't be listed/counted (which of course would make no sense if true). Could you please help me better understand Cantor's argument by telling me at which step my attempted parallel breaks down? I am not a mathematician - just someone trying to make sense of how infinite sets work.

Step 1 - Cantor's Argument-CA): Let the number of members (cardinality) of the infinite set of Natural numbers be defined as aleph-0. Let any infinite set that is bijective with the set of Natural numbers be called countably infinite/listable.

Step 1 - Parallel Argument-PA): Let the infinite set of Countable Numbers (C) be defined as follows {1*, 2*, 3*, 4*, 5*...}. (I am aware this is not a very formal definition, but I think it should be possible to formally and independently define an infinite set that is equivalent to the set of natural numbers). Let the number of members (cardinality) of the set of Countable numbers be defined as aleph-0. Let any infinite set that is bijective with the set of Countable numbers be called countably infinite/listable.

Step 2 - Cantor's Argument): Let M be defined as the list of all infinite two-bit sequences. Let L denote a subset of M, constructed as an unbounded list of its members Li: L1, L2, L3 etc. Match each member of L with a member of N (Natural Numbers). The result would be something like:

1. L1 - 10111101110110001...
2. L2 - 0010110011101010...
3. L3 - 1001011010101010...
4. ...(it is not necessary for the list to be complete)

Step 2 - Parallel Argument) Let N be defined as the list of all finite two-bit sequences starting with 1. Let K denote a subset of N, constructed as an unbounded list of its members Ki: K1, K2, K3 etc. Match each member of K with a member of C (Countable Numbers). The result would be something like:

-1* - K1 - 1

-2* - K2 - 10

-3* - K3 - 100010

-4* - K4 - 1000

-5* - K5 - 11101

-...(it is not necessary for the list to be complete)

Step 3 - Cantor's Argument) For any number x of already constructed Li, we can construct a L0 that is different from L1, L2, L3...Lx, yet that by definition belongs to M. For this, we use the diagonalization technique: we invert the first member of L1 to get the first member of L0, then we invert the second member of L2 to get the second member of L0 and so on. In our case L0 = 011...

-L0 belongs to M

-L0 does not belong to L={L1, L2, L3...Lx} for any x.

It follows that: L={L1, L2, L3...Lx} for any x cannot be M. Given that L1, L2, L3... was each matched to a Natural number, it follows that there are more members of M than members of the Natural number set, therefore the set M is not countably infinite. It is possible to show that the set of real numbers is bijective with M, therefore the set of Real numbers is also not countably infinite.

Step 3 - Parallel Argument) For any number x of already constructed Ki, we can construct a K0 that is different from K1, K2, K3...Kx, yet that by definition belongs to N. For that we use the copying and addition technique: going over the list sequentially, we copy the digits of each Kr (r=1 to x) into the corresponding digits of K0, always overwriting existing entries. After that we add one additional {0} at the end. In our case we get K0=111010...0.

-K0 belongs to N

-K0 does not belong to K={K1, K2, K3...Kx} for any x.

It follows that: K={K1, K2, K3...Kx} for any x cannot be N. Given that K1, K2, K3... was each matched to a Counting number, it follows that there are more members of N than members of the Counting number set, therefore the set N is not countably infinite. It is possible to show that the set of Natural numbers is bijective with N, therefore the set of Natural numbers is also not countably infinite.

Concluding remark: My problem with Cantor's argument is that the second premise in the syllogism in step 3 seems to fail because that premise seems to presuppose under L both an actually infinite list, and a constructed list {L1, L2, L3...Lx} which is by definition finite. I would conclude that L is not defined and that therefore the conclusion doesn't really hold. Which would explain why, in my exposition, the argument paradoxically "works" for natural numbers as well. I am sure I am misconstruing something though and I will be grateful for your corrections. Thank you.

• Your arguments are almost all correct, except that the conclusion in Step3-PA should be that the set of all natural numbers is not finite. – Berci Mar 14 '19 at 23:41
• I only skimmed, but I'm guessing the problem is that the number constructed is not an integer. An integer must have finitely many digits. – Elliot G Mar 14 '19 at 23:47
• @Elliot G, thank you for the comment. Nicolas in his reply brought my attention to this same issue. It is quite possibly the solution I was looking for, I need to reflect. – Dan Tcaci Mar 15 '19 at 0:09
• @AlexR. Cantor's original proof did not require assuming the list to be complete. It rather proved that, given that L0 is not part of L but is part of M, L could not have been a complete list. Cantor's original text can be found here: logicmuseum.com/cantor/diagarg.htm – Dan Tcaci Mar 15 '19 at 0:13
• The problem with this question, with all of these questions about Cantor's diagonal, is that the answer is pretty much the same to all of them. And it's almost always $\frac13$, or some irrational number. – Asaf Karagila Mar 15 '19 at 8:54

If your list of natural numbers is finite, then your proof is correct, but it only disproves that there are only finitely many numbers. If your list is infinite, your generated (infinite) string that doesn't belong to your list need not necessarily be a natural number (think of a string like "1011011011111111...", which is not a natural number, even if you add a 0 to the end of it.

• I didn't realize that, given an infinite list of Ki, I was creating an infinite string in step 3 of the Parallel Argument. This is a very important insight, thank you! – Dan Tcaci Mar 14 '19 at 23:56

going over the list sequentially, we copy the digits of each Kr (r=1 to x) into the corresponding digits of K0, always overwriting existing entries

work for the sequence

$$K_1 = 0$$

$$K_2 = 1$$

$$K_3 = 0$$

$$K_4 = 1$$

and so on?

• Each Ki has to start with a {1}, as is noted in step 2 of the PA. Repetitive entries both in K and in L should be disallowed. Perhaps I should add that to the text, thank you. If your list of Ki would be admissable, K0 would be 10 i.e. (1,0). The first digit would have been rewritten 3 times (or for however long the list continues) and a 0 would have been added at the end. Note that 10 is not on the list. – Dan Tcaci Mar 14 '19 at 23:54
• If we ignore the problems for now, there's a big red flag when you say however long the list continues. Isn't the list meant to be infinite? Why should it be $10$ and not $00$? – John Gowers Mar 14 '19 at 23:56
• The list is indeed infinite, whatever that means (for one of my suspicions/claims is that infinity is defined inconsistently in Cantor's argument). I just meant to illustrate how the copying and addition procedure would work with your list of four members, I'm sorry for the confusion. In an infinite list, K0's first digit would be defined by the first digit of Kx (the latest member of the list). – Dan Tcaci Mar 15 '19 at 0:03
• @DanTcaci If a list is infinite then it hasn't got a latest member. – John Gowers Mar 15 '19 at 9:17
• What matters is that there is a well-defined procedure for producing the member K0 for any x. If the digits of my constructed K0 would be undefined, as you seem to suggest, then Cantor's argument would fail as well because the digits of L0 would as well be undefined (you need an arbitrarily large i'th member in order to invert its i'th digit and obtain the i'th digit of Li if you are working with an infinite list). I don't think that this is the issue. Nicolas's reply and Elliot's comment show why my parallel argument fails though (an infinite sequence cannot be a natural number). – Dan Tcaci Mar 15 '19 at 11:17

I think it might help you to visualize the argument by contradiction. Suppose that AFTER this process, your diagonal number is $$M$$, and you can find a number $$K_N$$, somewhere in your original enumeration list, such that $$K_N=M$$. $$N$$ by definition is some finite index, and yet, the $$N$$'th digit of $$K_N$$ is not equal to the $$N$$'th digit of $$M$$, by construction. This gives a contradiction.

The key point is that since we're assuming that we've listed out all the numbers on the manifold, any such number must have a corresponding (finite) index in the enumeration process, so you can always look it up and confirm the constructed number $$M$$ necessarily disagrees with it.

So while it's true that at any finite step $$s$$, your constructed number $$M$$ (thus far, with $$s$$ digits) only disagrees with the first $$s$$ numbers in your enumeration, if this process is taken to infinity, you will, sooner-or-later, have gone through all the real numbers. This ultimately gives the desired contradiction, that the manifold must actually be uncountable.