Большое счетное порядковое число

Ординалы в математике и теории множеств

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

Поскольку существует только счетное число обозначений, все ординалы с обозначениями исчерпываются значительно ниже первого несчетного ординала ω ₁ ; их супремум называется ω ₁ Чёрча–Клини или ω^СК
₁(не путать с первым несчетным порядковым числительным, ω ₁ ), описанным ниже. Порядковые числительные ниже ω^СК
₁являются рекурсивными ординалами (см. ниже). Счетные ординалы большего размера все еще могут быть определены, но не имеют обозначений.

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

Общие сведения о рекурсивных ординалах

Порядковые обозначения

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

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

Любой ординал, меньший рекурсивного ординала, сам по себе рекурсивен, поэтому множество всех рекурсивных ординалов образует определенный (счетный) ординал — ординал Чёрча–Клини (см. ниже).

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

Связь с системами арифметики

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

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

Например, обычные аксиомы Пеано первого порядка не доказывают трансфинитную индукцию для (или за пределами) ε : в то время как ординал ε ₀ можно легко арифметически описать (он счетен), аксиомы Пеано недостаточно сильны, чтобы показать, что он действительно является ординалом; на самом деле, трансфинитная индукция по ε ₀ доказывает непротиворечивость аксиом Пеано (теорема Генцена ), поэтому по второй теореме Гёделя о неполноте аксиомы Пеано не могут формализовать это рассуждение. (Это лежит в основе теоремы Кирби–Париса о последовательностях Гудстейна .) Поскольку арифметика Пеано может доказать, что любой ординал, меньший ε _{0 ,} является вполне упорядоченным, мы говорим, что ε ₀ измеряет теоретическую силу доказательств аксиом Пеано.

Но мы можем сделать это для систем, далеко выходящих за рамки аксиом Пеано. Например, теоретико-доказательная сила теории множеств Крипке–Платека — это ординал Бахмана–Говарда , и, по сути, простого добавления к аксиомам Пеано аксиом, которые утверждают хорошее упорядочение всех ординалов ниже ординала Бахмана–Говарда, достаточно, чтобы получить все арифметические следствия теории множеств Крипке–Платека.

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

Предикативные определения и иерархия Веблена

Мы уже упоминали (см. нормальную форму Кантора ) ординал ε 0 , который является наименьшим, удовлетворяющим уравнению , поэтому он является пределом последовательности 0, 1, , , , ... Следующий ординал, удовлетворяющий этому уравнению, называется ε ₁ : он является пределом последовательности ${\displaystyle \omega ^{\alpha }=\alpha }$ ${\displaystyle \omega }$ ${\displaystyle \omega ^{\omega }}$ ${\displaystyle \omega ^{\omega ^{\omega }}}$

${\displaystyle \varepsilon _{0}+1,\qquad \omega ^{\varepsilon _{0}+1}=\varepsilon _{0}\cdot \omega ,\qquad \omega ^{\omega ^{\varepsilon _{0}+1}}=(\varepsilon _{0})^{\omega },\qquad {\text{etc.}}}$

В более общем случае -й ординал такой, что называется . Мы могли бы определить как наименьший ординал такой, что , но поскольку греческий алфавит не имеет трансфинитного множества букв, лучше использовать более надежную нотацию: определить ординалы с помощью трансфинитной индукции следующим образом: пусть и пусть будут -й неподвижной точкой (т. е. -й ординал такой, что ; так, например, ), и когда будет предельным ординалом, определить как -ю общую неподвижную точку для всех . Это семейство функций известно как иерархия Веблена (существуют несущественные вариации в определении, такие как разрешение для предельного ординала быть пределом для : это по сути просто сдвигает индексы на 1, что безвредно). называется функцией Веблена (к основанию ). ${\displaystyle \iota }$ ${\displaystyle \omega ^{\alpha }=\alpha }$ ${\displaystyle \varepsilon _{\iota }}$ ${\displaystyle \zeta _{0}}$ ${\displaystyle \varepsilon _{\alpha }=\alpha }$ ${\displaystyle \varphi _{\gamma }(\beta )}$ ${\displaystyle \varphi _{0}(\beta )=\omega ^{\beta }}$ ${\displaystyle \varphi _{\gamma +1}(\beta )}$ ${\displaystyle \beta }$ ${\displaystyle \varphi _{\gamma }}$ ${\displaystyle \beta }$ ${\displaystyle \varphi _{\gamma }(\alpha )=\alpha }$ ${\displaystyle \varphi _{1}(\beta )=\varepsilon _{\beta }}$ ${\displaystyle \delta }$ ${\displaystyle \varphi _{\delta }(\alpha )}$ ${\displaystyle \alpha }$ ${\displaystyle \varphi _{\gamma }}$ ${\displaystyle \gamma <\delta }$ ${\displaystyle \delta }$ ${\displaystyle \varphi _{\delta }(\alpha )}$ ${\displaystyle \varphi _{\gamma }(\alpha )}$ ${\displaystyle \gamma <\delta }$ ${\displaystyle \varphi _{\gamma }}$ ${\displaystyle \gamma ^{th}}$ ${\displaystyle \omega }$

Порядок: тогда и только тогда, когда либо ( и ), либо ( и ), либо ( и ). ${\displaystyle \varphi _{\alpha }(\beta )<\varphi _{\gamma }(\delta )}$ ${\displaystyle \alpha =\gamma }$ ${\displaystyle \beta <\delta }$ ${\displaystyle \alpha <\gamma }$ ${\displaystyle \beta <\varphi _{\gamma }(\delta )}$ ${\displaystyle \alpha >\gamma }$ ${\displaystyle \varphi _{\alpha }(\beta )<\delta }$

Порядковый номер Фефермана-Шютте и за его пределами

Наименьший ординал, такой как , известен как ординал Фефермана–Шютте и обычно записывается . Его можно описать как множество всех ординалов, которые могут быть записаны как конечные выражения, начиная с нуля, используя только иерархию Веблена и сложение. Ординал Фефермана–Шютте важен, потому что в смысле, который сложно точно определить, это наименьший (бесконечный) ординал, который не может быть (« предикативно ») описан с помощью меньших ординалов. Он измеряет силу таких систем, как « арифметическая трансфинитная рекурсия ». ${\displaystyle \varphi _{\alpha }(0)=\alpha }$ ${\displaystyle \Gamma _{0}}$

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

Конечно, возможно описать ординалы за пределами ординала Фефермана–Шютте. Можно продолжать искать неподвижные точки все более и более сложным образом: перечислить неподвижные точки , затем перечислить неподвижные точки , и так далее, а затем искать первый ординал α такой, что α получается за α шагов этого процесса, и продолжать диагонализовать таким ad hoc образом. Это приводит к определению « малых » и « больших » ординалов Веблена. ${\displaystyle \alpha \mapsto \Gamma _{\alpha }}$

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

Чтобы выйти далеко за рамки ординала Фефермана–Шютте, нужно ввести новые методы. К сожалению, пока нет стандартного способа сделать это: каждый автор в этой области, кажется, изобрел свою собственную систему обозначений, и ее довольно сложно переводить между различными системами. Первая такая система была введена Бахманном в 1950 году (в порядке ad hoc ), а различные ее расширения и вариации были описаны Бухгольцем, Такеути (порядковые диаграммы), Феферманом (θ-системы), Ацелем , Бриджем, Шютте и Полерсом. Однако большинство систем используют одну и ту же базовую идею — построение новых счетных порядковых чисел путем использования существования определенных несчетных порядковых чисел. Вот пример такого определения, описанного гораздо подробнее в статье о функции свертывания порядковых чисел :

• ψ( α ) определяется как наименьший ординал, который нельзя построить, начиная с 0, 1, ω и Ω и многократно применяя сложение, умножение и возведение в степень, а также ψ к ранее построенным ординалам (за исключением того, что ψ можно применять только к аргументам, меньшим α , чтобы гарантировать его корректность).

Здесь Ω = ω ₁ — первый несчетный ординал. Он вставлен, потому что в противном случае функция ψ «застрянет» на наименьшем ординале σ таком, что ε _σ = σ : в частности, ψ( α )= σ для любого ординала α, удовлетворяющего σ ≤ α ≤Ω. Однако тот факт, что мы включили Ω, позволяет нам обойти эту точку: ψ(Ω+1) больше σ . Ключевое свойство Ω, которое мы использовали, заключается в том, что оно больше любого ординала, произведенного ψ.

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

Ординал Бахмана –Говарда (иногда называемый просто ординалом Говарда , ψ ₀ (ε _Ω+1 ) с обозначениями выше) является важным, поскольку он описывает силу доказательства теории множеств Крипке–Платека . Действительно, главная важность этих больших ординалов и причина их описания заключается в их связи с определенными формальными системами, как объяснено выше. Однако такие мощные формальные системы, как полная арифметика второго порядка , не говоря уже о теории множеств Цермело–Френкеля , кажутся на данный момент недостижимыми.

За пределами даже ординала Бахмана-Говарда

Помимо этого, существует несколько рекурсивных ординалов, которые не так хорошо известны, как предыдущие. Первый из них — ординал Бухгольца , определяемый как , сокращенно просто , используя предыдущую нотацию. Это ординал доказательства теории , ^[1] теории арифметики первого порядка, допускающей квантификацию по натуральным числам, а также по множествам натуральных чисел, и , «формальной теории конечно итерированных индуктивных определений». ^[2] ${\displaystyle \psi _{0}(\Omega _{\omega })}$ ${\displaystyle \psi (\Omega _{\omega })}$ ${\displaystyle \Pi _{1}^{1}-CA_{0}}$ ${\displaystyle ID_{<\omega }}$

Поскольку гидры из игры Бухгольца «Гидра» изоморфны порядковой нотации Бухгольца, порядковые числа до этого момента можно выразить с помощью гидр из игры. ^{[3] стр.136} Например, соответствует . ${\displaystyle +(0(\omega ))}$ ${\displaystyle \psi (\Omega _{\omega })}$

Далее следует ординал Такеути-Фефермана-Бухгольца , ординал теории доказательств ; ^[4] и еще одна подсистема арифметики второго порядка: - понимание + трансфинитная индукция, и , "формальная теория -кратно итерированных индуктивных определений". ^[5] В этой нотации он определяется как . Это супремум диапазона пси-функций Бухгольца. ^[6] Впервые он был назван Дэвидом Мадором. ^{[ требуется ссылка ]} ${\displaystyle \Pi _{1}^{1}-CA+BI}$ ${\displaystyle \Pi _{1}^{1}}$ ${\displaystyle ID_{\omega }}$ ${\displaystyle \omega }$ ${\displaystyle \psi _{0}(\varepsilon _{\Omega _{\omega }+1})}$

Следующий порядковый номер упоминается в фрагменте кода, описывающем большие счетные порядковые номера и числа в Agda, и определяется «AndrasKovacs» как . ${\displaystyle \psi _{0}(\Omega _{\omega +1}\cdot \varepsilon _{0})}$

Следующий ординал упоминается в том же фрагменте кода, что и ранее, и определяется как . Это ординал теории доказательств . ${\displaystyle \psi _{0}(\Omega _{\omega ^{\omega }})}$ ${\displaystyle ID_{<\omega ^{\omega }}}$

Следующий ординал, снова упомянутый в этом же фрагменте кода, определяется как , является теоретическим ординалом доказательства . В общем случае теоретический ординал доказательства равен — обратите внимание, что в этом конкретном случае представляет , первый ненулевой ординал. ${\displaystyle \psi _{0}(\Omega _{\varepsilon _{0}})}$ ${\displaystyle ID_{<\varepsilon _{0}}}$ ${\displaystyle ID_{<\nu }}$ ${\displaystyle \psi _{0}(\Omega _{\nu })}$ ${\displaystyle \Omega _{0}}$ ${\displaystyle 1}$

Далее следует неназванный ординал, который Дэвид Мадор называет «счетным» коллапсом , ^[5] где — первый недостижимый (= -неописуемый) кардинал. Это доказательно-теоретический ординал теории множеств Крипке-Платека , дополненный рекурсивной недостижимостью класса ординалов (KPi), или, с арифметической стороны, -понимания + трансфинитной индукции. Его значение равно использованию неизвестной функции. ${\displaystyle \varepsilon _{I+1}}$ ${\displaystyle I}$ ${\displaystyle \Pi _{0}^{1}}$ ${\displaystyle \Delta _{2}^{1}}$ ${\displaystyle \psi (\varepsilon _{I+1})}$

Далее следует еще один неназванный ординал, который Дэвид Мадор называет «счетным» коллапсом , ^[5] где — первый кардинал Мало . Это доказательно-теоретический ординал KPM, расширения теории множеств Крипке-Платека, основанной на кардинале Мало. ^[7] Его значение равно использованию одной из различных пси-функций Бухгольца. ^[8] ${\displaystyle \varepsilon _{M+1}}$ ${\displaystyle M}$ ${\displaystyle \psi (\varepsilon _{M+1})}$

Далее следует еще один неназванный ординал, названный Дэвидом Мадором "счетным" коллапсом , ^[5] где - первый слабо компактный (= -неописуемый) кардинал. Это доказательно-теоретический ординал теории множеств Крипке-Платека + Π3 - Ref. Его значение равно использованию функции Psi Ратьена. ^[9] ${\displaystyle \varepsilon _{K+1}}$ ${\displaystyle K}$ ${\displaystyle \Pi _{1}^{1}}$ ${\displaystyle \Psi (\varepsilon _{K+1})}$

