Лекция 3. Построение множеств, упорядоченные пары и парадокс Рассела

Лекция 1 ввела множества как готовый язык: подмножество, пустое множество, операции и законы. Третья лекция возвращается к множествам с другой стороны — как они вообще строятся. Из одного пустого множества получаются натуральные числа, из множеств — упорядоченные пары и декартово произведение, а попытка задать множество любым свойством приводит к парадоксу Рассела, после которого правило построения приходится ограничить. Начинается лекция с добивания темы лекции 2 — ещё одного доказательства от противного.

1. Иррациональность корня из трёх

Утверждение 1. $\sqrt{3}$ иррационально.

Доказательство. От противного: пусть $\sqrt{3} = \dfrac{p}{q}$, где $p, q \in \mathbb{Z}$, $q \ne 0$ и $\gcd(p, q) = 1$. Возведём в квадрат: $3 = \dfrac{p^2}{q^2}$, то есть $p^2 = 3q^2$, и $p^2$ делится на $3$.

Отсюда $p$ делится на $3$. Проверим разбором случаев: если $p = 3k \pm 1$, то $p^2 = 9k^2 \pm 6k + 1$ даёт остаток $1$ при делении на $3$, а не $0$. Значит, остаётся только $p = 3k$, $k \in \mathbb{Z}$.

Подставим: $(3k)^2 = 3q^2$, $9k^2 = 3q^2$, $q^2 = 3k^2$. Теперь $q^2$ делится на $3$, и тем же рассуждением $q$ делится на $3$. Получили, что $3$ — общий делитель $p$ и $q$, а $\gcd(p, q) = 1$. Противоречие. $\blacksquare$

2. Задание множества свойством

2.1. Универсум и запись через свойство

Множество можно задать не перечислением, а свойством, которым обладают его элементы. Свойство — это предикат $P(x)$ из лекции 2, а элементы берутся из заранее выбранного универсума $U$ — множества всех объектов, о которых сейчас идёт речь:

$\{x \in U \mid P(x)\}.$

Такая запись называется set-builder notation. Пример: $\{x \in \mathbb{N} \mid x \text{ чётно}\} = \{0, 2, 4, \dots\}$ (если считать $0 \in \mathbb{N}$, как в построении из раздела 3).

Важна часть «$x \in U$»: свойство не создаёт элементы из воздуха, оно выделяет их из множества, которое уже есть. Почему без неё нельзя — в разделе 8.

2.2. Подмножество и истинность по пустоте

Определение подмножества в кванторной записи:

$A \subseteq B \iff \forall x\ \big[(x \in A) \to (x \in B)\big].$

Для $A = \varnothing$ посылка $x \in \varnothing$ ложна при любом $x$, а импликация с ложной посылкой истинна: $0 \to 1 = 1$ и $0 \to 0 = 1$. Поэтому $\varnothing \subseteq A$ для любого $A$ — по умолчанию, как в утверждении 1 лекции 1.

Разность в той же записи: $A \setminus B = \{x \mid x \in A \wedge x \notin B\}$.

3. Натуральные числа из пустого множества

Пустое множество $\varnothing = \{\,\}$ существует и единственно. Из него одного фон Нейман строит все натуральные числа:

$0 = \varnothing, \qquad n + 1 = n \cup \{n\}.$

Каждое число — множество всех меньших чисел: $3 = \{0, 1, 2\}$. Отсюда два удобных следствия: в числе $n$ ровно $n$ элементов, и $m < n$ равносильно $m \in n$.

Похожая ловушка на уровень глубже: для $B = \{a, \{b\}\}$ верно $\{b\} \in B$, но $b \notin B$. Элементы $B$ — это $a$ и множество $\{b\}$, а не сам $b$.

4. Экстенсиональность и равенство

Аксиома экстенсиональности. Множество определяется своим составом: два множества равны, если у них одни и те же элементы.

$A = B \iff \forall x\ \big[(x \in A) \leftrightarrow (x \in B)\big].$

Раскрыв $\leftrightarrow$ как две импликации, получаем рабочую форму — метод двух включений:

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

