Talk:Cantor's diagonal argument/Archive 3

Archive 1

Archive 2

Archive 3

Constructivist interpretations

The late User:Futonchild added a problematic section which I tried to shape into something that was at least meaningful, but frankly it's still problematic. It goes like this at present:

The interpretation of Cantor's result will depend upon one's view of mathematics, and more specifically on how one thinks of mathematical functions. In the context of classical mathematics, functions need not be computable, and hence the diagonal argument establishes that, there are more infinite sequences of ones and zeros than there are natural numbers. To those constructivists who countenance only computable functions, Cantor's proof (merely) shows that there is no recursively enumerable set of indices (for example, Gödel numbers) for the programs computing them.

Now, I think it is true that constructivists, or at least some of them, do not accept the "quantity" interpretation of the argument. It seems to me, though, that to deny the quantity interpretation, they're pretty much obliged by the argument to deny that the sequences of zeroes and ones can be collected into a completed totality. They are not really saying, that is, that there are only as many sequences of zeroes and ones as there are natural numbers, even if the only sequences they accept are the computable ones, because for coherency's sake the only enumeration of sequences they could accept is a computable one (say, a computable enumeration of Turing machines that produce total sequences, or a global computable function giving the nth bit of the mth sequence), and Cantor's argument (which by the way is intuitionistically valid) excludes that possibility. (I don't know any intuitionistic proof, on the other hand, that there's no injection from the sequences into the naturals; it's conceivable that some intuitionists believe that the existence of such an injection is "not false".)

Anyway, I think the current text is unsatisfactory, but I don't want to just delete it out of hand; there probably are constructivist interpretations that deny the proof is about "quantity", and they should be fairly represented. Can anyone help out here, especially with versions that might be attributed to specific constructivist/intuitionist thinkers? --Trovatore 07:00, 14 March 2007 (UTC)

Your parenthetical remark about injections is close. I'm not sure but I think your proposed injection is still inconsistent, on the other hand it is quite consistent to assert a partial surjection from the naturals to the infinite bit sequences, i.e. that the infinite bit sequences are subcountable. Clearly this contradicts the "quantity interpretation" because although the naturals and infinite bit sequences are not in bijection, each one can be seen as a partial image of the other. Now pardon me while I fix this redlink. --99.234.59.230 (talk) 03:34, 4 January 2008 (UTC)

Could someone explain how $f:s\rightarrow T$ can have a partial surjection (i.e. be subcountable)? If the proof shows that there exists $T_{x}$ such that there does not exist a corresponding $s_{x},$ doesn't that mean that f is not surjective? If I'm understanding partial surjection correctly, it just means that the function is surjective and it is also a partial function. If f is not surjective, how can it have a partial surjection? StardustInTheDark (talk) 15:10, 25 November 2017 (UTC)

Confusion

In the section An uncountable set, it says

This sequence s_i is countable, as to every natural number n we associate one and only one element of the sequence.

And then below the example sequence, it goes on to state

For each m and n let s_m,n be the n^th element of the m^th sequence on the list. So, for instance, s_2,1 is the first element of the second sequence.

Is the n above and below the same? The same goes for the words "sequence" and "element".

Above the example sequence, the text appears to use the terms "sequence" and "element" in terms of the higher hierarchy, i.e. "sequence" referring to the list of numbers, and "elements" referring to individual sequences (i.e. lines), and n appears to refer to the numbering of the elements of the list of sequences.

Below the example sequence, individual sequences from the list (i.e. the "meta-sequence") are discussed as sequences, and now "element" refers to the position after decimal point within each individual sequence.

Could this be clarified? Maybe I'm just not understanding it properly, but I believe it's not just superficially confusing but actually nonsensical because the same terms (and the variable n) are used first in higher-order context, then in lower-order context. Or am I missing something here? --84.44.158.71 (talk) 18:38, 6 October 2012 (UTC)

No, there's no confusion as both n are preceded by words 'every' or 'each'. These two are separate statements, each of them describes its domain and each of them uses its own n to denote a variable from the domain. Of course we might force using different character to denote variables for each sentence in the text, but there is no need to do so. Anyway our alphabet is too short to do that even in medium-size mathematical text, not to mention integral tables... --CiaPan (talk) 18:51, 7 October 2012 (UTC)

And there's no 'decimal point' in any of the sequences discussed in that section. --CiaPan (talk) 18:38, 9 October 2012 (UTC)

You don't understand the mathematics involved. --213.196.218.202 (talk) 11:48, 6 November 2012 (UTC)

Does this create only a single sequence that falls outside of the enumeration rules?