Далее следует еще один неназванный ординал, который Дэвид Мадор называет «счетным» коллапсом , ^[5] где — первый -неописуемый кардинал. Это доказательно-теоретический ординал теории множеств Крипке-Платека + Πω-Ref. Его значение равно использованию функции Psi Стегерта, где = ( ; ; , , 0). ^[10] ${\displaystyle \varepsilon _{\Xi +1}}$ ${\displaystyle \Xi }$ ${\displaystyle \Pi _{0}^{2}}$ ${\displaystyle \Psi _{X}^{\varepsilon _{\Xi +1}}}$ ${\displaystyle X}$ ${\displaystyle \omega ^{+}}$ ${\displaystyle P_{0}}$ ${\displaystyle \epsilon }$ ${\displaystyle \epsilon }$

Далее следует последний неназванный ординал, который Дэвид Мадор называет ординалом доказательства теории стабильности. ^[5] Это ординал доказательства теории стабильности, расширение теории множеств Крипке-Платека. Его значение равно использованию функции Пси Стегерта, где = ( ; ; , , 0). ^[10] ${\displaystyle \Psi _{X}^{\varepsilon _{\Upsilon +1}}}$ ${\displaystyle X}$ ${\displaystyle \omega ^{+}}$ ${\displaystyle P_{0}}$ ${\displaystyle \epsilon }$ ${\displaystyle \epsilon }$

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

• Теоретико-доказательный ординал арифметики второго порядка .
• Возможный предел порядковой системы обозначений Тарановского. (Предположительно, предполагая обоснованность системы обозначений)
• Теоретико-доказательный ординал ZFC .

«Нерекурсивные» рекурсивные ординалы

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

За пределами рекурсивных ординалов

Ординал Чёрча-Клина

Супремум множества рекурсивных ординалов — это наименьший ординал, который не может быть описан рекурсивным способом. (Это не тип порядка любого рекурсивного полного упорядочения целых чисел.) Этот ординал — счетный ординал, называемый ординалом Чёрча–Клини , . Таким образом, — наименьший нерекурсивный ординал, и с этого момента нет никакой надежды точно «описать» какие-либо ординалы — мы можем только определить их. Но он все еще намного меньше первого несчетного ординала, . Однако, как предполагает его символ, он ведет себя во многих отношениях скорее как . Например, можно определить функции свертывания ординалов, используя вместо . ${\displaystyle \omega _{1}^{\mathrm {CK} }}$ ${\displaystyle \omega _{1}^{\mathrm {CK} }}$ ${\displaystyle \omega _{1}}$ ${\displaystyle \omega _{1}}$ ${\displaystyle \omega _{1}^{\mathrm {CK} }}$ ${\displaystyle \omega _{1}}$

Допустимые порядковые номера

Ординал Чёрча–Клини снова связан с теорией множеств Крипке–Платека , но теперь другим образом: в то время как ординал Бахмана–Говарда (описанный выше) был наименьшим ординалом, для которого КП не доказывает трансфинитную индукцию, ординал Чёрча–Клини является наименьшим α таким, что построение вселенной Гёделя , L , до стадии α , даёт модель КП. Такие ординалы называются допустимыми , поэтому является наименьшим допустимым ординалом (за пределами ω в случае, если аксиома бесконечности не включена в КП). ${\displaystyle L_{\alpha }}$ ${\displaystyle \omega _{1}^{\mathrm {CK} }}$

По теореме Фридмана , Йенсена и Сакса , счетные допустимые ординалы — это в точности те, которые построены способом, похожим на ординал Чёрча-Клини, но для машин Тьюринга с оракулами . ^{[11] [12]} Иногда пишут для -го ординала, который является либо допустимым, либо пределом меньших допустимых. ^{[ требуется ссылка ]} ${\displaystyle \omega _{\alpha }^{\mathrm {CK} }}$ ${\displaystyle \alpha }$

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

${\displaystyle \omega _{\omega }^{\mathrm {CK} }}$является наименьшим пределом допустимых ординалов (упомянутых позже), однако сам ординал не является допустимым. Он также является наименьшим таким, что является моделью -понимания. ^{[5] [13]} ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\cap P(\omega )}$ ${\displaystyle \Pi _{1}^{1}}$

