3

I feel that I didn't utilize the fact that A and B are disjoint in the proof below. Can anyone find the flaws in my proof?

Suppose $A$ and $B$ are disjoint sets.

Let $f : \mathcal P(A \cup B) \rightarrow \mathcal P(A) \times \mathcal P(B)$ be defined as $f (X) = (A \cap X) \times (B \cap X)$.

Let $C \subseteq A \cup B$ and $D \subseteq A \cup B$.

Suppose $f (C) = f (D)$.   From the definition of $f$, it follows that $(A \cap C) \times (B \cap C) = (A \cap D) \times (B \cap D)$.   This means $A \cap C = A \cap D$ and $B \cap C = B \cap D$.

Suppose $x \in C \subseteq A \cup B$.   If $x \in A$, then $x \in A \cap C = A \cap D \subseteq D$.   If $x \in B$, then $x \in B \cap C = B \cap D \subseteq D$.   Thus, $x \in D$.

Suppose $x \in D \subseteq A \cup B$. If $x \in A$, $x \in A \cap D = A \cap C \subseteq C$.   If $x \in B$, $x \in B \cap D = B \cap C \subseteq C$.

Therefore, $C = D$, and $f$ is one-to-one.

To prove $f$ is onto, let $D \subseteq A \times B$.   Let $C = \{ x \in A \cup B| \exists (a, b) \in D (x = a \vee x = b) \}$.   Then, $f (C) = D$.

Graham Kemp
  • 129,094
  • I formated the title using Latex. You would greatly increase your readability by adding more space. – Taladris Sep 18 '15 at 02:18
  • 1
    Well, one flaw is this: $U\times V=X\times Y$ need not indicate that $U=X$ and $V=Y.$ Take any two sets $U,Y,$ and let $V=X=\emptyset.$ – Cameron Buie Sep 18 '15 at 02:19
  • 1
    Also, I think you mean for $f(X)$ to yield an ordered pair, rather than a Cartesian product. That eliminates the previously-mentioned flaw. – Cameron Buie Sep 18 '15 at 02:21
  • Your $f$, after Cameron Buie's suggested modification, is the natural bijection. You may have a shorter proof by expliciting its inverse. – Taladris Sep 18 '15 at 02:23
  • 3
    By the way, +1 for showing what you did, and for listening to that little voice that said "Hey! There's a hypothesis you didn't use...." – Cameron Buie Sep 18 '15 at 02:33
  • When showing that $ f(C)=f(D)$ implies$ C=D$, when you reach $A\cap C=A\cap D$ and $ B\cap C=B\cap D$ you can then simply say $ C= (A\cap C)\cup (B\cap C)=(A\cap D)\cup (B\cap D)=D.$ – DanielWainfleet Sep 18 '15 at 06:17
  • @user254665 How can I use the fact that A and B are disjoint in C=(A∩C)∪(B∩C)=(A∩D)∪(B∩D)=D? –  Sep 18 '15 at 13:11
  • I dk what you mean. Since $ C$ and $ D$ are subsets of $A\cup B$, then once you have shown (as you did) that $A\cap C=A\cap D$ and $B\cap C=B\cap D$ (the 5th and 6th lines of your proof) then the next 4 lines can be replaced by the formula in my first comment , simplifying that step. – DanielWainfleet Sep 19 '15 at 01:10
  • Note that the theorem is basically just saying that $2^{A+B} \cong 2^A \times 2^B$. – goblin GONE Oct 05 '15 at 04:49

0 Answers0