Re: Cantor Diagonal Proof

On 18/04/2025 00:45, Lawrence D'Oliveiro wrote:

On Tue, 15 Apr 2025 19:44:11 +0100, Mike Terry wrote:
 

It is not a proof by induction as it makes no use of an induction
hypothesis PHI(n), and does not have any essential induction step PHI(n)
--> PHI(n+1).

 It does. It shows that, if the first N digits match, then so does the
(N+1)th digit. Given that it matches the first digit, those are your two
requirements for proof by induction.

Um, no it doesn't.
The first N digits will match somewhere in the list, but that DOES NOT imply that the (N+1)th digit will match the (N+1)th digit IN THAT MATCHING list entry.  E.g. in RH's counterexample the implication you are suggesting clearly fails.
It is true that the (N+1) digit prefix will match some completely NEW entry in the list, but that happens regardless of anything the N digit prefix did.  So this is not classified as a "proof by induction".

 

Nonsense!  RH's example using your very list constructs the
anti-diagonal 0.111111... which is NOT IN YOUR LIST.

 But at every stage, by induction, it matches an element in the list. You
only get a number that’s not in the list when you get to the end of the
construction. But it’s an infinite construction!

This is the fault of your misinterpretation of the Cantor argument as some kind of infinite supertask.  What Cantor produced was a mathematical proof, not an infinitely running program.  There   may be logical problems with your own misunderstanding of the proof, but that is your problem.
<..snip..>

Let’s start again, with the assumption that we have a list mapping all the
reals 1:1 to the positive integers. So given any real, we can assign it a
position N ∈ ℤ ≥ 1.
 So now we apply the Cantor construction, to try to come up with a number
not in the list. But a consequence of the starting assumption is that the
number being constructed must be somewhere in the list, and therefore the
Cantor construction must map to some positive integer Nₙ.
 So the question is: what is digit Nₙ of this number?
 The answer is, it must be different from digit Nₙ of itself!

Right - that is the contradiction.

 So you see, the assumption that you *can* perform the Cantor construction
on a list of the reals leads to a contradiction. Therefore the
construction cannot be performed. QED.

Nonsense.  That the "anti-diagonal" exists, given the existence of the input list, is just basic logic + set theory.  [Basically it just comes down to composition of functions and basic set theory and so on.]  It is NOT an additional hypothesis within the proof which was added to reach the contradiction.
The additional hypothesis was in your
    "Let’s start again, WITH THE ASSUMPTION that we have a list mapping
    all the reals 1:1 to the positive integers. So given any real, we
    can assign it a position N ∈ ℤ ≥ 1"
The clue for this is in your own choice of language in the word "ASSUMPTION" :).  You correctly identified the contradiction that follows, so the assumption on which it was based is false.  There is no such mapping, so the reals are uncountable.

 What we have here is duelling assumptions: either the list can be
constructed, or (according to the Cantor construction) it cannot. There is
no “self-evident” reason to say one argument is valid while the other is
not.

No, that's not a reasonable comparison.  The anti-diagonal definition is NOT an assumption within Cantor's proof - it is just verifiably valid applications of the axioms of set theory and logic that are in play.  For example, within ZFC the anti-diagonal digit sequence definition could be completely reduced to a sequence of ZFC and logical axioms.  It doesn't even involve the "controversial" Axiom of Choice! :)  Just the simple uncontroversial bits.
Mathematicians of course can (and do) look at what can be proved in weaker theories or weaker systems of logic itself, but that's a rather specialised field.  The VAST majority of the worlds mathematicians are not interested in this, and conduct their work within some basic set theory framework which for sure supports the definition of the anti-diagonal.  [Although most are not formal about the exact details of this.]
Your assumption that there is a complete list of real numbers is completely different.  It is introduced into the proof with no justification whatsoever - it is no more than an unproven claim being considered without regard to whether it is true/false.  Later it is used to deduce a contradiction, so it is rejected as false.

 Therefore I suggest that the Cantor construction is similarly an axiom,
that has to be added before you can construct the reals. Without it, the ℝ
you construct consists solely of computable numbers.
 

The Cantor diagonal argument is NOT an axiom - it follows from the other axioms of set theory.  So if you wanted to invalidate it as a proof method you would need instead to remove whatever set theory axioms allow as to prove the diagonal argument.  Well that's fine I guess for you personally, but you don't know what you're doing, so you can be sure to invalidate a significant fraction of existing mathematical results in the process.
It seems your problem might be with mathematics involving infinite sets.  That might fit in with your programming background with a corresponding lack of maths background, but mathematics is much more than just programming.
Of course, if someone stands there rejecting axioms or logical reasoning that the vast majority of mathematicians accept, then can end up unable to personally prove all sorts of standard mathematical results - but there's no reason others should accept there are any problems with those proofs.
Mike.