2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5 ... 20  След.
 
 Re: Формула включений/исключений
Сообщение25.08.2024, 15:51 


09/01/24
274
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)

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение25.08.2024, 15:54 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение25.08.2024, 16:08 


09/01/24
274
dgwuqtj в сообщении #1651401 писал(а):
И почему выполнено равенство?


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

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


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

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

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

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

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

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение25.08.2024, 16:13 


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

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение25.08.2024, 16:15 


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

$|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 элементов)

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение25.08.2024, 16:24 
Заслуженный участник


07/08/23
1055
Более-менее строгое доказательство может выглядеть так. Пусть $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$. То есть тут перебор всех возможных случаев.

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

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение25.08.2024, 16:25 


22/11/22
605
Elijah96 в сообщении #1651406 писал(а):
элементы попарных пересечений учтены дважды

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

-- 25.08.2024, 15:27 --

Elijah96 в сообщении #1651406 писал(а):
Мощность множества это количество элементов в нем.

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

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение25.08.2024, 16:33 


09/01/24
274
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|$ ?

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение25.08.2024, 17:09 


22/11/22
605
Elijah96 в сообщении #1651410 писал(а):
В пересечениях множеств уже содержатся какие-либо элементы,разве нет?

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

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение25.08.2024, 17:11 
Заслуженный участник


07/08/23
1055
Elijah96 в сообщении #1651410 писал(а):
И поэтому нужно вычесть $|A \cap B|$ чтобы элемент $x$ был посчитан только в $|A|,|B|$ ?

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

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение25.08.2024, 17:35 


09/01/24
274
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$

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

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение25.08.2024, 17:39 
Заслуженный участник


07/08/23
1055
Elijah96 в сообщении #1651426 писал(а):
Формула включений/исключений работает на множества

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

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение25.08.2024, 17:45 


09/01/24
274
dgwuqtj в сообщении #1651430 писал(а):
Elijah96 в сообщении #1651426 писал(а):
Формула включений/исключений работает на множества

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


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

-- 25.08.2024, 17:48 --

dgwuqtj в сообщении #1651417 писал(а):
Речь не о том, как придумать формулу, а о том, как её доказать.


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

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение25.08.2024, 17:53 
Заслуженный участник


07/08/23
1055
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$.

 Профиль  
                  
 
 Re: Формула включений/исключений
Сообщение25.08.2024, 18:11 


09/01/24
274
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 --

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 298 ]  На страницу Пред.  1, 2, 3, 4, 5 ... 20  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group