следующие её члены имеют то же значение в точке $b$ (т. е. $f_i(b) = f_0(b)$). Заменив значение в точке $b$ нулём, получим бесконечную убывающую последовательность из элементов меньшего ранга, что противоречит предположению.)

Теперь покажем, что такое явное определение степени согласовано с индуктивным определением. Для конечных $n$ это очевидно. Пусть $\gamma = \beta + 1$. Каково (явное) определение $\alpha^\gamma$? Пусть $B$ упорядочено по типу $\beta$. Тогда мы должны добавить к $B$ новый наибольший элемент (обозначим его $m$) и рассмотреть отображения $B \cup \{m\} \to A$ с конечным носителем. Ясно, что такое отображение задаётся парой, состоящей из его сужения на $B$ (которое может быть произвольным элементом множества $[B \to A]$) и значения на $m$. При определении порядка мы сначала сравниваем значения на $m$, а потом сужения на $B$, то есть полученное множество изоморфно $[B \to A] \times A$, что и требовалось.

Пусть теперь $\gamma$ — ненулевой предельный ординал и множество $C$ упорядочено по типу $\gamma$. Как устроено множество $[C \to A]$? Элементы, ранг которых меньше $c \in C$, образуют в нём начальный отрезок, и этот начальный отрезок изоморфен $[[0, c) \to A]$. А само множество $[C \to A]$ является объединением этих начальных отрезков (поскольку каждый элемент этого множества имеет конечный носитель) и потому его порядковый тип является точной верхней гранью их порядковых типов, что и требовалось. ▷

Непосредственным следствием этой теоремы является такое утверждение:

**Теорема 41.** Если $\alpha$ и $\beta$ — счётные ординалы, то $\alpha + \beta$, $\alpha\beta$ и $\alpha^\beta$ счётны.

◁ Для суммы и произведения утверждение очевидно. Для степени: если мы пронумеровали все элементы вполне упорядоченных множеств $A$ и $B$, то любой элемент множества $[B \to A]$ может быть задан конечным списком натуральных чисел (носитель и значения на элементах носителя), а таких списков счётное число. ▷

139. Докажите, что $\alpha^{\beta+\gamma} = \alpha^\beta \cdot \alpha^\gamma$ двумя способами: по индукции и с использованием явного определения степени.

140. Докажите, что $(\alpha^\beta)^\gamma = \alpha^{\beta\gamma}$.

141. Докажите, что если $\alpha \ge 2$, то $\alpha^\beta \ge \alpha\beta$.

142. Докажите, что если $\omega^\gamma = \alpha + \beta$ для некоторых ординалов $\alpha, \beta$ и $\gamma$, то либо $\beta = 0$, либо $\beta = \omega^\gamma$.

143. Какие ординалы нельзя представить в виде суммы двух меньших ординалов?
144. Докажите счётность $\alpha^\beta$ для счётных $\alpha$ и $\beta$, используя индуктивное определение степени.

145. Дан некоторый ординал $\alpha > 1$. Укажите наименьший ординал $\beta > 0$, для которого $\alpha\beta = \beta$. (Указание: что будет, если умножить $x$ на степенной ряд $1 + x + x^2 + x^3 + ...$?)

Отметим важную разницу между возведением ординалов в степень и ранее рассмотренными операциями сложения и умножения ординалов. Определяя сумму и произведение ординалов, мы вводили некоторый порядок на сумме и произведении соответствующих множеств (в обычном смысле), здесь же само множество $[B \to A]$ определяется с учётом порядка и отлично от $A^B$. (В частности, при счётных $A$ и $B$ множество $[B \to A]$ счётно, а $A^B$ — нет.)

Явное описание множества $[B \to A]$ позволяет понять, как устроены его начальные отрезки, то есть какой вид имеют ординалы, меньше $\alpha^\beta$.

Рассмотрим некоторую функцию $f \in [B \to A]$. Пусть она отлична от нуля в точках $b_1 > b_2 > \dots > b_k$ и принимает в этих точках значения $a_1, a_2, \dots, a_k$. Нас интересуют все функции, меньше функции $f$.

Все они равны нулю в точках, больших $b_1$. В самой точке $b_1$ они могут быть либо меньше $a_1$, либо равны $a_1$. Любая функция первого типа меньше любой функции второго типа. Функции первого типа могут принимать любые значения в точках, меньших $b_1$, а в точке $b_1$ имеют значение из $[0, a_1)$. Тем самым их можно отождествить с элементами множества $[[0, b_1) \to A] \times [0, a_1)$, и при этом отождествлении сохраняется порядок.

Функции второго типа (равные $a_1$ в точке $b_1$) снова разбиваются на две категории: те, которые в точке $b_2$ меньше $a_2$ и те, которые в $b_2$ равны $a_2$. Функции первой категории отождествляются с элементами множества $[[0, b_2) \to A] \times [0, a_2)$. Функции второй категории снова разобьём на части в зависимости от их значения в точке $b_3$ и т. д. Таким образом, $[0, f)$ как упорядоченное множество изоморфно множеству

$$ [[0, b_1) \to A] \times [0, a_1) + [[0, b_2) \to A] \times [0, a_2) + \dots + [[0, b_k) \to A] \times [0, a_k). $$

Переходя к ординалам (начальные отрезки — это меньше ординалы), получаем такое утверждение:
**Теорема 42.** Всякий ординал, меньший $\alpha^{\beta}$, представляется в виде

