Лекция 7. Мощность множеств, счётные и несчётные множества

На лекции 6 появились инъекции, сюръекции и биекции и принцип Дирихле для конечных множеств. Теперь те же отображения становятся инструментом сравнения размеров: два множества «одного размера», если между ними есть биекция. Для конечных множеств это обычный подсчёт элементов, а для бесконечных выясняется, что бесконечности бывают разные: натуральных чисел столько же, сколько рациональных, но меньше, чем точек прямой.

1. Конечные и бесконечные множества

Определение 1. Множество $A$ конечно, если для некоторого $n \in \mathbb N$ существует биекция $f\colon A \to \{0, 1, \dots, n - 1\}.$ Число $n$ называют числом элементов $A$ и пишут $|A| = n$. При $n = 0$ множество $\{0, \dots, n - 1\}$ пусто, и это определение пустого множества: $|\varnothing| = 0$.

В этом курсе $\mathbb N = \{0, 1, 2, \dots\}$: иначе случай $n = 0$ не вошёл бы в определение.

Определение 2. Множество бесконечно, если оно не конечно.

Дополнение. Число $n$ в определении 1 определено однозначно: если бы были биекции $A \to \{0, \dots, n - 1\}$ и $A \to \{0, \dots, m - 1\}$ с $m < n$, их композиция дала бы инъекцию из $n$-элементного множества в $m$-элементное, что запрещает принцип Дирихле.

2. Равномощность и кардинальные числа

2.1. Равномощные множества

Определение 3. Множества $A$ и $B$ равномощны, $|A| = |B|$, если существует биекция $f\colon A \to B$.

Для конечных множеств это то же самое, что «одинаковое число элементов». Но определение не требует считать элементы, поэтому работает и для бесконечных множеств.

Равномощность ведёт себя как отношение эквивалентности: $\mathrm{id}_A$ — биекция $A \to A$, обратная к биекции — биекция, композиция биекций — биекция.

2.2. Кардинальное число

Определение 4. Кардинальное число (мощность) множества — общий «размер» всех множеств, равномощных данному. В наивной теории множеств это класс эквивалентности по отношению равномощности.

Пример. Мощность $2$ — это класс всех двухэлементных множеств: $\bigl\{\{1, 2\},\ \{2, 3\},\ \{1, 3\},\ \dots\bigr\} = 2.$

Слово «класс», а не «множество», здесь не случайно: совокупность всех двухэлементных множеств слишком велика, чтобы быть множеством, — к ней применимы рассуждения в духе парадокса Рассела. Поэтому в аксиоматической теории кардиналы определяют иначе, а запись $|A|$ удобно понимать просто как «мощность $A$».

2.3. Сравнение мощностей

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

• $|A| \le |B|$, если существует инъекция $f\colon A \to B$;
• $|A| < |B|$, если $|A| \le |B|$ и не существует биекции $f\colon A \to B$.

Смысл: $A$ можно без склеек уложить внутрь $B$. Например, $|\mathbb N| \le |\mathbb R|$ через вложение $n \mapsto n$.

Теорема 1 (транзитивность). $|A| \le |B| \ \wedge\ |B| \le |C| \ \Rightarrow\ |A| \le |C|$.

Дополнение. Доказательство. Пусть $f\colon A \to B$ и $g\colon B \to C$ — инъекции. Тогда $g \circ f\colon A \to C$ инъективна: из $g(f(a_1)) = g(f(a_2))$ по инъективности $g$ следует $f(a_1) = f(a_2)$, а по инъективности $f$ — $a_1 = a_2$. $\blacksquare$

Ещё одно свойство порядка — антисимметричность: из $|A| \le |B|$ и $|B| \le |A|$ следует $|A| = |B|$. Это уже не очевидно и составляет теорему Кантора — Бернштейна — Шрёдера (раздел 5).

2.4. Подмножество конечного множества

Теорема 2. Если $A \subseteq B$, $|A| = |B|$ и $B$ конечно, то $A = B$.

Дополнение. Доказательство. Пусть $|B| = n$ и $A \ne B$: есть $b \in B \setminus A$. Возьмём биекцию $f\colon B \to A$. Тогда $f$ — инъекция из $B$ в $B \setminus \{b\}$, потому что $A \subseteq B \setminus \{b\}$. Но $|B \setminus \{b\}| = n - 1 < n$, и по принципу Дирихле такой инъекции нет. Противоречие. $\blacksquare$

