В нашем разговоре о бесконечностях я вскользь упомянул о таких понятиях как кардинальные и ординальные числа. С первым из них мы немного разобрались. Напомню, кардинальным числом мы назвали объект, отражающий количество элементов в каком-либо множестве (так называемую мощность). При этом равномощным множествам в соответствие мы поставили один и тот же кардинал. Например, всем конечным множествам в качестве кардинала мы сопоставили натуральные числа, равные, собственно, количеству их элементов, а счётным множествам мы присвоили загадочный кардинал ℵ₀. Фактически, мы рассматривали кардиналы как специальные ярлычки для множеств, отражающие, в некотором смысле, величину этих множеств. Что же такое ординалы? Люди, знакомые с английским (или латинским) языком могут догадаться, какова этимология этого слова. Ordinal — это производное от слова order (англ. "порядок"). Поэтому прежде, чем начать разговор об ординальных числах, нам необходимо поговорить о том, что такое порядок.
Порядок
В предыдущих статьях мы с Вами рассматривали множества как простую совокупность некоторых элементов. Об этих элементах мы не могли сказать ничего путного, кроме того, принадлежат ли они некоторому множеству (или подмножеству) или нет. Именно поэтому мы могли охарактеризовать сами множества лишь по их мощности. Однако человеческий ум устроен так, что он во всём ищет закономерность. В частности, весьма естественно собирать не просто элементы множества вместе, а присваивать им, например, некоторые номера (скажем, натуральные числа), чтобы потом их можно было рассматривать один за одним в некотором порядке (например, в порядке роста номеров). В таком случае, взяв два различных элемента, мы можем не только сказать, что они лежат или не лежат в одном множестве, но и указать, какой элемент имеет высший приоритет (идёт первым). Это даёт некоторые преимущества во многих случаях, так как позволяет рассматривать некоторую структуру множеств.
Данная идея может быть обобщена на любое множество. Фактически, нам нужен лишь способ, позволяющий из любой пары элементов множества выбрать тот, который первее. Итак, говорят, что на множестве А задан частичный строгий порядок (или просто порядок), если задано бинарное отношение, обозначаемое символом '<', для которого верны три следующих правила:
1. (антирефлексивность) Не найдётся такого элемента а ∈ А, чтобы было верно a < a
2. (асимметричночть) Если a < b, то невозможно, чтобы было верно b < a
3. (транзитивность) Если a < b и b < c, то a < c
Здесь указано очень страшное словосочетание — бинарное отношение — однако это всего лишь правило, по которому отбираются пары элементов из множества. В данном случае это правило отбора говорит, что первый элемент предшествует второму или меньше второго. Вот и всё. Если провести аналогию с числами, то все три правила становятся предельно логичными. Действительно, ни одно число не может быть меньше себя самого, если одно число меньше другого, то второе число не может быть меньше первого, а если одно число меньше другого, а это число меньше третьего, то первое уж и подавно меньше третьего. Однако в общем случае множества могут иметь произвольную природу, а за знаком "<" может скрываться совсем другой смысл. Приведём несколько примеров.
На множестве всех людей на Земле может быть введён порядок по старшинству. Тогда человек1 < человек2, если человек1 родился раньше, чем человек2 (дедовщина в чистом виде). Множеству слов в словаре обычно присваивают так называемый лексикографический порядок. А именно говорят, что слово1 < слово2, если первая буква слова1, в которой оно отличается от слово2, идёт по алфавиту раньше соответствующей буквы в слово2. Если же слова имеют различную длину и при этом совпадают во всех буквах вплоть до окончания одного из слов, то меньшим считается то слово, которое короче. Так, например, год < гол, волга < вольт, а сад < садовод. На множестве всех подмножеств некоторого множества (булеане) можно ввести порядок по включению: А < В, если А является подмножеством В.
Как видно, даже для множества из двух элементов существуют несравнимые в данном смысле подмножества: нельзя сказать, что { a } < { b } или { b } < { a }, так как одно из них не является подмножеством другого. Таким образом, имея частичный порядок, мы не всегда можем сказать, какой из двух элементов множества первее. Множества с частичным порядком, в которых любые два элемента либо равны, либо один из них меньше другого, называются линейно упорядоченными (или просто упорядоченными). В дальнейшем мы будем говорить только о таких множествах. Например, лексикографический порядок всегда линеен. Числа на вещественной прямой также упорядочены линейно.
Напомню, что изоморфными называются множества, между элементами которых можно установить взаимно однозначное соответствие (изоморфизм), то есть сопоставить каждому элементу одного множества единственный элемент другого. При этом верен тот факт, что множества изоморфны тогда и только тогда, когда они равномощны. В некотором смысле, такие множества одинаковы, неразличимы с точки зрения количества элементов. Когда же дополнительно у нас есть порядок, то необходимо его учитывать, чтобы отождествлять множества. Поэтому теперь мы введём более сильное понятие. Подобными называются упорядоченные множества, между элементами которых можно установить монотонное взаимно однозначное соответствие, то есть изоморфизм, сохраняющий отношение порядка для любой пары элементов (a < b, тогда и только тогда, когда f(a) < f(b), где f — обозначение изоморфизма). Монотонный изоморфизм сохраняет не только количество элементов, но и их порядок. Так, в случае естественного порядка, множество целых чисел хоть и изоморфно множеству натуральных, однако не подобно ему. Действительно, если бы подобие имело место, то какое-то целое число m было бы сопоставлено натуральному числу 1. Поскольку m - 1 < m, то натуральное число, сопоставленное целому числу m - 1, было бы обязано быть меньше 1, но таких натуральных чисел не существует.
Порядковые типы и действия над ними
Ранее в соответствие всем изоморфным множествам мы ставили некоторый кардинал. Теперь же в соответствие всем подобным множествам мы поставим некоторый порядковый тип. Опять же это пока будет просто буква (или цифра), обозначающая конкретный способ упорядочить элементы множества. Так, например, множество всех натуральных чисел с естественным порядком будет иметь порядковый тип ω, а множество целых чисел с естественным порядком — тип ζ. Любое упорядоченное множество можно упорядочить обратно, то есть поменять местами большие и меньшие элементы. Если упорядоченное множество имело некоторый порядковый тип α, то при упорядочении обратно ему приписывают тип α*, называемый сопряжённым или обратным к типу α. Например, ω* соответствует множеству { ..., 5, 4, 3, 2, 1 }, в то время как ζ*=ζ. И как обычно, самая простая ситуация с конечными множествами. Дело в том, что хоть любое множество из n элементов и можно упорядочить n! способами (кто не верит, пусть проверит), но все такие упорядочения будут подобны. Действительно, всегда можно указать конкретный монотонный изоморфизм, осуществляющий подобие. А именно наименьшему элементу мы сопоставим наименьший элемент, второму по порядку элементу мы сопоставим второй по порядку и так далее. В силу конечности множеств данный изоморфизм всегда можно построить (его можно воспринимать в виде обычной таблицы соответствия). В силу этого утверждения все порядковые типы конечных множеств мы будем просто обозначать натуральными числами (равными количеству элементов в таких множествах, естественно). Очевидно, что для любого натурального числа будет тогда верно n*=n.
Порядковые типы это ещё не ординальные числа, но над ними уже можно проводить некоторые арифметические операции. Например, их можно складывать друг с другом, получая новый порядковый тип. Определяется данная операция следующим образом: пусть α и β — некоторые порядковые типы, соответствующие непересекающимся упорядоченным множествам А и В, тогда α + β — это порядковый тип объединения множеств А∪ B, в котором все элементы множества B больше всех элементов множества А (в остальном отношение порядка остаётся тем же). Например, ω + 1 соответствует множеству { 2, 3, 4, …, 1 } (здесь единица считается больше всех остальных натуральных чисел), ω + ω — это порядковый тип множества { 1, 3, 5,…, 2, 4, 6,… }, а ω* + ω = ζ. Для конечных же множеств данная операция переходит в обыкновенное сложение натуральных чисел. Отметим, что, вообще говоря, от перемены мест слагаемых сумма меняется. Так, 1 + ω является типом множества { 1 } ∪ { 2, 3, 4, … } = { 1, 2, 3, 4, … }, то есть просто равен ω и не может быть равен ω + 1, так как во всех множествах этого типа есть наибольший элемент, а во множествах типа ω его нет. По сходной причине все следующие типы также различны: ω + 2, ω + 3, ω + 4, …, ω + n, … (в то время, как при любом натуральном n тип n + ω равен ω). Также нетрудно показать, что тип ω + ω не совпадает ни с одним из представленных выше, поскольку содержит бесконечно много элементов, которые больше счётного числа элементов. Ещё несколько забавных фактов: 1 + 1 + 1 + … = ω, n + n +n + ... = ω, 1 + 2 + 3 + … = ω. Это нетрудно показать, достаточно представить себе запись каждого из множеств таких типов в строчку. Все типы ω, ω + ω, ω + ω + ω, … различны и при этом отличаются от типа ω + ω + … + ω + … (где слагаемых счётное число). Последний тип соответствует, например, такому множеству: { 2, 4, 8,…, 3, 9, 27,…, 5, 25, 125,…,… }, то есть множеству, в котором по порядку перечислены все степени всех простых чисел. В таком множестве число упорядоченных по возрастанию бесконечных групп чисел бесконечно, в то время как в любом из множеств, соответствующих типу ω + ω + … + ω (n раз), таких групп конечное число, поэтому снова монотонный изоморфизм построить нельзя.
Как и обычные числа порядковые типы можно не только складывать друг с другом, но и умножать друг на друга. В силу исторических фактов множители в таком умножении пишутся в неестественном для нас порядке. Так, произведение порядковых типов α и β записывается как β⋅α (это можно читать как «бета, взятое альфа раз»). Это тоже порядковый тип и, если А — это множество, имеющее тип α, а В — имеющее тип β, то он соответствует декартовому произведению множеств А и В (A × B) с лексикографическим порядком.
Данная иллюстрация отчасти показывает, почему в записи произведения множители поменяны местами: в этой таблице три раза подряд перечислены множества, подобные множеству натуральных чисел, и оно имеет тип ω⋅3 ("омега трижды"). Уже сейчас видно, что от перестановки множителей произведение также может измениться, поскольку, например, 3⋅ω — это множество, в котором счётное число раз перечислены тройки из элементов (в нашем примере они имели бы вид (a, 1), (a, 2), (a, 3), (b, 1), (b, 2), (b, 3), …). Оно, в таком случае, имеет тип 3 + 3 + 3 +… = ω, в то время как тип ω⋅3 равен типу ω + ω + ω (это видно, если записать нашу таблицу в строчку). Вообще, для любого натурального числа n верно следующее: n⋅ω = n + n + n + ... = ω. Упомянутый выше тип ω + ω + … + ω + …, на самом деле просто равен типу ω⋅ω = ω² (достаточно просто переписать бесконечную цепочку счётных множеств в виде бесконечной таблицы, чтобы это увидеть). Отметим ещё, что для конечных множеств произведение порядковых типов переходит в обычное произведение чисел.
Теорема Цермело
Можно долго говорить об операциях над порядковыми типами. Например, можно доказать ассоциативность сложения и умножения (правила вида (α + β) + γ = α + (β + γ) и (α⋅β)⋅γ = α⋅(β⋅γ)). Однако давайте мы поговорим вот о чём: что именно нам даёт порядок и чем он так необходим? Если вспомнить, что такое множество, то можно прийти к факту, что в нём нет элементов более или менее главных, они все равноправны, нельзя между какими либо из них найти более или менее примечательный элемент. Из этого напрямую следует, что единственный вариант описать множество — это описать некоторое характеристическое свойство, определяющее все его элементы сразу. Например, мы говорим множество всех чётных натуральных чисел, подразумевая, что любой его элемент положителен и без остатка делится на два. Проблема заключается в том, что широкий класс множеств сложно или вообще нельзя описать подобным образом, но можно описать как именно строятся такие множества шаг за шагом. Даже говоря о чётных натуральных числах, мы сразу же представляем себе последовательность вида 2, 4, 6, ..., 2n, ..., в которой по умолчанию присутствует порядок. Из-за этого многие множества намного проще описывать индуктивно, то есть описывать то, как можно построить все их элементы шаг за шагом, начиная с некоторого малого числа начальных элементов. Понятно, что такие шаги сами по себе должны быть индексированы некоторым упорядоченным (очевидно, линейно) множеством. Мы так обычно и пишем шаг 1, шаг 2, шаг 3, ..., шаг n. Именно здесь нам очень важен порядок, потому как без него для нас не было бы разницы, в каком порядке применять действия, все шаги были бы равноправны. Однако, думая о шагах, как о некой последовательности действий, мы неявно используем ещё одно замечательное свойство: всегда ясно, какой именно шаг идёт следующим. За шагом 2 идёт шаг 3, это естественно. Данная ситуация становится менее естественна, если мы будем говорить об общем случае такого рода построений, в котором само число шагов может быть несчётным. Например, будь наши действия индексированы всеми числами отрезка [0; 1], мы не смогли бы сказать, какой шаг идёт сразу после нулевого.
Проблема кроется в том, что не у всех подмножеств единичного отрезка, упорядоченного стандартным способом, существует минимальный элемент. Очевидно, что будь это так, мы могли бы рассмотреть его подмножество вида (0; 1] и взять его минимальный элемент в качестве следующего за элементом 0. Далее мы могли бы выкинуть этот элемент из полуинтервала (0; 1], найти в получившемся подмножестве его минимальный элемент и сказать, что он следует далее. Линейно упорядоченные множества, в которых любое непустое подмножество имеет минимальный элемент, называются вполне упорядоченными. Это максимальная степень порядка. Все члены такого множества не просто понимают, кто из них главнее, а точно понимают кто за кем идёт. Для любого элемента можно найти тот, что идёт непосредственно за ним: это минимальный элемент подмножества, состоящего из элементов строго больших, чем данный элемент. Множество натуральных чисел со стандартным порядком является вполне упорядоченным, а вот множество целых чисел — нет (например, у отрицательных чисел нет минимального элемента). Однако целые числа допускают полное упорядочение. Если мы введём на них новый порядок по правилу, при котором a < b, если |a| < |b| или |a| = |b|, но a < 0, то множество целых чисел будет иметь следующий вид: 0, -1, 1, -2, 2, -3, 3, ... Теперь это множество, очевидно, вполне упорядочено, так как его тип совпадает с типом ω натуральных чисел. Отметим, что любое линейно упорядоченное конечное множество вполне упорядочено.
Возникает вопрос: а любое ли множество можно вполне упорядочить? Ответ на данный вопрос дал Эрнст Цермело. И он не так уж и прост на самом деле.
Казалось бы, как ответ может быть сложным, если варианта всего два: да или нет? Подвох кроется в том, что этот вопрос очень тесно связан с тем, что вообще такое множество и каким правилам множества обязаны подчиняться. Говоря кратко, вся теория множеств зиждется на нескольких аксиомах (которые теперь называют аксиомами Цермело-Френкеля). Они чётко описывают, что можно считать множеством и какие действия над ними допустимы. Например, любое объединение множеств является множеством, элементы множества, удовлетворяющие некоторому свойству являются множеством. Эта аксиоматика стала естественной ответной реакцией на неудачи наивной теории множеств, изначально предложенной Кантором (см. парадокс Рассела). Она была построена так, чтобы основанная на ней теория была непротиворечива. Помимо прочих утверждений аксиоматика, предложенная Цермело, включала в себя следующий постулат:
Для любого семейства непустых множеств существует правило, которое позволяет выбрать по одному элементу из каждого из множеств семейства
Это утверждение называется аксиома выбора. На первый взгляд, это даже аксиомой сложно назвать. Действительно, если мы заранее знаем, что все наши множества непустые, то, очевидно, в каждом из них есть хоть один элемент, тогда мы просто из каждого выберем любой элемент и дело в шляпе. Такие рассуждения естественны для случая конечного набора множеств. Для счётного набора множеств ситуация всё ещё более или менее естественна (опять же здесь есть некий алгоритм: возьмём элемент из первого множества, потом из второго и так далее). А вот начиная с несчётного набора множеств, данная аксиома начинает проявлять всю свою странную суть. Дело в том, что она лишь постулирует возможность выбора, но не даёт даже намёка на то, как именно такой выбор осуществляется. В своё время эта аксиома расколола математическое сообщество на два лагеря. Первые считают, что она естественна и не несёт в себе ничего противоречащего, другие же, напротив, уверены, что данная аксиома является корнем всего зла и обязана быть исключена из аксиоматики. Самое интересное заключается в том, что большинство результатов теории множеств остаются верными как при принятии, так и при непринятии аксиомы выбора.
Однако зачем я вспомнил про эту аксиому? Дело в том, что при условии её принятия верна следующая теорема:
Терема (Цермело): любое множество может быть вполне упорядочено
Самое же забавное состоит в том, что эта теорема эквивалентна аксиоме выбора, то есть, приняв её в качестве аксиомы, можно доказать аксиому выбора. Делается это тривиально: если у нас есть система множеств, то просто из каждого из них выберем минимальный элемент (теорема Цермело гарантирует его существование). Доказательство же самой теоремы Цермело весьма громоздко и приводить его мы не будем.
Итак, сам факт того, что любое множество можно упорядочить, можно принимать как аксиому, тем самым расширяя текущую теорию множеств. Именно это мы и сделаем.
Ординалы и порядок на них
И вот наконец мы можем переходить к основному предмету данной статьи. Порядковым числом или ординалом мы назовём порядковый тип вполне упорядоченного множества. Все натуральные числа являются ординалами. Ординалами также являются и ω, ω + n, ω⋅2, ω⋅n, ω⋅ω (это проверяется тривиально). Мы уже ввели операции над ординалами, когда вводили их над порядковыми типами, теперь введём понятие порядка для ординалов. Для начала давайте ещё раз уточним, что такое, в принципе, порядковый тип. Это некоторый объект, сопоставленный целому классу подобных множеств. Почти всегда, говоря о таком сопоставлении, мы использовали некоторый конкретный представитель данного класса (для типа ω, например, это были натуральные числа). Это естественно, ведь с точки зрения порядка все подобные множества просто неразличимы. В своё время Джон фон Нейман, используя эту идею, предложил считать каждый ординал не просто объектом, а конкретным представителем того класса подобных множеств, которые он определяет.
Теперь ординал это не просто некая эфемерная сущность, а конкретное множество, с которым можно работать. В таком случае порядок на любом множестве ординалов можно ввести как порядок по включению, иными словами, ординал α меньше, ординала β, если α есть подмножество β (говоря конкретнее, во множестве β существует подмножество подобное множеству α). Вишенкой на торте такого подхода является тот факт, что Нейман указал конкретно, какое именно из всего многообразия подобных множеств считать ординалом. А именно:
Ординал есть вполне упорядоченное множество, состоящее из всех ординалов, меньших его
Гениальность такого подхода заключается в том, что оно наиболее полно отражает саму суть ординала как индуктивно определяемого объекта. Что это значит? Теперь совокупность всех ординалов может быть в некотором роде построена поэтапно, начиная с одного конкретного ординала. Это как раз то, о чём мы говорили выше, когда пытались понять, зачем нам в принципе нужны вполне упорядоченные множества. Проиллюстрируем это более подробно.
Минимальным ординалом является ординал 0, являющийся пустым множеством. Следом за ним расположен ординал 1, который является множеством всех предшествующих ему ординалов, то есть множеством { 0 }. Следующий ординал — это 2 = { 0, 1 }. Далее идёт ординал 3 = { 0, 1, 2 }. Вообще, ординал n имеет вид { 0, 1, 2, …, n-1 }. Так мы можем построить все конечные ординалы. Множество всех конечных ординалов является первым трансфинитным ординальным числом и, как мы уже знаем, обозначается ω = { 0, 1, 2, … }. Следом за ним расположено число ω + 1 = { 0, 1, 2, …, ω } (здесь видно согласование с операцией сложения над порядковыми типами, введённой нами выше). Следом будет идти ω + 2 = { 0, 1, 2, …, ω, ω+1 }. После всех чисел вида ω + n идёт число ω + ω = ω⋅2 = { 0, 1, 2, …, ω, ω+1, ω+2, … } (и снова это множество всех предыдущих ординалов). Такого же рода переходом мы в конце концов получим ординалы ω⋅3, ω⋅4, …, ω⋅n, … Объединив все описанные ранее ординалы, мы получим ординал ω⋅ω = ω² (и снова, выписав его представление, мы убедимся в полнейшем согласовании введённых ранее операции с новым определением). Что идёт дальше? Правильно, ординал, полученный присоединением элемента ω² к самому себе (читай, ко множеству всех предыдущих ординалов), равный ω² + 1. В конце концов мы придём к ординалу ω³ и двинемся дальше. Построив все конечные степени ординала ω и объединив все имеющиеся у нас ординалы, мы получим ординал ω^ω ("омега в степени омега", к сожалению, Дзен не позволяет записывать символы в верхнем индексе). Чтобы примерно представить себе, что это за множество, скажу, что его представителем является множество всех монотонных функций из натуральных чисел в натуральные числа.
Ясно, что ω^ω не является последним ординалом. Присоединив его к самому себе, мы получим ординал ω^ω + 1 и продолжим цепочку (получая на некоторых этапах, например, ординалы ω^ω^ω, ω^ω^ω^ω и так далее). В конце концов, построив несчётное множество ординалов и объединив их, мы получим первый несчётный ординал — ω₁ — и продолжим далее. Вообще, ясно, что наибольшего ординала не существует: если бы он существовал, то присоединение его к самому себе в качестве элемента дало бы нам ординал, который, очевидно, больше наибольшего. Кроме того, какое бы множество ординалов мы не рассматривали, их объединение всегда будет ординалом. Это позволяет нам строить ординалы намного более простым способом, чем индуктивно перебирать каждый следующий. А именно если у нас есть некая индексированная совокупность ординалов (занумерованная некоторым вполне упорядоченным множеством), монотонно возрастающая с ростом индекса, то у этой совокупности существует так называемый предел, являющийся ничем иным, как объединением всех ординалов этой совокупности. Например, нумеруя "башни" из чисел ω (ω^ω^ω^...) высотой такой "башни", мы получим монотонно возрастающее с ростом индекса множество (занумерованное натуральными числами). Выходит, оно имеет предел. Этот предел обозначают ε₀, и оно тоже является ординалом (причём всего лишь счётным). Вообще, существование некоторых действительно "больших" ординалов (которые уж точно нельзя получить с помощью предела) приходится принимать как аксиому, так как оно просто недоказуемо (также как в своё время пришлось принять аксиому выбора, она же теорема Цермело). А кроме того, совокупность ВСЕХ ординальных чисел столь велика, что даже не является множеством сама по себе!
Таким образом, ординальные числа являются в некотором плане естественным расширением натурального ряда в сторону бесконечности, вобравшее в себя основные свойства натуральных чисел, связанных с порядком. Вот только такое расширение столь многообъемлюще, что не поддаётся полному описанию имеющимися математическими инструментами. На этом я, пожалуй, закончу данный экскурс в теорию порядковых чисел. Спасибо за внимание.