Re: Cantor Diagonal Proof

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.

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!

Your fallacy is in assuming that the human reader will extrapolate the
obvious pattern in that digit sequence to construct, in their mind, a
number that is not in the list. That’s not how logic works.

You misunderstand what it means for a number (such as the Cantor
anti-diagonal D) to "be in the list" or not.

Or maybe you misunderstand that there is no inherent logical validity to
the Cantor construction, just as there is no inherent logical validity to
proof by induction; induction had to be added as one of the axioms in the
construction of the integers, so that we could reason with it. But given
that it is there, you cannot prove induction false; because if you do, you
have proven that there is a logical contradiction in the system of
integers.

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!

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.

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.

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.