3. Счётные множества

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

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

• Множество счётно, если оно конечно или равномощно $\mathbb N$.
• Множество несчётно, если оно бесконечно и неравномощно $\mathbb N$.

Равномощность $\mathbb N$ означает, что элементы можно выписать в последовательность $x_0, x_1, x_2, \dots$ без повторов, в которой встретится каждый элемент: $x_n = f^{-1}(n)$.

3.2. Критерий счётности

Теорема 3. Для множества $X$ равносильны три условия:

1. $X$ счётно;
2. существует инъекция $X \to \mathbb N$;
3. $X$ пусто или существует сюръекция $\mathbb N \to X$.

Второе условие — это $|X| \le |\mathbb N|$: счётные множества — ровно те, что «не больше $\mathbb N$». Третье удобно на практике: достаточно выписать последовательность, в которой встречается каждый элемент $X$, а повторы разрешены.

Дополнение. Доказательство. Понадобится вспомогательный факт.

Лемма. Любое подмножество $S \subseteq \mathbb N$ счётно.

Если $S$ конечно, доказывать нечего. Если бесконечно, перенумеруем его элементы по возрастанию: $s_0 = \min S$, $s_{k+1} = \min\{s \in S \mid s > s_k\}$. Минимумы существуют, потому что каждое непустое подмножество $\mathbb N$ имеет наименьший элемент, а множества непусты, потому что $S$ бесконечно. Отображение $k \mapsto s_k$ инъективно (последовательность строго возрастает) и сюръективно: каждый $s \in S$ получит номер не больше $s$, потому что $s_k \ge k$. $\blacksquare$

• $(1 \Rightarrow 2)$ Конечное $X$ биективно отображается в $\{0, \dots, n - 1\} \subseteq \mathbb N$; равномощное $\mathbb N$ — биективно на $\mathbb N$. Оба отображения — инъекции в $\mathbb N$.
• $(2 \Rightarrow 1)$ Инъекция $f\colon X \to \mathbb N$ — биекция между $X$ и образом $f(X) \subseteq \mathbb N$, а $f(X)$ счётно по лемме.
• $(2 \Rightarrow 3)$ Пусть $X \ne \varnothing$, $f\colon X \to \mathbb N$ — инъекция и $x_0 \in X$. Положим $g(n) = f^{-1}(n)$, если $n \in f(X)$, и $g(n) = x_0$ иначе. Каждый $x \in X$ получается как $g(f(x))$, значит $g$ сюръективна.
• $(3 \Rightarrow 2)$ Пустое множество вкладывается в $\mathbb N$ пустой функцией. Если $g\colon \mathbb N \to X$ сюръективна, положим $f(x) = \min g^{-1}(\{x\})$ — наименьший номер, под которым $x$ встречается. Прообраз непуст по сюръективности, минимум существует, а $f$ инъективна, потому что у разных $x$ прообразы не пересекаются. $\blacksquare$

Заметьте, что в $(3 \Rightarrow 2)$ правая обратная к сюръекции строится без аксиомы выбора: в $\mathbb N$ всегда можно взять наименьший элемент.

3.3. Объединение счётных множеств

Теорема 4. Счётное объединение счётных множеств счётно: если $X_0, X_1, X_2, \dots$ счётны, то $\bigcup_{i \in \mathbb N} X_i$ счётно.

Дополнение. Доказательство. Пустые $X_i$ ничего не добавляют, их можно выбросить; если пусты все, объединение пусто. Для каждого непустого $X_i$ выберем сюръекцию $g_i\colon \mathbb N \to X_i$ — она есть по теореме 3. Тогда $G\colon \mathbb N \times \mathbb N \to \bigcup_i X_i, \qquad G(i, j) = g_i(j)$ сюръективна. Осталось занумеровать пары: $\mathbb N \times \mathbb N$ равномощно $\mathbb N$, например через канторову нумерацию по диагоналям $(0,0),\ (0,1),\ (1,0),\ (0,2),\ (1,1),\ (2,0),\ \dots, \qquad c(i, j) = \frac{(i + j)(i + j + 1)}{2} + i.$ Композиция $G \circ c^{-1}\colon \mathbb N \to \bigcup_i X_i$ — сюръекция, и по теореме 3 объединение счётно. $\blacksquare$

