How Can I Prove the Set Identity (A ∩ B) △ C = (A △ C) △ (A \ B)?

[user10921]

Homework Statement

$$(A \cap B) \triangle C = (A \triangle C) \triangle (A \backslash B)$$

Relevant Equations

none

Hello, I am having trouble with proving the following set identity:

$$(A \cap B) \triangle C = (A \triangle C) \triangle (A \backslash B)$$

What I did so far was focus on this:
$$((A \lor C) \land (\lnot A \lor \lnot C) \lor (A \land \lnot B)) \land ((\lnot A \land \lnot C) \lor (A \land C) \land (\lnot A \lor B))$$ ---> so I focus on the first part of the equation
$$((A \lor C) \land (\lnot C) \lor \lnot A \lor (A \land \lnot B)$$ which made it $$(A \land \lnot C) \lor (\lnot A \lor \lnot B)$$ and after that $$(A \land \lnot C) \lor \lnot A \lor (\lnot B)$$ which made it $$(\lnot A \lor \lnot C \lor \lnot B)$$ and using DeMorgan's Law it ended up being $$\lnot ((A \land B) \land C)) \land ?$$ I am not sure what to do for the other half of the equation though. I'm basically talking about this part:
$$((\lnot A \land \lor C) \lor (A \land C) \land (\lnot A \lor B))$$
Can someone use the same method shown in the image to the right hand side of the equation? I need help solving this and I am having a bit of trouble with this.

[Moderator's note: Moved from a technical forum and thus no template.]

 

[user10921]

It's also fine if you could show that they are subsets of each other

 

[nuuskur]

The attachment is not relevant to this problem.

I recommend playing around with Venn diagrams so you would get a feel for what's going on. The initial equality indeed does hold.

Remark

• in general $(A\lor B) \land (C\lor D) \not\equiv A \lor (B \land (C\lor D))$. You make this mistake right after you say "I focus on first part ...". When you correctly compute the part you are working on first, it yields
  $$(A\lor C) \land (\neg A\lor \neg C) \lor (A\land \neg B) \equiv (A\triangle C) \cup (A\setminus B)$$

For the second part, you would apply the distributive law and eventually arrive at
$$\neg (A\lor C) \lor (A\land C) \land (\neg A \lor B) \equiv \neg (A\lor C) \lor (A\land B\land C).$$
The connective between the first and second part of the long expression is $\land$, however this does not lead to desired result. Your long expression is not equivalent to the RHS, in fact the final intersection is empty (in fact your first and second part are negations of one another).

It is not unreasonable to solve this problem with truth tables. Alternatively, as you pointed out, it also suffices to show there is inclusion in both directions. Please revise your work before continuing.

 

[Mark44]

Problem Statement: $$(A \cap B) \triangle C = (A \triangle C) \triangle (A \backslash B)$$

What operation does the $\triangle$ symbol represent? I am familiar with all of the other symbols you've used, but not this one.

 

[nuuskur]

What operation does the $\triangle$ symbol represent? I am familiar with all of the other symbols you've used, but not this one.

This is known as the symmetric difference of sets:
$$A\triangle B := (A\setminus B) \cup (B\setminus A) = (A\cup B) \setminus (A\cap B).$$

 

[Mark44]

This is known as the symmetric difference of sets:
$$A\triangle B := (A\setminus B) \cup (B\setminus A) = (A\cup B) \setminus (A\cap B).$$

OK, thanks -- now I remember that one. It's been a while since I've seen it.

 

[user10921]

The problem is that it's supposed to be
$$((A \land B) \lor C)$$

 

[user10921]

But that doesn't help either so how can I prove they are inclusions of each other?

 

[Mark44]

But that doesn't help either so how can I prove they are inclusions of each other?

The usual way. For example, to show that D = E, assume that $x \in D$, and show that $x \in E$. This proves that $D \subset E$. To show inclusion in the other direction, assume that $x \in E$, and show that $x \in D$, thereby proving that $E \subset D$.
For your problem, assume that $x \in (A \cap B) \triangle C$ and then show that it must be true that $x \in (A \triangle C) \triangle (A \backslash B)$.
Then assume that $x \in (A \triangle C) \triangle (A \backslash B)$, and show that $x \in (A \cap B) \triangle C$.

 

[user10921]

The usual way. For example, to show that D = E, assume that $x \in D$, and show that $x \in E$. This proves that $D \subset E$. To show inclusion in the other direction, assume that $x \in E$, and show that $x \in D$, thereby proving that $E \subset D$.
For your problem, assume that $x \in (A \cap B) \triangle C$ and then show that it must be true that $x \in (A \triangle C) \triangle (A \backslash B)$.
Then assume that $x \in (A \triangle C) \triangle (A \backslash B)$, and show that $x \in (A \cap B) \triangle C$.

Do I expand out the equation or leave it as is?

 

[Mark44]

Do I expand out the equation or leave it as is?

If you prove the statement in the order I described, you can expand $(A \cup B)\triangle C$, and continue from there. You can do the same when you're doing the other half of the proof.

BTW, $(A \cup B)\triangle C$ is NOT an equation, nor is $(A \triangle C) \triangle (A \backslash B)$. An equation always has an = symbol in it.

 

[user10921]

If you prove the statement in the order I described, you can expand $(A \cup B)\triangle C$, and continue from there. You can do the same when you're doing the other half of the proof.

BTW, $(A \cup B)\triangle C$ is NOT an equation, nor is $(A \triangle C) \triangle (A \backslash B)$. An equation always has an = symbol in it.

Alright thank you, and I'll remember to not say equation.

 

[user10921]

Sorry, but I am having a bit of trouble with this. What I did so far was this:
$$ x\in ((A \land B) \lor C) \land x\notin ((A \land B) \land C)$$
And I used the distributive law
$$(x\in(A \lor C) \land x\in(B \lor C)) \land (x\in(\lnot A \lor \lnot C) \lor x\in(\lnot B \lor \lnot C))$$
I am not sure what's next. Don't be harsh I am a newbie

 

[Mark44]

Sorry, but I am having a bit of trouble with this. What I did so far was this:
$$ x\in ((A \land B) \lor C) \land x\notin ((A \land B) \land C)$$

I'm having a little bit of a hard time reading this because you're using logical symbols ($\land, \lor, \lnot$) instead of set symbols ($\cap, \cup, \sim$).
I would write your expression as $x \in ((A \cup B) \cap C) \land x \notin (A \cap B \cap C)$. The symbols $\land$ and $\lor$ are to be used for expressions that are either true or false, but not for combining sets.

And I used the distributive law
$$(x\in(A \lor C) \land x\in(B \lor C)) \land (x\in(\lnot A \lor \lnot C) \lor x\in(\lnot B \lor \lnot C))$$
I am not sure what's next. Don't be harsh I am a newbie

Instead of $\lnot A$, for the complement of A, I would write $\sim A$ or $A^C$ or $\overline A$, although what you wrote is actually fairly clear.

For this expression -- $x \in ((A \cup B) \cap C) \land x \notin (A \cap B \cap C)$ -- it would be helpful to draw several Venn diagrams to get a feel for what this is saying. The first subexpression says that x is in the intersection of A and B (which could be empty if the sets don't contain any common members, or x is in C. A couple of drawings where all three sets overlap vs. C doesn't overlap either A or B might be helpful.

 

[user10921]

Actually I believe they have the empty set in common. It is not $$A\cup B$$ it is
$$A\cap B$$.

 

[user10921]

If they have 0 elements in common they aren't subsets then? Then that means the original expression
$$(A\triangle C) \triangle (A\backslash B)$$
is not a subset? This is straight out How To Prove it by Daniel J Velleman. Here's a link or you can search it on Google:
HOW TO PROVE IT: A Structured Approach, Second Edition
users.metu.edu.tr/serge/courses/111-2011/textbook-math111.pdf

 

[user10921]

Well I created some venn diagrams and it cleared it all up now, never mind. Thank you for your contributions everyone.