Из экстенсиональности следует, что порядок и повторы при перечислении не важны: $\{a, b\} = \{b, a\} = \{a, a, b\}$. Именно поэтому для пар в разделе 6 понадобится отдельная конструкция.

Определение 1. $A$ — собственное (строгое) подмножество $B$, если $A \subseteq B$ и $A \ne B$.

5. Операции и тождества

5.1. Дополнение и симметрическая разность

Определение 2. Дополнение $A$ до универсума: $\overline{A} = U \setminus A$.

Определение 3. Симметрическая разность: $A \triangle B = (A \setminus B) \cup (B \setminus A)$ — элементы, лежащие ровно в одном из двух множеств.

Логический двойник симметрической разности — исключающее «или»:

$x \oplus y = (x \vee y) \wedge \neg(x \wedge y).$

Действительно, $x \in A \triangle B \iff (x \in A) \oplus (x \in B)$: «в $A$ или в $B$, но не в обоих». Эта же формула даёт ещё одну запись: $A \triangle B = (A \cup B) \setminus (A \cap B)$.

5.2. Два тождества

Утверждение 2. $A \cup (\overline{A} \cap B) = A \cup B$.

Доказательство. По дистрибутивности $A \cup (\overline{A} \cap B) = (A \cup \overline{A}) \cap (A \cup B) = U \cap (A \cup B) = A \cup B$, так как $A \cup \overline{A} = U$, а $U$ — нейтральный элемент для пересечения. $\blacksquare$

Смысл: добавлять к $A$ стоит только ту часть $B$, которой в $A$ ещё нет, и результат от этого не меняется.

Утверждение 3. $A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)$.

Доказательство. Цепочкой равносильностей для произвольного $x$:

$x \in A \setminus (B \cup C) \iff x \in A \wedge \neg(x \in B \vee x \in C) \qquad\text{[определения]}$ $\iff x \in A \wedge x \notin B \wedge x \notin C \qquad\text{[закон де Моргана]}$ $\iff (x \in A \wedge x \notin B) \wedge (x \in A \wedge x \notin C) \qquad\text{[идемпотентность } \wedge\text{]}$ $\iff x \in (A \setminus B) \cap (A \setminus C). \qquad\text{[определения]}$

Так как $x$ произвольный, множества равны по экстенсиональности. $\blacksquare$

Это закон де Моргана «внутри $A$»: если взять $A = U$, получится $\overline{B \cup C} = \overline{B} \cap \overline{C}$. Парный закон: $A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C)$.

5.3. Булеан

Определение 4. Булеан множества $A$ — множество всех его подмножеств:

$\mathcal{P}(A) = \{S \mid S \subseteq A\}, \qquad |\mathcal{P}(A)| = 2^{|A|}.$

Это то же, что $2^A$ из лекции 1, где формула для мощности объяснена через битовые маски. Пример: $\mathcal{P}(\{\varnothing\}) = \{\varnothing, \{\varnothing\}\}$ — это число $2$ из раздела 3.

6. Упорядоченные пары

6.1. Пара по Куратовскому

Множество $\{a, b\}$ не помнит порядок: $\{a, b\} = \{b, a\}$. Чтобы получить упорядоченную пару, где важно, что первое, а что второе, её выражают через множества:

Определение 5. $(a, b) = \{\{a\}, \{a, b\}\}$.

Первая компонента — та, что лежит в обоих элементах пары, вторая — оставшаяся. От определения требуется одно свойство, ради которого пара и вводится.

Утверждение 4. $(a, b) = (c, d) \iff a = c \wedge b = d$.

Доказательство. Справа налево очевидно. Слева направо: пусть $\{\{a\}, \{a, b\}\} = \{\{c\}, \{c, d\}\}$.

• Случай $a = b$. Тогда слева стоит $\{\{a\}\}$ — множество из одного элемента. Значит, $\{c\} = \{a\}$ и $\{c, d\} = \{a\}$, откуда $c = a$ и $d = a = b$.
• Случай $a \ne b$. Слева два разных элемента: одноэлементный $\{a\}$ и двухэлементный $\{a, b\}$. Справа тоже должно быть два разных элемента, поэтому $c \ne d$. Одноэлементные совпадают: $\{a\} = \{c\}$, $a = c$. Двухэлементные тоже: $\{a, b\} = \{a, d\}$, и так как $b \ne a$, получаем $b = d$. $\blacksquare$

