Лекция 1. Теория множеств

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

1. Множество и принадлежность

1.1. Что такое множество

Множество — неопределяемое понятие, как точка в геометрии. Его не определяют, а описывают: набор различимых объектов, рассматриваемый как единое целое. Запись $A = \{a, b, c, d\}$ означает, что множество $A$ состоит из четырёх элементов.

Два свойства, которые надо помнить как аксиомы:

Поэтому множества $\{1, 2, 2, 3\}$ и $\{3, 1, 2\}$ равны — типичный первый вопрос-подстава.

Способы задания множества:

1. Перечислением: $A = \{a, b, c, d\}$.
2. Через предикат: $A = \{x \mid P(x)\}$ — «все $x$, для которых $P(x)$ истинно». Например, $B = \{x \in \mathbb{N} \mid x < 5\} = \{0, 1, 2, 3, 4\}$.
3. Рекурсивно: $0 \in \mathbb{N}$; если $n \in \mathbb{N}$, то $n + 1 \in \mathbb{N}$.

Стандартные обозначения: $\mathbb{N}$ — натуральные, $\mathbb{Z}$ — целые, $\mathbb{Q}$ — рациональные, $\mathbb{R}$ — вещественные, $\varnothing$ — пустое множество, $U$ — универсум (всё, что рассматривается в задаче).

1.2. Принадлежность

$x \in A$ читается «$x$ принадлежит $A$». Это высказывание: оно либо истинно, либо ложно, третьего нет. $x \notin A$ — отрицание.

Для $A = \{a, b, c, d\}$ и $C = \{c, e\}$: высказывание $b \in A$ истинно, $x \in A$ для постороннего $x$ ложно, $e \in C$ истинно, $e \notin A$ истинно.

2. Логический язык

Теория множеств формулируется через логику: без связок и кванторов не записать ни одного определения.

2.1. Импликация

$S \Rightarrow T$ читается «если $S$, то $T$» (следование). Таблица истинности:

Единственный случай лжи — посылка истинна, а следствие ложно. Мнемоника: импликация — это обещание «если сдам сессию на пять, куплю новую видеокарту». Обещание нарушено только в одном случае: сессия сдана на пять, а видеокарты нет. Если сессия не сдана, обещание не нарушено, что бы ни случилось дальше.

2.2. Эквиваленция

$S \Leftrightarrow T$ («тогда и только тогда», ттт) истинно, когда $S$ и $T$ имеют одинаковое значение истинности. Рабочая формула:

$S \Leftrightarrow T \quad\text{это}\quad (S \Rightarrow T) \wedge (T \Rightarrow S).$

Именно поэтому любое доказательство «тогда и только тогда» распадается на два: в сторону $\Rightarrow$ и в сторону $\Leftarrow$.

2.3. Знак определения

Запись $\overset{\text{def}}{\Longleftrightarrow}$ — не утверждение, которое надо доказывать, а определение: левая часть по определению означает правую. Пометку def ставят, чтобы отличать: определение не доказывают, его применяют.

2.4. Кванторы

Две равносильные формы записи одного и того же:

$(\forall x)\ (x \in A \Rightarrow x \in B) \qquad\text{и}\qquad (\forall x \in A)\ x \in B.$

Вторая — ограниченный квантор, короткая запись.

Отрицание кванторов — обязательно к запоминанию:

$\neg(\forall x)\, P(x) \iff (\exists x)\, \neg P(x), \qquad \neg(\exists x)\, P(x) \iff (\forall x)\, \neg P(x).$

Словами: отрицание «все» — это «хотя бы один не». Отсюда алгоритм половины задач: чтобы опровергнуть утверждение с $\forall$, достаточно одного контрпримера; чтобы доказать его, нужно рассуждение для произвольного элемента.

2.5. Предикат

Определение 1. Предикат — высказывание с переменной. Само по себе оно ни истинно, ни ложно, пока не подставлено значение.

Пример: $Q(y)$ = «$y \in B$» — одноместный предикат. $Q(a)$ = «$a \in B$» уже высказывание (истинно), $Q(8)$ = «$8 \in B$» — высказывание (ложно).

