В теории множеств порядковое число , или ординал , является обобщением порядковых числительных (первый, второй, n- й и т. д.), направленным на расширение перечисления до бесконечных множеств . [1]
Конечное множество может быть пронумеровано путем последовательного присвоения каждому элементу наименьшего натурального числа , которое ранее не использовалось. Чтобы распространить этот процесс на различные бесконечные множества , порядковые числа определяются более обобщенно с использованием линейно упорядоченных греческих буквенных переменных , которые включают натуральные числа и обладают тем свойством, что каждое множество порядковых чисел имеет наименьший или «наименьший» элемент (это необходимо для придания смысла «наименьшим неиспользованным элементам»). [2] Это более общее определение позволяет нам определить порядковое число (омегу) как наименьший элемент, который больше любого натурального числа, наряду с порядковыми числами , и т. д., которые даже больше .
Линейный порядок, такой что каждое непустое подмножество имеет наименьший элемент, называется вполне упорядоченным . Аксиома выбора подразумевает, что каждое множество может быть вполне упорядоченным, и если даны два вполне упорядоченных множества, одно изоморфно начальному сегменту другого. Таким образом, порядковые числа существуют и по сути уникальны.
Порядковые числа отличаются от кардинальных чисел , которые измеряют размер множеств. Хотя различие между порядковыми и кардинальными числами не всегда очевидно на конечных множествах (можно перейти от одного к другому, просто подсчитав метки), они сильно отличаются в бесконечном случае, где различные бесконечные порядковые числа могут соответствовать множествам с одинаковым кардинальным числом. Как и другие виды чисел, порядковые числа можно складывать, умножать и возводить в степень , хотя ни одна из этих операций не является коммутативной .
Ординалы были введены Георгом Кантором в 1883 году [3] для того, чтобы охватить бесконечные последовательности и классифицировать производные множества , которые он ранее ввел в 1872 году, изучая уникальность тригонометрических рядов . [4]
Натуральное число ( которое в данном контексте включает число ) может использоваться для двух целей: для описания размера множества или для описания положения элемента в последовательности. При ограничении конечными множествами эти два понятия совпадают, поскольку все линейные порядки конечного множества изоморфны .
Однако при работе с бесконечными множествами необходимо различать понятие размера, которое приводит к кардинальным числам , и понятие положения, которое приводит к порядковым числам, описанным здесь. Это связано с тем, что, хотя любое множество имеет только один размер (его мощность ), существует множество неизоморфных хорошо упорядоченных множеств любого бесконечного множества, как объясняется ниже.
В то время как понятие кардинального числа связано с множеством без какой-либо конкретной структуры, ординалы тесно связаны с особым видом множеств, которые называются хорошо упорядоченными . Хорошо упорядоченное множество — это полностью упорядоченное множество ( упорядоченное множество, такое, что при наличии двух различных элементов один меньше другого), в котором каждое непустое подмножество имеет наименьший элемент. Эквивалентно, предполагая аксиому зависимого выбора , это полностью упорядоченное множество без какой-либо бесконечной убывающей последовательности — хотя могут быть бесконечные возрастающие последовательности. Ординалы могут использоваться для маркировки элементов любого данного хорошо упорядоченного множества (наименьший элемент маркируется 0, следующий за ним 1, следующий 2, «и так далее»), и для измерения «длины» всего множества наименьшим ординалом, который не является меткой для элемента множества. Эта «длина» называется типом порядка множества.
Любой ординал определяется набором ординалов, которые ему предшествуют. Фактически, наиболее распространенное определение ординалов идентифицирует каждый ординал как набор ординалов, которые ему предшествуют. Например, ординал 42 обычно идентифицируется как набор {0, 1, 2, ..., 41}. Наоборот, любой набор S ординалов, который замкнут вниз — это означает, что для любого ординала α из S и любого ординала β < α, β также находится в S — является (или может быть идентифицирован с) ординалом.
Это определение ординалов в терминах множеств допускает бесконечные ординалы. Наименьший бесконечный ординал — это , который можно отождествить с множеством натуральных чисел (так что ординал, связанный с каждым натуральным числом, предшествует ). Действительно, множество натуральных чисел вполне упорядочено — как и любое множество ординалов — и поскольку оно замкнуто вниз, его можно отождествить с ординалом, связанным с ним.
Возможно, более ясное представление о ординалах можно получить, изучив несколько первых из них: как упоминалось выше, они начинаются с натуральных чисел, 0, 1, 2, 3, 4, 5, ... После всех натуральных чисел идет первый бесконечный ординал, ω, а затем идут ω+1, ω+2, ω+3 и т. д. (Точно, что означает сложение, будет определено позже: просто рассматривайте их как имена.) После всех этих чисел идут ω·2 (что есть ω+ω), ω·2+1, ω·2+2 и т. д., затем ω·3, а затем еще позже ω·4. Теперь множество ординалов, образованное таким образом (ω· m + n , где m и n — натуральные числа), само должно иметь связанный с ним ординал: и это ω 2 . Далее будет ω 3 , затем ω 4 и так далее, и ω ω , затем ω ω ω , затем позже ω ω ω ω , и даже позже ε 0 ( эпсилон ноль ) (чтобы привести несколько примеров относительно малых — счетных — ординалов). Это можно продолжать до бесконечности (поскольку каждый раз, когда говорят «и так далее» при перечислении ординалов, это определяет больший ординал). Наименьший несчетный ординал — это множество всех счетных ординалов, выраженное как ω 1 или . [5]
В хорошо упорядоченном множестве каждое непустое подмножество содержит отдельный наименьший элемент. Учитывая аксиому зависимого выбора , это эквивалентно утверждению, что множество полностью упорядочено и не существует бесконечной убывающей последовательности (последнее легче визуализировать). На практике важность хорошо упорядоченного множества оправдывается возможностью применения трансфинитной индукции , которая, по сути, гласит, что любое свойство, которое передается от предшественников элемента к самому этому элементу, должно быть истинным для всех элементов (данного хорошо упорядоченного множества). Если состояния вычисления (компьютерной программы или игры) могут быть хорошо упорядочены — таким образом, что за каждым шагом следует «более низкий» шаг — то вычисление завершится.
Неуместно различать два хорошо упорядоченных множества, если они отличаются только «маркировкой своих элементов», или более формально: если элементы первого множества можно сопоставить с элементами второго множества таким образом, что если один элемент меньше другого в первом множестве, то партнер первого элемента меньше партнера второго элемента во втором множестве, и наоборот. Такое взаимно-однозначное соответствие называется изоморфизмом порядка , а два хорошо упорядоченных множества называются изоморфными по порядку или подобными (с пониманием того, что это отношение эквивалентности ).
Формально, если частичный порядок ≤ определен на множестве S , а частичный порядок ≤' определен на множестве S' , то частично упорядоченные множества ( S ,≤) и ( S' ,≤') являются порядково изоморфными , если существует биекция f , сохраняющая порядок. То есть, f ( a ) ≤' f ( b ) тогда и только тогда, когда a ≤ b . При условии, что существует порядковый изоморфизм между двумя вполне упорядоченными множествами, порядковый изоморфизм является единственным: это делает вполне оправданным рассматривать два множества как по существу идентичные и искать «канонического» представителя типа (класса) изоморфизма. Это именно то, что предоставляют ординалы, и это также обеспечивает каноническую маркировку элементов любого вполне упорядоченного множества. Каждое вполне упорядоченное множество ( S ,<) является порядково-изоморфным множеству ординалов, меньших одного конкретного порядкового числа при их естественном упорядочении. Это каноническое множество является типом порядка ( S ,<).
По сути, ординал предполагается определить как класс изоморфизма хорошо упорядоченных множеств: то есть как класс эквивалентности для отношения эквивалентности «быть изоморфным по порядку». Однако существует техническая трудность, связанная с тем, что класс эквивалентности слишком велик, чтобы быть множеством в обычной формализации теории множеств Цермело–Френкеля (ZF). Но это не серьезная трудность. Можно сказать, что ординал является типом порядка любого множества в классе.
Первоначальное определение порядковых чисел, найденное, например, в Principia Mathematica , определяет тип порядка вполне упорядоченного множества как множество всех вполне упорядоченных множеств, подобных (изоморфных по порядку) этому вполне упорядоченному множеству: другими словами, порядковое число действительно является классом эквивалентности вполне упорядоченных множеств. Это определение должно быть оставлено в ZF и связанных системах аксиоматической теории множеств , поскольку эти классы эквивалентности слишком велики, чтобы образовать множество. Однако это определение все еще может быть использовано в теории типов и в аксиоматической теории множеств Куайна New Foundations и связанных системах (где оно дает довольно удивительное альтернативное решение парадокса Бурали-Форти наибольшего порядкового числа).
Вместо того, чтобы определять ординал как класс эквивалентности хорошо упорядоченных множеств, он будет определяться как конкретное хорошо упорядоченное множество, которое (канонически) представляет класс. Таким образом, ординальное число будет хорошо упорядоченным множеством; и каждое хорошо упорядоченное множество будет изоморфно по порядку ровно одному ординальному числу.
Для каждого вполне упорядоченного множества T , определяет изоморфизм порядка между T и множеством всех подмножеств T , имеющих форму, упорядоченную включением. Это мотивирует стандартное определение, предложенное Джоном фон Нейманом в возрасте 19 лет, теперь называемое определением ординалов фон Неймана : "каждый ординал является вполне упорядоченным множеством всех меньших ординалов". В символах . [6] [7] Формально:
Таким образом, натуральные числа являются порядковыми числами по этому определению. Например, 2 является элементом 4 = {0, 1, 2, 3}, а 2 равно {0, 1} и, таким образом, является подмножеством {0, 1, 2, 3} .
С помощью трансфинитной индукции можно показать , что каждое вполне упорядоченное множество изоморфно по порядку ровно одному из этих ординалов, то есть между ними существует сохраняющая порядок биективная функция .
Более того, элементы каждого ординала сами являются ординалами. Если даны два ординала S и T , S является элементом T тогда и только тогда, когда S является собственным подмножеством T . Более того, либо S является элементом T , либо T является элементом S , либо они равны. Таким образом, каждый набор ординалов полностью упорядочен . Кроме того, каждый набор ординалов является вполне упорядоченным. Это обобщает тот факт, что каждый набор натуральных чисел является вполне упорядоченным.
Следовательно, каждый ординал S является множеством, имеющим в качестве элементов в точности ординалы, меньшие S . Например, каждый набор ординалов имеет супремум , ординал, полученный путем взятия объединения всех ординалов в наборе. Это объединение существует независимо от размера множества, по аксиоме объединения .
Класс всех ординалов не является множеством. Если бы это было множество, можно было бы показать, что это ординал и, таким образом, член самого себя, что противоречило бы его строгому упорядочению по членству. Это парадокс Бурали-Форти . Класс всех ординалов по-разному называется «Ord», «ON» или «∞».
Ординал конечен тогда и только тогда, когда противоположный порядок также вполне упорядочен, что имеет место тогда и только тогда, когда каждое из его непустых подмножеств имеет наибольший элемент .
Существуют и другие современные формулировки определения ординала. Например, принимая аксиому регулярности , следующие являются эквивалентными для множества x :
Эти определения не могут использоваться в необоснованных теориях множеств . В теориях множеств с урэлементами необходимо дополнительно убедиться, что определение исключает появление урэлементов в ординалах.
Если α — любой ординал, а X — множество, то α-индексированная последовательность элементов X является функцией от α до X. Эта концепция, трансфинитная последовательность (если α бесконечно) или ординально-индексированная последовательность , является обобщением концепции последовательности . Обычная последовательность соответствует случаю α = ω, тогда как конечный α соответствует кортежу , также известному как строка .
Трансфинитная индукция справедлива в любом хорошо упорядоченном множестве, но она настолько важна по отношению к ординалам, что ее стоит здесь переформулировать.
То есть, если P (α) истинно всякий раз, когда P (β) истинно для всех β < α , то P (α) истинно для всех α. Или, более практично: чтобы доказать свойство P для всех ординалов α, можно предположить, что оно уже известно для всех меньших β < α .
Трансфинитная индукция может использоваться не только для доказательства вещей, но и для их определения. Обычно говорят, что такое определение дается трансфинитной рекурсией — доказательство того, что результат хорошо определен, использует трансфинитную индукцию. Пусть F обозначает (класс) функцию F, которая должна быть определена на ординалах. Идея теперь заключается в том, что при определении F (α) для неопределенного ординала α можно предположить, что F (β) уже определено для всех β < α, и таким образом дать формулу для F (α) в терминах этих F (β). Затем с помощью трансфинитной индукции следует, что существует одна и только одна функция, удовлетворяющая формуле рекурсии вплоть до α включительно.
Вот пример определения с помощью трансфинитной рекурсии на ординалах (подробнее будет позже): определим функцию F , позволив F (α) быть наименьшим ординалом, не входящим в множество { F (β) | β < α} , то есть множество, состоящее из всех F (β) для β < α . Это определение предполагает, что F (β) известно в самом процессе определения F ; этот кажущийся порочный круг — именно то, что допускает определение с помощью трансфинитной рекурсии. Фактически, F (0) имеет смысл, поскольку не существует ординала β < 0 , а множество { F (β) | β < 0} пусто. Поэтому F (0) равно 0 (наименьшему ординалу из всех). Теперь, когда F (0) известно, определение, примененное к F (1), имеет смысл (это наименьший ординал, не входящий в синглтон-множество { F (0)} = {0} ), и так далее ( и так далее — это в точности трансфинитная индукция). Оказывается, этот пример не очень интересен, поскольку доказуемо F (α) = α для всех ординалов α, что можно показать, как раз, трансфинитной индукцией.
Любой ненулевой ординал имеет минимальный элемент, ноль. Он может иметь или не иметь максимальный элемент. Например, 42 имеет максимум 41, а ω+6 имеет максимум ω+5. С другой стороны, ω не имеет максимума, поскольку не существует наибольшего натурального числа. Если ординал имеет максимум α, то это следующий ординал после α, и он называется последовательным ординалом , а именно последователем α, записанным как α+1. В определении фон Неймана ординалов последователем α является , поскольку его элементы являются элементами α и самого α. [6]
Ненулевой ординал, который не является последователем, называется предельным ординалом . Одним из обоснований этого термина является то, что предельный ординал является пределом в топологическом смысле всех меньших ординалов (в топологии порядка ).
Когда — порядковая индексированная последовательность, индексированная пределом , и последовательность возрастает , т. е. всякий раз, когда ее предел определяется как наименьшая верхняя граница множества , то есть наименьший порядковый номер (он всегда существует), больший любого члена последовательности. В этом смысле предельный порядковый номер — это предел всех меньших порядковых номеров (индексированных самим собой). Говоря более прямо, это супремум множества меньших порядковых номеров.
Другой способ определения предельного ординала — сказать, что α является предельным ординалом тогда и только тогда, когда:
Итак, в следующей последовательности:
ω является предельным ординалом, поскольку для любого меньшего ординала (в данном примере натурального числа) существует другой ординал (натуральное число), больший его, но все еще меньший ω.
Таким образом, каждый ординал является либо нулем, либо последователем (хорошо определенного предшественника), либо пределом. Это различие важно, поскольку многие определения с помощью трансфинитной рекурсии опираются на него. Очень часто при определении функции F с помощью трансфинитной рекурсии по всем ординалам определяются F (0) и F (α+1), предполагая, что F (α) определено, а затем для предельных ординалов δ определяется F (δ) как предел F (β) для всех β<δ (либо в смысле пределов ординалов, как объяснялось ранее, либо для некоторого другого понятия предела, если F не принимает порядковых значений). Таким образом, интересным шагом в определении является шаг последователя, а не предельные ординалы. Такие функции (особенно для F , не убывающих и принимающих порядковые значения) называются непрерывными. Порядковое сложение, умножение и возведение в степень непрерывны как функции своего второго аргумента (но могут быть определены нерекурсивно).
Любой хорошо упорядоченный набор подобен (изоморфен по порядку) уникальному порядковому числу ; другими словами, его элементы могут быть проиндексированы в возрастающем порядке порядковыми числами, меньшими . Это применимо, в частности, к любому набору порядковых чисел: любой набор порядковых чисел естественным образом индексируется порядковыми числами, меньшими некоторого . То же самое справедливо, с небольшим изменением, для классов порядковых чисел (совокупность порядковых чисел, возможно, слишком большая, чтобы образовать множество, определяемая некоторым свойством): любой класс порядковых чисел может быть проиндексирован порядковыми числами (и, когда класс не ограничен в классе всех порядковых чисел, это помещает его в класс-биекцию с классом всех порядковых чисел). Таким образом, о -ом элементе в классе (с соглашением, что «0-й» является наименьшим, «1-й» является следующим наименьшим и т. д.) можно говорить свободно. Формально определение осуществляется с помощью трансфинитной индукции: -й элемент класса определяется (при условии, что он уже определен для всех ), как наименьший элемент, больший -го элемента для всех .
Это можно применить, например, к классу предельных ординалов: -й ординал, который является либо пределом, либо нулем, есть (см. ординальную арифметику для определения умножения ординалов). Аналогично можно рассмотреть аддитивно неразложимые ординалы (имея в виду ненулевой ординал, который не является суммой двух строго меньших ординалов): -й аддитивно неразложимый ординал индексируется как . Техника индексации классов ординалов часто полезна в контексте неподвижных точек: например, -й ординал, такой что записывается . Они называются « числами эпсилон ».
Говорят, что класс ординалов является неограниченным или конфинальным , когда для любого ординала существует такой , что (тогда класс должен быть собственным классом, т. е. он не может быть множеством). Говорят, что он замкнут , когда предел последовательности ординалов в классе снова находится в классе: или, что то же самое, когда индексирующая (классовая) функция непрерывна в том смысле, что для предельного ординала ( -й ординал в классе) является пределом всех для ; это также то же самое, что быть замкнутым в топологическом смысле для топологии порядка (чтобы избежать разговоров о топологии на собственных классах, можно потребовать, чтобы пересечение класса с любым данным ординалом было замкнуто для топологии порядка на этом ординале, это снова эквивалентно).
Особое значение имеют те классы ординалов, которые замкнуты и неограничены , иногда называемые клубами . Например, класс всех предельных ординалов замкнут и неограничен: это переводит тот факт, что всегда существует предельный ординал, больший заданного ординала, и что предел предельных ординалов является предельным ординалом (удачный факт, если терминология вообще должна иметь смысл!). Класс аддитивно неразложимых ординалов, или класс ординалов , или класс кардиналов, все замкнуты и неограничены; множество регулярных кардиналов, однако, неограничено, но не замкнуто, и любое конечное множество ординалов замкнуто, но не неограничено.
Класс стационарен, если он имеет непустое пересечение с каждым замкнутым неограниченным классом. Все суперклассы замкнутых неограниченных классов стационарны, а стационарные классы неограниченны, но есть стационарные классы, которые не замкнуты, и стационарные классы, которые не имеют замкнутого неограниченного подкласса (например, класс всех предельных ординалов со счетной конфинальностью). Поскольку пересечение двух замкнутых неограниченных классов замкнуто и неограниченно, пересечение стационарного класса и замкнутого неограниченного класса стационарно. Но пересечение двух стационарных классов может быть пустым, например, класс ординалов с конфинальностью ω с классом ординалов с несчетной конфинальностью.
Вместо того, чтобы формулировать эти определения для (собственных) классов ординалов, можно сформулировать их для множеств ординалов ниже заданного ординала : Подмножество предельного ординала называется неограниченным (или конфинальным) при , при условии, что любой ординал, меньший, меньше некоторого ординала в множестве. В более общем смысле, можно назвать подмножество любого ординала конфинальным в , при условии, что каждый ординал, меньший, меньше или равен некоторому ординалу в множестве. Подмножество называется замкнутым при , при условии, что оно замкнуто для топологии порядка в , т. е. предел ординалов в множестве либо находится в множестве, либо равен самому себе.
Существует три обычных операции над ординалами: сложение, умножение и возведение в степень. Каждая из них может быть определена по существу двумя различными способами: либо путем построения явного хорошо упорядоченного множества, представляющего операцию, либо с помощью трансфинитной рекурсии. Нормальная форма Кантора обеспечивает стандартизированный способ записи ординалов. Она однозначно представляет каждый ординал как конечную сумму степеней ординала ω. Однако это не может стать основой универсальной ординальной нотации из-за таких самореферентных представлений, как ε 0 = ω ε 0 .
Ординалы являются подклассом класса сюрреалистических чисел , а так называемые «естественные» арифметические операции для сюрреалистических чисел являются альтернативным способом арифметического комбинирования ординалов. Они сохраняют коммутативность за счет непрерывности.
Интерпретируемые как нимберы , игровой вариант чисел, ординалы также могут быть объединены посредством арифметических операций нимбера. Эти операции являются коммутативными, но ограничение натуральными числами, как правило, не совпадает с обычным сложением натуральных чисел.
Каждый ординал ассоциируется с одним кардиналом , его мощностью. Если между двумя ординалами существует биекция (например, ω = 1 + ω и ω + 1 > ω ), то они ассоциируются с одним и тем же кардиналом. Любое вполне упорядоченное множество, имеющее ординал в качестве своего типа порядка, имеет ту же мощность, что и этот ординал. Наименьший ординал, связанный с данным кардиналом, называется начальным ординалом этого кардинала. Каждый конечный ординал (натуральное число) является начальным, и никакой другой ординал не ассоциируется с его кардиналом. Но большинство бесконечных ординалов не являются начальными, так как многие бесконечные ординалы ассоциируются с тем же кардиналом. Аксиома выбора эквивалентна утверждению, что каждое множество может быть вполне упорядочено, т. е. что каждый кардинал имеет начальный ординал. В теориях с аксиомой выбора кардинальное число любого множества имеет начальный ординал, и можно использовать назначение кардинала фон Неймана в качестве представления кардинала. (Однако, мы должны быть осторожны и различать кардинальную арифметику и порядковую арифметику.) В теориях множеств без аксиомы выбора кардинальное число может быть представлено множеством множеств с этой мощностью, имеющим минимальный ранг (см. трюк Скотта ).
Одна из проблем с трюком Скотта заключается в том, что он отождествляет кардинальное число с , которое в некоторых формулировках является порядковым числом . Может быть, понятнее применить кардинальное назначение фон Неймана к конечным случаям и использовать трюк Скотта для множеств, которые бесконечны или не допускают хороших упорядочений. Обратите внимание, что кардинальная и порядковая арифметика согласуются для конечных чисел.
α-й бесконечный начальный ординал записывается как , это всегда предельный ординал. Его мощность записывается как . Например, мощность ω 0 = ω равна , что также является мощностью ω 2 или ε 0 (все являются счетными ординалами). Таким образом, ω можно отождествить с , за исключением того, что обозначение используется при записи кардиналов, а ω — при записи ординалов (это важно, поскольку, например, = тогда как ). Кроме того, является наименьшим несчетным ординалом (чтобы убедиться в его существовании, рассмотрим множество классов эквивалентности вполне упорядоченных натуральных чисел: каждое такое вполне упорядоченное число определяет счетный ординал и является типом порядка этого множества), является наименьшим ординалом, мощность которого больше , и так далее, и является пределом для натуральных чисел n (любой предел кардиналов является кардиналом, поэтому этот предел действительно является первым кардиналом после всех ).
Конфинальность ординала — это наименьший ординал , который является типом порядка конфинального подмножества . Обратите внимание, что ряд авторов определяют конфинальность или используют ее только для предельных ординалов. Конфинальность набора ординалов или любого другого хорошо упорядоченного набора — это конфинальность типа порядка этого набора.
Таким образом, для предельного ординала существует -индексированная строго возрастающая последовательность с пределом . Например, конфинальность ω 2 равна ω, поскольку последовательность ω· m (где m пробегает натуральные числа) стремится к ω 2 ; но, в более общем случае, любой счетный предельный ординал имеет конфинальность ω. Несчетный предельный ординал может иметь либо конфинальность ω, как и делает , либо несчетную конфинальность.
Конфинальность 0 равна 0. А конфинальность любого последующего ординала равна 1. Конфинальность любого предельного ординала не менее .
Ординал, равный своей конфинальности, называется регулярным, и он всегда является начальным ординалом. Любой предел регулярных ординалов является пределом начальных ординалов и, таким образом, также является начальным, даже если он не является регулярным, что обычно не так. Если Аксиома выбора, то является регулярным для каждого α. В этом случае ординалы 0, 1, , , и являются регулярными, тогда как 2, 3, , и ω ω·2 являются начальными ординалами, которые не являются регулярными.
Конфинальность любого ординала α является регулярным ординалом, т.е. конфинальность конфинальности α такая же, как и конфинальность α . Таким образом, операция конфинальности является идемпотентной .
Как упоминалось выше (см. нормальную форму Кантора ), ординал ε 0 является наименьшим, удовлетворяющим уравнению , поэтому он является пределом последовательности 0, 1, , , и т. д. Многие ординалы можно определить таким образом как неподвижные точки некоторых ординальных функций ( -й ординал такой, что называется , затем можно было бы продолжать попытки найти -й ординал такой, что , «и так далее», но вся тонкость заключается в «и так далее»). Можно было бы попытаться сделать это систематически, но независимо от того, какая система используется для определения и построения ординалов, всегда есть ординал, который лежит чуть выше всех ординалов, построенных этой системой. Возможно, наиболее важным ординалом, ограничивающим систему построения таким образом, является ординал Чёрча-Клини (несмотря на в названии, этот ординал является счётным), который является наименьшим ординалом, который никак не может быть представлен вычислимой функцией (конечно, это можно сделать строгим). Однако ниже могут быть определены значительно большие ординалы , которые измеряют «теоретико-доказательную силу» некоторых формальных систем (например, измеряет силу арифметики Пеано ). Большие счётные ординалы, такие как счётные допустимые ординалы, также могут быть определены выше ординала Чёрча-Клини, которые представляют интерес в различных частях логики. [ требуется ссылка ]
Любое порядковое число можно превратить в топологическое пространство , наделив его топологией порядка ; эта топология дискретна тогда и только тогда, когда порядковое число является счетным кардиналом, т. е. не более ω. Подмножество ω + 1 открыто в топологии порядка тогда и только тогда, когда оно либо коконечно , либо не содержит ω в качестве элемента.
См. раздел Топология и ординалы в статье «Топология порядка».
Трансфинитные порядковые числа, впервые появившиеся в 1883 году, [8] возникли в работе Кантора с производными множествами . Если P — множество действительных чисел, производное множество P ′ — это множество предельных точек P . В 1872 году Кантор сгенерировал множества P ( n ) , применив операцию производного множества n раз к P . В 1880 году он указал, что эти множества образуют последовательность P' ⊇ ··· ⊇ P ( n ) ⊇ P ( n + 1) ⊇ ···, и продолжил процесс вывода, определив P ( ∞) как пересечение этих множеств. Затем он повторил операцию производного множества и пересечения, чтобы расширить свою последовательность множеств до бесконечности: P (∞) ⊇ P (∞ + 1) ⊇ P (∞ + 2) ⊇ ··· ⊇ P (2∞) ⊇ ··· ⊇ P (∞ 2 ) ⊇ ···. [9] Верхние индексы, содержащие ∞, являются просто индексами, определенными процессом вывода. [10]
Кантор использовал эти множества в теоремах:
Эти теоремы доказываются путем разбиения P ′ на попарно непересекающиеся множества: P ′ = ( P ′ \ P (2) ) ∪ ( P (2) \ P (3) ) ∪ ··· ∪ ( P (∞) \ P (∞ + 1) ) ∪ ··· ∪ P ( α ) . Для β < α : поскольку P ( β + 1) содержит предельные точки P ( β ) , множества P ( β ) \ P ( β + 1) не имеют предельных точек. Следовательно, они являются дискретными множествами , поэтому они счетны. Доказательство первой теоремы: Если P ( α ) = ∅ для некоторого индекса α , то P ′ является счетным объединением счетных множеств. Следовательно, P ′ счетно. [11]
Вторая теорема требует доказательства существования α такого, что P ( α ) = ∅ . Чтобы доказать это, Кантор рассмотрел множество всех α, имеющих счетное число предшественников. Чтобы определить это множество, он определил трансфинитные порядковые числа и преобразовал бесконечные индексы в порядковые числа, заменив ∞ на ω , первое трансфинитное порядковое число. Кантор назвал множество конечных порядковых чисел первым числовым классом . Вторым числовым классом является множество порядковых чисел, предшественники которых образуют счетное бесконечное множество. Множество всех α , имеющих счетное число предшественников, то есть множество счетных порядковых чисел, является объединением этих двух числовых классов. Кантор доказал, что мощность второго числового класса является первой несчетной мощностью. [12]
Вторая теорема Кантора становится: Если P ′ счетно, то существует счетное ординальное число α такое, что P ( α ) = ∅ . Ее доказательство использует доказательство от противного . Пусть P ′ счетно, и предположим, что такого α не существует. Это предположение приводит к двум случаям.
В обоих случаях P ′ несчетно, что противоречит счетности P ′ . Следовательно, существует счетный ординал α такой, что P ( α ) = ∅ . Работа Кантора с производными множествами и ординальными числами привела к теореме Кантора-Бендиксона . [14]
Используя последователей, пределы и мощность, Кантор сгенерировал неограниченную последовательность порядковых чисел и числовых классов. [15] ( α + 1) -й числовой класс — это множество порядковых чисел, предшественники которых образуют множество той же мощности, что и α -й числовой класс. Мощность ( α + 1) -го числового класса — это мощность, непосредственно следующая за мощностью α -го числового класса. [16] Для предельного ординала α α -й числовой класс — это объединение β -х числовых классов для β < α . [17] Его мощность — это предел мощностей этих числовых классов.
Если n конечно, то n -й числовой класс имеет мощность . Если α ≥ ω , то α -й числовой класс имеет мощность . [18] Следовательно, мощности числовых классов однозначно соответствуют числам алеф . Кроме того, α -й числовой класс состоит из ординалов, отличных от тех, что были в предыдущих числовых классах, тогда и только тогда, когда α является непредельным ординалом. Следовательно, непредельные числовые классы разбивают ординалы на попарно непересекающиеся множества.
