How to write a proof in Set Theory?

I am relatively new to Set Theory.

I am trying to write a proof showing that

$(A-B)^\complement = A^\complement \cup B$

But I don't even know where to start.

If someone wouldn't mind explaining how you go about proving something like this, I would be very grateful.

Thanks

Corey

• A general tip for approaching these problems: What's the definition of complement? Of set difference? Write out the definitions of the sets being examined and see if a proof becomes apparent. May 5 '15 at 1:37

This is just an application of DeMorgan's law: $(A\cap B)^c=A^c\cup B^c$ (proof here).

$(A-B)^c=(A\cap B^c)^c=A^c\cup B$, since $(B^c)^c=B$.

Or $((A-B)^c\subseteq A^c\cup B$ and $A^c\cup B\subseteq (A-B)^c)$, which can be done by proving $$x\in(A-B)^c\iff x\in A^c\cup B,$$

since have $(A\subseteq B)\iff (x\in A\,\Rightarrow\, x\in B)$ by definition of a subset.

$x\in A^c\cup B\iff ((x\in A^c)\lor (x\in B))\iff ((x\not\in A)\lor (x\in B))$

$\iff ((x\not\in A)\lor (x\not\in B^c))\stackrel{\text{DM}}\iff x\not\in A\cap B^c$

$\iff x\not\in A-B\iff x\in(A-B)^c$.

This still used DeMorgan's law, but in the logic form

$((x\not\in A)\lor(x\not\in B^c))\iff \lnot ((x\in A)\wedge(x\in B^c))$

(and so $\iff \lnot(x\in A\cap B^c)\iff x\not\in A\cap B^c$).

You can still prove it just by checking all possible cases, e.g. in this case you just check what happens when $(x\in A$ and $x\not\in B)$ or $(x\in A$ and $x\in B)$ or $(x\not\in A$ and $x\not\in B)$ or $(x\not\in A$ and $x\in B)$. Try understanding the proof given in the Wikipedia link.

Note that $A-B=A \cap B^c$ and $(A \cap B^c)^c=A^c\cup B$.