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

редактировать

Тип порядка упорядоченного набора

Представление порядковых номеров до ω. Каждый поворот спирали представляет одну степень ω

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

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

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

(Трихотомия ) Для любых элементов x и y верно ровно одно из этих утверждений:
- x < y
- x>y
- x = y
(Транзитивность ) Для любых элементов x, y, z, если x>y и y>z, то x>z.
(Обоснованность ) Каждое непустое подмножество имеет наименьшее element, то есть у него есть такой элемент x, что нет другого элемента y в подмножестве, где x>y.

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

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

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

Содержание

1 Порядковые числа расширяют натуральные числа
2 Определения
- 2.1 Хорошо упорядоченные множества
- 2.2 Определение порядкового номера как класса эквивалентности
- 2.3 Определение фон Неймана ординалов
- 2.4 Другие определения
3 Трансфинитная последовательность
4 Трансфинитная индукция
- 4.1 Трансфинитная рекурсия
- 4.2 Последовательные и предельные ординалы
- 4.3 Классы индексации ординалов
- 4.4 Замкнутые неограниченные множества и классы
5 Арифметика порядковых чисел
6 Порядковые и кардинальные числа
- 6.1 Начальный порядковый номер кардинала
- 6.2 Кофинальность
7 Некоторые «большие» счетные порядковые числа
8 Топология и порядковые числа
9 Замкнутые вниз наборы порядковых номеров
10 История
11 См. Также
12 Примечания
13 Ссылки
14 Внешние ссылки

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

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

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

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

также существуют бесконечные ординалы: наименьший бесконечный порядковый номер $ω {\ displaystyle \ omega}$ $\ omega$ , который является порядковым типом натуральных чисел (конечных ординалов) и может даже быть отождествлен с набором натуральных чисел. Действительно, набор натуральных чисел хорошо упорядочен, как и любой набор ординалов, и, поскольку он закрыт сверху вниз, его можно идентифицировать с помощью связанного с ним порядкового номера (именно так $ω {\ displaystyle \ 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 - натуральные числа), сам должен иметь связанный с ним ординал: и это ω. Далее будет ω, затем ω и т. Д., И ω, затем ω, затем ω, и даже позже ε 0(эпсилон ноль ) (чтобы дать несколько примеров относительно малых - счетных - порядковые числительные). Это можно продолжать бесконечно (поскольку каждый раз, когда кто-то говорит «и так далее» при перечислении порядковых номеров, это определяет более крупный порядковый номер). Наименьший несчетный порядковый номер - это набор всех счетных порядковых номеров, выраженный как ω1 или $Ω {\ displaystyle \ Omega}$ $\ Omega$ .

Определения

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

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

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

Формально, если частичный порядок ≤ определен на множестве S, а частичный порядок ≤ 'определен на множестве S', то ставит ( S, ≤) и (S ', ≤') изоморфны порядку, если существует биекция f, которая сохраняет порядок. То есть f (a) ≤ 'f (b) тогда и только тогда, когда a ≤ b. При условии, что существует изоморфизм порядка между двумя хорошо упорядоченными множествами, изоморфизм порядка уникален: это делает вполне оправданным рассмотрение двух множеств как по существу идентичных и поиск «канонического» представителя типа (класса) изоморфизма. Это именно то, что предоставляют ординалы, а также обеспечивает каноническую маркировку элементов любого хорошо упорядоченного набора. Каждый хорошо упорядоченный набор (S, <) is order-isomorphic to the set of ordinals less than one specific ordinal number under their natural ordering. This canonical set is the order type of (S,<).

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

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

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

Определение порядковых чисел фон Неймана

Первые несколько порядковых чисел фон Неймана
0	= {}	= ∅
1	= {0}	= {∅}
2	= {0, 1}	= {∅, {∅}}
3	= {0, 1, 2}	= {∅, {∅}, {∅, {∅}}}
4	= {0, 1, 2, 3}	= {∅, {∅}, {∅, {∅}}, {∅, {∅}, {∅, {∅}}}}

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

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

Множество 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 - транзитивным множеством транзитивных наборы.

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

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

Если α - любой порядковый номер, а X - множество, α-индексированная последовательность элементов X является функцией от α до X. Это понятие, трансфинитное последовательность (если α бесконечно) или последовательность с порядковым индексом, является обобщением концепции последовательности. Обычная последовательность соответствует случаю α = ω, в то время как конечное α соответствует кортежу (математика), иначе строка (информатика).

Трансфинитная индукция

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

Любое свойство, которое переходит из набора ординалов, меньших заданного ординала α, к самому α, истинно для всех ординалов.

То есть, если P (α) истинно, когда P (β) истинно для всех β < α, then P(α) is true for all α. Or, more practically: in order to prove a property P for all ordinals α, one can assume that it is already known for all smaller β < α.

Трансфинитная рекурсия

Трансфинитная индукция может использоваться не только для доказательства вещей, но и для их определения. Такое определение обычно называется трансфинитной рекурсией - для доказательства того, что результат корректно определен, используется трансфинитная индукция. Пусть F обозначает (классовую) функцию F, определяемую на ординалах. Идея теперь состоит в том, что при определении F (α) для неуказанного ординала α можно предположить, что F (β) уже определено для всех β < α and thus give a formula for F(α) in terms of these F(β). It then follows by transfinite induction that there is one and only one function satisfying the recursion formula up to and including α. Вот пример определения с помощью трансфинитной рекурсии на ординалах (больше будет дано позже): определите функцию F, позволив F (α) быть наименьшим ординалом, не входящим в набор {F (β) | β < α}, that is, the set consisting of all F(β) for β < α. This definition assumes the F(β) known in the very process of defining F; this apparent vicious circle is exactly what definition by transfinite recursion permits. In fact, F(0) makes sense since there is no ordinal β < 0, and the set {F(β) | β < 0} is empty. So F(0) is equal to 0 (the smallest ordinal of all). Now that F(0) is known, the definition applied to F(1) makes sense (it is the smallest ordinal not in the singleton set {F(0)} = {0}), and so on (the and so on is exactly transfinite induction). It turns out that this example is not very exciting, since provably F(α) = α for all ordinals α, which can be shown, precisely, by transfinite induction.

Последующие и предельные порядковые номера

Любой ненулевой порядковый номер имеет минимальный элемент, ноль. Он может иметь или не иметь максимальный элемент. Например, 42 имеет максимум 41, а ω + 6 имеет максимум ω + 5. С другой стороны, ω не имеет максимума, поскольку нет наибольшего натурального числа. Если порядковый номер имеет максимальное значение α, то он является следующим порядковым номером после α и называется порядковым номером-преемником, а именно преемником α, записываемым α + 1. В определении ординалов фон Неймана преемником α является

α ∪ {α} {\ displaystyle \ alpha \ cup \ {\ alpha \}}

\ alpha \ cup \ {\ alpha \}

, поскольку его элементы являются элементами α и α

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

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

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

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

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

0, 1, 2,…, ω, ω + 1

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

Таким образом, каждый порядковый номер является либо нулем, либо преемником (четко определенного предшественника), либо пределом. Это различие важно, потому что многие определения с помощью трансфинитной рекурсии основываются на нем. Очень часто при определении функции F трансфинитной рекурсией по всем ординалам определяют F (0) и F (α + 1), предполагая, что F (α) определено, а затем для предельных ординалов δ определяют F (δ) как предел F (β) для всех β <δ (either in the sense of ordinal limits, as previously explained, or for some other notion of limit if F does not take ordinal values). Thus, the interesting step in the definition is the successor step, not the limit ordinals. Such functions (especially for F nondecreasing and taking ordinal values) are called continuous. Ordinal addition, multiplication and exponentiation are continuous as functions of their second argument (but can be defined non-recursively).

Классы индексации ординалов

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

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

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

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

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

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

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

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

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

Обозначаемые как числа, порядковые числа также подлежат быстрым арифметическим операциям.

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

Начальный порядковый номер кардинала

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

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

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

Cofinality

cofinality порядкового номера $α {\ displaystyle \ alpha}$ $\ alpha$ является наименьшим порядковым номером $δ {\ displaystyle \ delta}$ $\ delta$ , который является типом заказа cofinal подмножества $α {\ displaystyle \ alpha}$ $\ alpha$ . Обратите внимание, что ряд авторов определяют cofinality или используют его только для порядковых номеров пределов. Конфинальность набора ординалов или любого другого хорошо упорядоченного набора - это конфинальность типа заказа этого набора.

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

Конфинальность 0 равна 0. А конфинальность любого последующего порядкового номера равна 1. Конфинальность любого предельного порядкового номера не менее $ω {\ displaystyle \ omega}$ $\ omega$ .

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

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

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

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

Топология и порядковые числа

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

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

Наборы порядковых номеров, закрытые вниз

Набор является закрытым вниз, если в наборе также есть что-либо меньшее, чем элемент набора. Если набор порядковых номеров закрыт вниз, то этот набор является порядковым - наименьшим порядковым номером, отсутствующим в наборе.

Примеры:

Набор порядковых номеров меньше 3 равен 3 = {0, 1, 2}, наименьший порядковый номер не меньше 3.
Набор конечных порядковых номеров бесконечен, наименьший бесконечный порядковый номер: ω.
Набор исчисляемых порядковых чисел неисчислим, наименьший несчетный порядковый номер: ω 1.

История

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

Кантор использовал эти множества в теоремах: (1) Если P = ∅ для некоторого индекса α, то P 'счетно; (2) Наоборот, если P 'счетно, то существует индекс α такой, что P = ∅. Эти теоремы доказываются путем разбиения P 'на попарно непересекающиеся множества: P' = (P '∖ P) ∪ (P ∖ P) ∪ ··· ∪ (P ∖ P) ∪ ··· ∪ P.Для β < α: since P contains the limit points of P, the sets P ∖ P have no limit points. Hence, they are дискретных множеств, поэтому они счетны. Доказательство первой теоремы: если P = ∅ для некоторого индекса α, то P '- счетное объединение счетных множеств. Следовательно, P 'счетно.

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

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

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

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

. Используя преемников, ограничения и мощность, Кантор создал неограниченную последовательность порядковых чисел и классов чисел. (Α + 1) -й числовой класс - это набор ординалов, предшественники которых образуют набор той же мощности, что и α-й числовой класс. Мощность (α + 1) -го числового класса - это мощность, следующая сразу за мощностью α-го числового класса. Для предельного порядкового числа α α-й числовой класс является объединением β-ых числовых классов для β < α. Its cardinality is the limit of the cardinalities of these number classes.

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

См. Также

Примечания

Ссылки

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

Найдите ординал в Wiktionary, бесплатном словаре.

, Энциклопедия математики, EMS Press, 2001 [1994]
Ordinals at ProvenMath
Ordinal Calculator GPL бесплатное программное обеспечение для вычислений с порядковыми и порядковыми обозначениями
Глава 4 лекции Дона Монка примечания по теории множеств - введение в порядковые числа.