$$\alpha^{\beta_1} \alpha_1 + \alpha^{\beta_2} \alpha_2 + \dots + \alpha^{\beta_k} \alpha_k,$$

где $\beta > \beta_1 > \beta_2 > \dots > \beta_k$, а $\alpha_1, \alpha_2, \dots, \alpha_k < \alpha$. Такое представление однозначно и любая сумма указанного вида является ординалом, меньшим $\alpha^{\beta}$.

### Возможность такого представления мы уже доказали. Последнее утверждение следует из того, что любая сумма такого вида является начальным отрезком в множестве $[B \to A]$ (где $A$ и $B$ упорядочены по типам $\alpha$ и $\beta$) и разным суммам соответствуют разные начальные отрезки. ▷

Это утверждение обобщает описанную нами ранее (с. 90) «позиционную систему обозначений с основанием $\alpha$» для ординалов, меньших $\alpha^k$; теперь вместо $k$ можно использовать любой ординал.

Можно было бы сразу сказать, что элементами $[B \to A]$ являются формальные суммы вида

$$\alpha^{\beta_1} \alpha_1 + \alpha^{\beta_2} \alpha_2 + \dots + \alpha^{\beta_k} \alpha_k$$

(где $\beta > \beta_1 > \dots > \beta_k$ и $\alpha_1, \dots, \alpha_k < \alpha$) с естественным порядком на них.

Теперь уже понятно, как устроены ординалы в последовательности

$$\omega^{\omega}, \omega^{(\omega^{\omega})}, \dots$$

Первый из них образован «одноэтажными» выражениями вида

$$\omega^{b_1} a_1 + \omega^{b_2} a_2 + \dots + \omega^{b_k} a_k,$$

где $a_i$ и $b_i$ — натуральные числа (и $b_1 > \dots > b_k$). Если в качестве $b_1, \dots, b_k$ разрешить писать любые «одноэтажные» выражения указанного вида, то полученные «двухэтажные» выражения упорядочены по типу $\omega^{(\omega^{\omega})}$. Разрешив в показателях двухэтажные выражения, мы получим трехэтажные выражения, которые образуют следующий ординал и т.д. Если объединить все эти множества, то есть не ограничивать число этажей (которое для каждого выражения тем не менее конечно), то получится множество, упорядоченное по типу

$$\sup(\omega, \omega^{\omega}, \omega^{(\omega^{\omega})}, \dots)$$

Этот ординал обозначается $\varepsilon_0$.
146. Докажите, что

$$\epsilon_0 = \omega + \omega^\omega + \omega^{(\omega^\omega)} + \dots$$

147. Определим для натуральных чисел операцию «тотальной замены основания $k$ на $l$» (здесь $k$ и $l$ — натуральные числа, причём $l > k$) следующим образом: данное число $n$ запишем в $k$-ичной системе, то есть разложим по степеням $k$, показатели степеней снова запишем в $k$-ичной системе, новые показатели также разложим и т.д. Затем на всех уровнях заменим основание $k$ на основание $l$ и вычислим значение получившегося выражения. Докажите, что начав с любого $n$ и выполняя последовательность операций «вычитание единицы — тотальная замена основания 2 на 3 — вычитание единицы — тотальная замена основания 3 на 4 — вычитание единицы — тотальная замена основания 4 на 5 —...», мы рано или поздно зайдём в тупик, т. е. получится нуль и вычесть единицу будет нельзя. (Указание: заменим все основания сразу на ординал $\omega$; получится убывающая последовательность ординалов, меньших $\epsilon_0$.)

2.13. Приложения ординалов

В большинстве случаев рассуждения с использованием трансфинитной индукции и ординалов можно заменить ссылкой на лемму Цорна; при этом рассуждение становится менее наглядным, но формально более простым. Тем не менее бывают ситуации, когда такая замена затруднительна. В этом разделе мы приведём два полудобных примера.

Первый из них касается борелевских множеств. (Для простоты мы рассматриваем подмножества действительной прямой.) Семейство подмножеств называется $\sigma$-алгеброй, если оно замкнуто относительно конечных и счётных пересечений и объединений, а также относительно перехода к дополнению. (Это означает, что вместе с каждым множеством $A$ это семейство содержит его дополнение $\mathbb{R} \setminus A$, и вместе с любыми множествами $A_0, A_1, \dots$ семейство содержит их объединение $A_0 \cup A_1 \cup \dots$ и пересечение $A_0 \cap A_1 \cap \dots$.) Пример: семейство $P(\mathbb{R})$ всех подмножеств прямой, очевидно, является $\sigma$-алгеброй.

**Теорема 43.** Существует наименьшая $\sigma$-алгебра, содержащая все отрезки $[a, b]$ на прямой.

∠ Формально можно рассуждать так: рассмотрим все возможные $\sigma$-алгебры, содержащие отрезки. Их пересечение будет $\sigma$-алгеброй, и тоже будет содержать все отрезки. (Вообще пересечение любого семейства $\sigma$-алгебр будет $\sigma$-алгеброй — это очевидное следствие определения.) Эта $\sigma$-алгебра и будет искомой. ∠
Множества, входящие в эту наименьшую σ-алгебру, называют борелевскими.

**148. Докажите, что всякое открытое и всякое замкнутое подмножество прямой является борелевским.** (Указание: открытое множество есть объединение содержащихся в нём отрезков с рациональными концами.)

