Мы определили сложение и умножение ординалов с помощью явных конструкций порядка на соответствующих множествах. Вместо этого можно было бы их определить индуктивно.
Теорема 38.Сложение ординалов обладает следующими свойствами: $$\begin{align*} \alpha+ 0 = \alpha;\\ \alpha+(\beta+1) = (\alpha+\beta)+1;\\ \alpha+\gamma= \sup\{\alpha+\beta\mid \beta<\gamma\} \text{ для предельного $\gamma\hm\ne0$}. \end{align*}$$ Эти свойства однозначно определяют операцию сложения.
Доказательство. Два первых свойства очевидны; проверим третье. Если $$\beta\hm<\gamma$$, то $$\alpha\hm+\beta\hm<\alpha\hm+\gamma$$, так что $$\alpha\hm+\gamma$$ будет верхней границей всех сумм вида $$\alpha\hm+\beta$$ при $$\beta\hm<\gamma$$. Надо проверить, что эта граница точная. Пусть некоторый ординал $$\tau$$ меньше $$\alpha\hm+\gamma$$. Убедимся, что он меньше $$\alpha\hm+\beta$$ для некоторого $$\beta\hm<\gamma$$. Если $$\tau\hm<\alpha$$, все очевидно. Если $$\tau\hm\ge\alpha$$, представим его в виде $$\tau\hm=\alpha\hm+\sigma$$. Тогда $$\alpha\hm+\sigma \hm< \alpha\hm+\gamma$$ и потому $$\sigma\hm<\gamma$$. Поскольку ординал $$\gamma$$ предельный, $$\sigma\hm+1$$ также меньше $$\gamma$$ и остается положить $$\beta\hm=\sigma\hm+1$$.
Указанные свойства однозначно определяют операцию сложения, так
как представляют собой
Аналогично можно определить и умножение:
Теорема 39. Умножение ординалов обладает следующими свойствами: $$\begin{align*} \alpha 0 = 0;\\ \alpha(\beta+1) = \alpha\beta+\alpha;\\ \alpha\gamma= \sup\{\alpha\beta\mid \beta<\gamma\} \text{ для предельного $\gamma\hm\ne0$}. \end{align*}$$ Эти свойства однозначно определяют операцию умножения.
Доказательство. Доказательство аналогично, нужно только проверить, что если $$\tau\hm<\alpha\gamma$$ для предельного $$\gamma$$, то $$\tau\hm<\alpha\beta$$ для некоторого $$\beta\hm<\gamma$$. Как мы видели на с.101, ординал $$\tau$$ имеет вид $$\tau\hm=\alpha\gamma'\hm+\alpha'$$ при $$\gamma'\hm<\gamma$$ ; достаточно положить $$\beta\hm=\gamma'\hm+1$$.
Возникает естественное желание определить операцию возведения в степень. Мы уже по существу определили возведение в целую положительную степень ( $$\alpha^n$$ есть произведение $$n$$ сомножителей, равных $$\alpha$$ ). Другими словами, если $$A$$ упорядочено по типу $$\alpha$$, то множество $$A^n$$ последовательностей длины $$n$$ с элементами из $$A$$ с обратным лексикографическим порядком (сравнение справа налево) упорядочено по типу $$\alpha^n$$.
Следующий шаг- определить $$\alpha^\omega$$. Первая идея,
приходящая в голову- взять множество $$A^{\bbN}$$ бесконечных
последовательностей и определить на нем
Замечание. Тут опять мы подходим к опасной границе парадоксов и вынуждены выражаться уклончиво. На самом деле теорема о трансфинитной рекурсии говорила об определении функции на вполне упорядоченном множестве, а ординалы не образуют множества- их слишком много. Кроме того, в ней шла речь о функциях со значениями в некотором заданном множестве, которого здесь тоже нет. Подобные индуктивные определения можно корректно обосновать в теории множеств с использованием так называемой аксиомы подстановки, но мы об этом говорить не будем. Вместо этого мы дадим явное описание возведения в степень, свободное от этих проблем.
Чтобы понять смысл возведения в степень, посмотрим, как выглядит
ординал $$\alpha^\omega$$ (для некоторого $$\alpha$$ ). Пусть $$A$$ -
множество, упорядоченное по типу $$\alpha$$.
Ординал $$\alpha^\omega$$
по определению есть точная верхняя грань $$\alpha^n$$ для
натуральных $$n$$. Ординал $$\alpha^n$$ есть
Аналогичное утверждение верно и для любого показателя степени.
Пусть $$A$$ и $$B$$ - вполне упорядоченные множества, имеющие порядковые типы $$\alpha$$ и $$\beta$$. Рассмотрим множество $$[B\to A]$$ состоящее из отображений $$B$$ в $$A$$, имеющих " конечный носитель" (равных минимальному элементу $$A$$ всюду, за исключением конечного множества). Введем на $$[B\nolinebreak\to A]$$ порядок: если $$f_1\hm\ne f_2$$, выберем наибольший элемент $$b\hm\in B$$, для которого $$f_1(b)\hm\ne f_2(b)$$ и сравним $$f_1(b)$$ и $$f_2(b)$$.
Теорема 40.
Указанное правило задает
Доказательство. Нам надо проверить, что указанный порядок является полным и что выполнены требования индуктивного определения степени.
Назовем носителем элемента $$f\hm\in[B\to A]$$ множество тех $$b\hm\in B$$, для которых $$f(b)\hm>0$$ (здесь $$0$$ обозначает наименьший элемент множества $$A$$ ). Назовем рангом функции $$f$$ наибольший элемент носителя (по определению носитель конечен, так что наибольший элемент существует). Ранг определен для всех функций, кроме тождественно нулевой, которая является минимальным элементом множества $$[B\to A]$$. Чем больше ранг функции, тем больше сама функция в смысле введенного нами порядка.
Пусть порядок на $$[B\to A]$$ не является полным и $$f_0\hm>f_1\hm>f_2\hm>\ldots$$ - убывающая последовательность элементов $$[B\to A]$$. Все элементы $$f_i$$ отличны от $$0$$ ; рассмотрим их ранги. Эти ранги образуют невозрастающую последовательность, поэтому начиная с некоторого места стабилизируются (множество $$B$$ вполне упорядочено). Отбросим начальный отрезок и будем считать, что с самого начала ранги всех элементов убывающей последовательности одинаковы и равны некоторому $$b$$. В соответствии с определением, значения $$f_0(b), f_1(b),\dots$$ образуют невозрастающую последовательность, поэтому начиная с некоторого места стабилизируются. Отбросив начальный отрезок, будем считать, что все $$f_i$$ имеют одинаковый ранг $$b$$ и одинаковое значение $$f_i(b)$$. Тогда значения $$f_i(b)$$ не влияют на сравнения, и потому их можно заменить на $$0$$. Получим убывающую последовательность элементов $$[B\to A]$$ с рангами меньше $$b$$. Чтобы завершить рассуждение, остается сослаться на принцип индукции по множеству $$B$$.
(Более формально, рассмотрим все бесконечно убывающие последовательности. У каждой из них рассмотрим ранг первого элемента. Рассмотрим те из них, у которых этот ранг минимально возможный; пусть $$b$$ - это минимальное значение. В любой такой последовательности все элементы имеют ранг $$b$$. Из всех таких последовательностей $$f_0\hm>f_1\hm>\ldots$$ выберем ту, у которой значение $$f_0(b)$$ минимально; все следующие ее члены имеют то же значение в точке $$b$$ (т.е. $$f_i(b)\hm=f_0(b)$$ ). Заменив значение в точке $$b$$ нулем, получим бесконечную убывающую последовательность из элементов меньшего ранга, что противоречит предположению.)
Теперь покажем, что такое явное определение степени согласовано с индуктивным определением. Для конечных $$n$$ это очевидно. Пусть $$\gamma\hm=\beta\hm+1$$. Каково (явное) определение $$\alpha^\gamma$$? Пусть $$B$$ упорядочено по типу $$\beta$$. Тогда мы должны добавить к $$B$$ новый наибольший элемент (обозначим его $$m$$ ) и рассмотреть отображения $$B\cup\{m\}\to A$$ с конечным носителем. Ясно, что такое отображение задается парой, состоящей из его сужения на $$B$$ (которое может быть произвольным элементом множества $$[B\to A]$$ ) и значения на $$m$$. При определении порядка мы сначала сравниваем значения на $$m$$, а потом сужения на $$B$$, то есть полученное множество изоморфно $$[B\to A]\hm\times A$$, что и требовалось.
Пусть теперь $$\gamma$$ - ненулевой предельный ординал и
множество $$C$$ упорядочено
по типу $$\gamma$$. Как устроено множество $${[C\to A]}$$?
Элементы, ранг которых меньше $$c\hm\in C$$, образуют в нем
начальный отрезок, и этот начальный отрезок изоморфен $$[[0,c)\to
A]$$.
А само множество $$[C\to A]$$ является
объединением этих начальных отрезков (поскольку каждый элемент этого множества
имеет конечный носитель) и потому его
Непосредственным следствием этой теоремы является такое утверждение:
Теорема 41.Если $$\alpha$$ и $$\beta$$ - счетные ординалы, то $$\alpha+\beta$$, $$\alpha\beta$$ и $$\alpha^\beta$$ счетны.
Доказательство. Для суммы и произведения утверждение очевидно. Для степени: если мы пронумеровали все элементы вполне упорядоченных множеств $$A$$ и $$B$$, то любой элемент множества $$[B\to A]$$ может быть задан конечным списком натуральных чисел (носитель и значения на элементах носителя), а таких списков счетное число.
133. Докажите, что $$\alpha^{\beta+\gamma}=\alpha^\beta\cdot\alpha^\gamma$$ двумя способами: по индукции и с использованием явного определения степени.
134. Докажите, что $$(\alpha^\beta)^\gamma=\alpha^{\beta\gamma}$$.
135. Докажите, что если $$\alpha\ge2$$, то $$\alpha^\beta\ge\alpha\beta$$.
136. Докажите, что если $$\omega^\gamma=\alpha+\beta$$ для некоторых ординалов $$\alpha$$, $$\beta$$ и $$\gamma$$, то либо $$\beta=0$$, либо $$\beta=\omega^\gamma$$.
137. Какие ординалы нельзя представить в виде суммы двух меньших ординалов?
138. Докажите счетность $$\alpha^\beta$$ для счетных $$\alpha$$ и $$\beta$$, используя индуктивное определение степени.
139. Дан некоторый ординал $$\alpha\hm>1$$. Укажите наименьший ординал $$\beta\hm>0$$, для которого $$\alpha\beta\hm=\beta$$. (Указание: что будет, если умножить $$x$$ на степенной ряд $$1\hm+x\hm+x^2\hm+x^3\hm+\ldots$$?)
Отметим важную разницу между операцией возведения ординалов в степень и ранее рассмотренными операциями сложения и умножения ординалов. Определяя сумму и произведение ординалов, мы вводили некоторый порядок на сумме и произведении соответствующих множеств (в обычном смысле), здесь же само множество $${[B\to A]}$$ определяется с учетом порядка и отлично от $$A^B$$. (В частности, при счетных $$A$$ и $$B$$ множество $${[B\hm\to A]}$$ счетно, а $$A^B$$ - нет.)
Явное описание множества $$[B\to A]$$ позволяет понять, как устроены его начальные отрезки, то есть какой вид имеют ординалы, меньшие $$\alpha^\beta$$.
Рассмотрим некоторую функцию $$f\hm\in [B\to A]$$. Пусть она отлична от нуля в точках $$b_1\hm>b_2\hm>\ldots\hm>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]\hm\times [0,a_1)$$, и при этом отождествлении сохраняется порядок.
Функции второго типа (равные $$a_1$$ в точке $$b_1$$ ) снова разбиваются на две категории: те, которые в точке $$b_2$$ меньше $$a_2$$ и те, которые в $$b_2$$ равны $$a_2$$. Функции первой категории отождествляются с элементами множества $$[[0,b_2)\to A]\hm\times [0,a_2)$$. Функции второй категории снова разобьем на части в зависимости от их значения в точке $$b_3$$ и т.д Таким образом, $$[0,f)$$ как упорядоченное множество изоморфно множеству $$\begin{align*} [[0,b_1)\to A]\times [0,a_1)+ [[0,b_2)\to A]\times [0,a_2)+\ldots+\\ +[[0,b_k)\to A]\times [0,a_k). \end{align*}$$ Переходя к ординалам (начальные отрезки - это меньшие ординалы), получаем такое утверждение:
Теорема 42. Всякий ординал, меньший $$\alpha^\beta$$, представляется в виде $$\alpha^{\beta_1}\alpha_1 + \alpha^{\beta_2}\alpha_2+\ldots+ \alpha^{\beta_k}\alpha_k$$, где $$\beta\hm>\beta_1\hm>\beta_2\hm>\ldots\hm>\beta_k$$, а $$\alpha_1,\alpha_2,\dots,\alpha_k\hm<\alpha$$. Такое представление однозначно и любая сумма указанного вида является ординалом, меньшим $$\alpha^\beta$$.
Доказательство. Возможность такого представления мы уже доказали. Последнее утверждение следует из того, что любая сумма такого вида является начальным отрезком в множестве $$[B\to A]$$ (где $$A$$ и $$B$$ упорядочены по типам $$\alpha$$ и $$\beta$$ ) и разным суммам соответствуют разные начальные отрезки.
Это утверждение обобщает описанную нами ранее " позиционную систему обозначений с основанием $$\alpha$$ " для ординалов, меньших $$\alpha^k$$ ; теперь вместо $$k$$ можно использовать любой ординал.
Можно было бы сразу сказать, что элементами множества $$[B\to A]$$ являются формальные суммы вида$$\alpha^{\beta_1}\alpha_1 + \alpha^{\beta_2}\alpha_2+\ldots+ \alpha^{\beta_k}\alpha_k$$ (где $$\beta\hm>\beta_1\hm>\ldots\hm>\beta_k$$ и $$\alpha_1,\dots,\alpha_k\hm<\alpha$$ ) с естественным порядком на них.
Теперь уже понятно, как устроены ординалы в последовательности$$\omega^\omega, \omega^{(\omega^\omega)},\ldots$$ Первый из них образован " одноэтажными" выражениями вида$$\omega^{b_1}a_1 + \omega^{b_2}a_2+\ldots+ \omega^{b_k}a_k,$$ где $$a_i$$ и $$b_i$$ - натуральные числа (и $$b_1\hm>\dots\hm>b_k$$ ). Если в качестве $$b_1, \dots, b_k$$ разрешить писать любые " одноэтажные" выражения указанного вида, то полученные " двухэтажные" выражения упорядочены по типу $$\omega^{(\omega^\omega)}$$. Разрешив в показателях двухэтажные выражения, мы получим трехэтажные выражения, которые образуют следующий ординал и т.д Если объединить все эти множества, то есть не ограничивать число этажей (которое для каждого выражения тем не менее конечно), то получится множество, упорядоченное по типу$$\sup(\omega, \omega^\omega, \omega^{(\omega^\omega)},\ldots)$$ Этот ординал обозначается $$\varepsilon_0$$.
140. Докажите, что$$\varepsilon_0 = \omega + \omega^\omega + \omega^{(\omega^\omega)}+\ldots$$
141. Определим для натуральных чисел операцию " тотальной замены основания $$k$$ на $$l$$ " (здесь $$k$$ и $$l$$ - натуральные числа, причем $$l\hm>k$$ ) следующим образом: данное число $$n$$ запишем в $$k$$ - ичной системе, то есть разложим по степеням $$k$$, показатели степеней снова запишем в $$k$$ - ичной системе, новые показатели также разложим и т.д. Затем на всех уровнях заменим основание $$k$$ на основание $$l$$ и вычислим значение получившегося выражения. Докажите, что начав с любого $$n$$ и выполняя последовательность операций " вычитание единицы - тотальная замена основания $$2$$ на $$3$$ - вычитание единицы - тотальная замена основания $$3$$ на $$4$$ - вычитание единицы - тотальная замена основания $$4$$ на $$5$$ -, $$\dots$$ ", мы рано или поздно зайдем в тупик,т.е. получится нуль и вычесть единицу будет нельзя. (Указание: заменим все основания сразу на ординал $$\omega$$ ; получится убывающая последовательность ординалов, меньших $$\varepsilon_0$$.)
Мы определили сложение и умножение ординалов с помощью явных конструкций порядка на соответствующих множествах. Вместо этого можно было бы их определить индуктивно.
Теорема 38.Сложение ординалов обладает следующими свойствами: $$\begin{align*} \alpha+ 0 = \alpha;\\ \alpha+(\beta+1) = (\alpha+\beta)+1;\\ \alpha+\gamma= \sup\{\alpha+\beta\mid \beta<\gamma\} \text{ для предельного $\gamma\hm\ne0$}. \end{align*}$$ Эти свойства однозначно определяют операцию сложения.
Доказательство. Два первых свойства очевидны; проверим третье. Если $$\beta\hm<\gamma$$, то $$\alpha\hm+\beta\hm<\alpha\hm+\gamma$$, так что $$\alpha\hm+\gamma$$ будет верхней границей всех сумм вида $$\alpha\hm+\beta$$ при $$\beta\hm<\gamma$$. Надо проверить, что эта граница точная. Пусть некоторый ординал $$\tau$$ меньше $$\alpha\hm+\gamma$$. Убедимся, что он меньше $$\alpha\hm+\beta$$ для некоторого $$\beta\hm<\gamma$$. Если $$\tau\hm<\alpha$$, все очевидно. Если $$\tau\hm\ge\alpha$$, представим его в виде $$\tau\hm=\alpha\hm+\sigma$$. Тогда $$\alpha\hm+\sigma \hm< \alpha\hm+\gamma$$ и потому $$\sigma\hm<\gamma$$. Поскольку ординал $$\gamma$$ предельный, $$\sigma\hm+1$$ также меньше $$\gamma$$ и остается положить $$\beta\hm=\sigma\hm+1$$.
Указанные свойства однозначно определяют операцию сложения, так
как представляют собой
Аналогично можно определить и умножение:
Теорема 39. Умножение ординалов обладает следующими свойствами: $$\begin{align*} \alpha 0 = 0;\\ \alpha(\beta+1) = \alpha\beta+\alpha;\\ \alpha\gamma= \sup\{\alpha\beta\mid \beta<\gamma\} \text{ для предельного $\gamma\hm\ne0$}. \end{align*}$$ Эти свойства однозначно определяют операцию умножения.
Доказательство. Доказательство аналогично, нужно только проверить, что если $$\tau\hm<\alpha\gamma$$ для предельного $$\gamma$$, то $$\tau\hm<\alpha\beta$$ для некоторого $$\beta\hm<\gamma$$. Как мы видели на с.101, ординал $$\tau$$ имеет вид $$\tau\hm=\alpha\gamma'\hm+\alpha'$$ при $$\gamma'\hm<\gamma$$ ; достаточно положить $$\beta\hm=\gamma'\hm+1$$.
Возникает естественное желание определить операцию возведения в степень. Мы уже по существу определили возведение в целую положительную степень ( $$\alpha^n$$ есть произведение $$n$$ сомножителей, равных $$\alpha$$ ). Другими словами, если $$A$$ упорядочено по типу $$\alpha$$, то множество $$A^n$$ последовательностей длины $$n$$ с элементами из $$A$$ с обратным лексикографическим порядком (сравнение справа налево) упорядочено по типу $$\alpha^n$$.
Следующий шаг- определить $$\alpha^\omega$$. Первая идея,
приходящая в голову- взять множество $$A^{\bbN}$$ бесконечных
последовательностей и определить на нем
Замечание. Тут опять мы подходим к опасной границе парадоксов и вынуждены выражаться уклончиво. На самом деле теорема о трансфинитной рекурсии говорила об определении функции на вполне упорядоченном множестве, а ординалы не образуют множества- их слишком много. Кроме того, в ней шла речь о функциях со значениями в некотором заданном множестве, которого здесь тоже нет. Подобные индуктивные определения можно корректно обосновать в теории множеств с использованием так называемой аксиомы подстановки, но мы об этом говорить не будем. Вместо этого мы дадим явное описание возведения в степень, свободное от этих проблем.
Чтобы понять смысл возведения в степень, посмотрим, как выглядит
ординал $$\alpha^\omega$$ (для некоторого $$\alpha$$ ). Пусть $$A$$ -
множество, упорядоченное по типу $$\alpha$$.
Ординал $$\alpha^\omega$$
по определению есть точная верхняя грань $$\alpha^n$$ для
натуральных $$n$$. Ординал $$\alpha^n$$ есть
Аналогичное утверждение верно и для любого показателя степени.
Пусть $$A$$ и $$B$$ - вполне упорядоченные множества, имеющие порядковые типы $$\alpha$$ и $$\beta$$. Рассмотрим множество $$[B\to A]$$ состоящее из отображений $$B$$ в $$A$$, имеющих " конечный носитель" (равных минимальному элементу $$A$$ всюду, за исключением конечного множества). Введем на $$[B\nolinebreak\to A]$$ порядок: если $$f_1\hm\ne f_2$$, выберем наибольший элемент $$b\hm\in B$$, для которого $$f_1(b)\hm\ne f_2(b)$$ и сравним $$f_1(b)$$ и $$f_2(b)$$.
Теорема 40.
Указанное правило задает
Доказательство. Нам надо проверить, что указанный порядок является полным и что выполнены требования индуктивного определения степени.
Назовем носителем элемента $$f\hm\in[B\to A]$$ множество тех $$b\hm\in B$$, для которых $$f(b)\hm>0$$ (здесь $$0$$ обозначает наименьший элемент множества $$A$$ ). Назовем рангом функции $$f$$ наибольший элемент носителя (по определению носитель конечен, так что наибольший элемент существует). Ранг определен для всех функций, кроме тождественно нулевой, которая является минимальным элементом множества $$[B\to A]$$. Чем больше ранг функции, тем больше сама функция в смысле введенного нами порядка.
Пусть порядок на $$[B\to A]$$ не является полным и $$f_0\hm>f_1\hm>f_2\hm>\ldots$$ - убывающая последовательность элементов $$[B\to A]$$. Все элементы $$f_i$$ отличны от $$0$$ ; рассмотрим их ранги. Эти ранги образуют невозрастающую последовательность, поэтому начиная с некоторого места стабилизируются (множество $$B$$ вполне упорядочено). Отбросим начальный отрезок и будем считать, что с самого начала ранги всех элементов убывающей последовательности одинаковы и равны некоторому $$b$$. В соответствии с определением, значения $$f_0(b), f_1(b),\dots$$ образуют невозрастающую последовательность, поэтому начиная с некоторого места стабилизируются. Отбросив начальный отрезок, будем считать, что все $$f_i$$ имеют одинаковый ранг $$b$$ и одинаковое значение $$f_i(b)$$. Тогда значения $$f_i(b)$$ не влияют на сравнения, и потому их можно заменить на $$0$$. Получим убывающую последовательность элементов $$[B\to A]$$ с рангами меньше $$b$$. Чтобы завершить рассуждение, остается сослаться на принцип индукции по множеству $$B$$.
(Более формально, рассмотрим все бесконечно убывающие последовательности. У каждой из них рассмотрим ранг первого элемента. Рассмотрим те из них, у которых этот ранг минимально возможный; пусть $$b$$ - это минимальное значение. В любой такой последовательности все элементы имеют ранг $$b$$. Из всех таких последовательностей $$f_0\hm>f_1\hm>\ldots$$ выберем ту, у которой значение $$f_0(b)$$ минимально; все следующие ее члены имеют то же значение в точке $$b$$ (т.е. $$f_i(b)\hm=f_0(b)$$ ). Заменив значение в точке $$b$$ нулем, получим бесконечную убывающую последовательность из элементов меньшего ранга, что противоречит предположению.)
Теперь покажем, что такое явное определение степени согласовано с индуктивным определением. Для конечных $$n$$ это очевидно. Пусть $$\gamma\hm=\beta\hm+1$$. Каково (явное) определение $$\alpha^\gamma$$? Пусть $$B$$ упорядочено по типу $$\beta$$. Тогда мы должны добавить к $$B$$ новый наибольший элемент (обозначим его $$m$$ ) и рассмотреть отображения $$B\cup\{m\}\to A$$ с конечным носителем. Ясно, что такое отображение задается парой, состоящей из его сужения на $$B$$ (которое может быть произвольным элементом множества $$[B\to A]$$ ) и значения на $$m$$. При определении порядка мы сначала сравниваем значения на $$m$$, а потом сужения на $$B$$, то есть полученное множество изоморфно $$[B\to A]\hm\times A$$, что и требовалось.
Пусть теперь $$\gamma$$ - ненулевой предельный ординал и
множество $$C$$ упорядочено
по типу $$\gamma$$. Как устроено множество $${[C\to A]}$$?
Элементы, ранг которых меньше $$c\hm\in C$$, образуют в нем
начальный отрезок, и этот начальный отрезок изоморфен $$[[0,c)\to
A]$$.
А само множество $$[C\to A]$$ является
объединением этих начальных отрезков (поскольку каждый элемент этого множества
имеет конечный носитель) и потому его
Непосредственным следствием этой теоремы является такое утверждение:
Теорема 41.Если $$\alpha$$ и $$\beta$$ - счетные ординалы, то $$\alpha+\beta$$, $$\alpha\beta$$ и $$\alpha^\beta$$ счетны.
Доказательство. Для суммы и произведения утверждение очевидно. Для степени: если мы пронумеровали все элементы вполне упорядоченных множеств $$A$$ и $$B$$, то любой элемент множества $$[B\to A]$$ может быть задан конечным списком натуральных чисел (носитель и значения на элементах носителя), а таких списков счетное число.
133. Докажите, что $$\alpha^{\beta+\gamma}=\alpha^\beta\cdot\alpha^\gamma$$ двумя способами: по индукции и с использованием явного определения степени.
134. Докажите, что $$(\alpha^\beta)^\gamma=\alpha^{\beta\gamma}$$.
135. Докажите, что если $$\alpha\ge2$$, то $$\alpha^\beta\ge\alpha\beta$$.
136. Докажите, что если $$\omega^\gamma=\alpha+\beta$$ для некоторых ординалов $$\alpha$$, $$\beta$$ и $$\gamma$$, то либо $$\beta=0$$, либо $$\beta=\omega^\gamma$$.
137. Какие ординалы нельзя представить в виде суммы двух меньших ординалов?
138. Докажите счетность $$\alpha^\beta$$ для счетных $$\alpha$$ и $$\beta$$, используя индуктивное определение степени.
139. Дан некоторый ординал $$\alpha\hm>1$$. Укажите наименьший ординал $$\beta\hm>0$$, для которого $$\alpha\beta\hm=\beta$$. (Указание: что будет, если умножить $$x$$ на степенной ряд $$1\hm+x\hm+x^2\hm+x^3\hm+\ldots$$?)
Отметим важную разницу между операцией возведения ординалов в степень и ранее рассмотренными операциями сложения и умножения ординалов. Определяя сумму и произведение ординалов, мы вводили некоторый порядок на сумме и произведении соответствующих множеств (в обычном смысле), здесь же само множество $${[B\to A]}$$ определяется с учетом порядка и отлично от $$A^B$$. (В частности, при счетных $$A$$ и $$B$$ множество $${[B\hm\to A]}$$ счетно, а $$A^B$$ - нет.)
Явное описание множества $$[B\to A]$$ позволяет понять, как устроены его начальные отрезки, то есть какой вид имеют ординалы, меньшие $$\alpha^\beta$$.
Рассмотрим некоторую функцию $$f\hm\in [B\to A]$$. Пусть она отлична от нуля в точках $$b_1\hm>b_2\hm>\ldots\hm>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]\hm\times [0,a_1)$$, и при этом отождествлении сохраняется порядок.
Функции второго типа (равные $$a_1$$ в точке $$b_1$$ ) снова разбиваются на две категории: те, которые в точке $$b_2$$ меньше $$a_2$$ и те, которые в $$b_2$$ равны $$a_2$$. Функции первой категории отождествляются с элементами множества $$[[0,b_2)\to A]\hm\times [0,a_2)$$. Функции второй категории снова разобьем на части в зависимости от их значения в точке $$b_3$$ и т.д Таким образом, $$[0,f)$$ как упорядоченное множество изоморфно множеству $$\begin{align*} [[0,b_1)\to A]\times [0,a_1)+ [[0,b_2)\to A]\times [0,a_2)+\ldots+\\ +[[0,b_k)\to A]\times [0,a_k). \end{align*}$$ Переходя к ординалам (начальные отрезки - это меньшие ординалы), получаем такое утверждение:
Теорема 42. Всякий ординал, меньший $$\alpha^\beta$$, представляется в виде $$\alpha^{\beta_1}\alpha_1 + \alpha^{\beta_2}\alpha_2+\ldots+ \alpha^{\beta_k}\alpha_k$$, где $$\beta\hm>\beta_1\hm>\beta_2\hm>\ldots\hm>\beta_k$$, а $$\alpha_1,\alpha_2,\dots,\alpha_k\hm<\alpha$$. Такое представление однозначно и любая сумма указанного вида является ординалом, меньшим $$\alpha^\beta$$.
Доказательство. Возможность такого представления мы уже доказали. Последнее утверждение следует из того, что любая сумма такого вида является начальным отрезком в множестве $$[B\to A]$$ (где $$A$$ и $$B$$ упорядочены по типам $$\alpha$$ и $$\beta$$ ) и разным суммам соответствуют разные начальные отрезки.
Это утверждение обобщает описанную нами ранее " позиционную систему обозначений с основанием $$\alpha$$ " для ординалов, меньших $$\alpha^k$$ ; теперь вместо $$k$$ можно использовать любой ординал.
Можно было бы сразу сказать, что элементами множества $$[B\to A]$$ являются формальные суммы вида$$\alpha^{\beta_1}\alpha_1 + \alpha^{\beta_2}\alpha_2+\ldots+ \alpha^{\beta_k}\alpha_k$$ (где $$\beta\hm>\beta_1\hm>\ldots\hm>\beta_k$$ и $$\alpha_1,\dots,\alpha_k\hm<\alpha$$ ) с естественным порядком на них.
Теперь уже понятно, как устроены ординалы в последовательности$$\omega^\omega, \omega^{(\omega^\omega)},\ldots$$ Первый из них образован " одноэтажными" выражениями вида$$\omega^{b_1}a_1 + \omega^{b_2}a_2+\ldots+ \omega^{b_k}a_k,$$ где $$a_i$$ и $$b_i$$ - натуральные числа (и $$b_1\hm>\dots\hm>b_k$$ ). Если в качестве $$b_1, \dots, b_k$$ разрешить писать любые " одноэтажные" выражения указанного вида, то полученные " двухэтажные" выражения упорядочены по типу $$\omega^{(\omega^\omega)}$$. Разрешив в показателях двухэтажные выражения, мы получим трехэтажные выражения, которые образуют следующий ординал и т.д Если объединить все эти множества, то есть не ограничивать число этажей (которое для каждого выражения тем не менее конечно), то получится множество, упорядоченное по типу$$\sup(\omega, \omega^\omega, \omega^{(\omega^\omega)},\ldots)$$ Этот ординал обозначается $$\varepsilon_0$$.
140. Докажите, что$$\varepsilon_0 = \omega + \omega^\omega + \omega^{(\omega^\omega)}+\ldots$$
141. Определим для натуральных чисел операцию " тотальной замены основания $$k$$ на $$l$$ " (здесь $$k$$ и $$l$$ - натуральные числа, причем $$l\hm>k$$ ) следующим образом: данное число $$n$$ запишем в $$k$$ - ичной системе, то есть разложим по степеням $$k$$, показатели степеней снова запишем в $$k$$ - ичной системе, новые показатели также разложим и т.д. Затем на всех уровнях заменим основание $$k$$ на основание $$l$$ и вычислим значение получившегося выражения. Докажите, что начав с любого $$n$$ и выполняя последовательность операций " вычитание единицы - тотальная замена основания $$2$$ на $$3$$ - вычитание единицы - тотальная замена основания $$3$$ на $$4$$ - вычитание единицы - тотальная замена основания $$4$$ на $$5$$ -, $$\dots$$ ", мы рано или поздно зайдем в тупик,т.е. получится нуль и вычесть единицу будет нельзя. (Указание: заменим все основания сразу на ординал $$\omega$$ ; получится убывающая последовательность ординалов, меньших $$\varepsilon_0$$.)
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.