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?


2 Answers 2


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$
    – Saturn
    Sep 28, 2013 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$ Sep 28, 2013 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$
    – Saturn
    Sep 28, 2013 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$ Sep 28, 2013 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 $


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .