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: Union proof

  1. Mar 2, 2008 #1
    1. The problem statement, all variables and given/known data
    Prove that if A_1,A_2,…,A_n and B are sets, then
    (A_1 – B) U (A_2 – B) U … U (A_n – B) = (A_1 U A_2 U … U A_n) – B.



    2. Relevant equations
    The chapter this is in is based on mathematical induction, which might be a big hint.

    Mathematical induction:
    Step 1: Prove for the base-case (n = 1)
    Step 2: Prove for the general case (n = k)
    Step 3: Prove for the advancing case (n = k+1)


    3. The attempt at a solution
    I haven't a clue how to prove this in mathematical terms, but I know how to give an analogy to demonstrate that I understand the scenario.

    Imagine people are lined up to enter a building. As they enter the building (As you introduce each union), each person is carrying a bag (A1, A2, A3, etc). When they enter the building, their bags are searched, and anything on the "No-entry" list (Set B) is removed (An airport example would be removing sharp objects, etc).

    (Left side:) If you let people in, and remove their "No-entry" objects upon entry...

    (equals)...the result will be the same as...

    (Right side:) ...if you let them all in, and then removed their "No-entry" objects inside.

    This demonstrates that I understand the problem, and through just gosh darned common freakin' sense, I know that this is a true fact.

    However, I predict only getting part marks for not using mathematical induction, OR for not using mathematical terms.



    My car has stalled; can anyone gimme a push? ;)
     
    Last edited: Mar 2, 2008
  2. jcsd
  3. Mar 2, 2008 #2

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    Hi Goldenwind!

    No, I'll steer, and you push! :wink:

    Hint: Rewrite (A_1 U A_2 U … U A_n) – B as C_n - B.

    Does that help? :smile:

    [size=-2][noparse](… and you have to type ":wink:"!)[/noparse][/size]​
     
  4. Mar 2, 2008 #3

    HallsofIvy

    User Avatar
    Science Advisor

    If n= 1, this just says "A1- B= A1- B" which is obviously true.

    Now suppose that the statement is true for n= k, so that "(A1- B)U (A2-B)U ...U (Ak- B)= (A1-B)U(A2-B)U...UAk)- B.

    Let Ak+1 be any set. You need to prove that (A1U (A2U ...U(Ak- B)U(Ak+1- B)= (A1UA2U...UAkUAk+1)- B.

    The standard way of proving that two sets are equal is to prove each is a "subset" of the other. And the standard way to prove "X is a subset of Y" is to say "if x is in X" and then show "x is in Y".

    If x is in (A1U (A2U ...U(Ak- B)U(Ak+1- B) then it is in at least one of the sets Ai- B for i from 1 to k+ 1, which means it is in Ai but not in B. Do you see how that implies it is in (A1UA2U...UAkUAk+1)- B?

    Now do it the other way around. If x is in (A1UA2U...UAkUAk+1)- B, then it is in that union, but, again, not in B. What do you have to show to prove x is in (A1U (A2U ...U(Ak- B)U(Ak+1- B)?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook