Число элементов в симметрической разности множеств

[xmaister]

Здравствуйте! Натолкните на мысль по следующей задаче:
Пусть $A_1, A_2,\ldots , A_n$- конечные множества. Доказать, что

$$|A_1\triangle A_2\triangle\ldots\triangle A_n|=\sum\limits_{i}|A_i|-2\sum\limits_{i,j}|A_i\cap A_j|+4\sum\limits_{i,j,k}|A_i\cap A_j\cap A_k|-8\sum\limits_{i,j,k,l}|A_i\cap A_j\cap A_k\cap A_l|+\ldots$$

Благодраю.

[gris]

Слегка смущает нотация суммирования. Ясно, что в случае двух множеств, например, формула означает $\sum\limits_{i,j}|A_i\cap A_j|=|A_1\cap A_2|$, а не суммирование по всем парам индексов. Хотя формула для суммирования по всем парам выглядит даже забавнее.
Это я так, для собственного прояснения.
Можно выразить симметрическую разность через объединение и пересечение.
Можно проследить судьбу каждого элемента, в зависимости его принадлежности или не принадлежности к симметрической разности.
По индукции попробовать.

[xmaister]

gris, я хотел какую-то анологию между вкл-выкл просмотреть, но тут не понятно, почему мы каждый раз прибавляем или отнимаем в 2 раза больше....

gris в сообщении #476703 писал(а):

По индукции попробовать.

Попробую.

[gris]

Начните с двух множеств. Понятно, почему мощность пересечения убираем два раза?
Потом для трёх. Проще их нарисовать и следить, сколько раз суммируется каждая область.
Хотя у вас там требуется строгое, формальное решение. Но лучше всё-же вначале понять механизм действия формулы "на пальцах".

[xmaister]

gris в сообщении #476708 писал(а):

Начните с двух множеств. Понятно, почему мощность пересечения убираем два раза?

Потому что в симметрической разности не содержится пересечения, а оно посчитано 2 раза.

[ellipse]

Если $A\cap B=\varnothing$, то $|A\cup B|=|A|+|B|$.
Поэтому, если $B\subset A$, то $|A\setminus B| = |A|-|B|$.
$A\setminus B = A\setminus (A\cap B)$, где уже $(A\cap B)\subset A$. Отсюда $|A\setminus B|=|A|-|A\cap B|$.
$A\cup B=(A\setminus B) \cup B$, где $(A\setminus B) \cap B=\varnothing$. Отсюда $|A \cup B|=|A\setminus B|+|B|=|A|-|A\cap B|+|B|$.

Теперь индукцией по $n$.
$|A_1\triangle A_2| = |(A_1 \cup A_2)\setminus (A_1 \cap A_2)|=|A_1 \cup A_2|-|A_1 \cap A_2|=|A|+|B|-2|A\cap B|$.
Допустим доказано для $n$, докажем для $n+1$.
$|A_1\triangle \ldots \triangle A_n\triangle A_{n+1}|=|A_1\triangle \ldots \triangle A_n|+|A_{n+1}|-2|(A_1\triangle \ldots \triangle A_n)\cap A_{n+1}|= \\ = |A_1\triangle \ldots \triangle A_n|+|A_{n+1}|-2|(A_1\cap A_{n+1})\triangle \ldots \triangle (A_n\cap A_{n+1})|=\dots$

[xmaister]

Т.е. далее используя то, что $\triangle$ дистрибутивна относительно пересечения получаем:
$|(A_1\cap A_{n+1})\triangle \ldots \triangle (A_n\cap A_{n+1})|=|A_{n+1}\cap(A_1\triangle A_2\triangle\ldots\triangle A_n)|=|A_{n+1}|-|A_{n+1}-(A_1\triangle A_2\triangle\ldots\triangle A_n)|$. Что с последним пересечением сделать можно?

[ellipse]

xmaister в сообщении #476725 писал(а):

Т.е. далее используя то, что $\triangle$ дистрибутивна относительно пересечения получаем:
$|(A_1\cap A_{n+1})\triangle \ldots \triangle (A_n\cap A_{n+1})|=|A_{n+1}\cap(A_1\triangle A_2\triangle\ldots\triangle A_n)|=|A_{n+1}|-|A_{n+1}-(A_1\triangle A_2\triangle\ldots\triangle A_n)|$. Что с последним пересечением сделать можно?

Не надо выносить $A_{n+1}$. Раскрывайте $|(A_1\cap A_{n+1})\triangle \ldots \triangle (A_n\cap A_{n+1})|$ по уже доказанной формуле для мощности симм. разности $n$ множеств.

Доказываемую формулу наверно лучше так записать
$|A_1\triangle A_2\triangle\ldots\triangle A_n|=\sum_{1\le i_1\le n}|A_{i_1}|-2\sum_{1\le i_1<i_2\le n}|A_{i_1}\cap A_{i_2}|+ \\ + 4\sum_{1\le i_1<i_2<i_3\le n}|A_{i_1}\cap A_{i_2}\cap A_{i_3}|-\dots + \\ +(-1)^{k+1}2^k\sum_{1\le i_1<\dots <i_k\le n}|A_{i_1}\cap \dots \cap A_{i_k}| + \dots + \\ + (-1)^{n+1}2^n|A_1\cap \dots \cap A_n| $