problem with cantor diagonal argument

JeffJo · July 12, 2023

Nor will I call Russell's restrictions on how to set up the first part of that a "howler" simply because you think they don't allow for the list to be uncountable. They are supposed to do that, in part #1. I do think it wasn't necessary to do so, all he needed was to establish that (A) such lists were possible and (B) we can reference the nth character in the nth string.

wtf · July 12, 2023

10 hours ago, JeffJo said:

I've described it several times.

Ok well I guess I'm done, I can't explain this any better. Regarding the quote of mine that you object to, I stand by it 100%.

4 hours ago, JeffJo said:

Nor will I call Russell's restrictions on how to set up the first part of that a "howler" simply because you think they don't allow for the list to be uncountable.

I "think" that? You disagree with Turing's 1936 paper?

I would ask how you think "laws," interpreted as algorithms or effective procedures, can generate uncountably many distinct symbol strings. But they can't, so asking that question would not be productive.

There are countably many Turing machines. They can generate only countably many distinct symbol strings over a finite or countably infinite alphabet. Russell didn't know that and he didn't think about it. His error entirely invalidates his version of the CDA unless, being charitable, we ignore it.

You can have the last word. You are now denying a universally accepted 87 year old result.

If it helps at all, I have not followed the details of your discussion with @phyti nor the details of Cantor's original argument. I have only discussed Russell's technical error in the passage you quoted to me. So your protestations that I'm missing the same point as @phyti and Cantor are misplaced. I don't even know what that conversation is about and have not discussed it.

Edited July 12, 2023 by wtf

JeffJo · July 13, 2023

12 hours ago, wtf said:

Ok well I guess I'm done, I can't explain this any better. Regarding the quote of mine that you object to, I stand by it 100%

You don't need to explain - I understood it from the start. You are not understanding mine.

The restrictions Russell places, are placed on elements that he requires to comprise a countable set. Your objection is misplaced, because what you object to is that he cannot generate an uncountable set under those restrictions. That is irrelevant.

12 hours ago, wtf said:

His error entirely invalidates his version of the CDA unless, being charitable, we ignore it.

In what way does describing how to generate a countable set invalidate the countable set that is generated? I'm not trying to "get the last word." I am asking a legitimate question about what you keep repeating. I am pointing out exactly what I think it is that you are either not seeing, or ignoring.

CDA only ever makes use of a countable set.
CDA proves that any such countable set cannot be the full set M (whose countability is not yet determined).
Only after drawing a conclusion about countable sets, does Cantor conclude that M is uncountable. Because any subset that is countable - and as you seem to admit can be generated by the rules he described - is missing at least one element of M.

And again, since you keep missing it, the rules Russell describes are never associated with the entirety of an uncountable set.

12 hours ago, wtf said:

I have only discussed Russell's technical error in the passage you quoted to me.

No, you have discussed it for a version of that passage that is different than what Russell wrote.

I don't know how I can make this any clearer:

Russell's passage describes a countable set.
- Literally, "For let us take any denumerable collection of E’s..."
The passage places restrictions on how to generate this countable set.
- The only place these restrictions are used is for this "collection of E's."
You say it is an error because these restrictions cannot generate an uncountable set.
- I understand why it would be an error, if the passage was trying to generate an uncountable set.
- I don't understand why you think it is an error when it only needs to generate a countable set.
- I am suggesting that you, like phyti and what I believe is at least 99% of the people who think they understand CDA, do not fully realize that CDA is only ever applied to a countable set.

Edited July 13, 2023 by JeffJo

phyti · July 13, 2023

;
It's not about numbers, real, imaginary, or otherwise. It's not about surjection, injection, objection, or any similar forms. It's definitely not about subsets. By definition they contain less elements than their set of origin. That doesn't require a proof. Anyone who thinks Cantor was describing subsets, questions Cantor's abilities.

From reading his philosophy paper on set theory: He is considering a heirarchy of infinite sets, each as a complete independent thing. As an abstract concept in the field of pure mathematics, they do not require any type of physical correspondence.

I have never seen anyone state a list is the same as the set M. A list is only a visual aid for the purpose of understanding. Cantor nor anyone else has such a list. He shows a sample of an incomplete list of incomplete sequences. That's why the ellipsis ... was invented, to project a thought and move on.

My issue is more about logic than anything else.

To paraphrase Cantor (substituting for m & w)

"Set M contains all possible infinite sequences {E1, E2, E3, ...} composed of 0's and 1's."

and before he defines his diagonal

"the set M does not have the 'power' (cardinality) of N the natural numbers."

thus no one to one correspondence.

The set M can be divided into 2 subsets, M0 and M1

M0

0000...

0101...

0011...

0110...

D=0110...

E0=1001...

Cantor declares E0 is not in M.

It is a sequence but can't be in the list.

It can't be a member and not a member.

error 1.

It's a sequence of 0's and 1's, but oriented at 45º to the horizontal sequences,

thus it intersects all horizontal sequences, where no other sequence does so,

the points of intersection only allow one symbol, so E0 is excluded from the list by the introduction of the diagonal. Before the diagonal, the sequences are independent of each other.

error 2.

The standard convention for the printed page is horizontal rows of text, extending vertically in a 2 dimensional format. A diagonal row of characters would have no meaning relative to the context of the page.

error 3.

For whatever reason, he made his own contradiction, by not recognizing the complementary properties of binary sequences. If a sequence has each symbol swapped for the other, it becomes the complement of the first, i.e. they exist in pairs.

This is evident if M1 is compared side by side with M0. E0 (blue) is a member of M1.

E0 being a member of M1 and not a member of M0 is not a contradiction.

Also note in M0, the 4th sequence is a duplicate of the diagonal. Cantor could not detect it unless he compared every position after the intersection!

With the introduction of a single diagonal sequence, Cantor presented a self fulfilling prophecy. That would be appropriate, since he claimed his idea had a divine origin.

M1

1111...

1010...

1100...

1001...

JeffJo · July 13, 2023

1 hour ago, phyti said:

It's not about numbers, real, imaginary, or otherwise. It's not about surjection, injection, objection, or any similar forms. It's definitely not about subsets. By definition they contain less elements than their set of origin. That doesn't require a proof. Anyone who thinks Cantor was describing subsets, questions Cantor's abilities.

"It", meaning the diagonalization process, is about what subsets (and subsets can be "improper," meaning they equal the parent set) of Cantor's set M can be put into a surjection from the set N={1,2,3,...v, ...}. That is literally what this means:

"If E1, E2, …, Ev, … is any simply infinite [sequence] of elements of the manifold M ..."

What "it" is about, is the conclusion he proves, and that you doubt:

"... then there always exists an element E0 of M, which cannot be connected with any element Ev."

What "it" is used for, is this corollary:

"From this proposition it follows immediately that the totality of all elements of M cannot be put into the sequence: E1, E2, …, Ev, … otherwise we would have the contradiction, that a thing E0 would be both an element of M, but also not an element of M."

What CDA is not about, is anything Cantor said in a paper about his philosophy. This is a different paper entirely. Drop it.

1 hour ago, phyti said:

I have never seen anyone state a list is the same as the set M. A list is only a visual aid for the purpose of understanding.

A list is not the same as a set, and it is not "only a visual aid." It is the tool by which Cantor constructs the element he calls E0.

A list is a surjective function from a set of consequential natural numbers {1,2,3,...v} or {1,2,3,...v...} to the set of interest. It usually is injective also, but that is not necessary here. And, while it may seem to be implied, Cantor did not require it. Russel did.

1 hour ago, phyti said:

My issue is more about logic than anything else.

Your issue is that you do not understand CDA, and you find it non-intuitive. So you look for statements that could be wrong without bothering to verify that those statements exist in CDA. They do not.

1 hour ago, phyti said:

"the set M does not have the 'power' (cardinality) of N the natural numbers."

thus no one to one correspondence.

These statements are part of the narrative describing what he wants to accomplish, not the proof itself. Regardless of how you choose to misinterpret them, they have no bearing on the errors you think you see.

1 hour ago, phyti said:

The set M can be divided into 2 subsets, M0 and M1

Sure. Irrelevant to CDA, but they can. The more appropriate division of sets are E, (my name for the subset he puts into a list; that is, E1, E2, E3, ..., Ev, ...) and M-E, the elements in M but not in E.

The important observation is that E is countable, but at this point M and M-E may or may not be.

