Порядковый номер

Эта статья о математической концепции. Числовые слова, обозначающие позицию в последовательности («первый», «второй», «третий» и т. д.), см. Порядковое числительное .

Представление порядковых чисел до ω ^ой . Один виток спирали соответствует отображению ⁠ $f(\alpha )=\omega (1+\alpha )$⁠ . С $f$ имеет $\omega ^{\omega }$ как наименьшая фиксированная точка, большие порядковые числа не могут быть представлены.

В теории множеств , порядковое число или ординал , — это обобщение порядковых числительных (первого, второго, n -го и т. д.), направленное на расширение перечисления на бесконечные множества .

Конечное множество можно перечислить, последовательно помечая каждый элемент наименьшим натуральным числом , которое ранее не использовалось. Чтобы распространить этот процесс на различные бесконечные множества , порядковые числа определяются в более общем смысле с использованием линейно упорядоченных греческих букв переменных , которые включают натуральные числа и обладают свойством, состоящим в том, что каждый набор порядковых номеров имеет наименьший элемент (это необходимо для придания смысла « наименьший неиспользованный элемент»). Это более общее определение позволяет нам определить порядковый номер. $\omega$ (омега) — наименьший элемент, который больше любого натурального числа, а также порядковых чисел ⁠ $\omega +1$⁠ , ⁠ $\omega +2$⁠ и т. д., которые даже больше, чем ⁠ $\omega$⁠ .

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

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

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

Порядковые номера расширяют натуральные числа

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

Однако, имея дело с бесконечными множествами, нужно различать понятие размера, которое приводит к кардинальным числам , и понятие положения, которое приводит к описанным здесь порядковым числам. Это связано с тем, что, хотя любое множество имеет только один размер (его мощность ), существует множество неизоморфных правильных порядков любого бесконечного множества, как объясняется ниже.

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

Любой порядковый номер определяется набором предшествующих ему порядковых номеров. Фактически, наиболее распространенное определение порядковых номеров идентифицирует каждый порядковый номер как набор предшествующих ему порядковых номеров. Например, порядковый номер 42 обычно идентифицируется как набор {0, 1, 2,..., 41}. И наоборот, любой набор S ординалов, замкнутый вниз - это означает, что для любого порядкового номера α в S и любого порядкового номера β < α, β также находится в S - является порядковым номером (или может быть отождествлен с ним).

Это определение ординалов в терминах множеств допускает бесконечные ординалы. Наименьший бесконечный порядковый номер — ⁠ $\omega$⁠ , который можно отождествить с набором натуральных чисел (так что порядковый номер, связанный с каждым натуральным числом, предшествует $\omega$). Действительно, набор натуральных чисел хорошо упорядочен, как и любой набор ординалов, и, поскольку он замкнут вниз, его можно отождествить со связанным с ним порядковым номером.

Графическое представление порядкового номера ω в виде спичек. ² . Каждая палочка соответствует порядковому номеру вида ω · m + n , где m и n — натуральные числа.

Возможно, более ясное представление об ординалах можно получить, изучив первые несколько из них: как упоминалось выше, они начинаются с натуральных чисел: 0, 1, 2, 3, 4, 5... После всех натуральных чисел идут первые числа. бесконечный порядковый номер ω, а после него идут ω+1, ω+2, ω+3 и так далее. (Что именно означает сложение, будет определено позже: просто считайте их именами.) После всего этого следуют ω·2 (то есть ω+ω), ω·2+1, ω·2+2 и т. д. затем ω·3, а затем ω·4. Теперь набор ординалов, сформированный таким образом (ω · m + n , где m и n — натуральные числа), сам должен иметь связанный с ним ординал: и это ω ² . Далее будет ω ³ , то ω ⁴ и т. д., а ω ^ой , то ω ^{ой ой} , затем позже ω ^{ой ой ой} , и даже позже ε ₀ ( эпсилон ноль ) (чтобы привести несколько примеров относительно небольших счетных порядковых номеров). Это можно продолжать бесконечно (поскольку каждый раз, когда при перечислении порядковых номеров говорят «и так далее», это определяет больший порядковый номер). Наименьший неисчисляемый ординал — это совокупность всех счетных ординалов, выраженная как ω ₁ или ⁠. $\Omega$⁠ .

