problem with cantor diagonal argument

[studiot]

5 hours ago, wtf said:

Can you link the version of Cantor's proof that you're looking at? I looked up this translation: https://www.jamesrmeyer.com/infinite/cantors-original-1891-proof.php and could not correspond it to your exposition.

Good question +1

 

Thanks for the link, but there is more to it than that I think.

 

As far as I know Canto never used the term infinite, despite the above translation.

Instead he invented the term transfinite.

I am given to understand by Wikipedia that this was because he realised he was talking about something different from the ancient greek infinities.

 

In the German in the paper  you refer to he used the word unendliche.

 

But just as Rome wasn't built in a day, the theory of infinite aggregates took 10 to 15 years to develop, with more work going on after that and to this day.

 

In volume 1 of his "The Theory of functions of a Real Variable", Hobson claims the first English language exposition of Cantor's theory, as opposed to a translation.

Hobson keeps with the terms aggregate and transfinite, which were current at the time.

[wtf]

3 hours ago, phyti said:

CANTOR'S PHILOSOPHICAL WRITING

The link does not come up for me. It says "Yahoo will be right back," but I've been checking for an hour and it doesn't seem to be there. Does this link work for you?

Can you please show the entire context of your "infinite number" quote? That does not sound like anything Cantor would have said.

[StringJunky]

28 minutes ago, wtf said:

The link does not come up for me. It says "Yahoo will be right back," but I've been checking for an hour and it doesn't seem to be there. Does this link work for you?

Can you please show the entire context of your "infinite number" quote? That does not sound like anything Cantor would have said.

It's geocities.com then a btinternet email address. Not a link to an organisation's site.  It's not secure. Looks like a personal email address.

Edited June 27, 2023 by StringJunky

[phyti]

Follow these links.

https://www.logicmuseum.com/index.htm

Subjects in logic and metaphysics

Cantor's Philosophical Writing

On an Elementary Question of Set Theory (Georg Cantor)

https://www.logicmuseum.com/authors/index.htm

Primary sources in logic and metaphysics (Logic Museum II)

[wtf]

On 6/26/2023 at 7:49 AM, phyti said:

"if alpha is an infinitely large number,"

 

What is the meaning of the red if any?

From the links you gave, he's talking about transfinite ordinal numbers. In the same paragraph he talks about well-ordered sets.

https://www.logicmuseum.com/cantor/cantorquotes.htm

Edited June 28, 2023 by wtf

[JeffJo]

On 6/27/2023 at 1:16 PM, phyti said:

Jeff;

Keeping it simple, using 0 and 1 for symbols and S for sequence or string, divide M into 2 subsets,
M0 containing S beginning with '0', and M1 containing S beginning with '1'.

Keeping it relevant (see P:"It's possible you have a problem in comprehension." J:"It's obvious that you don't want to comprehend CDA."), which of your two sets. M0 or M1, is one where you know that the conditions Cantor placed on the set S hold true?" That is, the Ei's in these conditions:

• If E1, E2, …, Ev, … is any simply infinite [einfach unendliche] series of elements of the manifold M ....

If you can't show that either M0 or M1 can be put into such a list, then any answer to your question has no significance to CDA.

But the answer is

• s=0000... can be in subset S0 of M0 that can be put into a list as Cantor requires.
  • There are listable subsets S0' that do not have s=0000... as a member.
• s=1111... can be in subset S1 of M1 that can be put into a list as Cantor requires.
  • There are listable subsets S1' that do not have s=1111... as a member.

Now, if you will stop trying to change the details of CDA to fit your incorrect criticism of it, we can discuss why it is a valid proof. But if you continue to misrepresent it, we can't.

Quote

From CANTOR'S PHILOSOPHICAL WRITING

