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

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

Я не буду строить абстрактную теорию. Цель этого материала не в этом. Но мне в любом случае придётся перечислить все основные понятия множеств, все операции над множествами, функции и остальные фундаментальные вещи. Не потому, что я буду строить абстрактную теорию. А потому что обозначения, понятия и инструменты, с которыми мы сейчас познакомимся, будут далее встречаться абсолютно везде. Вы не встретите ни одного абзаца (кроме, может, мотивирующих), где не будет прямых или косвенных упоминаний этого инструментария.

Множества

Начнём мы, как полагается, с определения множеств и операций над ними.

Множество и его элементы

Множество — это набор каких-то объектов, базовое неопределяемое понятие в математике. Множества состоят из элементов. Если $x$ является элементом множества $S$ , то пишут $x\in S$ или $S\ni x$ . Обратное этому утверждение, если элемент $x$ не является элементом множества $S$ , обозначают $x\notin S$ или $S\notni x$ .

\begin{align*} x \in S = S \ni x &\defequiv \text{элемент}~ x ~\text{содержится в множестве}~ S \\ x \notin S = S \notni x &\defequiv \text{элемент}~ x ~\text{не содержится в множестве}~ S \end{align*}

Один из способов задать множество — просто перечислить все его элементы. Например, множество

X = \big\{ 1, 2, \{7, 3\}, \text{кастрюля} \big\}

Обратите внимание: это множество состоит из $4$ элементов: числа $1$ , числа $2$ , множества $\{7, 3\}$ и кастрюли. Обозначения коварны, путаться в них нельзя. Вот например страшное множество $\bigl\{ \bigl\{ \{\{8\}\} \bigr\} \bigr\}$ состоит из одного элемента, и это элемент не $8$ , а множество $\bigl\{ \{\{8\}\} \bigr\}$ . В общем, будьте внимательны.

Множество, не содержащее ни одного элемента, называется пустым и записывается как $\nothing$ .

Подмножества

Множество $A$ называется подмножеством множества $B$ , если каждый элемент множества $A$ является элементом множества $B$ . Этот факт записывается как $A\subset B$ .

A \subset B \defequiv \forall\, x \in A \? x \in B

Например, $\{ 1, 3, 6 \} \subset \{1, 2, 3, 4, 5, 6, 7\}$ . Также $\{\text{четные числа}\} \subset \NN$ .

Пустое множество является подмножеством любого множества. Иногда об это можно сильно споткнуться.

Подмножество $A$ множества $B$ можно задать, выделив свойство, которым обладают все его элементы

A = \{x \in B \colon x ~\text{обладает свойством}\}

Например, в множестве $\NN$ я могу выделить подмножество всех квадратов $\{n \in \NN : \exists\, a \in \NN \? a^2 = n \}$ .

Совпадение всех элементов множеств $A$ и $B$ называется равенством и записывается $A = B$ .

A \subset B \land B \subset A \iff A = B

Пишут $A \subsetneq B$ , если $A \subset B$ и одновременно $A \neq B$ , то есть $A$ строго внутри $B$ . Такое подмножество называется собственным. Если надо подчеркнуть, что множества могут быть равны, то пишут $A \subseteq B$ .

Я буду везде, где это не принципиально, писать $A\subset B$ . Но там, где это важно, например где суммирование идёт по всем подмножествам, или например где мы считаем количество подмножеств, обязательно нужно указывать, является ли подмножество собственным. Там, где это необходимо, я буду явно указывать, включается ли само множество.

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

Мощность множества $S$ — количество элементов в множестве $S$ . Обозначается $|S|$ .

Операции над множествами

Объединение и пересечение

Объединением множеств $A$ и $B$ называется множество $A \union B \defeq \{ x : x \in A \lor x \in B \}$

Пересечением множеств $A$ и $B$ называется множество $A \sect B \defeq \{ x : x \in A \land x \in B \}$

Обе эти операции являются ассоциативными и коммутативными, то есть

A \union B = B \union A \quad \text{и} \quad (A \union B) \union C = A \union (B \union C) \\[0.5em] A \sect B = B \sect A \quad \text{и} \quad (A \sect B) \sect C = A \sect (B \sect C)

Пересечение дистрибутивно по объединению и наоборот