Тонкость: выбрать сразу бесконечно много сюръекций $g_i$ позволяет только аксиома выбора (счётная её версия). Без неё теорема в общем виде не доказывается.

4. Несчётность

Теорема 5. Интервал $(0, 1)$ несчётен, а вместе с ним и вся прямая $\mathbb R$.

На лекции 4 по матану это доказывали через вложенные отрезки. Здесь — другой классический способ.

Дополнение. Доказательство диагональным методом Кантора. Пусть $(0, 1)$ счётно. Оно бесконечно, значит, его элементы можно выписать в последовательность $x_0, x_1, x_2, \dots$, в которой встречается каждое число. Запишем их десятичными дробями:

$$\begin{aligned} x_0 &= 0{,}\,\underline{d_{00}}\,d_{01}\,d_{02}\dots \\ x_1 &= 0{,}\,d_{10}\,\underline{d_{11}}\,d_{12}\dots \\ x_2 &= 0{,}\,d_{20}\,d_{21}\,\underline{d_{22}}\dots \end{aligned}$$

Построим $y = 0{,}\,c_0 c_1 c_2 \dots$, где $c_n = 5$, если $d_{nn} \ne 5$, и $c_n = 4$, если $d_{nn} = 5$. Тогда $y \in (0, 1)$, и $y$ отличается от каждого $x_n$ в $n$-й цифре после запятой. Цифр $0$ и $9$ в записи $y$ нет, поэтому у $y$ единственная десятичная запись (неоднозначность бывает только у дробей вида $\dots 0999\dots = \dots 1000\dots$), и $y \ne x_n$ для всех $n$. Получили число, которого нет в последовательности, — противоречие.

$\mathbb R$ несчётно: если бы была инъекция $\mathbb R \to \mathbb N$, её ограничение на $(0, 1)$ тоже было бы инъекцией, и $(0, 1)$ было бы счётно по теореме 3. $\blacksquare$

Итак, $|\mathbb N| < |\mathbb R|$: инъекция $\mathbb N \to \mathbb R$ есть, а биекции нет. Мощность $\mathbb R$ называют континуумом.

5. Теорема Кантора — Бернштейна — Шрёдера

Теорема 6 (Кантора — Бернштейна — Шрёдера). $|A| \le |B| \ \wedge\ |B| \le |A| \ \Rightarrow\ |A| = |B|.$

Иначе: если есть инъекция $A \to B$ и инъекция $B \to A$, то есть и биекция $A \to B$. Сами данные инъекции биекциями быть не обязаны — биекцию приходится собирать из их кусков.

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

Дополнение. Пример. $|[0, 1]| = |(0, 1)|$. Инъекция $(0, 1) \to [0, 1]$ — вложение $x \mapsto x$. Инъекция $[0, 1] \to (0, 1)$ — $x \mapsto \dfrac{x + 1}{3}$, её образ $\bigl[\tfrac13, \tfrac23\bigr]$. Явную биекцию выписать можно, но заметно сложнее.

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

Пусть $f\colon A \to B$ и $g\colon B \to A$ — инъекции. Определим множества $C_0 = A \setminus g(B), \qquad C_{k+1} = g\bigl(f(C_k)\bigr), \qquad C = \bigcup_{k \ge 0} C_k.$ $C_0$ — элементы $A$, у которых нет прообраза при $g$, а $C$ — всё, что из них получается, если ходить туда-обратно $A \xrightarrow{f} B \xrightarrow{g} A$. Положим $h(a) = \begin{cases} f(a), & a \in C, \\ g^{-1}(a), & a \notin C. \end{cases}$ Второй случай корректен: если $a \notin C$, то $a \notin C_0$, значит $a \in g(B)$, а прообраз при инъекции $g$ единственный.

Инъективность. На $C$ функция $h$ совпадает с инъекцией $f$, вне $C$ — с инъективной $g^{-1}$. Пусть $a \in C$, $a' \notin C$ и $f(a) = g^{-1}(a')$. Тогда $a' = g(f(a))$, и если $a \in C_k$, то $a' \in C_{k+1} \subseteq C$ — противоречие.

