# DeMorgan's Law and Differences of Sets

I'm currently trying to prove the following identity:

$(A \cup B)\triangle C \equiv (A \triangle C)\triangle(B \setminus A)$

I can easily figure that the left side reduces down to $(x \in A \land x \notin C) \lor (x \in B \land x \notin C) \lor (x \in C \land x \notin A \land x \notin B)$

But when I start working on the right side, I end up with something a bit confusing on my hands:

Let $x \in(A \triangle C)\triangle(B \setminus A) \rightarrow (x \in(A\triangle C)\setminus(B\setminus A)) \lor (x \in (B\setminus A)\setminus(A\triangle C))$

The first of those two possibilities is where it starts to break down for me, particularly when treating the second possibility in $(A \triangle C)$, which is $(C \setminus A)$. In that case, I end up with the following:

$x \in (C \setminus A)\setminus(B\setminus A)$

The logical equivalent of the difference of sets is 'and not,' so it could be rewritten

$(C \land \lnot A)\land \lnot (B \land \lnot A)$

But according to DeMorgan's Law, the negation of an end statement would be an or statement with both elements negated, meaning it becomes

$(C \land \lnot A) \land (\lnot B \lor A)$

If you distribute this, you'd end up with

$(C \land \lnot A \land \lnot B) \lor (C \land \lnot A \land A)$

That first one is fine, but if you let the contradiction cancel out, you're still now left with $x \in C$ in a way that does not exclude elements in A or B, which would mean it doesn't match up to the left side. What am I missing here?

I am not really familiar with all the logical statements, but I was able to solve it using the following properties

1. $X\cup Y=(X\Delta Y)\Delta(X\cap Y)$
2. $X\Delta Y=(X\cup Y)\backslash(X\cap Y)$

and some elementary set operations. I hope that this route will also be of use to you :)

To prove: $(A\cup B)\Delta C\equiv(A\Delta C)\Delta(B\backslash A)$

Proof:

By 1. we have $$(A\cup B)\Delta C=(A\Delta B)\Delta(A\cap B)\Delta C=(A\Delta B)\Delta C\Delta(A\cap B)=(A\Delta C)\Delta B\Delta(A\cap B)$$ Note that we want this to equal $(A\Delta C)\Delta(B\backslash A)$, so we want to show $B\Delta(A\cap B)=B\backslash A$.

By 2. we have $$B\Delta(A\cap B)=\Big(B\cup (A\cap B)\Big)\backslash\Big(B\cap (A\cap B)\Big)$$ Now $B\cup (A\cap B)=B$ and $B\cap (A\cap B)=B\cap A$, such that $$B\Delta(A\cap B)=B\backslash(B\cap A)=B\backslash A$$ and we are done.

• Thank you! I worked through the proof as described and arrived at the same conclusion. This was very helpful. I have one further question for you: do you think it's a good investment of my time now (as a newbie to logic/set theory) to spend some time working out various properties like the ones you used to solve this, or should I just continue through my text? I am finding part of the hang up in solving problems like this is that I don't have these very useful properties on-hand to make them intelligible, but I don't feel comfortable using them if I haven't proven them myself. Commented Dec 8, 2015 at 18:39
• You're welcome. What text are you referring to? If time permits, I'd recommend doing some exercises on set-equalities like the one in your question. Practicing is the best way to get familiar with it. Commented Dec 8, 2015 at 21:18
• I'm working through Velleman's "How to Prove It, A Structured Approach." Commented Dec 8, 2015 at 21:26
• I am not familiar with that, but looking at the table of contents I see it has exercises in it. I'd suggest making those. Other than that, I am not familiar enough with your situation to give you accurate advise on how to proceed, may be someone in your surroundings can provide that (e.g. a teacher)? Commented Dec 9, 2015 at 7:39

\newcommand{\calc}{\begin{align} \quad &} \newcommand{\op}[1]{\\ #1 \quad & \quad \unicode{x201c}} \newcommand{\hints}[1]{\mbox{#1} \\ \quad & \quad \phantom{\unicode{x201c}} } \newcommand{\hint}[1]{\mbox{#1} \unicode{x201d} \\ \quad & } \newcommand{\endcalc}{\end{align}} \newcommand{\ref}[1]{\text{(#1)}} \newcommand{\then}{\Rightarrow} \newcommand{\when}{\Leftarrow} \newcommand{\symdiff}{\mathbin\triangle} \newcommand{\true}{\text{true}} \newcommand{\false}{\text{false}}First, regarding your "What am I missing here?" question, as far as I can see the answer is simply this: $\; (x \in C \land x \not\in A \land x \not\in B) \lor (x \in C \land x \not\in A \land x \in A) \;$ is (as you already noted) equivalent to $\; x \in C \land x \not\in A \land x \not\in B \;$, which is one of the disjuncts of your $$(x \in A \land x \notin C) \lor (x \in B \land x \notin C) \lor (x \in C \land x \notin A \land x \notin B)$$

Second, as an alternative proof of $$\tag 0 (A \cup B) \symdiff C \;=\; (A \symdiff C) \symdiff (B \setminus A)$$ we could first use the fact that $\;\symdiff\;$ is both symmetrical and associative: $$\calc (A \cup B) \symdiff C \;=\; (A \symdiff C) \symdiff (B \setminus A) \op=\hint{\;\symdiff\; is symmetric} (A \cup B) \symdiff C \;=\; (B \setminus A) \symdiff (A \symdiff C) \op=\hints{\;\symdiff\; is associative} \hint{-- this gives LHS and RHS a similar shape} (A \cup B) \symdiff C \;=\; ((B \setminus A) \symdiff A) \symdiff C \op\when\hint{logic: Leibniz} \tag{1} A \cup B \;=\; (B \setminus A) \symdiff A \endcalc$$ Now we are left with proving $\ref 1$, and the symmetry and associativity of $\;\symdiff\;$.

Third, another alternative proof of $\ref 0$ would be to use the definition $$x \in X \symdiff Y \;\equiv\; x \in X \not\equiv x \in Y$$ together with the fact that both $\;\equiv\;$ and $\;\not\equiv\;$ are symmetric and associative, and also mutually associative: that will quickly reduce $\ref 0$ to something with a shape like $$P \lor Q \;\equiv\; \lnot Q \;\equiv\; P \land \lnot Q$$ which is easy to prove using the fact that $\;R \then S\;$ is equivalent to both $\;\lnot R \lor S\;$ and $\;R \;\equiv\; R \land S\;$.