I am trying to prove the following:
If $A \subseteq C$ and $B \subseteq C$, then $A \cup B \subseteq C$.
I thought of two ways that this could be attempted, the first of which I think is incorrect.
The first attempt is as follows:
Let $a \in A$ and $b \in B$.
Therefore, $a, b \in A \cup B$.
Therefore, since $A \subseteq C$ and $B \subseteq C$, we have that $a \in C$ and $b \in C$.
$\therefore A \cup B \subseteq C$
I think it's correct to claim that, since $a \in A$ and $b \in B$, then $a, b \in A \cup B$. However, in order to prove that $A \cup B \subseteq C$, we must prove that all of the elements in $A \cup B$ are also in $C$. At the moment, we have only proven that $a, b \in A \cup B$, but we have not proven that $a, b$ are the only elements in $A \cup B$, so we cannot then say that, since $A \subseteq C$ and $B \subseteq C$, then $A \cup B \subseteq C$.
Is my analysis of this proof correct?
The second attempt is as follows:
Let $x \in A \cup B$.
Therefore, $x \in A$ or $x \in B$, or both.
Since we do not know which of these are true, we will proceed with a proof by cases, where we assume that one is true and show that it therefore implies the conclusion, and then we do the same for the other cases, one-by-one.
- Let $x \in A$.
Therefore, $x \in C$ (Since $A \subseteq C$.)
$\therefore A \cup B \subseteq C$ (Since all elements in $A \cup B$, namely $x$, are also in $C$.)
$Q.E.D.$
- Let $x \in B$.
Therefore, $x \in C$ (Since $B \subseteq C$.)
$\therefore A \cup B \subseteq C$ (Since all elements in $A \cup B$, namely $x$, are also in $C$.)
$Q.E.D.$
Is this second attempt correct?
I'd appreciate your reviews of these two attempts.
Best Answer
The first attempt kind of misses the mark. To prove that $A \cup B \subseteq C$, you have to show that for any $x \in A \cup B$ you have that also $x \in C$. If you start by assuming $x \in A$ or $x \in B$, you've already side-stepped one step of the proof.
Your second attempt is correct, except that you shouldn't draw the conclusion in each case you treat. It doesn't follow that $A \cup B \subseteq C$ until you've completed both case analyses, and in particular QED doesn't apply -- because Q you wanted to D hasn't actually been D'd yet. :-)