Множества и операции

Множество — это набор различимых объектов, взятый как единое целое. Всё. Никаких дополнительных требований: элементы не упорядочены, не повторяются, и это может быть что угодно — числа, векторы, функции, другие множества.

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

Принадлежность и включение

Два разных отношения, которые постоянно путают.

Принадлежность $x \in A$ — «объект $x$ является элементом $A$». Слева стоит элемент, справа множество.

Включение $A \subseteq B$ — «каждый элемент $A$ является элементом $B$». Слева и справа стоят множества.

Разница видна на примере. Пусть $A = \{1, 2\}$. Тогда:

• $1 \in A$ — верно, $1$ лежит в $A$
• $\{1\} \subseteq A$ — верно, множество из одной единицы вкладывается в $A$
• $\{1\} \in A$ — ложно: элементы $A$ — это числа, а не множества

В коде это разница между x in s и s1.issubset(s2).

Обозначение $\subset$ у разных авторов означает то $\subseteq$ (включение, возможно совпадающее), то строгое включение $\subsetneq$. Если различие важно, хорошие авторы пишут $\subseteq$ и $\subsetneq$ явно. Если видите голое $\subset$ — почти всегда имеется в виду $\subseteq$.

Способы задать множество

Перечислением: $\{2, 3, 5, 7\}$.

Через условие — это называется аксиома выделения, а выглядит как list comprehension:

$\{x \in \N : x \text{ простое и } x < 10\}$

Двоеточие (или вертикальная черта $\mid$) читается «такое, что». Слева — откуда берём кандидатов, справа — какому условию они должны удовлетворять. Один в один [x for x in naturals if is_prime(x) and x < 10].

Пустое множество обозначается $\emptyset$ или $\{\}$. Оно единственно и является подмножеством любого множества — включая само себя.

Операции

A ∪ BA ∩ BA \ BB \ AA △ B

Все операции над множествами — это ровно те же операции, что над булевыми условиями:

Множества	Условие на $x$	Логика
$A \cup B$	$x \in A$ или $x \in B$	or
$A \cap B$	$x \in A$ и $x \in B$	and
$A \setminus B$	$x \in A$ и $x \notin B$	and not
$\bar{A}$	$x \notin A$	not

Это не совпадение и не мнемоника: операции над множествами определены именно через логические связки. Отсюда же берётся то, что законы де Моргана выглядят одинаково для тех и других:

$\overline{A \cup B} = \bar{A} \cap \bar{B}, \qquad \overline{A \cap B} = \bar{A} \cup \bar{B}$

Про дополнение

Запись $\bar{A}$ (или $A^c$) имеет смысл только когда задан универсум $U$ — множество, внутри которого мы работаем. Дополнение — это $U \setminus A$. Без явного или подразумеваемого $U$ запись бессмысленна: «всё, что не в $A$» — это не множество, а источник парадоксов.

В вероятности универсум — это пространство элементарных исходов $\Omega$, и $\bar{A}$ означает «событие $A$ не произошло». В блоке 3 это пригодится сразу.

Мощность

$|A|$ — число элементов. Для конечных множеств это len(s). Для бесконечных всё интереснее, и к этому мы вернёмся в уроке про счётность.

Полезное тождество, которое стоит запомнить, — формула включения-исключения для двух множеств:

$|A \cup B| = |A| + |B| - |A \cap B|$

Логика простая: сложив мощности, мы посчитали пересечение дважды, поэтому один раз его нужно вычесть.

Чего здесь намеренно нет

Аксиоматики ZFC, парадокса Рассела, ординалов и кардинальной арифметики. Для чтения статей по ML нужен словарь, а не теория множеств как дисциплина.