I'm trying to determine the truth value of

$(X \cap Y \subseteq \overline{A} \land Y \subseteq B) \implies Y \subseteq B - A$

We got two premises:

  • $X \cap Y \subseteq \overline{A}$
  • $Y \subseteq B$

Have some element $m \in Y$. If I prove that it is in $B - A$ then it's over.

The only inference with the premises I can think of is that since $m \in Y$, it must be in $B$, so we got $m \in B$. Now I need to prove that $m \notin A$.

Now I know that I should be working with the first premise. However, I'm not sure what can I infer from it. I know that $m\in Y$, but that doesn't necessarily mean $m \in \overline{A}$, since it may or not be in this intersection.

How can I proceed then?


We show that the implication need not hold.

Let $U$ be the universal set, assumed non-empty.

Let $X=\emptyset$ and let $A=B=Y=U$.

Then $X\cap Y=\emptyset$. Thus $X\cap Y\subseteq B$. That makes the antecedent of the implication true.

But $Y\not\subseteq B\setminus A$, since that is empty. So the consequent of the implication is false, making the implication false.

Remark: It is easy to come up with examples where the implication does hold. Most simply, let $Y$ be the empty set, and choose the other sets arbitrarily.

  • $\begingroup$ Interesting.. so basically, whenever I hit what seems to be a dead end, it is very likely that what I'm trying to prove is actually false :[ $\endgroup$ – Zol Tun Kul Sep 28 '13 at 3:49
  • 1
    $\begingroup$ It can be a good indication. Analysis of the "dead end" can lead us to the construction of a counterexample. $\endgroup$ – André Nicolas Sep 28 '13 at 3:52
  • $\begingroup$ By the way, if as a minor detail I was told that $A,B,X,Y$ were all subsets of an arbitrary $E$, this would still work, because $E$ is basically the universe of discourse here, right? $\endgroup$ – Zol Tun Kul Sep 28 '13 at 3:54
  • $\begingroup$ I called it $U$. If $U=\emptyset$ we could not build a counterexample! But in all other cases we can. $\endgroup$ – André Nicolas Sep 28 '13 at 4:15

Consider A = {1}, B = {1, 2, 3, 9}, X = {3, 4, 5}, Y = {1, 2, 3}.

$(X \cap Y \subseteq \overline{A} \land Y \subseteq B) \implies Y \subseteq B - A$

$\{3\} \subseteq \overline {\{1\}} \land \{1, 2, 3\} \subseteq \{1, 2, 3, 9\} \implies \{1, 2, 3\} \subseteq \{2, 3, 9\}$

$true \land true \implies false $


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.