Определения

Хорошо упорядоченные наборы

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

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

Формально, если частичный порядок определен на множестве S определен частичный порядок ≤’ ≤, а на множестве S’ , то частично упорядоченные множества ( S ,≤) и ( S’ ,≤’) порядково изоморфны , если существует биекция , f сохраняющая порядок. То есть f ( a ) ≤' f ( b ) тогда и только тогда, когда a ≤ b . Если между двумя вполне упорядоченными множествами существует порядковый изоморфизм, то порядковый изоморфизм единственен: это позволяет вполне оправданно считать два множества по существу тождественными и искать «канонического» представителя типа (класса) изоморфизма. Именно это и обеспечивают ординалы, а также каноническую маркировку элементов любого хорошо упорядоченного множества. Каждое хорошо упорядоченное множество ( S ,<) порядково изоморфно множеству ординалов меньше одного конкретного порядкового числа при их естественном порядке. Этот канонический набор имеет тип порядка ( S ,<).

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

Определение ординала как класса эквивалентности

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

Определение ординалов фон Нейманом

См. Также: Теоретико-множественное определение натуральных чисел и ординалов Цермело.

Первые несколько ординалов фон Неймана

0	=	{}	=	∅
1	=	{0}	=	{∅}
2	=	{0,1}	=	{∅,{∅}}
3	=	{0,1,2}	=	{∅,{∅},{∅,{∅}}}
4	=	{0,1,2,3}	=	{∅,{∅},{∅,{∅}},{∅,{∅},{∅,{∅}}}}

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

вполне упорядоченного множества T Для каждого $a\mapsto T_{<a}$ определяет порядковый изоморфизм между T и множеством всех подмножеств T, имеющих вид $T_{<a}:=\{x\in T\mid x<a\}$ упорядочены по включению. Это мотивирует стандартное определение, предложенное Джоном фон Нейманом в возрасте 19 лет, которое теперь называется определением ординалов фон Неймана : «каждый ординал представляет собой хорошо упорядоченный набор всех меньших ординалов». Символами ⁠ $\lambda =[0,\lambda )$⁠ . Формально:

Множество S является ординалом тогда и только тогда, когда S упорядочено строго относительно принадлежности к множеству и каждый элемент S также является подмножеством S .

Таким образом, натуральные числа по этому определению являются порядковыми. Например, 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 ,
• x — транзитивное множество, полностью упорядоченное по включению множества,
• x — транзитивное множество транзитивных множеств.

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

Трансфинитная последовательность

Если α — любой порядковый номер, а 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. В определении ординалов фон Неймана преемником α является $\alpha \cup \{\alpha \}$ поскольку его элементы являются элементами α и самого α.

Ненулевой порядковый номер, который не является преемником, называется предельным порядковым номером . Одним из оправданий этого термина является то, что предельный ординал является пределом в топологическом смысле всех меньших ординалов (в соответствии с топологией порядка ).

Когда $\langle \alpha _{\iota }|\iota <\gamma \rangle$ представляет собой порядковую индексированную последовательность, индексированную пределом $\gamma$ и последовательность возрастает , т.е. $\alpha _{\iota }<\alpha _{\rho }$ в любое время $\iota <\rho ,$ его предел определяется как наименьшая верхняя граница множества $\{\alpha _{\iota }|\iota <\gamma \},$ то есть наименьший порядковый номер (он всегда существует), больший любого члена последовательности. В этом смысле предельный порядковый номер — это предел всех меньших порядковых номеров (индексированных сам по себе). Говоря более прямо, это верхняя граница множества меньших порядковых номеров.

