Порядковое число

В теории множеств порядковым числом, или ординалом ( — порядковый) называется порядковый тип вполне упорядоченного множества. Как правило, порядковые числа отождествляются с наследственно транзитивными множествами. Ординалы представляют собой одно из расширений натуральных чисел, отличающееся как от целых, так и от кардинальных чисел. Как и другие разновидности чисел, их можно складывать, перемножать и возводить в степень. Бесконечные порядковые числа называют трансфинитными ( — за, через +  — край, предел). Ординалы играют ключевую роль в доказательстве многих теорем теории множеств — в частности, благодаря связанному с ними принципу трансфинитной индукции.

Порядковые числа были введены Георгом Кантором в 1883 году как способ описания бесконечных последовательностей, а также классификации множеств, обладающих определённой упорядоченной структурой.Более подробное описание было дано Леви (1979) и Йехом (2003). Он случайно открыл порядковые числа, работая над задачей, связанной с тригонометрическими рядами.

Множества и обладают одинаковой мощностью, если между ними можно установить биективное соответствие (то есть указать такую функцию , которая одновременно является инъективной и сюръективной: каждому из соответствует единственное из , а каждое из является образом единственного из ).

Предположим, что на множествах и заданы частичные порядки и соответственно. Тогда частично упорядоченные множества и называются изоморфными с сохранением порядка, если существует биективное отображение , при котором заданный порядок сохраняется. Иначе говоря, тогда и только тогда, когда . Любое вполне упорядоченное множество изоморфно с сохранением порядка по отношению к естественно упорядоченному множеству порядковых чисел, меньших некоторого определённого ординала (равного порядковому типу ).

Конечные порядковые (и кардинальные) числа представляют собой числа натурального ряда: 0, 1, 2, …, поскольку два любых полных упорядочения конечного множества изоморфны с сохранением порядка. Наименьшее бесконечно большое порядковое число отождествляется с кардинальным числом . Однако в случае трансфинитных чисел, больших , ординалы — по сравнению с кардинальными числами — позволяют выразить более тонкую классификацию множеств, основанную на информации об их упорядоченности. В то время как все счётные множества описываются одним кардинальным числом, равным , число счётных ординалов бесконечно велико и притом несчётно:

В данном случае сложение и умножение не обладают свойством коммутативности: так, совпадает с , но отличается от ; аналогично , но не равно . Множество всех счётных ординалов образует первое несчётное порядковое число , соответствующее кардинальному числу (следующее число после ). Вполне упорядоченные кардинальные числа отождествляются с их начальными ординалами, то есть минимальными ординалами соответствующей мощности. Мощность порядкового числа задает между классами порядковых и кардинальных чисел соответствие по типу «многие к одному».

Обычно произвольный ординал определяется как порядковый тип множества ординалов, строго меньших . Данное свойство позволяет представить любое порядковое число в виде множества ординалов, строго меньших его самого. Все порядковые числа можно разбить на три категории: нуль, следующее порядковое число и предельное порядковое число (последние различаются своей конфинальностью). Для заданного класса порядковых чисел можно указать его -й элемент — иначе говоря, элементы класса можно проиндексировать (сосчитать). Такой класс будет замкнутым и неограниченным при условии, что функция индексирования непрерывна и никогда не останавливается. Нормальная форма Кантора позволяет единственным образом представить любое порядковое число в виде конечной суммы порядковых степеней . Тем не менее, такая форма не может использоваться в качестве основы для универсальной системы обозначения порядковых чисел из-за наличия в ней автореферентных представлений: например, .

Можно определять всё более крупные порядковые числа, однако по мере роста их описание усложняется. Любое порядковое число можно представить в виде топологического пространства, приписав ему порядковую топологию.

Такая топология будет дискретной, тогда и только тогда, когда соответствующий ординал не превышает счётного кардинального числа, то есть меньше или равен . Подмножество будет открытым в порядковой топологии тогда и только тогда, когда оно является кофинитным или не содержит в качестве элемента.

Порядковые числа как расширение множества натуральных чисел Натуральные числа (к которым в данном случае относится и 0) имеют два основных применения: описание размера некоторого множества и описание позиции элемента в заданной последовательности. В случае конечных множеств эти понятия совпадают; с точностью до изоморфизма существует единственный способ расположить элементы конечного множества в виде последовательности. В случае же бесконечных множеств необходимо отличать понятие размера и связанных с ним кардинальных чисел от понятия позиции, обобщением которого служат описанные в данной статье порядковые числа. Это объясняется тем, что бесконечное множество, обладая однозначно определённым размером (мощностью), может быть вполне упорядочено более чем одним неизоморфным способом.

