?

Log in

No account? Create an account
Геркулес и гидра (что такое ординалы) - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

Геркулес и гидра (что такое ординалы) [фев. 26, 2002|09:11 am]
Anatoly Vorobey
[Настроение |уфффф...]

Несколько дней назад я предложил задачу о Геркулесе и гидре; на следующий день я записал в дневнике решение, которое использует ординальную арифметику — которую меня попросили объяснить для тех, кто с этим незнаком, но хочет понять решение. Я попробую это сделать, на очень элементарном уровне, в этой записи. Отдельно - не здесь, а в другой записи - мне ещё предстоит объяснить, почему у этой задачи нет простого решения, и почему использование ординалов, или сопоставимых с ними по сложности математических абстракций, неизбежно при решении этой задачи.

Сначала немного мотивации. Предположим, что мне удалось бы найти некий способ пронумеровать деревья - присвоить натуральное число 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 образуется с помощью какой-то гидры - но это сейчас не важно). Операция отсечения головы и вырастания новых уменьшает ординал дерева (опять-таки см. решение). Поэтому, если бы Геркулес мог бесконечно долго рубить гидру, мы могли бы построить бесконечную нисходящую последовательность ординалов, что невозможно. Что и требовалось доказать.

Вопросы и предложения принимаются.
СсылкаОтветить

Comments:
From: 9000
2002-02-26 02:12 am

Красота

Математика меня всегда привлекала именно красотой идей и возникающих из них конструкций.

Спасибо за ещё одну такую :-)
(Ответить) (Thread)
[User Picture]From: avva
2002-02-26 06:19 am

Re: Красота

Т.е. всё было понятно? А то я волновался по этому поводу, т.к. писал в цейтноте и в один присест, а перечитать и причесать времени нету.
(Ответить) (Parent) (Thread)
[User Picture]From: direvius
2006-08-17 11:37 am

Re: Красота

Да, все понятно вроде. Классно. (хотел прочитать, что такое ординалы -- набрал в гугле и попал сюда Спасибо большое!)
(Ответить) (Parent) (Thread)
[User Picture]From: tpars
2008-09-05 09:43 pm
Из этого следует, что невозможно построить нисходящую цепочку ординалов меньше ε0 (а не только членов какого-то одного ординала).

Вот на этом месте стало непонятно.
Причем непонятно стало вообще ничего.
Ординалов меньше эпсилон-ноль или цепочку меньше эпсилон-ноль? В любом случае, из любых двух и больше ординалов _можно_ построить нисходящую (или восходящую) цепочку (потому что для любых двух ординалов определено, какой из них больше, а какой меньше)...
(Ответить) (Thread)
[User Picture]From: avva
2008-09-05 10:22 pm
Имеется в виду - бесконечно нисходящую цепочку ординалов, каждый из которых меньше e0.

(Ответить) (Parent) (Thread)
[User Picture]From: tpars
2008-09-06 03:25 am
А, ну это да, понятно.

Тогда не очень понятно следующее предложение. ("Если бы была такая цепочка ординалов, можно было бы посмотреть на неё "внутри" ε0, который содержит их всех, и выстроить с её помощью нисходящую цепочку его членов (здесь есть несколько технических подробностей, к-е я опускаю, но идея должна быть ясна)".)
Да и предыдущая фраза настолько очевидна, что никакое пояснение и не требуется, на мой взгляд.
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2008-09-06 10:11 am
В вполне упорядоченном множестве не может быть бесконечной нисходящей цепочки членов.

Из этого не следует _автоматически_, что не может быть бесконечной нисходящей цепочки ординалов, потому что коллекция всех ординалов не есть множество (она слишком "большая"). Но тем не менее это верно, потому что можно взять напр. первый член такой гипотетической цепочки, и посмотреть на все остальные ее члены как на элементы первого члена, каковыми они обязательно являются. Поскольку первый член сам по себе множество, то внутри него такая цепочка невозможна. В этом суть того предложения, что вам показалось непонятным. Это не очень важная деталь, скорее техническая.
(Ответить) (Parent) (Thread)
[User Picture]From: tpars
2008-09-06 05:49 pm
А, вот оно что...
Чем дальше в абстракцию, тем хуже мне дается математика. :)
(Ответить) (Parent) (Thread)
[User Picture]From: rombell
2009-12-26 04:15 pm
про бесконечность - добавить бы в текст, а то я на этом месте тоже нить потерял.
(Ответить) (Parent) (Thread)
[User Picture]From: tpars
2008-09-06 03:26 am
А вообще, спасибо за пост. Интересно.
(Ответить) (Thread)
[User Picture]From: rombell
2009-12-26 04:19 pm

Огромное спасибо!

ОООО!
Я долго пытался вкурить Рюкера Руди "Белый свет" (Rucker Rudy "White Light, or What Is Cantor's Continuum Problem?") который вообще-то НФ роман, написанный профессором математики, причём явно обкурившимся. Там весь примерно сюжет изоморфен вашей заметке. Но я не смог ни у кого узнать, что же такое эпсилон-ноль! А среди моих знакомых есть несколько выпускников матфака далеко не худшего из вузов. И гугль не помог (лет пять назад)

Огромное спасибо!
(Ответить) (Thread)
[User Picture]From: gul_kiev
2015-01-14 05:50 am
Большое спасибо за объяснение!
И хорошо, что lj (в отличие от fb) даёт простой доступ к старым-старым постам. :)

У меня остался вопрос о роли ε0, нагуглить почему-то не получилось. Это счётный ординал? От него возможна бесконечная нисходящая последовательность?
Чем он интересен, что для него придумали отдельное название? Что такое ε1?

Где про это почитать ("man что")? ;-)
(Ответить) (Thread)
[User Picture]From: avva
2015-01-14 01:10 pm
Это счетный ординал. Он является наименьшим ординалом a для которого верно a = w^a. Чтобы получить его, мы просто берем объединение счетного числа счетных ординалов w, w^w, w^(w^w), w^(w^(w^w)), итд. Поскольку e_0 является счетным объединением счетных ординалов, он сам тоже счетный. Бесконечную последовательность вниз от него построить нельзя, как и от любого вообще ординала, по обычной причине - класс ординалов хорошо упорядочен. Интуитивно говоря, первый шаг вниз от e_0 приведет вас внутрь какого-то из w^(w^(....^w)).

Аналогия. Возьмите f(x)=1+x как функцию ординалов. f(0)=1, f(1)=2 итд. не являются неподвижными точками. Но если мы построим последовательность

0, f(0), f(f(0)), f(f(f(0))), итд.

т.е.

0, 1, 2, 3, 4...

и возьмем ее счетное объединение, то получим ординал w, который является неподвижной точкой f: 1+w=w.

Аналогичным образом если f(x)=w^x, то построив цепочку w, f(w), f(f(w))... и взяв ее объединение, получаем неподвижную точку e_0.

Причина, по которой e_0 нужен в этом доказательстве, это что если вы находитесь внутри e_0, вы не можете вырваться за его пределы операциями +, *, и даже w^x. Только важно подчеркнуть, что w^x здесь всюду обозначает ординальное возведение в степень, а не кардинальное (которое легко вырывается за пределы счетных кардиналов: 2^w > w).

Больше формализма:
http://en.wikipedia.org/wiki/Epsilon_numbers_(mathematics)
http://en.wikipedia.org/wiki/Fixed-point_lemma_for_normal_functions
(Ответить) (Parent) (Thread)
[User Picture]From: gul_kiev
2015-01-14 03:01 pm
Спасибо.
Пока не понимаю, почему счётное объединение счётных ординалов счётно, попытаюсь это понять самостоятельно. Хотя пока мне это кажется странным. Ведь множество ординалов до w*w, если я правильно понимаю, изоморфно множеству пар натуральных чисел (n1,n2), а множество ординалов до ww - множеству бесконечных последовательностей натуральных чисел. Но ведь множество этих последовательностей континуально (действительное число - бесконечная десятичная дробь, т.е. счётная последовательность цифр, и множество действительных чисел несчётно). Где-то что-то я явно понимаю неправильно. :-(

Можно ли вместо множества ординалов меньше ε0 в доказательстве рассматривать множество всех счётных ординалов (т.е. меньше Ω или ℵ1)? Лично для меня было бы интуитивно несколько более понятно, что мы не можем вырваться за пределы счётных ординалов, чем что мы не можем вырваться за пределы ε0 (хотя это субъективно, и может быть вообще неверно).
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2015-01-14 04:03 pm
Любое счетное объединение счетных множеств счетно (это утверждение требует слабой версии аксиомы выбора, см. например https://www.proofwiki.org/wiki/Countable_Union_of_Countable_Sets_is_Countable). Интуитивно говоря это следует по той же причине, по какой рациональных чисел есть счетное число: рациональные числа это счетное объединение счетных множеств вида {p/q:q=1}, {p/q:q=2}, итд.

Вас подводит интуиция в разнице между ординальным и кардинальным возведением в степень. Это две совершенно разные операции.

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

w^w, ординальная экспоненциация, это ординал, являющийся пределом последовательности w, w*w, w*w*w, w*w*w*w....
Поскольку эта последовательность монотонная, то собственно w^w является ее объединением. А что такое w*w, w*w*w итд.?

Помните все время, что ординалы это "типы порядка", т.е. определенный паттерн расположения элементов, где важно не только их число (т.е. кардинальность), но и порядок расположения. Держим это в уме и двигаемся от простого к сложному:

1,2,3,4... - конечные ординалы, соответствующие конечным последовательностям элементов
w - первый бесконечный (и счетный) ординал, предел (и одновременно объединение последовательности 1,2,3,4), соответствующий нескончаемой последовательности элементов: .....-> (стрелка означает "до бесконечности")
w+1 - "бесконечность, а потом еще после нее один элемент", т.е.: ....-> .
w+w - предел, он же объединение, последовательности w, w+1, w+2, итд. В схематичном виде его порядок выглядит так: .....-> .....->

(окончание следует)
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2015-01-14 04:03 pm
Теперь что такое w*w? Это объединение всех w, w+w, w+w+w, где на n-ном месте стоит ординал, состоящий из n копий w одна за другой. Значит, w*w это w копий w, записанных одна за другой. Это его идентичность как ординала, его порядок. С другой стороны, его *мощность*, кардинальность, все еще остается счетной, т.е. равна aleph_0 (объект, идентичный w, но мы его записываем так, когда речь о кардинальности). В частности, w*w можно привести в соответствие с натуральными числами, или парами натуральных чисел, как вы написали (нет разницы). Но это соответствие не будет *сохраняющим порядок*, т.е. идентичность w*w как ординала. Оно просто покажет, что w*w это счетное множество. Все счетные множества равномощны друг другу, всех их, включая все счетные ординалы, можно поставить в однозначное соответствие друг другу. Но как *упорядоченные множества* они очень разные, *изоморфизма* - т.е. соответствия, сохраняющего порядок - между w*w и парами натуральных чисел нет и не может быть.

("Множество пар натуральных чисел (n1,n2)" вообще не является хорошо упорядоченным и не изоморфно никакому ординалу. Наиболее на него похож ординал w+w, т.е. две копии w одна за другой, но обратите внимание, что он устроен по-другому: его члены это 1,2,3...w, w+1 (т.е. целая копия w плюс один элемент) итд. Он не включает в себя пары как таковые, в его элементах не присутствуют одновременно конечное число из первого w, а потом конечное из второго. Нет, пересчитывая w+w, сначала мы заканчиваем весь первый w, а потом "за ним" весь второй.)

Далее, что такое w*w*w? Представьте себе сначала один w ....-> , расположенный на линии, потом в уме поставьте рядом другой, третий, и продолжите их ставить "до бесконечности": это w*w. Теперь все, что получилось представьте в уме как один объект, и поставьте рядом еще один такой: это будет w*w*2 - еще один w*w*3... продолжите до бесконечности таких объектов - это будет w*w*w.

Теперь это бесконечное число копий w*w в свою очередь возьмите в уме в рамку, выделите в качестве объекта, и поставьте рядом копию, еще одну, бесконечность... выйдет w^4. Теперь представьте себе, что весь этот процесс вы повторяете бесконечное число раз, каждый раз беря то, что получилось в прошлый, и ставя рядом бесконечное число копий того же. Это будет w^5,w^6,w^7... Наконец, представьте себе, что вы берете лимит (объединение) всего этого процесса сразу за все его бесконечные повторения, объединяя вместе все w^n - и это будет epsilon_0. В качестве множества "вообще", без отношения к порядку, оно остается счетным, потому что вы ни разу не делали ничего более, чем счетное объединение счетных множеств (пусть и повторяли этот процесс счетное число раз). Но как *упорядоченное множество*, ординал, оно не очень поддается интуитивному описанию.
(Ответить) (Parent) (Thread)
[User Picture]From: gul_kiev
2015-01-14 05:34 pm
Разве каждому ординалу до w+w нельзя поставить в соответствие пару (n1,n2), где n1 принимает значение {0,1}, а n2 - произвольное натуральное число? Сравнение между парами (a1,a2) и (b1,b2) при этом можно определить как (в синтаксисе перла, он тут лаконичен):
a1 <=> b1 || a2 <=> b2
Тогда любому конечному ординалу N поставим в соответствие пару (0,N), а бесконечный ординал до w+w можно представить в виде w+N, и ему поставим в соответствие пару (1,N). Вроде бы, изоморфизм полный. Конечно, это множество счётно, любой паре (n1,n2) можно поставить в соответствие натуральное число (например, n1+2*n2), но тут уже порядок не сохранится.

Если тут ошибки нет, то получается, что ординалу до w*k (где k натуральное) можно поставить в соответствие пару (n1,n2), где n1 - число от 0 до k-1, а n2 - произвольное натуральное, с сохранением порядка. А ординалу до w*w - пару произвольных натуральных чисел (n1,n2), тоже с сохранением порядка. И множество таких пар получится вполне упорядоченным, без бесконечных убывающих последовательностей. И, конечно, оно остаётся счётным.

Далее, ординалам до w3 поставим в соответствие тройки (n1,n2,n3), упорядоченные по
a1<=>b1 || a2<=>b2 || a3<=>b3
Эти тройки тоже образуют вполне упорядоченное множество.
Соответственно, любой ординал wn является счётным, и изоморфен последовательности из n натуральных чисел.

А вот с ww оказалось понять сложнее. Пришлось вникать в доказательство того, что счётное объединение счётных множеств счётно, и применять его к бесконечным последовательностям.
Насколько я сейчас понимаю, ww не изоморфен множеству бесконечных последовательностей натуральных чисел, он изоморфен множеству всех конечных последовательностей (любой конечной длины). А это множество счётно. При сравнении более короткую последовательность можно спереди дополнить нулями. Мы не можем пересчитать бесконечные последовательности, но можем пересчитать все последовательности любой конечной длины.
А очень уж большое искушение было, если wn изоморфно последовательностям из n натуральных чисел, предположить, что ww изоморфно бесконечным последовательностям, а оно не так.
Уф.
Осталось понять, правильно ли я это понял, или всё неправильно нафантазировал. :)

Edited at 2015-01-14 18:00 (UTC)
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2015-01-14 06:22 pm
Ааа, теперь понял о чем вы, простит. Да, вы правы, так можно. Вы изобрели, примерно говоря, начальный отрезок
http://en.wikipedia.org/wiki/Ordinal_arithmetic#Cantor_normal_form

:)
(Ответить) (Parent) (Thread)
[User Picture]From: gul_kiev
2015-01-14 06:48 pm
Похоже, этого начального отрезка (т.е. операций с конечными последовательностями натуральных чисел) хватает для решения задачи о гидре и Геркулесе.

Получается, что в рамках PA недоказуемо, что множество пар (n1,n2), упорядоченное по правилу
a1<=>b1 || a2<=>b2
, вполне упорядочено?
(Ответить) (Parent) (Thread)
[User Picture]From: avva
2015-01-14 09:21 pm
Извините, опять вас не понимаю. Вы говорите, что для решения задачи вам достаточно ординалов до w*w? Каким образом?

(если вы говорите о w^w, то это соответствует не множеству пар, а множеству всех конечных последовательностей, как вы заметили; и в любом случае от w^w до epsilon_0 очень далеко).
(Ответить) (Parent) (Thread)
[User Picture]From: Рядовой Пользователь
2017-07-24 04:29 am
После прочтения подобных статей порой складывается совершенно отчетливое впечатление о чисто механическом понимании писателем предмета,совмещенное с совершенным отсутствием концептуальных понятий, за счет чего остается неприятный осадок после окончания чтения.
В таких же идеях как ординалы следует делать упор именно на втором, тем более когда пытаешься прояснить вопрос "для новичков".
(Ответить) (Thread)