# How to prove that the sets $B$ and $C$ are equal, given the following facts?

I'm self studying Ethan Bloch's book Proofs and Fundamentals and I'd like to know how to prove this (this is the book's Exercise 3.3.11).

Let $X$ be a set, and let $A, B, C \subseteq X$ be subsets. Suppose that $A \cap B = A \cap C$, and that $(X-A) \cap B = (X-A) \cap C$. Prove that $B = C$.

To prove that $B = C$ we need to show that $B \subseteq C$ and $C \subseteq B$, but I don't know how to actually begin proving it. I think that this is the first time I'm trying to prove something set theoretic with the aid of given statements, I've only done more "direct" proofs before.

I've managed to gather from $A \cap B = A \cap C$ that the sets $B$ and $C$ are not disjoint (unless one or both of them is the empty set), but that's the farthest I've gotten. Any kind help is appreciated.

• You can take $b\in B$, and study the two cases $b\in A$ and $b\in X-A$. – Kevin Quirin Apr 6 '16 at 13:41
• To prove $B \subseteq C$ you can do a proof by contradiction, that is, let $x \in B$ and assume $x \notin C$. Using the fact that either $x \in A$ or $x \in X-A$, this leads to a contradiction. The reverse implication $C \subseteq B$ is similar. – Cedric Cavents Apr 6 '16 at 13:46

If $b \in B$, then either $b \in A$ or $b \in X\setminus A$. If $b \in A$, then $b \in A\cap B = A\cap C\subset C$. If $b \in X\setminus A$, then $b \in B\cap X\setminus A = C \cap X\setminus A\subset C$, hence $B \subset C$. In a similar fashion one can show that $C\subset B$.

Note: I write $A\subset B$ to mean $A$ is a subset of $B$, not necessarily proper, in other words $A\subset A$

$B = (B\setminus A) \cup (A \cap B)$$=(B\cap A^c) \cup (A \cap B)=(C\cap A^c) \cup (A \cap C)=(C\setminus A) \cup (A \cap C)=C$

Let $x \notin C$. We will show $x\notin B$, which means $C^c \subseteq B^c$, where I use ${}^c$ to denote set complements (which can also be denoted $X-C$ and $X-B$). It immediately follows from $C^c \subseteq B^c$ that $B \subseteq C$. Note that proving that is itself a quick and simple exercise.

Anyway, let $x \notin C$. Then $x \notin A \cap C$, which means $x \notin A \cap B$ because $A \cap B = A \cap C$. Now, we have two possibilities. Either $x \in A$ or $x \notin A$. We'll show that both possibilities require that $x \notin B$.

Suppose $x\in A$. Recall that $x\notin C$. Therefore $x \notin A \cap C$. Since $A \cap C = A \cap B$, then $x \notin A \cap B$. And since we have $x\in A$, then we must have $x \notin B$ since otherwise $x \in A \cap B$, which is a contradiction.

Now suppose $x \notin A$. Then $x \in X-A$. Since $x \notin C$, then $x \notin (X-A) \cap C$. Since $(X-A)\cap C = (X-A) \cap B$, then $x \notin (X-A) \cap B$. This means that we must have $x \notin B$, since otherwise $x \in (X-A) \cap B$, which is a contradiction.

Therefore, if $x \notin C$ then we must have $x\notin B$. This implies $(X-C) \subseteq (X-B)$, which means $B \subseteq C$.

I'll leave the other direction to you, but it's basically identical except for swapping all the $B$s and $C$s.