Proof of Disjoint Sets: A Simple Induction Argument Using Probability Functions

[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 A₁,A₂,...,A_n of pairwise disjoint sets, P(Union from i=1 to n of A_i)=Ʃ from i=1 to n of A_i

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

There is a hint with the question:
If A₁,A₂,...,A_n are pairwise disjoints on the sample space Ω, then P(Union from i=1 to ∞ A_i) = Ʃ from i=1 to ∞ A_i

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 ∞ A_i) = Ʃ from i=1 to ∞ P(A_i)?

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)

 

[LCKurtz]

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 A₁,A₂,...,A_n of pairwise disjoint sets, P(Union from i=1 to n of A_i)=Ʃ from i=1 to n of A_i

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

Yes, that is for sure.

There is a hint with the question:
If A₁,A₂,...,A_n are pairwise disjoints on the sample space Ω, then P(Union from i=1 to ∞ A_i) = Ʃ from i=1 to ∞ A_i

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 ∞ A_i) = Ʃ from i=1 to ∞ P(A_i)?

Yes again.

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)

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.

 

[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(A₁ U A₂)= P(A₁) + P(A₂)...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 A_i)=P(Ʃ from i=1 to k of A_i) ?

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

 

[LCKurtz]

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(A₁ U A₂)= P(A₁) + P(A₂)...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 A_i)=P(Ʃ from i=1 to k of A_i) ?

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

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.

 

[Mark44]

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(A₁ U A₂)= P(A₁) + P(A₂)...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 A_i)=P(Ʃ from i=1 to k of A_i) ?

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.

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

 

[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.

 

[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 A_i) + P(A_k+1)=P(Ʃ for i=1 to k of A_i) + P(A_k+1)

Am I going in the right direction?

 

[LCKurtz]

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 ofA_i) + P(A_k+1)=P(Ʃ for i=1 to k of P(A_i)) + P(A_k+1)

Am I going in the right direction?

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.

 

[mrkb80]

P(∪ k+1 i=1 A i )= P(Union for i=1 to k of A_i U A _k+1) =
Ʃ(for i=1 to k of P(A_i)) + P(A_k+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 let's you add their individual probability?

 

[LCKurtz]

P(∪ k+1 i=1 A i )= P(Union for i=1 to k of A_i) U A _k+1) = P(Union for i=1 to k of A_i)+ P(A_k+1)=
Ʃ(for i=1 to k of P(A_i)) + P(A_k+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 let's you add their individual probability?

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.

 

[mrkb80]

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