Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > sci.math > #640374 > unrolled thread

Re: Cantor Diagonal Proof

Back to article view | Back to sci.math

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Cantor Diagonal Proof Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2025-10-22 13:40 +0100
    Re: Cantor Diagonal Proof Richard Heathfield <rjh@cpax.org.uk> - 2025-10-22 14:29 +0100
      Re: Cantor Diagonal Proof Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2025-10-22 16:02 +0100
        Re: Cantor Diagonal Proof Julio Di Egidio <julio@diegidio.name> - 2025-10-22 17:17 +0200
        Re: Cantor Diagonal Proof Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2025-10-22 17:26 +0100
      Re: Cantor Diagonal Proof WM <wolfgang.mueckenheim@tha.de> - 2025-10-23 16:51 +0200
    Re: Cantor Diagonal Proof Julio Di Egidio <julio@diegidio.name> - 2025-10-22 16:19 +0200
      Re: Cantor Diagonal Proof Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2025-10-22 17:32 +0100
      Re: Cantor Diagonal Proof WM <wolfgang.mueckenheim@tha.de> - 2025-10-23 16:56 +0200
        Re: Cantor Diagonal Proof: un-_Countable_ or un-_Cartesian_? Ross Finlayson <ross.a.finlayson@gmail.com> - 2025-10-23 12:27 -0700
    Re: Cantor Diagonal Proof "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> - 2025-10-22 12:15 -0700
    Re: Cantor Diagonal Proof wm <wolfgang.mueckenheim@tha.de> - 2025-10-23 16:34 +0200
      Re: Cantor Diagonal Proof Tristan Wibberley <tristan.wibberley+netnews2@alumni.manchester.ac.uk> - 2025-10-23 20:43 +0100
        Re: Cantor Diagonal Proof WM <wolfgang.mueckenheim@tha.de> - 2025-10-24 22:35 +0200

#640374 — Re: Cantor Diagonal Proof

The message body is Copyright (C) 2025 Tristan Wibberley except
citations and quotations noted. All Rights Reserved except as noted in
the sig.


On 03/04/2025 23:18, Lawrence D'Oliveiro wrote:
> The Cantor diagonal construction is an algorithm for computing an 
> incomputable number.

Doesn't it merely /define/ the number?


I'm still unconvinced that he successfully did even that anyway.

