Proof Strategy, Power sets, and Injections Let $S$ and $T$ be sets and define the function
$$f:\mathcal P(S) \times \mathcal P (T)\to \mathcal P(S \cup T)$$
by $f(A,B) = A \cup B$ for all $A \subseteq S$ and all $B \subseteq T$. Prove that $f$ is an injection iff $S$ and $T$ are disjoint.
The only thing I can think to do is start with the typical way of proving a biconditional.  The statement makes complete sense because if the sets overlap, then you could take away the overlap and get the same output, however I have no idea how to prove this.  Where should I start?
 A: $\implies:$ If $S$ and $T$ are not disjoint, there is at least one element in both, say, $x$. Then $\{x\} \subset S \cap T$.
Spoiler:

 So $f(\{x\}, \emptyset) = f(\emptyset, \{x\}) = \{x\}$, but $(\{x\}, \emptyset) \neq (\emptyset, \{x\})$. This way: $$\left(S \cap T \neq \emptyset \implies f \text{ not injective}\right) \implies \left(f \text{ injective} \implies S \cap T = \emptyset\right).$$

$\impliedby:$ Suppose that $S$ and $T$ are disjoint. Take $A,A' \subset S$, and $B,B' \subset T$ such that $f(A,B) = f(A',B')$. That is, $A \cup B = A' \cup B'$. Then we must have $A = A'$ and $B = B'$, and you can convince yourself of this using a Venn diagram. We're using heavily the hypothesis that $S \cap T  = \emptyset$ here.
Spoiler:

I'll prove that $A = A'$ and leave the other one for you. Take $x \in A \subset S$. Then $x \in A \cup B = A' \cup B'$, which means that $x \in A'$ or $x \in B'$. But $x \in S$ and $S \cap T = \emptyset$ gives us $x \not\in B'$, so we must have $x \in A'$, and $A \subset A'$. The other inclusion is analogous. Repeat the argument for $B$ and $B'$. 

So we conclude that $(A,B)=(A',B')$ and $f$ is injective.
Nice exercise.