Сюръективность. Возьмём $b \in B$. Если $g(b) \notin C$, то $h(g(b)) = g^{-1}(g(b)) = b$. Если $g(b) \in C$, то $g(b) \notin C_0$ (он лежит в $g(B)$), значит $g(b) \in C_{k+1} = g(f(C_k))$ для некоторого $k$: $g(b) = g(f(a))$ с $a \in C_k$. По инъективности $g$ получаем $b = f(a) = h(a)$.

Значит, $h$ — биекция $A \to B$. $\blacksquare$

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

• Считать, что из $A \subsetneq B$ следует $|A| < |B|$. Для бесконечных множеств это неверно: $2\mathbb N \subsetneq \mathbb N$, но мощности равны.
• Проверять $|A| = |B|$, предъявив одну функцию, которая не биекция, и сделав вывод «значит, неравномощны». Нужно, чтобы не было никакой биекции: $n \mapsto 2n$ на $\mathbb N$ не сюръективна, но $\mathbb N$, конечно, равномощно себе.
• Доказывая $|A| < |B|$, ограничиваться инъекцией $A \to B$. Она даёт только $\le$; строгость требует показать, что биекции нет.
• Путать соглашения: в курсе ДМ «счётное» включает конечные множества, на матане — нет.
• В диагональном методе забывать про двойную запись дробей вроде $0{,}5000\dots = 0{,}4999\dots$. Отсюда выбор цифр $4$ и $5$ без $0$ и $9$.
• Считать, что теорема Кантора — Бернштейна — Шрёдера делает одну из данных инъекций биекцией. Биекция строится заново из кусков обеих.

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

1. Постройте биекцию между $\mathbb N$ и множеством нечётных натуральных чисел.
2. Найдите номер пары $(2, 3)$ в канторовой нумерации $c(i, j) = \dfrac{(i + j)(i + j + 1)}{2} + i$ и пару с номером $12$.
3. Счётны ли множества: $\mathbb Z \times \mathbb Z$; множество всех конечных подмножеств $\mathbb N$; множество всех бесконечных последовательностей из $0$ и $1$?
4. Докажите, что если $A$ счётно и $B \subseteq A$, то $B$ счётно.
5. С помощью теоремы Кантора — Бернштейна — Шрёдера докажите, что $|[0, 1)| = |\mathbb R|$.
6. Множества $A$ и $B$ конечны, $|A| = 5$. Сколько существует биекций $A \to B$, если $|B| = 5$? А если $|B| = 6$?

Ответы

1. $n \mapsto 2n + 1$: инъективна, и каждое нечётное $m$ — образ $\frac{m - 1}{2}$.
2. $c(2, 3) = \frac{5 \cdot 6}{2} + 2 = 17$. Номер $12$: диагональ $i + j = 4$ начинается с номера $\frac{4 \cdot 5}{2} = 10$, значит $i = 2$, $j = 2$, пара $(2, 2)$.
3. $\mathbb Z \times \mathbb Z$ — счётно: $\mathbb Z \cong \mathbb N$, а $\mathbb N \times \mathbb N$ счётно. Конечные подмножества $\mathbb N$ — счётно: подмножество $\{a_1, \dots, a_k\}$ кодируется числом $2^{a_1} + \dots + 2^{a_k}$, и это биекция с $\mathbb N$ (двоичная запись). Бесконечные $0$-$1$-последовательности — несчётно: диагональный метод работает дословно, достаточно заменять $n$-й член на противоположный.
4. Если $f\colon A \to \mathbb N$ — инъекция, то её ограничение на $B$ тоже инъекция, и $B$ счётно по теореме 3.
5. $[0, 1) \to \mathbb R$: вложение $x \mapsto x$. $\mathbb R \to [0, 1)$: например, $x \mapsto \frac{1}{2} + \frac{1}{\pi}\operatorname{arctg} x$ — инъекция в $(0, 1) \subseteq [0, 1)$. По теореме 6 мощности равны.
6. При $|B| = 5$ биекций $5! = 120$. При $|B| = 6$ ни одной: биекция означала бы $|A| = |B|$.

Шпаргалка