Доказательство формулы включений и исключений

[Rusit8800]

Мне не понятен шаг доказательства этой формулы в википедии,
когда применяя формулу

$$\[N({{\bar a}_1} \ldots {{\bar a}_m}) = N - \sum\limits_{i \le m} N ({a_i}) + \sum\limits_{i < j \le m} N ({a_i}{a_j}) + \ldots + {( - 1)^m}N({a_1} \ldots {a_m}){\rm{ }}\]$$

к множеству $\[N({a_{m + 1}})\]$ для свойств ${\displaystyle a_{1},\ldots ,a_{m}}$ получают

$$\[N({{\bar a}_1} \ldots {{\bar a}_m}{a_{m + 1}}) = N({a_{m + 1}}) - \sum\limits_{i \le m} N ({a_i}{a_{m + 1}}) + \sum\limits_{i < j \le m} N ({a_i}{a_j}{a_{m + 1}}) + \ldots + {( - 1)^m}N({a_1} \ldots {a_m}{a_{m + 1}})\]$$

Можете поподробнее показать, почему это так?
И, если можно, без знаков суммирования, я пока к ним не привык, и они могут меня запутать еще больше.

[bot]

Где Вы такое вычитали? В википедии этого нет и $N(a_{m+1})$ - это не множество, а количество элементов, обладающих свойством $a_{m+1}, $ а $N(\overline a_1,\ldots, \overline a_m, a_{m+1})$ - количество элементов, обладающих свойством $a_{m+1} $, но не обладающих ни одним из свойств $ a_1,\ldots, a_m.$

[Sonic86]

Формула очень просто доказывается через характеристические (в Вики - индикаторные) функции - вся алгебра проводится автоматом. Попробуйте его сначала прочитать.

Rusit8800 в сообщении #1198168 писал(а):

Можете поподробнее показать, почему это так?

Ну просто по определению всех $N$-ок. Они всю конструкцию множеств пересекают новым множеством, обладающим свойством $a_{m+1}$ - оно везде автоматом добавляется.

[Rusit8800]

Sonic86 в сообщении #1198345 писал(а):

Они всю конструкцию множеств пересекают новым множеством, обладающим свойством $a_{m+1}$ - оно везде автоматом добавляется

Это все равно не понятно. Просто как можно применять "предполагаемую" формулу для "шаговой" формулы, если в "шаговой" формуле на одно свойство больше? Взять два свойства за одно?

-- 09.03.2017, 23:24 --

Sonic86 в сообщении #1198345 писал(а):

Формула очень просто доказывается через характеристические (в Вики - индикаторные) функции

Пока бы с индукцией разобраться.

-- 09.03.2017, 23:24 --

bot в сообщении #1198318 писал(а):

$N(a_{m+1})$ - это не множество, а количество элементов

Ну, да, описался.

[Sonic86]

Rusit8800 в сообщении #1198604 писал(а):

Это все равно не понятно. Просто как можно применять "предполагаемую" формулу для "шаговой" формулы, если в "шаговой" формуле на одно свойство больше? Взять два свойства за одно?

Нет же. В доказательстве не делается какая-то формальная подстановка или группировка, там делается пересечение системы множеств $A_1,...,A_m$ со свойствами $a_1,...,a_m$ новым множеством элементов $A_{m+1}$, обладающих свойством $a_{m+1}$.
Я с методической точки зрения м.б. неправ, но похоже, что неявно предполагается аналогичное соотношение аж для мультимножеств, оно неявно параллельно доказывается по индукции тоже и операция пересечения выполняется именно с его левой и правой частью. Очень трудно объяснять очевидные вещи
Если с мультимножествами знакомы, могу расписать - там все формально будет.

(bot)

bot в сообщении #1198318 писал(а):

Где Вы такое вычитали? В википедии этого нет и $N(a_{m+1})$ - это не множество, а количество элементов, обладающих свойством $a_{m+1}, $

А кстати загляните в Вику:

Вика писал(а):

Теперь применим формулу для свойств $a_{1},\ldots ,a_{m}$ к множеству $N(a_{m+1})$ объектов, для которых выполнено свойство $a_{m+1}$:

Т.е. текст немножко двусмысленен: его надо читать как "применим формулу ля-ля-ля к множеству, состоящему из $N(a_{m+1})$ объектов, обладающих свойством $a_m$". Просто много буков пропущено

[bot]

Sonic86, ага смотрел ещё раз и недоумевал - у нас разные вики что ли? Видел только очевидную переформулировку, потом некоторые приложения ... Наконец заметил спойлеры.

[Rusit8800]

Sonic86 в сообщении #1198616 писал(а):

Если с мультимножествами знакомы

Впервые такие слова слышу

[arseniiv]

(Мультимножества)

Тут такое отличие: для множества можно сказать, входит или не входит в них элемент, а для мультимножества можно сказать, сколько раз он туда входит (в том числе ноль). Часто хватает натуральночисленных чисел вхождений, и тогда мультимножества с носителем $M$ — это просто функции $M\to\mathbb N$ (носитель — это множество тех элементов, которые могут входить в интересующие мультимножества положительное число раз; часто можно ограничиться наборами мультимножеств с каким-то одним носителем). Такое представление мультимножества — это обобщение характеристической функции множества, она-то может принимать только значения 0 и 1.

[Rusit8800]

Ну, допустим.

[Sonic86]

(Оффтоп)

arseniiv в сообщении #1198814 писал(а):

а для мультимножества можно сказать, сколько раз он туда входит (в том числе ноль).

Ага, или, например, $-1$

arseniiv в сообщении #1198814 писал(а):

(носитель — это множество тех элементов, которые могут входить в интересующие мультимножества положительное число раз

а м.б. ненулевое?

Rusit8800 в сообщении #1198820 писал(а):

Ну, допустим.

Тогда представьте, что в доказательстве формулы включений исключений сначала доказывают изоморфную формулу для мультимножеств, а потом просто берут от этой формулы операцию мощности мультимножества - ее брать проще, она "вполне" аддитивна: $|A\pm B|=|A|\pm |B|$
Т.е. пусть $a_j$ - свойство, $\bar{a_j}$ - его отрицание, $M(c_1,...,c_k)$ - мультимножество элементов, взятых по 1 разу, обладающих свойствами $c_1,...,c_k$. Тогда доказываемая формула выглядит так:

$$M(\bar{a_1} \ldots \bar {a_m}) = M - \sum\limits_{1\leqslant i \leqslant m} M (a_i) + \sum\limits_{1\leqslant i < j \leqslant m} M (a_i,a_j) + \ldots + (-1)^mM(a_1,...,a_m)$$

(т.е. ну никакой разницы, только вместо натуральных чисел стоят мультимножества, сумма и разность мультимножеств понятно как определяются)
Теперь чисто формально можно обе части равенства пересечь с $M(a_{m+1})$ - мультимножеством элементов, обладающих свойством $a_{m+1}$, взятых по одному разу. Получится формула, изоморфная той, которую Вы хотели получить. Дальше надо формулы, видимо, вычитать для получения результата индукционного шага. Ну а потом просто берете ото всех формул мощность мультимножеств и все Надо только еще заметить, что мощности мультимножеств будут равны мощностям соответствующих множеств по понятной причине.

[arseniiv]

(Мультимножества)

Sonic86 в сообщении #1198938 писал(а):

Ага, или, например, $-1$

Sonic86 в сообщении #1198938 писал(а):

а м.б. ненулевое?

Ну, «мультимножества» с потенциально отрицательным числом вхождений, конечно, где-нибудь используются, но вряд ли их стоит так называть…

[Sonic86]

(мультимножества)

arseniiv в сообщении #1199006 писал(а):

Ну, «мультимножества» с потенциально отрицательным числом вхождений, конечно, где-нибудь используются, но вряд ли их стоит так называть…

Не, я честно говоря про мультимножества не читал ничего - я эту теорию сам изобретал в лучшие годы, так что я могу сильно врать.
Но!
А как Вы простите определите ассоциативную и коммутативную сумму + просто связанную разность $A-B = A+(-B)$ в мультимножествах?! Вот та страшная формула у ТС - там же суммы и разности.
Т.е. объединение и пересечение сводится к $\min, \max$, а сумма и разность - к сумме и разности целых чисел - и тогда все красиво.

[arseniiv]

(Мультимножества)

Sonic86 в сообщении #1199028 писал(а):

А как Вы простите определите ассоциативную и коммутативную сумму + просто связанную разность $A-B = A+(-B)$ в мультимножествах?! Вот та страшная формула у ТС - там же суммы и разности.

1. Я, честно говоря, не понимаю, зачем мультимножества для доказательства включений-исключений, когда характеристические функции обычных множеств прекрасно справляются.
2. Сумма определяется обычным поэлементным образом (если носитель один и тот же, а иначе, конечно, доопределяем нулями), а разность на самом деле ограничена поэлементно снизу нулём, и в отрицательные числа не выходит.

Конечно, можно определить ещё и обычную разность, но она будет плохо взаимодействовать с объединением и пересечением, не как у множеств.

P. S. Вспомните про взвешенные графы. Некоторые штуки не получаются, если веса могут быть отрицательными.

[Sonic86]

(мультимножества)

arseniiv в сообщении #1199047 писал(а):

а разность на самом деле ограничена поэлементно снизу нулём, и в отрицательные числа не выходит.

а, усеченную разность берете. Ну ок, но ИМХО все равно менее красиво.

arseniiv в сообщении #1199047 писал(а):

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

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

Rusit8800 в сообщении #1198604 писал(а):

Пока бы с индукцией разобраться.

Вот я ему и ответил. М.б. я зря мультимножества упомянул, мне интуитивно понятно и так

[Rusit8800]

Непонятно только, как идет пересечение данных мультимножеств. По такому аддитивному правилу мне не удалось это сделать.