Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
No. Axiom of regularity does not need to prove this result. –  tetori Aug 11 '13 at 10:00
1  
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. –  coffeemath Aug 11 '13 at 10:01

3 Answers 3

up vote 3 down vote accepted

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$.

share|improve this answer
    
+1 for cuteness! –  Peter Smith Aug 11 '13 at 14:56

Nonexistence of this set can be shown that using the Cantor's theorem:

Cantor's theorem. There is no injection between $\mathcal{P}(X)$ to $X$.

and Cantor's theorem can be shown that without the axiom of regularity. Here is the proof:

Proof the Cantor's theorem. Let $r$ is the injective function between $\mathcal{P}(X)$ to $X$. Let we define $$R=\{x\in \mathcal{P}(X) \mid r(x)\notin x\}$$ then $R$ ($\in\mathcal{P}(X)$) is the set by axiom schema of specification and $R\in R$ or $R\notin R$ must be hold. If $R\in R$, then $R\notin R$ by definition of $R$. And if $R\notin R$ then $R\in R$ because $R$ satisfies $R\notin R$. So we get a contradiction. So there is no injective function between $\mathcal{P}(X)$ to $X$.

Proof of there is no set satisfying $\mathcal{P}(X)\subseteq X$. If it exists, then $i:\mathcal{P}(X)\to X$, $i(x)=x$ is injective. It contradicts with the Cantor's theorem.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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