# Disproving $A \subset B \wedge B \cap C \neq \varnothing \Rightarrow A \cap C \neq \varnothing$

Let $A,B,C$ be any sets. Tell if $A \subset B \wedge B \cap C \neq \varnothing \Rightarrow A \cap C \neq \varnothing$ is true or false.

I tried to prove by absurd. Suppose $A \subset B \wedge B \cap C \neq \varnothing$ and $A \cap C = \varnothing$ (absurd).

Let $x \in A$, so by the hypothesis $x \notin C$.

By the hypothesis one have $A \subset B$, so $x \in B$. Because $x \notin C$, one have $x \notin B \cap C$. But by hypothesis one have, $B \cap C \neq \varnothing$. So there exist a $p$ such that $p \in B \cap C$ and $p \notin A$.

I know that this thought doesn't prove/disprove the statement. But can it help to show a counterexample?

Let $A=\{1,2,3\}$, $B= \{1,2,3,4 \}$ and $C=\{4\}$. By this counterexample one can say that the statement is false.

Can someone give me a hint on how to complete the proof whithout the counterexample? Thanks.

• You found a counterexample, so the claim is false. – Salech Rubenstein Jan 4 '14 at 7:19
• To disprove $P$, prove $\lnot P$. The negation of $\forall A,B,C \ P(A,B,C)$ is $\exists A,B,C \ \lnot P(A,B,C)$. To prove a "there exists" statement, it is sufficient to show a single example. – Henry Swanson Jan 4 '14 at 7:21

You actually need as little as one counterexample,to disprove a statement. Disproving a proposition $P$ is equivalent to proving $\,\lnot P\;$, and as we'll see, in this case, that means showing the existence of sets (a counterexample) such that it is not the case that $P$.

Your proposition $P$ is in effect:

$$\forall A, \forall B, \forall C\,\Big((A\subset B \land B\cap C\neq \varnothing) \rightarrow A\cap C \neq \varnothing\Big)\tag{P}$$

It's negation, then, is $$\exists A, \exists B, \exists C\,\Big(A\subset B \land B\cap C \neq \varnothing \land A\cap C = \varnothing\Big)\tag{\lnot P}$$

So proving $\lnot P$ (to disprove $P$) is proving that there exists some such sets $A, B, C$ such that $$A\subset B \land B\cap C \neq \varnothing \land A\cap C = \varnothing$$ and to do this, it suffices to do exactly what you ended with: provide an (counter-)example which validates $\lnot P$:

As you found:

Let $A=\{1,2,3\}$, $B= \{1,2,3,4 \}$ and $C=\{4\}$. By this counterexample one can say that the posted statement is false. $\square$

• @amWhy: Needs another Tu! +1 – Amzoti Jan 5 '14 at 14:34

Take $A:=B-C$, the set of elements in $B$ which are not elements of $C$. This is a proper subset of $B$ (since $B\cap C\neq\varnothing$) and is clearly disjoint to $C$.

Assume there is an $x$ such that $x\in A\cap C$, so $x\in A$ and $x\in C$. But $A\subset B$ so $x\in B$. $x\in C$ and $x\in B$ so $x\in B\cap C$. This means that the statement $$A \subset B \wedge B \cap C \neq \varnothing$$ is false.