Talk:Cantor's theorem

Proof "via barber paradox"

The proof section currently has the sentence: "For a finite set, the proof can also be illustrated using a more prosaic presentation known as the barber paradox.[4]" (I'll refer to this sentence as 'the sentence'.)

I wish to remove the sentence and will proceed to try to do so; I also recognise that the sentence is probably added with good intent and I think that removing content (especially when written by someone else) should be well motivated. I give my motivation here.

I will argue (in kettle-argument style) that: - the proof presented in [4] is precisely the proof already in the preceding article, hence the sentence is wrong. - the sentence is irrelevant. I believe that either of these reasons should be sufficient to remove the sentence.

First, I will argue that the sentence is wrong. Unfortunately, I don't have access to [4] in full. I was able to read up to page 196 here (that is, page 197 is missing): https://www.google.com/books/edition/The_Popularization_of_Mathematics/_PyT1x62oHwC?hl=en&gbpv=1&dq=isbn:9780521403191&printsec=frontcover this page explains how the proof of Cantor's theorem is used for one of the Christmas lectures, and gives the first definitions. These definitions match precisely the definitions used on the transparency in those Christmas lectures (last quarter of this video): https://www.rigb.org/christmas-lectures/watch/1978/mathematics-into-pictures/infinity-and-perspective

It therefore seems to me that [4] is an accurate description of the Christmas lectures. In those Christmas lectures, modulo some notation (2^A instead of P(A), and card(A) = card(B) is simply written as A = B – equality on sets is never used so the equality symbol is overloaded), the proof is exactly as in the wikipedia article (even though the presentation alludes to the barber paradox, it then proceeds to give a proof that follows similar lines as the barber paradox, it does not use the barber paradox as a proof step: it uses the contradiction already mentioned in the wikipedia article as a proof step). Moreover, the presentation makes it very clear that the proof is intended for infinite sets.

Next, let me argue that the sentence is irrelevant. This may be difficult to prove, because a sentence can convey multiple things and it is relevant if only one of them is. Two messages include 1) that there are alternate means to prove Cantor's theorem, and 2) that the proof of the Barber's paradox is related to Cantor's diagonalization argument. Both facts are already established on this wiki page, the first in the History section of this article, and the second in the "related paradoxes" section. Those sections are, I believe, a better place for those messages. The message that I believe is the main message this sentence tries to convey, is that there is a particular proof of Cantor's theorem. Alternative proofs would be valuable to know about, provided that they are not listed elsewhere in the same article (I argue in the above that this proof is listed in the article, but let's suppose I was wrong there). The problem with arguing relevance based on this, is that I am unable to reproduce a proof of Cantor's theorem based on the Barber's paradox. I also believe that the general audience for which this article is written will also be unable to reproduce the proof based on what is written here. (I cannot judge how easy something is to understand for something which I do not understand myself; I do have a background in discrete math and logic). To repeat the argument: even if the statement would have read "Cantor's theorem can also been proven via Pythagoras' theorem", that would only be relevant if the proof - or a rough outline thereof - were reproducible. I see no other reasons why this sentence could be relevant, and therefore claim that the sentence is irrelevant.

In conclusion, I don't believe the message the sentence is trying to convey (that there is an alternative proof in [4]) holds up, and I don't believe the sentence would be relevant if the sentence were true (for lack of clarity on how the alternative proof goes). I therefore decide to try and remove the sentence, which I will do after submitting this comment. (I write 'try' because I never understand how page locks work and when I can change something and when I cannot) Sjcjoosten (talk) 17:28, 23 June 2020 (UTC)

"Generalizations" section

The text said that the theorem had been generalised to any category with products and referenced a mathematics text but did not say anything else, so I went and looked up the reference and summarised that generalisation here. There are a few details missing that I am not sure if they ought to be included in the article. I am going to put those details here on the talk page, so if someone else thinks they do belong in the article text, they can add it themselves. (What is written below is not necessarily "article-ready".)

The notion of parameterising maps $T\to Y$ using a map $f:T\times T\to Y$ is mentioned. What this means precisely is: let $x:1\to T$ be an element of $T$. Then, by the nature of a product, there exists a unique map $(-,x):T\to T\times T$ such that $\pi _{1}\circ (-,x)=\operatorname {id} _{T}$ and

$T\to 1{\stackrel {x}{\to }}T=T{\stackrel {(-,x)}{\to }}T\times T{\stackrel {\pi _{2}}{\to }}T$

(i.e. this is a commutative square).

$f(-,x)$ is then simply the composition $f\circ (-,x):T\to Y$. If every map $T\to Y$ can be written as such a composition, we say that $f$ parameterises those maps (or that the elements of $T$ parameterise those maps using $f$).

The generalised result returns the set-theoretic result in the following way: let $2$ be an object with two elements, say $\operatorname {true} :1\to 2$ and $\operatorname {false} :1\to 2$ and with endomorphism $\operatorname {neg} :2\to 2$ such that $\operatorname {neg} \circ \operatorname {true} =\operatorname {false}$ and $\operatorname {neg} \circ \operatorname {false} =\operatorname {true}$. Now $\operatorname {neg}$ has no fixed points.

To parameterise the maps $T\to 2$ using a map $f:T\times T\to 2$ means to, for each map $g:T\to 2$, find an element $x_{g}:1\to T$ such that $f(-,x_{g})=g$. But the generalised theorem says we can not do this.

In the context of Set (the category of sets, where objects are sets and morphisms/maps are functions between sets), each map $g:T\to 2$ corresponds to a subset of the set $T$ ($g$ answers the question "is this element in the subset?" for each element $x$ of $T$). A parameterisation by $f:T\times T\to 2$ would mean associating each such $g$ with a distinct element $x_{g}$ of $T$; but this association would give us an injective function that takes any subset of $T$ as its input and return an element of $T$ as its output, i.e. an injection ${\mathcal {P}}(T)\to T$. Likewise, having such an injective function would give us such a parameterisation. Since this parameterisation is impossible, an injection ${\mathcal {P}}(T)\to T$ is impossible.

--superioridad ^(discusión) 20:29, 21 November 2023 (UTC)

Also, the text says the generalisation is for "any category with products", but the proof in the reference seems to only require finite products (or rather, binary products as well as terminal object = empty product, which is equivalent). --superioridad ^(discusión) 20:49, 21 November 2023 (UTC)