Другой способ определения предельного ординала состоит в том, чтобы сказать, что α является предельным ординалом тогда и только тогда, когда:

Существует ординал меньше α, и если ζ ординал меньше α, то существует ординал ξ такой, что ζ < ξ < α.

Итак, в следующей последовательности:

0, 1, 2, ..., ω, ω+1

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

Таким образом, каждый ординал является либо нулем, либо преемником (чётко определенного предшественника), либо пределом. Это различие важно, потому что на него опираются многие определения трансфинитной рекурсии. Очень часто при определении функции F посредством трансфинитной рекурсии по всем ординалам определяют F (0) и F (α+1), предполагая, что F (α) определена, а затем для предельных ординалов δ определяют F (δ) как предел F (β) для всех β<δ (либо в смысле порядковых пределов, как объяснялось ранее, либо для какого-либо другого понятия предела, если F не принимает порядковые значения). Таким образом, интересным шагом в определении является последующий шаг, а не предельные ординалы. Такие функции (особенно для F, неубывающих и принимающих порядковые значения) называются непрерывными. Порядковое сложение, умножение и возведение в степень непрерывны как функции второго аргумента (но могут быть определены нерекурсивно).

Индексирование классов ординалов

Любой хорошо упорядоченный набор подобен (изоморфен по порядку) уникальному порядковому числу. $\alpha$; другими словами, его элементы можно индексировать по возрастанию порядковыми номерами меньше ⁠ $\alpha$⁠ . Это относится, в частности, к любому набору ординалов: любой набор ординалов естественно индексируется ординалами меньшими, чем некоторые ⁠ $\alpha$⁠ . То же самое, с небольшой модификацией, справедливо и для классов ординалов (набор ординалов, возможно, слишком большой, чтобы сформировать набор, определяемый каким-либо свойством): любой класс ординалов может быть проиндексирован ординалами (и, когда класс неограничен в классе всех ординалов это ставит его в класс-биекцию с классом всех ординалов). Итак, $\gamma$О -ом элементе класса (при соглашении, что «0-й» является наименьшим, «1-й» — следующим по величине и т. д.) можно свободно говорить. Формально определение осуществляется с помощью трансфинитной индукции: $\gamma$-й элемент класса определен (при условии, что он уже определен для всех $\beta <\gamma$), как наименьший элемент, больший, чем $\beta$-й элемент для всех ⁠ $\beta <\gamma$⁠ .

Это можно применить, например, к классу предельных ординалов: $\gamma$-й порядковый номер, который является либо пределом, либо нулем, равен $\omega \cdot \gamma$ ( см. в порядковой арифметике определение умножения порядковых чисел ). Аналогичным образом можно рассматривать аддитивно неразложимые ординалы (имеется в виду ненулевой ординал, который не является суммой двух строго меньших ординалов): $\gamma$-й аддитивно неразложимый ординал индексируется как ⁠ $\omega ^{\gamma }$⁠ . Техника индексации классов ординалов часто бывает полезна в контексте фиксированных точек: например, $\gamma$-й порядковый номер $\alpha$ такой, что $\omega ^{\alpha }=\alpha$ написано ⁠ $\varepsilon _{\gamma }$⁠ . Их называют « эпсилон-числами ».

Закрытые неограниченные множества и классы

Класс $C$ ординалов называется неограниченным или конфинальным , если задан любой порядковый номер ⁠ $\alpha$⁠ , есть $\beta$ в $C$ такой, что $\alpha <\beta$ (тогда класс должен быть собственным классом, т. е. он не может быть множеством). Говорят, что он закрыт , когда предел последовательности ординалов в классе снова находится в классе: или, что то же самое, когда индексирующая (классовая) функция $F$ непрерывен в том смысле, что для $\delta$ предельный порядковый номер, $F(\delta )$ ( $\delta$-й порядковый номер в классе) является пределом всех $F(\gamma )$ для $\gamma <\delta$; это также то же самое, что быть замкнутым в топологическом смысле для порядковой топологии (чтобы не говорить о топологии собственных классов, можно потребовать, чтобы пересечение класса с любым данным порядковым номером было замкнутым для порядковой топологии на этом порядковом номере). , это снова эквивалентно).

