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

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

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

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

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

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

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

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

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

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

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

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

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

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

Существуют также бесконечные ординалы: наименьший бесконечный ординал ${\displaystyle \omega }$,^[3] который является порядковым типом натуральных чисел (конечных ординалов) и может быть даже отождествлен с набор натуральных чисел. В самом деле, набор натуральных чисел хорошо упорядочен, как и любой набор ординалов, и, поскольку он замкнут вниз, его можно отождествить с соответствующим ему порядковым номером (именно так ${\displaystyle \omega }$ определено).

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

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

Определения

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

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

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

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

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

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

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

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

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

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

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

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

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

Таким образом, по этому определению натуральные числа являются ординалами. Например, 2 является элементом 4 = {0, 1, 2, 3}, а 2 равно {0, 1}, поэтому это подмножество {0, 1, 2, 3}.

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

Более того, элементы каждого ординала сами являются ординалами. Учитывая два ординала S и Т, S является элементом Т если и только если S это правильное подмножество из Т. Более того, либо S является элементом Т, или Т является элементом S, или они равны. Итак, каждый набор ординалов полностью заказанный. Кроме того, каждый набор ординалов упорядочен. Это обобщает тот факт, что каждый набор натуральных чисел упорядочен.

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

Класс всех ординалов не является набором. Если бы это был набор, можно было бы показать, что это порядковый номер и, следовательно, член самого себя, что противоречило бы его строгий заказ по членству. Это Парадокс Бурали-Форти. Класс всех ординалов по-разному называется «Ord», «ON» или «∞».

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

Другие определения

Есть и другие современные формулировки определения порядкового номера. Например, если предположить аксиома регулярности, для множества Икс:

• Икс это порядковый номер,
• Икс это переходный набор, а набор членства трихотомический на Икс,
• Икс транзитивное множество полностью заказанный включением множества,
• Икс - транзитивное множество транзитивных множеств.

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

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

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

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

Основная статья: Трансфинитная индукция

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

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

То есть, если п(α) истинно, если п(β) верно для всех β <α, тогда п(α) верно для все α. Или, более практично: чтобы доказать собственность п для всех ординалов α можно считать, что он уже известен для всех меньших β <α.

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

Трансфинитная индукция может использоваться не только для доказательства вещей, но и для их определения. Такое определение обычно называют трансфинитная рекурсия - для доказательства корректности результата используется трансфинитная индукция. Позволять 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. В определении ординалов фон Неймана преемником α является ${\displaystyle \alpha \cup \{\alpha \}}$ поскольку его элементами являются элементы α и самого α.^[7]

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

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

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

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

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

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

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

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

Индексирование классов порядковых номеров

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

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

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

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

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

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

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

Арифметика ординалов

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

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

Интерпретируется как ловцы, ординалы также подвергаются лёгким арифметическим операциям.

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

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

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

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

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

Cofinality

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

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

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

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

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

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

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

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

Топология и порядковые номера

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

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

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

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

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

Примеры:

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

История

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

