Proof a set cannot contain its own powerset - Russell's Paradox [closed]

Solution 1:

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?).

Solution 2:

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.