Термины " индукция" и " рекурсия" часто употребляются вперемежку. Например, определение факториала $$n!=1\cdot2\cdot3\cdot\ldots\cdot n$$ как функции $$f(n)$$, для которой $$f(n)\hm=n\cdot f(n-1)$$ при $$n\hm>0$$ и $$f(0)\hm=1$$, называют и " индуктивным", и " рекурсивным". Мы будем стараться разграничивать эти слова так: если речь идет о доказательстве чего-то сначала для $$n\hm=0$$, затем для $$n\hm=1,2,\dots$$, причем каждое утверждение опирается на предыдущее, то это индукция. Если же мы определяем что-то сначала для $$n\hm=0$$, потом для $$n\hm=1,2,\dots$$, причем определение каждого нового значения использует ранее определенные, то это рекурсия.
Наша цель - научиться проводить индуктивные доказательства и
давать
Доказательства по индукции мы уже обсуждали, говоря о фундированных множествах (см. лекцию 8), и сейчас ограничимся только одним примером.
Теорема 17. Пусть $$A$$ - вполне упорядоченное множество, а $$f\colon A\hm\to A$$ - возрастающее отображение (то есть $$f(x)\hm<f(y)$$ при $$x\hm<y$$ ). Тогда $$f(x)\hm\ge x$$ для всех $$x\hm\in A$$.
Доказательство. Согласно принципу индукции (теорема 15) достаточно доказать неравенство $$f(x)\hm\ge x$$, предполагая, что $$f(y)\hm\ge y$$ при всех $$y\hm<x$$. Пусть это не так и $$f(x)\hm<x$$. Тогда по монотонности $$f(f(x))\hm<f(x)$$. Но, с другой стороны, элемент $$y\hm=f(x)$$ меньше $$x$$, и потому по предположению индукции $$f(y)\hm\ge y$$, то есть $$f(f(x))\hm\ge f(x)$$.
Если угодно, можно в явном виде воспользоваться существованием наименьшего элемента и изложить это же рассуждение так. Пусть утверждение теоремы неверно. Возьмем наименьшее $$x$$, для которого $$f(x)\hm<x$$. Но тогда $$f(f(x))\hm<f(x)$$ по монотонности и потому $$x$$ не является наименьшим вопреки предположению.
Наконец, это рассуждение можно пересказать и так: если $$x\hm>f(x)$$,то по монотонности$$x > f(x) > f(f(x)) > f(f(f(x))) > \ldots,$$ но бесконечных убывающих последовательностей в фундированном множестве быть не может.
Теперь перейдем к рекурсии. В определении факториала $$f(n)$$ выражалось
через $$f(n-1)$$. В общей ситуации значение $$f(n)$$
может использовать не только одно предыдущее значение функции,
но и все значения на меньших аргументах. Например, можно
определить функцию $$f\colon\bbN\hm\to\bbN$$, сказав, что $$f(n)$$ на единицу больше суммы всех предыдущих значений, то
есть $$f(n)\hm=f(0)\hm+f(1)\hm+\ldots\hm+f(n-1)\hm+1$$ ; это вполне
законное
112. Какую функцию $$f$$ задает такое определение?
Как обобщить эту схему на произвольные вполне упорядоченные
множества вместо натурального ряда? Пусть $$A$$ вполне
упорядочено. Мы хотим дать
Теорема 18. Пусть $$A$$ - вполне упорядоченное множество. Пусть $$B$$ - произвольное множество. Пусть имеется некоторое рекурсивное правило, то есть отображение $$F$$, которое ставит в соответствие элементу $$x\hm\in A$$ и функции $$g\colon [0,x)\hm\to B$$ некоторый элемент множества $$B$$. Тогда существует и единственна функция $$f\colon A\hm\to B$$, для которой$$f(x)= F(x,f|_{[0,x)})$$ при всех $$x\hm\in A$$. (Здесь $$f|_{[0,x)}$$ обозначает ограничение функции $$f$$ на начальный отрезок $$[0,x)$$ - мы отбрасываем все значения функции на элементах, больших или равных $$x$$.)
Доказательство. Неформально можно рассуждать так: значение $$f$$ на минимальном элементе определено однозначно, так как предыдущих значений нет (сужение $$f|_{[0,0)}$$ пусто). Тогда и на следующем элементе значение функции $$f$$ определено однозначно, поскольку на предыдущих (точнее, единственном предыдущем) функция $$f$$ уже задана, и т.д.
Конечно, это надо аккуратно выразить формально. Вот как это делается. Докажем по индукции такое утверждение о произвольном элементе $$a\hm\in A$$:
существует и единственно отображение $$f$$ отрезка $$[0,a]$$ в множество $$B$$, для которого
рекурсивное определение (равенство, приведенное в условии) выполнено при всех $$x\hm\in [0,a]$$.
Будем называть отображение $$f\colon [0,a]\hm\to B$$, обладающее указанным свойством, корректным. Таким образом, мы хотим доказать, что для каждого $$a\hm\in A$$ есть единственное корректное отображение отрезка $$[0,a]$$ в $$B$$.
Поскольку мы рассуждаем по индукции, можно предполагать, что для всех $$c<a$$ это утверждение выполнено, то есть существует и единственно корректное отображение $$f_c\colon [0,c]\hm\to B$$. (Корректность $$f_c$$ означает, что при всех $$d\hm\le c$$ значение $$f_с(d)$$ совпадает с предписанным по рекурсивному правилу.)
Рассмотрим отображения $$f_{c_1}$$ и $$f_{c_2}$$ для двух различных $$c_1$$ и $$c_2$$. Пусть, например, $$c_1\hm<c_2$$. Отображение $$f_{c_2}$$ определено на большем отрезке $$[0,c_2]$$. Если ограничить $$f_{c_2}$$ на меньший отрезок $$[0,c_1]$$, то оно совпадет с $$f_{c_1}$$, поскольку ограничение корректного отображения на меньший отрезок корректно (это очевидно), а мы предполагали единственность на отрезке $$[0,c_1]$$.
Таким образом, все отображения $$f_c$$ согласованы друг с другом, то есть принимают одинаковое значение, если определены одновременно. Объединив их, мы получаем некоторое единое отображение $$h$$, определенное на $$[0,a)$$. Применив к $$a$$ и $$h$$ рекурсивное правило, получим некоторое значение $$b\hm\in B$$. Доопределим $$h$$ в точке $$a$$, положив $$h(a)\hm=b$$. Получится отображение $$h\colon [0,a]\hm\to B$$ ; легко понять, что оно корректно.
Чтобы завершить индуктивный переход, надо проверить, что на
отрезке $$[0,a]$$
корректное отображение единственно. В самом деле, его
ограничения на отрезки $$[0,c]$$ при $$c\hm<a$$ должны
совпадать с $$f_c$$,
поэтому осталось проверить однозначность в точке $$a$$ -
что гарантируется
Осталось лишь заметить, что для разных $$a$$ корректные отображения отрезков $$[0,a]$$ согласованы друг с другом (сужение корректного отображения на меньший отрезок корректно, применяем единственность) и потому вместе задают некоторую функцию $$f\colon A\hm\to B$$, удовлетворяющую рекурсивному определению.
Существование доказано; единственность тоже понятна, так как ограничение этой функции на любой отрезок $$[0,a]$$ корректно и потому однозначно определено, как мы видели.
Прежде чем применить эту теорему и доказать, что из двух вполне упорядоченных множеств одно является отрезком другого, нам потребуется ее немного усовершенствовать. Нам надо предусмотреть ситуацию, когда рекурсивное правило не всюду определено. Пусть, например, мы определяем последовательность действительных чисел соотношением $$x_{n}\hm=\tg x_{n-1}$$ и начальным условием $$x_0\hm=a$$. При некоторых значениях $$a$$ может оказаться, что построение последовательности обрывается, поскольку тангенс не определен для соответствующего аргумента.
113. Докажите, что множество всех таких " исключительных" $$a$$ (когда последовательность конечна) счетно.
Аналогичная ситуация возможна и для общего случая.
Теорема 19. Пусть отображение $$F$$, о котором шла речь в теореме 18, является частичным (для некоторых $$x$$ и функций $$g\colon [0,x)\hm\to B$$ оно может быть не определено). Тогда существует функция $$f$$, которая
Доказательство. Это утверждение является обобщением, но одновременно и следствием предыдущей теоремы 18. В самом деле, добавим к множеству $$B$$ специальный элемент $$\bot$$ (" неопределенность") и модифицируем рекурсивное правило: новое правило дает значение $$\bot$$, когда старое было не определено. (Если среди значений функции на предыдущих аргументах уже встречалось $$\bot$$, новое рекурсивное правило тоже дает $$\bot$$.)
Применив теорему 18 к модифицированному правилу, получим некоторую функцию $$f'$$. Если эта функция нигде не принимает значения $$\bot$$, то реализуется первая из двух возможностей, указанных в теореме (при $$f\hm=f'$$ ). Если же функция $$f'$$ принимает значение $$\bot$$ в какой-то точке, то она имеет то же значение $$\bot$$ и во всех больших точках. Заменив значение $$\bot$$ на неопределенность, мы получаем из функции $$f'$$ функцию $$f$$. Область определения функции $$f$$ есть некоторый начальный отрезок $$[0,a)$$ и реализуется вторая возможность, указанная в формулировке теоремы.
114.Сформулируйте и докажите утверждение об однозначности функции, заданной частичным рекурсивным правилом.
Теперь у нас все готово для доказательства теоремы о сравнении вполне упорядоченных множеств.
Теорема. Пусть $$A$$ и $$B$$ - два вполне упорядоченных множества. Тогда либо $$A$$ изоморфно некоторому начальному отрезку множества $$B$$, либо $$B$$ изоморфно некоторому начальному отрезку множества $$A$$.
Доказательство. Отметим прежде всего, что начальный отрезок может совпадать со всем множеством, так что случай изоморфных множеств $$A$$ и $$B$$ также покрывается этой теоремой.
Определим отображение $$f$$ из $$A$$ в $$B$$ таким рекурсивным правилом: для любого $$a\hm\in A$$
$$f(a)$$ есть наименьший элемент множества $$B$$, который не встречается среди $$f(a')$$ при $$a'\hm<a$$.
Это правило не определено в том случае, когда значения $$f(a')$$ при $$a'\hm<a$$ покрывают все $$B$$. Применяя теорему 19, мы получаем функцию $$f$$, согласованную с этим правилом. Теперь рассмотрим два случая:
Таким образом, в обоих случаях утверждение теоремы верно.
Может ли быть так, что $$A$$ изоморфно начальному отрезку $$B$$, а $$B$$ изоморфно начальному отрезку $$A$$? Нет - за исключением тривиального случая, когда начальные отрезки представляют собой сами множества $$A$$ и $$B$$. Это вытекает из такого утверждения:
Теорема 21. Никакое вполне упорядоченное множество не изоморфно своему начальному отрезку (не совпадающему со всем множеством).
Доказательство. Пусть вполне упорядоченное множество $$A$$ изоморфно своему начальному отрезку, не совпадающему со всем множеством. Как мы видели на с. 67, этот отрезок имеет вид $$[0,a)$$ для некоторого элемента $$a\hm\in A$$. Пусть $$f\colon A\hm\to[0,a)$$ - изоморфизм. Тогда $$f$$ строго возрастает, и по теореме 17 имеет место неравенство $$f(a)\ge a$$, что противоречит тому, что множество значений функции $$f$$ есть $$[0,a)$$.
Если множество $$A$$ изоморфно начальному отрезку множества $$B$$, а множество $$B$$ изоморфно начальному отрезку множества $$A$$, то композиция этих изоморфизмов дает изоморфизм между множеством $$A$$ и его начальным отрезком (начальный отрезок начального отрезка есть начальный отрезок). Этот начальный отрезок обязан совпадать со всем множеством $$A$$, так что это возможно лишь если $$A$$ и $$B$$ изоморфны.
Сказанное позволяет сравнивать вполне упорядоченные множества. Если $$A$$ изоморфно начальному отрезку множества $$B$$, не совпадающему со всем $$B$$, то говорят, что порядковый тип множества $$A$$ меньше порядкового типа множества $$B$$ . Если множества $$A$$ и $$B$$ изоморфны, то говорят, что у них одинаковые порядковые типы. Наконец, если $$B$$ изоморфно начальному отрезку множества $$A$$, то говорят, что порядковый тип множества $$A$$ больше порядкового типа множества $$B$$ . Как мы только что доказали, верно такое утверждение:
Теорема 22. Для любых вполне упорядоченных множеств $$A$$ и $$B$$ имеет место ровно один из указанных трех случаев.
Если временно забыть о проблемах оснований теории множеств и
определить
Теорема 23. Всякое непустое семейство вполне упорядоченных множеств имеет " наименьший элемент" - множество, изоморфное начальным отрезкам всех остальных множеств.
Доказательство. Возьмем какое-то множество $$X$$ семейства. Если оно наименьшее, то все доказано. Если нет, рассмотрим все множества семейства, которые меньше его, то есть изоморфны его начальным отрезкам вида $$[0,x)$$. Среди всех таких элементов $$x$$ выберем наименьший. Тогда соответствующее ему множество и будет наименьшим.
Следствием доказанных теорем является то, что любые два вполне упорядоченных множества сравнимы по мощности (одно равномощно подмножеству другого). Сейчас мы увидим, что всякое множество может быть вполне упорядочено (теорема Цермело), и, следовательно, любые два множества сравнимы по мощности.
Термины " индукция" и " рекурсия" часто употребляются вперемежку. Например, определение факториала $$n!=1\cdot2\cdot3\cdot\ldots\cdot n$$ как функции $$f(n)$$, для которой $$f(n)\hm=n\cdot f(n-1)$$ при $$n\hm>0$$ и $$f(0)\hm=1$$, называют и " индуктивным", и " рекурсивным". Мы будем стараться разграничивать эти слова так: если речь идет о доказательстве чего-то сначала для $$n\hm=0$$, затем для $$n\hm=1,2,\dots$$, причем каждое утверждение опирается на предыдущее, то это индукция. Если же мы определяем что-то сначала для $$n\hm=0$$, потом для $$n\hm=1,2,\dots$$, причем определение каждого нового значения использует ранее определенные, то это рекурсия.
Наша цель - научиться проводить индуктивные доказательства и
давать
Доказательства по индукции мы уже обсуждали, говоря о фундированных множествах (см. лекцию 8), и сейчас ограничимся только одним примером.
Теорема 17. Пусть $$A$$ - вполне упорядоченное множество, а $$f\colon A\hm\to A$$ - возрастающее отображение (то есть $$f(x)\hm<f(y)$$ при $$x\hm<y$$ ). Тогда $$f(x)\hm\ge x$$ для всех $$x\hm\in A$$.
Доказательство. Согласно принципу индукции (теорема 15) достаточно доказать неравенство $$f(x)\hm\ge x$$, предполагая, что $$f(y)\hm\ge y$$ при всех $$y\hm<x$$. Пусть это не так и $$f(x)\hm<x$$. Тогда по монотонности $$f(f(x))\hm<f(x)$$. Но, с другой стороны, элемент $$y\hm=f(x)$$ меньше $$x$$, и потому по предположению индукции $$f(y)\hm\ge y$$, то есть $$f(f(x))\hm\ge f(x)$$.
Если угодно, можно в явном виде воспользоваться существованием наименьшего элемента и изложить это же рассуждение так. Пусть утверждение теоремы неверно. Возьмем наименьшее $$x$$, для которого $$f(x)\hm<x$$. Но тогда $$f(f(x))\hm<f(x)$$ по монотонности и потому $$x$$ не является наименьшим вопреки предположению.
Наконец, это рассуждение можно пересказать и так: если $$x\hm>f(x)$$,то по монотонности$$x > f(x) > f(f(x)) > f(f(f(x))) > \ldots,$$ но бесконечных убывающих последовательностей в фундированном множестве быть не может.
Теперь перейдем к рекурсии. В определении факториала $$f(n)$$ выражалось
через $$f(n-1)$$. В общей ситуации значение $$f(n)$$
может использовать не только одно предыдущее значение функции,
но и все значения на меньших аргументах. Например, можно
определить функцию $$f\colon\bbN\hm\to\bbN$$, сказав, что $$f(n)$$ на единицу больше суммы всех предыдущих значений, то
есть $$f(n)\hm=f(0)\hm+f(1)\hm+\ldots\hm+f(n-1)\hm+1$$ ; это вполне
законное
112. Какую функцию $$f$$ задает такое определение?
Как обобщить эту схему на произвольные вполне упорядоченные
множества вместо натурального ряда? Пусть $$A$$ вполне
упорядочено. Мы хотим дать
Теорема 18. Пусть $$A$$ - вполне упорядоченное множество. Пусть $$B$$ - произвольное множество. Пусть имеется некоторое рекурсивное правило, то есть отображение $$F$$, которое ставит в соответствие элементу $$x\hm\in A$$ и функции $$g\colon [0,x)\hm\to B$$ некоторый элемент множества $$B$$. Тогда существует и единственна функция $$f\colon A\hm\to B$$, для которой$$f(x)= F(x,f|_{[0,x)})$$ при всех $$x\hm\in A$$. (Здесь $$f|_{[0,x)}$$ обозначает ограничение функции $$f$$ на начальный отрезок $$[0,x)$$ - мы отбрасываем все значения функции на элементах, больших или равных $$x$$.)
Доказательство. Неформально можно рассуждать так: значение $$f$$ на минимальном элементе определено однозначно, так как предыдущих значений нет (сужение $$f|_{[0,0)}$$ пусто). Тогда и на следующем элементе значение функции $$f$$ определено однозначно, поскольку на предыдущих (точнее, единственном предыдущем) функция $$f$$ уже задана, и т.д.
Конечно, это надо аккуратно выразить формально. Вот как это делается. Докажем по индукции такое утверждение о произвольном элементе $$a\hm\in A$$:
существует и единственно отображение $$f$$ отрезка $$[0,a]$$ в множество $$B$$, для которого
рекурсивное определение (равенство, приведенное в условии) выполнено при всех $$x\hm\in [0,a]$$.
Будем называть отображение $$f\colon [0,a]\hm\to B$$, обладающее указанным свойством, корректным. Таким образом, мы хотим доказать, что для каждого $$a\hm\in A$$ есть единственное корректное отображение отрезка $$[0,a]$$ в $$B$$.
Поскольку мы рассуждаем по индукции, можно предполагать, что для всех $$c<a$$ это утверждение выполнено, то есть существует и единственно корректное отображение $$f_c\colon [0,c]\hm\to B$$. (Корректность $$f_c$$ означает, что при всех $$d\hm\le c$$ значение $$f_с(d)$$ совпадает с предписанным по рекурсивному правилу.)
Рассмотрим отображения $$f_{c_1}$$ и $$f_{c_2}$$ для двух различных $$c_1$$ и $$c_2$$. Пусть, например, $$c_1\hm<c_2$$. Отображение $$f_{c_2}$$ определено на большем отрезке $$[0,c_2]$$. Если ограничить $$f_{c_2}$$ на меньший отрезок $$[0,c_1]$$, то оно совпадет с $$f_{c_1}$$, поскольку ограничение корректного отображения на меньший отрезок корректно (это очевидно), а мы предполагали единственность на отрезке $$[0,c_1]$$.
Таким образом, все отображения $$f_c$$ согласованы друг с другом, то есть принимают одинаковое значение, если определены одновременно. Объединив их, мы получаем некоторое единое отображение $$h$$, определенное на $$[0,a)$$. Применив к $$a$$ и $$h$$ рекурсивное правило, получим некоторое значение $$b\hm\in B$$. Доопределим $$h$$ в точке $$a$$, положив $$h(a)\hm=b$$. Получится отображение $$h\colon [0,a]\hm\to B$$ ; легко понять, что оно корректно.
Чтобы завершить индуктивный переход, надо проверить, что на
отрезке $$[0,a]$$
корректное отображение единственно. В самом деле, его
ограничения на отрезки $$[0,c]$$ при $$c\hm<a$$ должны
совпадать с $$f_c$$,
поэтому осталось проверить однозначность в точке $$a$$ -
что гарантируется
Осталось лишь заметить, что для разных $$a$$ корректные отображения отрезков $$[0,a]$$ согласованы друг с другом (сужение корректного отображения на меньший отрезок корректно, применяем единственность) и потому вместе задают некоторую функцию $$f\colon A\hm\to B$$, удовлетворяющую рекурсивному определению.
Существование доказано; единственность тоже понятна, так как ограничение этой функции на любой отрезок $$[0,a]$$ корректно и потому однозначно определено, как мы видели.
Прежде чем применить эту теорему и доказать, что из двух вполне упорядоченных множеств одно является отрезком другого, нам потребуется ее немного усовершенствовать. Нам надо предусмотреть ситуацию, когда рекурсивное правило не всюду определено. Пусть, например, мы определяем последовательность действительных чисел соотношением $$x_{n}\hm=\tg x_{n-1}$$ и начальным условием $$x_0\hm=a$$. При некоторых значениях $$a$$ может оказаться, что построение последовательности обрывается, поскольку тангенс не определен для соответствующего аргумента.
113. Докажите, что множество всех таких " исключительных" $$a$$ (когда последовательность конечна) счетно.
Аналогичная ситуация возможна и для общего случая.
Теорема 19. Пусть отображение $$F$$, о котором шла речь в теореме 18, является частичным (для некоторых $$x$$ и функций $$g\colon [0,x)\hm\to B$$ оно может быть не определено). Тогда существует функция $$f$$, которая
Доказательство. Это утверждение является обобщением, но одновременно и следствием предыдущей теоремы 18. В самом деле, добавим к множеству $$B$$ специальный элемент $$\bot$$ (" неопределенность") и модифицируем рекурсивное правило: новое правило дает значение $$\bot$$, когда старое было не определено. (Если среди значений функции на предыдущих аргументах уже встречалось $$\bot$$, новое рекурсивное правило тоже дает $$\bot$$.)
Применив теорему 18 к модифицированному правилу, получим некоторую функцию $$f'$$. Если эта функция нигде не принимает значения $$\bot$$, то реализуется первая из двух возможностей, указанных в теореме (при $$f\hm=f'$$ ). Если же функция $$f'$$ принимает значение $$\bot$$ в какой-то точке, то она имеет то же значение $$\bot$$ и во всех больших точках. Заменив значение $$\bot$$ на неопределенность, мы получаем из функции $$f'$$ функцию $$f$$. Область определения функции $$f$$ есть некоторый начальный отрезок $$[0,a)$$ и реализуется вторая возможность, указанная в формулировке теоремы.
114.Сформулируйте и докажите утверждение об однозначности функции, заданной частичным рекурсивным правилом.
Теперь у нас все готово для доказательства теоремы о сравнении вполне упорядоченных множеств.
Теорема. Пусть $$A$$ и $$B$$ - два вполне упорядоченных множества. Тогда либо $$A$$ изоморфно некоторому начальному отрезку множества $$B$$, либо $$B$$ изоморфно некоторому начальному отрезку множества $$A$$.
Доказательство. Отметим прежде всего, что начальный отрезок может совпадать со всем множеством, так что случай изоморфных множеств $$A$$ и $$B$$ также покрывается этой теоремой.
Определим отображение $$f$$ из $$A$$ в $$B$$ таким рекурсивным правилом: для любого $$a\hm\in A$$
$$f(a)$$ есть наименьший элемент множества $$B$$, который не встречается среди $$f(a')$$ при $$a'\hm<a$$.
Это правило не определено в том случае, когда значения $$f(a')$$ при $$a'\hm<a$$ покрывают все $$B$$. Применяя теорему 19, мы получаем функцию $$f$$, согласованную с этим правилом. Теперь рассмотрим два случая:
Таким образом, в обоих случаях утверждение теоремы верно.
Может ли быть так, что $$A$$ изоморфно начальному отрезку $$B$$, а $$B$$ изоморфно начальному отрезку $$A$$? Нет - за исключением тривиального случая, когда начальные отрезки представляют собой сами множества $$A$$ и $$B$$. Это вытекает из такого утверждения:
Теорема 21. Никакое вполне упорядоченное множество не изоморфно своему начальному отрезку (не совпадающему со всем множеством).
Доказательство. Пусть вполне упорядоченное множество $$A$$ изоморфно своему начальному отрезку, не совпадающему со всем множеством. Как мы видели на с. 67, этот отрезок имеет вид $$[0,a)$$ для некоторого элемента $$a\hm\in A$$. Пусть $$f\colon A\hm\to[0,a)$$ - изоморфизм. Тогда $$f$$ строго возрастает, и по теореме 17 имеет место неравенство $$f(a)\ge a$$, что противоречит тому, что множество значений функции $$f$$ есть $$[0,a)$$.
Если множество $$A$$ изоморфно начальному отрезку множества $$B$$, а множество $$B$$ изоморфно начальному отрезку множества $$A$$, то композиция этих изоморфизмов дает изоморфизм между множеством $$A$$ и его начальным отрезком (начальный отрезок начального отрезка есть начальный отрезок). Этот начальный отрезок обязан совпадать со всем множеством $$A$$, так что это возможно лишь если $$A$$ и $$B$$ изоморфны.
Сказанное позволяет сравнивать вполне упорядоченные множества. Если $$A$$ изоморфно начальному отрезку множества $$B$$, не совпадающему со всем $$B$$, то говорят, что порядковый тип множества $$A$$ меньше порядкового типа множества $$B$$ . Если множества $$A$$ и $$B$$ изоморфны, то говорят, что у них одинаковые порядковые типы. Наконец, если $$B$$ изоморфно начальному отрезку множества $$A$$, то говорят, что порядковый тип множества $$A$$ больше порядкового типа множества $$B$$ . Как мы только что доказали, верно такое утверждение:
Теорема 22. Для любых вполне упорядоченных множеств $$A$$ и $$B$$ имеет место ровно один из указанных трех случаев.
Если временно забыть о проблемах оснований теории множеств и
определить
Теорема 23. Всякое непустое семейство вполне упорядоченных множеств имеет " наименьший элемент" - множество, изоморфное начальным отрезкам всех остальных множеств.
Доказательство. Возьмем какое-то множество $$X$$ семейства. Если оно наименьшее, то все доказано. Если нет, рассмотрим все множества семейства, которые меньше его, то есть изоморфны его начальным отрезкам вида $$[0,x)$$. Среди всех таких элементов $$x$$ выберем наименьший. Тогда соответствующее ему множество и будет наименьшим.
Следствием доказанных теорем является то, что любые два вполне упорядоченных множества сравнимы по мощности (одно равномощно подмножеству другого). Сейчас мы увидим, что всякое множество может быть вполне упорядочено (теорема Цермело), и, следовательно, любые два множества сравнимы по мощности.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.