Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Help with proof

  1. Jun 29, 2008 #1
    Ok so over the summer I decided to read Apostol's Calculus Vol. 1 and my only background in calculus is in a high school calculus class, so I know the extreme basics and am trying to put my knowledge on a my rigorous footing.

    I think my biggest problem is definitely writing my own proofs. I just started so I'm still in the section that covers basic set theory and it asks to prove commutative and associative properties involving unions and intersections. I think I can prove the commutative law but the associative law is proving (pun intended) to be quite difficult for me. I just seem to be going around in circles just writing out the problem so I was wondering if anyone could critique this bad attempt and give me some sort of starting place.

    Prove [tex](A \cup B) \cup C = A (B \cup C)[/tex]

    Let [tex]x \in A, y \in B, z \in C[/tex] and let [tex]D = A \cup B, E B \cup C[/tex]

    This implies D = {x, y} and E = {y, z}

    So [tex]D \cup C =[/tex] {x, y, z} and [tex] A \cup E =[/tex] {x, y, z}

    Therefore [tex]D \cup C = A \cup E = (A \cup B) \cup C = A (B \cup C)[/tex]
     
  2. jcsd
  3. Jun 29, 2008 #2
    You're going about this the wrong way. You do not know ahead of time that any of A, B, or C are non-empty so you can't really let x, y, or z belong to any of those sets. Furthermore even if we can let x be in A and y be in B then that does not mean D={x,y}, A and B could have other elements, or x could be equal to y.

    The basic idea in showing that two sets, let's call them P and Q are equal is to show that:
    1) if x is in P, then x is in Q, and
    2) if y is in Q then x is in P

    Statement one proves that P is a subset of Q (why?). And statement two proves that Q is a subset of P, and two sets can only be subsets of each other if they are equal and are in fact the same set, so this is what you need to do for the case where P=(AUB)UC and Q=AU(BUC).
     
  4. Jun 29, 2008 #3
    If you can prove statement one true it proves that P is a subset of Q by the definition of a subset which is for every element x in set P it is contained in set Q, the same goes for statement two just reversed in a sense, correct? My problem, I think, is proving statement one and two true. I thought about that but the best I could come up with was to assume that [tex]x \in P[/tex] which is one of the problems in my original attempt.

    I still don't think I'm getting it...
     
  5. Jun 29, 2008 #4
    yes precisely

    To show that P = Q, you must show that [itex]P \subset Q[/tex] and [itex]Q \subset P[/tex]


    To show that [itex]P \subset Q[/tex]

    Allow [itex] x \in P [/itex]. Then show that [itex] x \in Q [/itex].
     
  6. Jun 29, 2008 #5
    If x is in (AUB)UC what is true about x? How can we use any of this information to show that x is in AU(BUC)?
     
  7. Jun 30, 2008 #6
    If x is in (A U B) U C then x is in (A U B) or x is in C.

    just work the definitions
     
  8. Jun 30, 2008 #7
    All of this makes sense however what if A, B and C are empty then P would also be empty so how can we just assume [itex]x \in P[/itex]?

    Edit: By the way thanks for all the help so far :)
     
  9. Jun 30, 2008 #8

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    Some textbooks make the point that you should start a set proof like this "If x is in (A U B) U C" rather than "Let x be in (A U B) U C" for precisely that reason. If A, B, C are all empty you can't say "let x be in ..." but the hypothesis of "if x is in ..." is, in that case, false, so the theorem itself is vacuously true.
     
    Last edited: Aug 1, 2008
  10. Jun 30, 2008 #9
    So...

    Let P = (A U B) U C and Q = A U (B U C)

    If [itex]x \in P[/itex] then x must belong to, at least, one set A, B, or C.

    Therefore [itex]x \in Q[/itex] ==> [itex]P \subseteq Q[/itex]

    By the same logic we find [itex]Q \subseteq P[/itex]

    Therefore P=Q ==> (A U B) U C = A U (B U C)

    Is that correct?
     
  11. Jun 30, 2008 #10

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    This is largely immaterial: if X is empty, then the statement if x in X then... is vacuously true so there is nothing to worry about.
    Alternately one can worry about these exceptions individually, but the proof then is also trivial.
     
  12. Jun 30, 2008 #11
    Yeah, but the way I worded it in the first post was "Let x..." instead of "If x..." I can kind of see a difference in the two. "If" implies we're just considering a case where as "Let" kind of seems like one is simply saying x IS in a particular set.
     
  13. Jul 30, 2008 #12
    here is your proof:
    xεAU(BUC)<====>xεAVxε(BUC)<======>xεAV(xεBVxεC)<======>(xεAVxεB)VxεC<===>
    xε(AUB)VxεC<======>xε(AUB)UC<====> AU(BUC)= (AUB)UC
    The qestion now is how do we prove xεAV(xεBVxεC) <====>(xεAVxεB)VxεC
     
  14. Jul 31, 2008 #13
    Here is another proof:
    Let xɛ[AU(BUC)] then this is equivalent to xɛAV xɛ(BUC) then we have to examine two cases:
    1) for xɛA but xɛA ==> xɛAv xɛB <====> xɛ(AUB) ===> xɛ(AUB)v xɛC <===> xɛ[(AUB)UC]


    2) for xɛ(BUC),but xɛ(BUC) <===> xɛBv xɛC AND now we examine the two subcases.
    2a) for xɛB WE HAVE xɛB ==> xɛBv xɛA <===> xɛAv xɛB <==> xɛ(AUB) ===> xɛ(AUB)vxɛC <==> xɛ[(AUB)UC]
    2b) for xɛC WE HAVE xɛC ==> xɛCv xɛ(AUB) ==> xɛ(AUB)v xɛC <=====> xɛ[(AUB)UC]
    Hence all cases give us xɛ[(AUB)UC]
    So we have proved xɛ[AU(BUC)]====> xɛ[(AUB)UC]
    Now for the opposite we follow exactly the same way
     
  15. Jul 31, 2008 #14
    Here is one more proof

    Let xɛ[AU(BUC)] this is equivalent to xɛAvxɛ(BUC) which is equivalent to
    ~xɛA→xɛ(BUC). ………………………………………………..1

    Let ~xɛ(AUB) then by D Morgans rule we have that
    ~xɛA…………………………………………………………2
    ~xɛB………………………………………………………….3
    From 1 and 2 we deduce xɛ(BUC) which is equivalent to
    xɛBvxɛC↔ ~xɛB→xɛC…………………………………………….4
    From 3 and 4 we deduce xɛC
    Hence ~xɛ(AUB)→xɛC or xɛ(AUB)vxɛC or xɛ[(AUB)UC]
    Therefor xɛ[AU(BUC]→xɛ[(AUB)UC]
    For the opposite we follow exactly the same way
    NOTE ~xε means x does not belong to
     
  16. Aug 1, 2008 #15
    Now let us present a proof by contradiction.
    Let xε[AU(BUC)]
    But xε[AU(BUC)] <==> xεAv xε(BUC) <==>
    ~ xε A==> xε(BUC)………………………………………………1
    Let now ~ xε[(AUB)UC]
    But ~ xε[(AUB)UC] <==> ~ xε(AUB)˄ ~ xεC====>
    ~ xεA…………………………………………………………………2
    ~ xεB………………………………………………………………….3
    ~ xεC………………………………………………………………….4
    Now from 1 and 2 we deduce xε(BUC)……………………………..5
    From 3 and 4 we have ~ xεB˄~ xεC <===>~ xε(BUC)………….6
    But 5 and 6 are contradictory .
    Hence xε[(AUB)UC]
    So we have proved xε[AU(BUC)] ==>` xε[(AUB)UC]
    For the opposite we follow the same way
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Help with proof
  1. Proof Help (Replies: 1)

  2. Proof help (Replies: 6)

  3. Direct proofs help (Replies: 1)

Loading...