Results 1 to 12 of 12
Like Tree5Thanks
  • 1 Post By Plato
  • 1 Post By Plato
  • 1 Post By Plato
  • 1 Post By emakarov
  • 1 Post By emakarov

Math Help - Prove By Subsets

  1. #1
    Member
    Joined
    May 2011
    Posts
    178
    Thanks
    6

    Prove By Subsets

    Hello all,

    I am currently working on proving these statements \overline{A \cap B \cap C} and \overline{A}\cup \overline{B} \cup \overline{C}, by means of subsets (I've heard that is is also referred to as, "proof by double inclusion."). I am having trouble with these sort of problems, so I'd certainly appreciate the help.

    Here is my work:

    Suppose that x \in \overline{A \cap B \cap C}; for x to be in the set, x can't be in A \cap B \cap C. This means that x \notin A \wedge x \notin B \wedge x \notin C; however, by this fact, x can be in \overline{A}, \overline{B}, or \overline{C}. Thus, when x \in  \overline{A \cap B \cap C}, x is also in \overline{A}\cup \overline{B} \cup \overline{C}, meaning that \overline{A \cap B \cap C} \subseteq \overline{A}\cup \overline{B} \cup \overline{C}

    I have not commenced the second part, yet, because I feel as though there is something wrong with this, and I feel like I might have left out steps and explanations.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,386
    Thanks
    1476
    Awards
    1

    Re: Prove By Subsets

    Quote Originally Posted by Bashyboy View Post
    I am currently working on proving these statements \overline{A \cap B \cap C} and \overline{A}\cup \overline{B} \cup \overline{C}, by means of subsets (I've heard that is is also referred to as, "proof by double inclusion."). I am having trouble with these sort of problems, so I'd certainly appreciate the help.

    Here is my work:

    Suppose that x \in \overline{A \cap B \cap C}; for x to be in the set, x can't be in A \cap B \cap C. This means that x \notin A \wedge x \notin B \wedge x \notin C; however, by this fact, x can be in \overline{A}, \overline{B}, or \overline{C}. Thus, when x \in  \overline{A \cap B \cap C}, x is also in \overline{A}\cup \overline{B} \cup \overline{C}, meaning that \overline{A \cap B \cap C} \subseteq \overline{A}\cup \overline{B} \cup \overline{C}

    I have not commenced the second part, yet, because I feel as though there is something wrong with this, and I feel like I might have left out steps and explanations.
    This is usually done by using induction.

    What you have is not correct.

    x \in \overline {A \cap B \cap C}  \to x \notin A \vee x \notin B \vee x \notin C
    Thanks from Bashyboy
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2011
    Posts
    178
    Thanks
    6

    Re: Prove By Subsets

    Quote Originally Posted by Plato View Post
    This is usually done by using induction.

    What you have is not correct.

    x \in \overline {A \cap B \cap C}  \to x \notin A \vee x \notin B \vee x \notin C
    I haven't learned about induction yet. Where did I write in my proof that x \in \overline {A \cap B \cap C}  \to x \notin A \vee x \notin B \vee x \notin C? Isn't this what I am trying to prove?
    Last edited by Bashyboy; March 17th 2013 at 09:26 AM.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,386
    Thanks
    1476
    Awards
    1

    Re: Prove By Subsets

    Quote Originally Posted by Bashyboy View Post
    I haven't learned about induction yet. Where did I write in my proof that x \in \overline {A \cap B \cap C}  \to x \notin A \vee x \notin B \vee x \notin C? Isn't this what I am trying to prove?
    I did not say you wrote that.

    In fact you wrote is:
    x \in \overline{A \cap B \cap C}; for x to be in the set, x can't be in A \cap B \cap C. This means that x \notin A \wedge x \notin B \wedge x \notin C.
    That is FALSE.

    What I posted is TRUE.
    Thanks from Bashyboy
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2011
    Posts
    178
    Thanks
    6

    Re: Prove By Subsets

    Oh, so the use of the disjunction means that x can't be in any of the three sets?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,386
    Thanks
    1476
    Awards
    1

    Re: Prove By Subsets

    Quote Originally Posted by Bashyboy View Post
    Oh, so the use of the disjunction means that x can't be in any of the three sets?
    No again. It means that x is not in at least one of the three sets.
    Thanks from Bashyboy
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    May 2011
    Posts
    178
    Thanks
    6

    Re: Prove By Subsets

    Okay, Plato, is this better:

    Suppose that x \in \overline{A \cap B \cap C}, then x can't be an element of A \cap B \cap C; in order for x to not be in A \cap B \cap C, then it must be the case that x \notin A \vee x \notin B \vee x \notin C, that is, it must be the case that x is not in at least one of the three sets. If x is not in at least in one of those sets, then x \in A \vee x \in B \in C, that is, it is at least in of the three sets \overline {A}, \overline{B}, or \overline{C}. By the definition of the union, the set \overline{A} \cup \overline{B} \cup \overline{C} will possess the element x, because at least one of the three sets has x.

    Would this show that the statement is a subset of the other?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Member
    Joined
    May 2011
    Posts
    178
    Thanks
    6

    Re: Prove By Subsets

    And to prove that \overline{A} \cup \overline{B} \cup \overline{C} \subseteq (\overline{A \cap B \cap C}), would this be sufficient:

    Suppose that x \in \overline{A} \cup \overline{B} \cup \overline{C}. For x to be in the set, x has to be in at least one of the three sets, meaning x can't be in A \cap B \cap C, because if this were so, x would have to then be in all three sets, falsifying our original assumption. Moreover, if x is not in A \cap B \cap C, we can say that x \in \overline{(A \cap B \cap C)}.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Prove By Subsets

    Quote Originally Posted by Bashyboy View Post
    If x is not in at least in one of those sets, then x \in A \vee x \in B \in C
    This formula should be x\in\overline{A}\lor x\in\overline{B}\lor x\in\overline{C}.
    Thanks from Bashyboy
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Member
    Joined
    May 2011
    Posts
    178
    Thanks
    6

    Re: Prove By Subsets

    Oh yes, you are right. I forgot to type the lines in. But the rest of the proof is correct?
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Prove By Subsets

    Quote Originally Posted by Bashyboy View Post
    Oh yes, you are right. I forgot to type the lines in. But the rest of the proof is correct?
    Yes, though the style may be somewhat improved.

    Quote Originally Posted by Bashyboy View Post
    And to prove that \overline{A} \cup \overline{B} \cup \overline{C} \subseteq (\overline{A \cap B \cap C}), would this be sufficient:

    Suppose that x \in \overline{A} \cup \overline{B} \cup \overline{C}. For x to be in the set, x has to be in at least one of the three sets, meaning x can't be in A \cap B \cap C, because if this were so, x would have to then be in all three sets, falsifying our original assumption. Moreover, if x is not in A \cap B \cap C, we can say that x \in \overline{(A \cap B \cap C)}.
    This is correct, though since the fact is so simple, it is difficult to say whether this explanation is not enough, adequate, or too much. I would write, "... x has to be in at least one of the three sets. If x\in\overline{A}, then x\notin A and therefore x\notin A\cap B\cap C, and similarly for x\in\overline{B} and x\in\overline{C}. In all three cases, we have x\notin A\cap B\cap C, i.e., x\overline{A\cap B\cap C}."
    Thanks from Bashyboy
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Member
    Joined
    May 2011
    Posts
    178
    Thanks
    6

    Re: Prove By Subsets

    Oh, I see. Thank you both so very much for the help.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 14
    Last Post: October 30th 2012, 06:40 AM
  2. Replies: 1
    Last Post: November 8th 2011, 12:52 PM
  3. Subsets
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 19th 2011, 11:35 AM
  4. Subsets of R^3
    Posted in the Advanced Algebra Forum
    Replies: 11
    Last Post: May 14th 2011, 01:26 AM
  5. Subsets
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: October 1st 2009, 07:54 PM

Search Tags


/mathhelpforum @mathhelpforum