13
$\begingroup$

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?

$\endgroup$
11
  • 8
    $\begingroup$ 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. $\endgroup$ – Andrés E. Caicedo Mar 16 '13 at 17:44
  • 3
    $\begingroup$ 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)$. $\endgroup$ – Brian M. Scott Mar 16 '13 at 17:48
  • 2
    $\begingroup$ By hypothesis $X\subseteq A$ and $A\subseteq$, and $\subseteq$ is a transitive relation, so $X\subseteq B$. $\endgroup$ – Brian M. Scott Mar 16 '13 at 17:52
  • 2
    $\begingroup$ 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. $\endgroup$ – Mack Mar 16 '13 at 17:55
  • 2
    $\begingroup$ That’s right. (And you’re welcome.) $\endgroup$ – Brian M. Scott Mar 16 '13 at 18:00
17
$\begingroup$

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

$\endgroup$
10
$\begingroup$

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.

$\endgroup$

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