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

[Elijah96]

Здравствуйте,помогите пожалуйста с формулой включений/исключений

Имеется четыре множества
Тогда объединением четырех множеств будет:

$(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$

Вопрос в следующем:
Во всех тройных пересечениях ( $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$ ) оказывается посчитано четыре раза(по одному в каждом тройном пересечении),а в конце формулы четверное пересечение вычитается один раз,значит оно останется посчитанным ровно 3 раза,а должно быть посчитано 1 раз.

P.S.Знаю что формула включений\исключений правильная,но в чем моя ошибка?

[dgwuqtj]

Вы опять складываете и вычитаете множества... Так что формула не то что неправильная, она бессмысленная.

А вообще четверное пересечение ещё входит в двойные пересечения и в одинарные (т.е. в сами $A, B, C, D$).

[Elijah96]

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

А вообще четверное пересечение ещё входит в двойные пересечения и в одинарные (т.е. в сами $A, B, C, D$).

В одинарных пересечениях четверное пересечение складывается,в двойных вычитается,в тройных опять складывается(и складывается 4 раза),а вот вычитается потом один раз

[dgwuqtj]

$4 - 6 + 4 - 1 = 1$

[Elijah96]

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

$4 - 6 + 4 - 1 = 1$

Вы из одинарных множеств(их 4)вычли количество попарных пересечений(их 6),затем прибавили количество тройных пересечений(их 4)а затем вычли количество четверных пересечений(их одно)
В таком случае получается правильный результат

Но вопрос в другом
После сложениях тройных пересечений,зона четверного пересечения посчитана 4 раза,а вычитается один раз
На это вообще не стоит обращать внимание и следовать логике которую Вы привели?(то есть считать количество одинарных множеств,двойных,тройных...и т.д. пересечений,а затем считать все по формуле включений/исключений)

[dgwuqtj]

А для трёх множеств вы эту формулу понимаете? И вообще умеете её правильно записывать?

[Elijah96]

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

А для трёх множеств вы эту формулу понимаете?

Для трех множеств как раз таки все более понятно
После сложения одинарных множеств,вычитаются попарные,после вычитания попарных,зона тройного пересечения оказывается пуста,и поэтому прибавляется тройное пересечение

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

И вообще умеете её правильно записывать?

В интернете такое написание формулы:

$ \mid A \cup B \cup C \cup D \mid = \mid A \mid + \mid B \mid + \mid C \mid + \mid D \mid - \mid A \cap B \mid - \mid A \cap C \mid - \mid A \cap D \mid - \mid B \cap C \mid - \mid B \cap D \mid - \mid C \cap D \mid + \mid A \cap B \cap C \mid + \mid A \cap B \cap D \mid + \mid A \cap C \cap D \mid + \mid B \cap C \cap D \mid - \mid A \cap B \cap C \cap D \mid $

[dgwuqtj]

Ну и теперь посмотрите, сколько каждый элемент $x \in A \cap B \cap C \cap D$ будет посчитан в левой и в правой части.

[Elijah96]

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

Ну и теперь посмотрите, сколько каждый элемент $x \in A \cap B \cap C \cap D$ будет посчитан в левой и в правой части.

Погодите,я попробую:

Предположим что в $ \mid A \cap B \cap C \cap D \mid $ есть три элемента(1,2,3)

Тогда эти три элемента будут посчитаны:
В множестве А один раз
В множестве В один раз
В множестве С один раз
В множестве D один раз
(Так как эти элементы(1,2,3)есть в каждом множестве(А,B,C,D))
А раз они есть в каждом множестве(A,B,C,D)по отдельности,то они есть и во всех пересечениях этих множеств,и в каждом пересечении этих множеств,эти элементы будут посчитаны по одному разу(сказал что сам не понял,надеюсь Вы поймете что я написал)

И получается следующее:
1+1+1+1-1-1-1-1-1-1+1+1+1+1-1 = 4-6+4-1=1
(Единица это количество раз,сколько посчитаны элементы 1,2,3 в множествах)
Первые четыре единицы это одинарные множества
Вторые шесть единиц это попарные пересечения
Третьи четыре единицы это тройные пересечения
Четвертая единица это четверное пересечение

(Я видимо опять не туда думаю?)

[lel0lel]

Есть такой метод, называется математическая индукция. Может помочь.

[dgwuqtj]

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

А раз они есть в каждом множестве(A,B,C,D)по отдельности,то они есть и во всех пересечениях этих множеств,и в каждом пересечении этих множеств,эти элементы будут посчитаны по одному разу(сказал что сам не понял,надеюсь Вы поймете что я написал)

Вот вам бы ещё понять, что вы написали, а так всё правильно.

[Elijah96]

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

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

А раз они есть в каждом множестве(A,B,C,D)по отдельности,то они есть и во всех пересечениях этих множеств,и в каждом пересечении этих множеств,эти элементы будут посчитаны по одному разу(сказал что сам не понял,надеюсь Вы поймете что я написал)

Вот вам бы ещё понять, что вы написали, а так всё правильно.

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

И еще вопрос
Можно ли найти мощность объединения всех пересечений множеств по такое же логике как на примере выше(посчитать количество того сколько раз элемент $x$ учтен в правой части)

Например верна ли формула для мощности объединения всех пересечений множеств?

$ \mid A \cap B \cup A \cap C \cup A \cap D \cup B\cap C \cup B \cap D \cup C \cap D \cup A \cap B \cap C \cup A \cap B \cap D \cup A \cap C \cap D \cup B \cap C \cap D \cup A \cap B \cap C \cap D \mid = \mid A \cap B \mid + \mid A \cap C \mid + \mid A \cap D \mid + \mid B \cap C \mid + \mid B \cap D \mid + \mid C \cap D \mid - \mid A \cap B \cap C \mid - \mid A \cap B \cap D \mid - \mid A \cap C \cap D \mid - \mid B \cap C \cap D \mid + \mid A \cap B \cap C \cap D\mid $

P.S.Я не знаю как обозначить мощность объединения всех пересечений множеств,поэтому обозначил ее так громоздко $ \mid A \cap B \cup A \cap C \cup A \cap D \cup B\cap C \cup B \cap D \cup C \cap D \cup A \cap B \cap C \cup A \cap B \cap D \cup A \cap C \cap D \cup B \cap C \cap D \cup A \cap B \cap C \cap D \mid $

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

Верна ли мысль?

И верно ли что если из суммы мощностей множеств A,B,C,D вычесть мощность объединения всех пересечений множеств,то получится мощность объединения множеств A,B,C,D?

То есть(на примере множеств выше):
6-4+1=3(это,если можно так выразиться,мощность объединения всех пересечений множеств)
Далее из суммы мощностей множеств A,B,C,D вычитаем мощность объединения всех пересечений множеств,

Выходит:
4-3=1
Будет ли это мощностью объединения множеств A,B,C,D?

[dgwuqtj]

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

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

Нет, вы так всегда будете получать 1.

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

Можно ли найти мощность объединения всех пересечений множеств по такое же логике как на примере выше

Наверное, можно, но я вам формулу не назову.

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

Верна ли мысль?

Нет, проверьте сами на простом примере типа $A = B = C = D = \{x\}$.

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

И верно ли что если из суммы мощностей множеств A,B,C,D вычесть мощность объединения всех пересечений множеств,то получится мощность объединения множеств A,B,C,D?

Нет, тот же контрпример.

-- 25.08.2024, 13:20 --

Вообще давайте введём обозначение $\cup_{\geq 2}(A_1, \ldots, A_n) = \bigcup_{1 \leq i < j \leq n} (A_i \cap A_j)$, то есть множество тех элементов, которые входят в хотя бы два множества из $A_1, \ldots, A_n$ (вам вроде именно это надо). Можно руками получить такие формулы: $|\cup_{\geq 2}(A)| = 0$, $|\cup_{\geq 2}(A, B)| = |A \cap B|$, $|\cup_{\geq 2}(A, B, C)| = |A \cap B| + |A \cap C| + |B \cap C| - 2 |A \cap B \cap C|$,

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

А дальше можете угадать формулу и попробовать её доказать...

[Elijah96]

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

А дальше можете угадать формулу и попробовать её доказать...

Я могу попытаться доказать формулу для трех множеств,потому что для четырех у меня не сходиться

Например есть три множества 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]

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