Q. 2.9 - A First Course in Probability

Question

For a finite set$A$, let's $N\left(A\right)$denote the number of elements$A$.

$\left(a\right)$Show that$N(A \cup B) = N\left(A\right) + N\left(B\right) - N\left(AB\right)$

$\left(b\right)$More generally, show that${N\left({\cup A}_i\right)=\underset{}{\sum N\left(A_i\right)-\sum _{i<j}\underset{}{\sum }}N(A_i A_{j })+...+{(-1)}^{n+1}N(A_{1 } A_{2... } A_{n })}_{}$

Step-by-Step Solution

Answer

The proof $a)$is similar to the proof of Proposition $4.4$from the remark

$b)$is proved by mathematical induction, using$a)$

Step 1 Given Information.

For a finite set$A$, let's $N\left(A\right)$denote the number of elements$A$.

Step 2 Part (a) Explanation.

 Let's count the number of elements$A\cup B$ directly. There are $\mathrm{N}\left(\mathrm{A}\right)+\mathrm{N}\left(\mathrm{B}\right)$elements if we count them separately. But notice that we counted the elements $A\cap B$twice. Hence

$N(A\cup B=N(A)+N(B)-N(A\cap B).$

Step 3 Part (b) Explanation.

 We will apply mathematical induction to the number of sets. For$n=2$, see Part$\left(a\right)$. Now assume for$n=k$ we have.$N\left(A_1\cup A_2\cup \dots \cup A_k\right)=\sum _{i=1}^{k}N\left(A_i\right)-\sum _{i_1<i_2}N\left(A_{i_1}\cap A_{i_2}\right)+\dots +(-1{)}^{r+1}\sum _{i_1<\dots <i_r}N\left(A_{i_1}\cap \dots \cap A_{i_r}\right)+\dots +(-1{)}^{k+1}N\left(A_1\cap \dots \cap A_k\right)$

For$n=k+1$. Set $A=A_1\cup \dots \cup A_k$and apply Part$\left(a\right)$. Then we get

$N\left(A_1\cup A_2\cup \dots \cup A_k\cup A_{k+1}\right)=N\left(A\right)+N\left(A_{k+1}\right)-N\left(A\cap A_{k+1}\right)$

Using the induction hypothesis we get

$N\left(A_1\cup A_2\cup \dots \cup A_{k+1}\right)=N\left(A\right)+N\left(A_{k+1}\right)-N\left(A\cap A_{k+1}\right)$

$N\left(A_1\cup A_2\cup \dots \cup A_{k+1}\right)=N\left(A_{k+1}\right)+\sum _{i=1}^{k}N\left(A_i\right)-\sum _{i_1<i_2}N\left(A_{i_1}\cap A_{i_2}\right)+\dots +(-1{)}^{r+1}\sum _{i_1<\dots <i_r}N\left(A_{i_1}\cap \dots \cap A_{i_r}\right)+\dots +(-1{)}^{k+1}N\left(A_1\dots A_k\right)-N\left(A\cap A_{k+1}\right)$

Now observe that

$$\begin{gathered} N\left(A\cap A_{k+1}\right)=N\left(\left(A_1\cup \dots \cup A_k\right)\cap A_{k+1}\right) \\ =N\left(\left(A_1\cap A_{k+1}\right)\cup \dots \cup \left(A_k\cap A_{k+1}\right)\right) \\ =\sum _{i=1}^{k}N\left(A_i\cap A_{k+1}\right)-\sum _{i_1<i_2}N\left(A_{i_1}\cap A_{i_2}\cap A_{k+1}\right)+\dots +(-1{)}^{r+1}\sum _{i_1<\dots <i_r}N\left(A_{i_1}\cap \dots \cap A_{i_r}\cap A_{k+1}\right) \\ +\dots +(-1{)}^{k+1}N\left(A_1\cap \dots \cap A_k\cap A_{k+1}\right) \end{gathered}$$

Combining this with the identity above we get

$N\left(A_1\cup A_2\cup \dots \cup A_{k+1}\right)=\sum _{i=1}^{k+1}N\left(A_i\right)-\sum _{i_1<i_2}N\left(A_{i_1}\cap A_{i_2}\right)+\dots +(-1{)}^{r+1}\sum _{i_1<\dots <i_r}N\left(A_{i_1}\cap \dots \cap A_{i_r}\right)+\dots +(-1{)}^{k+2}N\left(A_1\cap \dots \cap A_{k+1}\right)$

Hence we get the desired identity by mathematical induction.