Whether or not you interpret such writing correctly (you don't), they have no bearing on the mathematical proof called CDA.

Edited June 29, 2023 by JeffJo

[studiot]

10 hours ago, JeffJo said:

Quote

From CANTOR'S PHILOSOPHICAL WRITING

Whether or not you interpret such writing correctly (you don't), they have no bearing on the mathematical proof called CDA.

 

10 hours ago, JeffJo said:

If you can't show that either M0 or M1 can be put into such a list, then any answer to your question has no significance to CDA.

I was beginning to wonder if this thread was actually anout the diagonal argument or a character assassination of Cantor.

Thank you for exposing this point so simply and  clearly.

+1

[phyti]

Jeff;

But the answer is

• s=0000... can be in subset S0 of M0 that can be put into a list as Cantor requires.
  • There are listable subsets S0' that do not have s=0000... as a member.

• s=1111... can be in subset S1 of M1 that can be put into a list as Cantor requires.
  • There are listable subsets S1' that do not have s=1111... as a member.

At least quote it correctly.

S=0000... is a member of M0, a subset of M.

S=1111... is a member of M1, a subset of M.

The point here, if one is a member both are members of M.

This isn’t something needing proof. It’s known from the properties of binary sets.

 

Cantor created his own contradiction when he claimed E0 was not in the set M while D (the template used to form E0) was in the set M!

 

When you say subset, that implies an incomplete or partial set.

It's a redundant statement.

Don't you think Cantor knew that while trying to prove his idea?

 

[JeffJo]

On 7/1/2023 at 10:58 AM, phyti said:

At least quote it correctly.

S=0000... is a member of M0, a subset of M.

S=1111... is a member of M1, a subset of M.

I try to represent things consistently, rather than how you use inconsistencies to misrepresent Cantor. You are co-opting the notation used by others, maybe in the hope of creating confusion. One example of such confusion is the "diagonal" that you think is an important property in CDA. It isn't defined, or even mentioned.

I am being consistent with the notation used in Wikipedia: A capital letter represents one of the sets being used, while a lower case letter represents one of the strings that is a member of these sets. That makes it easy to recognize how the indicies are being used. The letter S is used for the set that is subjected to CDA, and s for its members. The letter T is used for the set of all eligible strings; that is, Cantor's M.

Quote

The point here, if one is a member both are members of M.

No, the point is that CDA only works with sets that that are known to be countable. They are subsets of the complete set T (or Cantor's M), which is not yet known to be countable, or uncountable.

Before the proof, your M0 and M1 are also not established either way. So this argument you are trying to goad me into has no implication on CDA.

Quote

Cantor created his own contradiction when he claimed E0 was not in the set M while D (the template used to form E0) was in the set M!

This is where you misrepresent Cantor. He never claimed that E0 (what Wikipedia calls just s but I prefer s0) was not in M (what Wikipedia calls T).  He said it was not in the sequence E1, E2, E3, ... ." Cantor never names this set, or calls it a subset of M, but he does define it in a way that means a subset. You are trying to exploit this by misusing his symbols, and misquoting Cantor.

Quote

When you say subset, that implies an incomplete or partial set.

When I say that S is a subset of T - and note that "subset" means a relationship between two sets - I mean only that every member of S is also a member of T. It can be a proper subset ("incomplete or partial") or an improper subset. The only properties I reference are that every member of S is in T, and that all members of S are represented in a list  s1, s2, s3, ... .

This is what Cantor meant when he said "If E1, E2, …, Ev, … is any simply infinite series of elements of the manifold M...". He doesn't explicitly mention a set that is equivalent to my S, but he also never says "all elements of the manifold M." So, by definition these Ev's comprise a subset. What you are missing (either deliberately because it contradicts your arguments, or by omission because you don't want to look at what might contradict it), is that Cantor never says his E0 is not in his M. He says the exact opposite: "then there always exists an element E0­ of M, ...". Where he says E0 can't be found, is in the sequence: "...which cannot be connected with any element Ev."

Quote

Don't you think Cantor knew that while trying to prove his idea?

I am confident he knew exactly what his statements meant. But either you don't, or you don't want to admit that you do since it contradicts yous arguments.

Edited July 3, 2023 by JeffJo

[phyti]

6 hours ago, JeffJo said:

I try to represent things consistently, rather than how you use inconsistencies to misrepresent Cantor. You are co-opting the notation used by others, maybe in the hope of creating confusion. One example of such confusion is the "diagonal" that you think is an important property in CDA. It isn't defined, or even mentioned.

I am being consistent with the notation used in Wikipedia: A capital letter represents one of the sets being used, while a lower case letter represents one of the strings that is a member of these sets. That makes it easy to recognize how the indicies are being used. The letter S is used for the set that is subjected to CDA, and s for its members. The letter T is used for the set of all eligible strings; that is, Cantor's M.

No, the point is that CDA only works with sets that that are known to be countable. They are subsets of the complete set T (or Cantor's M), which is not yet known to be countable, or uncountable.

Before the proof, your M0 and M1 are also not established either way. So this argument you are trying to goad me into has no implication on CDA.

This is where you misrepresent Cantor. He never claimed that E0 (what Wikipedia calls just s but I prefer s0) was not in M (what Wikipedia calls T).  He said it was not in the sequence E1, E2, E3, ... ." Cantor never names this set, or calls it a subset of M, but he does define it in a way that means a subset. You are trying to exploit this by misusing his symbols, and misquoting Cantor.

When I say that S is a subset of T - and note that "subset" means a relationship between two sets - I mean only that every member of S is also a member of T. It can be a proper subset ("incomplete or partial") or an improper subset. The only properties I reference are that every member of S is in T, and that all members of S are represented in a list  s1, s2, s3, ... .

This is what Cantor meant when he said "If E1, E2, …, Ev, … is any simply infinite series of elements of the manifold M...". He doesn't explicitly mention a set that is equivalent to my S, but he also never says "all elements of the manifold M." So, by definition these Ev's comprise a subset. What you are missing (either deliberately because it contradicts your arguments, or by omission because you don't want to look at what might contradict it), is that Cantor never says his E0 is not in his M. He says the exact opposite: "then there always exists an element E0­ of M, ...". Where he says E0 can't be found, is in the sequence: "...which cannot be connected with any element Ev."

I am confident he knew exactly what his statements meant. But either you don't, or you don't want to admit that you do since it contradicts yous arguments.

Why does he say .  "Let M be the totality [Gesamtheit] of all elements E." 

 

[wtf]

2 hours ago, phyti said:

Why does he say .  "Let M be the totality [Gesamtheit] of all elements E." 

 

I wonder if part of the problem is trying to interpret a translation of an article written in German many decades ago expositing a brand new idea.

It's always that case that if you understand a scientific idea and you go back and try to read the original research, it's nearly incomprehensible. That's because over the ensuing years the argument gets simplified and sharpened, and the exposition gets clarified.

People don't speak or write today the way they did back in German academic circles 130 years ago. In science and math, historians study original papers. People only wanting to understand the ideas study the modern versions. 

Do you have similar objections to more modern treatments of the CDA, for example on Wikipedia?

https://en.wikipedia.org/wiki/Cantor's_diagonal_argument

Edited July 3, 2023 by wtf

[studiot]

We can all quote Cantor.

Quote

The aggregate which consists of the continuum of numbers in a given interval in not enumerable

Cantor

Crelle's Journal Vol LXXVII (1874) , page 260

(Original non diagonal proof)

He then goes on to provide a second proof

Jaresbericht der duetschen math Vereineg (1892) vol1 , p75, which is the  so called diagonal proof.

 

[phyti]

wtf;

Do you have similar objections to more modern treatments of the CDA, for example on Wikipedia?

They have the same errors, distortion of a random list with different types of sequences.

Cantor was forming the diagonal with his b-series having the same 2D coordinates (v,v).

I trust in competent translators.

[JeffJo]

On 7/3/2023 at 2:41 PM, phyti said:

Why does he say .  "Let M be the totality [Gesamtheit] of all elements E."

Because M is defined to be the totality of all possible elements E. Why does he not mention M in:

Quote

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.  Then there is a series b1, b2, … bv,…, defined so that bv is also equal to m or w but is different from av,v.

This is the construction of the list that is diagonalized. All it comprises, are elements defined like the element E. Not the "totality of all possible elements E."

What diagonalization  proves, is that any list of elements from M, necessarily omits at least one element of M. It never claims to use, or to not use, all of M in this proof.

 

+++++

On 7/3/2023 at 4:30 PM, wtf said:

I wonder if part of the problem is trying to interpret a translation of an article written in German many decades ago expositing a brand new idea.

The problem is that it is taught incorrectly. More than just claiming to use real numbers, which it works on but Cantor did not use.

The first line in most teachings is something like:

• Assume, for contradiction, that you have a list S of every real number in [0,1).

... when that first line should really be:

• Let S be any list that can be made from just real numbers in [0,1).

What is usually taught is invalid as a proof by contradiction (I'm not saying it is invalid, just not a proof by contradiction. You have to use every part of what you "assume, for contradiction, that...". And what is taught does not use the "every" part of that contradiction. It just proves it is not "every." But students have it hammered into their heads that it is the archetype, so they remember it.

Quote

People don't speak or write today the way they did back in German academic circles 130 years ago. In science and math, historians study original papers. People only wanting to understand the ideas study the modern versions. 

How about Bertrand Russell's version? It's very close to Cantor's, but in English, with more modern math terms:

Quote

From "THE PRINCIPLES OF MATHEMATICS" by Bertrand Russell, M. A.

Let m and w, Cantor says, be two mutually exclusive characters, and consider a collection M of elements E, where each element E is a denumerable collection, x₁, x₂, . . . x_n, . . . , and each x is either an m or a w. (The two characters m and w may be considered respectively as greater and less than some fixed term. Thus the x’s may be rational numbers, each of which is an m when it is greater than 1, and a w when it is less than 1. These remarks are logically irrelevant, but they make the argument easier to follow.) The collection M is to consist of all possible elements E of the above description. Then M is not denumerable, i.e. is of a power higher than the first. For let us take any denumerable collection of E’s, which are defined as follows:

      E₁ = (a₁₁, a₁₂, . . . a_1n, . . .)
      E₂ = (a₂₁, a₂₂, . . . a_2n, . . .)
      . . . . . . . . . . . . . . . . . . . . . . . . .
      E_p = (a_p1, a_p2, . . . a_pn, . . .)
      . . . . . . . . . . . . . . . . . . . . . . . . .

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.) Then however our series of E’s be chosen, we can always find a term E₀, belonging to the collection M, but not to the denumerable series of E’s. For let E₀ be the series (b₁, b₂, . . . b_n . . .), where, for every n, b_n is different from a_nn—i.e. if a_nn is an m, b_n is a w, and vice versâ. Then every one of our denumerable series of E’s contains at least one term not identical with the corresponding term of E₀, and hence E₀ is not any one of the terms of our denumerable series of E’s. Hence no such series can contain all the E’s, and therefore the E’s are not denumerable, i.e. M has a power higher than the first.

 

Edited July 6, 2023 by JeffJo

[wtf]

3 hours ago, JeffJo said:

How about Bertrand Russell's version? It's very close to Cantor's, but in English, with more modern math terms:

I must say I find this archaic presentation difficult to follow, in contrast with more contemporary versions. And Bertie got a detail terribly wrong:

 

3 hours ago, JeffJo said:

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.)

He is is claiming that each sequence of characters is "determinate." Of course Russell was writing years before Turing, but even so he should have known or could have realized that there are only countably many "rules" or "procedures" to determine sequences of characters; and that most (in the sense of all but countably many) of the sequences must be random; that is, NOT "determinate" or subject to any law or rule.

Is this important? I say yes; that this emphasizes my original point.  Accounts written near the time of an original discovery often obfuscate or confuse the key issues by throwing in extraneous and incorrect details; while accounts written decades later get straight to the essential point with less confusion and without irrelevant or erroneous detours (such as mistakenly requiring "laws" to produce the symbols in each row).

This shows that Russell, writing so near to the time of Cantor's discoveries, hadn't really understood or internalized the full import of what Cantor said. Cantor said nothing about sequences of symbols being generated by laws. Russell just made that up, and he got it wrong in a fundamentally important way. 

Bottom line is that Bertie was a near contemporary of Cantor, did not in my opinion offer a clearer exposition, and made a key mistake showing his own confusion (understandable since Turing and Gödel were decades in the future) about the nature of binary sequences and the profound limitations of laws and procedures.

Edited July 6, 2023 by wtf

[JeffJo]

On 7/6/2023 at 7:28 PM, wtf said:

He is is claiming that each sequence of characters is "determinate." Of course Russell was writing years before Turing, but even so he should have known or could have realized that there are only countably many "rules" or "procedures" to determine sequences of characters; and that most (in the sense of all but countably many) of the sequences must be random; that is, NOT "determinate" or subject to any law or rule.

And ... the sequence he is talking about is denumerable.

[wtf]

5 hours ago, JeffJo said:

And ... the sequence he is talking about is denumerable.

Yes that's true. The string of decimal digits representing a real number is countably infinite. Same for binary digits if we are using Cantor's original formulation of strings consisting of two symbols.

Not sure I'm following your point in mentioning this, but perhaps I was not sufficiently clear.

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.

But now Russell comes along in an attempt to "explain" the CDA, and claims that each such string is generated by a "law." And how many such strings can be generated by laws? If by law we mean algorithm, or effective procedure, or a rule written down in symbols, there are only countably many such strings. In this case, the CDA fails! In attempting to "clarify" the CDA, Russell entirely invalidates it. At best, he throws in a red herring that obfuscates and confuses the issue.

The earlier point I was making was that original research, and expositions written near the time of that research, are often lacking in clarity and simplicity. It takes decades for a technical argument to get boiled down to its clear essence. 

You suggested Russell's exposition as an improvement in clarity.

And I pointed out that (IMO) Russell's exposition is actually worse; because not only is it not more clear, it's actually wrong. It requires the symbol strings to be generated by laws; and there are only countably many such strings. We can never prove the uncountability of such strings, since there aren't uncountably many of them at all. There are only countably many such strings.

Proof: What is a law? A law is a finite string of symbols ("Alternate 1's and 0s"; or "Write eight million zeros followed by all 1's," etc.). Given a finite alphabet (say standard English), there are only a finite number of laws of length 1; finitely many of length 2; finitely many of length 3; and so forth. Taking the union of countably many finite sets gives us at most countably many laws; and therefore only countably many symbol strings that can be generated by laws.

A similar argument applies if by law we mean an algorithm, as formalized by Turing's concept of a Turing machine (TM). There are only finitely many TMs of length 1, finitely many of length 2, etc., and therefore at most countably many Turing machines. There are only finitely many algorithms, and therefore only finitely many real numbers that can bee generated by Turing machines. (For a TM you can substitute the more familiar notion of a computer program written in Python, Java, etc.) These are the computable real numbers. There are only countably many of them. Almost all real numbers, in the sense of all but countably many, can NOT be generated by an algorithm. They're entirely random.

Cantor said no such thing as to require the symbol strings to be generated by laws. Perhaps he had insight a few decades into the future, realizing that there could only be countably many laws, algorithms, or procedures. 

So Russell (in the passage you quoted) has not only obfuscated the CDA; he has entirely invalidated it. If you restrict attention to symbol strings generated by laws, there are only countably many of them. The antidiagonal is then a noncomputable number, and it's unclear (to me, anyway) what Russell's point would then be. 

Is that more clear? Or did I misunderstand the intent of  your remark?

Edited July 8, 2023 by wtf

[JeffJo]

5 hours ago, wtf said:

Not sure I'm following your point in mentioning this, but perhaps I was not sufficiently clear.

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.

And from that I'm pretty sure that you are not following my point. Or Cantor's, or Russell's.

By "Cantor's diagonal argument" I mean this part in Russell:

Quote

For let us take any denumerable collection of E’s, which are defined as follows:

      E₁ = (a₁₁, a₁₂, . . . a_1n, . . .)
      E₂ = (a₂₁, a₂₂, . . . a_2n, . . .)
      . . . . . . . . . . . . . . . . . . . . . . . . .
      E_p = (a_p1, a_p2, . . . a_pn, . . .)
      . . . . . . . . . . . . . . . . . . . . . . . . .

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.) Then however our series of E’s be chosen, we can always find a term E₀, belonging to the collection M, but not to the denumerable series of E’s.

This does not have the "content" you refer to. It refers to M only to say that E_p is a member. It does not refer to the countability, or uncountability, of M. This part is imbeded in a larger proof that does refer to M, and uncountability, but this actual "diagonalization" part does not.

I find two shortcomings in CDA. The first is similar to your complaint, but it is not that it uses arcane language. It is informal, which leads to Cantor using the vernacular language that you find arcane. It can be informal because it isn't the theorem that the paper was presenting. That was Cantor's Power Set Theorem, and CDA is only an example of it. Llike you might show a (3,4,5) triangle before proving the Pythagorean Theorem. This is why CDA is called an argument and not a proof or theorem.

The second is that Cantor did leave one thing out. The above passage applies to any list that can actually exist, not a hypothetical list "assumed for contradiction." Cantor really should have demonstrated that such lists exist, and he didn't. Examples are trivial (E_p is all m's except a w in position p) so this can be forgiven. What Russell did was to rectify this omission. He describes a more formal way to create many such lists. He may have gone too far, by limiting his lists to strings that followed a law. I suppose he was trying to get around any Axiom of Choice issues; each character in the diagonal can be found by its law. But:

HE DID NOT SAY THIS REPRESENTED ALL POSSIBLE LISTS, OR THE SET M.

One thing Russell included that Cantor did not, is that each string does not have to be different. They can be so limited, but the point is to show that there is no surjection from N to M.

Edited July 8, 2023 by JeffJo

[wtf]

11 hours ago, JeffJo said:

And from that I'm pretty sure that you are not following my point. Or Cantor's, or Russell's.

I wonder if you might possibly be confusing me with the OP, @phyti

 

 

11 hours ago, JeffJo said:

By "Cantor's diagonal argument" I mean this part in Russell:

I am not at all concerned about Russell's exposition, except for this howler:

"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.)"

The fact that Russell regards the symbol strings as being generated by a "law" or "in some determinate matter" completely invalidates Cantor's proof, for reasons that I've already discussed at length.

Now I agree that perhaps one could say, "Russell had a momentary brain fart, let's just pretend he didn't say that," and then all would be well. But you presented Russell's version as an improved exposition compared to Cantor, so I pointed out that the Russell quote contains a fatal flaw and is therefore worse, not better, than Cantor's version.

 

 

11 hours ago, JeffJo said:

I find two shortcomings in CDA. The first is similar to your complaint

I have no complaints at all about the CDA. I only suggested to @phyti that he might prefer a more modern exposition of the CDA. He replied to me that he finds modern versions equally objectionable. That answered my question and I left it at that. 

 

11 hours ago, JeffJo said:

He may have gone too far, by limiting his lists to strings that followed a law.

He did go too far. It's a fatal flaw in the argument to stipulate that the strings follow a law, since that absolutely rules out the uncountability of any collection of such strings. 

 

11 hours ago, JeffJo said:

I suppose he was trying to get around any Axiom of Choice issues; each character in the diagonal can be found by its law.

The axiom of choice has nothing to do with any of this. 

Summary: (1) I am not the OP. I have no objections to the CDA. (2) In general I prefer modern expositions to original ones, unless one is tracing the history of a given subject. (3) Russell committed a blooper that we can either pretend he didn't say, in order to get on with it; or else note that his blooper invalidates the very argument he's trying to explain. 

As for the rest, you seem to be trying to convince me that the CDA is true, which is entirely unnecessary; or that it's flawed, which it isn't. 

As far as the argument that Cantor assumes a list of "all" strings for purposes of a proof by contradiction, it's of course more clear to frame the argument as showing that ANY list of strings must necessarily be missing a string, showing that there is no list of all strings. That way no proof by contradiction is needed. 

So I agree with you that the reductio formulation of the CDA, so often reproduced online, is not the best way to put it. It's not wrong, but it seems to lead to confusion. Better to just use a direct proof to show that any arbitrary list can not contain all possible strings.

Edited July 8, 2023 by wtf

[joigus]

3 hours ago, wtf said:

assumes a list of "all" strings for purposes of a proof by contradiction, it's of course more clear to frame the argument as showing that ANY list of strings must necessarily be missing a string,

This is the simplest and thereby most beautiful way to explain the argument, IMO. It's the version I was exposed to. After reading most of the material here I'm convinced it's not the way in which Cantor formulated it historically. Probably.

I don't know the history of it. I don't read German either, but I doubt any ambiguities might be lurking behind a more or less obscure German word. I agree that modern formulations tend to streamline the proofs in a very interesting way. I like your phrasing: Any list of numbers that purports to be listing a connected piece of the continuum of real numbers must necessarily be missing a string.

The diagonal operation of somebody's version of Cantor's theorem goes on to prove in a glaringly obvious way, that we can always construct a number not in the declared list. The truth of such declaration is thus impossible.

I'm at a loss as to what else is there to be unravelled in such a simple argument.

 

[JeffJo]

On 7/8/2023 at 6:33 PM, wtf said:

I wonder if you might possibly be confusing me with the OP.

No, I think I was quite clear that I was replying to where you attributed "content" to CDA that simply is not there. You seem to think I am arguing with you about the validity of CDA; I'm not. And you are misrepresenting what I said when you describe how I am arguing with you. The result is that I'm not sure if you understand what I said, or what Cantor (and Russell) said.

On 7/7/2023 at 7:56 PM, JeffJo said:

And ... the sequence he is talking about is denumerable.

On 7/8/2023 at 1:36 AM, wtf said:

Yes that's true. The string of decimal digits representing a real number is countably infinite. Same for binary digits if we are using Cantor's original formulation of strings consisting of two symbols.

 

But I said the sequence was denumerable. Each string of binary digits is also denumerable, but that isn't what I said. It is, hoever, how you seem to have read it.

The list of such strings (or sequence of such strings) that is subjected to the process we (but not Cantor nor Russell) call diagonalization, is denumeable. Maybe Russell did add content that can only make whatever it refers to denumerable. So what? You are the one creating a side argument that has nothing to do with the thread. My point, in presenting Russell's version, was that he used language closer to modern set theory.

But in a similar state of confusion, what Russell said as that each string follows a law. He wasn't as specific as you imply about what this means. We use a summation that converges to, say, the binary representation of pi as such a Law. You seem to think it is something like arbitrarily large polynomials, which form a denumnberable set. And it is still unclear which set (the string, or the sequence of strings) you think has this restriction. Or why it matters, since in the proof both are supposed to be denumerable.

Quote

I am not at all concerned about Russell's exposition, except for this howler:

And I was trying to point out that Russell was adding a point that Cantor should have made, and maybe he went too far the other way. And that calling it out demonstrates that you, in addition to phyti, are not demonstrating that you understand what I am saying.

Quote

It's a fatal flaw in the argument to stipulate that the strings follow a law, since that absolutely rules out the uncountability of any collection of such strings

And again, I don't get that you see my point when you say this. THE SET OF STRINGS USED IN DIAGONALIZATION IS ALWAYS A COUNTABLE SET. The point is that ANY COUNTABLE SET OF STRINGS IS NECESSARILY MISSING AT LEAST ONE STRING. So what it the way he defines the set of Laws, that define the sequence  can only produce countable sets. They are supposed to be countable sets.

Quote

Summary: (1) I am not the OP. I have no objections to the CDA.

I never said you did. I said you objected to what Russell added, as you confirmed here. I said Russell went too far, but that an addition was necessary. And I speculated that Russell, not I, might have wanted to avoid Axiom of Choice issues. The point of his addition was to be able to "choose" each digit in the string he constructs. But I don't know what objections he was trying to avoid, I'm not a mind reader. This one seemed like a possibility.

Quote

(2) In general I prefer modern expositions to original ones, unless one is tracing the history of a given subject.

Wikipedia provides one. That didn't seem to satisfy you, so I provided an intermediate.

Quote

(3) Russell committed a blooper that we can either pretend he didn't say, in order to get on with it; or else note that his blooper invalidates the very argument he's trying to explain.

Again, please explain how it is invalidating to say that a denumerable sequence is defined by a denumerable algorithm. Note that I'm not agreeing, or disagreeing, with your claim about the algorithm.

Quote

As for the rest, you seem to be trying to convince me that the CDA is true, which is entirely unnecessary; or that it's flawed, which it isn't.

No, I'm trying to convince you that what most people think is CDA is flawed. But it is not what Cantor argued, so arguing about those flaws says nothing about CDA.

Most "disproofs" of CDA are based on either thinking diagonalization is being applied to an uncounatble set, or to the incorrect (yes, it is) way the proof is taught as a proof by contradiction. And again, note that I am not saying CDA is invalid, or that what is taught can't be used in a valid proof. I'm saying that what is taught is invalid as the complete proof, and give the wrong impression to many. Like phyti, who can't seem to understand what is has wrong.

A rough outline, with a clarification of some points that are omitted but implied, is:

1. Assume the statement (A&B) is true, where:
   1. A = The set S contains all possible strings.
   2. B = The set S, which contains only strings, is denumerable
2. Use Diagonalization on set S, based on statement B alone, to prove that statement A is false.
3. So (A&B) is also false.
4. By contradiction, (A&B) cannot be true.
5. So when A is true, so B must be false.

This is a jumble of questionable logic. But if one does not recognize that the typical opening statement that is taught as CDA ("The set R of real numbers in [0,1) is countable") is really two statements, both A and B, then most of it seems sorta kinda valid. And so it gets taught as the archetype of proof by contradiction.

Cantor's actual argument is

1. For any set S that satisfies B, Diagonalization proves that that there is a string s0 that is not in S.
2. Assume A&B
   1. Set S satisfies B. So there is a string s0 that is not in S.
   2. Set S satisfies A. So by definition s0 is in S.
   3. Contradiction. A&B is false.

On 7/8/2023 at 10:40 PM, joigus said:

I don't know the history of it. I don't read German either, but I doubt any ambiguities might be lurking behind a more or less obscure German word. I agree that modern formulations tend to streamline the proofs in a very interesting way. I like your phrasing: Any list of numbers that purports to be listing a connected piece of the continuum of real numbers must necessarily be missing a string.

The original German is translated here: With one word changed for consistency (Cantor's German used different forms of the same word), the two bits of interest say what you want, if a bit stiffly:

"If E₁, E₂, …, E_v, … is any simply infinite [sequence] of elements of the manifold M, then there always exists an element E_0­ of M, which cannot be connected with any element E_v."

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

[phyti]

Jeff;

Because M is defined to be the totality of all possible elements E. Why does he not mention M in:

 

He has already defined M. It isn't necessary to keep defining it for every detail he describes. Everything stated after that is within the same context of an infinite set/manifold M.

The beginning of an infinite random list, with one infinite sequence per line, and line 1 blank.

A random sequence can be placed anywhere in the list except at the end, since an infinite list has no end, but we have access to its beginning

 

s1

s2 010010...

s3 101011...

s4 111000...

s5 000111...

s6 011011...

s7 111111...

 

sx 110000...

 

Using Cantor's diag. method, sx is not in the list.

Put sx in line 1, now it is.

[JeffJo]

1 hour ago, phyti said:

He has already defined M. It isn't necessary to keep defining it for every detail he describes. Everything stated after that is within the same context of an infinite set/manifold M.

Bzzzzt. Wrong.

Read it again. The diagonalization algorithm uses elements from M, but is "within the context" of a subset that is known to be countable.

But thank you for playing. Come back when you understand CDA.

"If E₁, E₂, …, E_v, … is any simply infinite [sequence] of elements of the manifold M, then there always exists an element E_0­ of M, which cannot be connected with any element E_v."

Edited July 10, 2023 by JeffJo

[wtf]

On 7/10/2023 at 5:51 AM, JeffJo said:

No, I think I was quite clear that I was replying to where you attributed "content" to CDA that simply is not there.

Hi, I didn't want to just ghost the thread but I think I'd get frustrated if I tried to reply paragraph by paragraph, since we're talking past each other.

So just to focus this down to one specific thing, where you say I "attributed content to CDA that is not there," I would say that I did no such thing. 

Can you explain what you mean by that? I called out an error, a howler in fact, committed by Russell in the passage you quoted. That's all I did.

What content did I attribute to CDA that isn't there?

[JeffJo]

8 hours ago, wtf said:

So just to focus this down to one specific thing, where you say I "attributed content to CDA that is not there," I would say that I did no such thing. 

Can you explain what you mean by that? I called out an error, a howler in fact, committed by Russell in the passage you quoted. That's all I did.

What content did I attribute to CDA that isn't there?

On 7/8/2023 at 1:36 AM, wtf said:

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.

I've described it several times.

The "diagonal argument" in CDA is the proof that any countable list of infinite-length binary strings will necessarily omit at least one such string. This does not mention the set of all such strings, that Cantor called M and Wikipedia called S, except to say that the constructed string is a member. It does not mention "uncountability" in any way. The content you refer to is not in the argument. It is in the follow-up.

Yes, I am making a fine distinction. No, I don't think you misunderstand this distinction at its core. But I believe it to be the point that every "Cantor Doubter" falis to understand, because the two arguments Cantor made are usually taught as one.

Like how phyti misunderstands it. And continues to demonstrate the misunderstanding. You can see it, three posts higher, in his claims about being able to add the string he called "sx" to the list he worked with. He is still thinking that the listed set is "supposed" to be M, and he is claiming that any alleged "missing" string can be put into this "supposedly complete set." So that this disproves the uncountability of M. He somehow can't, or won't, recognize that the listed set is not supposed to be M, so adding sx to the listed set has no significance.

All I'm trying to make clear is that the "content" you refer to, as CDA, is the first of these two, separate arguments:

1. Any countable set of infinite-length binary strings (Ei, for all i>=1) will necessarily omit at least one such string E0.
2. The complete set of infinite-length binary strings, M, must be uncountable; otherwise, there would be a string E0 that both is, and is not, in M.

Note that the "contradiction" usually associated with CDA, with these two arguments combined into one, is that the "assumed to be complete" set M is found to not be complete. But the contradiction Cantor actually used in the second argument only is about E0, not M.

And no, I won't apologize for Cantor not making this distinction clearer. THIS IS NOT THE THEOREM HE WANTED TO PRESENT. It is an example of that theorem. It is an example of how the power set of an infinite set like N={1,2,3,4,...} cannot be put into a bijection with N. Find the rest of the same paper to see its proof, which is far more formal.