• Support PF! Buy your school textbooks, materials and every day products Here!

Proof of disjoint sets

  • Thread starter mrkb80
  • Start date
  • #1
41
0
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)
 

Answers and Replies

  • #2
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,508
730
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)?
Yes, that is for sure.

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)???
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.
 
  • #3
41
0
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
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,508
730
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.
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
33,079
4,782
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) ?
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.
 
  • #6
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,508
730
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
41
0
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
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,508
730
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 ofAi) + P(Ak+1)=P(Ʃ for i=1 to k of P(Ai)) + P(Ak+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.
 
Last edited:
  • #9
41
0
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:
  • #10
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,508
730
P(∪ k+1 i=1 A i )= P(Union for i=1 to k of Ai) U A k+1) = P(Union for i=1 to k of Ai)+ P(Ak+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?
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
41
0
You, sir, are a patient teacher to whom I owe many thanks.
 
Top