Кантор использовал эти множества в теоремах: (1) Если п^(α) = ∅ для некоторого индекса α, то П' счетно; (2) Наоборот, если П' счетно, то существует такой индекс α, что п^(α) = ∅. Эти теоремы доказываются разбиением П' в попарно непересекающиеся наборы: П' = (П'∖ п⁽²⁾) ∪ (п⁽²⁾ ∖ п⁽³⁾) ∪ ··· ∪ (п^(∞) ∖ п^(∞ + 1)) ∪ ··· ∪ п^(α). Для β <α: поскольку п^{(β + 1)} содержит предельные точки п^(β), наборы п^(β) ∖ п^{(β + 1)} не имеют предельных точек. Следовательно, они дискретные множества, поэтому они счетны. Доказательство первой теоремы: если п^(α) = ∅ для некоторого индекса α, то П' - счетное объединение счетных множеств. Следовательно, П' счетно.^[12]

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

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

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

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

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

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

Смотрите также

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

Заметки

1. Подробное введение дано (Леви 1979 ) и (Jech 2003 ).
2. Халлетт, Майкл (1979), "К теории программ математических исследований. I", Британский журнал философии науки, 30 (1): 1–25, Дои:10.1093 / bjps / 30.1.1, Г-Н  0532548. См. Сноску на стр. 12.
3. «Сборник математических символов». Математическое хранилище. 2020-03-01. Получено 2020-08-12.
4. «Исчерпывающий список символов теории множеств». Математическое хранилище. 2020-04-11. Получено 2020-08-12.
5. "Порядковые числа | Brilliant Math & Science Wiki". brilliant.org. Получено 2020-08-12.
6. Вайсштейн, Эрик В. "Порядковый номер". mathworld.wolfram.com. Получено 2020-08-12.
7. фон Нейман 1923
8. (Леви 1979, п. 52) связывает идею с неопубликованной работой Цермело 1916 года и несколькими работами фон Неймана 1920-х годов.
9. Cantor 1883. Английский перевод: Эвальд 1996, стр. 881–920
10. Феррейрос 1995, стр. 34–35; Феррейрос 2007, стр. 159, 204–5
11. Феррейрос 2007, п. 269
12. Феррейрос 1995, стр. 35–36; Феррейрос 2007, п. 207 Ошибка harvnb: цель отсутствует: CITEREFFerreirós_2007 (Помогите)
13. Феррейрос 1995, стр. 36–37; Феррейрос 2007, п. 271
14. Dauben 1979, п. 111
15. Феррейрос 2007, стр. 207–8
16. Dauben 1979, стр. 97–98
17. Халлетт 1986, стр. 61–62
18. Tait 1997, п. 5 сноска
19. Первый числовой класс имеет мощность ${\displaystyle \aleph _{0}}$. Математическая индукция доказывает, что п-й числовой класс имеет мощность ${\displaystyle \aleph _{n-1}}$. Поскольку ω-й числовой класс представляет собой объединение п-го числового класса, его мощность ${\displaystyle \aleph _{\omega }}$, предел ${\displaystyle \aleph _{n-1}}$. Трансфинитная индукция доказывает, что при α ≥ ω мощность α-го числового класса ${\displaystyle \aleph _{\alpha }}$.

использованная литература

• Кантор, Георг (1883), "Ueber unendliche, lineare Punktmannichfaltigkeiten. 5.", Mathematische Annalen, 21 (4): 545–591, Дои:10.1007 / bf01446819, S2CID  121930608. Опубликовано отдельно как: Grundlagen einer allgemeinen Mannigfaltigkeitslehre.
• Кантор, Георг (1897), "Beitrage zur Begrundung der transfiniten Mengenlehre. II", Mathematische Annalen, 49 (2): 207–246, Дои: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, Дои:10.1006 / hmat.1995.1003.
• Феррейрос, Хосе (2007), Лабиринт мысли: история теории множеств и ее роль в математической мысли (2-е изд. Перераб.), Биркхойзер, ISBN  978-3-7643-8349-7.
• Халлетт, Майкл (1986), Канторовская теория множеств и ограничение размера, Издательство Оксфордского университета, ISBN  0-19-853283-0.
• Гамильтон, А. Г. (1982), "6. Порядковые и количественные числа", Числа, множества и аксиомы: аппарат математики, Нью-Йорк: Издательство Кембриджского университета, 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.
• Jech, Томас (2013), Теория множеств (2-е изд.), Springer, ISBN  978-3-662-22400-7.
• Серпинский, В. (1965), Кардинальные и порядковые числа (2-е изд.), Варшава: Państwowe Wydawnictwo Naukowe Также определяет порядковые операции в терминах нормальной формы Кантора.
• Суппес, Патрик (1960), Аксиоматическая теория множеств, Д. Ван Ностранд, ISBN  0-486-61630-4.
• Тейт, Уильям У. (1997), «Фреге против Кантора и Дедекинда: о понятии числа» (PDF), в Уильяме В. Тейте (ред.), Ранняя аналитическая философия: Фреге, Рассел, Витгенштейн, Open Court, стр. 213–248, ISBN  0-8126-9344-2.
• фон Нейман, Джон (1923), "Zur Einführung der transfiniten Zahlen", Acta litterarum ac scientiarum Ragiae Universitatis Hungaricae Francisco-Josephinae, Sectio scientiarum mathematicarum, 1: 199–208, архивировано с оригинал на 2014-12-18, получено 2013-09-15
• фон Нейман, Джон (Январь 2002 г.) [1923 г.], «О введении трансфинитных чисел», в Жан ван Хейенорт (ред.), От Фреге до Гёделя: Справочник по математической логике, 1879–1931 гг. (3-е изд.), Harvard University Press, стр. 346–354, ISBN  0-674-32449-8 - английский перевод фон Нейман 1923.

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

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