Suppose $A\subseteq \mathscr P (A)$. Prove that $\mathscr P (A)\subseteq \mathscr P ( \mathscr P (A))$

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?

• Can you prove that if $A\subseteq B$ then $\mathscr P(A)\subseteq \mathscr P(B)$? – Milo Brandt Jul 27 '15 at 23:42
• @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. – Eugene Jul 27 '15 at 23:56
• 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)$? – bof Jul 28 '15 at 0:34
• possible duplicate of Set theory (containing Power Set) Need Help in a proof – 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))$.