1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Prove an Associative Law (set theory)

  1. Jun 12, 2013 #1
    1. The problem statement, all variables and given/known data
    Prove that: A[itex]\cup[/itex](B[itex]\cup[/itex]C) = (A[itex]\cup[/itex]B)[itex]\cup[/itex]C

    2. Relevant equations

    3. The attempt at a solution
    I never had to prove anything but I'll try.
    A[itex]\cup[/itex](B [itex]\cup[/itex]C).
    A = {1, 2, 3, 4, 5}, B = {5, 6, 7, 8, 9, 10}, C = {7, 8, 9, 10}
    (B[itex]\cup[/itex]C) = P
    If A[itex]\cup[/itex]P means A, united with the union of B and C, which is {5, ..., 10}. Their union is {1, ..., 10}
    Now take (A[itex]\cup[/itex]B) = P
    P = {1, ..., 10}
    P[itex]\cup[/itex]C = {1, ..., 10}
    With that I prove that the problem above is True :P But is that enough?
    Last edited: Jun 12, 2013
  2. jcsd
  3. Jun 12, 2013 #2


    User Avatar
    Education Advisor

    When proving a general statement, you need to avoid specific cases. Although working through a specific case may help you get the general idea on how to prove a statement, it doesn't prove the general case. When it comes to proving sets, the most common technique is to grab an arbitrary element from the set and show that since it belongs to a certain set it also belongs to this other set to and work towards your result. For example, let x be an element from the set A U (B U C), then x is an element of A or x is an element of (B U C). If x is an element of A...etc etc etc
  4. Jun 12, 2013 #3


    Staff: Mentor

    No, it's not. You can't prove a general statement by the use of an example.

    One way to prove this would be to start with an element x that is an element of ##A \cup (B \cup C) ##, and show that it is also in ##(A \cup B) \cup C ##. This shows that the set on the left side of the equation is a subset of the one on the right side.

    Now assume that x is an element of ##(A \cup B) \cup C ##. If you can show that the same element also belongs to ##(A \cup B) \cup C ##, you will have shown that the set on the right side is a subset of the one on the left side, which establishes the equality of the two sets.
  5. Jun 13, 2013 #4
    If x is an element of A U (B U C). That means that x is either in A, B or C.
    If x is an element of C U (A U B). That means that x is either in A, B or C.
  6. Jun 13, 2013 #5


    Staff: Mentor

    When you say "either ... or" the implication is that x is in one of them, but not the other. That is not necessarily true. It could be that A and B overlap (their intersection is not empty, or that A and C overlap, or that B and C overlap, or even that all three sets overlap.

    So it's conceivable that x is in both A and B, but not in C, for example.
    I would write it as (A U B) U C, which is the way it's written in the problem. What I said above applies here as well.
  7. Jun 13, 2013 #6


    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Presumably you mean ##(A\cup B)\cup C##. While what you say is true, it doesn't constitute a proof. To show two sets ##M## and ##N## are the same, you show ##M\subset N## and ##N \subset M##. You are leaving out a lot of steps. So start out with supposing ##x\in A\cup (B\cup C)##. That means ##x\in A## or ##x \in B\cup C##, as you have stated. And if ##x \in B\cup C## then ##x\in B## or ##x \in C##. Now, depending on which is the case, you have to show in any event that ##x \in (A\cup B)\cup C##. You can't just declare it to be true. Give the details for each possibility. Once you have that, you are half done with the problem.
  8. Jun 14, 2013 #7
    So, for (A [itex]\cup[/itex] B) [itex]\cup[/itex] C. Suppose x [itex]\in[/itex] (A [itex]\cup[/itex] B) [itex]\cup[/itex] C. That means x [itex]\in[/itex] (A [itex]\cup[/itex] B) or x [itex]\in[/itex] C. From x [itex]\in[/itex] (A [itex]\cup[/itex] B) we can derive that x [itex]\in[/itex] A or x [itex]\in[/itex] B.
  9. Jun 14, 2013 #8


    User Avatar
    Science Advisor

    I would give a little more detail. To prove "A U (B U C)= (A U B) To prove "if x is in A U (B U C) then it is s in A U (B U C)" (the statement says nothing about "C U (A U B)") we prove
    1) A U (B U C)[itex]\subseteq[/itex] (A U B) U C and then prove
    2) (A U B) U C [itex]\subseteq[/itex] A U (B U C)

    And we prove "X [itex]\subseteq[/itex] Y" by starting "if x is in X" and using the properties of X and Y to conclude "then x is in Y".

    If x is in A U(B U C) then (by definition of "U") x is in A or x is in B U C. Again, by definition of U, if x is in B U C then x is in B or in C. So we have three possibilities
    1) if x is in A then it is in A U B and so in (A U B) U C.
    2) if x is in B then it is in A U B and so in (A U B) U C.
    3) if x is in C then it is immediately in (A U B) U C.

    Do the same to prove "(A U B) U C [itex]\subseteq[/itex] A U (B U C)".
  10. Jun 14, 2013 #9
    Aha so firstly we prove how the left side is equal to the right and then how the right side is equal to the left?
  11. Jun 14, 2013 #10


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    No. First you prove that every element of the set on the left is an element of the set on the right, and then you prove that every element of the set on the right is an element of the set on the left.

    There's an axiom of set theory that says that an equality X=Y holds if and only if every element of X is an element of Y, and every element of Y is an element of X. That's what you need to use.

    So you should start by saying something like "Let x be an arbitrary element of ##A\cup(B\cup C)##". Then you use the definition of ##\cup## to prove that ##x\in (A\cup B)\cup C##. Then I suggest you leave a blank line for clarity, and start the next paragraph with "Now let x be an arbitrary element of ##(A\cup B)\cup C##". The rest should be obvious.

    This isn't precalculus by the way. Since set theory is usually studied after calculus, I will move this to calculus & beyond.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted