Формула включений/исключений

[Elijah96]

dgwuqtj в сообщении #1651399 писал(а):

Доказывайте тогда для трёх множеств.

Попытка (она приведена выше):

Пусть есть три множества A,B,C

Тогда мощностью объединения всевозможных их пересечений будет:

$|\cup_{\geq 2}(A, B, C)| = |A \cap B| + |A \cap C| + |B \cap C| - 2 |A \cap B \cap C|$

То есть сначала складываются всевозможные попарные пересечения
Затем нужно дважды вычесть тройное пересечение,так как оно учитывается три раза( в пересечении AB,в пересечении AC и в пересечении BC)

[dgwuqtj]

Это я видел. И почему выполнено равенство? Вы видели вообще доказательства в этой области, скажем, той же формулы включений-исключений для двух или трёх множеств?

[Elijah96]

dgwuqtj в сообщении #1651401 писал(а):

И почему выполнено равенство?

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

dgwuqtj в сообщении #1651401 писал(а):

Вы видели вообще доказательства в этой области, скажем, той же формулы включений-исключений для двух или трёх множеств?

Доказательства я видел в той же википедии,но к сожаление понял только логику примера для двух множеств
А именно:

В случае для двух множеств A и B формула включений/исключений имеет вид:

$|A \cup B| = |A| + |B| - |A \cap B|$

В сумме $|A| + |B|$ элементы пересечения $A \cap B$ учтены дважды,и чтобы компенсировать это мы вычитаем $|A \cap B|$ из правой части формулы.

Пример из википедии

[Combat Zone]

Вот не хотелось влезать. Но влезу. А что такое $|A|$, как вы думаете? без слова мощность если, а то спрошу, что такое мощность.

[Elijah96]

Для трех множеств(пример из интернета):

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

В сумме $|A| + |B| + |C|$ элементы попарных пересечений учтены дважды(по аналогии со случаем для двух множеств),значит нужно вычесть все попарные пересечения,а именно $|A \cap B| - |A \cap C| - |B \cap C|$,но теперь остается не учтенной зона тройного пересечения $|A \cap B \cap C|$,значит ее нужно обратно учесть(то есть прибавить)

-- 25.08.2024, 16:24 --

Combat Zone в сообщении #1651405 писал(а):

А что такое $|A|$, как вы думаете? без слова мощность если, а то спрошу, что такое мощность.

$|A|$ Это мощность множества А.
Далее,Вы спросите что такое мощность?
Мощность множества это количество элементов в нем.
Пример:
A = {1,2,3,4,5,6}
Тогда мощность множества А равно 6(так как в множестве 6 элементов)

[dgwuqtj]

Более-менее строгое доказательство может выглядеть так. Пусть $A$ и $B$ — конечные множества (иначе формула вообще бессмысленная). Посмотрим, сколько раз каждый элемент $x$ был посчитан в правой и левой части. Если $x$ не входит ни в $A$, ни в $B$, то в обеих частях он посчитан 0 раз. Если он входит ровно в одно из множеств $A$ или $B$, то в левой части он посчитан 1 раз, и в правой тоже 1 раз, так как он даст вклад ровно в одно слагаемое $|A|$ или $|B|$ (и он не содержится в $A \cap B$). Наконец, если $x \in A \cap B$, то слева он посчитан 1 раз, а справа он будет учтён во всех трёх слагаемых, итого $1 + 1 - 1 = 1$. То есть тут перебор всех возможных случаев.

А размахиваний руками с "нужно обратно учесть" не надо.

[Combat Zone]

Elijah96 в сообщении #1651406 писал(а):

элементы попарных пересечений учтены дважды

... некоторые дважды, некоторые трижды.

-- 25.08.2024, 15:27 --

Elijah96 в сообщении #1651406 писал(а):

Мощность множества это количество элементов в нем.

Прекрасно, но почему нигде ни разу вы не вспомнили про количество элементов множеств? И говорили только про множества?

[Elijah96]

dgwuqtj в сообщении #1651407 писал(а):

А размахиваний руками с "нужно обратно учесть" не надо.

Да я и не размахивал руками,а просто привел примеры из интернета(переписал их оттуда)

-- 25.08.2024, 17:03 --

Elijah96 в сообщении #1651410 писал(а):

Прекрасно, но почему нигде ни разу вы не вспомнили про количество элементов множеств? И говорили только про множества?

В пересечениях множеств уже содержатся какие-либо элементы,разве нет?

-- 25.08.2024, 17:08 --

dgwuqtj в сообщении #1651407 писал(а):

Наконец, если $x \in A \cap B$, то слева он посчитан 1 раз, а справа он будет учтён во всех трёх слагаемых, итого $1 + 1 - 1 = 1$. То есть тут перебор всех возможных случаев.

Во всех трех слагаемых это в $|A|,|B|,|A \cap B|$ ?
И поэтому нужно вычесть $|A \cap B|$ чтобы элемент $x$ был посчитан только в $|A|,|B|$ ?

[Combat Zone]

Elijah96 в сообщении #1651410 писал(а):

В пересечениях множеств уже содержатся какие-либо элементы,разве нет?

Может быть да. Может, нет. И что?
Формула не о множествах, а о количестве элементов в них.

[dgwuqtj]

Elijah96 в сообщении #1651410 писал(а):