**149. Докажите, что прообраз любого борелевского множества при непрерывном отображении является борелевским множеством.**

**150. Пусть $f_0, f_1, ...$ — последовательность непрерывных функций с действительными аргументами и значениями. Докажите, что множество точек $x$, в которых последовательность $f_0(x), f_1(x), ...$ имеет предел, является борелевским.**

Борелевские множества играют важную роль в дескриптивной теории множеств. Но мы хотим лишь продемонстрировать использование трансфинитной индукции (которую трудно заменить на лемму Цорна) на примере следующей теоремы:

**Теорема 44.** Семейство всех борелевских множеств имеет мощность континуума.

### ◁ Класс борелевских множеств можно строить постепенно. Начнём с отрезков и дополнений к отрезкам. На следующем шаге рассмотрим всевозможные счётные пересечения и объединения уже построенных множеств (отрезков и дополнений к ним).

**151. Докажите, что при этом получатся (среди прочего) все открытые и все замкнутые подмножества прямой.**

Далее можно рассмотреть счётные объединения и пересечения уже построенных множеств и т. д.

Более формально, пусть $B_0$ — семейство множеств, состоящее из всех отрезков и дополнений к ним. Определим $B_{i+1}$ по индукции как семейство множеств, являющихся счётными объединениями или пересечениями множеств из $B_i$.

Все семейства $B_i$ состоят из борелевских множеств (поскольку счётное объединение или пересечение борелевских множеств является борелевским). Исчерпывают ли они все борелевские множества? Вообще говоря, нет: если мы возьмём по одному множеству из каждого класса $B_i$ для всех $i = 0, 1, 2, ...$ и рассмотрим их счётное пересечение, то оно вполне может не принадлежать ни одному из классов. Поэтому мы рассмотрим класс $B_ω$, представляющий собой объединение всех $B_i$ по всем натуральным $i$, затем $B_{ω+1}, B_{ω+2}$ и т. д. Объединение этой последовательности классов естественно назвать $B_{ω2}$ и продолжить построение.
Дадим формальное определение $\mathcal{B}_\alpha$ для любого ординала $\alpha$. Это делается с помощью трансфинитной рекурсии. При $\alpha = \beta + 1$ элементами класса $\mathcal{B}_\alpha$ будут счётные объединения и пересечения множеств из класса $\mathcal{B}_\beta$. Если $\alpha$ — предельный ординал, отличный от 0, то класс $\mathcal{B}_\alpha$ представляет собой объединение всех $\mathcal{B}_\beta$ по всем $\beta < \alpha$. (Класс $\mathcal{B}_0$ мы уже определили.)

Из определения следует, что $\mathcal{B}_\alpha \subset \mathcal{B}_\beta$ при $\alpha < \beta$, так что мы получаем возрастающую цепь классов. Каждый класс замкнут относительно перехода к дополнению (для начального класса мы об этом позаботились, далее по индукции). Все классы $\mathcal{B}_\alpha$ содержатся в классе борелевских множеств, так как мы применяем лишь операции счётного объединения и пересечения, относительно которых класс борелевских множеств замкнут.

Возникает вопрос: как далеко нужно продолжать эту конструкцию? Оказывается, что достаточно дойти до первого несчётного ординала.

Пусть $\mathfrak{N}_1$ — наименьший несчётный ординал. (Это — стандартное для него обозначение.) Другими словами, $\mathfrak{N}_1$ есть семейство всех счётных ординалов, упорядоченных отношением $<$ на ординалах.

**Лемма.** Класс $\mathcal{B}_{\mathfrak{N}_1}$ замкнут относительно счётных объединений и пересечений и потому содержит все борелевские множества.

Доказательство леммы. Пусть имеется счётная последовательность множеств $B_0, B_1, \dots$, принадлежащих $\mathcal{B}_{\mathfrak{N}_1}$. Ординал $\mathfrak{N}_1$ — предельный, и класс $\mathcal{B}_{\mathfrak{N}_1}$ является объединением меньших классов. Поэтому каждое из множеств $B_i$ принадлежит какому-то классу $\mathcal{B}_{\alpha_i}$, где $\alpha_i$ — некоторый ординал, меньший $\mathfrak{N}_1$, т. е. конечный или счётный ординал. Положим $\beta = \sup_i \alpha_i$. Ординал $\beta$ есть точная верхняя грань счётного числа счётных ординалов и потому счётен. В самом деле, рассмотрим ординалы $\alpha_i$ как начальные отрезки в каком-то большем ординале (например, в $\mathfrak{N}_1$); их точная верхняя грань будет объединением счётного числа счётных начальных отрезков и потому будет счётным ординалом.

Теперь первое утверждение леммы очевидно: все $B_i$ лежат в $\mathcal{B}_\beta$, а потому их объединение (или пересечение) лежит в $\mathcal{B}_{\beta+1}$ и тем более в $\mathcal{B}_{\mathfrak{N}_1}$ (поскольку $\beta + 1$ есть счётный ординал и меньше $\mathfrak{N}_1$).

Таким образом, класс $\mathcal{B}_{\mathfrak{N}_1}$ является $\sigma$-алгеброй, содержащей отрезки, и потому содержит все борелевские множества. Лемма доказана.

Как мы уже отмечали, все классы $\mathcal{B}_\alpha$ состоят из борелевских множеств, так что класс $\mathcal{B}_{\mathfrak{N}_1}$ совпадает с классом всех борелевских
множеств.

