# Show $\lvert \mathcal{P}(A \cup B) \rvert = \lvert \mathcal{P(A)} \times \mathcal{P(B)} \rvert$

Let $A \cap B = \emptyset$. We want to show $$\lvert \mathcal{P}(A \cup B) \rvert = \lvert \mathcal{P(A)} \times \mathcal{P(B)} \rvert$$ My attempt is to use the equivalences: $$(1) \ \lvert A \rvert \leq \lvert B \rvert \iff \exists f: A \to B$$ where $f$ is injective.

$$(2) \ \lvert A \rvert \leq \lvert B \rvert \iff \exists f: B \to A$$ where $f$ is surjective.

The idea I have right now is to show two incjective functions $f: \mathcal{P}(A \cup B) \to \mathcal{P(A)} \times \mathcal{P(B)}$ and $g: \mathcal{P(A)} \times \mathcal{P(B)} \to \mathcal{P}(A \cup B)$. So far, I haven't figured out what these should look like.

• Do you know Schroder Bernstein theorem? – Enigma Dec 7 '16 at 19:55
• Isn't $\mathcal(A)$ supposed to be the power set of $A$? It consists of every subsets of $A$. There many errors in your argument. Hint: Think $A$ as a subset of the $x$-axis and $B$ a subset of the $y$-axis. It might help to get the right image. – user251257 Dec 7 '16 at 19:55
• @Enigma yes, but I only know it in the form which states $$\lvert A \rvert \leq \lvert B \rvert \land \lvert B \rvert \leq \lvert A \rvert \implies A \sim B$$. – Zelazny Dec 7 '16 at 20:01
• "It's relatively easy to see that $A\cap B=\emptyset\implies \mathcal{P}(A\cup B)=\mathcal{P}(A)\cup\mathcal{P}(B)$" false. Take $A=\{1\}$ and $B=\{2\}$ for a counterexample. On the left side you will have the element $\{1,2\}$ however this will not be an element of the right side. – JMoravitz Dec 7 '16 at 20:02
• @JMoravitz you're right, edited. – Zelazny Dec 7 '16 at 20:03

## 1 Answer

Hint:

Any element in $\mathcal{P}(A\cup B)$ can be written uniquely as the disjoint union $E\cup F$ where $E\subseteq A$ and $F\subseteq B$

Further, any element in $\mathcal{P}(A)\times \mathcal{P}(B)$ can be written uniquely as the ordered pair $(E,F)$ with $E\subseteq A$ and $F\subseteq B$

Prove that each of these observations are correct and attempt to define a bijection between $\mathcal{P}(A\cup B)$ and $\mathcal{P}(A)\times \mathcal{P}(B)$ which takes advantage of these observations and prove that it is indeed a bijection.

• Is it as simple as sending $E \sqcup F$ to $\langle E, F \rangle$? This is injective since we can only get $\langle E, F \rangle$ for $E$ and $F$. It is surjective since all the ordered pairs are the values of such a function. So this function would be bijective. – Zelazny Dec 7 '16 at 20:59
• @Zelazny yes. Letting $\varphi$ be the bijection from $\mathcal{P}(A\cup B)$ to $\mathcal{P}(A)\times \mathcal{P}(B)$ we have $\varphi(X)=(E,F)$ where $E\cup F$ is the unique representation of $X$ as a union of sets with $E\subseteq A$ and $F\subseteq B$. It is still worth taking a few moments to prove that the representation is unique. – JMoravitz Dec 7 '16 at 21:25