In Jech's book, one of the very first exercises at the end of the first chapter is to show that there is no set $X$ that

$\mathscr{P}(X) \subseteq X$

With the axiom of regularity it's extremely easy, since $X \in \mathscr{P}(X)$ and therefore $X \in X$.

But it's so early he's hardly mentioned that axiom at this point, saving it for a later chapter. So I wonder if I'm missing something and that there's another reason this can't happen?

If there were some such set $X$, then it would have to contain $\varnothing$ and itself, and then also {$\varnothing, X$}, and then {$\varnothing, X,$ {$\varnothing, X$}}, and more in the same way.

It seems pretty clear no finite set could satisfy this, and I have no clue how to show a set like {$\varnothing, X,$ {$\varnothing, X$}$,$ $...$} exists, but I can't see how to show it doesn't exist either (without Regularity).

  • $\begingroup$ No. Axiom of regularity does not need to prove this result. $\endgroup$
    – Hanul Jeon
    Aug 11, 2013 at 10:00
  • 1
    $\begingroup$ It can be shown provided you know there is no injection from the power set of X to X, since an inclusion is a specific kind of injection. $\endgroup$
    – coffeemath
    Aug 11, 2013 at 10:01

2 Answers 2


This seems to call for Cantor's diagonal argument: There is no surjective map $X\to \mathscr P(X)$, but there is a shortcut not even using the concept of map.

Using the Axiom Schema of Separation, we define $$S=\{\,x\in X\mid x\notin x\,\}.$$ In other words, we have $$ \forall x\colon(x\in S\leftrightarrow (x\in X\land x\notin x)),$$ hence specifically $$ S\in S\leftrightarrow (S\in X\land S\notin S).$$ By mere first order logic (namely: $p\leftrightarrow (q\land \neg p)$ is equivalent to $\neg p\land\neg q$, hence implies $\neg q$) we infer $S\notin X$. Since $S\in\mathscr P(X)$ by definition, this shows $\mathscr P(X)\not\subseteq X$.


First of all, you are right it isn't easy to show that the set $S_X= \{\varnothing, X, \{\varnothing, X\}, ...\}$ exists or doesn't exist. In fact taking $X=\{\varnothing\}$ the existence of $S_X$ is the "Axiom of Infinity" and is known to be independent from all other axioms of ZFC. However, the existence of such a set, doesn't give you a counterexample.
Now to answer your question: If $\mathscr{P}(X) \subseteq X$, then there is a surjection $f:X \to \mathscr{P}(X)$ defined by $x \to x$ if $x \in \mathscr{P}(X)$ and $x \to \varnothing$ otherwise. Let $A=\{x\in X: x \notin f(x)\}$. Since $A \in \mathscr{P}(X)$, $f(A) = A$. By definition of $A$ we have $A \in A$ if and only if $A \notin A$ giving the desired contradiction.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.