# Thread: Set Theory Proof Help

1. ## Set Theory Proof Help

Hey guys, I am working on this proof which I initially thought was true, but found a contradiction while working through it, so I am pretty sure that the statement is false.

However, if its false, I need to find an example for which its false and that is what I am having trouble with. I just cant seem to pick the right numbers.

Statement:

For all sets A, B, C (A-B) U (B-C) = (AUB) - (B (intersect) C)

Haha sorry, I dont know how to make an upside down U, so I just wrote intersect.

Also, is there any method to picking sets that give you a counter example? or is it just blind guessing?

2. Are you sure that these sets are different ? in fact
$\displaystyle (A\cup B)-(B\cap C) = (A-B)\cup(A-C)\cup(B-C)$
Let $\displaystyle x\in A-C$
if $\displaystyle x\notin A-B\ then\ x\in A\cap B$ and therefore $\displaystyle x\in B-C$
else $\displaystyle x\in A-B$ (since $\displaystyle A=[A-(A-B)]\cup(A-B)$)
therefore $\displaystyle A-C\subseteq (A-B)\cup(B-C)$

3. So this is my proof that the statement is actually true, correct me if I am wrong.

(AUB)-(B∩C)
x: xεA v xεB ^ ~xεB v ~xεC [by demorgans law]
xεA ^ ~xεB v xεB ^ ~xεC
(A-B)v(B-C) [by set difference law]

I am not really sure what law would the 2nd line be but I believe this to be correct..

4. Originally Posted by Kitizhi
I am not really sure what law would the 2nd line be but I believe this to be correct..
Using distribution of "et" and "ou", you should get
$\displaystyle (x\in A\wedge x\notin B)\vee (x\in B\vee x\notin C)\vee \color{red}{(x\in A\wedge x\notin C)}$
which I already stated. So how do you remove the red term?

5. Originally Posted by tah
Using distribution of "et" and "ou", you should get
$\displaystyle (x\in A\wedge x\notin B)\vee (x\in B\vee x\notin C)\vee \color{red}{(x\in A\wedge x\notin C)}$
which I already stated. So how do you remove the red term?
I am a little confused..so I am assuming what I did was wrong but for removing the red part I think..

$\displaystyle (x\in B\vee x\notin C)\vee (x\in A\wedge x\notin B)\vee {(x\in A\wedge x\notin C)}$ By commutative law.

$\displaystyle (x\in B\vee x\notin C)\vee (x\in A\wedge {(x\notin B\vee x\notin C))}$ By distribution

$\displaystyle (x\in B\vee x\notin C)\vee (x\in A-{(x\in B\vee x\in C))}$ By demorgans...i think

6. So, you get
$\displaystyle (x\in B-C) \wedge (x\in A-(B\cup C))$ and still you do not have the expression we want (there is a possible answer in my first post on this thread )

7. Originally Posted by tah
Are you sure that these sets are different ? in fact
$\displaystyle (A\cup B)-(B\cap C) = (A-B)\cup(A-C)\cup(B-C)$
Let $\displaystyle x\in A-C$
if $\displaystyle x\notin A-B\ then\ x\in A\cap B$ and therefore $\displaystyle x\in B-C$
else $\displaystyle x\in A-B$ (since $\displaystyle A=[A-(A-B)]\cup(A-B)$)
therefore $\displaystyle A-C\subseteq (A-B)\cup(B-C)$
Tah you have nearly completed the proof without realizing that:

WE want to prove :

$\displaystyle (AUB)-(B\cap C)\subseteq (A-B)U(B-C)$ first and then

$\displaystyle (A-B)U(B-C)\subseteq (AUB)-(B\cap C)$

Let $\displaystyle x\in [(AUB)-(B\cap C)]\Longrightarrow[(x\in A\vee x\in B)\wedge(\neg x\in B\vee\neg x\in C)]$

And:

$\displaystyle x\in A\vee x\in B$.................................................. ........................................1

$\displaystyle \neg x\in B\vee\neg x\in C$.................................................. .....................................2

Now let $\displaystyle \neg x\in(A-B)\Longrightarrow(\neg x\in A\vee x\in B)\Longrightarrow$$\displaystyle (\neg x\in B\rightarrow\neg x\in A)$.................................................. ........................................3

But from (1) we have :$\displaystyle (x\in A\vee x\in B)\Longrightarrow(\neg x\in A\rightarrow x\in B)$.................................................. .........................................4

And from (3) and (4) we get:

$\displaystyle (\neg x\in B\rightarrow x\in B)\Longrightarrow(x\in B\vee x\in B)\Longrightarrow x\in B$.................................................. .......5

But from (2) we have:$\displaystyle (\neg x\in B\vee\neg x\in C)\Longrightarrow(x\in B\rightarrow\neg x\in C)$.................................................. ..........6

And from (5) and (6) we have: $\displaystyle \neg x\in C$..................................7

Combining (5) and (7) we have: $\displaystyle (x\in B\wedge\neg x\in C)\Longrightarrow x\in(B-C)$

Finally we have proved:

$\displaystyle [\neg x\in(A-B)\rightarrow x\in(B-C)]\Longrightarrow x\in[(A-B)U(B-C)]$.

Hence ,$\displaystyle (AUB)-(B\cap C)\subseteq(A-B)U(B-C)$

To prove the converse is not so difficult

8. Thanks benes,

I was getting really confused.