Что можно сказать про мощность классов? Класс $B_0$ имеет мощность континуума (отрезки задаются своими концами). Если класс $B_\alpha$ имеет мощность континуума, то и следующий класс $B_{\alpha+1}$ имеет мощность континуума (каждый его элемент задаётся счётной последовательностью элементов предшествующего класса, а $c^{N_0} = c$). Каждый предельный класс есть объединение предыдущих, и пока мы не выходим за пределы счётных ординалов, объединение это будет счётно, а $c^{N_0} = c$, так что мы не выходим за пределы континуума. Наконец, $B_{N_1}$ есть объединение несчётного числа предыдущих классов (а именно, $N_1$ классов), но так как $N_1 \le c$, то $c^{N_1} = c$.

Таким образом, класс $B_{N_1}$, он же класс всех борелевских множеств, имеет мощность континуума. ▷

Обычно построение борелевских множеств начинается немного иначе. Именно, на нижнем уровне рассматриваются два класса: открытые и замкнутые множества. На следующем уровне находятся классы $F_\sigma$ (счётные объединения замкнутых множеств) и $G_\delta$ (счётные пересечения открытых множеств). Ещё на уровень выше лежат счётные пересечения множеств из $F_\sigma$ и счётные объединения множеств из $G_\delta$, и т.д. Такой подход является более естественным с точки зрения топологии, поскольку отрезки на прямой ничем не захватительны. Можно проверить, что разница между таким подходом и нашим определением невелика.

152. Докажите, что пересечение двух $F_\sigma$-множеств является $F_\sigma$-множеством (и вообще классы $F_\sigma$, $G_\delta$, а также классы следующих уровней, замкнуты относительно конечных объединений и пересечений).

153. Докажите, что $F_\sigma$- и $G_\delta$-множества лежат в классе $B_2$ в соответствии с нашей классификацией.

154. Докажите, что всякое множество класса $B_2$ отличается от некоторого $F_\sigma$- или $G_\delta$-множества не более чем на счётное множество.

155. Докажите, что всякое множество класса $B_3$ является счётным пересечением $F_\sigma$-множеств или счётным объединением $G_\delta$-множеств и что аналогичное утверждение верно для более высоких уровнях нашей иерархии.

156. Докажите, что существует открытое множество на плоскости, среди вертикальных сечений которого встречаются все открытые подмножества прямой. Докажите, что существует $G_\delta$-множество на плоскости, среди сечений которого встречаются все $G_\delta$-подмножества прямой. Докажите аналогичные утверждения для следующих уровнях.

157. Покажите, что существует $G_\delta$-множество, не являющееся $F_\sigma$-множеством. Покажите, что существует счётное объединение $G_\delta$-множеств,
не являющееся счётным пересечением $F_\sigma$-множеств и т. д. (Указание: воспользуйтесь предыдущей задачей.)

Ординалы часто появляются при классификации элементов того или иного множества по «рангам». Например, можно классифицировать элементы фундированного множества.

**Теорема 45.** Пусть $X$ — фундированное множество. Тогда существует и единственна функция $rk$, определённая на $X$ и принимающая значения в классе ординалов, для которой

$$rk(x) = \min\{\alpha \mid \alpha > rk(y) \text{ для любого } y < x\}$$

(при любом $x \in X$).

### ◁ Определим множество $X_\alpha$ рекурсией по ординалу $\alpha$: $X_\alpha$ состоит из всех элементов $x \in X$, для которых все меньше их (в $X$) элементы принадлежат $X_\beta$ с меньшими индексами $\beta$:

$$x \in X_\alpha \Leftrightarrow (\forall y < x) (\exists \beta < \alpha) (y \in X_\beta).$$

Заметим, что здесь (как и в формулировке теоремы) знак $<$ используется в двух разных смыслах: как порядок на $X$ и как порядок на ординалах.

Очевидно, что с ростом $\alpha$ множество $X_\alpha$ растёт (точнее, не убыwaет). Докажем, что при достаточно большом $\alpha$ множество $X_\alpha$ открывает всё $X$. Если это не так, то из $\beta < \gamma$ следует $X_\beta \subsetneq X_\gamma$ (произвольный минимальный элемент, не лежащий в $X_\beta$, принадлежит $X_\gamma$). Поэтому отображение $\alpha \mapsto X_\alpha$ будет инъекцией, что невозможно (возьмём ординал, по мощности больший $P(X)$; предшествующих ему ординалов уже слишком много).

Теперь определим $rk(x)$ как минимальное значение $\alpha$, для которого $x \in X_\alpha$. Если $rk(x) = \alpha$ и $y < x$, то $rk(y) < \alpha$. (В самом деле, по определению $X_\alpha$ из $x \in X_\alpha$ и $y < x$ следует, что $y \in X_\beta$ при некотором $\beta < \alpha$.) Наоборот, если для некоторого ординала $\gamma$ выполнено неравенство $rk(y) < \gamma$ при всех $y < x$, то $rk(x) \le \gamma$. В самом деле, тогда любой элемент $y < x$ принадлежит некоторому $X_\beta$ с $\beta < \gamma$ (положим $\beta = rk(y)$) и потому $x \in X_\gamma$ и $rk(x) \le \gamma$.

Итак, построенная нами функция $rk$ обладает требуемым свойством. Единственность доказать совсем легко: если есть две такие функции, рассмотрим минимальную точку в $X$, на которой они различаются, и сразу же получим противоречие. ▷