A \union (B \sect C) = (A \union B) \sect (A \union C) \quad \text{и} \quad A \sect (B \union C) = (A \sect B) \union (A \sect C)

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

Разность

Разностью множеств $A$ и $B$ называется множество

A \without B \defeq \{x : x \in A \land x \notin B \}

В рамках какой-то модели или какой-то конкретной задачи можно определить множество, которое содержит вообще все возможные элементы. Это множество называется универсумом (universum) или универсальным множеством и обозначается $\UUU$ .

Имея универсум, мы можем для каждого множества $X$ определить множество элементов, которые не содержатся в множестве $X$ . Такое множество называется дополнением.

Дополнение

Дополнением множества $X$ до универсума $\UUU$ называется множество

X^\complement \defeq \UUU \without X = \{ x : x \notin X \}

Законы де Моргана

Для любых множеств $A$ и $B$

(A \sect B)^\complement = A^\complement \union B^\complement \quad\text{и}\quad (A \union B)^\complement = A^\complement \sect B^\complement

Аналогично, для любого семейства множеств $A_j$ при индексах $j \in I$

\biggl( \bigsect_{j \;\! \in \;\! I} A_j \biggr)^\complement = \bigunion_{j \;\! \in \;\! I} (A_j)^\complement \quad\text{и}\quad \biggl( \bigunion_{j \;\! \in \;\! I} A_j \biggr)^\complement = \bigsect_{j \;\! \in \;\! I} (A_j)^\complement

Доказательство. Поскольку законы де Моргана в оригинале формулируются для логических высказываний, аналогичные утверждения для множеств удобно доказывать через логику.

\align{ x \in \biggl( \bigunion_{j \;\! \in \;\! I} A_j \biggr)^\complement &\iff x \notin \bigunion_{j \;\! \in \;\! I} A_j \iff \nexists\, j \in I \? x \in A_j \iff \forall\, j \in I \? x \notin A_j \\ &\iff \forall\, j \in I \? x \in (A_j)^\complement \iff x \in \bigsect_{j \;\! \in \;\! I} (A_j)^\complement }

Аналогично доказывается и второй закон де Моргана.

Симметрическая разность

Симметрической разностью множеств $A$ и $B$ называется множество

A \symdiff B \defeq \{ x : x \in A \land x \in B \land x \notin A \sect B \} = \{ x : x \in A \xor x \in B \}

Количество элементов в объединении множеств можно вычислить, зная количество элементов в каждом из этих множеств и количество элементов во всех возможных пересечениях этих множеств

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

Пусть $A_1, A_2, \dotsc, A_n \subset X$ . Мощность объединения всех этих множеств можно вычислить по страшной формуле

\left|\, \bigunion_{i \;\! = \;\! 1}^n A_i \,\right| = \sum\limits_{\nothing \;\! \neq \;\! I \subseteq \{1, ..., n\}} (-1)^{|I|+1} \cdot \left|\, \bigsect_{i \;\! \in \;\! I} A_i \,\right|

Более гуманный, но не менее страшный вариант

\left|\, \bigunion_{i \;\! = \;\! 1}^n A_i \,\right| = \sum\limits_{k=1}^n \, (-1)^{k+1} \cdot \sum\limits_{1 \;\! \le \;\! i_1 \lt i_2 \lt \dotsb \lt i_k \le n} |A_{i_1} \sect A_{i_2} \sect \dotsb \sect A_{i_k}|

Для двух множеств формула принимает очень даже милый вид $|A \union B| = |A| + |B| - |A \sect B|$

Да и для трех множеств тоже ничего

|A \union B \union C| = |A| + |B| + |C| - |A\sect B| - |B\sect C| - |C\sect A| + |A\sect B \sect C|

Доказать эту формулу можно посчитав количество вхождений элемента $x \in \bigsect_{j \;\! = \;\! 1}^m A_{i_j}$ в правую часть формулы.

k = (-1)^{m+1} \cdot \binom{m}{m} + (-1)^m \cdot \binom{m}{m-1} + \dotsb + (-1)^2 \cdot \binom{m}{1} = \binom{m}{0} - \sum\limits_{i=0}^m\, (-1)^i \cdot \binom{m}{i} = 1

Отображение