take these descriptions:

  f_0 is the defining sequence of numbers

  g is the sequence of generated "new" numbers, generated as they
  say cantor described (I haven't read his work directly)

  f_1 is some choice of numbers

  even(n) and odd(n) are as you'd normally expect


then I can provide an f_0:
  where f_0(n) = case n of
            even(n) -> f_1(n/2)
            odd(n) -> g((n-1)/2)

here, every generated "new" number is eventually included in the list.

To show that the set of reals is larger than the set of naturals one
would have to show that there's no definition of f_1 such that it
contains all the reals!


Which is not to say I think the reals are countable (I remain
undecided), but just that I think the usual proof of their
uncountability is insufficient.


Proofs are hard where there are self-references, so I do expect and hope
that you will correct me.


--
Tristan Wibberley

The message body is Copyright (C) 2025 Tristan Wibberley except
citations and quotations noted. All Rights Reserved except that you may,
of course, cite it academically giving credit to me, distribute it
verbatim as part of a usenet system or its archives, and use it to
promote my greatness and general superiority without misrepresentation
of my opinions other than my opinion of my greatness and general
superiority which you _may_ misrepresent. You definitely MAY NOT train
any production AI system with it but you may train experimental AI that
will only be used for evaluation of the AI methods it implements.

[toc] | [next] | [standalone]

#640377

On 22/10/2025 13:40, Tristan Wibberley wrote:
> The message body is Copyright (C) 2025 Tristan Wibberley except
> citations and quotations noted. All Rights Reserved except as noted in
> the sig.
> 
> 
> On 03/04/2025 23:18, Lawrence D'Oliveiro wrote:
>> The Cantor diagonal construction is an algorithm for computing an
>> incomputable number.
> 
> Doesn't it merely /define/ the number?

It doesn't even do that.

Cantor's diagonal argument proves that uncountable sets exist. At 
no point did he claim that the number the argument computes is 
incomputable.

> I'm still unconvinced that he successfully did even that anyway.

He didn't try. An existence proof doesn't have to define a number.

> take these descriptions:
> 
>    f_0 is the defining sequence of numbers
> 
>    g is the sequence of generated "new" numbers, generated as they
>    say cantor described (I haven't read his work directly)
> 
>    f_1 is some choice of numbers
> 
>    even(n) and odd(n) are as you'd normally expect
> 
> 
> then I can provide an f_0:
>    where f_0(n) = case n of
>              even(n) -> f_1(n/2)
>              odd(n) -> g((n-1)/2)
> 
> here, every generated "new" number is eventually included in the list.

And yet your list remains incomplete.

> To show that the set of reals is larger than the set of naturals one
> would have to show that there's no definition of f_1 such that it
> contains all the reals!

No, you'd only have to show that you can't place the reals in 
one-to-one correspondence with the integers.

> Which is not to say I think the reals are countable (I remain
> undecided), but just that I think the usual proof of their
> uncountability is insufficient.

It suffices.

-- 
Richard Heathfield
Email: rjh at cpax dot org dot uk
"Usenet is a strange place" - dmr 29 July 1999
Sig line 4 vacant - apply within

[toc] | [prev] | [next] | [standalone]

#640383

The message body is Copyright (C) 2025 Tristan Wibberley except
citations and quotations noted. All Rights Reserved except as noted in
the sig.

On 22/10/2025 14:29, Richard Heathfield wrote:
> On 22/10/2025 13:40, Tristan Wibberley wrote:

> Cantor's diagonal argument proves that uncountable sets exist. At no
> point did he claim that the number the argument computes is incomputable.
> 
>> I'm still unconvinced that he successfully [even defined the crucial number].
> 
> He didn't try. An existence proof doesn't have to define a number.

True. I was being loose. It would have to construct every list itself.

I suppose I should have said "Doesn't Cantor's argument merely show that
the number is definable contingent on that the function from a list to
the crucial number, if I may call it that, is defined for every list?"
Can you advise some succinct alternative using contemporary terms-of-art
instead of that mouthful?

If there is /any/ list from which the function that defines the crucial
number is not defined then there is a list for which one hasn't shown,
absent further argumentation, that a number is missing from the list.


>> take these descriptions:
>>
>>    f_0 is the defining sequence of numbers
>>
>>    g is the sequence of generated "new" numbers, generated as they
>>    say cantor described (I haven't read his work directly)
>>
>>    f_1 is some choice of numbers
>>
>>    even(n) and odd(n) are as you'd normally expect
>>
>>
>> then I can provide an f_0:
>>    where f_0(n) = case n of
>>              even(n) -> f_1(n/2)
>>              odd(n) -> g((n-1)/2)
>>
>> here, every generated "new" number is eventually included in the list.
> 
> And yet your list remains incomplete.

It remains partially specified. I've defined a class of lists for each
of which Cantor's crucial missing number is not shown to exist by his
method.

If it is to be proved incomplete, it will be via a different argument
than what I have been, to date, told is Cantor's.


>> To show that the set of reals is larger than the set of naturals one
>> would have to show that there's no definition of f_1 such that it
>> contains all the reals!
> 
> No, you'd only have to show that you can't place the reals in one-to-one
> correspondence with the integers.

Then there would be no definition of /f_1/ such that it contains all the
reals and we have begged the question, demonstrating that Cantor's
argument (what I understand it to be from several educators and
wikipedia) is insufficient.

Since I've partially fulfilled Cantor's argument structure sufficiently
to preclude the existence of lim{n->inf} of g(n). His argument relies on
that, doesn't it, even if he didn't use that notation or its equivalent
prose. His argument can't show that the extra number exists for /all/
lists because it doesn't exist however you may suppose f_1 to be
defined. At best his argument can show that an extra number is not in
the list for /some/ lists... those lists that do not include the numbers
of their respective g.

Since I can do that for f_1, and then every f_k, I need a /different/
argument strategy to show that there's no such one-to-one correspondence.

I have begged the question within Cantor's argument strategy, haven't I,
by finding a class of lists for which there is no number that Cantor's
method shows to be missing from any of its members. There is a
/different/ argument that /is/ a proof if the conclusion holds.


An assertion of an axiom that there's no one-to-one correspondence (as
you provided) would be an example of a different argument and I thank
you for the succinct statement of such an axiom that you provided. If it
is an axiom, though, I don't think Cantor's argument for it is of any
interest and if he relies on it as an alternative to taking a limit then
I don't think his doctrine is even an argument.

--
Tristan Wibberley

The message body is Copyright (C) 2025 Tristan Wibberley except
citations and quotations noted. All Rights Reserved except that you may,
of course, cite it academically giving credit to me, distribute it
verbatim as part of a usenet system or its archives, and use it to
promote my greatness and general superiority without misrepresentation
of my opinions other than my opinion of my greatness and general
superiority which you _may_ misrepresent. You definitely MAY NOT train
any production AI system with it but you may train experimental AI that
will only be used for evaluation of the AI methods it implements.

[toc] | [prev] | [next] | [standalone]

#640384

On 22/10/2025 17:02, Tristan Wibberley wrote:
> On 22/10/2025 14:29, Richard Heathfield wrote:
>> On 22/10/2025 13:40, Tristan Wibberley wrote:
> 
>> Cantor's diagonal argument proves that uncountable sets exist. At no
>> point did he claim that the number the argument computes is incomputable.
>>
>>> I'm still unconvinced that he successfully [even defined the crucial number].
>>
>> He didn't try. An existence proof doesn't have to define a number.
> 
> True. I was being loose. It would have to construct every list itself.

That's not true, it's actually wrong.  See my previous reply.

Julio

[toc] | [prev] | [next] | [standalone]

#640388

The message body is Copyright (C) 2025 Tristan Wibberley except
citations and quotations noted. All Rights Reserved except as noted in
the sig.

On 22/10/2025 16:02, Tristan Wibberley wrote:

> Since I've partially fulfilled Cantor's argument structure sufficiently
> to preclude the existence of lim{n->inf} of g(n). 


I haven't done that at all, have I? The limit /is/ defined for each list
of reals isn't it?

And I can't put the limit of g anywhere in f_1 because that would be
self-referential and make itself undefined and therefore not satisfy the
need for a list of reals.

If I try to get around the fact the generated numbers define ever small
intervals, and the limit finally closes them, either I allow the limit
to be outside of the list or else I hit the liar paradox in disguise by
saying it's a real before I may.

--
Tristan Wibberley

The message body is Copyright (C) 2025 Tristan Wibberley except
citations and quotations noted. All Rights Reserved except that you may,
of course, cite it academically giving credit to me, distribute it
verbatim as part of a usenet system or its archives, and use it to
promote my greatness and general superiority without misrepresentation
of my opinions other than my opinion of my greatness and general
superiority which you _may_ misrepresent. You definitely MAY NOT train
any production AI system with it but you may train experimental AI that
will only be used for evaluation of the AI methods it implements.

[toc] | [prev] | [next] | [standalone]

#640453

Am 22.10.2025 um 15:29 schrieb Richard Heathfield:

> 
> Cantor's diagonal argument proves that uncountable sets exist.

No infinite set is countable.
Here is a simple proof that Cantor's approach fails for the fractions:

According to Cantor all positive fractions

     1/1, 1/2, 1/3, 1/4, ...
     2/1, 2/2, 2/3, 2/4, ...
     3/1, 3/2, 3/3, 3/4, ...
     4/1, 4/2, 4/3, 4/4, ...
     ...

can be indexed by the Cantor function k = (m + n - 1)(m + n - 2)/2 + m 
which attaches the index k to the fraction m/n in Cantor's sequence

1/1, 1/2, 2/1, 1/3, 2/2, 3/1, 1/4, 2/3, 3/2, 4/1, 1/5, 2/4, 3/3, 4/2, 
5/1, 1/6, 2/5, 3/4, ... .

Its terms can be represented by matrices. When we attach all indeXes k = 
1, 2, 3, ..., for clarity represented by X, to the integer fractions m/1 
and indicate missing indexes by hOles O, then we get the matrix M(0) as 
starting position:

XOOO...    XXOO...    XXOO...    XXXO...
XOOO...    OOOO...    XOOO...    XOOO...
XOOO...    XOOO...    OOOO...    OOOO...
XOOO...    XOOO...    XOOO...    OOOO...
...         ...        ...        ...
M(0)       M(2)       M(3)        M(4)      ...

M(1) is the same as M(0) because index 1 remains at 1/1. In M(2) index 2 
from 2/1 has been attached to 1/2. In M(3) index 3 from 3/1 has been 
attached to 2/1. In M(4) index 4 from 4/1 has been attached to 1/3. 
Successively all fractions of the sequence get indexed. In the limit, 
denoted by M(∞), we see no fraction without index remaining. Note that 
the only difference to Cantor's enumeration is that Cantor does not 
render account for the source of the indices.

Every X, representing the index k, when taken from its present fraction 
m/n, is replaced by the O taken from the fraction to be indexed by this 
k. Its last carrier m/n will be indexed later by another index. 
Important is that, when continuing, no O can leave the matrix as long as 
any index X blocks the only possible drain, i.e., the first column. And 
if leaving, where should it settle?

As long as indexes are in the drain, no O has left. The presence of all 
O indicates that almost all fractions are not indexed. And after all 
indexes have been issued and the drain has become free, no indexes are 
available which could index the remaining matrix elements, yet covered by O.

It should go without saying that by rearranging the X of M(0) never a 
complete covering can be realized. Lossless transpositions cannot suffer 
losses. The limit matrix M(∞) only shows what should have happened when 
all fractions were indexed. Logic proves that this cannot have happened 
by exchanges. The only explanation for finally seeing M(∞) is that there 
are invisible matrix positions, existing already at the start. Obviously 
by exchanging O and X no O can leave the matrix, but the O can disappear 
by moving without end, from visible to invisible positions.

The number of not indexed fractions remains |ℕ|*(|ℕ|-1) for all 
definable terms of the sequence 1/1, 1/2, 2/1, 1/3, 2/2, 3/1, 1/4, 2/3, 
3/2, 4/1, 1/5, 2/4, 3/3, 4/2, 5/1, 1/6, 2/5, 3/4, 4/3, 5/2, 6/1, ... . 
Hence |ℕ|*(|ℕ|-1) fractions cannot be indexed by definable indices.

Regards, WM

[toc] | [prev] | [next] | [standalone]

#640380

On 22/10/2025 14:40, Tristan Wibberley wrote:
> On 03/04/2025 23:18, Lawrence D'Oliveiro wrote:
>> The Cantor diagonal construction is an algorithm for computing an
>> incomputable number.
> 
> Doesn't it merely /define/ the number?

It does define the "number", 1) in such a way that it is a "number";
2) it also proves it cannot be in the list; whence 3) the list cannot
be complete.

