# Proof of disjoint sets

1. Sep 10, 2012

### mrkb80

Hi. I need some help with a proof.

The question says:

Let P be a probability function. Prove that for any finite collection of sets, the sequence A1,A2,...,An of pairwise disjoint sets, P(Union from i=1 to n of Ai)=Ʃ from i=1 to n of Ai

I think there must a mistake in question. My guess is it is supposed to say P(Union from i=1 to n of Ai)=Ʃ from i=1 to n of P(Ai)?

There is a hint with the question:
If A1,A2,...,An are pairwise disjoints on the sample space Ω, then P(Union from i=1 to ∞ Ai) = Ʃ from i=1 to ∞ Ai

If A and B are disjoints defined on Ω then P(A U B) = P(A)+ P(B)

Again, I think there must be a mistake in the hint...P(Union from i=1 to ∞ Ai) = Ʃ from i=1 to ∞ P(Ai)???

My question is are there mistakes and can someone get me started in the right direction (Assuming the question has a mistake, then the book says the proof is a straight forward induction argument with P(A U B) = P(A) + P(B), if A and B are mutually exclusive events over S being the starting point)

2. Sep 10, 2012

### LCKurtz

Yes, that is for sure.

Yes again.

Theorem: If $\{A_i\}$ are n disjoint sets then $$P(\cup_{i=1}^n A_i) =\sum_{i=1}^n P(A_i)$$If $n=2$ you have your given starting case. Now suppose it is true for $n=k$, so you know $$P(\cup_{i=1}^k A_i) =\sum_{i=1}^k P(A_i)$$Now you have to show it works for $k+1$ using that it works for $k$ sets. Think about grouping things.

3. Sep 10, 2012

### mrkb80

Glad to confirm those are mistakes.

I wish I could follow you past n=2.

n=2 makes sense to me if you have P(A1 U A2)= P(A1) + P(A2)...that's from the definition in the hint

n=k is where you lose me...how do you jump to P(Union from i=1 to k of Ai)=P(Ʃ from i=1 to k of Ai) ?

Grouping? Not sure I follow...sorry I get a little confused in proofs, but thanks for your help so far.

4. Sep 10, 2012

### LCKurtz

Well, for example, if you had 5 objects, you could group into groups of 2 and 3 objects. Find a way to group $k+1$ into smaller groups that you can work with.

5. Sep 10, 2012

### Staff: Mentor

You get there by assuming that it is true. This is standard practice for induction proofs.

The next step is showing (proving) that $$P(\cup_{i = 1}^{k+1}A_i) = \sum_{i = 1}^{k+1}A_i$$
To do this, use the statement that you are assuming to be true.

6. Sep 10, 2012

### LCKurtz

Here's another hint. If you had three sets and only have the theorem for two you could write $A_1\cup A_2 \cup A_3 = (A_1\cup A_2)\cup A_3$ and use the theorem for two sets twice.

7. Sep 10, 2012

### mrkb80

I think I am starting to follow, it's almost like recursive calls to the 2 set case....not sure how I write that in correct notation.

P(U for i=1 to k of Ai) + P(Ak+1)=P(Ʃ for i=1 to k of Ai) + P(Ak+1)

Am I going in the right direction?

8. Sep 10, 2012

### LCKurtz

You need to start with$$P(\cup_{i=1}^{k+1}A_i)=$$Now group the $A_i$ appropriately with unions and then use the induction hypothesis. And notice you are making the same error as in the original problem of leaving off the P, noted in red.

Last edited: Sep 10, 2012
9. Sep 10, 2012

### mrkb80

P(∪ k+1 i=1 A i )= P(Union for i=1 to k of Ai U A k+1) =
Ʃ(for i=1 to k of P(Ai)) + P(Ak+1)

due to the fact that P(A U B) = P(A) + P(B)... in the case above I'm just letting A=all the sets from 1 to k and B=k+1...so the probability of the union these two "sets" together lets you add their individual probability?

Last edited: Sep 10, 2012
10. Sep 10, 2012

### LCKurtz

You have it, but I have suggested an intervening extra step to make it clearer. That way you use the theorem for 2 sets and for k sets at different steps instead of all at once.

11. Sep 10, 2012

### mrkb80

You, sir, are a patient teacher to whom I owe many thanks.