Results 1 to 13 of 13

Math Help - Need help with set theory proof

  1. #1
    Member
    Joined
    Mar 2010
    Posts
    75

    Need help with set theory proof

    Prove or Disprove: if the complement of A is a subset of B then A union B= U


    This is as far as I got.
    The complement of A is anything that is NOT A.
    If everything that is NOT A IS a subset of B then that does NOT necessarily mean that A union B=U.

    Let x be an element in the complement of set A.

    If x E of the complement of set A, and the complement of A is the subset of B then A also must be the subset of B. Because A is the subset of B then A union B= B it is NOT EQUAL to U. However, the complement of B union B would equal the universe.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,615
    Thanks
    1578
    Awards
    1
    Quote Originally Posted by matthayzon89 View Post
    Prove or Disprove: if the complement of A is a subset of B then A union B= U
    Clearly A\cup B\subseteq U.
    So suppose that x\in U. Then x\in A\text{ or }x\in A^c. WHY?
    If x\in A then x\in A\cup B. WHY?
    If x\notin A then x\in B. WHY?
    Therefore, x\in A\cup B. That completes the proof. HOW?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Mar 2010
    Posts
    75
    Okay I THINK I got it right, can someone please take a look?

    Prove or Disprove: If the complement of A is the subset of B then A union B= Universe

    TRUE.

    Proof By contradiction:
    Suppose not. That is, suppose that if the complement of A is the subset of B then A union B DOES NOT equal U.

    Let,
    Complement of A= {1,2,3}
    A= {4,5,6,7}
    B={1,2,3,4,5}
    U={1,2,3,4,5,6,7}

    Then,

    The complement of A subset B= {1,2,3}
    A union B= {1,2,3,4,5,6,7} = U

    This is a contradiction b/c we supposed that if the complement of A is the subset of B then A union B DOES NOT equal the universe.
    However, the original statement is TRUE b/c it IS the case that when the complement of A is the subset of B then A union B = U. **END OF PROOF***
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Banned
    Joined
    Mar 2009
    Posts
    256
    Thanks
    1
    Quote Originally Posted by matthayzon89 View Post
    Prove or Disprove: if the complement of A is a subset of B then A union B= U


    This is as far as I got.
    The complement of A is anything that is NOT A.
    If everything that is NOT A IS a subset of B then that does NOT necessarily mean that A union B=U.

    Let x be an element in the complement of set A.

    If x E of the complement of set A, and the complement of A is the subset of B then A also must be the subset of B. Because A is the subset of B then A union B= B it is NOT EQUAL to U. However, the complement of B union B would equal the universe.

    Let U = {1,2,3,4,} , A={1} ,B={2,3,4},then complement A ={2,3,4} which is a subset 0f B ,and now:

    A union B = {2,3,4}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,615
    Thanks
    1578
    Awards
    1
    Quote Originally Posted by xalk View Post
    Let U = {1,2,3,4,} , A={1} ,B={2,3,4},then complement A ={2,3,4} which is a subset 0f B ,and now:

    A union B = {2,3,4}
    But A\cup B=\{1,2,3,4\}=U

    @matthayzon89
    Did you bother to read my response?
    It is true. I gave you a proof.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Member
    Joined
    Mar 2010
    Posts
    75
    How is what I did incorrect? can you guys please specify or disprove my proof?

    Of can you tell me that it is correct? b/c it makes sense to me, i just don't want to get a bad grade b/c I didnt double check...
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Banned
    Joined
    Mar 2009
    Posts
    256
    Thanks
    1
    Quote Originally Posted by Plato View Post
    But A\cup B=\{1,2,3,4\}=U

    @matthayzon89
    Did yoy bother to read my response?
    It is true. I gave you a proof.
    It IS getting late and i am liable to do stupid mistakes
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    Mar 2010
    Posts
    75
    Quote Originally Posted by Plato View Post
    But A\cup B=\{1,2,3,4\}=U

    @matthayzon89
    Did you bother to read my response?
    It is true. I gave you a proof.
    Yes I read it, Thank you for taking the time to respond. However, while I was waiting for someone to respond I came up with my own proof, I don't doubt your proof is correct. I just wanted to see if my proof is incorrect Or maybe both methods are valid methods to prove this?
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Member
    Joined
    Mar 2010
    Posts
    75
    l
    Last edited by matthayzon89; April 5th 2010 at 04:16 PM.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    Mar 2010
    Posts
    75
    Can somone please let me know if my proof is correct? PLEASE I am veryyy tiered and frustrated and my brain is fried from working on discrete math all day

    moreover, this problem is due tomorrow morning.... and I need to get it done b4 i go to sleep
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Disregard this post. Please see next post
    Last edited by MoeBlee; April 6th 2010 at 07:12 AM.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4
    Quote Originally Posted by matthayzon89 View Post
    Can somone please let me know if my proof is correct?
    You mean your argument in your post #3? No that argument makes no sense. I'll explain.

    First, though, yes the statement in question is provable (but your approach itself is not correct).

    Let '\' stand for the binary complement operation.

    And since U is the universe, we suppose:

    A subset of U
    and
    B subset of U.

    Theorem:

    If A subset of U
    and
    B subset of U
    and
    U\A subset of B,
    then AuB = U.

    Proof (essentially the same as poster Plato's correct argument):

    Suppose x in AuB. So x in A or x in B. But since both A and B are subsets of U, we have x in U. So AuB subset of U.

    Now suppose x in U. If x in A then, since A subset of U, we have x in U. And if x not in A then x in U\A, which is a subset of B, so x in B. So since x either in A or not in A, we have x in A or x in B. So X in AuB. So U subset of AuB.

    So AuB subset of U, and U subset of AuB, so AuB = U.

    Done.

    Now, here's what's wrong with your approach. What you did is show that for PARTICULAR sets A, B, and U, we have the desired result. But that's not at all how proof by contradiction works in this case. In this case, proof by contradiction is to assume is that there exist sets A, B, and U for which the result fails and to derive a contradiction. The fact that the result does hold for some particular A, B, and U in no way proves that there isn't also some A, B, and U for which the result fails, thus you've not derived any contradiction. All you have is that the result holds for some A, B, and U along with the assumption that it fails for some A, B, and U. But that is not a contradiction.

    Anyway, we don't need proof by contradiction in this case. All we need is the straightforward approach to showing to sets equal by showing each is a subset of the other, just as the poster Plato first gave it to you.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Member
    Joined
    Mar 2010
    Posts
    75
    Okay! got it.

    Thank you for taking the time to write a reply, take care.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Set Theory: Help with a proof
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: November 11th 2010, 01:59 PM
  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: February 2nd 2010, 03:40 AM
  4. A Set Theory Proof
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: November 1st 2009, 02:53 PM
  5. Set Theory Proof
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 13th 2006, 01:54 PM

Search Tags


/mathhelpforum @mathhelpforum