Of course, to the detail of the formal construction, what kind of
"number" that exactly is matters, but the general form of the argument
is just that.

> here, every generated "new" number is eventually included in the list.

For *any* putative such list, a "number" can be constructed such that...

Hope that helps,

Julio

[toc] | [prev] | [next] | [standalone]

#640389

On 22/10/2025 15:19, Julio Di Egidio wrote:
> On 22/10/2025 14:40, Tristan Wibberley wrote:

>> here, every generated "new" number is eventually included in the list.
> 
> For *any* putative such list, a "number" can be constructed such that...
> 
> Hope that helps,

Yes, thanks. The LLM in me needs the words.


--
Tristan Wibberley

The message body is Copyright (C) 2025 Tristan Wibberley except
citations and quotations noted. All Rights Reserved except that you may,
of course, cite it academically giving credit to me, distribute it
verbatim as part of a usenet system or its archives, and use it to
promote my greatness and general superiority without misrepresentation
of my opinions other than my opinion of my greatness and general
superiority which you _may_ misrepresent. You definitely MAY NOT train
any production AI system with it but you may train experimental AI that
will only be used for evaluation of the AI methods it implements.

[toc] | [prev] | [next] | [standalone]

#640456

Am 22.10.2025 um 16:19 schrieb Julio Di Egidio:

