Re: Cantor Diagonal Proof

On 4/13/25 5:22 PM, Lawrence D'Oliveiro wrote:

On Fri, 11 Apr 2025 09:24:57 -0400, Richard Damon wrote:
 

The problem with your "induction" is you assumed the existance of a
computation that doesn't exist, a computation that given the nth digit
of the nth computable number for any value of n.

 If you don’t have that, then how can you have the Cantor construction?

Because Cantor wasn't talking about computable numbers, so his "construction" doesn't need to be one.
Cantor is proving uncountablilty of the Real by contradiction.
if there WAS a possible mapping of the reals to the natural numbers, then by that mapping the construction happens, and we can then by the simple method build a number that can't be on the list.
Since we started with the assumption that there was a mapping of ALL the reals to the Naturals, and this was one of them, then obviously this one wasn't actually complete, and thus NONE of them could be, so the construction doesn't ever happen because we can never do the prerequisite construction.
When we look at the later analysis on computable numbers, we don't need a master algorith, we need an algorithm for each number as that is what defines the computable numbers.
We then can use the Axiom of Choice to choose one of the many variations for each of the numbers, and then sort them by a given method to represent them.
That gives us an infinite list of algorithms, which we can "construct" with, but not "compute" with, as computations need to be finite.
This is just one of the weirdities of the axiom of choice.