90
правок
Изменения
→Формула включения-исключения
Пусть <tex>~l</tex> {{---}} это количество множеств, мощность пересечения которых мы ищем. Для случая <tex>~l=1</tex> и <tex>~l=2</tex> теорема, очевидно, верна. Таким образом, <tex>~l=2</tex> {{---}} база индукции.
Предположим, что для <tex>~l=n-1</tex> теорема верна, то есть равенство выполняется. Докажем, что равенство истинно для <tex>~l=n+1</tex>
Пусть <tex> A <center/tex>{{---}} пересечение <tex>~n</tex> множеств. Тогда очевидно, что <tex> A = \bigcup \limits_{i=1}^{n}A_i = \Bigg( \underbrace {\bigcup \limits_{i=1}^{n-1}A_i}_{B} \Bigg) \cup A_n </tex>. Пусть <tex> B = \bigcup \limits_{i=1}^{n-1}A_i </tex>
<center>
<tex> | B | = \sum \limits_{I \subset \{ 1,2, \ldots ,n-1 \} } (-1)^{|I|+1} \Big| \bigcap \limits_{ j \in I } A_j \Big| </tex>
