Prove that $ A \subseteq B \iff \mathcal{P}(A) \subseteq \mathcal{P}(B) $.

Question

I'm going through Velleman's How To Prove It and I'm currently on section 3.4 which deals with techniques for proofs involving conjunctions and biconditionals. The title of this question is from one of the exercises. To prove it, I started with a proof that $ A \subseteq B \implies \mathcal{P}(A) \subseteq \mathcal{P}(B) $, where $\mathcal{P}(A)$ is the power set of $A$.

Suppose $ A \subseteq B $. Let $x$ be arbitrary. Suppose that $x \in \mathcal{P}(A)$, or in other words, that $x \subseteq A$. Let $y$ be an arbitrary member of $x$. Then since $x \subseteq A$ and $A \subseteq B$, $y \in A$ and $y \in B$. Because we assumed $y$ was an arbitrary member of $x$ and we concluded that $y \in B$, it follows that $x \subseteq B$. Thus, $x \in \mathcal{P}(B)$. But $x$ was also arbitrary, hence $\mathcal{P}(A) \subseteq \mathcal{P}(B)$. Therefore, if $ A \subseteq B $, then $\mathcal{P}(A) \subseteq \mathcal{P}(B)$.$_\square$

However, I'm wondering whether this constitutes a valid proof. Earlier in the book Velleman claims that one can prove statements of the form $\forall xP(x)$ by assuming $x$ is arbitrary and proving $P(x)$. He mentions one restriction: one must not make any assumptions about which particular object $x$ stands for. My question is whether the step of assuming $x$ was a subset of $A$ via the assumption that it was an arbitrary member of $\mathcal{P}(A)$ is completely valid. I was used to problems where $x$ was an arbitrary member of a set $A$ containing no sets, or where $A$ was an arbitrary member of a family of sets $\mathcal{F}$, but this struck me as being different in a non-trivial sense.

Edit: Thank you all. I guess I was unduly skeptical of what was allowed in a proof like this one.

not sure if I understand your question. your problem is with the assumption: $x \in P(A)$? — Loreno Heer, Jan 18 '15 at 01:20
In general, whether the proof is correct. In particular, whether that step is valid. — MuchToLearn, Jan 18 '15 at 01:22
@user1542938 yes the step is valid. yes the proof is correct. — Loreno Heer, Jan 18 '15 at 01:22

score 1 · Answer 1 · answered Jan 18 '15 at 01:24

The definition of the power set is $\mathcal{P}(A) = \{x: x\subseteq A\}$, i.e., $\mathcal{P}(A)$ is the set of all subsets of $A$. This is then a family of sets, so choosing an arbitrary element of $\mathcal{P}(A)$ will give a set $x$, and this is indeed a subset of $A$.

score 0 · Accepted Answer · answered Jan 18 '15 at 01:25

To cut it down, the proof is effectively:

Suppose $A \subseteq B$. Let $x$ be arbitrary. If $x \in \mathcal{P}(A)$ then $x \in \mathcal{P}(B)$, because . . . . So $\mathcal{P}(A) \subseteq \mathcal{P}(B)$.

That is a valid proof so long as you are happy with the "Tf . . . then . . ." sentence, which is indeed valid here since $\subseteq$ is transitive.

Prove that $ A \subseteq B \iff \mathcal{P}(A) \subseteq \mathcal{P}(B) $.

2 Answers2