формула включения и исключения для 4-х множеств

[Marina]

Я знаю как выглядит формула включения и исключения для 4-х множеств:
$|A\cup B\cup C \cup D|=|A|+|B|+|C|+|D|-|A\cap B|-|A\cap C|-|A\cap D|-|B\cap C|-|B\cap D|-|C\cap D|+ |A\cap B\cap C|+|A\cap B\cap D|+|A\cap C\cap D|+|B\cap C\cap D|-|A\cap B\cap C\cap D|$.
А как это доказать или обосновать не знаю. Подскажите, пожалуйста.

[ИСН]

Круги рисовать умеете?

[Профессор Снэйп]

Marina в сообщении #297973 писал(а):

Я знаю как выглядит формула включения и исключения для 4-х множеств

Я тоже

Marina в сообщении #297973 писал(а):

А как это доказать или обосновать не знаю.

Взять формулу для $n$ множеств и подставить в неё $n=4$

[Marina]

ИСН, Вы имеете ввиду диаграмму Эйлера

[Профессор Снэйп]

(Оффтоп)

Леонид Ильич, переверните страницу, это олимпийские кольца :)

-- Пн мар 15, 2010 19:40:27 --

Нарисуйте круги так, чтобы все возможные пересечения образовывали $15$ различных множеств.

[Marina]

Цитата:

Взять формулу для $n$- множеств

Нужно объяснение без применения формулы $n$-множества.

-- Пн мар 15, 2010 16:50:38 --

Профессор Снэйп

(Оффтоп)

Если Вы своё пятое добавите для точности рисунка

[ИСН]

Круги у Вас не очень хороши тем, что четверное пересечение пусто; но вообще-то они тут не нужны, это просто у меня такая catchphrase. На самом деле надо так:
- Посчитаем все. Теперь смотрим: входящие в два множества оказались посчитаны дважды, поэтому их вычитаем. Но теперь входящие в три множества оказались...

[maxmatem]

Посмотрите в книге Виленкина "Комбинаторика", там по-моему есть!

[bot]

Да просто индукцию по числу множеств примените.

[Marina]

bot
Индукцию по числу множеств не проходили. Может без её можно обойтись?

[Alexey1]

Докажите формулу $|A \cup F|=|A|+|F|-|A \cap F|$. Затем, вместо $F$ возьмите $B \cup C$ и используйте доказанную формулу для доказательства $|A \cup B \cup C|$. Аналогично для четырёх множеств.

[Marina]

Alexey1 Я Вас правильно поняла:
$|A\cup B\cup C|=|(A\cup B)\cup C|=|A\cup B| +|C|- |(A\cup B)\cap C|=|A|+|B|-|A\cap B|+|C|-|(A\cap C)\cup (B\cap C)|=|A|+|B|-|A\cap B|+|C|-|A\cap C|+|B\cap C|-|(A\cap C)|\cap (B\cap C)|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap C\cap B|$

|A\cup B\cup C\cup D|= |A\cup B| + |C\cup D|- |(A\cup B)\cap (C\cup D)|=|A| + |B|+|C| + |D| - |C\cap D|-|A\cap B|- |(A\cup B)\cap (C\cup D)|=

[ewert]

В предпоследнем выражении первой цепочки скобки потеряны, но на выходе -- верно.

Общая теорема выглядит так: мощность объединения есть сумма единичных мощностей, минус сумма всех парных, плюс сумма всех троек, минус сумма всех четвёрок, и т.д. до мощности пересечения всех (с соответствующим знаком). И доказывается -- именно по индукции. Вот Вы сейчас эту индукцию и провели, только для конкретного $n=3$.

Для четырёх, соответственно -- Ваша стратегия не учень удачна. Разумнее раскрывать $|(A\cup B\cup C)\cup D|$.

[PAV]

Вывод по индукции здесь, наверное, самый правильный, но можно сделать напрямую и без него. Фактически это метод с помощью "кругов", но ничего рисовать не нужно. Все пространство представляется в виде попарно непересекающихся 16-ти множеств вида: $ABCD$, $ABC\overline{D}$, $AB\overline{C}D$, $AB\overline{C}\overline{D}$, ..., $\overline{A}\overline{B}\overline{C}\overline{D}$.

Левая часть тождества содержит 15 множеств (все, кроме последнего). Далее можно вручную выписать через эти множества все слагаемые в правой части. $A$ будет состоять из 8-ми множеств, $AB$ из четырех и так далее. Затем посокращать все, что получится, и должны придти к тому же, что написано слева.

В принципе ничего не мешать и для общего случая аккуратно доказать, что каждое множество в левой части будет встречаться ровно один раз и в правой.

[Marina]

ewert,
Пошла по Вашему предложению, так как оно мне показалось более понятным:
$|(A\cup B\cup C)\cup D|=|A\cup B\cup C|+|D|-|(A\cup B\cup C)\cap D|=|A|+|B|+|C|+|D|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|- |(A\cup B\cup C)\cap D|$
Или я сделала, что-то не так?