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

[Elijah96]

Верны ли мои рассуждения или опять не туда думаю?

[dgwuqtj]

Не очень понятно, что такое эти "сценарии". Просто варианты того, где оказался $x$? Ну так их можно по-разному определять, можно сколь угодно много вариантов придумать. Например, так:
1. $x$ число и лежит в $A_1 \cap A_2 \cap \ldots$,
2. $x$ вектор и не лежит в $A_1 \cup A_2 \cup \ldots$,
3. $x$ векторное расслоение на $\mathbb R \mathrm P^\infty$ и лежит в $(A_2 \cap \ldots) \setminus A_1$,
и так далее.

Вообще вы же понимаете, как доказывать что-то перебором случаев? Например, неравенство вида $|a - b| + |b - c| \geq |a - c|$ для вещественных чисел, если про модуль знать только определение. Сначала выписываются условия на $x$, не обязательно даже в конечном числе (и не обязательно буквально на бумаге выписываются) такие, что любой $x$ из задачи удовлетворяет хотя бы одному из этих условий. Например, в неравенстве $x = a - b$ вещественное число, и условия надо писать такие, что каждое вещественное число удовлетворяет какому-то из них ($x \leq 0$ и $x \geq 0$ подойдут). В формуле включений-исключений $x$ вообще произвольный объект.

Далее, эти условия должны быть такими, чтобы при них всё упрощалось. Вы можете написать какие угодно неравенства на $a, b, c$, но если из этих неравенств не следует порядок между ними, все модули не раскрыть. Поэтому $a - b \leq 0$ и т.д. в условия добавлять полезно, а $a^2 + 16 b > 0$ — уже не очень. В формуле включений-исключений я предпочитаю те $2^n$ вариантов именно потому, что при каждом из них понятно, что происходит. А если написать просто условие типа $x \in A_1$, то непонятно, будет ли $x$ посчитан в $A_1 \cap A_2$, скажем.

Если всё это выполнено, то доказательство так и начинается: для любого $x$ выполнено одно из следующих условий: ... Для каждого из этих условий проверим, что что-то там выполняется: ...

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

[Elijah96]

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

Не очень понятно, что такое эти "сценарии". Просто варианты того, где оказался $x$?

Да,именно так
Я просто не так выразился

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

Вообще вы же понимаете, как доказывать что-то перебором случаев?

Я ни разу не доказывал ничего перебором,поэтому не знаю
И к сожаление так же не знаю как доказать в принципе формулу В/И
И видимо не узнаю

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

Ну и иногда ещё надо, чтобы эти условия были взаимно исключающими.

Из Вашей таблицы это можно проверить

1. $x \in A$, $x \in B$ и $x \in C$;
2. $x \in A$, $x \in B$ и $x \notin C$;
3. $x \in A$, $x \notin B$ и $x \in C$;
4. $x \in A$, $x \notin B$ и $x \notin C$;
5. $x \notin A$, $x \in B$ и $x \in C$;
6. $x \notin A$, $x \in B$ и $x \notin C$;
7. $x \notin A$, $x \notin B$ и $x \in C$;
8. $x \notin A$, $x \notin B$ и $x \notin C$.

Например вариант 1 и 3

Поскольку не может одновременно $x$ $\in$ $B$ и $x$ $\notin$ $B$

[dgwuqtj]

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

И к сожаление так же не знаю как доказать в принципе формулу В/И
И видимо не узнаю

Ну, вы можете её прочитать... Или ещё страниц за 10 обсуждений получится, кто знает.

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

Я ни разу не доказывал ничего перебором,поэтому не знаю

А вот попробуйте доказать $|a - b| + |b - c| \geq |a - c|$.

В школьной геометрии, кстати, огромное множество фактов надо доказывать перебором. Например, ассоциативность для сложения векторов (учитывая, что сумма векторов по-разному определяется когда они линейно независимы, когда один из них нулевой, когда они сонаправлены, и когда они противоположно направлены).

[Elijah96]

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

В формуле включений-исключений я предпочитаю те $2^n$ вариантов именно потому, что при каждом из них понятно, что происходит. А если написать просто условие типа $x \in A_1$, то непонятно, будет ли $x$ посчитан в $A_1 \cap A_2$, скажем.

Но ведь для n множеств все варианты нельзя перебрать
Или можно?

[dgwuqtj]

Можно! Особенность в том, что можно придумать некое общее рассуждение, которое доказывает все эти варианты одновременно.

[Elijah96]

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

можно придумать некое общее рассуждение

И на чем основывается это общее рассуждение?

-- 31.08.2024, 16:45 --

В $|a - b| + |b - c| \geq |a - c|$ вместо a,b,c нужно поставить обычные числа?

[dgwuqtj]

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

В $|a - b| + |b - c| \geq |a - c|$ вместо a,b,c нужно поставить обычные числа?

Вам надо доказать это неравенство для всех вещественных чисел $a$, $b$, $c$. То есть это уже числа, но произвольные.

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

И на чем основывается это общее рассуждение?

На комбинаторике, разумеется. Вам бы сначала научиться сами случаи выписывать аккуратно, а потом уже можно учиться работать с биномиальными коэффициентами и считать всякие суммы.

[Elijah96]

Пусть a,b,c вещественные числа

Докажем что $|a - b| + |b - c| \geq |a - c|$

Пусть:
a = -1
b = 1
c = 1

Тогда:

$ |-a - b| + |b - c| \geq |a - c| \Rightarrow |a + b| + |b - c| \geq |a - c| \Rightarrow |1 + 1| + |1 - 1| > |1 - 1| \Rightarrow |2| + |0| > |0| \Rightarrow |a - b| + |b - c| > |a - c| $

Правильная попытка?

[dgwuqtj]

Во-первых, вы доказываете неравенство не для всех чисел, а только для каких-то трёх конкретных. Во-вторых, я вашу цепочку импликаций не понял. Вы что, хотите доказать $|{-a} - b| + |b - c| \geq |a - c| \Rightarrow |a - b| + |b - c| > |a - c|$? Так надо равенство доказывать, а не импликацию...

Можете вообще вычислить обе части неравенства при $a = -1$, $b = 1$, $c = 1$?

[Elijah96]

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

Можете вообще вычислить обе части неравенства при $a = -1$, $b = 1$, $c = 1$?

Так я же писал

$|1 + 1| + |1 - 1| > |1 - 1| \Rightarrow |2| + |0| > |0|$

Или это не то?

[dgwuqtj]

Если это вы числа подставили в неравенство, то вы их подставили неверно. А вообще я имел в виду сами модули раскрыть, чтобы получить чисто арифметическое выражение, типа $17 + 7 > 10$. И лучше не пишите $\Rightarrow$, если не понимаете, что такое импликация. Можно просто писать последовательность формул, как в школе выкладки делают.

[Elijah96]

Да
Видимо зря я всех отвлек своей темой
Потому как до сих пор ничего не понял(

[Combat Zone]

Elijah96
Можно я вас еще раз спрошу: учебной литературой вы не пользуетесь по каким-то идейным соображениям?

[dgwuqtj]

Elijah96, вам надо было просто другую тему создавать, раз проблема не в этой формуле, а вообще в школьных методах доказательств. Никто же не начинает изучение математики с формулы включений-исключений, даже в книжках по дискретной математике перед ней куча материала. Какое у вас образование, если не секрет?