Особое значение имеют те классы ординалов, которые являются замкнутыми и неограниченными , иногда называемые трефами . Например, класс всех предельных ординалов является замкнутым и неограниченным: это отражает тот факт, что всегда существует предельный ординал, больший заданного, и что предел предельных ординалов является предельным ординалом (счастливый факт, если использовать терминологию). вообще иметь какой-то смысл!). Класс аддитивно неразложимых ординалов, или класс $\varepsilon _{\cdot }$ ординалы, или класс кардиналов , все замкнуты и неограниченны; однако множество правильных кардиналов неограничено, но не замкнуто, а любое конечное множество ординалов замкнуто, но не неограничено.

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

Вместо того, чтобы формулировать эти определения для (собственных) классов ординалов, можно сформулировать их для наборов ординалов ниже заданного ординала. $\alpha$: Подмножество предельного порядкового номера. $\alpha$ называется неограниченным (или конфинальным) при $\alpha$ при условии, что любой порядковый номер меньше $\alpha$ меньше некоторого порядкового номера множества. В более общем смысле можно вызвать подмножество любого порядкового номера. $\alpha$ кофинал в $\alpha$ при условии, что каждый порядковый номер меньше $\alpha$ меньше или равно некоторому порядковому номеру в наборе. Говорят, что подмножество закрыто под $\alpha$ при условии, что он закрыт для топологии заказа в ⁠ $\alpha$⁠ , т. е. предел ординалов в множестве либо находится в множестве, либо равен $\alpha$ сам.

Арифметика порядковых чисел

Основная статья: Порядковая арифметика

Есть три обычных операции с порядковыми числами: сложение, умножение и возведение в степень. Каждый из них может быть определен двумя разными способами: либо путем создания явного упорядоченного набора, представляющего операцию, либо с помощью трансфинитной рекурсии. обеспечивает Нормальная форма Кантора стандартизированный способ записи порядковых номеров. Он однозначно представляет каждый ординал как конечную сумму порядковых степеней ω. Однако это не может лечь в основу универсального порядкового обозначения из-за таких самореферентных представлений, как ε ₀ = ω ^{е ₀} .

Порядковые числа — это подкласс класса сюрреалистических чисел , а так называемые «естественные» арифметические операции над сюрреалистическими числами — альтернативный способ арифметического объединения порядковых чисел. Они сохраняют коммутативность за счет непрерывности.

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

Ординалы и кардиналы

Начальный ординал кардинала

Каждый ординал связан с одним кардиналом , его мощностью. Если существует биекция между двумя ординалами (например, ω = 1 + ω и ω + 1 > ω ), то они связаны с одним и тем же кардиналом. Любой хорошо упорядоченный набор, типом порядка которого является порядковый номер, имеет ту же мощность, что и этот порядковый номер. Наименьший порядковый номер, связанный с данным кардиналом, называется начальным порядковым номером этого кардинала. Каждый конечный порядковый номер (натуральное число) является начальным, и никакой другой порядковый номер не связан с его кардиналом. Но большинство бесконечных ординалов не являются начальными, поскольку многие бесконечные ординалы связаны с одним и тем же кардиналом. Аксиома выбора эквивалентна утверждению, что каждое множество может быть хорошо упорядочено, т. е. что каждый кардинал имеет начальный порядковый номер. В теориях с аксиомой выбора кардинальное число любого набора имеет начальный порядковый номер, и можно использовать кардинальное присвоение Фон Неймана в качестве представления кардинала . (Однако в этом случае мы должны быть осторожны, чтобы различать кардинальную арифметику и порядковую арифметику.) В теориях множеств без аксиомы выбора кардинал может быть представлен набором множеств с этой мощностью, имеющим минимальный ранг (см. Трюк Скотта ).

