3
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ You found a counterexample, so the claim is false. $\endgroup$ – Salech Rubenstein Jan 4 '14 at 7:19
  • $\begingroup$ 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. $\endgroup$ – Henry Swanson Jan 4 '14 at 7:21
4
$\begingroup$

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$

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

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

$\endgroup$
1
$\begingroup$

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.

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