Мощность симметрической разности из n элементов

[parean]

Это отрывок из книжки Шеня "Начала теории множеств". Я понимаю, что доказательство можно провести по индукции, но мне интересно, существует ли способ сделать это как-нибудь изящно через характеристические функции, так же, как в доказательстве теоремы перед заданием (не зря же оно расположено сразу после этого доказательства).

Я что-то не могу придумать. Может быть, кто-нибудь может подсказать?

[slavav]

Надо придумать как выразить характеристическую функцию симметрической разности пары множеств через характеристические функции самих множеств. Что вы предложите?

[Munin]

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

[parean]

slavav в сообщении #1360563 писал(а):

Надо придумать как выразить характеристическую функцию симметрической разности пары множеств через характеристические функции самих множеств. Что вы предложите?

Munin в сообщении #1360597 писал(а):

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

Если я не ошибаюсь, она равна их сумме по модулю два. А для $n$ элементов сумме по модулю два всех элементов. Каждую из сумм можно выразить через коньюнкции и дизъюнкции, но там будет рекуррентная формула, из которой у меня не получается вывести итоговую.

[mihaild]

А через обычное сложение и умножение можете? В итоге нам они ведь понадобятся.

[parean]

mihaild в сообщении #1360601 писал(а):

А через обычное сложение и умножение можете? В итоге нам они ведь понадобятся.

Вроде бы, вот так.
$\chi_{A \triangle B} = ((1-\chi_A)+(1-\chi_B))(\chi_A+\chi_B) = - {\chi_A}^2 - {\chi_B}^2 + 2\chi_A + 2\chi_B - 2\chi_A \chi_B = - {\chi_A} - {\chi_B} + 2\chi_A + 2\chi_B - 2\chi_A \chi_B = \chi_A + \chi_B - 2\chi_A \chi_B $

Мне понятно, что если вместо $B$ подставить симметрическую разность $n-1$ множества, а потом раскрутить её рекуррентно так, чтобы остались только сложение и умножение, после всех упрощений как раз итоговая формула и получится. Но мне непонятно, как этот рекуррентный спуск правильно формально провести. Как-то воспользоваться индукцией?

[slavav]

Без индукции никуда. Распишите индукционный шаг. Там всё просто.

[parean]

slavav в сообщении #1360738 писал(а):

Без индукции никуда. Распишите индукционный шаг. Там всё просто.

Нужно доказать, что
$\chi_{A_1 \triangle ... \triangle A_{n}} = \sum\limits_{i}^{n}\chi_{A_i} - 2\sum\limits_{i<j}^{n}\chi_{A_i}\chi_{A_j}+4\sum\limits_{i<j<k}^{n}\chi_{A_i}\chi_{A_j}\chi_{A_k}+...+(-2)^{n-1}\prod\limits_{i}^{n}\chi_{A_i}$

База доказана ранее.
Пусть для $n$ формула верна. Докажем её для $n + 1$.

$\chi_{A_1 \triangle ... \triangle A_{n+1}} = \chi_{A{n+1}} + \chi_{A_1 \triangle ... \triangle A_{n}} - 2\chi_{A_1 \triangle ... \triangle A_{n}} \chi_{A{n+1}} = \chi_{A{n+1}} + \sum\limits_{i}^{n}\chi_{A_i} - 2\sum\limits_{i<j}^{n}\chi_{A_i}\chi_{A_j}+4\sum\limits_{i<j<k}^{n}\chi_{A_i}\chi_{A_j}\chi_{A_k}+...+(-2)^{n-1}\prod\limits_{i}^{n}\chi_{A_i} - 2\sum\limits_{i}^{n}\chi_{A_i}\chi_{A_{n+1}} + 4\sum\limits_{i<j}^{n}\chi_{A_i}\chi_{A_j}\chi_{A_{n+1}}-8\sum\limits_{i<j<k}^{n}\chi_{A_i}\chi_{A_j}\chi_{A_k}\chi_{A_{n+1}}+...+(-2)^{n}\prod\limits_{i}^{n+1}\chi_{A_i} = \sum\limits_{i}^{n+1}\chi_{A_i} - 2\sum\limits_{i<j}^{n+1}\chi_{A_i}\chi_{A_j}+4\sum\limits_{i<j<k}^{n+1}\chi_{A_i}\chi_{A_j}\chi_{A_k}+...+(-2)^{n}\prod\limits_{i}^{n+1}\chi_{A_i}$

Просуммировав эту формулу по объединению всех множеств, получаем формулу из задания. Всё верно?

[slavav]

Верно.

[parean]

Здорово, спасибо.