Ординал, который является как допустимым, так и пределом допустимых, или, что эквивалентно, таким, что является -ым допустимым ординалом, называется рекурсивно недостижимым , а наименее рекурсивно недостижимый может быть обозначен . ^[14] Ординал, который является как рекурсивно недостижимым, так и пределом рекурсивно недостижимых, называется рекурсивно гипернедостижимым . ^[5] Существует теория больших ординалов таким образом, которая весьма параллельна теории (малых) больших кардиналов . Например, мы можем определить рекурсивно ординалы Мало : это такие , что каждое -рекурсивно замкнутое неограниченное подмножество содержит допустимый ординал (рекурсивный аналог определения кардинала Мало ). 1-секция функционала Харрингтона равна , где - наименее рекурсивно ординал Мало. ^{[15] стр.171} ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \omega _{1}^{E_{1}}}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle {}^{2}S^{\#}}$ ${\displaystyle L_{\rho }\cap {\mathcal {P}}(\omega )}$ ${\displaystyle \rho }$

Но заметьте, что мы все еще говорим здесь о возможно счетных ординалах. (В то время как существование недоступных или Мало-кардиналов не может быть доказано в теории множеств Цермело–Френкеля , существование рекурсивно недоступных или Мало-ординалов является теоремой ZFC: на самом деле, любой регулярный кардинал является рекурсивно Мало и более, но даже если мы ограничимся счетными ординалами, ^{[ необходимо разъяснение ]} ZFC доказывает существование рекурсивно Мало-ординалов. Однако они находятся за пределами досягаемости теории множеств Крипке–Платека.)

Отражение

Для множества формул предельный ординал называется -отражающим , если ранг удовлетворяет определенному свойству отражения для каждой -формулы . ^[16] Эти ординалы появляются в ординальном анализе таких теорий, как KP+Π ₃ -ref , теории, дополняющей теорию множеств Крипке-Платека схемой -отражения. Их также можно считать "рекурсивными аналогами" некоторых несчетных кардиналов, таких как слабо компактные кардиналы и неописуемые кардиналы . ^[17] Например, ординал, который -отражающий, называется рекурсивно слабо компактным . ^[18] Для конечного наименьший -отражающий ординал также является супремумом замыкающих ординалов монотонных индуктивных определений, графики которых равны Π m+1 . ^[18] ${\displaystyle \Gamma }$ ${\displaystyle \alpha }$ ${\displaystyle \Gamma }$ ${\displaystyle L_{\alpha }}$ ${\displaystyle \Gamma }$ ${\displaystyle \phi }$ ${\displaystyle \Pi _{3}}$ ${\displaystyle \Pi _{3}}$ ${\displaystyle n}$ ${\displaystyle \Pi _{n}}$

В частности, -рефлективные ординалы также имеют характеристику, использующую функционалы более высокого типа на ординальных функциях, что дает им название 2-допустимые ординалы . ^[18] Неопубликованная статья Соломона Фефермана предоставляет для каждого конечного , аналогичное свойство, соответствующее -рефлексии. ^[19] ${\displaystyle \Pi _{3}}$ ${\displaystyle n}$ ${\displaystyle \Pi _{n}}$

Непроецируемость

Допустимый ординал называется непроектируемым , если не существует тотальной -рекурсивной инъективной функции, отображающейся в меньший ординал. (Это тривиально верно для регулярных кардиналов; однако нас в основном интересуют счетные ординалы.) Быть непроектируемым — гораздо более сильное условие, чем быть допустимым, рекурсивно недоступным или даже рекурсивно Мало. ^[13] По методу Йенсена проекции ^[20] это утверждение эквивалентно утверждению, что универсум Гёделя , L , до стадии α, дает модель KP + -разделения. Однако само по себе -разделение (не в присутствии ) не является достаточно сильной схемой аксиом, чтобы подразумевать непроектируемость, на самом деле существуют транзитивные модели + -разделения любой счетной допустимой высоты . ^[21] ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }}$ ${\displaystyle \Sigma _{1}}$ ${\displaystyle \Sigma _{1}}$ ${\displaystyle V=L}$ ${\displaystyle KP}$ ${\displaystyle \Sigma _{1}}$ ${\displaystyle >\omega }$

Непроецируемые ординалы связаны с работой Дженсена по проекту. ^{[5] [22]} Наименьшие ординалы, которые непроецируемы относительно заданного множества, связаны с конструкцией Харрингтона наименьшего отражающего класса Спектора 2. ^{[15] стр.174}

«Недоказуемые» порядковые числа

Мы можем представить себе даже более крупные ординалы, которые все еще являются счетными. Например, если ZFC имеет транзитивную модель (гипотезу, более сильную, чем простая гипотеза согласованности, и подразумеваемую существованием недостижимого кардинала), то существует счетное число, такое, что является моделью ZFC. Такие ординалы находятся за пределами силы ZFC в том смысле, что она не может (по построению) доказать их существование. ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }}$

Если — рекурсивно перечислимая теория множеств, согласующаяся с V = L , то наименьшее такое, что меньше наименьшего устойчивого ординала, что следует из ^{[23] .} ${\displaystyle T}$ ${\displaystyle \alpha }$ ${\displaystyle (L_{\alpha },\in )\vDash T}$

Стабильные порядковые числа

Даже большие счетные ординалы, называемые устойчивыми ординалами , могут быть определены условиями неописуемости или такими, что является Σ 1 -элементарной подмоделью L ; существование этих ординалов может быть доказано в ZFC, ^[24], и они тесно связаны с непроектируемыми ординалами с точки зрения теории моделей. ^{[5] : 6} Для счетного , устойчивость эквивалентна . ^[5] ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\prec _{\Sigma _{1}}L_{\omega _{1}}}$

Наименее стабильный уровень имеет некоторые свойства, связанные с определимостью. Пусть будет наименьшим, таким, что : ${\displaystyle L}$ ${\displaystyle \sigma }$ ${\displaystyle L_{\sigma }\prec _{1}L}$

• Множество имеет определение в том и только том случае, если оно является членом . ^{[5] стр.6} ${\displaystyle \Sigma _{1}}$ ${\displaystyle L}$ ${\displaystyle L_{\sigma }}$
• Множество является множеством тогда и только тогда, когда оно является членом множества . ^{[5] стр.6} ${\displaystyle x\subseteq \mathbb {N} }$ ${\displaystyle \Delta _{2}^{1}}$ ${\displaystyle L_{\sigma }}$
• Множество является множеством тогда и только тогда, когда оно является -рекурсивно перечислимым, в терминологии теории альфа-рекурсии . ^{[5] стр.6} ${\displaystyle x\subseteq \mathbb {N} }$ ${\displaystyle \Sigma _{2}^{1}}$ ${\displaystyle \sigma }$

Варианты устойчивых порядковых числительных

Это ослабленные варианты стабильных ординалов. Существуют ординалы с этими свойствами, меньшие, чем вышеупомянутый наименее непроецируемый ординал, ^[5] например, ординал является -стабильным тогда и только тогда, когда он является -отражающим для всех натуральных . ^[18] ${\displaystyle (+1)}$ ${\displaystyle \Pi _{n}^{0}}$ ${\displaystyle n}$

• Счетный ординал называется -стабильным тогда и только тогда ^[5] ${\displaystyle \alpha }$ ${\displaystyle (+\beta )}$ ${\displaystyle L_{\alpha }\prec _{\Sigma _{1}}L_{\alpha +\beta }}$
• Счетный ординал называется -устойчивым тогда и только тогда , когда , где - наименьший допустимый ординал, больший . ^{[5] [25]} ${\displaystyle \alpha }$ ${\displaystyle (^{+})}$ ${\displaystyle L_{\alpha }\prec _{\Sigma _{1}}L_{\beta }}$ ${\displaystyle \beta }$ ${\displaystyle \alpha }$
• Счетный ординал называется -устойчивым тогда и только тогда , когда , где - наименьший допустимый ординал, больший допустимого ординала, большего . ^[25] ${\displaystyle \alpha }$ ${\displaystyle (^{++})}$ ${\displaystyle L_{\alpha }\prec _{\Sigma _{1}}L_{\beta }}$ ${\displaystyle \beta }$ ${\displaystyle \alpha }$
• Счетный ординал называется недостижимо-устойчивым тогда и только тогда , когда , где — наименьший рекурсивно недостижимый ординал, больший . ^[5] ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\prec _{\Sigma _{1}}L_{\beta }}$ ${\displaystyle \beta }$ ${\displaystyle \alpha }$
• Счетный ординал называется устойчивым по Мало тогда и только тогда , когда , где — наименьший рекурсивно ординал Мало, больший . ^[5] ${\displaystyle \alpha }$ ${\displaystyle L_{\alpha }\prec _{\Sigma _{1}}L_{\beta }}$ ${\displaystyle \beta }$ ${\displaystyle \alpha }$
• Счетный ординал называется дважды -устойчивым тогда и только тогда, когда существует -устойчивый ординал такой, что . ^[5] ${\displaystyle \alpha }$ ${\displaystyle (+1)}$ ${\displaystyle (+1)}$ ${\displaystyle \beta >\alpha }$ ${\displaystyle L_{\alpha }\prec _{\Sigma _{1}}L_{\beta }}$

Более сильные ослабления устойчивости появились в работах по теории доказательств, включая анализ подсистем арифметики второго порядка . ^[26]

Псевдохороший порядок

В схеме обозначений Клини некоторые представляют ординалы, а некоторые нет. Можно определить рекурсивный полный порядок, который является подмножеством обозначений Клини и имеет начальный сегмент, который является хорошо упорядоченным с order-type . Каждое рекурсивно перечислимое (или даже гиперарифметическое) непустое подмножество этого полного порядка имеет наименьший элемент. Поэтому оно напоминает хорошо упорядоченное в некоторых отношениях. Например, можно определить арифметические операции на нем. Тем не менее, невозможно эффективно определить точно, где заканчивается начальная хорошо упорядоченная часть и начинается часть, в которой отсутствует наименьший элемент. ${\displaystyle \omega _{1}^{\mathrm {CK} }}$

Для примера рекурсивного псевдохорошего порядка, пусть S будет ATR ₀ или другой рекурсивно аксиоматизируемой теорией, которая имеет ω-модель, но не имеет гиперарифметических ω-моделей, и (при необходимости) консервативно расширяет S с помощью функций Скулема . Пусть T будет деревом (по сути) конечных частичных ω-моделей S: Последовательность натуральных чисел принадлежит T тогда и только тогда, когда S плюс ∃m φ(m) ⇒ φ(x _⌈φ⌉ ) (для первых n формул φ с одной числовой свободной переменной; ⌈φ⌉ — число Гёделя) не имеет доказательства несоответствия короче n. Тогда порядок Клини–Брауэра T является рекурсивным псевдохорошим порядком. ${\displaystyle x_{1},x_{2},...,x_{n}}$

Любая такая конструкция должна иметь тип порядка , где — тип порядка , а — рекурсивный ординал. ^[27] ${\displaystyle \omega _{1}^{CK}\times (1+\eta )+\rho }$ ${\displaystyle \eta }$ ${\displaystyle (\mathbb {Q} ,<)}$ ${\displaystyle \rho }$

Ссылки

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

О рекурсивных ординалах

• Wolfram Pohlers, Proof theory , Springer 1989 ISBN  0-387-51842-8 (для иерархии Веблена и некоторых непредикативных ординалов). Это, вероятно, самая читаемая книга о больших счетных ординалах (что не говорит о многом).
• Гаиси Такеути , Теория доказательств , 2-е издание 1987 ISBN 0-444-10492-5 (для порядковых диаграмм) 
• Курт Шютте , Теория доказательств , Springer 1977 ISBN 0-387-07911-4 (для иерархии Веблена и некоторых непредикативных ординалов) 
• Крейг Сморински, Разнообразие древесного опыта Math. Intelligencer 4 (1982), № 4, 182–189; содержит неформальное описание иерархии Веблена.
• Хартли Роджерс-младший , Теория рекурсивных функций и эффективная вычислимость McGraw-Hill (1967) ISBN 0-262-68052-1 (описывает рекурсивные ординалы и ординал Чёрча-Клини) 
• Ларри В. Миллер, Нормальные функции и конструктивные порядковые обозначения , Журнал символической логики , том 41, номер 2, июнь 1976 г., страницы 439–459, JSTOR  2272243,
• Гильберт Левиц, Трансфинитные ординалы и их обозначения: для непосвященных , пояснительная статья (8 страниц, в PostScript )
• Герман Руге Джервелл, Истина и доказуемость, рукопись в процессе написания.

За пределами рекурсивных ординалов

• Barwise, Jon (1976). Допустимые множества и структуры: подход к теории определимости . Перспективы математической логики. Springer-Verlag. ISBN 3-540-07451-1.
• Хинман, Питер Г. (1978). Рекурсивно-теоретические иерархии . Перспективы в математической логике. Springer-Verlag.

Как рекурсивные, так и нерекурсивные ординалы

• Майкл Ратьен, «Область порядкового анализа». в SB Cooper и J. Truss (ред.): Sets and Proofs . (Cambridge University Press, 1999) 219–279. В файле Postscript.

Встроенные ссылки

