Results 1 to 8 of 8

Thread: Set Theory Proof Help

  1. #1
    Newbie
    Joined
    Feb 2009
    Posts
    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?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    tah
    tah is offline
    Junior Member
    Joined
    Feb 2009
    Posts
    51
    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)$
    Last edited by tah; Feb 26th 2009 at 06:28 AM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2009
    Posts
    48
    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..
    Follow Math Help Forum on Facebook and Google+

  4. #4
    tah
    tah is offline
    Junior Member
    Joined
    Feb 2009
    Posts
    51
    Quote Originally Posted by Kitizhi View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Feb 2009
    Posts
    48
    Quote Originally Posted by tah View Post
    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
    Follow Math Help Forum on Facebook and Google+

  6. #6
    tah
    tah is offline
    Junior Member
    Joined
    Feb 2009
    Posts
    51
    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 )
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Feb 2009
    Posts
    18
    Quote Originally Posted by tah View Post
    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
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Junior Member
    Joined
    Feb 2009
    Posts
    48
    Thanks benes,

    I was getting really confused.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help with set theory proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Mar 8th 2011, 10:25 AM
  2. Replies: 5
    Last Post: Oct 19th 2010, 10:50 AM
  3. Set theory proof?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 10th 2010, 12:27 PM
  4. Set Theory Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Feb 2nd 2010, 03:40 AM
  5. Set Theory Proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: Sep 13th 2006, 01:54 PM

Search Tags


/mathhelpforum @mathhelpforum