Results 1 to 8 of 8

Math Help - 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
    (A\cup B)-(B\cap C) = (A-B)\cup(A-C)\cup(B-C)
    Let x\in A-C
    if  x\notin A-B\  then\ x\in A\cap B and therefore  x\in B-C
    else x\in A-B (since A=[A-(A-B)]\cup(A-B))
    therefore A-C\subseteq (A-B)\cup(B-C)
    Last edited by tah; February 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
    (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
    (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..

    (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.

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

    (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
    (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
    (A\cup B)-(B\cap C) = (A-B)\cup(A-C)\cup(B-C)
    Let x\in A-C
    if  x\notin A-B\ then\ x\in A\cap B and therefore  x\in B-C
    else x\in A-B (since A=[A-(A-B)]\cup(A-B))
    therefore A-C\subseteq (A-B)\cup(B-C)
    Tah you have nearly completed the proof without realizing that:


    WE want to prove :

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

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

    Let 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:

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


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

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

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

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

    (\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: (\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: \neg x\in C..................................7


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

    Finally we have proved:


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


    Hence , (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: March 8th 2011, 10:25 AM
  2. Replies: 5
    Last Post: October 19th 2010, 10:50 AM
  3. Set theory proof?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 10th 2010, 12:27 PM
  4. Set Theory Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 2nd 2010, 03:40 AM
  5. Set Theory Proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 13th 2006, 01:54 PM

Search Tags


/mathhelpforum @mathhelpforum