Does Cantor’s Theorem require Russell’s paradox

axiomsset-theory

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.

Best Answer

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.

Related Question