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

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

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

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

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

Основная статья: Вычислимый порядковый номер

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

Основная статья: Порядковое обозначение

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

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

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

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

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

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

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

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

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

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

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

Основная статья: функция Веблена

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

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

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

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

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

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

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

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

Импредикативные ординалы

Основная статья: Порядковая схлопывающая функция

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Порядковый номер Церкви – Клини

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

Допустимые ординалы

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

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

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

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

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

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

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

Отражение

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

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

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

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

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

«Недоказуемые» ординалы

См. Также: Минимальная модель (теория множеств)

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

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

Стабильные ординалы

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

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

• В наборе есть $\Sigma _{1}$ определение в $L$ если он является членом $L_{\sigma }$. ^стр.6
• Набор $x\subseteq \mathbb {N}$ является $\Delta _{2}^{1}$ если он является членом $L_{\sigma }$. ^стр.6
• Набор $x\subseteq \mathbb {N}$ является $\Sigma _{2}^{1}$ если это так $\sigma$-рекурсивно перечислимое, в терминологии теории альфа-рекурсии . ^стр.6

Варианты стабильных ординалов

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

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

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

Псевдо-хорошо упорядоченный

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

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

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

Ссылки

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

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

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

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

• Барвайз, Джон (1976). Допустимые множества и структуры: подход к теории определимости . Перспективы математической логики. Спрингер-Верлаг. ISBN  3-540-07451-1 .
• Хинман, Питер Г. (1978). Теоретико-рекурсивные иерархии . Перспективы математической логики. Спрингер-Верлаг.

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

• Майкл Ратьен , «Царство порядкового анализа». в С.Б. Купере и Дж. Трассе (ред.): Наборы и доказательства . (Издательство Кембриджского университета, 1999) 219–279. В файле Postscript .