Re: Cantor Diagonal Proof

On 4/17/25 7:45 PM, 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.

But you don't need the match N digits to show that it matches to N+1 digits, as simple counting shows that if you look at the first 10^(N+1) entries, every N+1 digit number is there.

 

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!

But that is part of the point. Induction doesn't say it handles ALL infinities, just that the set it works for is the same as the Natural Numbers.
So, the fact that it holds for ALL N, means that since all N are finite, you have proven that every FINITE length number is in the list.
Since, as shown, 1/9, i.e, 0.11111... doesn't have a finite expansion as a decimal, you haven't shown that it is in the list.

 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.

No, that *IS* the number that you can PROVE is the result by actual induction.

 

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.

WHat is invalid in Cantor's construction?
Note, The *IS* laogica validity to proof by induction, as induction is one of the AXIOMS of the system that defines the Natural Numbers.
You are running into the proble that you are trying to argue with the definition of the system.

 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.

In other words, you don't understand that operation of the operation of proof by contradiction.
The key is that there is no rule that inately rules such a constuction against the rules, Cantor just shows that any system that actually allows validly to form such a construction, by proof, is contradictory, and one of the assumed preconditions is that the logic system is not contradictory.
Thus, since there is only ONE presumed capability, if the system with that capability is shown to lead to a contradiction, that capability must not exist.
This is basically, a use of the arguemnt:
A -> B
not B
Therefore, not A.
With A being the proposition that we can create a one-to-one mapping between the Reals and the Naturals, and B is that the Number on that diagonal is in that mapping (as required by it being a complete one-to-one mapping)

 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.

You can't add Cantor construction as a axiom, because that would break your system. Cantor's proof is showing that such a construction CAN'T exist, so making its existance an axiom makes your system contradictory.