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.

Here is my proof, I would appreciate it if someone could critique it for me:

To prove this statement true, we must proof that the two conditional statements ("If $\mathcal{P}(A)⊆ \mathcal{P}(B)$, then $A⊆B$," and, If $A⊆B$, then $\mathcal{P}(A)⊆ \mathcal{P}(B)$) are true.


Contrapositive of the first statement: If $A \nsubseteq B$, then $\mathcal{P}(A) \nsubseteq \mathcal{P}(B)$

If $A \nsubseteq B$, then there must be some element in $A$, call it $x$, that is not in $B$: $x \in A$, and $x \notin B$. Since $x \in A$, then $\{x\} \in \mathcal{P}(A)$; moreover, since $x \notin B$, then $\{x\} \notin \mathcal{P}(B)$, which proves that, if $A \nsubseteq B$, then $\mathcal{P}(A) \nsubseteq \mathcal{P}(B)$. By proving the contrapositive true, the original proposition must be true.


To prove the second statement true, I would implement nearly the same argument, so that isn't necessary to write. So, does this proof seem correct? Also, was the contrapositive necessary? Or is there another way to prove the initial statement?

share|improve this question

marked as duplicate by Asaf Karagila, Davide Giraudo, Dominic Michaelis, Alexander Gruber, ncmathsadist Mar 17 '13 at 0:23

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

8  
If $\mathcal P(A)\subseteq\mathcal P(B)$, then in particular $A\in\mathcal P(B)$, so $A\subseteq B$. There is no need to use contrapositive. –  Andres Caicedo Mar 16 '13 at 17:44
3  
You can prove the second statement directly as well: if $X\in\wp(A)$, then $X\subseteq A\subseteq B$, and therefore $X\in\wp(B)$. –  Brian M. Scott Mar 16 '13 at 17:48
2  
By hypothesis $X\subseteq A$ and $A\subseteq$, and $\subseteq$ is a transitive relation, so $X\subseteq B$. –  Brian M. Scott Mar 16 '13 at 17:52
2  
Oh, I see. Because $X$ is an element of the powerset of $A$, it must be a subset of $A$, etc. Thank you both for the help. –  Mack Mar 16 '13 at 17:55
2  
That’s right. (And you’re welcome.) –  Brian M. Scott Mar 16 '13 at 18:00
show 6 more comments

2 Answers

up vote 8 down vote accepted

Your argument is fine, if a little more roundabout than necessary: both directions can be done easily with direct proofs.

Suppose first that $\wp(A)\subseteq\wp(B)$. $A\subseteq A$, so $A\in\wp(A)\subseteq\wp(B)$, so $A\in\wp(B)$, and hence $A\subseteq B$.

Now suppose that $A\subseteq B$. Then for any $X\in\wp(A)$ we have $X\subseteq A\subseteq B$, so $X\subseteq B$, and therefore $X\in\wp(B)$. Thus, $\wp(A)\subseteq\wp(B)$.

share|improve this answer
add comment

I know you were asking for a critique of your original proof. But since I find text-based proofs (like yours, and the one from another answer) more difficult to read than symbolic ones, let me answer by presenting the way in which I would write a proof for this.

Proof. For all sets A and B,

$$ \begin{array}{ll} & \mathcal{P}(A) ⊆ \mathcal{P}(B) \\ \equiv & \;\;\;\text{"definition of ⊆"} \\ & \langle \forall V : V \in \mathcal{P}(A) : V \in \mathcal{P}(B) \rangle \\ \equiv & \;\;\;\text{"definition of $\mathcal{P}$, twice"} \\ & \langle \forall V : V ⊆ A : V ⊆ B \rangle \;\;\;\;\;\;\;\;\;\;\;\; (*) \\ \equiv & \;\;\;\text{"see below"} \\ & A ⊆ B \\ \end{array} $$

which proves this theorem. The forward direction in the last step is easily proven:

$$ \begin{array}{ll} & \langle \forall V : V ⊆ A : V ⊆ B \rangle \\ \Rightarrow & \;\;\;\text{"choose $V := A$; $A ⊆ A$"} \\ & A ⊆ B \\ \end{array} $$

For the other direction, assuming $A ⊆ B$ we prove $(*)$ as follows: for every $V$,

$$ \begin{array}{ll} & V ⊆ A \\ \Rightarrow & \;\;\;\text{"A ⊆ B, and ⊆ is transitive"} \\ & V ⊆ B \\ \end{array} $$

Note. This is the style of proof writing used in, e.g., A Logical Approach to Discrete Math by Gries and Schneider; it was originally designed by Dijkstra and Feijen, and is discussed in chapter "On our proof format" of Dijkstra and Scholten, Predicate calculus and program semantics, and (to provide a more accessible source) near the end of EWD1300.

The nice thing about this style is that the $\text{"hints"}$ show very clearly which properties are used: apart from predicate logic and the definitions of $\mathcal{P}$ and $⊆$, the above proof only uses the fact that $⊆$ is reflexive and transitive.

share|improve this answer
add comment

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