Предикат превращается в высказывание двумя способами: подстановкой значения ($Q(8)$) или навешиванием квантора ($(\forall y)\, Q(y)$, $(\exists y)\, Q(y)$).

A = {1, 2, 3, 4}
B = {1, 2, 3, 4, 5}
all(x in B for x in A)       # (∀x∈A) x∈B, то есть A ⊆ B  →  True
any(x not in B for x in A)   # есть контрпример?          →  False

3. Подмножество

3.1. Определение

Определение 2. $A$ — подмножество $B$, если каждый элемент $A$ является элементом $B$:

$A \subseteq B \overset{\text{def}}{\Longleftrightarrow} (\forall x)\ (x \in A \Rightarrow x \in B).$

Это главная формула лекции.

Пример. $A = \{a, b, c, d\}$. Для $B = \{a, b, d\}$ верно $B \subseteq A$: все три элемента лежат в $A$. Для $C = \{c, e\}$ неверно $C \subseteq A$: контрпример $e \in C$, но $e \notin A$.

Важно, как именно опровергается $C \subseteq A$. Не «там же $e$ лишний», а формально:

$\text{Требуется опровергнуть: } (\forall x)\ (x \in C \Rightarrow x \in A).$ $\text{Отрицание: } (\exists x)\ (x \in C \wedge x \notin A).$ $\text{Контрпример: } x = e,\ e \in C \text{ истинно},\ e \in A \text{ ложно, импликация ложна (строка T, F). Значит } C \not\subseteq A.\ \blacksquare$

Именно так это надо писать в ДЗ. Строка «$e$ не лежит в $A$» — ответ, но не доказательство.

3.2. Свойства включения

Рефлексивность, транзитивность и антисимметричность вместе означают, что $\subseteq$ — отношение частичного порядка. Термин появится через пару лекций.

4. Пустое множество

Определение 3. $\varnothing = \{\,\}$ — множество, не содержащее ни одного элемента. Формально, в двух равносильных записях: $(\forall x)\ x \notin \varnothing$, или $(\nexists x)\ x \in \varnothing$.

Утверждение 1. $\varnothing \subseteq A$ для любого множества $A$.

Доказательство. По определению $\varnothing \subseteq A \iff (\forall x)\ (x \in \varnothing \Rightarrow x \in A)$. Посылка $x \in \varnothing$ ложна для любого $x$: в пустом множестве нет элементов. По таблице истинности импликация с ложной посылкой истинна. Значит, импликация истинна для каждого $x$, квантор $\forall$ выполнен, и $\varnothing \subseteq A$. $\blacksquare$

Это истинность по пустоте. Бытовая аналогия: «все мои Ferrari красные» — Ferrari нет ни одной, опровергнуть нечем, высказывание истинно. На контрольной это спрашивают почти гарантированно в формулировке «докажите, что пустое множество является подмножеством любого множества»; доказательство ровно в три строки, как выше.

5. Строгое подмножество и равенство

Определение 4. $A$ — строгое (собственное) подмножество $B$, если $A$ лежит в $B$, но не совпадает с ним:

$A \subset B \overset{\text{def}}{\Longleftrightarrow} A \subseteq B \wedge A \ne B.$

То есть в $B$ есть хотя бы один элемент, которого нет в $A$.

Определение 5. Множества равны, если состоят из одних и тех же элементов:

$A = B \overset{\text{def}}{\Longleftrightarrow} (\forall x)\ (x \in A \Leftrightarrow x \in B).$

Раскрывая $\Leftrightarrow$ по разделу 2.2, получаем рабочую форму:

$A = B \iff (A \subseteq B) \wedge (B \subseteq A).$

Метод двух включений. Любое доказательство равенства множеств пишется по одному шаблону:

Большинство задач на доказательство в первом модуле решаются подстановкой в эту рамку.

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

Единственное место, где первокурсники стабильно теряют баллы. Пусть $A = \{a, b, c, d\}$.

Правило-детектор: смотрите на левую часть. Если слева одиночный объект — работает только $\in$. Если слева множество (в фигурных скобках или обозначенное буквой множества) — уместны оба знака, но проверяются они по-разному.

7. Мощность и булеан