Пример: $(1, 2) = \{\{1\}, \{1, 2\}\}$, а $(2, 1) = \{\{2\}, \{1, 2\}\}$ — разные множества. Пара с равными компонентами вырождается: $(a, a) = \{\{a\}\}$.

6.2. Декартово произведение

Определение 6. $A \times B = \{(a, b) \mid a \in A,\ b \in B\}$.

Все такие пары лежат в одном готовом множестве: $\{a\}$ и $\{a, b\}$ — подмножества $A \cup B$, то есть элементы $\mathcal{P}(A \cup B)$, а сама пара — подмножество $\mathcal{P}(A \cup B)$, то есть элемент $\mathcal{P}(\mathcal{P}(A \cup B))$. Поэтому

$A \times B \subseteq \mathcal{P}(\mathcal{P}(A \cup B)),$

и декартово произведение получается выделением из этого множества по свойству «быть парой $(a, b)$ с $a \in A$, $b \in B$» — ровно так, как разрешает раздел 8.

7. Принадлежность и включение на вложенных множествах

Сводка ловушек этой лекции. Каждая строка проверяется по определению: для $\in$ — ищем объект среди перечисленных элементов, для $\subseteq$ — проверяем, что каждый элемент левого множества лежит в правом.

8. Парадокс Рассела

8.1. Наивное построение

Хочется разрешить любое свойство: для каждого $P(x)$ существует множество $\{x \mid P(x)\}$ — всех объектов с этим свойством, без указания, откуда они берутся. Бертран Рассел показал, что это правило противоречиво.

Возьмём свойство $P(A) = (A \notin A)$ — «множество не содержит себя в качестве элемента» — и множество

$R = \{A \mid A \notin A\}.$

Спросим, лежит ли $R$ в самом себе.

• Если $R \in R$, то $R$ удовлетворяет свойству, задающему $R$, то есть $R \notin R$.
• Если $R \notin R$, то $R$ обладает свойством $A \notin A$, значит, попадает в $R$: $R \in R$.

Получили $R \in R \iff R \notin R$ — противоречие. Значит, такого множества $R$ нет, и правило «любое свойство задаёт множество» ложно.

8.2. Выход: выделение из готового множества

Разрешено только выделять элементы по свойству из множества, которое уже построено:

$\{x \in A \mid P(x)\}.$

Это аксиома выделения. Построение множества тогда идёт в два шага: сначала есть множество (универсум $U$ или любое уже полученное), затем из него выделяются элементы по свойству. Запись из раздела 2 — ровно эта форма.

Если повторить рассуждение Рассела с выделением, $R_A = \{x \in A \mid x \notin x\}$, противоречия нет: получается лишь, что $R_A \notin A$. Иначе при $R_A \in A$ снова $R_A \in R_A \iff R_A \notin R_A$.

Следствие. Множества всех множеств не существует. Если бы оно было, $V$, то $R_V$ пришлось бы лежать в $V$, а мы только что показали, что $R_V \notin V$. Поэтому универсум $U$ в каждой задаче свой — например, $\mathbb{N}$, $\mathbb{R}$ или $\mathcal{P}(A)$, — а не «всё на свете».

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

• Считать, что из $p^2 \mathbin{\vdots} n$ всегда следует $p \mathbin{\vdots} n$. Верно для простого $n$, для составного нет: $36 \mathbin{\vdots} 4$, но $6$ не делится на $4$.
• Путать $\varnothing$ и $\{\varnothing\}$, $b$ и $\{b\}$. Фигурные скобки добавляют уровень вложенности: $\{b\}$ — это коробка с $b$, а не сам $b$.
• Проверять $X \subseteq Y$ поиском $X$ среди элементов $Y$. Так проверяется $X \in Y$; для включения надо перебрать элементы $X$.
• Считать пару $(a, b)$ множеством $\{a, b\}$. Множество порядок не различает, пара различает: $(1, 2) \ne (2, 1)$, а $\{1, 2\} = \{2, 1\}$.
• Считать $(A \times B) \times C$ и $A \times (B \times C)$ одним множеством.
• Писать $\{x \mid P(x)\}$ без универсума и считать, что так можно задать любое множество. Правильная форма — $\{x \in U \mid P(x)\}$.
• Доказывать тождество «на кругах Эйлера». Рисунок подсказывает, но доказательство — два включения или цепочка равносильностей с подписями.

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

