I came to point where I suppose for case 1 that $A\subseteq B$ and conclusion is trivial. For case 2 I suppose that $A\not\subseteq B$ and try to prove $B\subseteq A$, but that gets me nowhere. Any pointers here are most welcome.
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)$
3 Answers
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}
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)$.
-
1Oh, you're right, although for this theorem it could be looked at both ways. Thanks anyway for quick reply. BTW, I like the step with creating additional set very much. :) – 2012-11-28
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$.
-
1I still think @MattN. your idea with intermediary set is great, but Manny is closer to what I had in mind. I saw technique with intermediary sets in one proof long time ago, so it seems it is a well known approach. I thank both of you for help. – 2012-11-28