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

[Combat Zone]

Лево-право )

-- 25.08.2024, 20:13 --

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

Но в левой то части формулы элемент 6 посчитан трижды,или так и должно быть?

Лучше избегать таких фраз. Что такое посчитан трижды? Ну я так телепатически улавливаю, что на месте каждого из трех слагаемых будет стоять единица, потому что 6 входит во все три множества ) Да?

Плохо то, что это я что-то там понимаю, то есть это мои домыслы, а что при этом думаете вы - совершенно непонятно.

[Elijah96]

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

Но в левой то части формулы элемент 6 посчитан трижды,или так и должно быть?

Я уже исправил)
Там должно быть право)

-- 25.08.2024, 21:27 --

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

Ну я так телепатически улавливаю, что на месте каждого из трех слагаемых будет стоять единица, потому что 6 входит во все три множества ) Да?

Да,ведь элемент 6 входит в A,в B и в пересечение AB

-- 25.08.2024, 21:30 --

То есть нужно доказать что взяв любой элемент,он будет учтен ровно один раз?(либо 0 если он никуда не входит)

[Combat Zone]

Ну тогда так и надо писать. Потому что "посчитан трижды" в обиходе три.

Что еще вы не поняли? Тут понятно стало?

-- 25.08.2024, 20:33 --

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

То есть нужно доказать что взяв любой элемент,он будет учтен ровно один раз?(либо 0 если он никуда не входит)

А это нуждается в доказательстве? Любой элемент из любого множества учитывается один раз.
А мы доказываем равенство. И его и хотели доказать. То самое, вкл-искл.

[Elijah96]

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

Ну тогда так и надо писать. Потому что "посчитан трижды" в обиходе три.

Извините,не так написал(

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

Что еще вы не поняли? Тут понятно стало?

Да вроде все понял
Просто уточнил

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

То есть нужно доказать что взяв любой элемент,он будет учтен ровно один раз?(либо 0 если он никуда не входит)

[Combat Zone]

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

Просто уточнил

См.выше.

[Elijah96]

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

А мы доказываем равенство

Все
Дошло

В левой части формулы элементы всегда будут учитываться по одному разу(так как это объединение)
И в правой части формулы элементы тоже будут учитываться по одному разу(вне зависимости от того какой элемент и из какого множества рассматривается),так как это равенство

Возьму Вашу запись:
1=1+0-0 Здесь элемент $x$ принадлежит A но не принадлежит B и AB
1=0+1-0 Здесь элемент $x$ принадлежит B но не принадлежит A и AB
1=1+1-1 Здесь элемент $x$ принадлежит и A и B и AB
0=0+0-0 Здесь элемент $x$ не принадлежит ни A ни B ни AB

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

-- 25.08.2024, 21:54 --

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

Вообще давайте введём обозначение $\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|}.$$

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

А если получиться доказать по такой же логике как в формуле включений/исключений этот пример,то можно ли такое доказательство использовать если множеств n?

[Combat Zone]

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

Давайте я вам часть напишу, с остальным попробуйте сами разобраться.

Напомню, слева у нас стоит 1, если икс лежит в объединении, ноль иначе.
То есть если выписать все такие равенства для всех элементов из объединения и сложить их построчно, то слева получится сумма из единичек, равная количеству элементов объединения, то есть число $|A\cup B|$.
На месте первого слагаемого в правой части будет в сумме стоять столько же единичек, сколько элементов в множестве $A$, то есть $|A|$

Это понятно?
Если понятно, попробуйте продолжить для след. слагаемых.

Вот так прямо столбиком и складываем.

-- 25.08.2024, 21:04 --

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

А если получиться доказать по такой же логике как в формуле включений/исключений этот пример,то можно ли такое доказательство использовать если множеств n?

Погодите пока с этим. Ни к чему торопиться.

[Elijah96]

Попытаюсь вкратце

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

$A = \lbrace 1,2,6,8 \rbrace , B = \lbrace 1,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 $

Всевозможные объединения пересечений я обозначу $ \cup_i \cap_i $

А мощность всевозможных объединений пересечений я обозначу $| \cup_i \cap_i |$

(Не будьте строги,я не знаю как правильно обозначить это,равно как и многое другое)

Тогда $ \cup_i \cap_i $ = {1,6,8,9}

А $| \cup_i \cap_i |$ = 4

Проверяем по формуле:

$| \cup_i \cap_i | = |A \cap B| + |A \cap C| + |B \cap C| - 2 |A \cap B \cap C|$ = 2+2+2-(1*2)=4

Результаты совпали

Далее

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

Тогда $ \cup_i \cap_i $ = {1,3,6,7,8}

А $| \cup_i \cap_i |$ = 5

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

Проверяем по формуле:

$| \cup_i \cap_i | = |A \cap B| + |A \cap C| + |B \cap C| - 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|$ = 3+3+3+3+3+3-(2*2)-(2*2)-(2*2)-(2*2)+(3*1) = 5

Результаты совпали

[Combat Zone]

Вы, конечно, орел, столько писать ) я даже сейчас почитаю. Но все-таки вернитесь к моему предыдущему посту. Там было нужно другое. Попробуйте сделать.

[Elijah96]

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

Вы, конечно, орел, столько писать ) я даже сейчас почитаю. Но все-таки вернитесь к моему предыдущему посту. Там было нужно другое. Попробуйте сделать.

Я там накосячил,так что можете не читать,все равно не правильно получилось)

[Combat Zone]

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

= 5

Сомневаюсь я.

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

Я там накосячил,так что можете не читать,все равно не правильно получилось)

Поздно. )

[Elijah96]

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

Напомню, слева у нас стоит 1, если икс лежит в объединении, ноль иначе.

Это понятно,то есть если элемента икс нет в объединении,то будет 0

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

То есть если выписать все такие равенства для всех элементов из объединения и сложить их построчно, то слева получится сумма из единичек, равная количеству элементов объединения, то есть число $|A\cup B|$.

Вы имеете ввиду что если перебрать все элементы и выписать все неравенства?

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

На месте первого слагаемого в правой части будет в сумме стоять столько же единичек, сколько элементов в множестве $A$, то есть $|A|$

Это вообще не понятно

А на месте второго слагаемого будет стоять столько же единичек сколько $|B|$

[Combat Zone]

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

Это вообще не понятно

Ага. И значит, непонятно, при чем тут формула вкл-искл

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

То есть если выписать все такие равенства для всех элементов из объединения и сложить их построчно, то слева получится сумма из единичек, равная количеству элементов объединения, то есть число $|A\cup B|$.

А это понятно?

[Elijah96]

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

А это понятно?

Имеется ввиду что нужно найти все равенства для всех элементов из объединения?

-- 25.08.2024, 23:14 --

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

Ага. И значит, непонятно, при чем тут формула вкл-искл

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

На месте первого слагаемого в правой части будет в сумме стоять столько же единичек, сколько элементов в множестве $A$, то есть $|A|$

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

[Combat Zone]

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

Вы имеете ввиду что если перебрать все элементы и выписать все неравенства?

Все равенства для всех элементов, да.

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

Имеется ввиду что нужно найти все равенства для всех элементов из объединения?

Предположим, что вы их уже выписали. Сама по себе цитата моя понятна?