Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Principle of inclusion-exclusion proof

  1. Sep 16, 2011 #1
    There are 3 events A,B and C prove that

    P(A[itex]\cup[/itex]B[itex]\cup[/itex]C) = P(A)+P(B)+P(C)-P(A[itex]\cap[/itex]B)-P(A[itex]\cap[/itex]C)-P(B[itex]\cap[/itex]C)+P(A[itex]\cap[/itex]B[itex]\cap[/itex]C)
    each event is disjoint so by the additivity rule....

    My attempt:
    A[itex]\cup[/itex]B[itex]\cup[/itex]C = (A[itex]\cap[/itex]B[itex]\cap[/itex]C)[itex]\cup[/itex](A[itex]\cap[/itex][A[itex]\cap[/itex]B[itex]\cap[/itex]C]c)[itex]\cup[/itex]([B[itex]\cap[/itex]C][itex]\cap[/itex][A[itex]\cap[/itex]B[itex]\cap[/itex]C]c)[itex]\cup[/itex](C[itex]\cap[/itex]Ac[itex]\cap[/itex]([B[itex]\cap[/itex]C][itex]\cap[/itex][A[itex]\cap[/itex]B[itex]\cap[/itex]C]c)c)[itex]\cup[/itex](B[itex]\cap[/itex]Ac[itex]\cap[/itex]([B[itex]\cap[/itex]C][itex]\cap[/itex][A[itex]\cap[/itex]B[itex]\cap[/itex]C]c)c)

    each event is disjoint so by the additivity rule....
    P(A[itex]\cup[/itex]B[itex]\cup[/itex]C) = P(A[itex]\cap[/itex]B[itex]\cap[/itex]C)+P(A[itex]\cap[/itex][A[itex]\cap[/itex]B[itex]\cap[/itex]C]c)+P([B[itex]\cap[/itex]C][itex]\cap[/itex][A[itex]\cap[/itex]B[itex]\cap[/itex]C]c)+P(C[itex]\cap[/itex]Ac[itex]\cap[/itex]([B[itex]\cap[/itex]C][itex]\cap[/itex][A[itex]\cap[/itex]B[itex]\cap[/itex]C]c)c)+P(B[itex]\cap[/itex]Ac[itex]\cap[/itex]([B[itex]\cap[/itex]C][itex]\cap[/itex][A[itex]\cap[/itex]B[itex]\cap[/itex]C]c)c)

    P(A[itex]\cap[/itex](A[itex]\cap[/itex]B[itex]\cap[/itex]C)c) = P(A)-P(A[itex]\cap[/itex]B[itex]\cap[/itex]C)
    P((B[itex]\cap[/itex]C)[itex]\cap[/itex](A[itex]\cap[/itex]B[itex]\cap[/itex]C)c) = P(B[itex]\cap[/itex]C)-P(A[itex]\cap[/itex]B[itex]\cap[/itex]C)
    P(C[itex]\cap[/itex]Ac[itex]\cap[/itex]([B[itex]\cap[/itex]C][itex]\cap[/itex][A[itex]\cap[/itex]B[itex]\cap[/itex]C]c)c) = P(C[itex]\cap[/itex](A[itex]\cap[/itex]C)c[itex]\cap[/itex]([B[itex]\cap[/itex]C][itex]\cap[/itex][A[itex]\cap[/itex]B[itex]\cap[/itex]C]c)c) = P(C)-P(A[itex]\cap[/itex]C)-P((B[itex]\cap[/itex]C)[itex]\cap[/itex](A[itex]\cap[/itex]B[itex]\cap[/itex]C)c) = P(C)-P(A[itex]\cap[/itex]C)-P(B[itex]\cap[/itex]C)+P(A[itex]\cap[/itex]B[itex]\cap[/itex]C)
    P(B[itex]\cap[/itex]Ac[itex]\cap[/itex]([B[itex]\cap[/itex]C][itex]\cap[/itex][A[itex]\cap[/itex]B[itex]\cap[/itex]C]c)c) = P(B[itex]\cap[/itex](A[itex]\cap[/itex]B)c[itex]\cap[/itex]([B[itex]\cap[/itex]C][itex]\cap[/itex][A[itex]\cap[/itex]B[itex]\cap[/itex]C]c)c) = P(B)-P(A[itex]\cap[/itex]B)-P((B[itex]\cap[/itex]C)[itex]\cap[/itex](A[itex]\cap[/itex]B[itex]\cap[/itex]C)c) = P(B)-P(A[itex]\cap[/itex]B)-P(B[itex]\cap[/itex]C)+P(A[itex]\cap[/itex]B[itex]\cap[/itex]C)

    then by substitution...

    P(A[itex]\cup[/itex]B[itex]\cup[/itex]C) = P(A[itex]\cap[/itex]B[itex]\cap[/itex]C)+P(A)-P(A[itex]\cap[/itex]B[itex]\cap[/itex]C)+P(B[itex]\cap[/itex]C)-P(A[itex]\cap[/itex]B[itex]\cap[/itex]C)+P(C)-P(A[itex]\cap[/itex]C)-P(B[itex]\cap[/itex]C)+P(A[itex]\cap[/itex]B[itex]\cap[/itex]C)+P(B)-P(A[itex]\cap[/itex]B)-P(B[itex]\cap[/itex]C)+P(A[itex]\cap[/itex]B[itex]\cap[/itex]C)
    = P(A)+P(B)+P(C)-P(A[itex]\cap[/itex]C)-P(A[itex]\cap[/itex]B)-P(B[itex]\cap[/itex]C)+P(A[itex]\cap[/itex]B[itex]\cap[/itex]C)

    did i do this right? I feel like i may have overcomplicated it..
     
    Last edited: Sep 16, 2011
  2. jcsd
  3. Sep 16, 2011 #2

    Stephen Tashi

    User Avatar
    Science Advisor

    You haven't explained what laws of probability can be assumed in order to prove the result and you didn't say which laws you used. Putting a 'P' in front of each set in an expression is not "substitution".
     
  4. Oct 9, 2011 #3
    Proof By Induction is a lot more elegant,but you have to be careful of your notation
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Principle of inclusion-exclusion proof
Loading...