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:
- L1 – 10111101110110001…
- L2 – 0010110011101010…
- L3 – 1001011010101010…
- …(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.
Best Answer
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.