I'm not a mathematician, but the way the article is currently worded, a very cursory glance implies that this argument results in the construction of one and only one sequence that is present in the collection but not given in the enumeration.

If that is the case, why couldn't the enumeration rules be redefined to simply give that one single special case as S1 as the rest of the sequences starting at S2, S3, S4, etc. ? Seems like a rather obvious solution. If functions can have piecewise definitions; why not enumerations? Element S1 equals == Foo, Elements S2-S[infinity] == Bar.

The article on countability says "Whether finite or infinite, the elements of a countable set can always be counted one at a time and, although the counting may never finish, every element of the set is associated with a unique natural number." Right. I think I get that. So, uhhhhhh...just adjust your enumeration ordering rules to be slightly messier. Problem solved? At least in the context of Cantor's Argument.

But if Cantor's argument implies the existence of more than one sequence excluded from the enumeration and these exclusions cannot be ordered, perhaps the article could make that more clear?

I'm not trying to claim I've revolutionized mathematics here with my 5 minutes of article skimming and thought; I'm just saying the description of the proof as-is fails to clearly explain why one could not write a set of piecewise-defined enumeration rules to put the elements of T in a one to one relationship with the natural numbers. Blue Rock (talk) 19:52, 25 October 2017 (UTC)

No, the proof is fine as it is. What you're missing is that the proof works for any proposed enumeration. If there is one, you reach a contradiction; therefore, there isn't one. This is a fundamental point of logic.

If you want to discuss how the point can be made clearer, we can do that here, but if you want more explanation on a personal level, please ask a question at WP:RD/Math. --Trovatore (talk) 20:01, 25 October 2017 (UTC)

I understand how proof by contradiction works, thank you. Please read my post more carefully. The article does not explain at all how this would apply to any possible enumeration scheme; in fact it completely glosses over Cantor's chosen scheme, which I have not dissected or thought about yet in any great detail. If Cantor's diagonalization argument does not construct more than this one single contradiction, then one could simply construct a new enumeration scheme simply by specifying that one known, definable sequence as my S1, then use Cantor's rules--new S2 is Cantor's S1, new S3 is Cantor's S2, etc. I'm still reading but the article on this argument, as it is currently worded, does not appear to address how Cantor's diagonalization could be used to rule out piecewise defined enumeration rules. Blue Rock (talk) 20:15, 25 October 2017 (UTC)

The article does in fact explain how it would apply to any possible enumeration scheme. --Trovatore (talk) 20:18, 25 October 2017 (UTC)

Mmmm... sort of. Not terribly well but yes after a few more minutes of thought I think I see what the main idea is that I've completely overlooked here. The construction of the contradiction is permitted to be even more "piecewise" as you are basically are allowed to "look" at the entire sequence and contradict each term individually. Uh, well ok then. Nevermind. There is actually still an interesting argument (not for this talk page, sure sure) to be had here in that what happens if you allow the rules for enumeration to explicitly contradict the rules for generating the contradicting sequence, which results in an undecidable stalemate (between the enumeration ruleset would be trying to defeat the ruleset for generating the contradiction). I grant that said stalemate would result in no enumeration being possible for an infinite set of infinite sequences, so in that respect I guess Cantor wins. But what do you call a self-referential set of rules that cannot in fact end up generating any enumeration because they (impossibly) seek to deny the possibility of this particular hand-crafted contradiction? The rule set I am describing exists. It has no logically consistent interpretation, but it surely exists in the same way that undecidable statements in formal logic exist.

So...on reflection, I must insist I do still have a point, but it's convoluted enough to fall outside of the scope of the article. Carry on, then. Blue Rock (talk) 21:02, 25 October 2017 (UTC)

Summary: my own brief comprehension issue was that in the "Uncountable set" section, the article did not seem to provide either the function to generate the ordered sequences or the function to generate the contradiction. If it had, it might have been clear at a glance that a generalization of the formalization to generate the contradiction was, well, just a wrapper around the function to generate the sequences. In that case, of course you can't ever beat it. But you CAN "tie" it. If the function to generate the ordered sequences were able to refer to the function that generates the proof-by-contradiction sequence--if it were a FAIR fight, so to speak, with the contradiction function and the enumeration function both allowed to refer to each other--you could at least create an unsolvable contradiction such that no stable enumeration was possible. Which I maintain is not the same thing as merely generating an incomplete enumeration. The significance of that observation, I don't know. But I do believe I have a small point here about the clarity of the article, and there is thus an argument for a more formal treatment in the Uncountable Set section, though I'd understand if we're just trying to keep the example as simple to grasp as possible. But these misunderstanding will tend to crop up when infinity is involved. Blue Rock (talk) 21:51, 25 October 2017 (UTC)

