Мощность множества

[talmid]

Ради интереса решил порешать задачки по основам теории множеств. В одной из задач нужно доказать, что $|X \cup Y|= |X| + |Y| - |X \cap Y|$. Я понимаю эту запись, тут все просто. Но как это нужно доказывать не знаю. Помогите, пожалуйста!

[Gagarin1968]

talmid
Диаграммы Венна Вам в помощь.

[talmid]

Про диаграммы Венна я знаю. Но если я нарисую, то это будет доказательством мощности объединения? Я думал, что диаграммы используются только для наглядных примеров операций с множествами, а не их характеристик. То есть из областей диаграмм Венна видно, что $X \cup Y = X \setminus Y + Y \setminus X + X \cap Y$.

[ИСН]

А ведь нет никакой операции "+" на множествах. Это если хотите совсем уж строго.

[ihq.pl]

ИСН в сообщении #1399911 писал(а):

ведь нет никакой операции "+" на множествах

Почему, в теорвере $+$ означает объединение непересекающихся множеств и отличается от $\cup$

[ИСН]

Если так, то пожалуйста. (А что сделает эта операция, если ей подсунуть пересекающиеся множества? Рухнет с ошибкой 500?)

[ihq.pl]

ну если подсунуть такое компьютеру, то наверно рухнет. Но в теории вероятности $+$ оч даже оправдывает себя, так как вероятность $p(A\cup B) = p(A)+p(B)$ если $A\cap B = \emptyset$

[ИСН]

Ну там-то да, конечно. Но топикстартер ещё не там.

[arseniiv]

ihq.pl
Всё-таки это не совсем операция, это часть записи отношения «(1) раскладывается в дизъюнктное объединение множеств (2)». Подобные такой записи действительно удобны, но это не простые выражения с какой-то особенной операцией, а метафоры как например запись $f = o(g)$.

[eugensk]

talmid

По индукции доказать

$$\text{Если }X = \bigsqcup\limits_{i=1}^n X_i \text{ (т.е. } X = \bigcup\limits_{i=1}^n X_i } \text{, причем } i \ne j \implies X_i \cap X_j = \varnothing \text{ ), то } |X| = \sum\limits_{i=1}^n |X_i|$$

Потом заметить, что

$$X = (X \backslash Y) \sqcup (X \cap Y), Y = (Y \backslash X) \sqcup (X \cap Y), X\cup Y = (X \backslash Y) \sqcup (Y \backslash X) \sqcup (X \cap Y) $$

Получается, что

$$|X| = |X \backslash Y| + |X \cap Y|, |Y| = |Y \backslash X| + |X \cap Y|, |X\cup Y| = |X \backslash Y| + |Y \backslash X| + |X \cap Y| $$

Из последнего следует то, что искали (если сложить $|X|$ и $|Y|$ и сравнить с $|X\cup Y|$)

[Someone]

talmid в сообщении #1399903 писал(а):

Ради интереса решил порешать задачки по основам теории множеств. В одной из задач нужно доказать, что $|X \cup Y|= |X| + |Y| - |X \cap Y|$. Я понимаю эту запись, тут все просто. Но как это нужно доказывать не знаю. Помогите, пожалуйста!

Перенесите член с "минусом" в левую часть и посчитайте элементы.

Более формальный способ состоит в том, чтобы представить $X\cup Y$ как объединение двух дизъюнктных множеств, в которых количество элементов известно или легко вычисляется.

eugensk, не советуйте сложных методов для решения простой задачи.

[eugensk]

Someone

Полагаю, простые задачи самое то, чтобы обкатывать надежные методы, а не диаграммы рисовать :)
(Это ваше "более формальное" решение, конечно же, я просто потренировался с формулами на форуме).

[Connector]

В задаче, очевидно, речь идёт о конечных множествах — для бесконечных операция вычитания разностей не определена. Для доказательства можно также использовать понятие индикаторной функции.

(Оффтоп)

В теории вероятностей, которую здесь уже вспоминали, вероятность события — это матожидание его индикатора, и там аналогичные теоремы тоже возможно доказывать через индикаторы.

[bot]

eugensk в сообщении #1399925 писал(а):

Полагаю, простые задачи самое то, чтобы обкатывать надежные методы, а не диаграммы рисовать

Диаграмма не доказательство, а руководство к действию:

Someone в сообщении #1399924 писал(а):

Более формальный способ состоит ...