Proof $(A \times B) \cup (C \times D)$ is subset of $(A \cup C) \times (B \cup D)$ I am trying to figure out how to do this subset proof. I was given a proposition in class, which is true. The proposition is $(\mathrm{A}\times\mathrm{B})\cup(\mathrm{C}\times\mathrm{D}) \subseteq (\mathrm{A}\cup\mathrm{C}) \times (\mathrm{B}\cup\mathrm{D})$ where $\mathrm{A}\times\mathrm{B} = \{(a,b):a\in\mathrm{A}\wedge b\in\mathrm{B}\}$.
The proof we were given was as follows:
$$(a,b)\in(\mathrm{A}\times\mathrm{B})\cup(\mathrm{C}\times\mathrm{D})$$
$$\Rightarrow(a\in\mathrm{A}\wedge b\in\mathrm{B})\vee(a\in\mathrm{C}\wedge b\in\mathrm{D})$$
the transition from the previous step to the next one is where [I thought] the error [was]:
$$\Rightarrow(a\in\mathrm{A}\vee a\in\mathrm{C})\wedge(b\in\mathrm{B}\vee b\in\mathrm{D})$$
$$\Rightarrow (a,b)\in(\mathrm{A}\cup\mathrm{C}) \times (\mathrm{B}\cup\mathrm{D})$$
Unless I am mistaken, if the distribution were correct, this would mean that the two original sets were equivalent and $\Leftrightarrow$ would be used instead of $\Rightarrow$. But that is not true, a counterexample to this would be $a\in\mathrm{A}$ and $b\in\mathrm{D}$ which is an element of $(\mathrm{A}\cup\mathrm{C}) \times (\mathrm{B}\cup\mathrm{D})$ but not an element of $(\mathrm{A}\times\mathrm{B})\cup(\mathrm{C}\times\mathrm{D})$. With that being said, how can this subset proof be done correctly? I asked my teacher about it and she said that she was right, and I didn't want to go further with it because I had to get to my next class and hadn't thought about it since last week. Or am I making a dumb mistake?
Thanks for the help.
 A: Applying the distributive law yields
$$
(a\in\mathrm{A} \lor a\in\mathrm{C})
\land (a\in\mathrm{A} \lor b\in\mathrm{D})
\land (b\in\mathrm{B} \lor a\in\mathrm{C})
\land (b\in\mathrm{B} \lor b\in\mathrm{D}),
$$
which implies the weaker proposition
$$
(a\in\mathrm{A} \lor a\in\mathrm{C})
\land (b\in\mathrm{B} \lor b\in\mathrm{D}).
$$
A: This is a long comment that's meant to add to the accepted answer.
In logic there's a valid rule of inference called conjunction elimination that states if $\phi\land\psi$ is true then we may derive $\phi$ or we may derive $\psi$ — i.e., $\dfrac{\phi\land\psi}{\phi}$ or $\dfrac{\phi\land\psi}{\psi}$. Intuitively, if a conjunction is true, it must be the case that both conjuncts are true, thus, each conjunct is true individually.
This allows us to chop up formulas and put them together in useful ways. In this particular case, it allows us to remove the conjuncts that don't meet the intersection definition.
Another thing to note is that mathematicians have a tendency to drop a lot of the logic they view as "obvious" to their audience. As well as dropping the conjunction elimination step, they also dropped the substitution from definition steps, the universal elimination step, the universal introduction step, and the sequent or theorem introduction step (required to use the distribution law). This is done to avoid obfuscating the main point of the proof, but it can be very confusing sometimes.
The best piece of advice I received is to always interrogate proofs. Ask why each line is there, and how we move from one line to the next. It may be the case that logic has been dropped, if that's the case, ask what steps are required to fill the gaps. If it still doesn't make sense, then have a go at proving the statement yourself — work out what's required.