Одна из проблем с трюком Скотта заключается в том, что он идентифицирует кардинальное число. $0$ с ⁠ $\{\emptyset \}$⁠ , который в некоторых формулировках является порядковым номером ⁠ $1$⁠ . Возможно, было бы яснее применить кардинальное присвоение фон Неймана к конечным случаям и использовать прием Скотта для множеств, которые бесконечны или не допускают хорошего упорядочения. Обратите внимание, что кардинальная и порядковая арифметика согласуются для конечных чисел.

α-й бесконечный начальный ординал записывается ⁠ $\omega _{\alpha }$⁠ , это всегда предельный порядковый номер. Его мощность записывается ⁠ $\aleph _{\alpha }$⁠ . Например, мощность ω ₀ = ω равна ⁠ $\aleph _{0}$⁠ , что также является мощностью ω ² или ε ₀ (все являются счетными ординалами). Таким образом, ω можно отождествить с ⁠ $\aleph _{0}$⁠ , за исключением того, что обозначение $\aleph _{0}$ используется при записи кардинальных чисел, а ω — при записи порядковых (это важно, поскольку, например, $\aleph _{0}^{2}$ = $\aleph _{0}$ тогда как $\omega ^{2}>\omega$). Также, $\omega _{1}$ - наименьший несчетный ординал (чтобы убедиться в его существовании, рассмотрим множество классов эквивалентности правильного порядка натуральных чисел: каждый такой правильный порядок определяет счетный ординал, а $\omega _{1}$ — тип ордера этого набора), $\omega _{2}$ - наименьший порядковый номер, мощность которого больше ⁠ $\aleph _{1}$⁠ и так далее, и $\omega _{\omega }$ это предел $\omega _{n}$ для натуральных чисел n (любой предел кардиналов является кардиналом, поэтому этот предел действительно является первым кардиналом после всех $\omega _{n}$).

Кофинальность

Конфинальность ​ ординала $\alpha$ это наименьший порядковый номер $\delta$ это тип порядка конфинального подмножества ⁠ $\alpha$⁠ . Обратите внимание, что ряд авторов определяют конфинальность или используют ее только для предельных ординалов. Конфинальность набора ординалов или любого другого хорошо упорядоченного набора — это конфинальность типа порядка этого набора.

Таким образом, для предельного ординала существует $\delta$-индексированная строго возрастающая последовательность с пределом ⁠ $\alpha$⁠ . Например, конфинальность ω ² является ω, поскольку последовательность ω · m (где m пробегает натуральные числа) стремится к ω ² ; но, в более общем смысле, любой счетный предельный ординал имеет конфинальность ω. Несчетный предельный ординал может иметь конфинальность ω, как и $\omega _{\omega }$ или несчетная конфинальность.

Конфинальность 0 равна 0. И конфинальность любого порядкового ординала-преемника равна 1. Конфинальность любого предельного ординала не менее ⁠ $\omega$⁠ .

Порядковый номер, равный своей конфинальности, называется регулярным и всегда является начальным порядковым номером. Любой предел правильных ординалов является пределом начальных ординалов и, следовательно, также является начальным, даже если он не является регулярным, чем обычно не является. Если Аксиома выбора, то $\omega _{\alpha +1}$ является регулярным для каждого α. В этом случае ординалы 0, 1, ⁠ $\omega$⁠ , ⁠ $\omega _{1}$⁠ и $\omega _{2}$ регулярны, тогда как 2, 3, ⁠ $\omega _{\omega }$⁠ и ω _ω·2 — начальные ординалы, которые не являются регулярными.

Конфинальность любого ординала α является регулярным ординалом, т. е. конфинальность конфинальности α такая же, как конфинальность α . Таким образом, операция конфинальности идемпотентна .

Некоторые «большие» счетные ординалы

Дополнительная информация: Большой счетный порядковый номер.

