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$.

  • $\begingroup$ I formated the title using Latex. You would greatly increase your readability by adding more space. $\endgroup$ – Taladris Sep 18 '15 at 2:18
  • 1
    $\begingroup$ 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.$ $\endgroup$ – Cameron Buie Sep 18 '15 at 2:19
  • 1
    $\begingroup$ Also, I think you mean for $f(X)$ to yield an ordered pair, rather than a Cartesian product. That eliminates the previously-mentioned flaw. $\endgroup$ – Cameron Buie Sep 18 '15 at 2:21
  • $\begingroup$ Your $f$, after Cameron Buie's suggested modification, is the natural bijection. You may have a shorter proof by expliciting its inverse. $\endgroup$ – Taladris Sep 18 '15 at 2:23
  • 3
    $\begingroup$ 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...." $\endgroup$ – Cameron Buie Sep 18 '15 at 2:33

Your Answer

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

Browse other questions tagged or ask your own question.