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

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

Порядковые числа были введены Георгом Кантором в 1883 году как способ описания бесконечных последовательностей, а также классификации множеств, обладающих определённой упорядоченной структурой.[1] Он случайно открыл порядковые числа, работая над задачей, связанной с тригонометрическими рядами.

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

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

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

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

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

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

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

любой ординал есть вполне упорядоченное множество, состоящее из всех ординалов, меньших его

С помощью трансфинитной индукции можно показать, что любое вполне упорядоченное множество подобно ровно одному ординалу — иначе говоря, между ними можно установить биективное соответствие, сохраняющее порядок.

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

В современной математике существуют и другие подходы к определению порядковых чисел. Так, при выполнении аксиомы регулярности следующие утверждения относительно множества x являются эквивалентными:

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