В частности, счётные ординалы можно использовать для классификации деревьев, в которых нет бесконечных путей. Мы будем
рассматривать корневые деревья с конечным или счётным ветвлением (у каждой вершины конечное или счётное число сыновей), в которых нет бесконечной ветви (последовательности вершин, в которых каждая есть сын предыдущей).

Формально такое дерево можно определить как подмножество $T$ множества $N^*$ конечных последовательностей натуральных чисел, замкнутое относительно взятия префикса (если последовательность принадлежит $T$, то любой её начальный отрезок принадлежит $T$). Элементы множества $T$ мы называем вершинами дерева; вершина $u$ есть сын вершины $x$, если $u$ получается из $x$ приписыванием справа какого-то одного числа. Вершина $u$ является потомком вершины $x$, если $u$ получается добавлением к $x$ одного или нескольких чисел.

Мы говорим, что в дереве $T$ нет бесконечной ветви, если не существует бесконечной последовательности натуральных чисел, все начала которой принадлежат $T$. В этом случае отношение порядка

$$y < x \Leftrightarrow y \text{ есть потомок } x$$

фундировано и можно применить предыдущую теорему, определив ранги всех вершин дерева $T$. Ранг его корня (последовательности длины 0) и будем называть рангом дерева.

**Теорема 46.** (а) Ранг любого дерева (описанного вида) является счётным ординалом.

(б) Всякий счётный ординал является рангом некоторого дерева.

∠ (а) Пусть ранг некоторого дерева, то есть ранг его корня, является несчётным ординалом. Тогда ранг одного из сыновей корня также несчётен. (В самом деле, точная верхняя грань счётного множества счётных ординалов является счётным ординалом; это становится ясным, если рассматривать эти ординалы как начальные отрезки большего — тогда точная верхняя грань будет объединением.) У этого сына в свою очередь есть сын несчётного ранга и т. д. Этот процесс не может оборваться, и мы получаем бесконечную ветвь в противоречии с предположением.

(б) Это утверждение доказывается индукцией: пусть $\alpha$ — наи-меньший счётный ординал, для которого такого дерева нет. Тогда для всех меньших ординалов деревья есть. Возьмём эти деревья и сделаем их поддеревьями с общим корнем (их корни станут сыновьями этого общего корня). Новое дерево также имеет счётное ветвление и ранг его корня равен $\alpha$. Δ

158. Пусть имеется счётное дерево, не имеющее бесконечных ветвей. Предположим, что в каждом его листе находится отрезок или дополнение
до отрезка, а в каждой внутренней вершине стоит знак пересечения или объединения. Как сопоставить такому дереву некоторое борелевское множество? (Указание: покажите, что в каждой вершине можно единственным образом написать некоторое множество, согласованное с пометками.) Покажите, что все борелевские множества могут быть получены таким способом.

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

**159.** Докажите, что семейство борелевских множеств имеет мощность континнума, используя «бесконечные формулы» — размеченные деревья, в которых нет бесконечных ветвей. (Это доказательство обходится без ординалов, трансфинитной индукции и даже леммы Цорна — хотя и использует аксиому выбора.)

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

**Теорема 47.** Существует множество точек на плоскости, которое пересекается с каждой прямой ровно в двух точках.

Две параллельные прямые почти что удовлетворяют этому требованию (исключением являются лишь параллельные им прямые). Но избавиться от этого исключения не так просто.

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

Будем строить это множество трансфинитной рекурсией. Пусть $\alpha$ — минимальный ординал, имеющий мощность континуума. (Если континуум-гипотеза верна, то он совпадает с $N_1$, но это нам не важно.) Тогда множество всех меньших ординалов можно поставить во взаимно однозначное соответствие с множеством всех прямых на плоскости. Пусть $l_\beta$ — прямая, соответствующая ординалу $\beta < \alpha$.

Для каждого $\beta < \alpha$ построим множество $M_\beta$, в котором никакие три точки не лежат на одной прямой, следующим образом. Объединим все построенные ранее множества $M_\gamma$ при всех $\gamma < \beta$. Могут ли в этом множестве (обозначим его $T$) какие-то три точки лежать на одной прямой? Если да, то эти точки берутся из каких-то множеств $M_{\gamma_1}, M_{\gamma_2}, M_{\gamma_3}$; возьмём наибольший из ординалов $\gamma_1, \gamma_2, \gamma_3$; в соответствующем множестве будут три точки, лежащие на одной
прямой, что противоречит предположению индукции.

Посмотрим, во скольких точках пересекает прямая $l_β$ множество $T$. Таких точек (по доказанному) не больше двух. Если их ровно две, то всё хорошо и мы новых точек не добавляем, считая, что $M_β = T$. Если их меньше, то мы должны добавить новые точки (до двух), но только так, чтобы при этом не образовалось трёх точек, лежащих на одной прямой. Другими словами, нельзя добавлять точки, которые лежат на пересечении $l_β$ с прямыми, проходящими через пары уже имеющихся точек.

Сколько таких прямых (то есть сколько пар уже имеющихся точек)? По построению видно, что все уже имеющиеся точки лежат по две на каждой прямой $l_γ$ при $γ < β$. (Строго говоря, это следует включить в индуктивное предположение.) Таким образом, множество $T$ по мощности есть $2β = β$, а пар точек не больше $β^2 = β < c$. Поэтому запрещённые точки составляют лишь малую (по мощности) часть прямой $l_β$, и можно выбрать две разрешённые точки.

