Математика начинается с теории множеств. А теория множеств начинается с одного вопроса: принадлежит ли объект выбранному множеству. Именно отсюда берут начало такие простые вещи, как равенство, включение и все основные операции. Поэтому чтобы понять математику, нужно заговорить на языке теории множеств.
Сквозной пример в этой статье будет максимально простым: возьмём множества $A = \{1, 2, 3\}$ и $B = \{3, 4\}$. Числа здесь выбраны только для иллюстрации определений. Никакой тайной жизни у числа 3 нет, хотя ему и придётся состоять сразу в двух множествах.
Основа основ: $\in$ и $=$
Как обозначают множества
Множества обозначают большими латинскими буквами: $A$, $B$ и так далее. Элементы множеств обозначают малыми буквами: $a$, $b$ и так далее.
Символ принадлежности $\in$
Объект может быть в множестве, то есть быть его элементом, а может не быть. Если некоторый абстрактный объект $a$ является элементом множества $A$, пишут $a \in A$, а если не является — $a \notin A$.
В примере $1 \in A$, $3 \in A$ и одновременно $3 \in B$, а $4 \notin A$. Запись не объясняет природу объекта — она только фиксирует его положение относительно множества.
Символ равенства $=$
Множества $A$ и $B$ равны, если состоят из одних и тех же элементов; тогда пишут $A = B$.
Пустое множество $\varnothing$
Множество без единого элемента называют пустым и обозначают $\varnothing$. Это полноценное множество с очень короткой ведомостью: здесь ничего нет.
Символ подмножества $\subset$
Если каждый элемент $A$ принадлежит $B$, то $A$ называют подмножеством $B$ и пишут $A \subset B$. То же отношение можно прочитать с другой стороны: $B$ является надмножеством $A$, то есть $B \supset A$.
Критерий равенства множеств
То есть два множества равны тогда и только тогда, когда каждое из них является подмножеством другого.
Разберём направление от включений к равенству. Из $A \subset B$ следует, что каждый элемент $A$ есть в $B$; из $B \subset A$ — что каждый элемент $B$ есть в $A$. Значит, множества содержат одни и те же элементы, поэтому $A = B$.
Объединение, пересечение и разность множеств
Три операции над двумя множествами
Объединение собирает элементы, которые принадлежат хотя бы одному из двух множеств:
Пересечение оставляет элементы, которые одновременно принадлежат обоим множествам:
Разность оставляет элементы первого множества, которые не принадлежат второму:
В примере получаем $A \cup B = \{1, 2, 3, 4\}$, $A \cap B = \{3\}$ и $A \setminus B = \{1, 2\}$.
Разложение объединения
Формула делит объединение на три части: элементы только из $A$, элементы только из $B$ и общие элементы. Чтобы доказать равенство множеств, проверим оба включения.
Доказательство разложения
Докажем это используя критерий равенства множеств.
Любой элемент $A \setminus B$ принадлежит $A$, любой элемент $B \setminus A$ принадлежит $B$, а любой элемент $A \cap B$ принадлежит и $A$, и $B$. Поэтому каждая из трёх частей лежит в $A \cup B$.
Теперь возьмём $x \in A \cup B$. Если $x$ принадлежит обоим множествам, то $x \in A \cap B$. Если он принадлежит $A$, но не $B$, то $x \in A \setminus B$. Если он принадлежит $B$, но не $A$, то $x \in B \setminus A$.
Каждое множество включено в другое, а значит, равенство доказано.
Существование и всеобщность
Объединение системы множеств
Пусть множества $A_\alpha$ образуют систему с индексами $\alpha \in \mathfrak{U}$. Элемент попадает в объединение системы, если найдётся хотя бы один индекс, для которого он принадлежит соответствующему множеству:
Ключевое слово здесь — «квантор существования $\exists$». Всего одного подходящего множества достаточно, чтобы элемент оказался в общем объединении.
Пересечение системы множеств
Здесь ключевое слово — «квантор всеобщности $\forall$». Элемент должен принадлежать всем множествам системы:
Поэтому объединение спрашивает: «нашёлся ли хотя бы один свидетель?», а пересечение — «подтвердили ли все?». В первом случае достаточно одного голоса, во втором заседание должно быть единогласным.
Дополнение объединения и пересечения
Зафиксируем множество $X$ и систему множеств $A_\alpha \subset X$ для всех $\alpha \in \mathfrak{U}$. Разность $X \setminus A_\alpha$ содержит элементы $X$, которых нет в $A_\alpha$. Теперь отрицание условия принадлежности меняет квантор и вместе с ним операцию.
Дополнение объединения
Проверим произвольный элемент. Условие $x \in X \setminus \underset{\alpha \in \mathfrak{U}}{\cup} A_{\alpha}$ означает, что $x \in X$ и $x$ не принадлежит объединению. Значит, для каждого $\alpha$ верно $x \notin A_\alpha$, то есть для каждого $\alpha$ выполняется $x \in X \setminus A_\alpha$. Это и есть принадлежность пересечению дополнений.
Дополнение пересечения
Здесь условие $x \notin \underset{\alpha \in \mathfrak{U}}{\cap} A_\alpha$ означает, что найдётся индекс $\alpha$, для которого $x \notin A_\alpha$. Следовательно, для этого индекса $x \in X \setminus A_\alpha$, а значит, $x$ принадлежит объединению дополнений.
В обеих формулах меняются сразу две детали: «существует» превращается во «для всех» или наоборот, а объединение меняется на пересечение.
Дистрибутивность объединения и пересечения
Два дистрибутивных закона
В первом законе элемент должен принадлежать $C$ и хотя бы одному из множеств $A$ или $B$. Поэтому он попадает либо в $A \cap C$, либо в $B \cap C$. Во втором законе элемент принадлежит одновременно $A$ и $B$ либо принадлежит $C$; это равносильно одновременной принадлежности $A \cup C$ и $B \cup C$.
Один способ читать все доказательства
Во всех разобранных леммах работает один маршрут: берём произвольный $x$, раскрываем определения операций, преобразуем условия принадлежности и собираем их обратно в нужное множество. Для равенства проверяем оба включения или строим цепочку равносильных условий.