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  След.

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



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

Сейчас этот форум просматривают: DariaRychenkova


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

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