Proof of disjoint sets

mrkb80 · Sep 10, 2012

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 · Sep 10, 2012

mrkb80 said: ↑

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 · Sep 10, 2012

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 · Sep 10, 2012

mrkb80 said: ↑

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 · Sep 10, 2012

mrkb80 said: ↑

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.

mrkb80 said: ↑

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

LCKurtz · Sep 10, 2012

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 · Sep 10, 2012

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 · Sep 10, 2012

mrkb80 said: ↑

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 · Sep 10, 2012

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 lets you add their individual probability?

LCKurtz · Sep 10, 2012

mrkb80 said: ↑

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

mrkb80 · Sep 10, 2012

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

Log in or Sign up

Proof of disjoint sets

mrkb80

LCKurtz

mrkb80

LCKurtz

Mark44

Staff: Mentor

LCKurtz

mrkb80

LCKurtz

mrkb80

LCKurtz

mrkb80

Set Theory Proof (Replies: 3)

Family of sets proof (Replies: 6)

Proof concerning infinite sets (Replies: 5)

Elementary Set Theory Proof (Replies: 2)

Power sets and cardinalities (proof) (Replies: 3)