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


    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


    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