1 hour ago, phyti said:

Cantor declares E0 is not in M.

By using the list structure you called "only a visual aid", Cantor constructs an element E0 that is proven to not be in E.

1 hour ago, phyti said:

It is a sequence but can't be in the list.

It can't be a member and not a member.

error 1.

It is not a sequence, it is an element. It is member of M but not a member of E which is put into a sequence. No error here.

1 hour ago, phyti said:

It's a sequence of 0's and 1's, but oriented at 45º to the horizontal sequences, ...

error 2.

Get the terminology straight. Cantor calls the members of M "elements," not "sequences." Another possible name is "string." "Sequence" means the list of these elements that make the list you deny is important.

There is no meaningful context for orientations of sequences, or strings.

No error.

1 hour ago, phyti said:

A diagonal row of characters would have no meaning relative to the context of the page.

error 3.

Exactly. This word "diagonal" has no meaning to the proof. It is only the visual aid you misinterpret.

No error.

The contradiction is not a part of diagonalization. It is the "corollary" I listed above.

Edited July 13, 2023 by JeffJo

JeffJo · July 14, 2023

I don't think I emphasized this lie enough in my point-by-point debunk of phyti's complete misrepresentation of CDA:

20 hours ago, phyti said:

Cantor declares E0 is not in M.

It is a sequence but can't be in the list.

It can't be a member and not a member.

As a recap, Cantor first defines the set M. (I'm adding the emphasis - bold italic - to indicate an infinite set. This distinguishes the symbol for a set from those representing its elements.) It is the set of all possible binary strings. He is consistent in calling each such string an "element," not a "sequence," and he uses either E or Ev (where v is a natural number) for these elements.

What Cantor does, is first say that that he is using only a subset of M, which I call E, that has the property that it can be put into an infinite list E1, E2, ... Ev, ... . Cantor never says whether this set E does, or does not, represent all of M. Only that it is countable. Phyti seems to think it does, and keeps implying that E=M without having the integrity to come out and say that this is what his claims are based on.

Cantor then uses the algorithm that was, only after his proof, called his" Diagonal Argument." Or CDA. He uses it to construct the element (or string) he names E0:

"Then consider the element E0 = (b1, b2, b3, …) of M ... " (you all know the rest).

Please note that Cantor explicitly says that E0 is an element of M. This fact can't be missed. What phyti is lying about (I don't believe that he lacks the ability to understand this, so he must be intentionally misrepresenting it) is this:

"The equation E0 = Ev cannot be satisfied by any positive integer v."

In the quote at the top of this reply, phyti is claiming that in this sentence "Cantor declares E0 is not in M." Cantor is not saying that. Cantor is explicitly saying that E0 is not in E, the set listed in E1, E2, ... Ev, ... . The only way phyti's interpretation is true, is if we require E=M. That is never a requirement in the proof. If we admit that it is not in the proof, phyti's entire argument evaporates.

The lie is refusing to recognize that (A) Cantor defined E as having elements from M, not being equal to M, (B) Cantor makes this crystal clear by saying that E0 is in E but not in M. and (C) then having the audacity to insist that Cantor is saying that E0 both is, and is not, a member of M when no such statement is made. in this part of the proof.

It is made later, to prove that any that E meets the countability requirement cannot ever be equal to M. In other words, the very contradiction that phyti claims debunks CDA, is what it uses correctly to prove that there are uncountable sets.

Edited July 14, 2023 by JeffJo

phyti · July 15, 2023

Jeff;
I only read what Cantor wrote.

Your interpetation is distorted.

Cantor used the 2-dimensional coordinate system, u for row and v for column.

The letter s will stand for sequence/string.

The symbols 0 and 1 have coordinates (u,v).

For the horizontal s, u is constant equal to 9 and v varies as (1, 2, 3, ...).

For the diagonal s, u varies as (11, 12, 13, ...) and v varies as (1, 2, 3, ...).

They are different things with different properties.

A case of basic geometry.

JeffJo · July 15, 2023

1 hour ago, phyti said:

Jeff;
I only read what Cantor wrote.

Your interpetation is distorted.

No you didn't. You read looking for something you wanted to see, and you added it. My interpretation is exact.

1 hour ago, phyti said:

Cantor used the 2-dimensional coordinate system, u for row and v for column.

Yes he did. But a better description is that row u is the "element" E_u that is a string in the set M. (And note that he mixes u and v up sometimes). What you want to add seems to be that every element of M is associated with a natural number u, and that simply is not true.

1 hour ago, phyti said:

Then consider the element

E0 = (b1, b2, b3, …)

of M,

Then consider the element

E0 = (b1, b2, b3, …)

of M,

Then consider the element

E0 = (b1, b2, b3, …)

of M,

The letter s will stand for sequence/string.

Cantor's "sequence" is the list E₁, E₂, …, E_u, … . It is not a string - he never uses that word, but modern version do for what Cantor calls an "element." In other words, "sequence" and "string" mean different things, so this is a very confused statement that dose not correspond to Cantor.

1 hour ago, phyti said:

The symbols 0 and 1 have coordinates (u,v).

No, the coordinate pair (u,v) references either an 'm' or a 'w'. If you want to use Wikipedia, they don't refer to coordinates, per se, but do use '0' and '1'. If you ant to claim you are using Cantor, please stick to one nomenclature, or indicate (as I try to do) which and how it fits with the other.

1 hour ago, phyti said:

For the horizontal s, u is constant equal to 9 and v varies as (1, 2, 3, ...).

I have no idea what this gibberish (and what follows) is supposed to mean. Why does '9' get into it? This bears no relationship to anything Cantor did. This does:

For proof, let there be

E1 = (a1.1, a1.2, … , a1,v, …)

E2 = (a2.1, a2.2, … , a2,v, …)

Eu = (au.1, au.2, … , au,v, …)

………………………….

where the characters au,v are either m or w.

Meaning: E1, E2, ..., Eu ... is a list of elements from M. Not a list of every element in M. I call this set of Eu the set E. It is a subset of M, but at this point it may be an improper subset (meaning all of M).

Then there is a series b1, b2, … bv,…, defined so that bv is also equal to m or w ...
... if av.v = m, then bv = w

And by implication, if av.v = w, then bv = m.

Meaning: This is a new series of characters that fits the definition of an element in M. Cantor calls this new element E0, not s. But, while Wikipedia does call it s, it is not your s. Yours starts at "coordinates" (11,1). This really doesn't matter, except that you are not using Cantor.

then one sees straight away, that the equation

E0 = Eu

cannot be satisfied by any positive integer u.

Meaning: E0 is not in E. But, from above, it is in M. This is not a contradiction, since nowhere, so far, does Cantor say E=M.

This proves the "proposition" that CDA wants (and I fixed the mixed-up uses of u and v):

If E1, E2, …, Eu, … is any simply infinite series of elements of the manifold M, then there always exists an element E0 of M, which cannot be connected with any element Eu."

That's it. That's CDA. It does not do this:

2 hours ago, phyti said:

For the diagonal s, u varies as (11, 12, 13, ...) and v varies as (1, 2, 3, ...).

They are different things with different properties.

A case of basic geometry.

There is no "geometry" in Cantor. You can't find any words in Cantor that have that meaning. What you refer to is, indeed, the visual aid you claimed others use.

Cantor never draws a diagonal. Not one starting at (1,1), nor one starting at (11,1). There is no property associated with being a "diagonal," other than it also being a string. You can't find any words in Cantor that "define it as a different thing with different properties."

In fact, the closes he comes is to say it is the same kind of thing. I left that out above so I could put it here:

Then consider the element

E0 = (b1, b2, b3, …)

of M,

These b's come from the characters you can find along a diagonal (but again, Cantor never used that word).

Now, if you think any of this is wrong, please point to the words in Cantor that confirm your opinion.

wtf · July 16, 2023

On 7/13/2023 at 4:22 AM, JeffJo said:

The restrictions Russell places, are placed on elements that he requires to comprise a countable set. Your objection is misplaced, because what you object to is that he cannot generate an uncountable set under those restrictions. That is irrelevant.

Your latest post is very clear and I understand you much better now.

I want to get to my other mentions on a couple of other threads before I write a detailed reply. If it takes me longer than expected just wanted to let you know that a response is all the way.

I'll just say here that your post caused me to have a good think about all this; after which I am more certain than ever that Russell has undermined his own argument. What he has proven is that either:

(a) If his initial list contains all computable numbers, then he's just shown that there exists a noncomputable number (namely the antigiagonal). But for all we know the reals are still countable, so he hasn't proved the reals are uncountable; or

(b) If his initial list was just a countably infinite list containing some[/i] computable numbers, then all he proved is that the antidiagonal is some other real, maybe computable or maybe not.

The core problem is that by restricting attention in the initial list to only computable reals, the argument falls apart.

Only by starting with an arbitrary list of reals, as Cantor does, do we conclude that the antidiagonal is a real not on the list; thereby showing that no list of reals can contain all of them. Therefore the reals are uncountable.

So Russell's casual use of the word law destroys his entire argument, and fails to prove the reals are uncountable.

Now that I think of it, this little summary is actually a concise exposition of what I wanted to say. I was going to add in some background on computable real numbers, but I think I'll just leave it at this for now and see if you have any feedback to what I wrote here. So nevermind that I'll post something better later, I'll go with this for now.

And like I say, the charitable thing to do is just ignore Russell's law remark and just go with the spirit of the proof. I'm fine with that. But if you are saying my objection is not relevant, then I have to reiterate that it is highly relevant. By restricting the rows to be computable reals, all the diagonal argument shows is that there's some other real not on the list, which may be noncomputable. But that proves nothing about the countability or uncountability of the reals.

To show the uncountability of the reals it's necessary to allow the initial list to be an arbitrary list of real numbers. Restricting the list to only contain computable numbers (that is, numbers whose digits are chosen according to some particular law) wrecks the proof. It does prove something else, namely that there exists a noncomputable real number. But that's not what we're trying to prove.

Edited July 16, 2023 by wtf

studiot · July 16, 2023

@wtf

I was suprised to see that you are apparantly not even parsing the contributions of others here.

It seems to me that everyone is concentrating on too narrow a view.

It would be better to take a long term overview sincenot only was Set Theory not built in a day, but it has changed dramatically over more than 2 centuries.

Cantor did not wite it down all at once.

I am posting to short extracts from the Stanford Encyclopedia which are highly relevant to this discussion.

sets1.jpg.ff5265236dd041fff76031a8e5c5b947.jpg

Noting the years 1850 to 1930 as critical, though we could easily extend this timeline by 50 years or more if we wish to included the Bolzano theorem (1817) Cantor relied so heavily on for his first proofs or we wish to discuss computability which came well after Cantor's death and which is still a busy area of active reserch and debate.

@phyti

Simply declaring Cantor was wrong is not enough. He modified his theories quite substantially as he went along, and that process contues today.

Here is his significant breakthrough, when he was first experimenting with sets and did not know about many infinities.

Sets2.jpg.49798a3ff95ef95626b85ad1e9888043.jpg

In realising that the set of real numbers must be somehow bigger than the set of natural numbers he kick-started the whole thing off.

Here is the link to the full Plato article

https://plato.stanford.edu/entries/settheory-early/

wtf · July 17, 2023

16 hours ago, studiot said:

I was suprised to see that you are apparantly not even parsing the contributions of others here.

The OP, @phyti, has been making this same argument for years on various online forums. I have no interest in arguing the subject.

I only suggested that rather than try to slog through a translation of 19th century German academic prose, he might find a more contemporary account more sensible. He responded that he finds contemporary accounts of the CDA equally objectionable. That closed the subject as far as I was concerned. I am not debating CDA.

@JeffJo then suggested the Russell quote, which unfortunately contained a material error. Rather than take the sensible approach, to say that Russell just mis-spoke himself and we should ignore the error, @JeffJo has taken the view that Russell's restriction of the elements of the list to be symbol strings that can be generated by a law -- that is, computable strings -- does not fatally compromise the argument. It does, and I've pointed that out.

I have no interest in unpacking the OP's issues with the CDA. My focus is intentionally narrow.

Edited July 17, 2023 by wtf

studiot · July 18, 2023

On 7/17/2023 at 7:00 AM, wtf said:

The OP, @phyti, has been making this same argument for years on various online forums. I have no interest in arguing the subject.

I only suggested that rather than try to slog through a translation of 19th century German academic prose, he might find a more contemporary account more sensible. He responded that he finds contemporary accounts of the CDA equally objectionable. That closed the subject as far as I was concerned. I am not debating CDA.

@JeffJo then suggested the Russell quote, which unfortunately contained a material error. Rather than take the sensible approach, to say that Russell just mis-spoke himself and we should ignore the error, @JeffJo has taken the view that Russell's restriction of the elements of the list to be symbol strings that can be generated by a law -- that is, computable strings -- does not fatally compromise the argument. It does, and I've pointed that out.

I have no interest in unpacking the OP's issues with the CDA. My focus is intentionally narrow.

Thank you for your reply.

I would just like to point out that there are many other members interested in the subject as evidenced by their occasional posts and the best part of two thousand views.

The diagonalisation argument is a direct result of the fact that there are more real numbers than there are natural numbers, even though both are transfinite.

The ramifications of this fact are enormous and widespread so it is a good idea to review them and note the relevant ones.

One area where phyti has already made a misstatement is that it means that for many sets, a set with more members that the original may be constructed.
This was not fully grasped at the time of diagonalisation.

But the killer conclusion is that it is not possible to form a list of all the real numbers, or even all the real numbers in a finite interval.

This conclusion is the essence of diagonalisation.

But because of this also leads to ideas of density and completenessnd more structure, there are other ways to prove the result.

That this all hangs together is gives further support to the belief that we are on the right track, even though we know we haven't finished yet.

There are still more queastions to be asked and resolved.

wtf · July 18, 2023

11 hours ago, studiot said:

I would just like to point out that there are many other members interested in the subject as evidenced by their occasional posts and the best part of two thousand views.

Yes I agree. It's one of the most popular math topics online.

However, "alternative" aka cranky discussions abound on this topic, probably (in my opinion) because it's one of the simplest math stories that is quite counterintuitive. So it gets a lot of play online, and it's also a crank magnet.

I'm a grizzled internet veteran so I try not to get too involved in Cantor threads just as I avoid .999... = 1 threads. Just been in too many of these discussions over the years. In fact I'm all-to-eager to jump in to these kinds of discussions, which is why I try to avoid them.

So I agree with you that a lot of people are interested, and I hope you understand why I've mostly given this thread a pass. I gave at the office, as it were.

11 hours ago, studiot said:

The diagonalisation argument is a direct result of the fact that there are more real numbers than there are natural numbers, even though both are transfinite.

My picky self has a couple of quibblets here. First, the diagonal argument is a proof, not a "result," of the fact that there's an injection but not a surjection from the naturals to the reals.

But when you say, "There are more real numbers than natural numbers," in my opinion this phrasing is one of the leading causes of confusion among people. Because "more than" is being overloaded with a specific technical meaning that does not necessarily correspond with the everyday meaning of the phrase.

When we say there are "more reals than naturals," what we mean, by definition, is that

* There is an injection from [math]\mathbb N \to \mathbb R[/math]; and

* There is no surjection from [math]\mathbb N \to \mathbb R[/math]

With those definitions clearly having been stated and explained, THEN we can casually say "more than," knowing that our listener will hear, or can be trained to hear, the technical definition in their head.

But without that technical preparatory work, we are swindling the naive listener a bit, by telling them something that sounds impossible, based on the everyday meaning of "less than" or "smaller than."

In fact it's manifestly nonsense that any infinite set is less than or smaller than some other infinite set, until we specify the context

We might be talking about cardinality :|[0,1]| = |[0,2]|; or measure, or Euclidean length: m[0,1] = 1/2 m[0,2], or asymptotic density: the evens occur half the time in the naturals, or the subset relationship: the evens are a proper subset of the naturals, or some other way of characterizing the sizes of infinite sets that mathematicians have devised.

So for these reasons, I object to the casual claim that one infinite set is "smaller than" another, unless you note that you are using the phrase in its technical sense of an injection but no surjection.

Well you asked for my input and there you go :-) A little mini-rant about telling the uninitiated that one infinite set is "smaller than" another, without pointing out that "smaller than" is a term of art in the math biz. It doesn't mean what it does in every day natural language. And that when spoken to a naive listener, it obfuscates more than it elucidates. So I'm against this particular lack of clarity. One should always make it clear that "less than" or "smaller" are true in a technical sense, once the proper definitions have been made; and likewise for "greater than" or "larger."

Edited July 18, 2023 by wtf

JeffJo · July 19, 2023

On 7/17/2023 at 2:00 AM, wtf said:

@JeffJo then suggested the Russell quote, which unfortunately contained a material error. Rather than take the sensible approach, to say that Russell just mis-spoke himself and we should ignore the error, @JeffJo has taken the view that Russell's restriction of the elements of the list to be symbol strings that can be generated by a law -- that is, computable strings -- does not fatally compromise the argument. It does, and I've pointed that out.

And I still think you do not understand my point. Which was only that "Russell's restriction of the elements of the list" does not invalidate the construction of such lists. Not that there can't be an issue with the uncountability proof, WHICH IS A COROLLARY TO CDA. And the reason for making this subtle distinction, between CDA and this corollary, is that almost every objection to CDA that I have seen is based on misunderstanding it.

The sets used in the "diagonalization argument" part of the proof, are always sets that are denumerable. The full set M may or may not be. (And btw, M never contains real numbers, and CDA never mentions real numbers in any context except to say they aren't used. I know that there are relationships between the two, but I feel the discussions of CDA need to be about strings.)

So a restriction that limits these lists to denumerable sets is not, by itself, a problem. But I also said that Russell went too far by stating this restriction, because we now know that there elements in his set M that cannot meet the restrictions. What I said was that his restrictions seemed necessary to him at the time he wrote it, in order to have access to all of the characters a_n,n.

Where the potential problem lies is in the difference between L, the set of strings that can be found by his laws, and the set M that contains all strings. This isn't my area, but by my understanding what CDA (the actual argument, without the corollary) says is that applying diagonalization to any infinite list containing elements of L will produce a string that is not listed. Whether or not this string is in L is open to debate as far as I know, since it is "found in some determinate manner" but not in a finite number of steps like what your objection is based on. Maybe this is where we aren't seeing the objection the same way?

If it is in L, it proves that L is uncountable, as shown in the corollary. The L that you think his restrictions define is countable. So the "finite steps" part seems like the issue. All that theory comes post-Russell, and I agree he didn't know the ramifications. Or consider that there could be. I just don't think your arguments apply in the way you think they do.

But I remind you, again, that this proof was never meant to be a formal proof. It is an example of Cantor's Theorem, that the power set of any set A has a greater cardinality than set A.

Edited July 19, 2023 by JeffJo

phyti · July 19, 2023

Jeff;

He doesn't have to use the word 'diagonal' when that is what he describes.

If Cantor uses 2-dimensional coordinates, he is using geometry, whether you recognize it or not.

Cantor showed a partial list because that's all he had. There is no complete list. He is asking the reader to imagine of pretend it exists. Consider N the natural/counting integers. There is no greatest integer, thus no one will ever see a complete list of N. A complete list of an infinite set is a contradiction of terms. It is always incomplete, since there is no last term.

Which brings us to the real world of finiteness. Objects have boundaries which allow measurement. A sequence (ordered set of elements) can be modeled as a rod of constant cross section with a definite length x. To measure x, the zero end of a tape is fixed at the near end, and x = the nearest mark on the tape that coincides with the far end. For astronomical distances light is a better method. An emitter is fixed at the near end of the 'infinite' (latin for 'no boundary') sequence/rod. Where is the far end with a reflector?

There is none, and that is why 'infinite' also means immeasurable. The methods of measurement were developed for applications in a world of finite objects. They don't work for objects without boundaries.

Then there is empty. A container can be empty, but it can't be emptier. There is no superlative degree of empty. There is no superlative degree of infinite. It's a state/condition of unlimited extent. 'Infinity' is not a number.

Jeff;

I'll leave you with this graphic which you ignored previously.

It's the primary proof that Cantor's construction of the diagonal D is not new but a duplicate of an existing sequence/string/(your favorite word).

This is the list using his characters/symbols, without the E's and the remaining

sequences. The focus is on D beginning at u1 and its duplicate as u8.

There is nothing to prevent u8 from appearing in the list before Cantor alters it.

It's a random list of all possible sequences, each independent of the others.

The sequence of m or w could be decided by flipping a coin (H or T).

A random list has no order, contrary to Cantor's philosophical rambling on 'well ordered' or 'determinate' sets. If m precedes w as a rule of order, the 1st row u1 would be all m's. The 2nd row u2 would be the same except a w in the last position, but there is no last position!

His method has no provision for detection of duplicates, which requires a comparison of all symbols beyond the intersection at (8, 8).

If D is not new than neither is E0, the complement/negation of D.

Each row/u can correspond to an integer from the set N, which also has no end.

He like everyone else, had no experience with things that are endless or boundless or infinite, thus no ability to conceptualize his idea.

JeffJo · July 20, 2023

9 hours ago, phyti said:

He doesn't have to use the word 'diagonal' when that is what he describes.

He does if it is to be a defined object whose properties are required.

9 hours ago, phyti said:

If Cantor uses 2-dimensional coordinates, he is using geometry, whether you recognize it or not.

Sure, if you want to call it that. Cantor doesn't, and no properties associated with "geometry" are required by any object in the proof.

By this standard, he is also using vectors. Also unimportant.

9 hours ago, phyti said:

Cantor showed a partial list because that's all he had.

Cantor uses a "partial list" because that is what his proof needs at that point. You refuse to understand this, which is why you will never understand CDA. He uses it to prove only:

"If E1, E2, …, Ev, … is any simply infinite [einfach unendliche] series of elements of the manifold M, then there always exists an element E0 of M, which cannot be connected with any element Ev."

9 hours ago, phyti said:

He is asking the reader to imagine [or?] pretend it exists.

Please identify the words that you think support this in Cantor. Or Russell. Or Wikipedia (which, incidentally, includes the note "Cantor does not assume that every element of T is in this enumeration."

9 hours ago, phyti said:

It is always incomplete, since there is no last term.

So, do you want to admit that you do not understand infinite sets? The complete set of all natural numbers can be ordered, and has no last member.

I'll skip your incorrect analogies based on this fallacy.

9 hours ago, phyti said:

I'll leave you with this graphic which you ignored previously.

I didn't ignore it. I explained why I could dismiss it.

But again: Every string in Cantor's sequence of strings is identified with a unique natural number n. Cantor's string b₁b₂...b_n... differs from the string identified with n in position, and so is different that every string in this sequence of strings. So it is not in this sequence of strings. This method explicitly rules out any possibility of a duplicate.

Edited July 20, 2023 by JeffJo

wtf · July 20, 2023

15 hours ago, JeffJo said:

And I still think you do not understand my point. Which was only that "Russell's restriction of the elements of the list" does not invalidate the construction of such lists.

I trust you are sincere. But you have gone astray here already.

You say, ""Russell's restriction of the elements of the list" does not invalidate the construction of such lists."

Correct. Agreed. We can certainly make a list of computable numbers. By using knowledge from a few decades after Cantor, we may note that the set of computable strings -- strings whose progress is determined by a law, which I take to be equivalent for purposes of this discussion to be an algorithm -- that set of computable strings is countably infinite.

And therefore, we can place ALL the computable strings on a list. Now the antidiagonal isn't on the list. What is it? Since we listed all the computable numbers, the antidiagonal must be noncomputable!

Now that's an achievement. Using a diagonal argument we've proven that there exists at least one noncomputable number. That's a great achievement in thought. If Russell had seen the implications of his own rhetorical inaccuracy, he'd have scooped Turing in the naming and discovery of noncomputable real numbers (or strings).

But you see the problem. We CAN of course form lists of SOME and even ALL of the computable strings. But now the antidiagonal only furnishes proof of the existence of a noncomputable number. We completely lost our proof of the uncountability of the reals.

So you may be right that Russells use of laws "does not invalidate the construction of such lists," whatever it is that you mean by that.

But Russell's use of laws DOES kick the legs out from under any hoped for proof that you can't enumerate the reals. Having found a noncomputable number, you still have no way to show that there is no list or enumeration of all real numbers.

So no matter how you slice it, Russell's remark destroys the point of his proof. He can no longer prove what he hoped to.

Your argument here is: "Russell's proof is ok because he didn't KNOW at the time that it was wrong. Well that does not make Russell's proof become correct. It means that Russell made a mistake in the light of something that was only discovered later. That still counts as a mistake, in the scheme of things.

Past that, what does it matter? That's the point I was making, and it's the only point I was making, and now that I've made it, I have nothing else to add. I can only keep reiterating the same argument.

15 hours ago, JeffJo said:

So a restriction that limits these lists to denumerable sets is not, by itself, a problem. But I also said that Russell went too far by stating this restriction, because we now know that there elements in his set M that cannot meet the restrictions. What I said was that his restrictions seemed necessary to him at the time he wrote it, in order to have access to all of the characters a_n,n

I don't see why you think you need the "laws" restriction in order to have access to all the characters. In a completely random (ie noncomputable) string there is nonetheless a fact of the matter as to what character is in slot 1, and what character is in slot 2, and in general, what character is in slot n, for all n.

The characters that make up each string are "known" in the sense that they exist mathematically. There is just no algorithm that cranks them out.

You mentioned a couple of times that you think Russell thought he needed the axiom of choice simply to postulate an infinitely long character string. That's not true, whether or not it's something he ever thought. So this seems to be a point of error in your thinking. You don't need a "law" to know what's in slot n. There's is something there. There is in fact a function: you put in a natural number n, and it spits out the character in the n-th slot.

The only issue is that this function is not computable. But it does have mathematical existence; and the axiom of choice is not needed.

I didn't try to respond to the rest of what you wrote about L. Since L (the set of all computable strings) is countable, finding a real number that's not in L only proves that L isn't all of the reals. But it DOESN'T prove that there is no list of reals.

So Cantor's proof is no longer there. I call that a serious flaw.

But as I've said, I can be charitable and stipulate that Russell made an honest mistake, and didn't realize how technically significant the idea of a law is; and that we should just ignore it. Then his proof works. I'm perfectly happy to leave it at that.

Edited July 20, 2023 by wtf

JeffJo · July 20, 2023

6 hours ago, wtf said:

By using knowledge from a few decades after Cantor, we may note that the set of computable strings -- strings whose progress is determined by a law, which I take to be equivalent for purposes of this discussion to be an algorithm -- that set of computable strings is countably infinite.

Massaging Wikipedia's informal definition (from the introduction) of a computable number, a computable string "can be computed to any desired number of characters by a finite, terminating algorithm."

Russell's restriction was "[The characters comprising the strings E] are each [calculated by] some determinate manner ... which insures that the E’s of our series are all different." You are the one who translated this very non-specific statement into "computable string."

I do not disagree that the set of all computable strings, which I will call L1 (I trust you can see where I am going) is countable. So there exists a bijection between L1 and the set of all natural numbers. What CDA says is that there is a string E0 that is "determined" from this bijection, that is not in L1. Which means that it is not computable.

My point is that this string E0 can satisfy Russell's intended restriction, even though it cannnot satisfy yours. It is found "in a determinate manner" as described by CDA. So there is another set L2 where every string meets Russell's restriction, but some do not meet yours. Your L1 is a strict subset of L2. L2 may, or may not, be all of Cantor's M. It may, or may not, have a useable definition. But if it does, it is uncountable.

6 hours ago, wtf said:

Your argument here is: "Russell's proof is ok because he didn't KNOW at the time that it was wrong. Well that does not make Russell's proof become correct. It means that Russell made a mistake in the light of something that was only discovered later. That still counts as a mistake, in the scheme of things.

No, my argument here is that you are adding meaning to Russell's argument that he did not intend. For the obvious reason that the concepts required for this added meaning would not be developed for decades. My argument is that you can't blithely translate his vague statement into a formal definition that was beyond his time, and then turn that formal definition back on his vague statement to claim it invalidates his informal proof.

He did not define what he meant by "some determinate manner" because he did not know, envision how, or care if it could be done. He was merely saying that one could "determine" every character a_n,n and subsequently every b_n.

Yes, there is a character in each randomly-accessed position, and we don't need to "know" it to say we can invert it. But the difference between knowing it is there, and actually having it for such manipulation, is close to the subject of the Axiom of Choice. Again, not my area, but I don't know how well Choice was understood in Russell's time. My impression is that he wanted to advance the known state of the diagonal character a_n,n above "we know it is there and everything it can be." And that is Choice, as I understand it.

+++++

But my main point is, and always has been, that the set of strings in the list used in the actual "diagonal argument" part of the uncountability proof is not the entire set M. What I consider to be "CDA" does not mention whether M is, or is not, uncountable. That's in a corollary. And to avoid drivel like what phyti spouts, we should make this clearer in all discussions of CDA. So:

wtf: "How many countably infinite strings (decimal or binary makes no difference) are there? Well, there are uncountably many. That's the content of Cantor's diagonal argument."

No, that's the content of the corollary to CDA.

CDA: Any countable subset of M, the set of all infinite-length binary strings, necessarily omits a string E0 that is in M.

Corollary: M is uncountable.

wtf · July 21, 2023

On 7/20/2023 at 5:15 AM, JeffJo said:

Massaging Wikipedia's informal definition (from the introduction) of a computable number, a computable string "can be computed to any desired number of characters by a finite, terminating algorithm."

I will respond point-by-point to your post later. Before I do that, I want to give a little background, and then pose and solve a seeming Puzzler about the computability of the antidiagonal of L. In short, you are equivocating two different meanings of "determined," and that is causing your reasoning to go astray.

First, as we agree, a computable real number is one whose decimal (or binary, makes no difference) digits can be cranked out by an algorithm.

By algorithm we include words and phrases like "law," "rule," "effective procedure," "effective calculation," "computation," and the like. These are all terms that were used in the 1920s as mathematicians sought their holy grail, a mechanical process by which they could determine the truth or falsity of any given mathematical statement. That holy grail turned out not to exist, as Gödel and Turing and others of that era showed.

Here is a Wiki article giving an overview of the subject.

The vague concepts of law, rule, effective procedure, etc., were clarified once and for all by Turing in his famous 1936 paper, "On Computable Numbers, with an Application to the Entscheidungsproblem." Here's the relevant Wiki page.

The key properties any such law, effective procedure, algorithm, computation, etc. must have is:

(1) The rule, or algorithm, is finite.

(2) It's entirely mechanical. The answer can be cranked out by a machine or rote procedure; and

(3) It always ends in finitely many steps, giving an answer.

Two examples illustrate the concept.

1. The number [math]\pi[/math] is computable. That's because there are lots of formulas for it, such as the famous Leibniz series pi/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9 ...

It's a beginning programming exercise to implement that formula in Python or Java or C++ or any other popular programming language. So despite the fact that pi is irrational and transcendental, and that its digits are often regarded as "random," they are nothing of the sort. The digits are completely deterministic, and a beginning programming student could crank out as many digits of pi as desired, subject only to physical limitations on computing resources. [In the definition of computability we ignore such physical constraints].

2) Let's make up a completely random binary sequence that has no rule, law, algorithm, effective procedure, etc., to generate its digits.

Suppose we generate the binary digits of a real number by flipping a hypothetical fair coin infinitely many times, once for each digit position to the right of the binary point. If you insist on realism, perhaps we can use the oddness or evenness of the low-order bit of the femotosecond timestamp of the next neutrino to hit our detector. Any mechanism that's as random as we can imagine in this world.

We will generate some noncomputable real number. Its digits are still "determined," in the sense of a mathematical function. If you give me a natural number n, I'll tell you whether there's a 1 or a 0 in that position.

But it's not computable. There's no mechanical rule or procedure that tells us what bit is at digit position n.

So you see that there is an ambiguity in the use of the word "determined." Any mathematical function takes an input and produces an output. The output is therefore "determined" by the input.

But the mapping from inputs to outputs may or may not be computable.

I believe that in your reasoning, you are often equivocating between these two meanings of "determined." The output of a mathematical function is always determined by the input. That's the definition of a functional relationship. But the mapping is only sometimes computable; and other times, it isn't.

Now with all this in mind, I'm going to present a Puzzler.

We know (because there are at most countably many possible computer programs, given a finite or countably infinite alphabet, and given that any program is a finite string of symbols) that there are countably many computable real numbers.

Therefore there is an enumeration of ALL the computable numbers. You have been calling such an enumeration L.

Given such an enumeration, we can form the antidiagonal in a perfectly deterministic, rule-based manner, by the rule "whatever symbol is in row n, column n, replace it with a different symbol."

Now, since the antidiagonal is clearly not in L; that is, it is not on our list, which contains ALL the computable reals; therefore the antidiagonal can NOT be computable.

Simple enough. But wait! We DO have a mechanical procedure to generate the antidiagonal. Step one, enumerate the computable reals; and step two, form the antidiagonal according to the "change the symbol" rule.

So the antidiagonal is computable after all! Paradox! Mystery! What happened? What is the answer?

Well, the answer is kind of subtle, and interesting.

There is indeed an enumeration of the computable numbers. But there is no computable enumeration of the real numbers.

In other words in step 1, when we say, "Form an enumeration of the computable real numbers," we can do so mathematically. Such an enumeration exists. Given a natural number n, we can say what is the n-th computable number.

But that enumeration is itself NOT computable. There is no law, no rule, no algorithm, no effective procedure, no computation that can crank out the list!

So the antidiagonal is not "law-determined." It's mathematically determined, in the sense that there's some symbol in each digit position. But there is no mechanical procedure to crank out the digits of the antidiagonal, because there is no computable enumeration of the computable numbers.

Without going into detail, the reason there can be no computable enumeration of the computable numbers is related to the unsolvability of the Halting problem. No computer program exists that can input an arbitrary program and determine whether that program will halt after a finite number of steps. Turing proved this in his 1936 paper. If we could mechanically list all the computable numbers, that would amount to being able to determine which algorithms halt, and Turing showed that we can't do that.

I believe this clears up some of the ambiguity in your post. You said the antidiagonal of L is "determined," but it is not computably determined. It's determined as the output of a mathematical function, but NOT as the output of a computation, algorithm, rule, law, effective procedure, etc.

I will leave this post as it is, and reply specifically to your most recent post a little later in the day.

But I hope that I have already cleared up the ambiguity in your reasoning. The antidiagonal of L is not "determined" by a law or rule or algorithm. It is not, after all, a computable number.

Edited July 21, 2023 by wtf

wtf · July 21, 2023

On 7/20/2023 at 5:15 AM, JeffJo said:

Massaging Wikipedia's informal definition (from the introduction) of a computable number, a computable string "can be computed to any desired number of characters by a finite, terminating algorithm."

Russell's restriction was "[The characters comprising the strings E] are each [calculated by] some determinate manner ... which insures that the E’s of our series are all different." You are the one who translated this very non-specific statement into "computable string."

Ok here are my specific responses to your post.

I agree that I did interpret "law" as effective procedures, computation, algorithm, etc., as was already being done even in Russell's time, though I'm not sure if you gave the date of his quote. But I can't imagine what ELSE he could have meant. A law is a finitely-expressed, deterministic procedure for obtaining an output from an input. It's an algorithm, computation, effective procedure, etc.

Just because he didn't think of this at the time doesn't mean it wasn't a material error. Just as we don't regard the believers in the phlogiston theory of heat as having been right, simply because they were well-intentioned and couldn't see into the future. From what we know now, they were simply wrong. As was Russell.

On 7/20/2023 at 5:15 AM, JeffJo said:

I do not disagree that the set of all computable strings, which I will call L1 (I trust you can see where I am going) is countable. So there exists a bijection between L1 and the set of all natural numbers. What CDA says is that there is a string E0 that is "determined" from this bijection, that is not in L1. Which means that it is not computable.

Yes. It's determined in the sense that each digit position has some particular value in it. And since it's the antidiagonal of a list of ALL the computable numbers, it can't be computable. We agree on this.

On 7/20/2023 at 5:15 AM, JeffJo said:

My point is that this string E0 can satisfy Russell's intended restriction, even though it cannnot satisfy yours. It is found "in a determinate manner" as described by CDA. So there is another set L2 where every string meets Russell's restriction, but some do not meet yours. Your L1 is a strict subset of L2. L2 may, or may not, be all of Cantor's M. It may, or may not, have a useable definition. But if it does, it is uncountable.

You really lost me by referring to "Russell's intended restriction" and mine. I have no idea what specific ideas you are referring to. It would be good to clarify that.

So here you are using "in a determinate manner" in the wrong way. The antidiag of the list of all computable numbers is determined, but not law-determined. It's not computable. That's because, as I noted, the enumeration itself is not computable. This is exactly where your argument is going wrong.

Now the trouble is that you can NOT conclude that anything is uncountable. Having found that the antidiag of the list of all computable numbers is not itself on the list, for all you know, the real numbers are countable. You can just keep adding new antidiags one at a time to your list and it's always countable. You are adding one element at a time to a countable list. The list is still countable.

In other words, Russell and you have given up trying to show that the reals are uncountable. All you are showing is that there exists a noncomputable number (or string if you prefer).

You have not shown anything is uncountable at all. Where is your argument? You made a claim but not an argument. You keep throwing one more item at a time into a countable set, and the resulting set is still countable.

On 7/20/2023 at 5:15 AM, JeffJo said:

No, my argument here is that you are adding meaning to Russell's argument that he did not intend. For the obvious reason that the concepts required for this added meaning would not be developed for decades. My argument is that you can't blithely translate his vague statement into a formal definition that was beyond his time, and then turn that formal definition back on his vague statement to claim it invalidates his informal proof.

It's perfectly clear that when he says there is a law, he means algorithm, computation, whatever.

I'm perfectly willing to agree that he had a lapse in judgment and we can ignore what he wrote. But I can not agree that, taken literally, his error is not material. His error entirely destroys the argument he's trying to make.

On 7/20/2023 at 5:15 AM, JeffJo said:

He did not define what he meant by "some determinate manner" because he did not know, envision how, or care if it could be done. He was merely saying that one could "determine" every character a_n,n and subsequently every b_n.

If he doesn't mean rule, algorithm, finitary mechanical procedure, etc., then what else CAN he mean?

Russell certainly knew what a function was. A function deterministically produces an output for each input; but it NEED NOT do so according to a "law." It's pointless to keep arguing about this.

On 7/20/2023 at 5:15 AM, JeffJo said:

Yes, there is a character in each randomly-accessed position, and we don't need to "know" it to say we can invert it. But the difference between knowing it is there, and actually having it for such manipulation, is close to the subject of the Axiom of Choice. Again, not my area, but I don't know how well Choice was understood in Russell's time. My impression is that he wanted to advance the known state of the diagonal character a_n,n above "we know it is there and everything it can be." And that is Choice, as I understand it.

Nothing at all to do with the axiom of choice. You do not need choice to refer to an infinite string of symbols. Russell would surely have known that if he thought about it at all. Infinite strings of symbols exist because each one is a function from the natural numbers to the set of symbols. (Input 47, output the symbol in slot 47. It's a function from the naturals to the set of symbols). No choice needed for that.

Perhaps you are referring to constructivism, the philosophy of math that says nothing exists unless it can be specifically (algorithmically) constructed.

https://en.wikipedia.org/wiki/Constructivism_(philosophy_of_mathematics)

Constructivism is related to intuitionism. These ideas started in the 1920s. I see no evidence that Russell was an intuitionist.

He would perfectly well know that you don't need a "rule" or a "law" to define a function. Now again I agree with you that he misspoke himself and we should just ignore it and move on. But you cannot insist that we take him literally and then claim it doesn't matter. Russell should have and most probably did know better.

Or perhaps (I'm hazy on the history) the modern, set-theoretic understanding of function as a set of ordered pairs was not yet well-known to Russell. In that case he's with the phlogiston-believers. Not "Right by virtue of being unable to see the future," but "Wrong, no matter how noble their intentions."

On 7/20/2023 at 5:15 AM, JeffJo said:

But my main point is, and always has been, that the set of strings in the list used in the actual "diagonal argument" part of the uncountability proof is not the entire set M. What I consider to be "CDA" does not mention whether M is, or is not, uncountable. That's in a corollary. And to avoid drivel like what phyti spouts, we should make this clearer in all discussions of CDA. So:

wtf: "How many countably infinite strings (decimal or binary makes no difference) are there? Well, there are uncountably many. That's the content of Cantor's diagonal argument."

No, that's the content of the corollary to CDA.

CDA: Any countable subset of M, the set of all infinite-length binary strings, necessarily omits a string E0 that is in M.

Corollary: M is uncountable.

No that's simply false. The computable numbers are a subset of M, and we can show that the antidiagonal E0 is not computable, and all we've shown is that a noncomputable number exists. We have NOT shown that M is uncountable.

I truly don't know why you keep claiming without proof that this shows M is uncountable, when it clearly does not.

Look at it this way. You have the countably infinite set of computable numbers. You adjoin to that set one noncomputable number. The resulting set is still countable. You adjoin another countably infinite many noncomputable numbers, and the augmented set is still countable. How do you know you can't exhaust the reals this way, proving them (or M) countable?

Where is your proof that M is uncountable? You haven't got one. You start from a countable set and keep adding elements, but you don't have a proof that you won't end up exhausting M that way, proving M is countable.

To prove M uncountable, you have to start from an arbitrary set of strings and show that there's one missing. That shows there's no enumeration of all the strings.

If you start from a specialized countable set like the computables, you lose the uncountability proof.

ps -- I think I sort of see what you might be doing.

You start with a countable set and you keep adding elements, one at a time. (What happens after you've added countably many? You seem to be reinventing the ordinal numbers).

Now if at some point we claim we have ALL the reals, that's falsified by the antidiag.

So at best you have proved that you can't reach all the reals starting with a countable set and adding one real at a time.

This is a far cry from the CDA.

pps -- I just wanted to say that I find talking about the noncomputable numbers far more interesting, and far more within my own wheelhouse of competence, than trying to figure out what Russell meant by laws or knew about the axiom of choice. I'm no Russell scholar by any means.

Edited July 21, 2023 by wtf

JeffJo · July 22, 2023

And here is my (well, not so) quick response to your response.

The passage is from Russell's 1903 book "The Principles of Mathematics." I only have it in PDF form where it starts on page 283. But in the document scanned, it starts on what appears to be page 532. And that document has notes in the margin indicating it was taken from page 365 of Russell's. I don't know what other versions might have been published. But it is in Chapter XLIII, "The Philosophy of the Infinite."

In the introduction to the passage, Russell says "The proof [[Cantor's second on uncountability]] is interesting and important on its own account, and will be produced in outline." So not a formal rendering. But it translates, almost verbatim, what Cantor wrote. In clearer, English terminology. Which was my only point in posting it.

Then, it is important to realize (and I don't think you have responded to this) that CDA and its corollary represent an informal proof only. Russell called it an outline, because he apparfently saw what Cantor wrote as an outline. It is an example of the far more formal proof that follows, that the power set of any set A has greater cardinality than that of set A. Specifically, if 'm' and 'w' are taken to mean "included" and "excluded" (and I don't know which, my German is limited), then each element of M defines a unique subset of N, the set of all natural numbers.

And the reason I keep repeating this, is that I feel you are applying far to high of a standard to what Russell wrote. It updates some of the language in Cantor, almost literally. But neither is a formal proof.

And Russell does not place, as restrictions, what you seem to think invalidates it as a formal proof:

Russell does not say that we must use a "law" to define the strings in the list E₁, E₂, ..., E_n, ... .
He merely says that the characters are to be found "in some determinate manner."
He added a parenthetical comment that describes one such list, and says that "an other [sic] law might be suggested."
- THIS IS IN NO WAY THE REQUIREMENT YOU CLAIM IT IS.
- THIS IS A SUGGESTION FOR WHAT MIGHT BE USED TO MAKE A LIST.

His goal for saying that appears to be twofold:

To make sure that each E_n is different than any other. He states this explicitly, but it is actually unnecessary to the proof and Cantor did not say it.
To make sure that we can "determine" each character a_n,n rather than just know it exists.

And the reason I think you go too far, is that Russell clearly thinks that the anti-diagonal is a string that is found "in some determinate manner." Turing's definition that "clarified once and for all by Turing in his famous 1936 paper" does not apply to what Russell wrote, because:

Russell's concept was what Turing was trying to clarify.
Russell did not require a "law," even if Turing's definition could be retroactively applied to what Russell meant.
It is not part of a formal proof.

15 hours ago, wtf said:

You are adding one element at a time to a countable list. The list is still countable.

This is the kind of statement that makes me think you are not reading anything that I have written, only cherry-picking for what you think I get wrong. You are assuming that I must be wrong when I contradict with you, and not looking at the context I use to contradict you.

There is no part of Cantor's Second Uncountability Proof that involves adding elements to a countable list. That is the wrong context. I know that is the popular representation of it, but there is no part of the proof that says anything like it. I even outlined it before:

CDA: Any countable subset of M, the set of all infinite-length binary strings, necessarily omits a string E0 that is in M.
Corollary: M is uncountable.

CDA (the first part above) does not mention uncountability, or add any elements to a list. It shows that any list that can exist (Russell's "in some determinate manner") is missing one. I contradicted you to point out that uncountability is not mentioned, not to say your final conclusion is wrong.

CDA (the first part above) is not a proof-by-contradiction. It is a direct proof, that "determines" (al a Russell) an element E0 that is not in any list that can be provided.

Cantor never suggests adding E0 to the list. That is a Freshman's initial thought, when CDA (the first part above) is treated as the complete proof, and as a proof-by-contradiction. That alleged contradiction is "This list that we assumed to be complete, is not in fact complete." The Freshman will have the knee-jerk reaction that we can just add E0 to the list, and so remove the contradiction. The part that makes this an invalid proof-by-contradiction is that saying "we assume the list is complete" is not enough - you have to use that assumption to prove the contradictory statement. And CDA does not.

This "determinate manner" Russell mentions is not subject to Turing's definition. It was a vague reference to what Russell thought could exist, at the time he wrote those words, and that Turing later clarified.

The corollary is not proven by adding the anti-diagonal element to the list. It is a proof-by-contradiction. If a listing of M could exist, then there is an E0 that both is, and is not, a member of M.

phyti · July 23, 2023

wtf;

Your reference to algorithms opens up other points to ponder.

Cantor considers the diagonal formed from one character from each row with coordinates (v, v) a sequence. His method of formation for E0 is to swap characters m and w. He doesn't specify a method of formation for the E elements in the list/array prior to E0. It can't be the same since the first E would have nothing to modify. The diagonal cannot be completed until the list is complete.
If the list is complete, E0 is redundant as a duplicate.

As Wittgenstein noted, the product of an algorithm/procedure is not without limits/infinite, it's the algorithm/procedure.

For the integers of N, a unit can be pulled out of nowhere, added to any current integer to form a larger one. As stated by one mathematician, 'mathematics' is a manipulation of symbols (total abstraction).

As for a program to generate the set N:

1. x=0
2. n=x
3. x=n+1
4. if x>n, goto 1 ;n is not the greatest integer
5. stop

n+1>n = 1>0, which is always true, thus step 5 is redundant, and never happens.

Any process requiring an infinite number of steps, never reaches its goal.

pzkpfw · July 23, 2023

In step 4, you want "goto 2".

Curious, and I do believe this is relevant, do you accept 0.999... = 1 ?

JeffJo · July 23, 2023

4 hours ago, phyti said:

[Cantor's] method of formation for E0 is to swap characters m and w. He doesn't specify a method of formation for the E elements in the list/array prior to E0.

His "method" applies to any list that can be formed. The method by which is is formed is not relevant.

4 hours ago, phyti said:

The diagonal cannot be completed until the list is complete.

Please, define what you think "complete" means here. Because it isn't what Cantor asked for.

wtf · July 23, 2023

On 7/22/2023 at 7:09 AM, JeffJo said:

And here is my (well, not so) quick response to your response.

"Act in haste, repent at leisure."

On 7/22/2023 at 7:09 AM, JeffJo said:

The passage is from Russell's 1903 book "The Principles of Mathematics." I only have it in PDF form where it starts on page 283. But in the document scanned, it starts on what appears to be page 532. And that document has notes in the margin indicating it was taken from page 365 of Russell's. I don't know what other versions might have been published. But it is in Chapter XLIII, "The Philosophy of the Infinite."

In the introduction to the passage, Russell says "The proof [[Cantor's second on uncountability]] is interesting and important on its own account, and will be produced in outline." So not a formal rendering. But it translates, almost verbatim, what Cantor wrote. In clearer, English terminology. Which was my only point in posting it.

Ok, 1903. This will become relevant shortly. I will soon introduce evidence that as early as 1905, and no later than 1913, Brouwer introduced into mathematics the idea of "lawlike" sequences, that are defined by SEP as being generated by algorithms; and that it's entirely possible that Russell may have been familiar with these ideas that were "in the air" at the time. Or maybe he wasn't. But you can't accuse Russell, a famous philosopher, of using words imprecisely.

You say, "But it translates, almost verbatim, what Cantor wrote." But it does NOT. It ADDS the concept of a "law" that determines the characters of the string, and that entirely invalidates Russell's claim to be explaining Cantor's proof. Cantor made no such mistake. I suspect Russell didn't really understand Cantor's argument.

On 7/22/2023 at 7:09 AM, JeffJo said:

Then, it is important to realize (and I don't think you have responded to this) that CDA and its corollary represent an informal proof only.

I honestly think that I've answered this point several times already, to you and to @studiot. Let me make this crystal clear.

* I am perfectly satisfied with the correctness of the CDA and indeed Cantor's other two proofs of the uncountability of the reals, based on the modern treatments that I've seen.

* I rarely get involved in "alternative" aka "skeptic" aka "crank" discussions of the subject.

* I only mentioned to @phyti that he might benefit from looking at a contemporary account of the CDA. He responded by saying that he finds contemporary versions equally objectionable. That completed the conversation as far as I was concerned.

* You replied to me, offering the Russell quote as a "better" explanation of the CDA. I pointed out that by requiring the strings to be generated by a "law," and then giving specific examples of algorithms, Russell underminded the CDA and missed the point entirely. And that although I could live with saying that Russell misspoke himself and that we should not be pedantic about the matter; your continued claim that Russell did not mean what he wrote, or even if he did, he can still prove the CDA, are wrong.

* Finally, I am not actually familiar with Cantor's original paper on the subject, in German or in English translation, and I'm totally unable to offer any comment on it.

* Therefore any attempts on your part to engage me in conversation regarding Cantor's original exposition is pointless. I have neither the knowledge nor the inclination to discuss the matter. If you say his original argument was informal, or imprecise, or lacking in some particular virtue, I will take your word for it and I won't bother to look any deeper. As I originally said to @phyti, the original paper introducing a revolutionary new idea is often more difficult and sometimes even error-prone, than the later, cleaned-up versions.

I truly hope this is clear.

On 7/22/2023 at 7:09 AM, JeffJo said:

And the reason I keep repeating this, is that I feel you are applying far to high of a standard to what Russell wrote. It updates some of the language in Cantor, almost literally.

Well the "almost" is the operative word. Russell specifies a law.

A law is an algorithm, and was beginning to be recognized as such at the time of Russell's writing. Let me elaborate on this point. See Intuitionism in the philosophy of mathematics.

A guy named Brouwer suggested that the only legitimate sequences were the ones given to us by laws or algorithms. From the SEP article:

"A choice sequence is an infinite sequence of numbers (or finite objects) created by the free will. The sequence could be determined by a law or algorithm [my emphasis], such as the sequence consisting of only zeros, or of the prime numbers in increasing order, in which case we speak of a lawlike sequence, or it could not be subject to any law, in which case it is called lawless."

As I say, Brouwer (according to the SEP article) published a philosophical article about his ideas as early as 1905, only two years after the Russell quote. And he published his first full-fledged paper on his mathematical ideas about intuitionism as early as 1913, only ten years after the Russell quote.

I do not know if the British Russell and the Dutch Brouwer corresponded, directly or indirectly; or if perhaps these early ideas about intuitionism were "in the air" at the time, and known to Russell.

It seems to me at least as likely that when Russell used the word "law," he did so deliberately, being a famous philosopher well up to speed on the intellectual trends of his time; as that he simply misspoke himself and did not mean to write what he clearly wrote.

Here is Russell's quote as you initially wrote it to me:

"... where the a’s are each an m or a w in some determinate manner. (For example, the first p terms of E_p might be m’s, the rest all w’s. Or an other law might be suggested, which insures that the E’s of our series are all different."

You can see that the examples he give: "first p terms are m, the rest w ..." are obvious examples of algorithms. It's perfectly clear that he's thinking of algorithms.

[Note: On rereading, I realize that he's saying he wants a SINGLE law to generate ALL the strings. This is truly hopeless. He can never prove the uncountability of the reals that way. This is even worse than I initially thought].

And as I believe you agreed earlier, the strings on the list need not even be different for the argument to go through.

It seems clear to me that Russell did not actually grasp the subtleties of Cantor's argument, and made at least two mistakes.

Indeed, even his claim that different laws must give rise to different strings is a mistake. Where is his proof that two distinct laws must necessarily give rise to distinct strings? For example the sequence of natural numbers given by the primes, and the sequence of numbers that satisfy Wilson's theorem, are the exact same sequence, even though at first glance the rules seem very different.

https://en.wikipedia.org/wiki/Wilson's_theorem

So I'd say Russell made three errors: One, requiring the symbol strings to be generated by laws; two, thinking the strings need to be distinct; and three, thinking that distinct laws always generate distinct strings.

And even if these errors are (charitably) excused as not being material, they are at the very least confusing, because they are utterly irrelevant to the argument.

In trying to "clarify" Cantor's argument, Russell has mangled it. Which is my entire point here.

On 7/22/2023 at 7:09 AM, JeffJo said:

This is the kind of statement that makes me think you are not reading anything that I have written, only cherry-picking for what you think I get wrong. You are assuming that I must be wrong when I contradict with you, and not looking at the context I use to contradict you.

There is no part of Cantor's Second Uncountability Proof that involves adding elements to a countable list.

This is in reference to my understanding that you are starting with a countable list an adding one element at a time, in the hopes of (somehow?) proving the uncountability of the reals. I got this idea from your exposition about the L and L1 and L2 and E0 and E1 and the like.

If I have misunderstood your argument, please state it more clearly.

I also note that you did not respond to my challenge to prove your claim that you can prove the uncountability of the reals by starting with a list of all the computable reals, showing the list is incomplete, and thereby concluding that the reals are uncountable. That proves nothing of the kind! I have asked you for an explanation and you have as yet not supplied one.

On 7/22/2023 at 7:09 AM, JeffJo said:

Cantor never suggests adding E0 to the list.

Correct. He never did, because he knew better. I thought YOU were suggesting that, but now you say you are not. So what is the argument about L, L1, L2, E0, E1, etc.? If I misunderstood, please clarify the argument so I can understand it.

On 7/22/2023 at 7:09 AM, JeffJo said:

This "determinate manner" Russell mentions is not subject to Turing's definition. It was a vague reference to what Russell thought could exist, at the time he wrote those words, and that Turing later clarified.

You claim it's vague. i showed that the philosophical notion of a law being the same as an algorithm was "in the air" in the decade following Russell's quote, in the work of Brouwer.

You say Russell didn't mean what he wrote. I say that a philosopher of Russell's stature would ALWAYS use words that meant exactly what he wanted to communicate, and that it's more probable that he meant what he wrote and simply made a technical error.

We can never resolve this. I don't understand why you want to argue the point. I've stated several times that I'm perfectly willing to say, "Ok Russell made an oopsie, let's let it slide." But you don't even want to admit he made a mistake. You want to claim that by "law" he meant ... what, exactly? I can't imagine. SEP regards the terms law and algorithm as synonymous.

On 7/22/2023 at 7:09 AM, JeffJo said:

The corollary is not proven by adding the anti-diagonal element to the list.

I agree with that point. I just misunderstood your L, L1, L2, etc. argument, and still don't understand it, and I am requesting clarification.

Where is your proof that you can restrict the CDA to start with the list of computable reals and end up proving the uncountability of the reals? You can't do that! At best you can prove only that there exists a noncomputable real number (or symbol string).

7 hours ago, phyti said:

Any process requiring an infinite number of steps, never reaches its goal.

The natural numbers are computable. Given any natural number n, we have an algorithm ("keep adding 1 till you get where you're going") that reaches n in finitely many steps. The algorithm is not required to generate ALL the natural numbers at once; merely generate any arbitrary one in finitely many steps. That, it can clearly do.

As another example, I noted earlier that the number pi is computable. Now clearly no algorithm can generate ALL of the digits in finitely many steps! But that is not what is required.

Pi is computable because if you give me a natural number n, I can determine the n-th decimal digit of pi in finitely many steps. And I can do that for any n.

So even though pi has infinitely many nonrepeating digits, each individual digit can be algorithmically determined in finitely many steps. That makes pi a computable real number.

Edited July 24, 2023 by wtf

Sign In

problem with cantor diagonal argument

Recommended Posts

Link to comment

Share on other sites

Top Posters In This Topic

Popular Days

Top Posters In This Topic

Popular Days

Popular Posts

phyti

KJW

Genady

Posted Images

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Create an account or sign in to comment

Create an account

Sign in

Important Information