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}\sum _{}}N(A_i{A}_j)+...+{(-1)}^{n+1}N(A_1{A}_{2...}{A}_n)}_{}$

Short 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-by-step solution

Given Information.

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

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 localid="1649342106325" $A\cap B$twice. Hence

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

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.