Results 1 to 5 of 5

Math Help - Elementary Set Theory Question

  1. #1
    Junior Member
    Joined
    Dec 2009
    From
    Texas
    Posts
    70
    Awards
    1

    Elementary Set Theory Question

    Hi guys!

    I just worked on another simple set theory proof, and have come out with what seems like it might work alright, but while I was writing this I kind of felt like I was making some statements that perhaps needed to be more better justified. For example, in the second sentence of the proof, it kind of feels like I just pulled that out of thin air without justification.

    \text{\underline{Theorem}:} If A\subseteq B, then \bar{A}= A\ B \cup \bar{B}
    \text{\underline{Proof}:} To show the left to right containment, let x \in \bar{A}. Then x\notin A. Note that there are two cases for B, either x \in B or x \notin B. If x \in B, then we have x \in B and x \notin A, which implies that x \in B\ A. If x \notin B, then x \in \bar{B}, and so x \in B\ A \cup \bar{B}. Therefore, \bar{A} \subseteq B\ A \cup \bar{B}. To show the reverse containment, let  x \in A\ B \cup \bar{B}. Then x \in B\ A or x \in \bar{B}. So we have two cases to consider. Suppose x\in B\ A. Then x \in B and x \notin A. Since x \notin A, x \in \bar{A}. Suppose x \in \bar{B}. Then x \notin B. Note that by hypothesis A \subseteq B, and thus x \notin B clearly implies x \notin A. And so x \in \bar{A}.. Since in either case x \in \bar{A}, we can conlude that B\ A \cup \bar{B} \subseteq \bar{A}. Since we've shown both containments hold true, we can conlude that \bar{A}= B\ A \cup \bar{B}.

    Thanks for taking your time to read this,
    James
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by james121515 View Post
    Hi guys!

    I just worked on another simple set theory proof, and have come out with what seems like it might work alright, but while I was writing this I kind of felt like I was making some statements that perhaps needed to be more better justified. For example, in the second sentence of the proof, it kind of feels like I just pulled that out of thin air without justification.

    \text{\underline{Theorem}:} If A\subseteq B, then \bar{A}= A\ B \cup \bar{B}
    \text{\underline{Proof}:} To show the left to right containment, let x \in \bar{A}. Then x\notin A. Note that there are two cases for B, either x \in B or x \notin B. If x \in B, then we have x \in B and x \notin A, which implies that x \in B\ A. If x \notin B, then x \in \bar{B}, and so x \in B\ A \cup \bar{B}. Therefore, \bar{A} \subseteq B\ A \cup \bar{B}. To show the reverse containment, let  x \in A\ B \cup \bar{B}. Then x \in B\ A or x \in \bar{B}. So we have two cases to consider. Suppose x\in B\ A. Then x \in B and x \notin A. Since x \notin A, x \in \bar{A}. Suppose x \in \bar{B}. Then x \notin B. Note that by hypothesis A \subseteq B, and thus x \notin B clearly implies x \notin A. And so x \in \bar{A}.. Since in either case x \in \bar{A}, we can conlude that B\ A \cup \bar{B} \subseteq \bar{A}. Since we've shown both containments hold true, we can conlude that \bar{A}= B\ A \cup \bar{B}.

    Thanks for taking your time to read this,
    James
    I would phrase your proof a little better

    "Let x\in A', then x\notin A. If x\in B' we are done, so assume that x\notin B'. Clearly then, we have that x\in B, but since x\notin A it follows that x\in B-A. We may therefore conclude that x\in B' or x\in B-A and thus x\in \left[\left(B-A\right)\cup B'\right]. Conversely, suppose that x\in\left[\left(B-A\right)\cup B'\right]. Then, x\in \left(B-A\right) or x\in B' so that x\in \left(B\cap A'\right) or x\in B'. This leads us to conclude that x\in B\text{ and }x\in A' or x\in B', Using the distributive properties of conjunction (and) and disjunction (or) we may therefore conclude that \left(x\in B'\text{ or }x\in B\right)\text{ and } \left(x\in A'\text{ or }x\in B'\right)\Leftrightarrow x\in\left[U\cup \left(A'\cup B'\right)\right] and since A\subseteq B\implies B'\subseteq A' we see that the above implies x\in A'."


    Alternatively, you may just use the algebra of sets.

    \left(B-A\right)\cup B'=\left(B\cap A'\right)\cup B'=\left(B\cup B'\right)\cap \left(A'\cup B'\right) =U\cap\left(A'\cup B'\right)=A'\cup B'=\left(A\cap B\right)'=A'
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Dec 2009
    From
    Texas
    Posts
    70
    Awards
    1
    Hi Drexel,
    Thank you for your response. So for the first containment (left to right) ours proofs seem to follow the same logic. Would you say my left to right is satisfactory? As for the right to left part, I don't understand what you did there. The only way that made sense was to do it by cases. Clearly we have x \in [A-B] or x\in B', so what made sense at least in my mind was to show that in either case, x \in A'. Also, I notice you said that A \subseteq B \implies B'\subseteq A'. Would this be something that would normally requrie a proof within the proof itself?

    Thanks again for your help,
    james
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by james121515 View Post
    As for the right to left part, I don't understand what you did there.
    Let x\in\left[\left(B-A\right)\cup B'\right]

    1. Then x\in \left(B-A\right)\text{ or }x\in B' (I think you got that)

    2. Since x\in\left(B-A\right)\Leftrightarrow x\in\left(B\cap A'\right) we know that x\in B\text{ and }x\in A' (this is just using the definition of intersection)

    3. So now what we really have is that \left(x\in B\text{ and }x\in A'\right)\text{ or } x\in B' now using the distributive laws of language (in this case the statement \left(P\text{ and }Q\right)\text{ or }S is the same thign as  \left(P\text{ or }S\right)\text{ and }\left(P\text{ or }Q\right)) we see that \left(x\in B\text{ or }x\in B'\right)\text{ and }\left(x\in A'\text{ or }x\in B'\right)

    4. This last thing tells us precisely that x\in\left[\left(B\cup B'\right)\cap\left(A'\cup B'\right)\right]. But, B\cup B'=U (the universal set) and U intersected with anything is itself. So x\in\left[U\cap\left(A'\cup B'\right)\right]\Leftrightarrow x\in\left(A'\cup B'\right)

    5. You may have to prove this (let x\in B' then x\notin B and since x\in A\implies x\in B we may conclude that x\notin A so that x\in A') but A\subseteq B\implies B'\subseteq A' so we may finally conclude that x\in\left(A'\cup B'\right)\Leftrightarrow x\in A'

    This finishes it (I bulletined it so you could better understand it.)
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Grandad's Avatar
    Joined
    Dec 2008
    From
    South Coast of England
    Posts
    2,570
    Thanks
    1
    Hello everyone
    Quote Originally Posted by james121515 View Post
    ...
    \text{\underline{Theorem}:} If A\subseteq B, then \bar{A}= A\ B \cup \bar{B}
    ...
    In case anyone reading this is confused, this should read:

    \text{\underline{Theorem}:} If A\subseteq B, then \bar{A}= (B\ A) \cup \bar{B}

    Grandad
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. elementary number theory question
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 9th 2011, 10:23 AM
  2. Elementary # theory
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 29th 2008, 10:06 AM
  3. elementary # theory
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: October 10th 2008, 06:51 AM
  4. Elementary # Theory
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 2nd 2008, 11:13 PM
  5. Elementary # Theory
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 2nd 2008, 10:36 AM

Search Tags


/mathhelpforum @mathhelpforum