Определение 6. Мощность конечного множества $|A|$ — число его элементов. $|\{a, b, c, d\}| = 4$, $|\varnothing| = 0$, $|\{\varnothing\}| = 1$, $|\{a, a, b\}| = 2$ (кратность не считается).

Для бесконечных множеств мощность — более тонкое понятие (счётные и несчётные множества, $|\mathbb{N}| = \aleph_0$); это дальше по курсу. Пока мощность — это число элементов.

Определение 7. Булеан (множество всех подмножеств) множества $A$:

$2^A = \mathcal{P}(A) = \{X \mid X \subseteq A\}.$

Для $A = \{a, b\}$: $2^A = \{\varnothing, \{a\}, \{b\}, \{a, b\}\}$, $|2^A| = 4$.

Утверждение 2. $|2^A| = 2^{|A|}$.

Объяснение по-программистски: каждое подмножество однозначно кодируется битовой маской длины $n = |A|$, где $i$-й бит показывает, взят ли $i$-й элемент. Масок ровно $2^n$. Для $A = \{a, b, c\}$:

000 → ∅        100 → {a}
001 → {c}      101 → {a, c}
010 → {b}      110 → {a, b}
011 → {b, c}   111 → {a, b, c}      всего 2³ = 8

Тем же приёмом перебирают подмножества в задачах на полный перебор: for (int mask = 0; mask < (1 << n); mask++). Число строгих подмножеств — $2^n - 1$ (все, кроме самого $A$); непустых тоже $2^n - 1$ (все, кроме $\varnothing$).

8. Операции и законы алгебры множеств

Определение 8. Пусть $A, B \subseteq U$.

Законы (все доказываются одинаково):

Как доказывать закон. Либо методом двух включений, либо цепочкой равносильностей с подписью, какой закон применён на каждом шаге:

$x \in A \cap (B \cup C) \iff x \in A \wedge (x \in B \vee x \in C) \qquad\text{[определения } \cap \text{ и } \cup\text{]}$ $\iff (x \in A \wedge x \in B) \vee (x \in A \wedge x \in C) \qquad\text{[дистрибутивность в логике]}$ $\iff x \in A \cap B \vee x \in A \cap C \iff x \in (A \cap B) \cup (A \cap C). \qquad\text{[определения } \cap \text{ и } \cup\text{]}\ \blacksquare$

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

9. Типовые задачи

Частые ошибки

1. «Очевидно» вместо ссылки на определение. За это снимают балл: каждое утверждение опирается на определение или уже доказанный факт.
2. Опровержение $\forall$-утверждения без явного контрпримера. Нужен конкретный элемент и проверка обеих частей импликации.
3. Путаница $\in$ и $\subseteq$ хотя бы в одном месте (раздел 6).
4. Равенство множеств доказано только в одну сторону. Нужны оба включения.
5. $\subset$ там, где допускается равенство. В этом курсе $\subset$ — строгое включение; для нестрогого пишите $\subseteq$.
6. $\varnothing$ и $\{\varnothing\}$ считаются одним и тем же. У них разная мощность.
7. Нет знака $\blacksquare$ или слов «что и требовалось доказать» в конце доказательства.

Мини-тренажёр

1. Заполните таблицу истинности $S \Rightarrow T$ по памяти.
2. Запишите определение $A \subseteq B$ через кванторы.
3. Докажите $\varnothing \subseteq A$ в три строки.
4. Чему равны $|\varnothing|$ и $|\{\varnothing\}|$?
5. Верно ли $\varnothing \in \{\varnothing\}$? А $\{\varnothing\} \subseteq \varnothing$?
6. В чём разница между $\subseteq$ и $\subset$?
7. Запишите определение $A = B$ двумя способами.
8. Какие записи верны для $A = \{a, b\}$: $a \in A$, $\{a\} \in A$, $\{a\} \subseteq A$, $A \subseteq A$?
9. Сколько подмножеств у множества из 5 элементов? А строгих?
10. Запишите закон де Моргана для множеств.
11. Запишите на языке логики: «в множестве $A$ найдётся элемент, не принадлежащий $B$». Что это утверждение опровергает?

Шпаргалка