Path: news.eternal-september.org!eternal-september.org!feeder3.eternal-september.org!border-3.nntp.ord.giganews.com!local-3.nntp.ord.giganews.com!border-2.nntp.ord.giganews.com!border-1.nntp.ord.giganews.com!nntp.giganews.com!Xl.tags.giganews.com!local-4.nntp.ord.giganews.com!nntp.brightview.co.uk!news.brightview.co.uk.POSTED!not-for-mail
NNTP-Posting-Date: Fri, 18 Apr 2025 03:13:24 +0000
Subject: Re: Cantor Diagonal Proof
Newsgroups: comp.theory
References: <vsn1fu$1p67k$1@dont-email.me> <vthad1$3oh15$3@dont-email.me>
 <9c27b08cca9d0fca87e57bcabc3412c80ff7a4f1@i2pn2.org>
 <vtk37d$295ku$7@dont-email.me>
 <99bd9c3545fdcc03cf33152ee0db852edbe1e23d@i2pn2.org>
 <vtko3u$2u0tr$6@dont-email.me>
 <yfmcnXdudYVoNWP6nZ2dnZfqn_WdnZ2d@brightview.co.uk>
 <vts3r9$1lm06$4@dont-email.me>
From: Mike Terry <news.dead.person.stones@darjeeling.plus.com>
Date: Fri, 18 Apr 2025 04:13:25 +0100
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
 Firefox/91.0 SeaMonkey/2.53.18.2
MIME-Version: 1.0
In-Reply-To: <vts3r9$1lm06$4@dont-email.me>
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Message-ID: <OWqdndMdMZLJXpz1nZ2dnZfqnPudnZ2d@brightview.co.uk>
Lines: 115
X-Usenet-Provider: http://www.giganews.com
X-Trace: sv3-HWBj6n/dGQoiVlVSTEQBCFJp+ArUCdBJOoxsd6gW3PRmqQi7O3/p76hTlN5mWs10Id7u5d4SuwqqPri!uVzfScA5I/0JaiuF8IFTc73ZwEXcQxGwv0DOL7bo7RO7T2yvvh/g9EIE7Oc9G9JAWp/rSgzmHjiM!yHwlCoJM6JsscE3zCOsZICSz2rk=
X-Abuse-and-DMCA-Info: Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info: Otherwise we will be unable to process your complaint properly
X-Postfilter: 1.3.40

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.