2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user242007 Dec 8 '15 at 18:39
  • $\begingroup$ 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. $\endgroup$ – Eric S. Dec 8 '15 at 21:18
  • $\begingroup$ I'm working through Velleman's "How to Prove It, A Structured Approach." $\endgroup$ – user242007 Dec 8 '15 at 21:26
  • $\begingroup$ 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)? $\endgroup$ – Eric S. Dec 9 '15 at 7:39
0
$\begingroup$

$ \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\;$.

$\endgroup$

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.