# Does Cantor's Theorem require Russell's paradox?

Russell's paradox is that the set of sets $\{x\mid x\notin x\}$ contains itself if and only if it doesn't.

Cantor's theorem states that for any set $S$, its power set $\mathcal{P}(S)$ has greater cardinality. The proof of this (the one I know about) is by contradiction and goes as follows. Assume $S$ and $\mathcal{P}(S)$ have the same cardinality. Then there exists a bijection $f:S\rightarrow\mathcal{P}(S)$. Now consider the set $R=\{s\mid s\notin f(s)\}$. Since $R\subseteq S$, we have $R\in\mathcal{P}(S)$. Since $f$ is surjective, there must exist some $r\in S$ such that $f(r)=R$. We arrive at our desired contradiction upon noticing: $r\in R\iff r\notin R$.

There is some difference between Russell's paradox and the contradiction in the above proof. In the contradiction, $R$ is a subset of some fixed arbitrary set $S$ whereas in Russell's paradox, we seem to be working in the universe of all sets. In the contradiction, there is this function $f$ distinguishing the element $s$ from its image, whereas in Russell's paradox, we talk directly about whether $x$ is a member of itself.

I'm interested in how significant or profound those differences are.

• Cantor's theorem is not a paradox. It states that for any set $S$, there is no surjective function from $S$ to its powerset $\mathcal{P}(S)$. The proof is by the (constructive) argument that if $f$ is a function $S \to \mathcal{P}(S)$, then $\{x \in S \mid x \not\in f(x)\}$ is a subset of $S$ that is not in the range of $f$. This uses the (restricted) axiom of specification, but there is nothing paradoxical about it. – Rob Arthan Aug 19 '18 at 20:47
• "I wonder what axiomatic structure might avoid Russell's paradox while allowing us to still prove Cantor's theorem" -- ever heard of ZFC? – Henning Makholm Aug 21 '18 at 20:24
• @HenningMakholm Oh yeah. I admit I should have thought more about this question before posting it. – j0equ1nn Aug 21 '18 at 21:39
• Russell discovered his "paradox" reflecting on Cantor's Th; see : Ivor Grattan-Guinness, How Bertrand Russell discovered his paradox, HistMath (1978). – Mauro ALLEGRANZA Aug 30 '18 at 10:34
• @MauroALLEGRANZA Thank you! This historical perspective on how the ideas connect seems exactly what I was unknowingly yearning, I'm definitely going to check out that article in detail. – j0equ1nn Sep 1 '18 at 18:36

In the latter 19th century when Set Theory as an area of general study was beginning, it was often assumed that we could assume the existence of the set of all and only those things that had any specific property $P$. This is known as the Axiom Schema of Abstraction. (A "schema" because it it an infinite list of axioms, one for each property $P$ that you can state.) Russell showed this was illogical because the assumption that $\{x:x\not \in x\}$ exists is paradoxical.(Note: It does not depend on any definition of what $\in$ means. Russell offered the Barber Paradox to illustrate this: A barber shaves all those and only those who don't shave themselves. Does the barber shave the barber? For barber, read "set". For shaves, read "contains as a member".)

One remedy was to eliminate Abstraction and replace it with the schema of Comprehension (Specification): Informally it says that if $X$ is a set then there exists a set $Y$ whose members are all,and only, those members of $X$ that have some specified property. The crucial difference is that, although we can say that if a set $X$ exists then $Y=\{x\in X:x\not \in x\}$ exists, we cannot prove from Comprehension that $\{x:x \not \in x\}$ exists.

Comprehension also implies, by contradiction, there is no set $V$ of all sets. Otherwise we would have the set $\{x\in V: x\not \in x\},$ which would be $\{x:x\not \in x\}$ and we'd have Russell's Paradox again.

As already stated in other responses to your Q, Cantor's theorem does employ an instance of Comprehension.

BTW. The original names for some (most?) of the axioms of modern set theory were not English and different writers have at times used different English names for them. "Extensionality" (Informally, sets $X$ and $Y$ are equal iff they have the same members) is also called Regularity... And some textbooks combine the Comprehension schema and the Separation schema into a single schema, which they also call Separation.

I recommend the short introductory text on Set Theory by Suppes.

• This is helpful. Thanks also for the reference. I'm wondering if this answers the follow up question in my post, about axioms that support one part but not the other. If we eliminate the axiom schema of abstraction, but not the axiom schema of specification, does that give a scenario wherein Russell's paradox is resolved, yet we can still prove Cantor's theorem? – j0equ1nn Aug 20 '18 at 3:26
• Russell's Paradox can't be "resolved". It can be avoided. Basically Russell showed that the axiom (i.e. the assumption ) $\exists S\;\forall x\;(x\in S\iff x\not \in x\}$ is inconsistent. So we should not include that assumption among our axioms. – DanielWainfleet Aug 20 '18 at 11:44
• Does eliminating the axiom schema of specification give a scenario wherein Russell's paradox is avoided, yet we can still prove Cantor's theorem? – j0equ1nn Aug 21 '18 at 20:12
• @j0equ1nn I think this is quite obvious if you think about Daniel's answer for some more time. – Cave Johnson Aug 21 '18 at 20:21
• @j0equ1nn I like your question very much :-) When I first learned Cantor's theorem, I spent a lot of time pondering without success how to make sense of power set now that Russell's paradox is there. How I hope I had seen a question like yours and read these answers... – Cave Johnson Aug 22 '18 at 1:34

Cantor's theorem is a theorem, not a paradox.

Russel's paradox is also not a real paradox, but really a very short and elegant proof that the class of all sets is not a set.

The proof of Cantor's theorem uses a very similar idea as that of Russel's. This is not so surprising, as the conclusions are also related. It is very easy to deduce from Cantor's theorem that the class of all sets is not a set.

I hope this helps clearing the confusion.

• I'd argue that Russell's paradox doesn't necessarily say this about a universal set, the evidence being NF(U) or Church set theories. It does show that the full naïve comprehension axiom scheme is simply inconsistent. – Malice Vidrine Aug 19 '18 at 22:35
• This does not go into enough detail to clear the confusion. My issue is about the difference between the contradiction arising in the proof of Cantor's theorem, and Russell's paradox. As for what is or isn't a "real paradox," that is another conversation. – j0equ1nn Aug 20 '18 at 3:23
• What do you mean by Russel's paradox is also not a real paradox? Russel's paradox is of course real. What paradox are you qualified for real? – Math Wizard Aug 25 '18 at 18:39
• So far, none, fortunately. Otherwise, I would have to look for another job. But it is possible that some of our beloved systems of axioms is inconsistent. – A. Pongrácz Aug 25 '18 at 20:04
• Russel's paradox is real because it causes damage to entire set theory -- foundation of mathematics. Some paradoxes are not considered as real because their existence will not change the foundation of mathematics. For example, Banach-Tarski paradox may not be real because doubling the ball would not threat foundation of mathematics despite it causes controversy. – Math Wizard Aug 29 '18 at 17:20