Теперь осталось объединить множества $M_β$ для всех ординатов $β < α$ и получить искомое множество. (По условию три точки на одной прямой в нём появиться не могут, а всякая прямая будет рано или поздно рассмотрена и две точки на ней будут обеспечены.) ▷

160. Найдите ошибку в следующем «опровержении гипотезы кончинаума»: пусть $N_1 = c$. Упорядочим отрезок $[0, 1]$ по типу $N_1$. Рассмотрим функцию двух переменных, равную единице на паре $(x, y)$, если $x < y$ (в смысле этого порядка), и нулю в остальных случаях. Тогда при фиксированном $x$ функция $y \mapsto f(x, y)$ равна единице везде, кроме счётного множества, и потому интегрируема и $\int f(x, y) dy = 1$ при любом $x$. С другой стороны, функция $x \mapsto f(x, y)$ равна нулю всюду, кроме счётного множества, так что $\int f(x, y) dx = 0$. Получаем противоречие с теоремой Фубини, которая утверждает, что

$$ \int_{0}^{1} \left( \int_{0}^{1} f(x, y) \, dy \right) \, dx = \int_{0}^{1} \left( \int_{0}^{1} f(x, y) \, dx \right) \, dy. $$
## Литература

[1] П. С. Александров, *Введение в теорию множеств и общую топологии*. М.: Наука, 1977.

[2] Н. Бурбаки, *Начала математики*. Первая часть. *Основные структуры анализа*. Книга первая. *Теория множеств*. Перевод с французского Г. Н. Поварова и Ю. А. Шихановича под редакцией В. А. Успенского. М.: Мир, 1965. 456 с.

[3] Т. Йех, *Теория множеств и метод форсинга*. Перевод с английского В. И. Фуксона под редакцией В. Н. Гришина. М.: Мир, 1973. 150 с.

[4] Георг Кантор, *Труды по теории множеств, перевод Ф. А. Медведева и А. П. Юшкевича, издание подготовили А. Н. Колмогоров, Ф. А. Медведев, А. П. Юшкевич, ответственные редакторы А. Н. Колмогоров, А. П. Юшкевич*. М.: Наука, 1985. 431 с. (Серия «Классики науки».)

[5] Пол Дж. Коэн, *Теория множеств и континуум-гипотеза*. Перевод с английского А. С. Есенина-Вольпина, М.: Мир, 1969. 347 с.

[6] К. Куратовский, А. Мостовский, *Теория множеств*. Перевод с английского М. И. Кратко под редакцией А. Д. Тайманова. М.: Мир, 1970. 416 с.

[7] И. А. Лавров, Л. Л. Максимова, *Задачи по теории множеств, математической логике и теории алгоритмов*. Издание второе, М.: Наука, 1984. 224 с.

[8] Ю. И. Манин, *Доказуемое и недоказуемое*. М.: Советское радио, 1979. 168 с.

[9] А. Мостовский, *Конструктивные множества и их приложения*. Перевод с английского М. И. Кратко, Н. В. Белякина и М. К. Валиева под редакцией А. Г. Драгалина и А. Д. Тайманова. М.: Мир, 1973. 256 с.

[10] *Справочная книга по математической логике в четырёх частях под редакцией Дж. Барвайса*. Часть II. *Теория множеств*. Перевод с английского В. Г. Кановея под редакцией В. Н. Гришина. М.: Наука, 1982. 376 с.
[11] А. А. Френкель, И. Бар-Хиллел, *Основания теории множеств*. Перевод с английского Ю. А. Гастева под редакцией А. С. Есенина-Вольпина. М.: Мир, 1966. 556 с.

[12] Ф. Хаусдорф, *Теория множеств*. Под редакцией и с дополнениями П. С. Александрова и А. Н. Колмогорова. М. – Л.: ОНТИ, 1937.

[13] Дж. Шенфилд, *Математическая логика*, перевод с английского И. А. Лаврова и И. А. Мальцева под редакцией Ю. Л. Ершова. М.: Наука, 1975. 528 с.
Предметный указатель

$2^X 13, 38$
= (равенство) 6

$[B \to A] 93$

$(a, b, c) 7, 36$

$\aleph_0 39$

$\aleph_1 99$

$\aleph_1 13$

$\aleph_* 102$

$\aleph^k 15$

$\mathbb{Q} 15$

$\mathbb{R} 15, 19, 27$

$\Delta 7$

$(\binom{n}{k} 11)$

$\cap 6$

$\cup 6$

$\text{Dom } F 32$

$\text{id}_A 33$

$(a, b) 32, 36$

$\mathcal{B}_\alpha 99$

$\mathfrak{c} 39$

$\omega 57, 58$

$\omega \cdot 2 57$

$\omega^2 57, 59$

$\subset 6$

$\subseteq 7$

$\supseteq 6$

$\text{Val } F 32$

$|A| 26$

$A + B 46$

$a < b 45$

$A \times B 32, 37$

$A^B 37$

$C_n^k 11$

$f: A \to B 33$

$f|_{[0,x]} 60$

$f^{-1}(B) 33$

$F_\sigma 100$

$g \circ f 33$

$G_\delta 100$

$P(U) 13, 38$

ZF, ZFC, теории 31

Автоморфизм 49

Аксиома

