Why I have trouble with Cantor's diagonal argument…
2 reactions
Why I have trouble with Cantor's diagonal argument.
Cantor's diagonal argument starts with a pair of infinite sets s_n and T, where s_n is an enumeration each element of elements from T, and the elements of T is defined to be natural number. Then he shows that an element s_n of T can be constructed that doesn't correspond to any s_n in the enumeration. This is accomplished by bit flipping the n-th bit of the n-th element of digits in T. Thus s is a member of T that differs from each existing s_n because the n-th digits differ.
* s_1 = (**0**, 0, 0, 0, 0, 0, 0, ...)
* s_2 = (1, **1**, 1, 1, 1, 1, 1, ...)
* s_3 = (0, 1, **0**, 1, 0, 1, 0, ...)
* s_4 = (1, 0, 1, **0**, 1, 0, 1, ...)
* s_5 = (1, 1, 0, 1, **0**, 1, 1, ...)
* s_6 = (0, 0, 1, 1, 0, **1**, 1, ...)
* s_7 = (1, 0, 0, 0, 1, 0, **0**, ...)
* ...
* s_n = (**1, 0, 1, 1, 1, 0, 1**, ...)
Let's assume s_n corresponds to the set of all natural numbers. But that's a problem since natural numbers, in spite of being a (presumed) countably infinite set, are defined such that every natural number has finitely many digits. Yet a member of the set T, in Cantor's construction, is allowed to extend to an infinite number of digits, because the set s_n is infinite. To show this I'll define what I'll call bin-adic numbers, in honor of p-adic numbers. Essentially just an inverted binary representation of base10 numbers.
* Binary:
* s_1 = (..., 0, 0, 0, 1)
* s_2 = (..., 0, 0, 1, 0)
* s_3 = (..., 0, 0, 1, 1)
* s_4 = (..., 0, 1, 0, 0)
* s_5 = (..., 0, 1, 0, 1)
* s_6 = (..., 0, 1, 1, 0)
* s_7 = (..., 0, 1, 1, 1)
* Bin-adic: Where (...) consists only of a series of zeros of arbitrary length.
* s_1 = (1, 0, 0, 0, ...)
* s_2 = (0, 1, 0, 0, ...)
* s_3 = (1, 1, 0, 0, ...)
* s_4 = (0, 0, 1, 0, ...)
* s_5 = (1, 0, 1, 0, ...)
* s_6 = (0, 1, 1, 0, ...)
* s_7 = (1, 1, 1, 0, ...)
Let the natural number have only finitely many digits, per standard definition. Then the natural numbers map one-to-one to the bin-adic numbers where the last 1 bit is, by definition, limited to a finite distance from the first bit. In fact the bin-adic numbers don't just map one-to-one to the natural numbers, they uniquely define the natural number that maps to it without reference to the index set s_n. Which I call well-ordering with identity. If the number of bits in any element is infinite, as Cantor has posited for the set T, then this unique mapping continues well beyond a finite distance from the first bit. Any bit set with all 1 bits a finite distance from the first bit in the element is by definition a natural number, limited to a finite number of digits. Any element of T that contains a 1 bit greater than a finite distance from the first bit is an integer with transfinite digits, hence not a natural number. Because the natural numbers are, by definition, those numbers where the 1s are limited to a finite distance from the first bit.
Here's the problem. Cantor assumed that for every infinite index s_n he could operate on a unique digit of T. But the digits of T are by definition finite. Hence, he must run out of digits in T before he exhausts the set s_n. His constructive new number must then terminate prior to reaching exhausting the s_n index. Leaving plenty members of the set of natural numbers he never operated on. By randomizing his natural number set he could obfuscate the assumption that the number of digits in a natural number equals the number of elements on the index of that set. The premise then concluded itself.
If the number of digits in a natural number are by definition finite, then that digit count cannot equal the index count of natural numbers. Because that would require a natural number with infinite digits, thus (by definition) cannot be a natural number. Any iteration over any given natural number must, by definition, terminate before exhausting the index set.
This implies to me that the set of all natural numbers are uncountably infinite. Because you cannot exhaust the index set before running out of digits in any given natural number to operate on Cantor style. If they are equal (one-to-one) then by definition they cannot be natural numbers to begin with. A natural number does not have infinite digits, by definition. Obscuring the digit count of an element in a set by randomization, and assuming the index count and the digit count of an element in the set maps one-to-one, merely assumes the premise proves itself.
#technology
Cantor's diagonal argument starts with a pair of infinite sets s_n and T, where s_n is an enumeration each element of elements from T, and the elements of T is defined to be natural number. Then he shows that an element s_n of T can be constructed that doesn't correspond to any s_n in the enumeration. This is accomplished by bit flipping the n-th bit of the n-th element of digits in T. Thus s is a member of T that differs from each existing s_n because the n-th digits differ.
* s_1 = (**0**, 0, 0, 0, 0, 0, 0, ...)
* s_2 = (1, **1**, 1, 1, 1, 1, 1, ...)
* s_3 = (0, 1, **0**, 1, 0, 1, 0, ...)
* s_4 = (1, 0, 1, **0**, 1, 0, 1, ...)
* s_5 = (1, 1, 0, 1, **0**, 1, 1, ...)
* s_6 = (0, 0, 1, 1, 0, **1**, 1, ...)
* s_7 = (1, 0, 0, 0, 1, 0, **0**, ...)
* ...
* s_n = (**1, 0, 1, 1, 1, 0, 1**, ...)
Let's assume s_n corresponds to the set of all natural numbers. But that's a problem since natural numbers, in spite of being a (presumed) countably infinite set, are defined such that every natural number has finitely many digits. Yet a member of the set T, in Cantor's construction, is allowed to extend to an infinite number of digits, because the set s_n is infinite. To show this I'll define what I'll call bin-adic numbers, in honor of p-adic numbers. Essentially just an inverted binary representation of base10 numbers.
* Binary:
* s_1 = (..., 0, 0, 0, 1)
* s_2 = (..., 0, 0, 1, 0)
* s_3 = (..., 0, 0, 1, 1)
* s_4 = (..., 0, 1, 0, 0)
* s_5 = (..., 0, 1, 0, 1)
* s_6 = (..., 0, 1, 1, 0)
* s_7 = (..., 0, 1, 1, 1)
* Bin-adic: Where (...) consists only of a series of zeros of arbitrary length.
* s_1 = (1, 0, 0, 0, ...)
* s_2 = (0, 1, 0, 0, ...)
* s_3 = (1, 1, 0, 0, ...)
* s_4 = (0, 0, 1, 0, ...)
* s_5 = (1, 0, 1, 0, ...)
* s_6 = (0, 1, 1, 0, ...)
* s_7 = (1, 1, 1, 0, ...)
Let the natural number have only finitely many digits, per standard definition. Then the natural numbers map one-to-one to the bin-adic numbers where the last 1 bit is, by definition, limited to a finite distance from the first bit. In fact the bin-adic numbers don't just map one-to-one to the natural numbers, they uniquely define the natural number that maps to it without reference to the index set s_n. Which I call well-ordering with identity. If the number of bits in any element is infinite, as Cantor has posited for the set T, then this unique mapping continues well beyond a finite distance from the first bit. Any bit set with all 1 bits a finite distance from the first bit in the element is by definition a natural number, limited to a finite number of digits. Any element of T that contains a 1 bit greater than a finite distance from the first bit is an integer with transfinite digits, hence not a natural number. Because the natural numbers are, by definition, those numbers where the 1s are limited to a finite distance from the first bit.
Here's the problem. Cantor assumed that for every infinite index s_n he could operate on a unique digit of T. But the digits of T are by definition finite. Hence, he must run out of digits in T before he exhausts the set s_n. His constructive new number must then terminate prior to reaching exhausting the s_n index. Leaving plenty members of the set of natural numbers he never operated on. By randomizing his natural number set he could obfuscate the assumption that the number of digits in a natural number equals the number of elements on the index of that set. The premise then concluded itself.
If the number of digits in a natural number are by definition finite, then that digit count cannot equal the index count of natural numbers. Because that would require a natural number with infinite digits, thus (by definition) cannot be a natural number. Any iteration over any given natural number must, by definition, terminate before exhausting the index set.
This implies to me that the set of all natural numbers are uncountably infinite. Because you cannot exhaust the index set before running out of digits in any given natural number to operate on Cantor style. If they are equal (one-to-one) then by definition they cannot be natural numbers to begin with. A natural number does not have infinite digits, by definition. Obscuring the digit count of an element in a set by randomization, and assuming the index count and the digit count of an element in the set maps one-to-one, merely assumes the premise proves itself.
#technology
2
| 8,000 mlx | |
| 6 | |
| 2 |
comments
The snag is a swap in the setup, not the bit flip. The naturals only number the rows. Each row is an infinite string of bits, and flipping bit n of row n builds a string that disagrees with every row already written down. That fires on whatever list you started with, so the claim is not one missing natural. It is that no list indexed by the naturals can hold every infinite bit string. Which part will not sit still, the new string being well-defined, or the jump from one missed list to every possible list?
