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

Proofs . . .

  1. Feb 9, 2010 #1


    User Avatar
    Gold Member

    I just have a very quick (and simple) question: When trying to prove equalities like [itex]A \cup (B \cup C) = (A \cup B) \cup C[/itex], is it sufficient to note that both sets consist of all elements [itex]x[/itex] such that [itex]x \in A[/itex], [itex]x \in B[/itex] or [itex]x \in C[/itex]? Or do I need to go through proving that each set is a subset of the other and consequently deduce that the two sets are equal?

    I already know that the second procedure works and although the first one seems make intuitive sense, I'm concerned that it isn't considered sufficient or formal. I would appreciate any feedback. Thanks!
  2. jcsd
  3. Feb 9, 2010 #2
    I would definitely go about it the second way; ie. show that each set is a subset of the other.
  4. Feb 9, 2010 #3
    Yes. I would first assume that x is an element of the left hand side and do a prove by cases, then do the same assuming x is an element of the right hand side.
  5. Feb 10, 2010 #4


    User Avatar
    Gold Member

    Alright, that's what I've been doing. Thanks for the feedback.
  6. Feb 12, 2010 #5


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Since two sets are equal if and only if they have the same members, the first method is equally valid. But when you consider more difficult problems, it's going to be much more difficult to explicitly write down a set of conditions on x that are satisfied if and only if x is a member of the set on the left (or the set on the right).
  7. Feb 12, 2010 #6


    User Avatar
    Science Advisor

    The key here is to notice that this is just the 'set-theoretic translation' of the corresponding (obvious) fact from logic:
    [tex]P\vee(Q\vee R)\equiv(P\vee Q)\vee R[/tex].

    So my preferred proof would be:

    [tex]x\in A\ \cup \ (B\ \cup \ C)\Leftrightarrow (x\in A)\ \vee \ (x\in B\ \vee \ x\in C)\Leftrightarrow(x\in A\ \cup \ B)\ \vee \ (x\in C)\Leftrightarrow x\in (A\ \cup \ B)\ \cup \ C[/tex].
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook