2014 dxdy logo

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

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


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


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



Начать новую тему Ответить на тему На страницу Пред.  1 ... 15, 16, 17, 18, 19, 20  След.
 
 Re: Формула включений/исключений
Сообщение04.09.2024, 20:40 
Заслуженный участник


07/08/23
1055
Теперь вы пишете сразу $0 = 2 a - 2 b$! Упростили вы правильно, впрочем. Можно ещё на 2 сократить и посмотреть, не очевидно ли это неравенство исходя из того, что известно про $a, b, c$.

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


09/01/24
274
dgwuqtj в сообщении #1653210 писал(а):
Теперь вы пишете сразу $0 = 2 a - 2 b$! Упростили вы правильно, впрочем. Можно ещё на 2 сократить и посмотреть, не очевидно ли это неравенство исходя из того, что известно про $a, b, c$.


Напишу так,надеюсь более правильно:

$a - b - b + c + a - c \geq 0 $

$a + a - b - b +  c - c \geq 0$

$2a - 2b \geq 0$

Если сократить на 2 то получиться

$a - b \geq 0$ что верно,так как |a - b| это положительное число

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


07/08/23
1055
Elijah96 в сообщении #1653231 писал(а):
Напишу так,надеюсь более правильно:

$a - b - b + c + a - c \geq 0 $

$a + a - b - b +  c - c \geq 0$

$2a - 2b \geq 0$

Наконец-то!
Elijah96 в сообщении #1653231 писал(а):
$a - b \geq 0$ что верно,так как |a - b| это положительное число

Нет, $|a - b|$ всегда неотрицательное, но не всегда $a - b \geq 0$. Вспоминайте, что известно про $a, b, c$.

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


09/01/24
274
dgwuqtj в сообщении #1653233 писал(а):
Elijah96 в сообщении #1653231 писал(а):
Напишу так,надеюсь более правильно:

$a - b - b + c + a - c \geq 0 $

$a + a - b - b +  c - c \geq 0$

$2a - 2b \geq 0$

Наконец-то!
Elijah96 в сообщении #1653231 писал(а):
$a - b \geq 0$ что верно,так как |a - b| это положительное число

Нет, $|a - b|$ всегда неотрицательное, но не всегда $a - b \geq 0$. Вспоминайте, что известно про $a, b, c$.


А,все,понял

Тогда $a - b \geq 0$ так как $a - b$ положительное

Так?

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


07/08/23
1055
Так, отлично. То есть вы разобрали один случай. Теперь, по идее, надо вообще выписать все случаи, которые имеет смысл разбирать, и понять, почему больше ничего быть не может. А потом уже для них всех доказывать.

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


09/01/24
274
А для случая когда:

$b - c$ положительное

$a - b$ отрицательное

$a - c$ отрицательно

Не будет ли такая же формула как и для $a - b$ ?

То есть $a - b$ поменяется на $b - c$

И тогда формула примет вид:

$b - c - a + b + a - c \geq 0 $

$b + b - c - c  + a - a \geq 0$

$2b - 2c \geq 0$

Верно ли это?

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


07/08/23
1055
Верно... Там вообще с точностью до симметрий случаев мало. Но это надо понимать, что такое симметрии. Давайте лучше поймём, какие случаи бывают в принципе. Вы вроде хотели понять, как проводить такие доказательства, для этого выписывать доказательство каждого случая не обязательно, в общих чертах достаточно.

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


09/01/24
274
А для случая когда:

$b - c$ положительное

$a - b$ положительное

$a - c$ отрицательно

Формула примет вид:

$a - b + b - c + a - c \geq 0 $

$a + a - b + b  - c - c \geq 0$

$2a - 2c \geq 0$

В данном случае $a - c = 0$

-- 04.09.2024, 22:20 --

dgwuqtj в сообщении #1653244 писал(а):
Верно... Там вообще с точностью до симметрий случаев мало. Но это надо понимать, что такое симметрии. Давайте лучше поймём, какие случаи бывают в принципе. Вы вроде хотели понять, как проводить такие доказательства, для этого выписывать доказательство каждого случая не обязательно, в общих чертах достаточно.


Мы сейчас идем к доказательству формулы В\И?

Или просто в общих чертах разбираем как доказывать такие неравенства?

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


07/08/23
1055
Elijah96 в сообщении #1653245 писал(а):
В данном случае $a - c = 0$

Почему $a - c = 0$? Это надо уметь доказывать, исходя из предпосылок.
Elijah96 в сообщении #1653245 писал(а):
Мы сейчас идем к доказательству формулы В\И?

Или просто в общих чертах разбираем как доказывать такие неравенства?

Просто разбираем, как доказывать. В конце концов, в формуле включений-исключений вообще нет неравенств и там только целые числа.

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


