2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Мощность симметрической разности из n элементов
Сообщение11.12.2018, 22:16 
Изображение
Изображение

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

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

 
 
 
 Re: Мощность симметрической разности из n элементов
Сообщение11.12.2018, 23:12 
Надо придумать как выразить характеристическую функцию симметрической разности пары множеств через характеристические функции самих множеств. Что вы предложите?

 
 
 
 Re: Мощность симметрической разности из n элементов
Сообщение12.12.2018, 02:23 
Аватара пользователя
Эту формулу, кажется, можно записать по-разному. Желательно найти такое выражение, которое будет справедливо для любого количества множеств.

 
 
 
 Re: Мощность симметрической разности из n элементов
Сообщение12.12.2018, 02:27 
slavav в сообщении #1360563 писал(а):
Надо придумать как выразить характеристическую функцию симметрической разности пары множеств через характеристические функции самих множеств. Что вы предложите?

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


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

 
 
 
 Re: Мощность симметрической разности из n элементов
Сообщение12.12.2018, 02:31 
Аватара пользователя
А через обычное сложение и умножение можете? В итоге нам они ведь понадобятся.

 
 
 
 Re: Мощность симметрической разности из n элементов
Сообщение12.12.2018, 02:41 
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$ множества, а потом раскрутить её рекуррентно так, чтобы остались только сложение и умножение, после всех упрощений как раз итоговая формула и получится. Но мне непонятно, как этот рекуррентный спуск правильно формально провести. Как-то воспользоваться индукцией?

 
 
 
 Re: Мощность симметрической разности из n элементов
Сообщение12.12.2018, 14:56 
Без индукции никуда. Распишите индукционный шаг. Там всё просто.

 
 
 
 Re: Мощность симметрической разности из n элементов
Сообщение12.12.2018, 20:19 
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}$

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

 
 
 
 Re: Мощность симметрической разности из n элементов
Сообщение12.12.2018, 20:32 
Верно.

 
 
 
 Re: Мощность симметрической разности из n элементов
Сообщение12.12.2018, 20:55 
Здорово, спасибо.

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group