Как упоминалось выше (см. нормальную форму Кантора ), ординал ε ₀ является наименьшим, удовлетворяющим уравнению ⁠ $\omega ^{\alpha }=\alpha$⁠ , поэтому это предел последовательности 0, 1, ⁠ $\omega$⁠ , ⁠ $\omega ^{\omega }$⁠ , ⁠ $\omega ^{\omega ^{\omega }}$⁠ и т. д. Многие ординалы можно определить таким образом, как неподвижные точки определенных ординальных функций ( $\iota$-й порядковый номер такой, что $\omega ^{\alpha }=\alpha$ называется ⁠ $\varepsilon _{\iota }$⁠ , то можно было бы продолжать попытки найти $\iota$-й порядковый номер такой, что ⁠ $\varepsilon _{\alpha }=\alpha$⁠ , «и так далее», но вся тонкость заключается в «и так далее»). Можно было бы попытаться сделать это систематически, но независимо от того, какая система используется для определения и построения ординалов, всегда существует ординал, который лежит чуть выше всех ординалов, построенных этой системой. Возможно, наиболее важным порядковым номером, ограничивающим систему построения таким образом, является порядковый номер Чёрча-Клин , $\omega _{1}^{\mathrm {CK} }$ (несмотря на $\omega _{1}$ по названию этот порядковый номер счетен), то есть наименьший порядковый номер, который никак не может быть представлен вычислимой функцией (это, конечно, можно сделать строгим). Значительно большие ординалы можно определить ниже ⁠ $\omega _{1}^{\mathrm {CK} }$⁠ , однако, которые измеряют «теоретическую силу доказательства» определенных формальных систем (например, $\varepsilon _{0}$ измеряет силу арифметики Пеано ). Большие счетные ординалы, такие как счетные допустимые ординалы, также могут быть определены над порядковым номером Черча-Клин, которые представляют интерес в различных частях логики.

Топология и ординалы

Дополнительная информация: Топология заказа.

Любое порядковое число можно превратить в топологическое пространство , наделив его топологией порядка ; эта топология дискретна тогда и только тогда, когда ординал является счетным кардиналом, т. е. не превосходит ω. Подмножество ω + 1 открыто в порядковой топологии тогда и только тогда, когда оно либо коконечно , либо не содержит ω как элемент.

См. раздел «Топология и порядковые номера» статьи «Порядковая топология».

История

Трансфинитные порядковые числительные, впервые появившиеся в 1883 году, зародился в работе Кантора с производными множествами . Если P — набор действительных чисел, производное множество ′ является набором предельных точек P P . В 1872 году Кантор сгенерировал множества P ^{( н )} применив операцию производного множества n раз к P . В 1880 году он указал, что эти множества образуют последовательность P' ⊇ ··· ⊇ P ^{( н )} ⊇ П ^{( п + 1)} ⊇ ···, и он продолжил процесс вывода, определив P ^(∞) как пересечение этих множеств. Затем он повторил операцию над производным множеством и пересечения, чтобы расширить свою последовательность множеств до бесконечности: P ^(∞) ⊇ П ^{(∞ + 1)} ⊇ П ^{(∞ + 2)} ⊇ ··· ⊇ П ^(2∞) ⊇ ··· ⊇ П ^{(∞ 2 )} ⊇ ···. Верхние индексы, содержащие ∞, — это просто индексы, определенные в процессе вывода.

Кантор использовал эти множества в теоремах:

1. Если П ^{( а )} = ∅ для некоторого индекса α , то P ′ счетно;
2. Обратно, если P ′ счетно, то существует индекс α такой, что P ^{( а )} = ∅ .

Эти теоремы доказываются путем разбиения P ′ на попарно непересекающиеся множества: P ′ = ( P ′ \ P ⁽²⁾ ) ∪ ( П ⁽²⁾ \ П ⁽³⁾ ) ∪ ··· ∪ ( П ^(∞) \ П ^{(∞ + 1)} ) ∪ ··· ∪ П ^{( а )} . Для β < α : поскольку P ^{( б + 1)} содержит предельные точки P ^{( б )} , множества P ^{( б )} \ П ^{( б + 1)} не имеют предельных точек. Следовательно, они являются дискретными множествами , а значит, они счетны. Доказательство первой теоремы: если P ^{( а )} = ∅ для некоторого индекса α , то P ′ — счетное объединение счетных множеств. Следовательно, P ′ счетно.