выбора 14, 31, 35, 65, 73, 75

выделения 31

подстановки 92

степени 31

суммы 31

фундирования 85

экстенсиональности
(объёмности) 85

Аксиоматическая теория
множеств 85

$\sigma$-алгебра 97

Антисимметричность 43

Аргумент функции 32

Ассоциативность 87, 89

Базис Гамеля 68, 69, 77

Банаха – Тарского парадокса 75

Биекция 35

Бином Ньютона 11

Борелевское множество 97, 98

Верхняя граница 57

Взаимно однозначное
соответствие 35

Вложение 34

Возвведение в степень
мощностей 37, 95

Возвведение ординалов в степень 91
индуктивное определение 91

Вполне упорядоченные
множества 55, 68
сравнение 63

Вычитание ординалов 88

Гипотеза континуума 28, 30, 39,
103

График функции 32
Декартово произведение
множеств 32
Деление ординалов с остатком 89
Дерево 101
Дескриптивная теория
множеств 98
Диагональная конструкция 26
Дистрибутивность 89
Добавление счётного множества 17
Дополнение множества 6

Замкнутое множество 100
Значение функции 32

Изоморфизм 48
Индукция 52, 59
Индуцированный порядок 46
Инъекция 34

Кардинал 65
Кардинальное число множества 26
Класс 25
Класс эквивалентности 42
Комбинаторика 10
Коммутативность 87, 89
Композиция функций 33
Континуум 19
Континуум-гипотеза 104
Кривая Пеано 19

Лексикографический порядок 44,
55
Лемма Форна 75, 97
Линейно независимое
множество 69
Линейный порядок 43, 78

Максимальный элемент 47
Минимальный элемент 47
Множества 6
борелевские 97, 98
вполне упорядоченные 55, 68
декартово произведение 32
замкнутые 100

изоморфные 48
линейно независимые 69
линейно упорядоченные 43
мощность 6, 9, 25, 26, 31
объединение 6
ограниченные сверху 57
открытые 100
пересечение 6
плотные 51
произведение 87
пустые 6
равенство 6
равномощные 11, 35
разность 6
симметрическая разность 7
сумма 87
счётные 13
транзитивные 86
фундированные 52, 53, 101
частично упорядоченные 43
Монотонные булевы функции 8
Мощности 6, 9, 25, 26, 31
возведение в степень 37, 95
операции 37
произведение 37, 82
сравнение 19, 25
сумма 37, 80

Наибольший элемент 47
Наименьший элемент 47
Наложение 34
Начальный отрезок 57, 64
Непосредственно следующий
элемент 56
Носитель отображения 93

Область определения функции 32
Образ 33
Обратная функция 35
Объединение множеств 6
Ограничение функции 60
Операции над мощностями 37
Ординалы 65, 83, 86, 88
непредельные 84

предельные 84

сравнение 84

Открытое множество 100

Отношение 32

бинарное 32

линейного порядка 43, 78

полного порядка 55

порядка 42

частичного порядка 43, 78

эквивалентности 12, 42

Отображение 34

Парадокс

Банаха – Тарского 75

Бурали-Форти 85

лжеца 30

Рассела 29

Пересечение множеств 6

Периодическая дробь 16

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

Позиционная система
счисления 90, 96

Полный порядок 55

Порядковый тип 48, 65, 87

Предельный элемент 56

Предпорядок 45

Префиксный код 13

Произведение множеств 87

Произведение мощностей 37, 82

Прообраз 33, 98

Псевдообъём 72

Пустое множество 6

Пятый постулат 30

Равенство множеств 6

Равномощность базисов 83

Равномощность множеств 11, 35

Равносоставленные
многогранники 71

Разность множеств 6

Ранг дерева 102

Рекурсивное определение 60

Рефлексивность 12, 42, 43

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

Симметричность 12, 42

Сложение ординалов 87
индуктивное определение 90

Соответствие взаимно
однозначное 35

Соседние элементы 51

Сравнимость 43

Сумма множеств 87

Сумма мощностей 37, 80

Счётное множество 13

Сюръекция 34

Теорема

Кантора 26, 28

Кантора – Шрёдера –
Бернштейна 19, 40, 80

Кёнига 41

Рамсея 43

Фубини 104

Цермело 65

Тождественная функция 33

Топологическая сортировка 79

Точная верхняя грань 57

Транзитивное множество 86

Транзитивность 12, 42, 43

Трансфинитная индукция
(рекурсия) 59, 68

Третья проблема Гильберта 71

ультрафильтр 79

Умножение ординалов 88
индуктивное определение 91

Упорядоченная пара 32, 35
по Винеру 37
по Куратовскому 36

Фактор-множество 43

Финитные последовательности 49

Формула включений и
исключений 9
Фубини теорема 104

Фундированное множество 52, 53, 101

Функция 32

аргумент 32

график 32

значение 32

из ... в ... 32

инъективная 34

множество значений 32

область определения 32

обратная 34, 35

ограничение 60

сюръективная 34

тождественная 33

Характеристическая функция

множества 9

Цепные дроби 40

Цепь 76

Частичный порядок 43, 78

Числа

алгебраические 16

двочно-рациональные 50

действительные 15, 19, 27

натуральные 13

рациональные 15

трансцендентные 27

Число сочетаний 11

Элемент множества 6

Элементарная эквивалентность 50
Указатель имён

