ABSTRACT:
This paper reveals why Cantor's diagonalization argument fails to prove what it purportedly proves and the logical absurdity of "uncountable sets" that are deemed larger than the set of natural numbers.
Cantor's diagonalization proof (CDP) is used to prove various things like Gödel's Incompleteness theorem (GIT) and the uncountability of real numbers (URN). In the case of GIT, it is assumed that you can have a complete list of provable statements. You use CDP to prove a statement that is not on the list, then conclude the statement is not a provable statement; otherwise, it would be part of the list of all provable statements. However, if your complete list is not really complete, then it makes sense that you can prove a new provable statement not on the list. In the case of proving the URN, you use proof by contradiction: assume the real numbers are countable and assume a complete list of them between, say, .000 ... and .111 ... The list is believed to be complete because an infinite number of counting numbers (1 to n) each allegedly have a one-to-one correspondence to each real number on the list. CDP is then used to show there is a real number that is not on the list (a contradiction). Therefore, according to the proof, there is no bijection between the real numbers and the counting numbers.
Below, we will work through an example proof using CDP and demonstrate why it comes up short. Let's begin with an nXn matrix of real numbers in base 2. We go along the diagonal and flip each bit from 0 to 1 or 1 to 0 to create a new number not on the list. If we think the number is on the list, say, at row r, we can check it and see that its bit at column r doesn't match. We can repeat this exercise for all rows and see that we truly have a new real number not on the list.
Assuming we have used up all the counting numbers to make the complete list of reals from .000 ... to .111 ..., we are forced to conclude that the number of reals exceeds the number of counting numbers by at least one. Therefore, the reals are uncountable (contrary to an initial assumption, via proof by contradiction, that the reals are countable). However, a list of positive integers (counting numbers, including 0) can also be shown to be uncountable:
Using CDP we can create a positive integer that is not on the list! The good news is we can use this new integer to count the new real number, so could it be that the real numbers are countable after all? If your alarm bells are going off, I feel your pain. You may have noticed that the new integer is 0...11 which is 3 in base 10. How can the number 3 be absent from a complete list of positive integers?! Answer: the complete list is not really complete. An nXn matrix only provides a subset of the set of positive integers. This is why CDP can produce numbers that are not part of the list. The assumption that we have a "complete list" of members of a given set is a false premise. Here's why:
Each matrix column corresponds to a digit. Thus we have a list of numbers with n digits. Where there's n digits, there's B^n (B is the number base) numbers with n digits. For example, if B = 2, and there are 3 digits, there are eight possible numbers, not three. If we only list three numbers, there are five more numbers that are not on the list. Once included, though, no amount of diagonal gimmickry will create a three-digit number not part of the list. This is not only true for integers but also real numbers, since reals are just integers with decimal points. Below is a mathematical proof showing that a complete list has 2^n members, not n members:
If the goal is to have a complete list, then we need a (2^n)Xn matrix:
Note that 0...11 is now included on the list. Now, just for the sake of argument, let's assume the list of reals we started with is complete, i.e., countable. By some method m, we derive a new real number not on the list. Let's assume method m is an indisputable method. We conclude that the set of real numbers is larger than the set of counting numbers, and, cannot be counted. But this implies that we run out of counting numbers before we run out of reals, i.e., it is possible to have a higher "count" of real numbers than the the numbers that count them. If we can't count the extra real numbers, then it is meaningless to say we have more, or, a higher count of real numbers and a lower count of the numbers that do the counting. The following diagram provides a visual representation of this absurdity:
If we have a list of n real numbers and derive one more, what does "one more" mean if not n+1 real numbers? If "one more" means n+1, then for every new real number created, there is an additional natural number added as well. With this in mind, we can map the positive integers (including 0) to real numbers in a range of 0 to 1:
Notice that if we take n to the limit of infinity, the number of real numbers grows and so does the number of positive integers. To count the reals between 0 and 1 requires 2^n + 1 counting numbers as n moves to infinity. Suppose we expand the range of reals: 0 to 2^n:
We now need 2^(2n) + 1 (n-->infinity) natural numbers to count this expanded range. If we continue to map 0 to 0, we could map the even positive integers to the positive real numbers, and, the odd positive integers to the negative real numbers:
We now need 2^(2n+1) + 1 (n-->infinity) natural numbers to count real numbers from -2^n to 2^n.
The great thing about the concept of infinity is infinity isn't a finite number. If we think the natural number set N is too small and can't count a bigger real number set R, we can make N bigger without using up its infinite potential. Both sets are forever growing and neither is fixed in stone. Therefore, for every increase in set R there is a corresponding increase in set N. If not, then it is meaningless to claim there are more members in R when its extra members can't be counted.
In conclusion, Cantor's diagonalization result makes perfect sense once we are aware of the fact that the "complete list" is only a partial list of members of a set. This should cast doubt on whatever Cantor's diagonal argument allegedly proves. Additionally, all methods of proving the uncountability of real numbers, etc. fail to address the absurdity of claiming that a set R has more members than the set of counting numbers needed to confirm that R does in fact have more members. It is obvious that there are more real numbers between, say, 1 and 2 than natural numbers. Albeit, the phrase "more real numbers" implies a higher count, i.e., countability.
References:
1. 2020. SP20:Lecture 9 Diagonalization. courses.cs.cornell.edu
2. Cantor's Diagonal Argument. Wikipedia
3. Dr. Pevam. 2018. R is Uncountable. youtube.com
4. Zap, Elvis. 2010. The Cantor Set is Uncountable. youtube.com
5. Hartl, Werner (and a comment from Pendaran Roberts.) Cantors Diagonal Argument Fails. youtube.com