Мощность объединения множеств

Пример

Пусть $A_1$, $A_2$, ..., $A_k$ — конечные множества.

Пусть $A = A_1\cup A_2\cup ...\cup A_k$.

Требуется найти мощность $A$, если известны $

Пусть $S = \{1,2,...,k\}$ и $T\subseteq S$. Будем говорить, что $x\in A$ обладает свойством $i$, если $x\in A_i$.

Обозначим $f_=(T)$ — число элементов из $A$, обладающих всеми свойствами из $T$ и не обладающих другими свойствами из $S$;

$f_\geq(T)$ — число элементов из $A$, обладающих всеми свойствами из $T$.

Очевидно, $f_\geq (T) = |\bigcap_{i\in T} A_i|$, если $T$ не пусто и $f_\geq (\varnothing) = |A|$

Тогда можно использовать формулу включения-исключения.

Утверждение:

[math]\displaystyle{ |A_1\cup A_2\cup ...\cup A_k| = \sum_{i=1}^{k}|A_i| - \sum_{1\leq i_1 \lt i_2\leq k} |A_{i_1}\cap A_{i_2}| + + \sum_{1\leq i_1 \lt i_2 \lt i_3\leq k} |A_{i_1}\cap A_{i_2}\cap A_{i_3}| - \cdots + (-1)^{k+1}|A_1\cap A_2\cap ... \cap A_k|. }[/math]

Доказательство:

Поскольку каждый элемент из $A$ обладает хотя бы одним свойством из $S$, то $f_=(\varnothing) = 0$. С другой стороны, из формулы включения-исключения получаем [math]\displaystyle{ 0 = f_=(\varnothing)= \sum_{Y\subseteq S} (-1)^{|Y|} f_\geq(Y) = |A| + \sum_{\substack{Y\subseteq S,\\|Y|\geq 1}} (-1)^{|Y|} |\bigcap_{i\in Y} A_i| = }[/math] [math]\displaystyle{ =|A|- \sum_{i=1}^{k}|A_i| + \sum_{1\leq i_1 \lt i_2\leq k} |A_{i_1}\cap A_{i_2}| - \sum_{1\leq i_1 \lt i_2 \lt i_3\leq k} |A_{i_1}\cap A_{i_2}\cap A_{i_3}| + \cdots + (-1)^{k}|A_1\cap A_2\cap ... \cap A_k|. }[/math] Перенесем все слагаемые, кроме первого, за знак равенства и получим искомое утверждение.

[math]\displaystyle{ \blacksquare }[/math]

Рис. 1. Сумма мощностей [math]\displaystyle{ 6+4+7=17 }[/math] считает парные пересечения дважды, а тройное — трижды; вычитаем пары [math]\displaystyle{ 2+3+2=7 }[/math] и прибавляем тройное [math]\displaystyle{ 1 }[/math]. Получаем [math]\displaystyle{ |A\cup B\cup C|=17-7+1=11 }[/math].

Конспект: Дискретная математика