Union proof

  • Thread starter Goldenwind
  • Start date
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:

tiny-tim

Science Advisor
Homework Helper
25,789
242
My car has stalled; can anyone gimme a push? ;)
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]​
 

HallsofIvy

Science Advisor
41,620
821
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)?
 

Want to reply to this thread?

"Union proof" You must log in or register to reply here.

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving

Top Threads

Top