If $X \subseteq A \cup B$, then $X \subseteq A$ or $X \subseteq B$.

If $X \subseteq A \cup B$, then $X \subseteq A$ or $X \subseteq B$.

My counterexample: Let $A = \{1\}$ and $B = \{2\}$. Then $\{1, 2\} \subseteq A\cup B$, but $\{1,2\} \not\subseteq A$ and $\{1,2\} \not\subseteq B$. How would I prove this generally? I've tried starting with the fact that if $X \subseteq A \cup B$ then $x \in X$ implies $x \in A \cup B$ and further $x \in A$ or $x \in B$, but I'm not making any decent progress after that.

How would you prove this without a counterexample?

• You already proved it: the claim is false, and it is enough to give one single counter example...and you did it. – Timbuc Nov 19 '14 at 4:42
• I know that I already proved it. I just want to do try doing it without the counterexample. – St Vincent Nov 19 '14 at 4:44
• To disprove something it suffices to find a counterexample. – Empiricist Nov 19 '14 at 4:46
• @StVincent, you can't. First, because sometimes it is true that $\;X\subset A\;\;or\;\; X\subset B\;$, and second because you must give a counter example to refute a mathematical claim. – Timbuc Nov 19 '14 at 4:47
• I know that the counterexample is sufficient, but I wanted some more practice. In other words, could it be shown false without the counterexample? – St Vincent Nov 19 '14 at 4:48

As my comment has already mentioned, counterexamples are enough to disprove a statement. If you want to characterize when the statement is wrong, an answer goes as follows:

The statement is in general wrong, given that $B \setminus A$ and $A \setminus B$ are non-empty.

Take $X = A \cup B$. Then $X \subseteq A \cup B$ trivially.

Since $B \setminus A$ is non-empty, pick $b \in B \setminus A$. Then $b \in X \setminus A$ and therefore it is false to say $X \subseteq A$.

It is symmetric to show that it is false to say $X \subseteq B$ either. This completes the proof of the statement "Given $B \setminus A$ and $A \setminus B$ are non-empty, $X \subseteq A \cup B$ does NOT imply $X \subseteq A$ or $X \subseteq B$". But please note that we also suggest a counterexample here.

Moreover, this is the largest generality you can get, i.e., the conditions "$B \setminus A$ and $A \setminus B$ are non-empty" cannot be dropped. If, say, $B \setminus A$ is empty, then $B \subseteq A$ and $A \cup B = A$. Then certainly $X \subseteq A \cup B$ implies $X \subseteq A$.

Your counterexample proves that the statement is false.

Counterexamples are perfectly valid counterproofs.

There is nothing else required--you have shown that it is not the case that the claim is true in all cases.