В то время как понятие кардинального числа, связанного с множеством, не требует задания на нём какой-либо структуры, ординалы тесно связаны с особой разновидностью множеств, которые называются вполне упорядоченными (в сущности эти понятия настолько близки, что некоторые математики не делают между ними никаких различий). Данный термин обозначает линейно упорядоченное множество (то есть множество с некоторым единообразным способом выбора наименьшего и наибольшего значения для произвольной пары элементов), в котором нет бесконечно убывающих последовательностей (хотя могут существовать бесконечно возрастающие), или — в эквивалентной формулировке — множество, в котором любое непустое подмножество содержит наименьший элемент. Порядковые числа можно использовать как для обозначения элементов любого заданного вполне упорядоченного множества (наименьший элемент получает метку 0, следующий за ним — метку 1, следующий — 2, «и так далее»), так и для измерения «размера» всего множества путём указания наименьшего ординала, который не является меткой какого-либо элемента множества. Такой «размер» называется порядковым типом множества.

Любое порядковое число определяется множеством предшествующих ординалов: фактически наиболее распространённое определение порядкового числа отождествляет его со множеством предшествующих ординалов. Так, ординал 42 представляет собой порядковый тип множества предшествующих ординалов, то есть ординалов от 0 (наименьший ординал) до 41 (непосредственный предшественник 42), и обычно отождествляется со множеством . Верно и обратное: любое замкнутое вниз множество ординалов  — то есть такое, что для любого ординала и произвольного ординала ординал также является элементом  — само является ординалом (либо его можно отождествить с таковым).

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

Вероятно, более интуитивное представление о порядковых числах можно получить, рассмотрев несколько их первых представителей: как уже упоминалось выше, множество ординалов начинается с натуральных чисел После всех натуральных чисел располагается первый бесконечный ординал , за которым следуют , , , и так далее.

После всех таких чисел располагаются (то есть ), , , и так далее, затем , а после него — . Далее, множество ординалов, которые можно записать в виде , где и  — натуральные числа, также должно обладать соответствующим порядковым числом: таким числом будет . За ним последуют , ,…, , затем и — намного позже — («эпсилон-нуль») (перечисленные примеры дают представление о сравнительно небольших счётных ординалах). Этот процесс можно продолжать неограниченно (выражение «неограниченности» — это и есть сильная сторона порядковых чисел: собственно говоря, когда мы, перечисляя порядковые числа, употребляем выражение «и так далее», мы тем самым определяем порядковое число большего размера). Наименьший несчетный ординал представляет собой множество всех счётных ординалов и обозначается .

Определения Для обозначения порядковых чисел обычно используются строчные греческие буквы Данная статья придерживается таких обозначений.

Вполне упорядоченные множества

Каждое непустое подмножество вполне упорядоченного множества содержит наименьший элемент. При соблюдении аксиомы зависимого выбора это утверждение эквивалентно тому, что множество линейно упорядочено и не содержит бесконечно убывающих последовательностей — последняя формулировка, вероятно, проще поддаётся визуализации. На практике важность понятия вполне упорядоченности объясняется возможностью применения трансфинитной индукции, основная идея которой сводится к тому, что любое свойство, переходящее от предшественников элемента к нему самому, должно выполняться для всех элементов (входящих в заданное вполне упорядоченное множество). Если вычислительные состояния (компьютерной программы или игры) можно вполне упорядочить так, что каждый последующий шаг будет «меньше» предыдущего, то процесс вычислений гарантированно завершится.

Далее, мы не хотим различать два вполне упорядоченных множества, если они отличаются только «маркировкой своих элементов», или, говоря более формальным языком, если элементы первого множества можно так соотнести с элементами второго, что в произвольно взятой паре элементов одного множества первый меньше второго тогда и только тогда, когда то же соотношение имеет место между их соответствующими партнёрам из второго множества. Такое взаимно однозначное соответствие называется изоморфизмом, сохраняющим порядок, а два вполне упорядоченных множества называются изоморфными с сохранением порядка, или же подобными (такое подобие очевидно является отношением эквивалентности). Если два вполне упорядоченных множества изоморфны с сохранением порядка, то соответствующий изоморфизм является единственным: это обстоятельство позволяет воспринимать упомянутые множества как практически идентичные и служит основанием для поисков «каноничного» представления типов изоморфизма (классов). Порядковые числа не только играют роль такого представления, но ещё и предоставляют нам каноническую маркировку элементов любого вполне упорядоченного множества.

Иными словами, мы хотим ввести понятие ординала как класса изоморфизмов вполне упорядоченных множеств, то есть класса эквивалентности, основанного на отношении «изоморфности с сохранением порядка». При таком подходе, однако, существует одна техническая сложность: определённый таким образом класс эквивалентности оказывается слишком большим, чтобы подходить под определением множества с точки зрения стандартной формализации теории множеств по Цермело-Френкелю. Тем не менее, эта сложность не создает серьезных проблем. Ординалом мы будем называть порядковый тип произвольного множества в таком классе.

Определение порядковых чисел как классов эквивалентности