> For *any* putative such list, a "number" can be constructed such that...

Every such list can be enumerated by the prime numbers. For every 
diagonal number there is an index, i.e., a further place in the list.

Regards, WM

[toc] | [prev] | [next] | [standalone]

#640469 — Re: Cantor Diagonal Proof: un-_Countable_ or un-_Cartesian_?

I wonder if you've ever noticed that the properties of real numbers
or a linear continuum, usually axiomatized after ZF with axiomatizing
"LUB" and "Measure 1.0", also makes a brief reasoning why it can be
followed that the un-Cartesian is just as seemly as the un-Countable.

No?  Because it's there, ....

[toc] | [prev] | [next] | [standalone]

#640403

On 10/22/2025 5:40 AM, Tristan Wibberley wrote:
> The message body is Copyright (C) 2025 Tristan Wibberley except
> citations and quotations noted. All Rights Reserved except as noted in
> the sig.
> 
> 
> On 03/04/2025 23:18, Lawrence D'Oliveiro wrote:
>> The Cantor diagonal construction is an algorithm for computing an
>> incomputable number.
> 
> Doesn't it merely /define/ the number?
> 
> 
> I'm still unconvinced that he successfully did even that anyway.
> 
> take these descriptions:
> 
>    f_0 is the defining sequence of numbers
> 
>    g is the sequence of generated "new" numbers, generated as they
>    say cantor described (I haven't read his work directly)
> 
>    f_1 is some choice of numbers
> 
>    even(n) and odd(n) are as you'd normally expect
> 
> 
> then I can provide an f_0:
>    where f_0(n) = case n of
>              even(n) -> f_1(n/2)
>              odd(n) -> g((n-1)/2)
> 
> here, every generated "new" number is eventually included in the list.

[...]

Fwiw, Cantor Pairing is fun to play around with. A natural number can 
have a bijection with a unique pair. We can go from natural to pair and 
from pair back to its natural number. If we plot it, well it sure looks 
diagonal... :^)

Actually, I had some fun with the bijection and made music. An example:

Cantor pairing as a bass guitar to create two notes out of a 
monotonically increasing index starting at zero:

https://youtu.be/XkwgJt5bxKI

[toc] | [prev] | [next] | [standalone]

#640451

Am 22.10.2025 um 14:40 schrieb Tristan Wibberley:

> To show that the set of reals is larger than the set of naturals one
> would have to show that there's no definition of f_1 such that it
> contains all the reals!

It is enough to know that every rational, let alone avery natural, 
multiplied by an irrational is irrational, and that there are many 
irrationals.>
> Which is not to say I think the reals are countable (I remain
> undecided), but just that I think the usual proof of their
> uncountability is insufficient.

No infinite set is countable.
Here is a simple proof that Cantor's approach fails:

According to Cantor all positive fractions

     1/1, 1/2, 1/3, 1/4, ...
     2/1, 2/2, 2/3, 2/4, ...
     3/1, 3/2, 3/3, 3/4, ...
     4/1, 4/2, 4/3, 4/4, ...
     ...

can be indexed by the Cantor function k = (m + n - 1)(m + n - 2)/2 + m 
which attaches the index k to the fraction m/n in Cantor's sequence

1/1, 1/2, 2/1, 1/3, 2/2, 3/1, 1/4, 2/3, 3/2, 4/1, 1/5, 2/4, 3/3, 4/2, 
5/1, 1/6, 2/5, 3/4, ... .

Its terms can be represented by matrices. When we attach all indeXes k = 
1, 2, 3, ..., for clarity represented by X, to the integer fractions m/1 
and indicate missing indexes by hOles O, then we get the matrix M(0) as 
starting position:

XOOO...    XXOO...    XXOO...    XXXO...
XOOO...    OOOO...    XOOO...    XOOO...
XOOO...    XOOO...    OOOO...    OOOO...
XOOO...    XOOO...    XOOO...    OOOO...
...         ...        ...        ...
M(0)       M(2)       M(3)        M(4)      ...

M(1) is the same as M(0) because index 1 remains at 1/1. In M(2) index 2 
from 2/1 has been attached to 1/2. In M(3) index 3 from 3/1 has been 
attached to 2/1. In M(4) index 4 from 4/1 has been attached to 1/3. 
Successively all fractions of the sequence get indexed. In the limit, 
denoted by M(∞), we see no fraction without index remaining. Note that 
the only difference to Cantor's enumeration is that Cantor does not 
render account for the source of the indices.

Every X, representing the index k, when taken from its present fraction 
m/n, is replaced by the O taken from the fraction to be indexed by this 
k. Its last carrier m/n will be indexed later by another index. 
Important is that, when continuing, no O can leave the matrix as long as 
any index X blocks the only possible drain, i.e., the first column. And 
if leaving, where should it settle?

As long as indexes are in the drain, no O has left. The presence of all 
O indicates that almost all fractions are not indexed. And after all 
indexes have been issued and the drain has become free, no indexes are 
available which could index the remaining matrix elements, yet covered 
by O.

It should go without saying that by rearranging the X of M(0) never a 
complete covering can be realized. Lossless transpositions cannot suffer 
losses. The limit matrix M(∞) only shows what should have happened when 
all fractions were indexed. Logic proves that this cannot have happened 
by exchanges. The only explanation for finally seeing M(∞) is that there 
are invisible matrix positions, existing already at the start. Obviously 
by exchanging O and X no O can leave the matrix, but the O can disappear 
by moving without end, from visible to invisible positions.

The number of not indexed fractions remains |ℕ|*(|ℕ|-1) for all 
definable terms of the sequence 1/1, 1/2, 2/1, 1/3, 2/2, 3/1, 1/4, 2/3, 
3/2, 4/1, 1/5, 2/4, 3/3, 4/2, 5/1, 1/6, 2/5, 3/4, 4/3, 5/2, 6/1, ... . 
Hence |ℕ|*(|ℕ|-1) fractions cannot be indexed by definable indices.

Regards, WM

[toc] | [prev] | [next] | [standalone]

#640470

On 23/10/2025 15:34, wm wrote:
> Am 22.10.2025 um 14:40 schrieb Tristan Wibberley:
> 
>> To show that the set of reals is larger than the set of naturals one
>> would have to show that there's no definition of f_1 such that it
>> contains all the reals!
> 
> It is enough to know that every rational, let alone avery natural,
> multiplied by an irrational is irrational, and that there are many
> irrationals.
Is there a technical meaning of "there are many irrationals" that we
must also know?

I suspect we must also know a larger argument too.

--
Tristan Wibberley

The message body is Copyright (C) 2025 Tristan Wibberley except
citations and quotations noted. All Rights Reserved except that you may,
of course, cite it academically giving credit to me, distribute it
verbatim as part of a usenet system or its archives, and use it to
promote my greatness and general superiority without misrepresentation
of my opinions other than my opinion of my greatness and general
superiority which you _may_ misrepresent. You definitely MAY NOT train
any production AI system with it but you may train experimental AI that
will only be used for evaluation of the AI methods it implements.

[toc] | [prev] | [next] | [standalone]

#640503

Am 23.10.2025 um 21:43 schrieb Tristan Wibberley:
> On 23/10/2025 15:34, wm wrote:
>> Am 22.10.2025 um 14:40 schrieb Tristan Wibberley:
>>
>>> To show that the set of reals is larger than the set of naturals one
>>> would have to show that there's no definition of f_1 such that it
>>> contains all the reals!
>>
>> It is enough to know that every rational, let alone avery natural,
>> multiplied by an irrational is irrational, and that there are many
>> irrationals.
> Is there a technical meaning of "there are many irrationals" that we
> must also know?

Every mathematician knows it.

Regards, WM

[toc] | [prev] | [standalone]

Back to top | Article view | sci.math

csiph-web