Доказываем теорему по индукции.
Пусть [math]~l[/math] — это количество множеств, мощность пересечения которых мы ищем. Для случая [math]~l=1[/math] и [math]~l=2[/math] теорема, очевидно, верна. Таким образом, [math]~l=2[/math] — база индукции.
Предположим, что для [math]~l=n-1[/math] равенство верно. Докажем, что равенство истинно для [math]~l=n[/math]
Пусть [math] A [/math]— пересечение [math]~n[/math] множеств. Тогда очевидно, что [math] A = \bigcup \limits_{i=1}^{n}A_i = \left( {\bigcup \limits_{i=1}^{n-1}A_i} \right) \cup A_n [/math]. Пусть [math] B = \bigcup \limits_{i=1}^{n-1}A_i [/math]
Тогда исходя из предположения индукции имеем, что
[math] | B | = \sum \limits_{I_{n-1}} (-1)^{|I_{n-1}|+1} \Big| \bigcap \limits_{ j \in I_{n-1} } A_j \Big| [/math]
Кроме того, так как формула верна для [math]~l=2[/math] (из базы индукции), то верно равенство [math] | A | = | B | + | A_n | - | B \cap A_n |(1)[/math]. То найдем мощность множества [math]~ B \cap A_n [/math].
Очевидно, что [math] \Big| B \cap A_n \Big| = \Bigg| \Bigg( \bigcup \limits_{i=1}^{n-1}A_i \Bigg) \cap A_n \Bigg|= \Bigg| \bigcup \limits_{i=1}^{n-1} \bigg( A_i \cap A_n \bigg) \Bigg| (2)[/math]
Тогда из предположения индукции имеем, что [math] (2) = [/math] [math] \sum \limits_{I_{n-1}} (-1)^{|I_{n-1}|+1} \bigg| \bigcap \limits_{ j \in I_{n-1} } \Big( A_j \cap A_n \Big) \bigg| = \sum \limits_{I_{n-1}} (-1)^{|I_{n-1}|+1} \Big| \bigcap \limits_{ j\in I_{n-1} \cup \{ n \} } A_j \Big| [/math]
Подставим полученные значение в [math](1)[/math]:
[math] | A |=| A_n |+\Bigg( \sum \limits_{I_{n-1}} (-1)^{|I_{n-1}|+1} \Big| \bigcap \limits_{ j \in I_{n-1} } A_j \Big| \Bigg) - - \Bigg( \sum \limits_{I_{n-1}} (-1)^{|I_{n-1}|+1} \Big| \bigcap \limits_{ j\in I_{n-1} \cup \{ n \} } A_j \Big| \Bigg)[/math]
В силу того, что [math] - \sum \limits_{I_{n-1}} (-1)^{|I_{n-1}|+1} \Big| \bigcap \limits_{ j\in I_{n-1} \cup \{ n \} } A_j \Big| = \ \sum \limits_{I_{n-1}} (-1)^{|I_{n-1}|+2} \Big| \bigcap \limits_{ j\in I_{n-1} \cup \{ n \} } A_j \Big| \[/math]
Имеем в предыдущей формуле
[math] | A |=| A_n |+\Bigg( \sum \limits_{I_{n-1}} (-1)^{|I_{n-1}|+1} \Big| \bigcap \limits_{ j \in I_{n-1} } A_j \Big| \Bigg) + \Bigg( \sum \limits_{I_{n-1}} (-1)^{|I_{n-1}|+2} \Big| \bigcap \limits_{ j\in I_{n-1} \cup \{ n \} } A_j \Big| \Bigg) = \sum \limits_{I_n} (-1)^{|I_n|+1} \Big| \bigcap \limits_{ j \in I_n } A_j \Big| )[/math] .
Равенство справедливо, потому что все наборы [math] I_n [/math] можно разбить на три группы :
- [math] (n) [/math]
- [math] (I_{n-1})[/math] Это означает, что в наборе точно не будет присутствовать индекс [math] n [/math], а будут все различные варианты индексов остальных множеств, т.е. [math] I_{n-1} [/math]
- [math] (n; I_{n-1}) [/math] Аналогично предыдущему, только в наборе будет индекс [math] n [/math]
Как видно из равенства, каждое слагаемое "отвечает" за соответствующие группы. Значит равенство истинно.
Значит для [math]~l=n[/math] мы доказали, что равенство верно. Значит индукционный переход доказан, то теорема доказана. |