Suppose $\mathcal{P} (A) \cup \mathcal{P} (B) = \mathcal{P} (A \cup B) $. Then either $A \subseteq B$ or $B \subseteq A$.

elementary-set-theoryproof-verification

Prove that for any sets $A$ and $B$, if $\mathcal{P} (A) \cup \mathcal{P} (B) = \mathcal{P} (A \cup B) $, then either $A \subseteq B$ or $B \subseteq A$.

My attempt:
Suppose $\mathcal{P} (A) \cup \mathcal{P} (B) = \mathcal{P} (A \cup B) $. Either $A \subseteq B$ or $A \nsubseteq B$. Suppose $A \nsubseteq B$. Then there is an element $x_0 \in A$ such that $x_0 \notin B$. Suppose $x \in B$. Clearly $\{x, x_0 \} \in \mathcal{P}(A \cup B)$ so $\{x, x_0 \} \in \mathcal{P} (A) \cup \mathcal{P} (B)$. This means $\{x, x_0 \} \subseteq A$ or $\{x, x_0 \} \subseteq B$. Since $x_0 \notin B$, $\{x, x_0 \} \nsubseteq B$. So $\{x, x_0 \} \subseteq A$, which means $x \in A$. Since x is arbitrary, $B \subseteq A$. Thus, either $A \subseteq B$ or $B \subseteq A$.

Is this attempt correct? Also, is this considered a constructive proof?

Best Answer

Your proof is good. When you need to conclude that one of two things must be true, your strategy of assuming the first is false and then concluding that the second must be true is a strong one. As the comments suggest, there are more elegant proofs, but that doesn't detract from the validity of yours. So, from here, I'll quibble a little just to critique a few things that would have made the proof easier to read.

Even though this is a short proof, it may have flowed a little better if you had described the overall strategy. The distracted reader may reach the final sentence of your proof and think "Wait, I thought we were supposing $A\not\subseteq B$, what just happened?" Let me break your proof into an introductory paragraph, a "body paragraph" that contains $x$ from start to finish, and a concluding paragraph that repeats how the body paragraph solved the problem.

Suppose $\mathcal{P} (A) \cup \mathcal{P} (B) = \mathcal{P} (A \cup B) $. Either $A \subseteq B$ or $A \nsubseteq B$. If $A\subseteq B$, then we are done. Suppose then that $A \nsubseteq B$. Then there is an element $x_0 \in A$ such that $x_0 \notin B$.

Suppose $x \in B$. Clearly $\{x, x_0 \} \in \mathcal{P}(A \cup B)$ so $\{x, x_0 \} \in \mathcal{P} (A) \cup \mathcal{P} (B)$. This means $\{x, x_0 \} \subseteq A$ or $\{x, x_0 \} \subseteq B$. Since $x_0 \notin B$, $\{x, x_0 \} \nsubseteq B$. So $\{x, x_0 \} \subseteq A$, which means $x \in A$. Since $x$ is arbitrary, $B \subseteq A$.

We have shown that $B\subseteq A$ under the assumption that $A\not\subseteq B$. Thus, either $A \subseteq B$ or $B \subseteq A$.

Also, your choice of variables was curious. You're free to use any variable names you wish, of course, but $a\in A$ and $b\in B$ would have helped the reader much more than $x_0\in A$ and $x\in B$.

To answer your final question: a constructive proof is a proof where you show that something exists by actually demonstrating that a specific object satisfies the conditions. By contrast, a non-constructive proof proves that a set is non-empty without conclusively describing what the set contains. Since this is not an existence proof, neither of those words would accurately describe your proof.

Related Question