3
$\begingroup$

Seems obvious but I doubt how to show it step by step... I could prove the reverse statement (if $A\subseteq B$ or $B\subseteq A$ then $\mathcal{P}(A)\cup\mathcal{P}(B)=\mathcal{P}(A\cup B)$), but it doesn't help.
I saw a hint that it's easy to prove by negation, but I cant see how... Thanks for help at advance!

Edit: $\mathcal{P}(X)$ notes the powerset of $X$

$\endgroup$
  • $\begingroup$ Plus, the "reverse" would be a completely different result, maybe you were thinking about the contrapositive. $\endgroup$ – cronos2 Nov 6 '17 at 21:47
  • $\begingroup$ @learning union of two power sets $\endgroup$ – Marina Rappoport Nov 6 '17 at 21:50
  • $\begingroup$ @PeldePinda no, I wrote correct $\endgroup$ – Marina Rappoport Nov 6 '17 at 21:51
  • 1
    $\begingroup$ @cronos2 I don't know what is contrapositive statement... I mean that I could prove statement if change "if" and "then" parts. Reverse is not a negation $\endgroup$ – Marina Rappoport Nov 6 '17 at 21:53
  • 1
    $\begingroup$ math.stackexchange.com/questions/345978/… contains enough, no? $\endgroup$ – Asaf Karagila Nov 7 '17 at 0:04
3
$\begingroup$

Hint:

If $A \not\subset B$ nor $B \not\subset A$ then $\exists a \in A \setminus B, b \in B \setminus A$. Think about some element of $\mathcal{P}(A \cup B)$ that couldn't possibly belong to $\mathcal{P}(A) \cup \mathcal{P}(B)$.

Edit:

thinking about your comment it could actually constitute a proof (just for the finite case)

Clearly $|\mathcal{P}(A)| = 2^{|A|}, |\mathcal{P}(B)| = 2^{|B|}$.

$|\mathcal{P}(A) \cup \mathcal{P}(B)| = 2^{|A|} + 2^{|B|} - |\mathcal{P}(A) \cap \mathcal{P}(B)| = 2^{|A|} + 2^{|B|} - |\mathcal{P}(A \cap B)| = 2^{|A|} + 2^{|B|} - 2^{|A \cap B|}$ $|\mathcal{P}(A \cup B)| = 2^{|A| + |B| - |A \cap B|}$

Now if $A \not\subset B$ and $B \not\subset A$ then $|A \cap B| < \min \{|A|, |B|\}$. This way, $|\mathcal{P}(A) \cup \mathcal{P}(B)| = 2^{|A|} + 2^{|B|} - 2^{|A \cap B|}$ has, at least, three $1$s in its binary representation, while $|\mathcal{P}(A \cup B)| = 2^{|A| + |B| - |A \cap B|}$ has just one.

$\endgroup$
  • $\begingroup$ does it mean that I could prove it using size of P(A∪B) and P(A)∪P(B)? $\endgroup$ – Marina Rappoport Nov 6 '17 at 21:56
  • $\begingroup$ or it's simply means that in ∃{a,b} ∈ P(A∪B) that not belongs to P(A)∪P(B)? could I state it without any additional steps? $\endgroup$ – Marina Rappoport Nov 6 '17 at 22:15
  • $\begingroup$ The second comment is what I meant originally. See my edit for more about the first comment. $\endgroup$ – cronos2 Nov 6 '17 at 22:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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