Proof of disjoint sets

  • Thread starter mrkb80
  • Start date
  • #1
mrkb80
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,568
774
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
mrkb80
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,568
774
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
36,702
8,693
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,568
774
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
mrkb80
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,568
774
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
mrkb80
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 let's you add their individual probability?
 
Last edited:
  • #10
LCKurtz
Science Advisor
Homework Helper
Insights Author
Gold Member
9,568
774
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 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.
 
  • #11
mrkb80
41
0
You, sir, are a patient teacher to whom I owe many thanks.
 

Suggested for: Proof of disjoint sets

Replies
11
Views
481
Replies
3
Views
306
  • Last Post
Replies
12
Views
530
  • Last Post
Replies
10
Views
611
Replies
19
Views
437
  • Last Post
Replies
11
Views
747
Replies
1
Views
479
Replies
4
Views
326
Replies
32
Views
619
Replies
13
Views
622
Top