1. Бухгольц, В. (1986-01-01). «Новая система доказательство-теоретических ординальных функций». Annals of Pure and Applied Logic . 32 : 195–207. doi : 10.1016/0168-0072(86)90052-7 . ISSN  0168-0072.
2. Симпсон, Стивен Г. (2009). Подсистемы арифметики второго порядка. Перспективы в логике (2-е изд.). Кембридж: Cambridge University Press. ISBN 978-0-521-88439-6.
3. В. Бухгольц, "Результат независимости для ( Π 1 1 − C A ) + B I {\displaystyle (\Pi _{1}^{1}{\mathsf {-CA}}){\mathsf {+BI}}} . (1987)"
4. Бухгольц, Вильфрид; Феферман, Соломон ; Полерс, Вольфрам; Зиг, Вильфрид (1981). Итерированные индуктивные определения и подсистемы анализа: недавние исследования теории доказательств . Конспект лекций по математике. Том 897. Springer-Verlag, Берлин-Нью-Йорк. doi :10.1007/bfb0091894. ISBN 3-540-11170-0. МР  0655036.
5. «Зоопарк ординалов» (PDF) . Мадор . 29 июля 2017 г. Проверено 10 августа 2021 г.
6. В. Бухгольц, Новая система доказательно-теоретических ординальных функций (1984) (леммы 1.3 и 1.8). Доступ 2022-05-04.
7. Ратьен, Майкл (1994-01-01). "Сворачивание функций на основе рекурсивно больших порядковых чисел: хорошо упорядоченное доказательство для KPM". Архив для Mathematical Logic . 33 (1): 35–55. doi :10.1007/BF01275469. ISSN  1432-0665. S2CID  35012853.
8. "Порядковые обозначения, основанные на слабо кардинале Мало" (PDF) . Университет Лидса . 1990. Получено 10 августа 2021 г.
9. "Доказательство теории отражения" (PDF) . Университет Лидса . 1993-02-21 . Получено 2021-08-10 .
10. Stegert, Jan-Carl (2010). «Теория ординального доказательства теории множеств Крипке-Платека, дополненная принципами сильного отражения». miami.uni-muenster.de . Получено 10 августа 2021 г.
11. Фридман, Х., Йенсен, Р. (1968). Заметка о допустимых ординалах. В: Барвайз, Дж. (ред.) Синтаксис и семантика бесконечных языков. Конспект лекций по математике, т. 72. Springer, Берлин, Гейдельберг.
12. Сакс, Джеральд Э. (1976). «Счетные допустимые ординалы и гиперстепени». Успехи в математике . 20 (2): 213–262. doi : 10.1016/0001-8708(76)90187-0 .
13. "Подсистемы арифметики второго порядка" (PDF) . Penn State Institution . 2006-02-07 . Получено 2010-08-10 .
14. Ф. Г. Абрамсон, Дж. Е. Сакс, «Неисчисляемые ординалы Ганди» (1976), стр.387. По состоянию на 13 февраля 2023 г.
15. A. Kechris, "Spector Second-order Classes and Reflection". Появляется в Generalized Recursion Theory II: Proceedings of the 1977 Oslo Symposium , Studies in Logic and the Foundation of Mathematics vol. 94 (1978), pp.147--183
16. Араи, Тошиясу (2015). «Упрощенный анализ отражения первого порядка». arXiv : 1907.17611v1 .
17. В. Рихтер, П. Ацель, Индуктивные определения и свойства отражения допустимых ординалов (1973)
18. Рихтер, Уэйн; Ацель, Питер (1974-01-01). "Индуктивные определения и отражающие свойства допустимых ординалов" (PDF) . Исследования по логике и основаниям математики . 79 : 301–381. doi :10.1016/S0049-237X(08)70592-5. hdl :10852/44063. ISBN 9780444105455. ISSN  0049-237X.
19. S. Feferman, «Неописуемые кардиналы и допустимые аналоги» (2013, неопубликовано). Доступ 18 ноября 2022 г.
20. KJ Devlin, Введение в тонкую структуру конструктивной иерархии, Исследования по логике и основаниям математики (т. 79, 1974). Доступ 2022-12-04.
21. "Fred G. Abramson, Locally countable models of Σ 1 {\displaystyle \Sigma _{1}} -separation" (2014). Доступ 23 июля 2022 г.
22. KJ Devlin, Введение в тонкую структуру конструктивной иерархии (1974). Доступ 21 февраля 2023 г.
23. В. Марек, К. Расмуссен, Спектр L в библиотеках ( каталог WorldCat ) (страница EuDML), Państwowe Wydawn. Доступ 01 декабря 2022 г.
24. Барвайз (1976), теорема 7.2.
25. Simpson, Stephen G. (1978-01-01). "Краткий курс по теории допустимой рекурсии". Исследования по логике и основаниям математики . 94 : 355–390. doi :10.1016/S0049-237X(08)70941-8. ISBN 9780444851635. ISSN  0049-237X.
26. Араи, Тошиясу (1996). «Введение в жесткую линию в теорию доказательств». arXiv : 1104.1842v1 [math.LO].
27. W. Chan, Счетное допустимое отношение порядковой эквивалентности (2017), стр. 1233. Доступ 28 декабря 2022 г.