Геркулес и гидра (что такое ординалы)
Feb. 26th, 2002 09:11 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaНесколько дней назад я предложил задачу о Геркулесе и гидре; на следующий день я записал в дневнике решение, которое использует ординальную арифметику — которую меня попросили объяснить для тех, кто с этим незнаком, но хочет понять решение. Я попробую это сделать, на очень элементарном уровне, в этой записи. Отдельно - не здесь, а в другой записи - мне ещё предстоит объяснить, почему у этой задачи нет простого решения, и почему использование ординалов, или сопоставимых с ними по сложности математических абстракций, неизбежно при решении этой задачи.
Сначала немного мотивации. Предположим, что мне удалось бы найти некий способ пронумеровать деревья - присвоить натуральное число f(T) каждому дереву-гидре T - так, чтобы после операции отсечения головы и приращения новых число гидры всегда уменьшалось бы. Тогда задача была бы решена, т.к. бесконечной нисходящей последовательности натуральных чисел не бывает. Интуитивно это очевидно: если, например, последовательность натуральных чисел начинается с миллиона и всё время уменьшается, в ней не может быть больше миллиона членов. С формальной точки зрения это происходит потому, что множество натуральных чисел N вместе с порядком между его членами (т.е. отношением, задающим, какие члены больше каких других) вполне упорядоченно (по-английски well-ordered). Например, множество целых чисел Z не вполне упорядоченно: в нём есть бесконечная нисходящая последовательность -1, -2, -3, -4, ... .
Вполне упорядоченные множества тесно связаны с принципом математической индукции. В случае натуральных чисел этот принцип гласит следующее. Пусть некое утверждение верно для числа 0; кроме того, если оно верно для всех натуральных чисел меньше n, то оно верно и для n. Тогда это утверждение верно для всех натуральных чисел. Но почему это так - почему принцип верен? Предположим, что его заключение неверно, что есть число n0, для которого утверждение не выполняется. Тогда должно быть какое-то число n1 меньше его, для которого оно тоже не выполняется (иначе по условию оно выполнялось бы для n0). Тогда в свою очередь должно найтись n2 < n1, для к-го условие не выполняется, и так далее; эта цепочка никогда не может завершиться на нуле, т.к. для него дано, что условие выполняется; поэтому неизбежно выстраивается бесконечная нисходящая последовательность n0 > n1 > n2 > ..., что как раз и противоречит вполне-упорядоченности натуральных чисел.
Однако оказывается, что решить задачу этим способом - нахождением подходящей нумерации деревьев - невозможно (о том, почему, будет рассказано отдельно). Но натуральные числа - не единственное возможное вполне упорядоченное множество. Мы можем присвоить деревьям не числовые значения, а какие-то другие абстрактные значения из некоторого множества M, на котором определён порядок между членами. Если при этом будет соблюдаться условие, что значение гидры уменьшается после любого хода Геркулеса, и если множество M вполне упорядочено - в нём не бывает бесконечных нисходящих последовательностей - то это решает задачу столь же хорошо, как и нумерация натуральными числами, по той же самой причине: Геркулес не сможет рубить головы бесконечно долго, т.к. это позволило бы построить бесконечную нисходящую последовательность членов M.
Для этого нам и нужны ординалы.
Ординалы возникают в теории множеств в качестве абстракции понятия вполне-упорядоченного множества.
Давайте начнём с конечных множеств. Вот начальный отрезок из натуральных чисел:
0 1 2 3 4 5 6
На него можно посмотреть как на множество из семи объектов — не обращая внимания на порядок между ними. Такому взгляду на множества соответствуют кардинальные числа, измеряющие размеры множеств; кардинальное число этого множества - 7, т.к. у него семь членов.
Но можно на него посмотреть и как на упорядоченное множество из семи членов: 0 < 1 < 2 < 3 < 4 < 5 < 6.
Любые два упорядоченных множества из семи членов - будь то семь натуральных чисел, семь точек на прямой или семь любых других объектов, выставленных в каком-либо порядке - изоморфны между собой, то есть между ними всегда можно построить однозначное соответствие, сохраняющее порядок:
Ординальное число 7 - в отличие от кардинального числа 7 - являет собой каноническое вполне-упорядоченное множество из семи элементов - например, <0 1 2 3 4 5 6>. Ординальные числа являются абстрактизацией идеи вполне-упорядоченного множества: если есть два разных вполне-упорядоченных множества, которые изоморфны друг другу - т.е. с точки зрения порядка членов они как бы "одно и то же" - то они обязаны соответствовать одному и тому же, идентичному ординальному числу.
Пока мы говорим о конечных множествах, никакой разницы между кардинальными и ординальными числами нет, потому что любые два способа упорядочить конечное множество приводят к изоморфным (и вполне-упорядоченным) результатам. То есть в случае конечного множества его размер (кол-во членов, кардинальность) как бы определяет полностью его структуру, добавление порядка между членами ничего нового сообщить нам не может. По-настоящему важными ординальные числа становятся в бесконечном случае.
Выстроим цепочку ординальных чисел:
И теперь построим новое, объединяющее все обозначенные выше, которое называется омега (w):
Омега является порядковым типом множества всех натуральных чисел. Теперь добавим "в конце" ещё один объект:
В качестве упорядоченного множества w+1 выглядит так: сначала идут все натуральные числа, а "после них", после того как "все они кончатся", ещё один объект, который больше их всех. Я его здесь обозначил буквой a для простоты; формальный подход немного запутанней.
Это самое "после них" может быть трудным для понимания, но важно понять, что это всего лишь метафора. Мы не отсчитываем на самом деле все натуральные числа одно за другим (такой процесс никогда бы не завершился), мы просто вводим новый член множества, который по определению больше всех, которые есть до сих пор (хоть их и бесконечное множество).
С одной стороны, любое упорядоченное множество, которое "устроено" таким же способом - сначала бесконечное счётное множество объектов, а потом ещё один, больше их всех - будет изоморфно w+1. С другой стороны, упорядоченное множество w+1 не изоморфно w. Не существует взаимно однозначного соответствия между w+1 и w (множеством натуральных чисел), сохраняющего порядок. Это легко видеть хотя бы потому, что у w+1 есть наибольший член, который больше всех остальных, а у w такого нет, поэтому куда бы этот наибольший член a ни "поставить" в таком соответсвии внутри w, там всегда будут числа больше его, в то время как в w+1 больше его ничего нет - порядок нарушится.
С другой стороны, размер, он же кардинальность, у множеств w и w+1 одинаковый, и равен размеру множества натуральных чисел. Иными словами, множество w+1 можно пересчитать, подставив ему в соответсвие натуральные числа из w:
Таким образом все члены w+1 "пересчитываются" при помощи членов w, и поэтому размер у них одинаковый. Но такое соответствие не сохраняет отношения порядка между членами. Тип размерности у них одинаковый, а порядковый тип - разный. Т.е. на бесконечных множествах понятия кардинала и ординала расходятся; ординалы более скрупулезно различают разные множества. Если у двух множеств один и тот же порядковый тип-ординал, т.е. если они изоморфны, то размер у них уж точно одинаковый; но обратное неверно.
Важно заметить также, что множество w+1 остаётся вполне упорядоченным. В нём нет бесконечных нисходящих последовательностей. В самом деле, мы можем начать такую последовательность членом a, но потом нам неизбежно придётся "прыгнуть" куда-то внутрь натуральных чисел, и куда бы мы не прыгнули, оттуда останется только конечное кол-во мест спускаться дальше.
Построение ординалов можно продолжить:
Например, w+123 "выглядит" так: "сначала" все натуральные числа w, а "после них" и больше их всех ещё 123 выстроенных в каком-то порядке объекта (к-е я здесь пометил латинскими буквами, но на самом деле их природа неважна, важно только отношение порядка между ними).
w+w "выглядит" так: сначала все натуральные числа, а потом "за ними" и больше их всех ещё одна копия натуральных чисел. Даже и это множество остаётся вполне упорядоченным. В нём невозможно построить бесконечную нисходящую последовательность. Где бы её не начать, например, во второй копии w, через конечное число шагов придётся спуститься куда-нибудь в первую, где тоже останется только конечное число шагов.
Я опускаю, здесь и далее, доказательство того, что все эти множества действительно разные ординалы, т.е. что они не изоморфны друг другу, они действительно представляют собой существенно разные способы упорядочить объекты. Интуитивно в этом легко убедиться.
Продолжая (заменяю теперь латинские буквы числами для удобства, но надо понимать, что это разные копии w и потому "разные" числа):
Сокращая и подразумевая всегда под w копию всего множества натуральных чисел:
Совершая как бы новый предельный прыжок, мы приходим к ординальному числу w*w, которое "выглядит" так: копия натуральных чисел, за ней ещё одна, и ещё, и ещё, и так бесконечное число раз. Даже и это множество остаётся вполне упорядоченным. Пытаясь построить в нём нисходящую последовательность, мы неизбежно выбираем первый член в какой-то из копий w, например в 127-й; после этого мы можем только конечное число раз спускаться в каждой копии, и у нас есть только 127 копий, в которых спускаться; поэтому через конечное число шагов мы придём в начало.
Обозначим w2 = w*w.
Далее:
Таким образом можно продолжать и дальше. Повторяя бесконечное число копий w3 одна за другой, получим w4, повторяя его - w5, и так далее. Каждый такой повтор добавляет огромное количество предельных переходов "внутрь" порядка, оценить которые интуитивно становится очень нелегко уже на стадии w2. Тем не менее можно убедиться (подробно объяснять это я уже не буду), что все возникающее множества-ординалы остаются хорошо упорядоченными. Несмотря на гигантское множество разных бесконечностей, таящихся в них, можно построить только конечные по длине нисходящие последовательности членов.
Более того, все эти множества остаются счётными по размеру. То есть по количеству членов в них они все равны между собой и равны w. Их все можно "перенумеровать" натуральными числами, хотя такие нумерации не будут, конечно, сохранять порядок членов.
Если взять предел
то мы получим ординал ww. От него можно продолжить дальше: ww+1 ...
ww + w ... ww + w2 ... ww + ww ... ww + ww + ww ... ww*w = ww+1.
На этом этапе уже совсем практически невозможно оценить "на глаз" внутреннюю структуру порядков этих ординалов, такой она становится сложной. Но отсюда можно продолжать и дальше и дойти постепенно до ww*w, ww*w*w, и в пределе этого - www.
Продолжая всё тот же процесс добавления копий меньших ординалов и перехода к пределу, мы приходим к ординалам wwww, wwwww, wwwwww и т.д.
Наконец, взяв предел этой последовательности "лесенок" степеней ординалов, мы получаем ординал, больший их всех, который называется эпсилон-ноль - ε0. От него тоже можно продолжать дальше и строить, скажем, ε0+1 и т.п., но это нам уже не нужно. Важно понять, что ε0 является ординалом, который объединяет в себе все возможные комбинации натуральных чисел, w и степеней w. Начиная с w, можно складывать, умножать и возводить в степень друг друга сколько угодно раз, и никогда не выйдешь за пределы ε0.
И все эти ординалы, включая ε0, остаются вполне упорядоченными множествами.
Более того, между самими ординалами (а не только между их членами) можно определить отношение порядка: какой ординал меньше какого другого. Собственно, это получается тривиально после очень важного результата: если есть два ординала A и B, то либо A является начальным сегментом B (в качестве упорядоченного множества), либо B является начальным сегментом A, либо они идентичны. Доказывать строго я это не буду, но объяснить на примерах это можно весьма убедительно. Например, w является начальным сегментом ординалов w+1, w+w, w2, w2+w+1, ww и т.п. - собственно все ординалы, кроме конечных натуральных чисел, начинаются с копии w, как легко видеть из нашего построения их выше. Ординал w2+w+1 является начальным сегментом ординала w3. И вообще благодаря тому, что мы всегда строили новые ординалы пристроением справа к уже существующим, очевидно, что они выстраиваются таким образом в упорядоченную цепочку. И все ординалы меньше ε0 являются начальными сегментами (каждый из них - разным начальным сегментом) ординала ε0, который включает их всех.
Из этого следует, что невозможно построить нисходящую цепочку ординалов меньше ε0 (а не только членов какого-то одного ординала). Если бы была такая цепочка ординалов, можно было бы посмотреть на неё "внутри" ε0, который содержит их всех, и выстроить с её помощью нисходящую цепочку его членов (здесь есть несколько технических подробностей, к-е я опускаю, но идея должна быть ясна).
Тут мы и приходим к решению задачи о Геркулесе и гидре. Каждому дереву-гидре мы ставим в соответствие ординал, путём, описанным в решении задачи; при этом мы всё время рекурсивно возводим в степени и складываем, и поэтому никогда не выходим за пределы ε0, все получающиеся ординалы меньше ε0 (более того, как легко проверить, любой ординал меньше ε0 образуется с помощью какой-то гидры - но это сейчас не важно). Операция отсечения головы и вырастания новых уменьшает ординал дерева (опять-таки см. решение). Поэтому, если бы Геркулес мог бесконечно долго рубить гидру, мы могли бы построить бесконечную нисходящую последовательность ординалов, что невозможно. Что и требовалось доказать.
Вопросы и предложения принимаются.
Сначала немного мотивации. Предположим, что мне удалось бы найти некий способ пронумеровать деревья - присвоить натуральное число f(T) каждому дереву-гидре T - так, чтобы после операции отсечения головы и приращения новых число гидры всегда уменьшалось бы. Тогда задача была бы решена, т.к. бесконечной нисходящей последовательности натуральных чисел не бывает. Интуитивно это очевидно: если, например, последовательность натуральных чисел начинается с миллиона и всё время уменьшается, в ней не может быть больше миллиона членов. С формальной точки зрения это происходит потому, что множество натуральных чисел N вместе с порядком между его членами (т.е. отношением, задающим, какие члены больше каких других) вполне упорядоченно (по-английски well-ordered). Например, множество целых чисел Z не вполне упорядоченно: в нём есть бесконечная нисходящая последовательность -1, -2, -3, -4, ... .
Вполне упорядоченные множества тесно связаны с принципом математической индукции. В случае натуральных чисел этот принцип гласит следующее. Пусть некое утверждение верно для числа 0; кроме того, если оно верно для всех натуральных чисел меньше n, то оно верно и для n. Тогда это утверждение верно для всех натуральных чисел. Но почему это так - почему принцип верен? Предположим, что его заключение неверно, что есть число n0, для которого утверждение не выполняется. Тогда должно быть какое-то число n1 меньше его, для которого оно тоже не выполняется (иначе по условию оно выполнялось бы для n0). Тогда в свою очередь должно найтись n2 < n1, для к-го условие не выполняется, и так далее; эта цепочка никогда не может завершиться на нуле, т.к. для него дано, что условие выполняется; поэтому неизбежно выстраивается бесконечная нисходящая последовательность n0 > n1 > n2 > ..., что как раз и противоречит вполне-упорядоченности натуральных чисел.
Однако оказывается, что решить задачу этим способом - нахождением подходящей нумерации деревьев - невозможно (о том, почему, будет рассказано отдельно). Но натуральные числа - не единственное возможное вполне упорядоченное множество. Мы можем присвоить деревьям не числовые значения, а какие-то другие абстрактные значения из некоторого множества M, на котором определён порядок между членами. Если при этом будет соблюдаться условие, что значение гидры уменьшается после любого хода Геркулеса, и если множество M вполне упорядочено - в нём не бывает бесконечных нисходящих последовательностей - то это решает задачу столь же хорошо, как и нумерация натуральными числами, по той же самой причине: Геркулес не сможет рубить головы бесконечно долго, т.к. это позволило бы построить бесконечную нисходящую последовательность членов M.
Для этого нам и нужны ординалы.
Ординалы возникают в теории множеств в качестве абстракции понятия вполне-упорядоченного множества.
Давайте начнём с конечных множеств. Вот начальный отрезок из натуральных чисел:
0 1 2 3 4 5 6
На него можно посмотреть как на множество из семи объектов — не обращая внимания на порядок между ними. Такому взгляду на множества соответствуют кардинальные числа, измеряющие размеры множеств; кардинальное число этого множества - 7, т.к. у него семь членов.
Но можно на него посмотреть и как на упорядоченное множество из семи членов: 0 < 1 < 2 < 3 < 4 < 5 < 6.
Любые два упорядоченных множества из семи членов - будь то семь натуральных чисел, семь точек на прямой или семь любых других объектов, выставленных в каком-либо порядке - изоморфны между собой, то есть между ними всегда можно построить однозначное соответствие, сохраняющее порядок:
0 1 2 3 4 5 6 | | | | | | | a b c d e f g
Ординальное число 7 - в отличие от кардинального числа 7 - являет собой каноническое вполне-упорядоченное множество из семи элементов - например, <0 1 2 3 4 5 6>. Ординальные числа являются абстрактизацией идеи вполне-упорядоченного множества: если есть два разных вполне-упорядоченных множества, которые изоморфны друг другу - т.е. с точки зрения порядка членов они как бы "одно и то же" - то они обязаны соответствовать одному и тому же, идентичному ординальному числу.
Пока мы говорим о конечных множествах, никакой разницы между кардинальными и ординальными числами нет, потому что любые два способа упорядочить конечное множество приводят к изоморфным (и вполне-упорядоченным) результатам. То есть в случае конечного множества его размер (кол-во членов, кардинальность) как бы определяет полностью его структуру, добавление порядка между членами ничего нового сообщить нам не может. По-настоящему важными ординальные числа становятся в бесконечном случае.
Выстроим цепочку ординальных чисел:
0 - (пустое множество) 1 - 0 2 - 0 1 3 - 0 1 2 4 - 0 1 2 3 ...
И теперь построим новое, объединяющее все обозначенные выше, которое называется омега (w):
w - 0 1 2 3 4 5 6 7 8 9 10 11 12 13 ...
Омега является порядковым типом множества всех натуральных чисел. Теперь добавим "в конце" ещё один объект:
w+1 - 0 1 2 3 4 5 6 7 8 ... a
В качестве упорядоченного множества w+1 выглядит так: сначала идут все натуральные числа, а "после них", после того как "все они кончатся", ещё один объект, который больше их всех. Я его здесь обозначил буквой a для простоты; формальный подход немного запутанней.
Это самое "после них" может быть трудным для понимания, но важно понять, что это всего лишь метафора. Мы не отсчитываем на самом деле все натуральные числа одно за другим (такой процесс никогда бы не завершился), мы просто вводим новый член множества, который по определению больше всех, которые есть до сих пор (хоть их и бесконечное множество).
С одной стороны, любое упорядоченное множество, которое "устроено" таким же способом - сначала бесконечное счётное множество объектов, а потом ещё один, больше их всех - будет изоморфно w+1. С другой стороны, упорядоченное множество w+1 не изоморфно w. Не существует взаимно однозначного соответствия между w+1 и w (множеством натуральных чисел), сохраняющего порядок. Это легко видеть хотя бы потому, что у w+1 есть наибольший член, который больше всех остальных, а у w такого нет, поэтому куда бы этот наибольший член a ни "поставить" в таком соответсвии внутри w, там всегда будут числа больше его, в то время как в w+1 больше его ничего нет - порядок нарушится.
С другой стороны, размер, он же кардинальность, у множеств w и w+1 одинаковый, и равен размеру множества натуральных чисел. Иными словами, множество w+1 можно пересчитать, подставив ему в соответсвие натуральные числа из w:
a - 0 0 - 1 1 - 2 2 - 3 ...
Таким образом все члены w+1 "пересчитываются" при помощи членов w, и поэтому размер у них одинаковый. Но такое соответствие не сохраняет отношения порядка между членами. Тип размерности у них одинаковый, а порядковый тип - разный. Т.е. на бесконечных множествах понятия кардинала и ординала расходятся; ординалы более скрупулезно различают разные множества. Если у двух множеств один и тот же порядковый тип-ординал, т.е. если они изоморфны, то размер у них уж точно одинаковый; но обратное неверно.
Важно заметить также, что множество w+1 остаётся вполне упорядоченным. В нём нет бесконечных нисходящих последовательностей. В самом деле, мы можем начать такую последовательность членом a, но потом нам неизбежно придётся "прыгнуть" куда-то внутрь натуральных чисел, и куда бы мы не прыгнули, оттуда останется только конечное кол-во мест спускаться дальше.
Построение ординалов можно продолжить:
w+1 - 0 1 2 3 4 ... a w+2 - 0 1 2 3 4 ... a b w+3 - 0 1 2 3 4 ... a b c ............ w+w - 0 1 2 3 4 ... a b c d e ...
Например, w+123 "выглядит" так: "сначала" все натуральные числа w, а "после них" и больше их всех ещё 123 выстроенных в каком-то порядке объекта (к-е я здесь пометил латинскими буквами, но на самом деле их природа неважна, важно только отношение порядка между ними).
w+w "выглядит" так: сначала все натуральные числа, а потом "за ними" и больше их всех ещё одна копия натуральных чисел. Даже и это множество остаётся вполне упорядоченным. В нём невозможно построить бесконечную нисходящую последовательность. Где бы её не начать, например, во второй копии w, через конечное число шагов придётся спуститься куда-нибудь в первую, где тоже останется только конечное число шагов.
Я опускаю, здесь и далее, доказательство того, что все эти множества действительно разные ординалы, т.е. что они не изоморфны друг другу, они действительно представляют собой существенно разные способы упорядочить объекты. Интуитивно в этом легко убедиться.
Продолжая (заменяю теперь латинские буквы числами для удобства, но надо понимать, что это разные копии w и потому "разные" числа):
w+w+1 - 0 1 2 3 4 ... 0 1 2 3 4 ... 0 w+w+2 - 0 1 2 3 4 ... 0 1 2 3 4 ... 0 1 ... w+w+w - 0 1 2 3 4 ... 0 1 2 3 4 ... 0 1 2 3 4 ...
Сокращая и подразумевая всегда под w копию всего множества натуральных чисел:
w+w+w - w w w w+w+w+1 - w w w 0 w+w+w+2 - w w w 0 1 ... w+w+w+w - w w w w ....... w * w = w w w w w w ...
Совершая как бы новый предельный прыжок, мы приходим к ординальному числу w*w, которое "выглядит" так: копия натуральных чисел, за ней ещё одна, и ещё, и ещё, и так бесконечное число раз. Даже и это множество остаётся вполне упорядоченным. Пытаясь построить в нём нисходящую последовательность, мы неизбежно выбираем первый член в какой-то из копий w, например в 127-й; после этого мы можем только конечное число раз спускаться в каждой копии, и у нас есть только 127 копий, в которых спускаться; поэтому через конечное число шагов мы придём в начало.
Обозначим w2 = w*w.
Далее:
w2+1 - w w w ... 0 ... w2+w - w w w .... w w2+w+1 - w w w ... w 0 ... w2+w2 - w w w ... w w w ... ........ w3 = w2+w2+... - (w w w ...) (w w w ...) (w w w ...) (w w w ...) ...
Таким образом можно продолжать и дальше. Повторяя бесконечное число копий w3 одна за другой, получим w4, повторяя его - w5, и так далее. Каждый такой повтор добавляет огромное количество предельных переходов "внутрь" порядка, оценить которые интуитивно становится очень нелегко уже на стадии w2. Тем не менее можно убедиться (подробно объяснять это я уже не буду), что все возникающее множества-ординалы остаются хорошо упорядоченными. Несмотря на гигантское множество разных бесконечностей, таящихся в них, можно построить только конечные по длине нисходящие последовательности членов.
Более того, все эти множества остаются счётными по размеру. То есть по количеству членов в них они все равны между собой и равны w. Их все можно "перенумеровать" натуральными числами, хотя такие нумерации не будут, конечно, сохранять порядок членов.
Если взять предел
w w2 w3 w4 ...
то мы получим ординал ww. От него можно продолжить дальше: ww+1 ...
ww + w ... ww + w2 ... ww + ww ... ww + ww + ww ... ww*w = ww+1.
На этом этапе уже совсем практически невозможно оценить "на глаз" внутреннюю структуру порядков этих ординалов, такой она становится сложной. Но отсюда можно продолжать и дальше и дойти постепенно до ww*w, ww*w*w, и в пределе этого - www.
Продолжая всё тот же процесс добавления копий меньших ординалов и перехода к пределу, мы приходим к ординалам wwww, wwwww, wwwwww и т.д.
Наконец, взяв предел этой последовательности "лесенок" степеней ординалов, мы получаем ординал, больший их всех, который называется эпсилон-ноль - ε0. От него тоже можно продолжать дальше и строить, скажем, ε0+1 и т.п., но это нам уже не нужно. Важно понять, что ε0 является ординалом, который объединяет в себе все возможные комбинации натуральных чисел, w и степеней w. Начиная с w, можно складывать, умножать и возводить в степень друг друга сколько угодно раз, и никогда не выйдешь за пределы ε0.
И все эти ординалы, включая ε0, остаются вполне упорядоченными множествами.
Более того, между самими ординалами (а не только между их членами) можно определить отношение порядка: какой ординал меньше какого другого. Собственно, это получается тривиально после очень важного результата: если есть два ординала A и B, то либо A является начальным сегментом B (в качестве упорядоченного множества), либо B является начальным сегментом A, либо они идентичны. Доказывать строго я это не буду, но объяснить на примерах это можно весьма убедительно. Например, w является начальным сегментом ординалов w+1, w+w, w2, w2+w+1, ww и т.п. - собственно все ординалы, кроме конечных натуральных чисел, начинаются с копии w, как легко видеть из нашего построения их выше. Ординал w2+w+1 является начальным сегментом ординала w3. И вообще благодаря тому, что мы всегда строили новые ординалы пристроением справа к уже существующим, очевидно, что они выстраиваются таким образом в упорядоченную цепочку. И все ординалы меньше ε0 являются начальными сегментами (каждый из них - разным начальным сегментом) ординала ε0, который включает их всех.
Из этого следует, что невозможно построить нисходящую цепочку ординалов меньше ε0 (а не только членов какого-то одного ординала). Если бы была такая цепочка ординалов, можно было бы посмотреть на неё "внутри" ε0, который содержит их всех, и выстроить с её помощью нисходящую цепочку его членов (здесь есть несколько технических подробностей, к-е я опускаю, но идея должна быть ясна).
Тут мы и приходим к решению задачи о Геркулесе и гидре. Каждому дереву-гидре мы ставим в соответствие ординал, путём, описанным в решении задачи; при этом мы всё время рекурсивно возводим в степени и складываем, и поэтому никогда не выходим за пределы ε0, все получающиеся ординалы меньше ε0 (более того, как легко проверить, любой ординал меньше ε0 образуется с помощью какой-то гидры - но это сейчас не важно). Операция отсечения головы и вырастания новых уменьшает ординал дерева (опять-таки см. решение). Поэтому, если бы Геркулес мог бесконечно долго рубить гидру, мы могли бы построить бесконечную нисходящую последовательность ординалов, что невозможно. Что и требовалось доказать.
Вопросы и предложения принимаются.
