Jump to content

Talk:Cantor's diagonal argument

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia


Set of all sets

[edit]

Moved to arguments page. --Trovatore (talk) 06:30, 16 July 2021 (UTC)[reply]

diagonal counterexample

[edit]

Moved to arguments page. --Trovatore (talk) 06:30, 16 July 2021 (UTC)[reply]

In his 1891 article...

[edit]

"In his 1891 article, Cantor considered the set T of all infinite sequences of binary digits (i.e. each digit is zero or one):"

No, he didn't. In his 1891 article, Cantor considered a bicoloring by m and w. It is standard in wikipedia for modified proofs to be indicated as such and it is amateurish not to do so when the article itself is referred to by date and linked to in the footnotes. The proof should either conform to the reference or (if we're so endeared to the modification that we prefer it to the original) be indicated as an updated or simplified restatement thereof. — Preceding unsigned comment added by 2603:7000:8E03:3E7E:6979:D94F:B78E:B1DA (talk) 18:56, 15 November 2021 (UTC)[reply]

Cantor's proof is unrelated to binary sequences. Binary sequences are related to Cantor's proof. — Preceding unsigned comment added by 2603:7000:8E01:2B47:F8AA:FA7F:B5CA:53D8 (talk) 19:59, 19 April 2022 (UTC)[reply]

diagonal = contradiction

[edit]

Duplicate of talk:Cantor's diagonal argument/Arguments#diagonal_=_contradiction

Clarifying subtle points

[edit]

Most people learn CDA as a compact, one-step proof. If you assume that R (or sometimes the range [0,1]) can be enumerated, then you can prove that R has not been enumerated. The contradiction "disproves" the assumption.

Ignoring the fact that Cantor (explicitly) did not apply diagonalization to real numbers, this is not valid as a proof by contradiction. The supposed proof never uses the assumption that all members of R (or whatever set) are enumerated, only that the enumeration contains members of R. And the statement that is contradicted is the part of the assumption that isn't used. That is closer to a direct proof.

The previous Wiki did get all this right, but was subject to intentional misinterpretation. Many Cantor Doubters claim to "disprove' CDA based on this self-contradictory assumption. And use the previous text of this Wiki as evidence of what Cantor "did wrong." Since he did no such thing, the Wiki should not allow people to believe he did.

So I feel that several points needed to be made more explicit. First, that the diagonalization procedure is only ever applied to a subset of T that is known, not assumed, to be countable. Literally (in the notation used here), ""If s1, s2, …, sn, … is any simply infinite series of elements of T ..."

Technically, we should demonstrate that such subsets do exist, but examples are trivial and Cantor did not. So it is acceptable to not do so. Cantor proved that any countable subset of T necessarily omits an element s that is in T. This is the first part of a two-part proof.

But the second part is the important one: IfT is countable, then we know that the proven result applies to it without actually diagonalizing it. And the contradiction Cantor uses is not that T both contains, and does not contain, every sequence. It is that the sequence s both is, and is not, in T.

For reference, I use the translation at http://www.logicmuseum.com/cantor/diagarg.htm JeffJor (talk) 15:38, 23 March 2023 (UTC)[reply]

If you have a point in your above arguments, then I didn't get it. (Maybe you tried to elaborate on a typical fringe disproof, and make explicit where it is wrong?)
The proof in the article's current version is pretty clear. Introducing (as you did in your recent edit) a set S = { s1, ..., sn, ... } doesn't add clarity, imo; this is whhy I reverted you. - Jochen Burghardt (talk) 16:43, 23 March 2023 (UTC)[reply]

Notion orthogonal to theorems

[edit]

With respect to this edit, what does it mean to say that a notion is orthogonal to a theorem? It doesn't mean anything to a lay reader; does it mean anything to mathematically-trained readers? MartinPoulter (talk) 16:37, 22 April 2023 (UTC)[reply]

The word seems to have survived a lot of rewriting, particularly since about March this year, but has been there for longer in a slightly different sentence and place in the paragraph with an explicit concrete example, through which it may have been clearer at the time. I think those last two sentences from the section 'Ordering of cardinals' back then might make it clearer. I don't think 'orthogonal' is used in a particularly technical mathematical way here though. It seems it just means to say that they don't particularly have much to do with each other, that subcountability is irrelevant to the statement about the cardinality, countability and uncountability and is independent in that it doesn't really immediately have anything to do with that. I think really just to say that, since it is defined in terms of surjection, it has no bearing on theorems about injections, so in that way they are independent. It is just a certain broader meaning of orthogonal.
The newer wording appears to simply be more general, I am not certain the wording about orthogonality of a notion is the best and clearest, perhaps it should be expanded a bit with explanation, but I think what is meant is as simple as that subcountability is defined in terms of surjection, so anything being subcountable has to do with surjections, and theorems about injections are about injections, which is something else than surjections. So one could prove theorems or assert things about the one without that necessarily having bearing upon stuff to do with the other. MathsWolf (talk) 12:15, 15 June 2023 (UTC)[reply]
Thanks User:MathsWolf for the explanation. Glad to hear from someone much more familiar with the topic than I. Would you like to have a go at rephrasing that sentence so the word "orthogonal" isn't used. It's an unfamiliar term to a lot of readers and it seems excessive precision to use that when the intended meaning is something like "irrelevant" or "different". Cheers, MartinPoulter (talk) 15:05, 15 June 2023 (UTC)[reply]

