Proof a set cannot contain its own powerset - Russell's Paradox Using naive set theory and not using the cardinal number of a power set, how can you prove a set cannot contain its own power set?
Is this connected to Russell's Paradox?
 A: Yes, this is connected to Russell's paradox.
Given a set $S$, we can consider the "Russell set" built from $S$ - this is just $$\mathcal{R}_S=\{a\in S: a\not\in a\}.$$ The important thing to note is that this isn't necessarily paradoxical, since there is in general no reason to believe $\mathcal{R}_S\in S$. However, certain kinds of $S$ do yield paradoxes. The famous one is when we take $S$ to be the "set of all sets." Then:


*

*$\mathcal{R}_S\in S$, since $S$ contains all sets.

*If $\mathcal{R}_S\not\in\mathcal{R}_S$, then $\mathcal{R}_S$ is an element of $S$ not containing itself, so $\mathcal{R}_S\in \mathcal{R}_S$.

*If $\mathcal{R}_S\in\mathcal{R}_S$, then $\mathcal{R}_S$ must not contain itself since the only elements of $\mathcal{R}_S$ are sets which don't contain themselves; that is, $\mathcal{R}_S\not\in\mathcal{R}_S$.

*So we have a contradiction.

It turns out this line of reasoning also works if $S$ is just some set containing its own powerset! HINT:


*

*$\mathcal{R}_S\subseteq S$, always (why?).

*So $\mathcal{R}_S\in S$ in this particular case (what assumption about $S$ are we using here?).

*From that, we can just run the Russell argument above (do you see how?).
A: Assume $S$ contains all its subsets as elements. Some of those (e.g. $S$ itself) contain themselves (as elements), some (such as the empty set) do not.
Let $X \subseteq S$, $X\in S$ be the set of those subsets of $S$ that do not contain themselves. Does it contain itself? (If it does, then it doesn't and the other way round.) This contradiction concludes the proof.