И поэтому нужно вычесть $|A \cap B|$ чтобы элемент $x$ был посчитан только в $|A|,|B|$ ?

Речь не о том, как придумать формулу, а о том, как её доказать. Вычитаемое уже написано, надо только формально проверить, что всё сходится. В принципе, из доказательства видно, что вычитаемое нужно и что $A \cap B$ в нём нельзя заменить на что-то другое.

[Elijah96]

Combat Zone в сообщении #1651416 писал(а):

Elijah96 в сообщении #1651410 писал(а):

В пересечениях множеств уже содержатся какие-либо элементы,разве нет?

Может быть да. Может, нет. И что?
Формула не о множествах, а о количестве элементов в них.

Пусть есть три множества A,B,C

$A = \lbrace 1,2,6,8 \rbrace , B = \lbrace1,9,6,7 \rbrace , C = \lbrace 1,5,8,9 \rbrace , A \cap B = \lbrace 1,6 \rbrace , A \cap C = \lbrace 1,8 \rbrace , B \cap C = \lbrace 1,9 \rbrace , A \cap B \cap C = \lbrace 1 \rbrace $

Берем формулу включений/исключений

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

То есть,сначала складываются множества по отдельности,затем вычитаются попарные пересечения,затем прибавляется тройное пересечение
Заменим множества на элементы в них

То есть:
$ \lbrace 1,2,6,8 \rbrace + \lbrace 1,9,6,7 \rbrace + \lbrace 1,5,8,9 \rbrace = \lbrace 1,1,1,2,6,6,5,7,8,8,9,9 \rbrace $

Отсюда видно что некоторые элементы учтены несколько раз(1,6,8,9)
Значит вычитаем попарные пересечения:

$ \lbrace 1,1,2,6,6,5,7,8,8,9 \rbrace - \lbrace 1,6 \rbrace - \lbrace 1,8 \rbrace - \lbrace 1,9 \rbrace = \lbrace 2,6,5,7,8,9 \rbrace $

Теперь осталась пустая зона тройного пересечения {1}
Добавляем ее:

$ \lbrace 2,6,5,7,8,9 \rbrace + \lbrace 1 \rbrace = \lbrace 1,2,5,6,7,8,9 \rbrace $

Получается:

$ \lbrace 1,2,5,6,7,8,9 \rbrace = \lbrace 1,2,6,8 \rbrace + \lbrace 1,9,6,7 \rbrace + \lbrace 1,5,8,9 \rbrace - \lbrace 1,6 \rbrace - \lbrace 1,8 \rbrace - \lbrace 1,9 \rbrace + \lbrace 1 \rbrace$

Формула включений/исключений работает на множества и на элементы в них

[dgwuqtj]

Elijah96 в сообщении #1651426 писал(а):

Формула включений/исключений работает на множества

Можно, пожалуйста, написать определение $A + B$?

[Elijah96]

dgwuqtj в сообщении #1651430 писал(а):

Elijah96 в сообщении #1651426 писал(а):

Формула включений/исключений работает на множества

Можно, пожалуйста, написать определение $A + B$?

Это объединение множеств A и B
То есть множество содержащее в себе все элементы исходных множеств A и B называется их объединением

-- 25.08.2024, 17:48 --

dgwuqtj в сообщении #1651417 писал(а):

Речь не о том, как придумать формулу, а о том, как её доказать.

Вот с доказательством у меня и проблема

[dgwuqtj]

Elijah96 в сообщении #1651426 писал(а):

То есть:
$ \lbrace 1,2,6,8 \rbrace + \lbrace 1,9,6,7 \rbrace + \lbrace 1,5,8,9 \rbrace = \lbrace 1,1,1,2,6,6,5,7,8,8,9,9 \rbrace $

И $\{1,1,1,2,6,6,5,7,8,8,9,9\} = \{1, 2, 5, 6, 7, 8, 9\}$. Если потом вычесть $\{1, 6\}$, $\{1, 8\}$ и $\{1, 9\}$, то получится $\{2, 5, 7\}$. То есть вы не умеете вычитать множества друг из друга (и видимо не знаете, что такое множества). Если что, $(A \cup B) \setminus B$ в общем случае не равно $A$.

[Elijah96]

dgwuqtj в сообщении #1651434 писал(а):

Elijah96 в сообщении #1651426 писал(а):

То есть:
$ \lbrace 1,2,6,8 \rbrace + \lbrace 1,9,6,7 \rbrace + \lbrace 1,5,8,9 \rbrace = \lbrace 1,1,1,2,6,6,5,7,8,8,9,9 \rbrace $

И $\{1,1,1,2,6,6,5,7,8,8,9,9\} = \{1, 2, 5, 6, 7, 8, 9\}$. Если потом вычесть $\{1, 6\}$, $\{1, 8\}$ и $\{1, 9\}$, то получится $\{2, 5, 7\}$. То есть вы не умеете вычитать множества друг из друга (и видимо не знаете, что такое множества). Если что, $(A \cup B) \setminus B$ в общем случае не равно $A$.

Почему $\{1,1,1,2,6,6,5,7,8,8,9,9\} = \{1, 2, 5, 6, 7, 8, 9\}$ ?

Складываются несколько множеств,и в этих множествах есть одинаковые элементы,разве они не будут учтены по несколько раз?

-- 25.08.2024, 18:14 --

Короче я вообще запутался что и как(