• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Proving set equivalencies

26
2
Homework Statement
$$(A \cap B) \triangle C = (A \triangle C) \triangle (A \backslash B)$$
Homework 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.]
 

Attachments

Last edited:
26
2
It's also fine if you could show that they are subsets of each other
 
509
324
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 [itex](A\lor B) \land (C\lor D) \not\equiv A \lor (B \land (C\lor D))[/itex]. 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
    [tex]
    (A\lor C) \land (\neg A\lor \neg C) \lor (A\land \neg B) \equiv (A\triangle C) \cup (A\setminus B)
    [/tex]
For the second part, you would apply the distributive law and eventually arrive at
[tex]
\neg (A\lor C) \lor (A\land C) \land (\neg A \lor B) \equiv \neg (A\lor C) \lor (A\land B\land C).
[/tex]
The connective between the first and second part of the long expression is [itex]\land[/itex], 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.
 
Last edited:
32,631
4,378
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.
 
509
324
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:
[tex]
A\triangle B := (A\setminus B) \cup (B\setminus A) = (A\cup B) \setminus (A\cap B).
[/tex]
 
32,631
4,378
This is known as the symmetric difference of sets:
[tex]
A\triangle B := (A\setminus B) \cup (B\setminus A) = (A\cup B) \setminus (A\cap B).
[/tex]
OK, thanks -- now I remember that one. It's been a while since I've seen it.
 
26
2
The problem is that it's supposed to be
$$((A \land B) \lor C)$$
 
26
2
But that doesn't help either so how can I prove they are inclusions of each other?
 
32,631
4,378
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##.
 
26
2
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?
 
32,631
4,378
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.
 
26
2
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.
 
26
2
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
 
32,631
4,378
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.
user10921 said:
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.
 
26
2
Actually I believe they have the empty set in common. It is not $$A\cup B$$ it is
$$A\cap B$$.
 
26
2
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
 
26
2
Well I created some venn diagrams and it cleared it all up now, never mind. Thank you for your contributions everyone.
 

Want to reply to this thread?

"Proving set equivalencies" You must log in or register to reply here.

Related Threads for: Proving set equivalencies

  • Posted
Replies
2
Views
1K
Replies
3
Views
3K
  • Posted
Replies
4
Views
1K
  • Posted
Replies
3
Views
1K
Replies
10
Views
1K
Replies
4
Views
984
  • Posted
Replies
4
Views
3K

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Hot Threads

Top