1. Докажите, что $\sqrt{5}$ иррационально. Какие остатки может давать $p^2$ при делении на $5$?
2. Запишите число $4$ по фон Нейману через $0, 1, 2, 3$ и найдите $|4|$.
3. Для $B = \{1, \{2\}, \{1, 2\}\}$ определите, что верно: $2 \in B$, $\{2\} \in B$, $\{2\} \subseteq B$, $\{1\} \subseteq B$, $\{1, 2\} \subseteq B$.
4. Найдите $A \triangle B$ для $A = \{1, 2, 3, 4\}$, $B = \{3, 4, 5\}$ двумя способами: по определению и как $(A \cup B) \setminus (A \cap B)$.
5. Докажите цепочкой равносильностей, что $A \setminus (B \cap C) = (A \setminus B) \cup (A \setminus C)$.
6. Распишите $(1, 1)$ и $(1, 2)$ по Куратовскому. Сколько элементов в каждом множестве?
7. Сколько элементов в $\{0, 1\} \times \{a, b, c\}$? Выпишите их.
8. Пусть $A = \{1, 2, 3\}$. Найдите $R_A = \{x \in A \mid x \notin x\}$, считая $1, 2, 3$ числами по фон Нейману. Лежит ли $R_A$ в $A$?

Ответы

1. От противного: $p^2 = 5q^2$. Квадраты дают при делении на $5$ остатки $0, 1, 4, 4, 1$ для $p \equiv 0, 1, 2, 3, 4$, так что $p^2 \mathbin{\vdots} 5$ только при $p \mathbin{\vdots} 5$. Тогда $p = 5k$, $q^2 = 5k^2$, и $q \mathbin{\vdots} 5$ — противоречие с несократимостью.
2. $4 = 3 \cup \{3\} = \{0, 1, 2, 3\}$, $|4| = 4$.
3. $2 \in B$ — нет (элементы: $1$, $\{2\}$, $\{1, 2\}$). $\{2\} \in B$ — да. $\{2\} \subseteq B$ — нет, так как $2 \notin B$. $\{1\} \subseteq B$ — да. $\{1, 2\} \subseteq B$ — нет, снова из-за $2$ (хотя $\{1, 2\} \in B$).
4. $A \setminus B = \{1, 2\}$, $B \setminus A = \{5\}$, $A \triangle B = \{1, 2, 5\}$. Второй способ: $\{1, 2, 3, 4, 5\} \setminus \{3, 4\} = \{1, 2, 5\}$.
5. $x \in A \setminus (B \cap C) \iff x \in A \wedge \neg(x \in B \wedge x \in C) \iff x \in A \wedge (x \notin B \vee x \notin C) \iff (x \in A \wedge x \notin B) \vee (x \in A \wedge x \notin C) \iff x \in (A \setminus B) \cup (A \setminus C)$: определения, де Морган, дистрибутивность, определения.
6. $(1, 1) = \{\{1\}, \{1, 1\}\} = \{\{1\}\}$ — один элемент. $(1, 2) = \{\{1\}, \{1, 2\}\}$ — два элемента.
7. $2 \cdot 3 = 6$: $(0, a), (0, b), (0, c), (1, a), (1, b), (1, c)$.
8. Число по фон Нейману не содержит себя: $n \in n$ означало бы $n < n$. Поэтому $R_A = \{1, 2, 3\} = A$, и $R_A \notin A$: множество $\{1, 2, 3\}$ не совпадает ни с $1$, ни с $2$, ни с $3 = \{0, 1, 2\}$ (в нём нет $0$) — как и обещает раздел 8.2.

Шпаргалка