"Cantor" as agent in the argument

As the article currently explains the argument, there's a lot of Cantor does this, Cantor does that, as though he were personally constructing the counterexample to a proposed enumeration.

I know we didn't actually invent this style; I've seen it before, and it probably does exist in some RS. But that doesn't mean we have to use it. It kind of grates on me. Does anyone object to changing the exposition so that we can give Cantor's spirit some rest, instead of constantly requiring him to be involved in the argument? --Trovatore (talk) 22:18, 25 October 2017 (UTC)

Cantor killed my father. He deserves no rest. Blue Rock (talk) 22:19, 25 October 2017 (UTC)

(I have no opinion on it as a matter of style but I did feel unable to resist adding that, sorry) Blue Rock (talk) 22:21, 25 October 2017 (UTC)

Trovatore makes a good point that Cantor is mentioned too often in the diagonal argument proof. I eliminated some of the mentions of Cantor and only kept those relevant to the strategic decisions that he made. Namely, he separated his proof into two parts: a constructive part and a proof by contradiction to prove uncountability. This mention of Cantor is important because it's historically accurate and because Cantor used this approach whenever possible. Too many accounts of Cantor's work leave out the constructive part of his proofs. This has led to Cantor being credited for non-constructive proofs that he did not publish and then these proofs are critiqued as just pure existence proofs. Another example of Cantor giving constructive arguments can be found in Cantor's first set theory article where his constructive argument leads to both the construction of transcendental numbers and the uncountability of the real numbers. By the way, I also made a small change to the non-constructive proof of "T is uncountable" that clarifies the contradiction. --RJGray (talk) 21:50, 14 January 2018 (UTC)

du Bois-Raymond and Cantor's diagonal argument

An edit saying du Bois-Raymond invented the argument earlier was reverted, correctly I believe. However there probably should be something here about the attribution and why it is wrong and there is the chance that Cantor was inspired by d Bois-Raymond's proof as he had an interest in infinity and infinitesimals. See note 1 page 187 in Simmons, Keith (1993). Universality and the Liar: An Essay on Truth and the Diagonal Argument. CUP. p. 187.. Dmcq (talk) 18:02, 9 January 2018 (UTC)

The line removed was

Historically, the diagonal argument first appeared in the work of Paul du Bois-Reymond in 1875.

Du Bois-Reymond, Paul (1875), "Über asymptotische Werte, infinitäre Approximationen und infinitäre Auflösungen von Gleichungen", Mathematische Annalen, 8 (3): 363–414, doi:10.1007/bf01443187

Dmcq (talk) 18:09, 9 January 2018 (UTC)

I will restore the reference to du Bois-Reymond together with a book on his work by G. H. Hardy, where the diagonal argument is explained.nikita (talk) 17:37, 25 July 2020 (UTC)

What's the problem with this disproof?

Hi, I'm not a mathematician, but I've always thought this theorem was false, and I thought somebody might have an intelligent opinion. Here is an explanation of why:

1. Define an enumeration A of all expressions in language (e.g. by enumerating sequences of letters and symbols).

2. Define an enumeration B of all infinite sequences of binary digits, as those items in A which define infinite sequences of binary digits. This will be the enumeration used for Cantor's Theorem.

3. Cantor's additional sequence must be within A, because it is written in language. For example, A must contain "The additional sequence that will be defined in terms of B for Cantor's Theorem."

4. If this additional sequence defines an infinite sequence of binary digits, then it will be an element of B with an index n. However, because of the nature of its definition, its nth digit would be its own complement.

5. Therefore, the additional sequence does not define an infinite sequence of binary digits. The sequence Cantor proposes to generate does not exist in this case.

Furthermore, there are multiple ways of writing a description of a sequence in language, implying a 1-to-1 mapping of describable sequences to natural numbers, but not of natural numbers to describable sequences. There are more natural numbers than describable sequences.

I mentioned this to my high school calculus teacher in class around 2001, and this point is where the argument stalled. Xloem (talk) 21:03, 10 October 2018 (UTC)

Hi Xloem. Per the talk page guidelines, the article talk pages are for discussing improvements to the article. If you have general questions about the subject matter, you can ask at the math reference desk. Also, this talk page has an arguments subpage. --Trovatore (talk) 21:11, 10 October 2018 (UTC)

Pinging OP: Xloem. --CiaPan (talk) 07:29, 11 October 2018 (UTC)

A quickie though, any more should go to the arguments page, in step one you are at best describing the computable numbers. And the argument can be used to show one can't list out the computable numbers even though they are countable.This is the Halting problem. Dmcq (talk) 10:58, 11 October 2018 (UTC)