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

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

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

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

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

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

Что можно сказать про мощность классов? Класс $$\mathcal{B}_0$$ имеет мощность континуума (отрезки задаются своими концами). Если класс $$\mathcal{B}_\alpha$$ имеет мощность континуума, то и следующий класс $$\mathcal{B}_{\alpha+1}$$ имеет мощность континуума (каждый его элемент задается счетной последовательностью элементов предшествующего класса, а $$\mathfrak{c}^{\aleph_0}\hm=\mathfrak{c}$$ ). Каждый предельный класс есть объединение предыдущих, и пока мы не выходим за пределы счетных ординалов, объединение это будет счетно, а $$\mathfrak{c}\aleph_0\hm=\mathfrak{c}$$, так что мы не выходим за пределы континуума. Наконец, $$\mathcal{B}_{\aleph_1}$$ есть объединение несчетного числа предыдущих классов (а именно, $$\aleph_1$$ классов), но так как $$\aleph_1\hm\le\mathfrak{c}$$, то $$\mathfrak{c}\aleph_1\hm=\mathfrak{c}$$.

Таким образом, класс $$\mathcal{B}_{\aleph_1}$$, он же класс всех борелевских множеств, имеет мощность континуума.

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

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

147. Докажите, что $$F_{\sigma}$$ - и $$G_{\delta}$$ - множества лежат в классе $$\mathcal{B}_2$$ в соответствии с нашей классификацией.

148. Докажите, что всякое множество класса $$\mathcal{B}_2$$ отличается от некоторого $$F_{\sigma}$$ - или $$G_{\delta}$$ - множества не более чем на счетное множество.

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

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

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

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

Теорема 45. Пусть $$X$$ - фундированное множество. Тогда существует и единственна функция $$\rk$$, определенная на $$X$$ и принимающая значения в классе ординалов, для которой$$\rk(x)=\min\{\alpha\mid\text{$\alpha>\rk(y)$ для любого $y<x$}\}$$ (при любом $$x\hm\in X$$ ).

Доказательство. Определим множество $$X_{\alpha}$$ рекурсией по ординалу $$\alpha$$: $$X_{\alpha}$$ состоит из всех элементов $$x\hm\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}$$ растет (точнее, не убывает). Докажем, что при достаточно большом $$\alpha$$ множество $$X_{\alpha}$$ покрывает все $$X$$. Если это не так, то из $$\beta \hm< \gamma$$ следует $$X_{\beta}\hm\subsetneq X_{\gamma}$$ (произвольный минимальный элемент, не лежащий в $$X_{\beta}$$, принадлежит $$X_\gamma$$ ). Поэтому отображение $$\alpha\hm\mapsto X_{\alpha}$$ будет инъекцией, что невозможно (возьмем ординал, по мощности больший $$P(X)$$ ; предшествующих ему ординалов уже слишком много).

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

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

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

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

Мы говорим, что в дереве $$T$$ нет бесконечной ветви, если не существует бесконечной последовательности натуральных чисел, все начала которой принадлежат $$T$$. В этом случае отношение порядка$$y<x \ \Leftrightarrow \ \text{$y$ есть потомок $x$}$$ фундировано и можно применить предыдущую теорему, определив ранги всех вершин дерева $$T$$. Ранг его корня (последовательности длины $$0$$ ) и будем называть рангом дерева.

Теорема 46.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Теперь осталось объединить множества $$M_{\beta}$$ для всех ординалов $$\beta\hm<\alpha$$ и получить искомое множество. (По условию три точки на одной прямой в нем появиться не могут, а всякая прямая будет рано или поздно рассмотрена и две точки на ней будут обеспечены.)

154. Найдите ошибку в следующем " опровержении гипотезы континуума": пусть $$\aleph_1=\mathfrak{c}$$. Упорядочим отрезок $$[0,1]$$ по типу $$\aleph_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 f(x,y)\,dx\right)\,dy$$