# Sets Problem with Discrete Mathematics

I've been having trouble solving this problem and I have no clue where to go at this point. If anyone could help me out and explain along the way I'd appreciate it greatly.

Let $A,B,C$ be a sets. Supppose that $A\setminus B = A\setminus C$, then $A \cap B = A \cap C$. Prove or disprove with a counterexample.

-
Have you tried drawing a picture? –  Karolis Juodelė Sep 20 '12 at 15:29
I know that it takes into consideration everything that's in A but not in B and everything that's in A but not in C. With this taken into consideration, B and C definitely don't have to be the same set and A\B can still be equal to A\C. Therefore, if A\B=A\C, then A∩B=A∩C. I'm pretty sure that this is right but I'm not sure how to actually make a proof out of it. –  Requiem Sep 20 '12 at 15:49
Keep in mind that I just started writing proofs a week ago. –  Requiem Sep 20 '12 at 15:50
Although an "if ... then ..." proof might be okay, I suggest you evaluate $A \setminus (A \setminus B)$. I assume you know how to write difference as intersection and a complement of intersection as union. –  Karolis Juodelė Sep 20 '12 at 16:06
So I should start the proof off by restating the problem and then also saying "This means that the is an element x \in A that is not in B and an element x \in A that is also not in C. Suppose x \in B and x \in C." and then continue to prove by contradiction? Would this be the best way to go about it? –  Requiem Sep 20 '12 at 16:15

Hint. Note that $(A \setminus B) \cup (A \cap B) = A$. Note, also, that the two sets are disjoint. Try writing things in terms of logic, if you don't see intuitively. $x \in A \setminus B$ means $x \in A \wedge x \notin B$.

-
What does the arrow cone shaped ^ mean? –  Requiem Sep 20 '12 at 15:37
$\wedge$ stands for and. $\vee$ stands for or and $\neg$ stands for not. It is useful to know that set operations correspond to logical ones. $\cup$ is $\vee$, $\cap$ is $\wedge$ and complement is $\neg$. –  Karolis Juodelė Sep 20 '12 at 15:38
I haven't been taught that unfortunately but I have been taught the not symbols. Thank you for the information! –  Requiem Sep 20 '12 at 15:42
@KarolisJuodelė Does A/B another way of saying A-B? –  math101 Sep 20 '12 at 15:54
Yes. A\B is another way to say A-B. –  Requiem Sep 20 '12 at 15:55

Expanding $A \setminus B = A \setminus C$ using the definition $$x \in A \setminus B \;\equiv\; x \in A \land \lnot(x \in B)$$ and then simplifying results in \begin{align} & A \setminus B = A \setminus C \\ \equiv & \;\;\;\;\;\text{"extensionality"} \\ & \langle \forall x :: x \in A \setminus B \equiv x \in A \setminus C \rangle \\ \equiv & \;\;\;\;\;\text{"definition of \setminus, twice"} \\ & \langle \forall x :: x \in A \land \lnot(x \in B) \equiv x \in A \land \lnot(x \in C) \rangle \\ \equiv & \;\;\;\;\;\text{"logic: move common conjunct out of \equiv"} \\ & \langle \forall x :: x \in A \Rightarrow (\lnot(x \in B) \equiv \lnot(x \in C)) \rangle \\ \equiv & \;\;\;\;\;\text{"logic: simplify by negating both sides of \equiv"} \\ & \langle \forall x :: x \in A \Rightarrow (x \in B \equiv x \in C) \rangle \\ \end{align}

Now, in the same way expand $A \cap B = A \cap C$ using the definition $$x \in A \cap B \;\equiv\; x \in A \land x \in B$$ and compare the results.

-