Вторая теорема требует доказать существование α такого , что P ^{( а )} = ∅ . Чтобы доказать это, Кантор рассмотрел множество всех α, имеющих счетное число предшественников. Чтобы определить этот набор, он определил трансфинитные порядковые числа и преобразовал бесконечные индексы в порядковые числа, заменив ∞ на ω , первое трансфинитное порядковое число. Кантор назвал множество конечных ординалов первым классом чисел . Второй класс чисел представляет собой набор ординалов, предшественники которых образуют счетное бесконечное множество. Множество всех α, имеющих счетное число предшественников, то есть множество счетных ординалов, представляет собой объединение этих двух числовых классов. Кантор доказал, что мощность второго класса чисел есть первая неисчисляемая мощность.

Вторая теорема Кантора звучит следующим образом: если P ′ счетно, то существует счетный ординал α такой, что P ^{( а )} = ∅ . Его доказательство использует доказательство от противного . Пусть P ′ счетно и такого α не существует. Это предположение приводит к двум случаям.

• Случай 1: П ^{( б )} \ П ^{( б + 1)} непусто для всех счетных β . Так как таких попарно непересекающихся множеств несчетно, то их объединение несчетно. Это объединение является подмножеством P ′ , поэтому P' несчетно.
• Случай 2: П ^{( б )} \ П ^{( б + 1)} пусто для некоторого счетного β . Поскольку П ^{( б + 1)} ⊆ П ^{( б )} , это означает P ^{( б + 1)} = П ^{( б )} . Таким образом, П ^{( б )} это совершенное множество , поэтому оно несчетно. Поскольку П ^{( б )} ⊆ P ′ множество P ′ несчетно.

В обоих случаях P ′ несчетно, что противоречит P ′ счетности . Следовательно, существует счетный ординал α такой, что P ^{( а )} = ∅ . Работа Кантора с производными множествами и порядковыми числами привела к теореме Кантора-Бендиксона .

Используя преемников, пределы и мощность, Кантор создал неограниченную последовательность порядковых чисел и классов чисел. -й ( α + 1) класс чисел — это набор ординалов, предшественники которых образуют набор той же мощности, что и α -й класс чисел. Мощность ( α + 1) -го класса чисел — это мощность, следующая непосредственно за мощностью α -го класса чисел. Для предельного ординала α -й числовой класс α представляет собой объединение β -го числового класса для β < α . Его мощность является пределом мощностей этих числовых классов.

Если n конечно, n -й класс чисел имеет мощность ⁠ $\aleph _{n-1}$⁠ . Если α ≥ ω , α -й класс чисел имеет мощность ⁠ $\aleph _{\alpha }$⁠ . Следовательно, мощности числовых классов однозначно соответствуют числам алефа . Кроме того, α -й класс чисел состоит из порядковых номеров, отличных от порядковых номеров предыдущих классов чисел, тогда и только тогда, когда α является непредельным порядковым номером. Следовательно, классы непредельных чисел разбивают ординалы на попарно непересекающиеся множества.

См. также

• Подсчет
• Четные и нечетные ординалы
• Первый неисчисляемый порядковый номер
• Порядковое пространство
• Сюрреалистическое число — обобщение порядковых чисел, включающее отрицательные, действительные и бесконечно малые значения.

Ссылки

• Кантор, Георг (1883), «О бесконечных линейных точечных многообразиях. 5». , Mathematical Annals , 21 (4): 545–591, doi : 10.1007/bf01446819 , S2CID   121930608 . Опубликовано отдельно как: Основы общей теории разнообразия .
• Кантор, Георг (1897), «Вклад в основу теории трансфинитных множеств. II» , Mathematical Annals , vol. 49, № 2, стр. 207–246, doi : 10.1007/BF01444205 , S2CID   121665994 Английский перевод: Вклад в создание теории трансфинитных чисел II .
• Конвей, Джон Х .; Гай, Ричард (2012) [1996], «Порядковые числа Кантора» , Книга чисел , Springer, стр. 266–7, 274, ISBN  978-1-4612-4072-3
• Даубен, Джозеф (1979), Георг Кантор: его математика и философия бесконечного , издательство Гарвардского университета , ISBN  0-674-34871-0 .
• Эвальд, Уильям Б., изд. (1996), От Иммануила Канта до Дэвида Гильберта: Справочник по основам математики, Том 2 , Oxford University Press , ISBN  0-19-850536-1 .
• Феррейрос, Хосе (1995), « 'То, что бродило во мне годами': открытие Кантором трансфинитных чисел» (PDF) , Historia Mathematica , 22 : 33–42, doi : 10.1006/hmat.1995.1003 .
• Феррейрос, Хосе (2007), Лабиринт мысли: история теории множеств и ее роль в математической мысли (2-е исправленное издание), Birkhäuser , ISBN  978-3-7643-8349-7 .
• Халлетт, Майкл (1986), Канторианская теория множеств и ограничение размера , Oxford University Press, ISBN  0-19-853283-0 .
• Гамильтон, AG (1982), «6. Порядковые и кардинальные числа», Числа, множества и аксиомы: математический аппарат , Нью-Йорк: Cambridge University Press, ISBN  0-521-24509-5 .
• Канамори, Акихиро (2012), «Теория множеств от Кантора до Коэна» (PDF) , в Габбае, Дов М.; Канамори, Акихиро; Вудс, Джон Х. (ред.), Множества и расширения в двадцатом веке , Cambridge University Press, стр. 1–71, ISBN  978-0-444-51621-3 .
• Леви, А. (2002) [1979], Теория базовых множеств , Springer-Verlag , ISBN  0-486-42079-5 .
• Джех, Томас (2013), Теория множеств (2-е изд.), Springer, ISBN  978-3-662-22400-7 .
• Серпинский, В. (1965), Кардинальные и порядковые числа (2-е изд.), Варшава: Państwowe Wydawnictwo Naukowe Также определяет порядковые операции в терминах нормальной формы Кантора.
• Суппес, Патрик (1960), Аксиоматическая теория множеств , Д. Ван Ностранд, ISBN  0-486-61630-4 .
• Тейт, Уильям В. (1997), «Фреге против Кантора и Дедекинда: о концепции числа» (PDF) , в книге Уильяма В. Тейта (ред.), Ранняя аналитическая философия: Фреге, Рассел, Витгенштейн , Открытый суд, стр. 213–248, ISBN .  0-8126-9344-2 .
• фон Нейман, Джон (1923), «Zur Einführung der transfiniten Zahlen» , Журнал литературы и науки Венгерского университета францисканцев-Жозефин, секция математических наук , том. 1, стр. 199–208, заархивировано из оригинала 18 декабря 2014 г. , получено 15 сентября 2013 г.
• фон Нейман, Джон (январь 2002 г.) [1923], «О введении трансфинитных чисел» , в книге Жана ван Хейеноорта (ред.), От Фреге до Гёделя: Справочник по математической логике, 1879–1931 (3-е изд.) , Издательство Гарвардского университета, стр. 346–354, ISBN.  0-674-32449-8 - Английский перевод фон Неймана 1923 г.

Внешние ссылки

• «Порядковое число» , Математическая энциклопедия , EMS Press , 2001 [1994]
• Порядковые числа в ProvenMath
• Порядковый калькулятор. Бесплатное программное обеспечение под лицензией GPL для вычислений с порядковыми числами и порядковыми обозначениями.
• Глава 4 Дона Монка конспектов лекций по теории множеств представляет собой введение в ординалы.