Пусть у нас есть два множества $X$ и $Y$ . Обозначим за $f$ какое-то правило, по которому каждому элементу из множества $X$ ставится в соответствие какой-то один элемент множества $Y$ . Это правило $f$ называется функцией или отображением (map). Записывается

f \colon X \to Y \qquad \text{или} \qquad X \xrightarrow{f} Y

Множество $X$ называется областью определения функции $f$ , обозначается $\dom f$ (domain).

Множество $Y$ называется областью назначения функции $f$ , обозначается $\codom f$ (codomain).

Есть еще один, чуть более фундаментальный и запутанный подход к определению отображений. Если элементу $x \in X$ ставится в соответствие элемент $y \in Y$ , то будем интерпретировать это «соответствие» как пару $(x, y)$ .

Тогда отображение $f \colon X \to Y$ задается просто каким-то подмножеством $f \subset X \times Y$ . Это подмножество $f$ должно удовлетворять свойству функциональности. Для любого $x \in X$ существует ровно один $y \in Y$ такой, что $(x, y) \in f$ .

Термин «область значений»

В русской литературе есть термин «область значений», значение которого сильно зависит от контекста. В каких-то случаях область значений $f$ значит $\codom f$ , а в каких-то $\im f$ .

Во избежание путаницы я буду использовать английские термины codomain of the function и image of the function.

Кстати, название «область назначения» я выдумал сам.

График отображения

График отображения $f \colon X \times Y$ — подмножество $X \times Y$

\graph f \defeq \big\{ (x, y) \in X \times Y \colon y = f(x) \big\}

Вот пример отображения $\{\text{A}, \text{B}, \text{C}\} \to \{1, 2\}$ и его график $\big\{ (\text{A}, 1), (\text{B}, 2), (\text{C}, 1) \big\}$

Пример отображения из множества {A, B, C} в множество {1, 2}

Образ множества

Образ множества $A \subset \dom f$ при отображении $f$ — множество образов его элементов. Обозначается

f[A] \defeq \big\{ f(x) \enspace \forall\, x \in A \big\}

Например, если $g$ — отображение из предыдущего примера, то $g\big[\{\text{A}, \text{C}\}\big] = \{1\}$ .

Область значений отображения $f$ — образ области определения $f$ . Обозначается $\im f \defeq f\big[\dom f\big]$ .

Композиция двух отображений $f \colon X \to Y$ и $g \colon Y \to Z$ — отображение $g \compose f \colon X \to Z$ , в котором $x \mapsto g\big(f(x)\big)$ . Композиция отображений является ассоциативной операцией, то есть $(f \compose g) \compose h = f \compose (g \compose h)$ .

Инъективное отображение

Отображение $f \colon X \to Y$ называется инъективным или вложением, если разные элементы $X$ переходят в разные элементы $Y$ . Формально, $f(x) = f(y) \Rightarrow x = y$ , или $x != y \Rightarrow f(x) = f(y)$ . Записывается

f \colon X \injto Y \qquad \text{или} \qquad X \xinjto{f} Y

Сюръективное отображение

Отображение $f \colon X \to Y$ называется сюръективным, если все элементы $Y$ являются образами элементов $X$ . Формально, $f[X] = Y$ или $Y = \im f$ . Записывается

f \colon X \surjto Y \qquad \text{или} \qquad X \xsurjto{f} Y

Биективное отображение

Отображение $f \colon X \to Y$ называется биективным, если оно одновременно и инъективно, и сюръективно. Такое отображение задает взаимно однозначное соответствие между множествами $X$ и $Y$ . Записывается

f \colon X \bijto Y \qquad \text{или} \qquad X \xbijto{f} Y

Композиция биекций также является биекцией.

Обратные отображения

Тождественное отображение $\Id_X$ множества $X$ — отображение, которое каждый элемент переводит в себя.

\Id_X \colon X \to X ~\text{где}~ x \mapsto x

Обратное к отображению $f \colon X \to Y$ — отображение $f^-1 \colon Y \to X$ такое, что $f \compose f^-1 = \Id_X$ и $f^-1 \compose f = \Id_Y$ .

Отображение обратимо тогда и только тогда, когда оно является биекцией. На самом деле можно так же обратить и инъективное отображение, но нужно дополнительно изменить область определения обратного.