Intersection and complement proof I'm trying to prove that if $A \cap B = A \cap C$ then $A \cap \overline{B} = A \cap \overline{C}$.
I've tried several manipulations, but I can't get to it. 
 A: Hint: the first equality is equivalent to the statement "for every $x \in A$ we have $x \in B \iff x \in C$" and the second equality is equivalent to an analogous statement.
More explanation: Let's assume that $A \cap B = A \cap C$.  This means that for all $x$, the equivalence $x \in A \cap B \iff x \in A \cap C$ holds. In particular, this equivalence holds for all $x \in A$.  If we assume that $x$ is in $A$, then the intersections with $A$ do not do anything and we have the equivalence $x \in B \iff x \in C$.  This means that the equivalence $x \notin B \iff x \notin C$ also holds for all $x \in A$, and it's starting to resemble the second equality now...
A: Another interpretation:
\begin{align}
A \cap B &= A \cap C  & \text{apply complement}\\
\overline{A \cap B} &= \overline{A \cap C} & \text{De Morgan's law} \\
\overline{A} \cup \overline{B} &= \overline{A} \cup \overline{C} & \text{apply } A\cap\bullet\\
A\cap \left(\overline{A} \cup \overline{B}\right) &= A \cap \left(\overline{A} \cup \overline{C}\right) & \text{expand}\\
A \cap \overline{B} &= A \cap \overline{C}
\end{align}
Hope it helps ;-)
