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

[dgwuqtj]

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

[Elijah96]

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| это положительное число

[dgwuqtj]

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

[Elijah96]

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$ положительное

Так?

[dgwuqtj]

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

[Elijah96]

А для случая когда:

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

Верно ли это?

[dgwuqtj]

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

[Elijah96]

А для случая когда:

$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 писал(а):

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

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

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

[dgwuqtj]

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

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

Почему $a - c = 0$? Это надо уметь доказывать, исходя из предпосылок.

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

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

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

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

[Elijah96]

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$

[dgwuqtj]

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

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

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

[Elijah96]

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

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

Верно?

[dgwuqtj]

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$. Другими словами, надо получить противоречие, исходя из предпосылок.

[Elijah96]

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$ отрицательно),что в природе своей не может существовать,так как число не может быть одновременно и положительным и отрицательным

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

[dgwuqtj]

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$. Всё. Из этого надо вывести противоречие. Для этого никаких дополнительных "если" не надо.