# Simplification of set formulas: $[ (A - B)^c - (B - A)^c ]\cap A = \varnothing$

Using the set properties, I have to demonstrate that

$[ (A - B)^\mathsf{c} - (B - A)^\mathsf{c}] \cap A = \emptyset.$

So far I've seen some logic properties, but never applied to sets. Could you guys help me?

-
What means $\neg A$? Does this means $\{ x : x \notin A \}?$ – user29999 Dec 6 '12 at 21:22
Complement of a set, like in here: basic-mathematics.com/complement-of-a-set.html I don't know how to put that with LaTeX. – Axel Prieto Dec 6 '12 at 21:23
I don;t know this symbol ¬ for sets. I think it is used in logic statements. – Babak S. Dec 6 '12 at 21:24
I've just edited. Is it clearer now? – Axel Prieto Dec 6 '12 at 21:28

The definition of $A - B$ is $\{x \mid x \in A \text{ and } x \notin B\}$, which can be rewritten as $A \cap B^c$. This fact allows us to write \begin{align*} [(A - B)^\mathsf{c} - (B - A)^\mathsf{c}] \cap A &= [(A \cap B^\mathsf{c})^\mathsf{c} - (B \cap A^\mathsf{c})^\mathsf{c}] \cap A\\ &= [(A \cap B^\mathsf{c})^\mathsf{c} \cap (B \cap A^\mathsf{c})] \cap A\\ &\subseteq A^\mathsf{c} \cap A\\ &= \emptyset. \end{align*}

-
Thank you very much. – Axel Prieto Dec 6 '12 at 21:57

\begin{align}&x\in((A\setminus B)^{\mathsf c}\,\setminus\, (B\setminus A)^{\mathsf c})\cap A\\\implies&x\in(A\setminus B)^{\mathsf c}\land x\notin(B\setminus A)^{\mathsf c}\land x\in A\\ \implies&x\notin(A\setminus B)\land x\in (B\setminus A)\land x\in A\\ \implies&x\in (B\setminus A)\land x\in A\\ \implies&x\in B\land x\notin A\land x\in A\\ \implies& x\notin A\land x\in A\\ \implies &\perp \end{align}

-
Thank you very much. – Axel Prieto Dec 6 '12 at 22:00
+1 This is also (almost) the way I would do it: just expand the definitions to go from sets to the logic level, and use the rules of logic to simplify. Four things I would do differently: I would split up the third step; I would use $\;\iff\;$ instead of $\;\implies\;$ throughout; I would add comments explaining each step, as in the Dijkstra-Feijen proof format; and I would write $\;\text{false}\;$ instead of $\;\perp\;$. – Marnix Klooster Aug 4 '14 at 11:54

The key fact with such set equations is that they can usually be translated into corresponding logical formulae.

For example:

• $x \in A \cap B$ if and only if $x \in A \wedge x \in B$.
• $x \in A^\mathsf{c}$ if and only if $\neg (x \in A)$
• $x \in A - B$ if and only if $x\in A \wedge x \not\in B$.

Applying these rules repeatedly ought to transform your statement about sets into a logical statement. Membership of the left hand side corresponds to a statement which can't possibly be true, so the set has no members. Two sets are equal exactly when they have the same members, so that means it is the empty set.

-
Thank you very much. – Axel Prieto Dec 6 '12 at 22:03

In my notation $A^c = \{ x : x \notin A\}$. Then we must prove that

$$[ (A \cap B^c )^c \cap (B \cap A^c)^c ] \cap A = \emptyset.$$ Notice that $$(A \cap B^c)^c = (A^c \cup B)$$ Then \begin{eqnarray} [(A^c \cup B) \cap (B^c \cup A)] \cap A & =&\left \{ [(A^c \cup B) \cap B^c] \cup [(A^c \cup B) \cap A]\right \} \cap A \\ &=& \left \{ [A^c \cap B^c] \cup [(A^c \cup B)] \right \} \cap A\\ &=& \left \{ [A^c \cap B^c] \cap A \right \} \cup \left \{ [(A^c \cup B)] \cap A \right \}\\ &=& \emptyset \cup \emptyset \\ &=& \emptyset. \end{eqnarray}

-
Thank you very much. – Axel Prieto Dec 6 '12 at 22:01
You're welcome. – user29999 Dec 6 '12 at 22:04