Банах С. (Stefan Banach), 30.03.1892 (Krakóv, ныне в
Польше) – 31.08.1945 (Львів, ныне в Украине) : 75

Берштейн Ф. (Felix Bernstein), 24.02.1878, Halle (Германия) – 03.12.1956,
Zurich (Швейцария) : 19, 23

Борель Э. (Félix Édouard Justin Émile Borel), 07.01.1871, Saint Affrique,
Aveyron, Midi-Pyrénées (Франция) – 03.02.1956, Paris (Франция) : 97

Брауэр Л. Э. Я. (Luitzen Egbertus Jan Brouwer), 27.02.1881,
Overschie (ныне в Роттердаме, Нидерланды) – 02.12.1966,
Blaricum (Нидерланды) : 18

Бурали-Форти (Cesare Burali-Forti), 13.08.1861,
Arezzo (Италия) – 21.01.1931, Turin (Италия) : 85

Винер Н. (Norbert Wiener), 26.11.1894, Columbia,
Missouri (США) – 18.03.1964, Stockholm (Швеция) : 37

Галилей Г. (Galileo Galilei), 15.02.1564, Pisa (ныне в Италии) – 08.01.1642,
Arcetri, рядом с Флоренцией (Италия) : 19

Гамель (Georg Karl Wilhelm Hamel), 12.09.1877, Düren,
Rheinland (Германия) – 04.10.1954, Landshut (Германия) : 68, 69

Гёдель К. (Kurt Gödel), 28.04.1906, Brünn, Австро-Венгрия (ныне Брно,
Чехия) – 14.01.1978, Princeton (США) : 14

Гильберт Д. (David Hilbert), 23.01.1862, Königsberg, Prussia (ныне
Калиниград, Россия) – 14.02.1943, Göttingen (Германия) : 71

Дедекинд Р. (Julius Wilhelm Richard Dedekind), 06.10.1831,
Braunschweig (ныне Германия) – 12.02.1916,
Braunschweig (Германия) : 17, 18

Евклид Александрийский, около 325 (?) до Р. Х. – около 265 (?) до Р. Х.,
Александрия (ныне Египет) : 30

Кантор Г. (Georg Ferdinand Ludwig Philipp Cantor), 03.03.1845,
Петербург (Россия) – 06.01.1918, Halle (Германия) : 7, 18, 19, 23,
26–28, 30, 31, 68

Кёниг Ю. (Julius König), 16.12.1849, Györ (Венгрия) – 08.04.1913,
Budapest (Венгрия) : 41

Коэн П. Дж. (Paul Joseph Cohen), 02.04.1934, Long Branch, New
Jersey (США) – 23.03.2007, Stanford, California (США) : 15

Куратовский К. (Kazimierz Kuratowski), 02.02.1896, Warsaw,
Польша (Россия) – 18.06.1980, Warsaw (Польша) : 36

Линдеман Ф. (Carl Louis Ferdinand von Lindemann), 12.04.1852,
Hannover (ныне Германия) – 06.03.1939, Munich (Германия) : 27

Лиувиль Ж. (Joseph Liouville), 24.03.1809,
Saint-Omer (Франция) – 08.09.1882, Paris (Франция) : 27

Лобачевский Николай Иванович, 01.12.1792, Нижний
Новгород (Россия) – 24.02.1856, Казань (Россия) : 30
Нейман Дж. (John von Neumann), 28.12.1903,
Budapest (Венгрия) – 08.02.1957, Washington, D.C. (США) : 85

Ньютон И. (Sir Isaac Newton), 04.01.1643, Woolsthorpe,
Lincolnshire (Англия) – 31.03.1727, London (Англия) : 11

Пеано Дж. (Giuseppe Peano), 27.08.1858, Cuneo, Piemonte (Италия) –
20.04.1932, Turin (Италия) : 19

Рамсей Ф. (Frank Plumpton Ramsey), 22.02.1903,
Cambridge, Cambridgeshire (Англия) – 19.01.1930,
London (Англия) : 43

Рассел Б. (Bertrand Arthur William Russell), 18.05.1872, Ravenscroft,
Trelleck, Monmouthshire (Уэльс, Великобритания) – 02.02.1970,
Penrhyndeudraeth, Merioneth (Уэльс, Великобритания) : 29

Тарский А. (Alfred Tarski), 14.01.1902, Warsaw (Россия, ныне
Польша) – 26.10.1983, Berkeley, California (США) : 75

Френкель А. А. (Adolf Abraham Halevi Fraenkel), 17.02.1891,
Munich (Германия) – 15.10.1965, Jerusalem (Израиль) : 31, 85

Фубини Г. (Guido Fubini), 19.01.1879, Venice (Италия) – 06.06.1943, New
York (США) : 104

Цермело Э. (Ernst Friedrich Ferdinand Zermelo), 27.07.1871,
Berlin (Германия) – 21.05.1953, Freiburg im
Breisgau (Германия) : 31, 65, 68, 85

Цорн М. (Max August Zorn), 06.06.1906, Krefeld (Германия) – 09.03.1993,
Bloomington, Indiana (США) : 75

Шрёдер Э. (Friedrich Wilhelm Karl Ernst Schröder), 25.11.1841,
Mannheim (Германия) – 16.06.1902, Karlsruhe (Германия) : 23

Эрмит Ш. (Charles Hermite), 24.12.1822, Dieuze,
Lorraine (Франция) – 14.01.1901, Paris (Франция) : 27