Proving Union of Sets: A Mathematical Induction Approach

[Goldenwind]

Homework Statement

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.

Homework 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)

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? ;)

 

[tiny-tim]

My car has stalled; can anyone gimme a push? ;)

Hi Goldenwind!

No, I'll steer, and you push!

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

Does that help?

[size=-2][noparse](… and you have to type ""!)[/noparse][/size]​

 

[HallsofIvy]

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

Now suppose that the statement is true for n= k, so that "(A₁- B)U (A₂-B)U ...U (A_k- B)= (A₁-B)U(A₂-B)U...UA_k)- B.

Let A_k+1 be any set. You need to prove that (A₁U (A₂U ...U(A_k- B)U(A_k+1- B)= (A₁UA₂U...UA_kUA_k+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 (A₁U (A₂U ...U(A_k- B)U(A_k+1- B) then it is in at least one of the sets A_i- B for i from 1 to k+ 1, which means it is in A_i but not in B. Do you see how that implies it is in (A₁UA₂U...UA_kUA_k+1)- B?

Now do it the other way around. If x is in (A₁UA₂U...UA_kUA_k+1)- B, then it is in that union, but, again, not in B. What do you have to show to prove x is in (A₁U (A₂U ...U(A_k- B)U(A_k+1- B)?