I had to prove that: For all sets A and B, $A^c \cup (A \setminus B) = (A \cap B)^c$.

Below is what I did, but I'm kind of stuck at the time.

So I begin with proving $A^c \cup (A \setminus B) \subseteq (A \cap B)^c$.
Let $x \in A^c \cup (A \setminus B)$.
Note, by DeMorgan's law, $(A \cap B)^c$ = $A^c \cup B^c$.
Then, $x \in A^c$ or $x \in A$ and $x \notin B$.
If $x \in A^c$, then $x \in A^c \cup B^c$.
If $x \in (A \setminus B)$, then $x \in A$ and $x \in B^c$, thus $x \in A^c \cup B^c$.

Left is to prove $(A \cap B)^c \subseteq A^c \cup (A \setminus B)$.
Let $x \in A^c \cup B^c$.
Then, $x \in A^c$ or $x \in B^c$.
If $x \in A^c$ then $x \in A^c \cup (A \setminus B)$.
If $x \in B^c$ then ..?

I don't think you can now say that $x \in A \setminus B$, can you? I considered coming up with a counterexample as I couldn't figure out what I'm missing, but I can't seem to find one.

Any help is appreciated! Thank you.


HINT: Now consider the two cases, either $x\in A$ or it isn't. One of them you dealt with. What does the other give you?

Full answer: (After indication from the comments that the hint was understood) if $x\in B^c$ then either $x\in B^c$ and $x\in A^c$, in which case we already know that $x\in A^c\cup(A\setminus B)$, or $x\in B^c$ and $x\in A$, in which case $x\in A\setminus B$ and the proof is completed.

  • $\begingroup$ If $x \in A$, obviously $x \in A \setminus B$. $\endgroup$ – Alexei Oct 21 '14 at 22:54
  • $\begingroup$ Yes. And if it is not? $\endgroup$ – Asaf Karagila Oct 21 '14 at 22:54
  • $\begingroup$ If $x \notin A$, then $x \notin A \setminus B$. How do I get to this from $x \in B^c$? I believe I have to show that $x \notin A$ and $x \notin B$, but I can only show the latter. $\endgroup$ – Alexei Oct 21 '14 at 22:58
  • $\begingroup$ First of all, $x\notin A$ can also be written as? Secondly, you have that $x\in A$ or $x\notin A$. Regardless to $x\in B^c$, you just do a case by case analysis. $\endgroup$ – Asaf Karagila Oct 21 '14 at 23:00
  • $\begingroup$ $x \notin A$ can be written as $x \in A^c$. Sorry if my questions are trivial, but I don't see why we have to consider them separately (because of the brackets). I thought we have to consider two cases: (1): $x \in A^c$ and (2): $x \in A$ and $x \notin B$. $\endgroup$ – Alexei Oct 21 '14 at 23:04

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.