Need help proving A $\subseteq$ B or B $\subseteq$ A.

32 Views Asked by At

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

Scratch work: If $\mathcal{P}$(A) $\cup$ $\mathcal{P}$(B) = $\mathcal{P}$(A $\cup$ B) then $$\tag1 \forall x (x \in (\mathcal{P}(A) \cup \mathcal{P}(B)) \iff x \in \mathcal{P}(A\cup B)). $$ If A $\subseteq$ B then we are done. If A $\nsubseteq$ B then we must show B $\subseteq$ A. We can first assume y $\in$ B. Then there exists a set Z such that Z $\subseteq$ B and y $\in$ Z. Since Z $\subseteq$ B, Z $\in$ $\mathcal{P}$(B) and obviously Z $\in$ $\mathcal{P}$(A) $\cup$ $\mathcal{P}$(B). By (1), Z $\in$ $\mathcal{P}$(A $\cup$ B). Thus Z $\subseteq$ A $\cup$ B. Since y $\in$ Z, y $\in$ A $\cup$ B. Since y was an arbitrary element of B, B $\subseteq$ B or B $\subseteq$ A.

It doesn't seem then that B is necessarily a subset A.

1

There are 1 best solutions below

4
On

You're taking it from the wrong side. In $\mathcal{P}(A\cup B)$ there is $A\cup B$, which should be a member of $\mathcal{P}(A)\cup\mathcal{P}(B)$, so it is in one of the two sets.

What does it mean that $A\cup B\in\mathcal{P}(A)$?


Further note: the inclusion $\mathcal{P}(A)\cup\mathcal{P}(B)\subseteq\mathcal{P}(A\cup B)$ is true for any sets $A$ and $B$, so what you have to use is the converse inclusion, as I suggested above.


Let's look at your attempt. It's correct to examine the case when $A\not\subseteq B$. Now you're not even trying to use this assumption. Take $x\in A$, $x\notin B$. If $z\in B$, then you can consider $\{x,z\}$, which is a subset of $A\cup B$, so it must belong to $\mathcal{P}(A)\cup\mathcal{P}(B)$, hence it is either a subset of $A$ or of $B$. Since $x\notin B$, we must have $\{x,z\}\subseteq A$, so $z\in A$.

However, it's simpler to just consider $B$ and $\{x\}\cup B$, which, with the same argument as before, has to be a subset of $A$, because it is not a subset of $B$.