Can some one help me as i am struck in how to prove inclusion exclusion principle in set theory without using Venn diagrams
That is we have to prove:
$|A \cup B \cup C|=|A|+|B|+|C|+|A \cap B \cap C|-|A \cap B|-|B \cap C|-|C \cap A|$.
[Math] Inclusion exclusion principle in set theory
elementary-set-theory
Best Answer
Here's a derivation using indicators. Let the universe be $X$. Write $I(A)$ for the indicator of set $A$, i.e., $I(A)$ is the function mapping $X$ into $\{0,1\}$ such that $I(A)(x)$ takes value $1$ when $x\in A$, and $0$ otherwise. Then
$$ \begin{align} I(A\cup B\cup C)&\stackrel{(1)}=1-I[(A\cup B\cup C)^c]\\ &\stackrel{(2)}=1-I(A^c\cap B^c\cap C^c)\\ &\stackrel{(3)}=1-I(A^c)I(B^c)I(C^c)\\ &\stackrel{(4)}=1-[1-I(A)][1-I(B)][1-I(C)]\\ &\stackrel{(5)}=I(A)+I(B)+I(C)-I(A)I(B)-I(B)I(C)-I(A)I(C)+I(A)I(B)I(C)\\ &\stackrel{(6)}=I(A)+I(B)+I(C)-I(A\cap B)-I(B\cap C)-I(A\cap C)+I(A\cap B\cap C) \end{align} $$ Steps (1) and (4) use the fact $I(A)=1-I(A^c)$ for the complement $A^c$ of set $A$; step (2) is set algebra; steps (3) and (6) use the fact $I(A\cap B)=I(A)I(B)$; step (5) is algebra. To obtain your result, sum over all $x$ in $X$, using $\sum_x I(A) = |A|$.