This is Velleman's exercise 3.3.4. Suppose $A\subseteq \mathscr P (A)$. Prove that $ \mathscr P (A)\subseteq \mathscr P ( \mathscr P (A))$. I started reexpressing the terms in their equivalent forms to discover relations I did not believe are possible. $A\subseteq \mathscr P (A)$ is equivalent to $\forall x(x\in A \rightarrow x \subseteq A)$. Is there such an x at all? Anyway, $ \mathscr P (A)\subseteq \mathscr P ( \mathscr P (A))$ is equivalent to $ \forall x (x\subseteq A \rightarrow x \subseteq \mathscr P (A))$. Setting x arbitrary I have:

  • Givens: $x\in A \rightarrow x \subseteq A$
  • Goal: $ x\subseteq A \rightarrow x \subseteq \mathscr P (A)$.

Two question:

  1. How do I proceed with the proof?
  2. Can someone please show an example where these relations actually hold?

Thanks in advance.

  • 3
    $\begingroup$ Can you prove that if $A\subseteq B$ then $\mathscr P(A)\subseteq \mathscr P(B)$? $\endgroup$ – Milo Brandt Jul 27 '15 at 23:42
  • $\begingroup$ @MiloBrandt: I believe that I can prove this. If $A\subseteq B$ and for all $x$ $x \subseteq A \rightarrow x \subseteq B$, then, assuming $x \subseteq A$ $x$ will be a subset of B because $A\subseteq B$. Correct? I still have difficulties applying this to the question I asked. $\endgroup$ – Eugene Jul 27 '15 at 23:56
  • 1
    $\begingroup$ Well, can you prove that if $A\subseteq X$ then $\mathscr P(A)\subseteq\mathscr P(X)$? What happens when you specialize this to $X=\mathscr P(A)$? $\endgroup$ – bof Jul 28 '15 at 0:34
  • 3
    $\begingroup$ possible duplicate of Set theory (containing Power Set) Need Help in a proof $\endgroup$ – Marnix Klooster Sep 15 '15 at 16:33

In general, if $A\subseteq B$, then $\mathscr P (A)\subseteq \mathscr P (B)$ because every subset of $A$ is a subset of $B$.

More formally, if $a\in \mathscr P (A)$, we need to show that $a\in \mathscr P (B)$. But this is trivial, since if $x\in a$, then $x\in B$ which implies that $a\subseteq B$ which is the same as $a\in \mathscr P (B)$.

Now take $B=\mathscr P (A)$ to obtain your claim.

For an example, take $A=\emptyset$. Then, $\mathscr P (A)=\left \{ \emptyset \right \}$, $\mathscr P(\mathscr P(A))=\left \{ \emptyset,\left \{ \emptyset \right \} \right \}$ and then $\mathscr P (A)\subset \mathscr P ( \mathscr P (A))$.


Your result is an immediate consequence of the following proposition.

Proposition. Suppose $X\subseteq Y$. Then $\mathscr P(X)\subseteq\mathscr P(Y)$.

Proof. Let $E\in\mathscr P(X)$. Then $E\subseteq X\subseteq Y$ so that $E\subseteq Y$. Hence $E\in\mathscr P(Y)$. This proves $\mathscr P(X)\subseteq\mathscr P(Y)$. $\Box$

Do you see how your problem is now a corollary?


$X\subset Y$ implies every element of X is an element of Y, so subsets of X are subsets of Y, so $\mathcal{P}(X)\subset\mathcal{P}(Y)$. Finally, for $Y=\mathcal{P}(X)$ you have $\mathcal{P}(X)\subset\mathcal{P}(\mathcal{P}(X))$.


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.