Path: ...!weretis.net!feeder9.news.weretis.net!news.nk.ca!rocksolid2!i2pn2.org!.POSTED!not-for-mail From: Richard Damon Newsgroups: comp.theory Subject: Re: Cantor Diagonal Proof Date: Thu, 17 Apr 2025 20:22:20 -0400 Organization: i2pn2 (i2pn.org) Message-ID: <803c9fbf2e03253f889e618357b2d2b3c7728cea@i2pn2.org> References: <9c27b08cca9d0fca87e57bcabc3412c80ff7a4f1@i2pn2.org> <99bd9c3545fdcc03cf33152ee0db852edbe1e23d@i2pn2.org> MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Date: Fri, 18 Apr 2025 00:43:21 -0000 (UTC) Injection-Info: i2pn2.org; logging-data="793383"; mail-complaints-to="usenet@i2pn2.org"; posting-account="diqKR1lalukngNWEqoq9/uFtbkm5U+w3w6FQ0yesrXg"; User-Agent: Mozilla Thunderbird X-Spam-Checker-Version: SpamAssassin 4.0.0 Content-Language: en-US In-Reply-To: Bytes: 6181 Lines: 120 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.