0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Do you know Schroder Bernstein theorem? $\endgroup$ – Enigma Dec 7 '16 at 19:55
  • 2
    $\begingroup$ 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. $\endgroup$ – user251257 Dec 7 '16 at 19:55
  • $\begingroup$ @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$$. $\endgroup$ – Zelazny Dec 7 '16 at 20:01
  • 1
    $\begingroup$ "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. $\endgroup$ – JMoravitz Dec 7 '16 at 20:02
  • $\begingroup$ @JMoravitz you're right, edited. $\endgroup$ – Zelazny Dec 7 '16 at 20:03
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Zelazny Dec 7 '16 at 20:59
  • 1
    $\begingroup$ @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. $\endgroup$ – JMoravitz Dec 7 '16 at 21:25

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.