09/01/24
274
dgwuqtj в сообщении #1653248 писал(а):
Почему $a - c = 0$?


Я опять невнимателен

Если:

$b - c$ положительное

$a - b$ положительное

$a - c$ отрицательно

Формула примет вид:

$a - b + b - c + a - c \geq 0 $

$a + a - b + b  - c - c \geq 0$

$2a - 2c \geq 0$

В данном случае $a - c \geq 0$

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


07/08/23
1055
Elijah96 в сообщении #1653365 писал(а):
В данном случае $a - c \geq 0$

Это вам надо доказать. В предпосылках такого нет.

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


09/01/24
274
dgwuqtj в сообщении #1653248 писал(а):
В конце концов, в формуле включений-исключений вообще нет неравенств и там только целые числа.


А как тогда доказать формулу В\И?
Ведь тема изначально про нее была

И еще момент
Вы писали формулу

${|\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|$

То есть мощность объединения пересечений,начиная с двойных пересечений
То есть из суммы мощностей попарные пересечений вычитаются мощности тройных пересечений,затем прибавляется мощность четверных пересечений(и все эти пересечения с определенными коэффициентами)

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

Пример 1:
Есть 5 множеств $A,B,C,D,E$

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

Пример 2:

Есть 6 множеств $A,B,C,D,E,F$

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

В чем собственно вопрос
А вопрос в самих коэффициентах
Ведь для 5 и для 6 множеств будут разные коэффициенты перед пересечениями,и следовательно получить универсальную формулу нельзя(или я что-то не так опять посчитал)

Есть ли какая-то система или закономерность,при которой можно найти универсальную формулу В\И для мощности объединения пересечений,независимо от того с какого количество пересечений начинается формула
То есть:
Пусть есть n множеств,и нужно найти мощность объединения пересечений,начиная с m пересечений(с трех в моих примерах)
Или же в каждом случае будет отдельная формула?

-- 05.09.2024, 16:55 --

dgwuqtj в сообщении #1653370 писал(а):
Это вам надо доказать. В предпосылках такого нет.


Там в принципе не может быть $a - c \geq 0$

Так как из предположений что

$b - c$ положительное

$a - b$ положительное

$a - c$ отрицательно

А раз $a - c$ отрицательно ,то оно не может быть больше нуля

Верно?

-- 05.09.2024, 16:55 --

dgwuqtj в сообщении #1653370 писал(а):
Это вам надо доказать. В предпосылках такого нет.


Там в принципе не может быть $a - c \geq 0$

Так как из предположений что

$b - c$ положительное

$a - b$ положительное

$a - c$ отрицательно

А раз $a - c$ отрицательно ,то оно не может быть больше нуля и даже не может быть равно нулю,ведь отрицательные числа это -1,-2,-3,-...-n

А они меньше нуля

Верно?

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


07/08/23
1055
Elijah96 в сообщении #1653373 писал(а):
А как тогда доказать формулу В\И?
Ведь тема изначально про нее была

Там есть разные доказательства, лично мне нравится через характеристические функции. Для каждого множества $A$ заведём функцию $\chi_A$ на множестве всего вообще такую, что $\chi_A(x) = 1$ при $x \in A$ и $\chi_A(x) = 0$ иначе. Тогда $|A| = \sum_x \chi_A(x)$. Чтобы доказать, например, $|A \cup B| = |A| + |B| - |A \cap B|$, перепишем это в виде
$$\sum_x \chi_{A \cup B}(x) = \sum_x \chi_A(x) + \sum_x \chi_B(x) - \sum_x \chi_{A \cap B}(x),$$
и будет доказывать равенства $\chi_{A \cup B}(x) = \chi_A(x) + \chi_B(x) - \chi_{A \cap B}(x)$ для каждого $x$ по отдельности (сумма этих равенств и будет требуемой формулой). А вот такие равенства доказываются неким перебором случаев, для $n$ множеств ещё и с комбинаторикой.
Elijah96 в сообщении #1653373 писал(а):
Но что если нужно найти мощность объединения пересечений,начиная с тройных пересечений

Угадывать нужную формулу... Можно даже алгоритм придумать, как получать вообще все возможные формулы для мощностей булевых выражений множеств. А ещё можно вывести универсальную формулу для мощности объединения $n$ множеств, начиная с $k$-кратных пересечений, то есть для $|bigcup_{i_1 < \ldots < i_k} \bigcap_{j = 1}^k A_{i_j}|$. Там коэффициенты при $|A_{i_1} \cap \ldots \cap A_{i_l}|$ должны зависеть только от $k$ и $l$.
Elijah96 в сообщении #1653373 писал(а):
А раз $a - c$ отрицательно ,то оно не может быть больше нуля и даже не может быть равно нулю,ведь отрицательные числа это -1,-2,-3,-...-n

А они меньше нуля

Верно?

Ну... Верно, конечно, только вам всё равно надо доказать $a - c \geq 0$. Другими словами, надо получить противоречие, исходя из предпосылок.

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


09/01/24
274
dgwuqtj в сообщении #1653377 писал(а):
Там есть разные доказательства, лично мне нравится через характеристические функции. Для каждого множества $A$ заведём функцию $\chi_A$ на множестве всего вообще такую, что $\chi_A(x) = 1$ при $x \in A$ и $\chi_A(x) = 0$ иначе. Тогда $|A| = \sum_x \chi_A(x)$. Чтобы доказать, например, $|A \cup B| = |A| + |B| - |A \cap B|$, перепишем это в виде
$$\sum_x \chi_{A \cup B}(x) = \sum_x \chi_A(x) + \sum_x \chi_B(x) - \sum_x \chi_{A \cap B}(x),$$
и будет доказывать равенства $\chi_{A \cup B}(x) = \chi_A(x) + \chi_B(x) - \chi_{A \cap B}(x)$ для каждого $x$ по отдельности (сумма этих равенств и будет требуемой формулой). А вот такие равенства доказываются неким перебором случаев, для $n$ множеств ещё и с комбинаторикой.


То есть чтобы доказать формулу В\И нужно перебрать m случаев для n множеств,и основываясь на комбинаторике доказать саму формулу В\И?

dgwuqtj в сообщении #1653377 писал(а):
Угадывать нужную формулу... Можно даже алгоритм придумать, как получать вообще все возможные формулы для мощностей булевых выражений множеств. А ещё можно вывести универсальную формулу для мощности объединения $n$ множеств, начиная с $k$-кратных пересечений, то есть для $\bigcup_{i_1 < \ldots < i_k} \bigcap_{j = 1}^k A_{i_j}|$. Там коэффициенты при $|A_{i_1} \cap \ldots \cap A_{i_l}|$ должны зависеть только от $k$ и $l$.


То есть в принципе я "прав",в том что универсальной формулы нет?
Поскольку от того сколько есть множеств и сколько есть пересечений этих множеств,такие коэффициенты и будут?
(как я и говорил,для 5 и 6 множеств,будут свои коэффициенты)

dgwuqtj в сообщении #1653377 писал(а):
Ну... Верно, конечно, только вам всё равно надо доказать $a - c \geq 0$. Другими словами, надо получить противоречие, исходя из предпосылок.


Если:

$b - c$ положительное

$a - b$ положительное

$a - c$ отрицательно

Формула примет вид:

$a - b + b - c + a - c \geq 0 $

$a + a - b + b  - c - c \geq 0$

$2a - 2c \geq 0$

В данном случае $a - c \geq 0$

Если:

$b - c$ отрицательно

$a - b$ отрицательно

$a - c$ положительно

Формула примет вид:

$ - a - b - b - c + a - c \geq 0 $

$ - a +  a - b - b  - c - c \geq 0$

$2b - 2c \geq 0$

В данном случае $b - c \geq 0$

В первом случае $a - c$ отрицательно по предположению и по результатам вычислений

Во втором случае $a - c$ положительно по предположению,а вот по результатам вычислений является отрицательным(так как $b - c$ отрицательно),что в природе своей не может существовать,так как число не может быть одновременно и положительным и отрицательным

Можно ли это принять за противоречие?
Или у меня опять ошибки в расчетах?

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


07/08/23
1055
Elijah96 в сообщении #1653385 писал(а):
То есть чтобы доказать формулу В\И нужно перебрать m случаев для n множеств,и основываясь на комбинаторике доказать саму формулу В\И?

Все $m = 2^n$ случаев, да. Они разбираются одновременно, но надо же понимать, что это за случаи и почему они всё исчерпывают.
Elijah96 в сообщении #1653385 писал(а):
То есть в принципе я "прав",в том что универсальной формулы нет?
Поскольку от того сколько есть множеств и сколько есть пересечений этих множеств,такие коэффициенты и будут?
(как я и говорил,для 5 и 6 множеств,будут свои коэффициенты)

Ну будут там коэффициенты вида $l^k + \binom k l$, чем это не общая формула? Я не очень понял, что вы вообще хотите получить.
Elijah96 в сообщении #1653385 писал(а):
Можно ли это принять за противоречие?

У вас один набор предположений, $b - c > 0$, $a - b > 0$, $a - c < 0$. Всё. Из этого надо вывести противоречие. Для этого никаких дополнительных "если" не надо.

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

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



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

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


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

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