1
$\begingroup$

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?

$\endgroup$
  • 3
    $\begingroup$ You already proved it: the claim is false, and it is enough to give one single counter example...and you did it. $\endgroup$ – Timbuc Nov 19 '14 at 4:42
  • $\begingroup$ I know that I already proved it. I just want to do try doing it without the counterexample. $\endgroup$ – St Vincent Nov 19 '14 at 4:44
  • $\begingroup$ To disprove something it suffices to find a counterexample. $\endgroup$ – Empiricist Nov 19 '14 at 4:46
  • $\begingroup$ @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. $\endgroup$ – Timbuc Nov 19 '14 at 4:47
  • $\begingroup$ I know that the counterexample is sufficient, but I wanted some more practice. In other words, could it be shown false without the counterexample? $\endgroup$ – St Vincent Nov 19 '14 at 4:48
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.