Докажем что 
1) Характеристическая функции левой части:
2) Характеристическая функции правой части:
3) 
, следовательно 
Мощность объединения множеств (формула включений и исключений):
Мощность объединения двух множеств может быть вычислена с помощью формулы:
Очевидно, что если сложить мощности исходных множеств, то элементы, входящие в оба множества будут посчитаны дважды, следовательно, нужно вычесть их количество из общей суммы что бы получить мощность объединения.
Для мощности объединения произвольного количества множеств справедлива следующая формула (формула включений и исключений):
