If $A \subseteq C$ and $B \subseteq C$, then $A \cup B \subseteq C$: Review of Two Proof Attempts

elementary-set-theoryproof-verification

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.

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

  1. 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. :-)

Related Question