not written for the average user

[edit]

like so many math/logic/science articles, this is not written for the average user
why are you math people so bad at describing stuff in terms an ordinary person can understand ?
that is mean; that is just reality — Preceding unsigned comment added by 2601:197:d00:3ca0:adb1:4bc0:d097:b9a6 (talk) 04:12, 21 February 2024 (UTC)[reply]

You are more than welcome to suggest improvements to the article, including ways it can be made more understandable to more readers. --Trovatore (talk) 20:30, 23 February 2024 (UTC)[reply]
Nice paradox! He says he can't understand it so you suggest he rephrases it!  :) BioImages2000 (talk) 11:49, 21 May 2024 (UTC)[reply]
There was no actionable complaint in the post. Comments that just whine about the article being too hard to understand are of minimal value. If they give specifics as to where they're getting stuck, there might be something to fix. --Trovatore (talk) 21:10, 21 May 2024 (UTC)[reply]

Cantor proved this for reals in [0,1]--for a reason

[edit]

The page needs to clearly state that these strings of digits represent binary fractions between 0 and 1 inclusive.

This version of the proof differs from Cantor's original in two ways: (1) it uses base 2 numbers instead of base 10 numbers; and (2) it uses arbitrary strings of digits--which include leading zeros-- rather than place notation. The proof as given holds for arbitrary strings of digits, but not if the digits are interpreted as numbers.

When digits are used to express whole numbers, leading zeros are not significant. 1 = 01 = 001 = 0001 = 000001 etc. So too with rational and real numbers greater than 1: 1.1 = 01.1 = 001.1 = 0001.1, etc. That is why Cantor used decimal fractions in [0,1]: 0.1 is different from 0.01. etc.

So in Wiki's form of the proof, to prove that the number 7 is missing from say a 6 row x 6 column table, one must show that 1 1 1 0 0 0, 0 1 1 1 0 0 , 0 0 1 1 1 0, and 0 0 0 1 1 1 are missing--since all these numerals represent the same number. That is not shown--and indeed is not true--making the proof (which is otherwise air-tight) invalid. Mgryan (talk) 01:50, 16 May 2024 (UTC)[reply]

The proof (text between "Cantor considered the set T of all infinite sequences of binary digits" and "Therefore, T is uncountable.") uses infinite sequences of binary digits. These are mathematical objects by their own, and are not interpreted as natural or real numbers. Lateron, in subsection Cantor's_diagonal_argument#Real_numbers, the uncountability of the set of real numbers between 0 and 1 is shown as a corollary. - Jochen Burghardt (talk) 05:20, 16 May 2024 (UTC)[reply]

Proposed disproof

[edit]

Consider the set of all numbers to N elements, there are 2 power N possible numbers. S only traverses N numbers so it can never keep up and lags further and further behind as N increases. Especially when N reaches infinity. So S is not-equal to only a small subset of the numbers in the set and may well equal one of the others. BioImages2000 (talk) 11:45, 21 May 2024 (UTC)[reply]

This belongs to the page Talk:Cantor's_diagonal_argument/Arguments. I'd recommend to try to make your argument "waterproof" before. - Jochen Burghardt (talk) 08:06, 22 May 2024 (UTC)[reply]
...or even "bulletproof" :) CiaPan (talk) 10:31, 22 May 2024 (UTC)[reply]
I am the only decent antiset theorist editor on Wikipedia.
The disproof is valid except is missing several parts. For one it should not be applied first to the general set theory diagonal argument but to the powerset proof that exponential of cardinal infinity does not equal the same infinity but rather its exponential only, second should point out certain tree proofs prove exponential of cardinal aleph0 does equal aleph0 . And a few other things missing.
the author is apparently not a mathematician so I don’t see that the arguments page would be appropriate, unless you people want to argue it amongst yourselves. Even then the arguments page doesn’t properly in its current form link, or post changes in Victor Kosko (talk) 23:32, 22 May 2024 (UTC)[reply]
Or post changes in watchlist Victor Kosko (talk) 23:37, 22 May 2024 (UTC)[reply]
You just have to add it separately to your personal watchlist. - Jochen Burghardt (talk) 04:13, 23 May 2024 (UTC)[reply]