Stuck with proof for $\forall A\forall B(\mathcal{P}(A)\cup\mathcal{P}(B)=\mathcal{P}(A\cup B)\rightarrow A\subseteq B \vee B\subseteq A)$

Solution 1:

Here's a proof without contrapositive, if you prefer.

Suppose that $P(A) \cup P(B) = P(A \cup B)$. Then $A \cup B \in P(A \cup B) = P(A) \cup P(B)$. This means that $A \cup B$ is an element of either $P(A)$ or $P(B)$. Thus, either $B \subseteq A \cup B \subseteq A$ or $A \subseteq A \cup B \subseteq B$.

Solution 2:

Assume that neither $A \subseteq B$ nor $B \subseteq A$. Then there are elements $x \in A \setminus B$ and $y \in B \setminus A$.

Then the set $\{x,y\}$ is in $P(A \cup B)$ but not in $P(A) \cup P(B)$.

Solution 3:

Translating to the element level using $$V \in P(X) \;\equiv\; V \subseteq X$$ as the definition of $\;P(\cdot)\;$, this can be proved using a mostly straightforward calculation:

\begin{align} & P(A) \cup P(B) \;=\; P(A \cup B) \\ \equiv & \;\;\;\;\;\text{"set extensionality; in left hand side expand definition of $\;\cup\;$"} \\ & \langle \forall V :: V \in P(A) \;\lor\; V \in P(B) \;\;\equiv\;\; V \in P(A \cup B) \rangle \\ \equiv & \;\;\;\;\;\text{"definition of $\;P(\cdot)\;$, three times"} \\ & \langle \forall V :: V \subseteq A \;\lor\; V \subseteq B \;\;\equiv\;\; V \subseteq A \cup B \rangle \\ \Rightarrow & \;\;\;\;\;\text{"choose $\;V := A \cup B\;$} \\ & \;\;\;\;\;\phantom{"}\text{-- choosing a specific $\;V\;$ seems the best direction, given that we} \\ & \;\;\;\;\;\phantom{"}\text{are asked to prove a forward implication; and the other obvious} \\ & \;\;\;\;\;\phantom{"}\text{choices, $\;V := A\;$ and $\;V := B\;$, lead to set-theoretic tautologies"} \\ & A \cup B \subseteq A \;\lor\; A \cup B \subseteq B \;\;\equiv\;\; A \cup B \subseteq A \cup B \\ \equiv & \;\;\;\;\;\text{"set theory: simplify using $\;X \cup Y \subseteq X \;\equiv\; Y \subseteq X\;$, twice, and $\;Z \subseteq Z\;$"} \\ & B \subseteq A \;\lor\; A \subseteq B \\ \end{align}