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

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

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

Использование и определение порядковых схлопывающих функций неразрывно переплетено с теорией порядкового анализа , поскольку большие счетные ординалы, определяемые и обозначаемые данным коллапсом, используются для описания ординально-теоретической силы определенных формальных систем , обычно подсистемы анализа (например, те, которые рассматриваются в свете обратной математики ), расширения теории множеств Крипке-Платека , в стиле Бишопа системы конструктивной математики или в стиле Мартина-Лёфа системы интуиционистской теории типа .

Порядковые свертывающиеся функции обычно обозначаются с использованием некоторых вариаций греческой буквы $\psi$ ( пси ) или $\theta$ ( тета ).

Пример, ведущий к порядковому номеру Бахмана – Говарда.

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

Определение

Позволять $\Omega$ обозначают первый неисчисляемый порядковый номер $\omega _{1}$, или, по сути, любой порядковый номер, который является $\varepsilon$-числом и гарантированно будет больше, чем все счетные ординалы , которые будут построены (например, ординал Чёрча-Клин достаточен для наших целей; но мы будем работать с $\omega _{1}$ слово счетный поскольку это позволяет удобно использовать в определениях ).

Мы определяем функцию $\psi$ (который будет неубывающим и непрерывным ), взяв произвольный порядковый номер $\alpha$ до счетного ординала $\psi (\alpha )$, рекурсивно на $\alpha$, следующее:

Предполагать $\psi (\beta )$ было определено для всех $\beta <\alpha$, и мы хотим определить $\psi (\alpha )$.

Позволять $C(\alpha )$ быть набором порядковых номеров, сгенерированных, начиная с $0$, $1$, $\omega$ и $\Omega$ рекурсивно применяя следующие функции: порядковое сложение, умножение и возведение в степень, а также функцию $\psi \upharpoonright _{\alpha }$, то есть ограничение $\psi$ порядковым номерам $\beta <\alpha$. (Формально мы определяем $C(\alpha )_{0}=\{0,1,\omega ,\Omega \}$ и индуктивно $C(\alpha )_{n+1}=C(\alpha )_{n}\cup \{\beta _{1}+\beta _{2},\beta _{1}\beta _{2},{\beta _{1}}^{\beta _{2}}:\beta _{1},\beta _{2}\in C(\alpha )_{n}\}\cup \{\psi (\beta ):\beta \in C(\alpha )_{n}\land \beta <\alpha \}$ для всех натуральных чисел $n$ и мы позволяем $C(\alpha )$ быть союзом $C(\alpha )_{n}$ для всех $n$.)

Затем $\psi (\alpha )$ определяется как наименьший порядковый номер, не принадлежащий $C(\alpha )$.

Более кратко (хотя и более неясно):

$\psi (\alpha )$ наименьший порядковый номер, который нельзя выразить через $0$, $1$, $\omega$ и $\Omega$ используя суммы, произведения, экспоненты и $\psi$ сама функция (к ранее построенным ординалам меньше $\alpha$).

Здесь предпринята попытка объяснить мотивацию определения $\psi$ интуитивно: поскольку обычных операций сложения, умножения и возведения в степень недостаточно для очень далекого обозначения ординалов, мы пытаемся систематически создавать новые имена для ординалов, беря первое, у которого еще нет имени, и всякий раз, когда у нас заканчивается имен, вместо того, чтобы изобретать их ad hoc или использовать диагональные схемы , мы ищем их в порядковых числах, далеко выходящих за пределы тех, которые мы конструируем (за пределами $\Omega$, то есть); поэтому мы даем имена неисчисляемым порядковым номерам и, поскольку в конечном итоге список имен обязательно счетен, $\psi$ «свернёт» их до счётных порядковых номеров.

Вычисление значений ψ

Чтобы уточнить, как работает функция $\psi$ способен создавать обозначения для определенных порядковых номеров, теперь мы вычислим его первые значения.

Предикативное начало

Сначала рассмотрим $C(0)$. Он содержит порядковые номера $0,1,2,3,\omega ,\omega +1,\omega +2,\omega \cdot 2,\omega \cdot 3,\omega ^{2},\omega ^{3},\omega ^{\omega },\omega ^{\omega ^{\omega }}$ и так далее. Он также содержит такие порядковые номера, как $\Omega ,\Omega +1,\omega ^{\Omega +1},\Omega ^{\Omega }$. Первый порядковый номер, которого он не содержит, равен $\varepsilon _{0}$ (что является пределом $\omega$, $\omega ^{\omega }$, $\omega ^{\omega ^{\omega }}$ и так далее — меньше $\Omega$ по предположению). Верхняя граница содержащихся в нем порядковых номеров равна $\varepsilon _{\Omega +1}$ (предел $\Omega$, $\Omega ^{\Omega }$, $\Omega ^{\Omega ^{\Omega }}$ и так далее), но это не столь важно. Это показывает, что $\psi (0)=\varepsilon _{0}$.

Сходным образом, $C(1)$ содержит порядковые номера, которые можно составить из $0$, $1$, $\omega$, $\Omega$ и на этот раз также $\varepsilon _{0}$, используя сложение, умножение и возведение в степень. Он содержит все порядковые номера до $\varepsilon _{1}$ но не последнее, так что $\psi (1)=\varepsilon _{1}$. Таким образом, мы доказываем, что $\psi (\alpha )=\varepsilon _{\alpha }$ индуктивно на $\alpha$: доказательство работает, однако, только до тех пор, пока $\alpha <\varepsilon _{\alpha }$. Таким образом, мы имеем:

$\psi (\alpha )=\varepsilon _{\alpha }=\phi _{1}(\alpha )$ для всех $\alpha \leq \zeta _{0}$, где $\zeta _{0}=\phi _{2}(0)$ это наименьшая неподвижная точка $\alpha \mapsto \varepsilon _{\alpha }$.

(Здесь, $\phi$ функции — это функции Веблена, определенные, начиная с $\phi _{1}(\alpha )=\varepsilon _{\alpha }$.)

Сейчас $\psi (\zeta _{0})=\zeta _{0}$ но $\psi (\zeta _{0}+1)$ не больше, так как $\zeta _{0}$ не может быть построено с использованием конечных приложений $\phi _{1}\colon \alpha \mapsto \varepsilon _{\alpha }$ и поэтому никогда не принадлежит $C(\alpha )$ набор для $\alpha \leq \Omega$, и функция $\psi$ остается «застрявшим» на $\zeta _{0}$ в течение некоторого времени:

$\psi (\alpha )=\zeta _{0}$ для всех $\zeta _{0}\leq \alpha \leq \Omega$.

Первые импредикативные значения

Снова, $\psi (\Omega )=\zeta _{0}$. Однако, когда мы подходим к вычислениям $\psi (\Omega +1)$, что-то изменилось: с тех пор $\Omega$ был («искусственно») добавлен ко всем $C(\alpha )$, нам разрешено принять значение $\psi (\Omega )=\zeta _{0}$ в процессе. Так $C(\Omega +1)$ содержит все порядковые номера, которые можно построить из $0$, $1$, $\omega$, $\Omega$, $\phi _{1}\colon \alpha \mapsto \varepsilon _{\alpha }$ функционировать до $\zeta _{0}$ и на этот раз также $\zeta _{0}$ сам, используя сложение, умножение и возведение в степень. Наименьший порядковый номер, которого нет в $C(\Omega +1)$ является $\varepsilon _{\zeta _{0}+1}$ (самый маленький $\varepsilon$-номер после $\zeta _{0}$).

Мы говорим, что определение $\psi (\Omega )=\zeta _{0}$ и следующие значения функции $\psi$ такой как $\psi (\Omega +1)=\varepsilon _{\zeta _{0}+1}$ непредикативны , поскольку используют порядковые номера (здесь $\Omega$) больше, чем определяемые (здесь $\zeta _{0}$).

Значения ψ с точностью до ординала Фефермана – Шютте.

Тот факт, что $\psi (\Omega +\alpha )$ равно $\varepsilon _{\zeta _{0}+\alpha }$ остается верным для всех $\alpha \leq \zeta _{1}=\phi _{2}(1)$. (Обратите внимание, в частности, что $\psi (\Omega +\zeta _{0})=\varepsilon _{\zeta _{0}\cdot 2}$: но поскольку теперь порядковый номер $\zeta _{0}$ уже построено, и ничто не мешает выйти за рамки этого). Однако в $\zeta _{1}=\phi _{2}(1)$ (первая фиксированная точка $\alpha \mapsto \varepsilon _{\alpha }$ вне $\zeta _{0}$), строительство снова останавливается, потому что $\zeta _{1}$ не может быть построено из меньших порядковых номеров и $\zeta _{0}$ путем конечного применения $\varepsilon$ функция. Итак, у нас есть $\psi (\Omega \cdot 2)=\zeta _{1}$.

Те же рассуждения показывают, что $\psi (\Omega (1+\alpha ))=\phi _{2}(\alpha )$ для всех $\alpha \leq \phi _{3}(0)=\eta _{0}$, где $\phi _{2}$ перечисляет неподвижные точки $\phi _{1}\colon \alpha \mapsto \varepsilon _{\alpha }$ и $\phi _{3}(0)$ является первой фиксированной точкой $\phi _{2}$. Тогда у нас есть $\psi (\Omega ^{2})=\phi _{3}(0)$.

Опять же, мы можем это видеть $\psi (\Omega ^{\alpha })=\phi _{1+\alpha }(0)$ в течение некоторого времени: это остается верным до первой фиксированной точки $\Gamma _{0}$ из $\alpha \mapsto \phi _{\alpha }(0)$, который является ординалом Фефермана-Шютте . Таким образом, $\psi (\Omega ^{\Omega })=\Gamma _{0}$ – ординал Фефермана–Шхютте.

За пределами ординала Фефермана – Шюте

У нас есть $\psi (\Omega ^{\Omega }+\Omega ^{\alpha })=\phi _{\Gamma _{0}+\alpha }(0)$ для всех $\alpha \leq \Gamma _{1}$ где $\Gamma _{1}$ является следующей фиксированной точкой $\alpha \mapsto \phi _{\alpha }(0)$. Итак, если $\alpha \mapsto \Gamma _{\alpha }$ перечисляет рассматриваемые фиксированные точки (что также можно отметить $\phi (1,0,\alpha )$ с помощью многозначных функций Веблена) имеем $\psi (\Omega ^{\Omega }(1+\alpha ))=\Gamma _{\alpha }$, до первой фиксированной точки $\phi (1,1,0)$ принадлежащий $\alpha \mapsto \Gamma _{\alpha }$ себя, что будет $\psi (\Omega ^{\Omega +1})$ (и первая фиксированная точка $\phi (2,0,0)$ принадлежащий $\alpha \mapsto \phi (1,\alpha ,0)$ функции будут $\psi (\Omega ^{\Omega \cdot 2})$). Таким образом:

• $\psi (\Omega ^{\Omega ^{2}})$ – ординал Аккермана (диапазон обозначений $\phi (\alpha ,\beta ,\gamma )$ определяется предикативно),
• $\psi (\Omega ^{\Omega ^{\omega }})$ – «малый» порядковый номер Веблена (диапазон обозначений $\phi (\cdot )$ предикативно с использованием конечного числа переменных),
• $\psi (\Omega ^{\Omega ^{\Omega }})$ – «большой» порядковый номер Веблена (диапазон обозначений $\phi (\cdot )$ предикативно с использованием трансфинитно, но предикативно многих переменных),
• предел $\psi (\varepsilon _{\Omega +1})$ из $\psi (\Omega )$, $\psi (\Omega ^{\Omega })$, $\psi (\Omega ^{\Omega ^{\Omega }})$и т. д. — это ординал Бахмана–Говарда : после этого наша функция $\psi$ является константой, и мы не можем идти дальше с данным определением.

Порядковые обозначения до порядкового номера Бахмана – Говарда.

Теперь мы объясним более систематически, как $\psi$ Функция определяет обозначения для ординалов до ординала Бахмана – Говарда.

Примечание о базовых представлениях

Напомним, что если $\delta$ это порядковый номер, который является степенью $\omega$ (например $\omega$ сам по себе, или $\varepsilon _{0}$, или $\Omega$), любой порядковый номер $\alpha$ может быть однозначно выражено в виде $\delta ^{\beta _{1}}\gamma _{1}+\ldots +\delta ^{\beta _{k}}\gamma _{k}$, где $k$ является натуральным числом, $\gamma _{1},\ldots ,\gamma _{k}$ ненулевые ординалы меньше, чем $\delta$, и $\beta _{1}>\beta _{2}>\cdots >\beta _{k}$ являются порядковыми числами (мы допускаем $\beta _{k}=0$). Эта «база $\delta$ представление» является очевидным обобщением нормальной формы Кантора (что имеет место $\delta =\omega$). Конечно, вполне может быть, что выражение неинтересно, т.е. $\alpha =\delta ^{\alpha }$, но в любом другом случае $\beta _{i}$ все должно быть меньше $\alpha$; также может быть случай, когда выражение тривиально (т. е. $\alpha <\delta$, в этом случае $k\leq 1$ и $\gamma _{1}=\alpha$).

Если $\alpha$ является порядковым номером меньше, чем $\varepsilon _{\Omega +1}$, то его основание $\Omega$ представление имеет коэффициенты $\gamma _{i}<\Omega$ (по определению) и показатели $\beta _{i}<\alpha$ (из-за предположения $\alpha <\varepsilon _{\Omega +1}$): следовательно, можно переписать эти показатели в базе $\Omega$ и повторять операцию до тех пор, пока процесс не завершится (любая убывающая последовательность ординалов конечна). Полученное выражение назовем итерированной базой $\Omega$ представление ​ $\alpha$ и различные коэффициенты, участвующие (в том числе в качестве показателей степени) в частях представления (все они $<\Omega$), или, короче, $\Omega$-кусочки $\alpha$.

Некоторые свойства ψ

• Функция $\psi$ неубывает и непрерывен (это более или менее очевидно из его определения).
• Если $\psi (\alpha )=\psi (\beta )$ с $\beta <\alpha$ тогда обязательно $C(\alpha )=C(\beta )$. Действительно, никакого порядкового номера $\beta '$ с $\beta \leq \beta '<\alpha$ может принадлежать $C(\alpha )$ (в противном случае его изображение $\psi$, что $\psi (\alpha )$ принадлежал бы $C(\alpha )$ - невозможный); так $C(\beta )$ закрыто всем, под чем $C(\alpha )$ это замыкание, поэтому они равны.
• Любое значение $\gamma =\psi (\alpha )$ взятый $\psi$ это $\varepsilon$-число (т.е. фиксированная точка $\beta \mapsto \omega ^{\beta }$). Действительно, если бы это было не так, то, записав его в нормальной форме Кантора , его можно было бы выразить с помощью сумм, произведений и возведения в степень от элементов, меньших его, следовательно, в $C(\alpha )$, так что это будет в $C(\alpha )$, противоречие.
• Лемма: Предположим $\delta$ это $\varepsilon$-номер и $\alpha$ порядковый номер такой, что $\psi (\beta )<\delta$ для всех $\beta <\alpha$: тогда $\Omega$-куски (определенные выше ) любого элемента $C(\alpha )$ меньше, чем $\delta$. Действительно, пусть $C'$ быть набором ординалов, все из которых $\Omega$- штук меньше $\delta$. Затем $C'$ замкнуто относительно сложения, умножения и возведения в степень (поскольку $\delta$ это $\varepsilon$-число, поэтому ординалы меньше его замыкаются при сложении, умножении и возведении в степень). И $C'$ также содержит все $\psi (\beta )$ для $\beta <\alpha$ по предположению, и он содержит $0$, $1$, $\omega$, $\Omega$. Так $C'\supseteq C(\alpha )$, который должен был быть показан.
• В условиях предыдущей леммы $\psi (\alpha )\leq \delta$ (действительно, лемма показывает, что $\delta \not \in C(\alpha )$).
• Любой $\varepsilon$-число меньше некоторого элемента в диапазоне $\psi$ сам находится в пределах $\psi$ (то есть, $\psi$ опускает нет $\varepsilon$-число). Действительно: если $\delta$ это $\varepsilon$-число, не превышающее диапазон $\psi$, позволять $\alpha$ быть наименьшей верхней границей $\beta$ такой, что $\psi (\beta )<\delta$: тогда согласно вышеизложенному мы имеем $\psi (\alpha )\leq \delta$, но $\psi (\alpha )<\delta$ противоречило бы тому факту, что $\alpha$ является наименьшей верхней границей, поэтому $\psi (\alpha )=\delta$.
• В любое время $\psi (\alpha )=\delta$, набор $C(\alpha )$ состоит именно из таких ординалов $\gamma$ (меньше, чем $\varepsilon _{\Omega +1}$) все чьи $\Omega$- штук меньше $\delta$. Действительно, мы знаем, что все ординалы меньше $\delta$, следовательно, все ординалы (меньше $\varepsilon _{\Omega +1}$) чей $\Omega$- штук меньше $\delta$, находятся в $C(\alpha )$. И наоборот, если мы предположим $\psi (\beta )<\delta$ для всех $\beta <\alpha$ (другими словами, если $\alpha$ минимально возможно с $\psi (\alpha )=\delta$), лемма дает искомое свойство. С другой стороны, если $\psi (\alpha )=\psi (\beta )$ для некоторых $\beta <\alpha$, то мы уже заметили $C(\alpha )=C(\beta )$ и мы можем заменить $\alpha$ как можно меньше с $\psi (\alpha )=\delta$.

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

Используя приведенные выше факты, мы можем определить (каноническую) порядковую запись для каждого $\gamma$ меньше ординала Бахмана – Говарда. Сделаем это индукцией по $\gamma$.

Если $\gamma$ меньше, чем $\varepsilon _{0}$, мы используем итерированную нормальную форму Кантора $\gamma$. В противном случае существует самый большой $\varepsilon$-число $\delta$ меньше или равно $\gamma$ (это потому, что набор $\varepsilon$-числа закрыты): если $\delta <\gamma$ то по индукции мы определили обозначение для $\delta$ и база $\delta$ представление $\gamma$ дает один за $\gamma$, итак, мы закончили.

Остается рассмотреть случай, когда $\gamma =\delta$ это $\varepsilon$-число: мы доказали, что в этом случае мы можем написать $\delta =\psi (\alpha )$ для некоторого (возможно, несчетного) порядкового номера $\alpha <\varepsilon _{\Omega +1}$: позволять $\alpha$ быть максимально возможным таким порядковым номером (который существует, поскольку $\psi$ является непрерывным). Используем итерированную базу $\Omega$ представление $\alpha$: осталось показать, что каждая часть этого представления меньше $\delta$ (поэтому мы уже определили для него обозначение). Если это не так, то по показанным нами свойствам $C(\alpha )$ не содержит $\alpha$; но потом $C(\alpha +1)=C(\alpha )$ (они закрываются при тех же операциях, так как значение $\psi$ в $\alpha$ никогда не может быть взят), поэтому $\psi (\alpha +1)=\psi (\alpha )=\delta$, что противоречит максимальности $\alpha$.

Примечание . На самом деле мы определили канонические обозначения не только для ординалов ниже ординала Бахмана–Говарда, но и для некоторых несчетных ординалов, а именно тех, у которых $\Omega$-части меньше порядкового номера Бахмана-Говарда (а именно: запишите их в итерированной базе $\Omega$ представление и использовать каноническое представление для каждого фрагмента). Эта каноническая запись используется для аргументов $\psi$ функция (которая может быть несчетной).

Примеры

Для порядковых чисел меньше $\varepsilon _{0}=\psi (0)$, определенное каноническое порядковое обозначение совпадает с итерированной нормальной формой Кантора (по определению).

Для порядковых чисел меньше $\varepsilon _{1}=\psi (1)$, обозначение совпадает с итерированной базой $\varepsilon _{0}$ обозначения (части сами по себе записаны в итерированной нормальной форме Кантора): например, $\omega ^{\omega ^{\varepsilon _{0}+\omega }}$ будет написано ${\varepsilon _{0}}^{\omega ^{\omega }}$, или, точнее, $\psi (0)^{\omega ^{\omega }}$. Для порядковых чисел меньше $\varepsilon _{2}=\psi (2)$, аналогично пишем в итерированной базе $\varepsilon _{1}$ а затем записать кусочки в итерированную базу $\varepsilon _{0}$ фрагменты (и запишите эти в итерированной нормальной форме Кантора): итак $\omega ^{\omega ^{\varepsilon _{1}+\varepsilon _{0}+1}}$ написано ${\varepsilon _{1}}^{\varepsilon _{0}\omega }$, или, точнее, $\psi (1)^{\psi (0)\,\omega }$. Таким образом, до $\zeta _{0}=\psi (\Omega )$, мы всегда используем максимально возможный $\varepsilon$-числовая база, дающая нетривиальное представление.

Помимо этого, нам может потребоваться выразить порядковые номера за пределами $\Omega$: это всегда делается в итерации $\Omega$-база, а сами фигуры нужно выразить с помощью максимально возможного $\varepsilon$-числовая база, дающая нетривиальное представление.

Обратите внимание, что пока $\psi (\varepsilon _{\Omega +1})$ равен порядковому номеру Бахмана-Говарда, это не «каноническая запись» в том смысле, который мы определили (канонические обозначения определены только для порядковых номеров, меньших, чем порядковый номер Бахмана-Говарда).

Условия каноничности

Определенные таким образом обозначения обладают свойством: всякий раз, когда они вложены друг в друга, $\psi$ функции, аргументы «внутренних» $\psi$ функции всегда меньше, чем у «внешней» (это следствие того, что $\Omega$-кусочки $\alpha$, где $\alpha$ является максимально возможным таким, что $\psi (\alpha )=\delta$ для некоторых $\varepsilon$-число $\delta$, все меньше $\delta$, как мы показали выше). Например, $\psi (\psi (\Omega )+1)$ не встречается в виде записи: это четко определенное выражение (и оно равно $\psi (\Omega )=\zeta _{0}$ с $\psi$ является постоянным между $\zeta _{0}$ и $\Omega$), но это не запись, созданная индуктивным алгоритмом, который мы изложили.

Каноничность можно проверить рекурсивно: выражение канонично тогда и только тогда, когда оно является либо повторной канторовской нормальной формой порядкового числа меньшего $\varepsilon _{0}$, или повторенная база $\delta$ представление, все части которого каноничны, для некоторых $\delta =\psi (\alpha )$ где $\alpha$ сам написан на итерированной базе $\Omega$ представление, все части которого каноничны и меньше $\delta$. Порядок проверяется лексикографической проверкой на всех уровнях (имея в виду, что $\Omega$ больше любого выражения, полученного $\psi$, а для канонических значений тем больше $\psi$ всегда превосходит меньшие или даже произвольные суммы, произведения и экспоненты меньшего).

Например, $\psi (\Omega ^{\omega +1}\,\psi (\Omega )+\psi (\Omega ^{\omega })^{\psi (\Omega ^{2})}42)^{\psi (1729)\,\omega }$ - это каноническая запись для ординала, меньшего ординала Фефермана – Шютте: его можно записать с использованием функций Веблена как $\varphi _{1}(\varphi _{\omega +1}(\varphi _{2}(0))+\varphi _{\omega }(0)^{\varphi _{3}(0)}42)^{\varphi _{1}(1729)\,\omega }$.

Что касается порядка, то можно отметить, что $\psi (\Omega ^{\Omega })$ (порядковый номер Фефермана-Шютте) намного больше, чем $\psi (\Omega ^{\psi (\Omega )})=\varphi _{\varphi _{2}(0)}(0)$ (потому что $\Omega$ больше, чем $\psi$ чего-либо) и $\psi (\Omega ^{\psi (\Omega )})=\varphi _{\varphi _{2}(0)}(0)$ само по себе гораздо больше, чем $\psi (\Omega )^{\psi (\Omega )}=\varphi _{2}(0)^{\varphi _{2}(0)}$ (потому что $\Omega ^{\psi (\Omega )}$ больше, чем $\Omega$, поэтому любое выражение суммы произведения или экспоненциальное выражение, включающее $\psi (\Omega )$ и меньшее значение останется меньше, чем $\psi (\Omega ^{\Omega })$). Фактически, $\psi (\Omega )^{\psi (\Omega )}$ уже меньше, чем $\psi (\Omega +1)$.

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

Основная статья: Фундаментальная последовательность (порядковые номера)

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

Следующие правила более или менее очевидны, за исключением последнего:

• Во-первых, избавьтесь от (итерированной) базы $\delta$ представления: определить стандартную последовательность, сходящуюся к $\alpha =\delta ^{\beta _{1}}\gamma _{1}+\cdots +\delta ^{\beta _{k}}\gamma _{k}$, где $\delta$ либо $\omega$ или $\psi (\cdots )$ (или $\Omega$, но см. ниже):
  • если $k$ тогда равен нулю $\alpha =0$ и ничего не поделаешь;
  • если $\beta _{k}$ равен нулю и $\gamma _{k}$ является преемником, то $\alpha$ является преемником и ничего не поделаешь;
  • если $\gamma _{k}$ является пределом, возьмем стандартную последовательность, сходящую к $\gamma _{k}$ и заменить $\gamma _{k}$ в выражении элементами этой последовательности;
  • если $\gamma _{k}$ является преемником и $\beta _{k}$ это предел, перепишите последний член $\delta ^{\beta _{k}}\gamma _{k}$ как $\delta ^{\beta _{k}}(\gamma _{k}-1)+\delta ^{\beta _{k}}$ и замените показатель степени $\beta _{k}$ в последнем члене сходящимися к нему элементами основной последовательности;
  • если $\gamma _{k}$ является преемником и $\beta _{k}$ также переписать последний член $\delta ^{\beta _{k}}\gamma _{k}$ как $\delta ^{\beta _{k}}(\gamma _{k}-1)+\delta ^{\beta _{k}-1}\delta$ и замените последний $\delta$ в этом выражении сходящимися к нему элементами фундаментальной последовательности.
• Если $\delta$ является $\omega$, тогда примите очевидное $0,1,2,3,\ldots$ как фундаментальная последовательность $\delta$.
• Если $\delta =\psi (0)$ затем возьмем в качестве фундаментальной последовательности для $\delta$ последовательность $\omega ,\omega ^{\omega },\omega ^{\omega ^{\omega }},\ldots$
• Если $\delta =\psi (\alpha +1)$ затем возьмем в качестве фундаментальной последовательности для $\delta$ последовательность $\psi (\alpha ),\psi (\alpha )^{\psi (\alpha )},\psi (\alpha )^{\psi (\alpha )^{\psi (\alpha )}},\ldots$
• Если $\delta =\psi (\alpha )$ где $\alpha$ является предельным ординалом счетной конфинальности, определите стандартную последовательность для $\delta$ получить, подав заявку $\psi$ стандартной последовательности для $\alpha$ (напомним, что $\psi$ здесь непрерывен и возрастает).
• Осталось рассмотреть случай, когда $\delta =\psi (\alpha )$ с $\alpha$ ординал несчетной конфинальности (например, $\Omega$ сам). Очевидно, не имеет смысла определять последовательность, сходящуюся к $\alpha$ в этом случае; однако то, что мы можем определить, — это последовательность, сходящаяся к некоторому $\rho <\alpha$ со счетной конфинальностью и такой, что $\psi$ является постоянным между $\rho$ и $\alpha$. Этот $\rho$ будет первой неподвижной точкой некоторой (непрерывной и неубывающей) функции $\xi \mapsto h(\psi (\xi ))$. Чтобы его найти, примените те же правила (из базы $\Omega$ представление $\alpha$), чтобы найти каноническую последовательность $\alpha$, за исключением того, что всякий раз, когда последовательность, сходящаяся к $\Omega$ требуется (то, чего не может существовать), замените $\Omega$ в вопросе, в выражении $\alpha =h(\Omega )$, по $\psi (\xi )$ (где $\xi$ является переменной) и выполнить повторную итерацию (начиная с $0$, скажем) функции $\xi \mapsto h(\psi (\xi ))$: это дает последовательность $0,h(\psi (0)),h(\psi (h(\psi (0)))),\ldots$ склонен к $\rho$и каноническая последовательность для $\psi (\alpha )=\psi (\rho )$ является $\psi (0)$, $\psi (h(\psi (0)))$, $\psi (h(\psi (h(\psi (0)))))$... Если мы позволим $n$-й элемент (начиная с $0$) фундаментальной последовательности для $\delta$ обозначаться как $\delta [n]$, то мы сможем выразить это более четко, используя рекурсию. Используя эти обозначения, мы видим, что $\delta [0]=\psi (0)$ довольно легко. Мы можем определить остальную часть последовательности, используя рекурсию: $\delta [n]=\psi (h(\delta [n-1]))$. (Приведенные ниже примеры должны прояснить это.)

Вот несколько примеров для последнего (и самого интересного) случая:

• Каноническая последовательность для $\psi (\Omega )$ является: $\psi (0)$, $\psi (\psi (0))$, $\psi (\psi (\psi (0)))$... Это действительно сходится к $\rho =\psi (\Omega )=\zeta _{0}$ после чего $\psi$ является постоянным до тех пор, пока $\Omega$.
• Каноническая последовательность для $\psi (\Omega 2)$ является: $\psi (0)$, $\psi (\Omega +\psi (0))$, $\psi (\Omega +\psi (\Omega +\psi (0))),\ldots$ Это действительно сходится к значению $\psi$ в $\rho =\Omega +\psi (\Omega 2)=\Omega +\zeta _{1}$ после чего $\psi$ является постоянным до тех пор, пока $\Omega 2$.
• Каноническая последовательность для $\psi (\Omega ^{2})$ является: $\psi (0),\psi (\Omega \psi (0)),\psi (\Omega \psi (\Omega \psi (0))),\ldots$ Это сходится к значению $\psi$ в $\rho =\Omega \psi (\Omega ^{2})$.
• Каноническая последовательность для $\psi (\Omega ^{2}3+\Omega )$ является $\psi (0),\psi (\Omega ^{2}3+\psi (0)),\psi (\Omega ^{2}3+\psi (\Omega ^{2}3+\psi (0))),\ldots$ Это сходится к значению $\psi$ в $\rho =\Omega ^{2}3+\psi (\Omega ^{2}3+\Omega )$.
• Каноническая последовательность для $\psi (\Omega ^{\Omega })$ является: $\psi (0),\psi (\Omega ^{\psi (0)}),\psi (\Omega ^{\psi (\Omega ^{\psi (0)})}),\ldots$ Это сходится к значению $\psi$ в $\rho =\Omega ^{\psi (\Omega ^{\Omega })}$.
• Каноническая последовательность для $\psi (\Omega ^{\Omega }3)$ является: $\psi (0),\psi (\Omega ^{\Omega }2+\Omega ^{\psi (0)}),\psi (\Omega ^{\Omega }2+\Omega ^{\psi (\Omega ^{\Omega }2+\Omega ^{\psi (0)})}),\ldots$ Это сходится к значению $\psi$ в $\rho =\Omega ^{\Omega }2+\Omega ^{\psi (\Omega ^{\Omega }3)}$.
• Каноническая последовательность для $\psi (\Omega ^{\Omega +1})$ является: $\psi (0),\psi (\Omega ^{\Omega }\psi (0)),\psi (\Omega ^{\Omega }\psi (\Omega ^{\Omega }\psi (0))),\ldots$ Это сходится к значению $\psi$ в $\rho =\Omega ^{\Omega }\psi (\Omega ^{\Omega +1})$.
• Каноническая последовательность для $\psi (\Omega ^{\Omega ^{2}+\Omega 3})$ является: $\psi (0),\psi (\Omega ^{\Omega ^{2}+\Omega 2+\psi (0)}),\psi (\Omega ^{\Omega ^{2}+\Omega 2+\psi (\Omega ^{\Omega ^{2}+\Omega 2+\psi (0)})}),\ldots$

Вот примеры других случаев:

• Каноническая последовательность для $\omega ^{2}$ является: $0$, $\omega$, $\omega 2$, $\omega 3$...
• Каноническая последовательность для $\psi (\omega ^{\omega })$ является: $\psi (1)$, $\psi (\omega )$, $\psi (\omega ^{2})$, $\psi (\omega ^{3})$...
• Каноническая последовательность для $\psi (\Omega )^{\omega }$ является: $1$, $\psi (\Omega )$, $\psi (\Omega )^{2}$, $\psi (\Omega )^{3}$...
• Каноническая последовательность для $\psi (\Omega +1)$ является: $\psi (\Omega )$, $\psi (\Omega )^{\psi (\Omega )}$, $\psi (\Omega )^{\psi (\Omega )^{\psi (\Omega )}}$...
• Каноническая последовательность для $\psi (\Omega +\omega )$ является: $\psi (\Omega )$, $\psi (\Omega +1)$, $\psi (\Omega +2)$, $\psi (\Omega +3)$...
• Каноническая последовательность для $\psi (\Omega \omega )$ является: $\psi (0)$, $\psi (\Omega )$, $\psi (\Omega 2)$, $\psi (\Omega 3)$...
• Каноническая последовательность для $\psi (\Omega ^{\omega })$ является: $\psi (1)$, $\psi (\Omega )$, $\psi (\Omega ^{2})$, $\psi (\Omega ^{3})$...
• Каноническая последовательность для $\psi (\Omega ^{\psi (0)})$ является: $\psi (\Omega ^{\omega })$, $\psi (\Omega ^{\omega ^{\omega }})$, $\psi (\Omega ^{\omega ^{\omega ^{\omega }}})$... (это вытекает из фундаментальной последовательности для $\psi (0)$).
• Каноническая последовательность для $\psi (\Omega ^{\psi (\Omega )})$ является: $\psi (\Omega ^{\psi (0)})$, $\psi (\Omega ^{\psi (\psi (0))})$, $\psi (\Omega ^{\psi (\psi (\psi (0)))})$... (это вытекает из фундаментальной последовательности для $\psi (\Omega )$, что было указано выше).

Хотя порядковый номер Бахмана–Говарда $\psi (\varepsilon _{\Omega +1})$ сам по себе не имеет канонической записи, для него полезно также определить каноническую последовательность: это $\psi (\Omega )$, $\psi (\Omega ^{\Omega })$, $\psi (\Omega ^{\Omega ^{\Omega }})$...

Завершающий процесс

Начните с любого порядкового номера, меньшего или равного порядковому номеру Бахмана – Ховарда, и повторяйте следующий процесс, пока он не равен нулю:

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

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

1. может занять очень много времени, завершение
2. доказательство завершения может быть недостижимо для некоторых слабых систем арифметики.

Чтобы дать представление о том, на что похож этот процесс, вот несколько его этапов: начиная с $\psi (\Omega ^{\Omega ^{\omega }})$ (маленький порядковый номер Веблена), мы могли бы перейти к $\psi (\Omega ^{\Omega ^{3}})$, оттуда вниз $\psi (\Omega ^{\Omega ^{2}\psi (0)})$, затем $\psi (\Omega ^{\Omega ^{2}\omega ^{\omega }})$ затем $\psi (\Omega ^{\Omega ^{2}\omega ^{3}})$ затем $\psi (\Omega ^{\Omega ^{2}\omega ^{2}3})$ затем $\psi (\Omega ^{\Omega ^{2}(\omega ^{2}2+\omega )})$ затем $\psi (\Omega ^{\Omega ^{2}(\omega ^{2}2+1)})$ затем $\psi (\Omega ^{\Omega ^{2}\omega ^{2}2+\Omega \psi (\Omega ^{\Omega ^{2}\omega ^{2}2+\Omega \psi (0)})})$ затем $\psi (\Omega ^{\Omega ^{2}\omega ^{2}2+\Omega \psi (\Omega ^{\Omega ^{2}\omega ^{2}2+\Omega \omega ^{\omega ^{\omega }}})})$ и так далее. Кажется, что выражения становятся все более и более сложными, тогда как на самом деле порядковые номера всегда уменьшаются.

Что касается первого утверждения, то для любого порядкового номера можно было бы ввести $\alpha$ меньше или равно порядковому номеру Бахмана – Говарда $\psi (\varepsilon _{\Omega +1})$, целочисленная функция $f_{\alpha }(n)$ который подсчитывает количество шагов процесса до завершения, если всегда выбирать $n$'-й элемент канонической последовательности (эта функция удовлетворяет тождеству $f_{\alpha }(n)=f_{\alpha [n]}(n)+1$). Затем $f_{\alpha }$ может быть очень быстрорастущей функцией: уже $f_{\omega ^{\omega }}(n)$ по существу $n^{n}$, функция $f_{\psi (\Omega ^{\omega })}(n)$ сравнимо с функцией Аккермана $A(n,n)$, и $f_{\psi (\varepsilon _{\Omega +1})}(n)$ сравнима с функцией Гудштейна . Если вместо этого мы создадим функцию, удовлетворяющую тождеству $g_{\alpha }(n)=g_{\alpha [n]}(n+1)+1$, поэтому индекс функции увеличивается, то мы создаем гораздо более быстрорастущую функцию: $g_{\psi (0)}(n)$ уже сравнима с функцией Гудштейна, а $g_{\psi (\Omega ^{\Omega ^{\omega }\omega })}(n)$ сравнимо с функцией TREE .

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

Вариации на примере

Делаем функцию менее мощной

Поучительно (хотя и не совсем полезно) сделать $\psi$ менее мощный.

Если мы изменим определение $\psi$ выше, чтобы исключить возведение в степень из репертуара, из которого $C(\alpha )$ построено, то мы получаем $\psi (0)=\omega ^{\omega }$ (поскольку это наименьший порядковый номер, который нельзя составить из $0$, $1$ и $\omega$ используя только сложение и умножение), то $\psi (1)=\omega ^{\omega ^{2}}$ и аналогично $\psi (\omega )=\omega ^{\omega ^{\omega }}$, $\psi (\psi (0))=\omega ^{\omega ^{\omega ^{\omega }}}$ пока мы не придем к фиксированной точке, которая тогда будет нашей $\psi (\Omega )=\varepsilon _{0}$. Тогда у нас есть $\psi (\Omega +1)={\varepsilon _{0}}^{\omega }$ и так до тех пор, пока $\psi (\Omega 2)=\varepsilon _{1}$. Поскольку умножение $\Omega$разрешено, мы все еще можем сформировать $\psi (\Omega ^{2})=\varphi _{2}(0)$ и $\psi (\Omega ^{3})=\varphi _{3}(0)$ и так далее, но на этом наша конструкция заканчивается, поскольку нет возможности добраться до нее или выйти за ее пределы. $\Omega ^{\omega }$: таким образом, диапазон этой ослабленной системы обозначений составляет $\psi (\Omega ^{\omega })=\phi _{\omega }(0)$ (стоимость $\psi (\Omega ^{\omega })$ в нашей более слабой системе то же самое, что и в нашей исходной системе, за исключением того, что теперь мы не можем выйти за ее пределы). Это не доходит даже до ординала Фефермана-Шютте.

Если мы изменим определение $\psi$ еще немного, чтобы разрешить только сложение в качестве примитива для построения, мы получаем $\psi (0)=\omega ^{2}$ и $\psi (1)=\omega ^{3}$ и так до тех пор, пока $\psi (\psi (0))=\omega ^{\omega ^{2}}$ и все еще $\psi (\Omega )=\varepsilon _{0}$. На этот раз, $\psi (\Omega +1)=\varepsilon _{0}\omega$ и так до тех пор, пока $\psi (\Omega 2)=\varepsilon _{1}$ и аналогично $\psi (\Omega 3)=\varepsilon _{2}$. Но на этот раз мы не можем пойти дальше: поскольку мы можем только добавить $\Omega$Дальность действия нашей системы составляет $\psi (\Omega \omega )=\varepsilon _{\omega }=\varphi _{1}(\omega )$.

Если мы изменим определение еще больше, чтобы не допускать ничего, кроме пси, мы получим $\psi (0)=1$, $\psi (\psi (0))=2$, и так далее, пока $\psi (\omega )=\omega +1$, $\psi (\psi (\omega ))=\omega +2$, и $\psi (\Omega )=\omega 2$, и в этот момент мы не можем идти дальше, поскольку мы не можем ничего сделать с $\Omega$х. Таким образом, дальность действия этой системы составляет всего $\omega 2$.

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

Выход за пределы ординала Бахмана – Говарда

Мы знаем, что $\psi (\varepsilon _{\Omega +1})$ – ординал Бахмана–Говарда. Причина, почему $\psi (\varepsilon _{\Omega +1}+1)$ не больше, с нашими определениями, заключается в том, что нет обозначения для $\varepsilon _{\Omega +1}$ (оно не принадлежит $C(\alpha )$ для любого $\alpha$, это всегда его наименьшая верхняя граница). Можно попробовать добавить $\varepsilon$ функции (или функции Веблена для очень многих переменных) к разрешенным примитивам, помимо сложения, умножения и возведения в степень, но это не продвинет нас далеко. Чтобы создать более систематические обозначения для счетных ординалов, нам нужны более систематические обозначения для неисчисляемых ординалов: мы не можем использовать $\psi$ сама функция, поскольку она дает только счетные ординалы (например, $\psi (\Omega +1)$ является, $\varepsilon _{\varphi _{2}(0)+1}$, конечно нет $\varepsilon _{\Omega +1}$), поэтому идея состоит в том, чтобы имитировать его определение следующим образом:

Позволять $\psi _{1}(\alpha )$ — наименьший порядковый номер, который не может быть выражен из всех счетных порядковых номеров и $\Omega _{2}$ используя суммы, произведения, экспоненты и $\psi _{1}$ сама функция (к ранее построенным ординалам меньше $\alpha$).

Здесь, $\Omega _{2}$ новый порядковый номер, гарантированно превышающий все порядковые номера, которые будут построены с использованием $\psi _{1}$: опять позволяю $\Omega =\omega _{1}$ и $\Omega _{2}=\omega _{2}$ работает.

Например, $\psi _{1}(0)=\Omega$и вообще $\psi _{1}(\alpha )=\varepsilon _{\Omega +\alpha }$ для всех счетных ординалов и даже за их пределами ( $\psi _{1}(\Omega )=\psi _{1}(\psi _{1}(0))=\varepsilon _{\Omega 2}$ и $\psi _{1}(\psi _{1}(1))=\varepsilon _{\varepsilon _{\Omega +1}}$): это справедливо до первой фиксированной точки $\zeta _{\Omega +1}$ функции $\xi \mapsto \varepsilon _{\xi }$ вне $\Omega$, что является пределом $\psi _{1}(0)$, $\psi _{1}(\psi _{1}(0))$ и так далее. Помимо этого, у нас есть $\psi _{1}(\alpha )=\zeta _{\Omega +1}$ и это остается верным до тех пор, пока $\Omega _{2}$: точно так же, как и в случае с $\psi (\Omega )$, у нас есть $\psi _{1}(\Omega _{2})=\zeta _{\Omega +1}$ и $\psi _{1}(\Omega _{2}+1)=\varepsilon _{\zeta _{\Omega +1}+1}$.

The $\psi _{1}$ функция дает нам систему обозначений ( при условии, что мы можем каким-то образом записать все счетные ординалы!) для несчетных ординалов ниже $\psi _{1}(\varepsilon _{\Omega _{2}+1})$, что является пределом $\psi _{1}(\Omega _{2})$, $\psi _{1}({\Omega _{2}}^{\Omega _{2}})$ и так далее.

Теперь мы можем повторно ввести эти обозначения в оригинал. $\psi$ функция, измененная следующим образом:

$\psi (\alpha )$ наименьший порядковый номер, который нельзя выразить через $0$, $1$, $\omega$, $\Omega$ и $\Omega _{2}$ используя суммы, произведения, экспоненты, $\psi _{1}$ функция и $\psi$ сама функция (к ранее построенным ординалам меньше $\alpha$).

Эта модифицированная функция $\psi$ совпадает с предыдущим до (и включительно) $\psi (\psi _{1}(1))$ - который является порядковым номером Бахмана – Говарда. Но теперь мы можем выйти за рамки этого и $\psi (\psi _{1}(1)+1)$ является $\varepsilon _{\psi (\psi _{1}(1))+1}$ (следующий $\varepsilon$-число после порядкового номера Бахмана–Говарда). Мы сделали нашу систему вдвойне непредикативной: для создания обозначений счетных ординалов мы используем обозначения для определенных ординалов между $\Omega$ и $\Omega _{2}$ которые сами определяются с использованием определенных порядковых номеров, выходящих за рамки $\Omega _{2}$.

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

$\psi (\alpha )$ наименьший порядковый номер, который нельзя выразить через $0$, $1$, $\omega$, $\Omega$ и $\Omega _{2}$ используя суммы, произведения, экспоненты и $\psi _{1}$ и $\psi$ функции (к ранее построенным ординалам меньше $\alpha$).

т. е. разрешить использование $\psi _{1}$ только для аргументов меньше $\alpha$ сам. Используя это определение, мы должны написать $\psi (\Omega _{2})$ вместо $\psi (\psi _{1}(\Omega _{2}))$ (хотя оно все равно также равно $\psi (\psi _{1}(\Omega _{2}))=\psi (\zeta _{\Omega +1})$, конечно, но теперь оно постоянно до тех пор, пока $\Omega _{2}$). Это изменение несущественно, поскольку, интуитивно говоря, $\psi _{1}$ функция сворачивает именованные порядковые номера за пределы $\Omega _{2}$ ниже последнего, поэтому не имеет большого значения, $\psi$ вызывается непосредственно для порядковых номеров за пределами $\Omega _{2}$ или на их изображении $\psi _{1}$. Но это позволяет определить $\psi$ и $\psi _{1}$ путем одновременной (а не «нисходящей») индукции, и это важно, если мы хотим использовать бесконечное количество схлопывающих функций.

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

«Обычный» вариант

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

Следующее определение (по индукции по $\alpha$) полностью эквивалентна функции $\psi$ выше :

Позволять $C(\alpha ,\beta )$ быть набором порядковых номеров, сгенерированных, начиная с $0$, $1$, $\omega$, $\Omega$ и все ординалы меньше $\beta$ рекурсивно применяя следующие функции: порядковое сложение, умножение и возведение в степень, а также функцию $\psi \upharpoonright _{\alpha }$. Затем $\psi (\alpha )$ определяется как наименьший порядковый номер $\rho$ такой, что $C(\alpha ,\rho )\cap \Omega =\rho$.

(Это эквивалентно, потому что если $\sigma$ является наименьшим порядковым номером, не входящим в $C(\alpha ,0)$, именно так мы изначально определили $\psi (\alpha )$, то это также наименьший порядковый номер, не входящий в $C(\alpha ,0)=C(\alpha ,\sigma )$, а также описанные нами свойства $\psi$ подразумевают, что нет порядкового номера между $\sigma$ инклюзивный и $\Omega$ эксклюзив принадлежит $C(\alpha ,\sigma )$.)

Теперь мы можем внести изменения в определение, которое немного изменит его:

Позволять ${\tilde {C}}(\alpha ,\beta )$ быть набором порядковых номеров, сгенерированных, начиная с $0$, $1$, $\omega$, $\Omega$ и все ординалы меньше $\beta$ рекурсивно применяя следующие функции: порядковое сложение, умножение и возведение в степень, а также функцию ${\tilde {\psi }}\upharpoonright _{\alpha }$. Затем ${\tilde {\psi }}(\alpha )$ определяется как наименьший порядковый номер $\rho$ такой, что ${\tilde {C}}(\alpha ,\rho )\cap \Omega =\rho$ и $\alpha \in {\tilde {C}}(\alpha ,\rho )$.

Первые значения ${\tilde {\psi }}$ совпадают с таковыми $\psi$: а именно для всех $\alpha <\zeta _{0}$ где $\zeta _{0}=\varphi _{2}(0)$, у нас есть ${\tilde {\psi }}(\alpha )=\psi (\alpha )$ потому что дополнительный пункт $\alpha \in {\tilde {C}}(\alpha ,\rho )$ всегда остается доволен. Но на этом этапе функции начинают различаться: в то время как функция $\psi$ «застревает» в $\zeta _{0}$ для всех $\zeta _{0}\leq \alpha \leq \Omega$, функция ${\tilde {\psi }}$ удовлетворяет ${\tilde {\psi }}(\zeta _{0})=\varepsilon _{\zeta _{0}+1}$ потому что новое состояние $\alpha \in {\tilde {C}}(\alpha ,\rho )$ навязывает ${\tilde {\psi }}(\zeta _{0})>\zeta _{0}$. С другой стороны, у нас еще есть ${\tilde {\psi }}(\Omega )=\zeta _{0}$ (потому что $\Omega \in C(\alpha ,\rho )$ для всех $\rho$ поэтому дополнительное условие не играет роли). Обратите внимание, в частности, что ${\tilde {\psi }}$, в отличие от $\psi$, не является монотонным и не является непрерывным.

Несмотря на эти изменения, ${\tilde {\psi }}$ функция также определяет систему порядковых обозначений вплоть до ординала Бахмана – Говарда: обозначения и условия каноничности немного отличаются (например, $\psi (\Omega +1+\alpha )={\tilde {\psi }}({\tilde {\psi }}(\Omega )+\alpha )$ для всех $\alpha$ меньше обычного значения $\psi (\Omega 2)={\tilde {\psi }}(\Omega +1)$).

Другие подобные OCF

Арая ψ

Араи ψ- функция — это порядковая схлопывающая функция, введенная Тошиясу Араи (мужем Норико Х. Араи ) в его статье: Упрощенный порядковый анализ отражения первого порядка . $\psi _{\Omega }(\alpha )$ является схлопывающей функцией такой, что $\psi _{\Omega }(\alpha )<\Omega$, где $\Omega$ представляет собой первый неисчисляемый порядковый номер (его можно заменить порядковым номером Чёрча-Клин ценой дополнительных технических трудностей). На протяжении всей этой статьи ${\mathsf {KP\Pi _{N}}}$ представляет собой теорию множеств Крипке – Платека для ${\mathsf {\Pi _{N}}}$- отражающая вселенная, $\mathbb {K} _{N}$ это наименьший ${\mathsf {\Pi }}_{N-2}^{1}$- неописуемый кардинал (его можно заменить наименьшим ${\mathsf {\Pi }}_{N}$-отражение порядкового номера ценой дополнительных технических сложностей), $N$ фиксированное натуральное число $\geq 3$, и $\Omega _{0}=0$.

Предполагать ${\mathsf {KP\Pi _{N}}}\vdash \theta$ для ${\mathsf {\Sigma _{1}}}$ ( $\Omega$)-предложение ${\mathsf {\theta }}$. Тогда существует конечное $n$ такой, что для $\alpha =\psi _{\Omega }(\omega _{n}(\mathbb {K} _{N}+1))$, $L_{\alpha }\models \theta$. Также можно доказать, что ${\mathsf {KP\Pi _{N}}}$ доказывает, что каждый начальный отрезок $\{\alpha \in OT:\alpha <\psi _{\Omega }(\omega _{n}(\mathbb {K} _{N}+1))\};n=1,2,\ldots$ является вполне обоснованным и, следовательно, $\psi _{\Omega }(\varepsilon _{\mathbb {K} _{N}+1})$ является теоретико-доказательным ординалом ${\mathsf {KP\Pi _{N}}}$. Затем можно выполнить следующие преобразования:

• $\psi _{\Omega }(\varepsilon _{\Omega +1})=|{\mathsf {KP\omega }}|={\mathsf {BHO}}$, где $\Omega$ является либо наименее рекурсивно регулярным ординалом, либо наименее несчетным кардиналом, ${\mathsf {KP\omega }}$ — это теория множеств Крипке–Платека с бесконечностью и ${\mathsf {BHO}}$ – ординал Бахмана–Говарда .
• $\psi _{\Omega }(\Omega _{\omega })=|{\mathsf {\Pi _{1}^{1}-CA_{0}}}|={\mathsf {BO}}$, где $\Omega _{\omega }$ является либо наименьшим пределом допустимых ординалов, либо наименьшим пределом бесконечных кардиналов и ${\mathsf {BO}}$ является порядковым номером Бухгольца .
• $\psi _{\Omega }(\varepsilon _{\Omega _{\omega }+1})=|{\mathsf {KPl}}|={\mathsf {TFBO}}$, где $\Omega _{\omega }$ является либо наименьшим пределом допустимых ординалов, либо наименьшим пределом бесконечных кардиналов, ${\mathsf {KPl}}$ это КПи без схемы сбора и ${\mathsf {TFBO}}$ – ординал Такеути–Фефермана–Бухгольца .
• $\psi _{\Omega }(\varepsilon _{I+1})=|{\mathsf {KPi}}|$, где $I$ является либо наименее рекурсивно недоступным ординалом, либо наименее слабо недоступным кардиналом и ${\mathsf {KPi}}$ — это теория множеств Крипке–Платека с рекурсивно недоступной вселенной.

Бахмана ψ

Первый настоящий OCF, Бахманн. $\psi$ был изобретен Хайнцем Бахманом и несколько громоздок, поскольку зависит от фундаментальных последовательностей для всех предельных ординалов; и исходное определение сложно. Майкл Ратьен предложил «переделать» систему следующим образом:

• Позволять $\Omega$ представляют собой неисчисляемый ординал, например $\omega _{1}$;
• Затем определите $C^{\Omega }(\alpha ,\beta )$ как закрытие $\beta \cup \{0,\Omega \}$ в дополнение, $(\xi \rightarrow \omega ^{\xi })$ и $(\xi \rightarrow \psi _{\Omega }(\xi ))$ для $\xi <\alpha$.
• $\psi _{\Omega }(\alpha )$ — наименьший счетный ординал ρ такой, что $C^{\Omega }(\alpha ,\rho )\cap \Omega =\rho$

$\psi _{\Omega }(\varepsilon _{\Omega +1})$ — это ординал Бахмана–Ховарда, теоретико-доказательный ординал теории множеств Крипке–Платека с аксиомой бесконечности (КП).

Бухгольца ψ

Основная статья: пси-функции Бухгольца

Бухгольца $\psi$ представляет собой иерархию функций с одним аргументом $\psi _{\nu }:{\mathsf {On}}\rightarrow {\mathsf {On}}$, с $\psi _{\nu }(\alpha )$ иногда сокращается как $\psi _{\nu }\alpha$. Эта функция, вероятно, является наиболее известной из всех OCF. Определение такое:

• Определять $\Omega _{0}=1$ и $\Omega _{\nu }=\aleph _{\nu }$ для $\nu >0$.
• Позволять $P(\alpha )$ — множество различных членов в нормальной форме Кантора $\alpha$ (с каждым членом формы $\omega ^{\xi }$ для $\xi \in {\mathsf {On}}$, см. теорему Кантора о нормальной форме )
• $C_{\nu }^{0}(\alpha )=\Omega _{\nu }$
• $C_{\nu }^{n+1}(\alpha )=C_{\nu }^{n}(\alpha )\cup \{\gamma \mid P(\gamma )\subseteq C_{\nu }^{n}(\alpha )\}\cup \{\psi _{\nu }(\xi )\mid \xi \in \alpha \cap C_{\nu }^{n}(\alpha )\land \xi \in C_{u}(\xi )\land u\leq \omega \}$
• $C_{\nu }(\alpha )=\bigcup \limits _{n<\omega }C_{\nu }^{n}(\alpha )$
• $\psi _{\nu }(\alpha )=\min(\{\gamma \mid \gamma \notin C_{\nu }(\alpha )\})$

Пределом этой системы является $\psi _{0}(\varepsilon _{\Omega _{\omega }+1})$, ординал Такеути–Фефермана–Бухгольца .

Бухгольца Расширенный ψ

Основная статья: Пси-функции Бухгольца § Расширение

Эта OCF является усовершенствованным расширением метода Бухгольца. $\psi$ математик Денис Максудов. Предел этой системы, иногда называемый расширенным ординалом Бухгольца, гораздо больше и равен $\psi _{0}(\Omega _{\Omega _{\Omega _{\cdots }}})$ где $\Omega _{\Omega _{\Omega _{...}}}$ обозначает первую фиксированную точку омеги. Функция определяется следующим образом:

• Определять $\Omega _{0}=1$ и $\Omega _{\nu }=\aleph _{\nu }$ для $\nu >0$.
• $C_{\nu }^{0}(\alpha )=\{\beta \mid \beta <\Omega _{\nu }\}$
• $C_{\nu }^{n+1}(\alpha )=\{\beta +\gamma ,\psi _{\mu }(\eta )\mid \mu ,\beta ,\gamma ,\eta \in C_{\nu }^{n}(\alpha )\land \eta <\alpha \}$
• $C_{\nu }(\alpha )=\bigcup \limits _{n<\omega }C_{\nu }^{n}(\alpha )$
• $\psi _{\nu }(\alpha )=\min(\{\gamma \mid \gamma \notin C_{\nu }(\alpha )\})$

Мадора ψ

Эта OCF была такой же, как функция ψ , ранее использовавшаяся в этой статье; это более простая и эффективная версия ψ -функции Бухгольца, определенной Дэвидом Мадором. Ее использование в этой статье привело к широкому использованию функции.

• $C_{0}(\alpha )=\{0,1,\omega ,\Omega \}$
• $C_{n+1}(\alpha )=\{\gamma +\delta ,\gamma \delta ,\gamma ^{\delta },\psi (\eta )\mid \gamma ,\delta ,\eta \in C_{n}(\alpha );\eta <\alpha \}$
• $C(\alpha )=\bigcup \limits _{n<\omega }C_{n}(\alpha )$
• $\psi (\alpha )=\min(\{\beta \in \Omega \mid \beta \notin C(\alpha )\})$

Эту функцию использовал Крис Берд, который также изобрел следующую OCF.

θ птицы

Крис Берд разработал следующее сокращение для расширенной функции Веблена. $\varphi$:

• $\theta (\Omega ^{n-1}a_{n-1}+\cdots +\Omega ^{2}a_{2}+\Omega a_{1}+a_{0},b)=\varphi (a_{n-1},\ldots ,a_{2},a_{1},a_{0},b)$
• $\theta (\alpha ,0)$ сокращенно $\theta (\alpha )$

Эта функция определена только для аргументов меньше $\Omega ^{\omega }$, и его выходные данные ограничены небольшим порядковым номером Веблена.

Егера ψ

Егера ψ - это иерархия одноаргументных порядковых функций ψ _κ, индексированных несчетными регулярными кардиналами κ, меньшими, чем наименее слабый кардинал Мало M _0, введенный немецким математиком Герхардом Йегером в 1984 году. Она была разработана на основе подхода Бухгольца.

• Если $\kappa =I_{\alpha }(0)$ для некоторого α < κ , $\kappa ^{-}=0$.
• Если $\kappa =I_{\alpha }(\beta +1)$ для некоторых α , β < κ , $\kappa ^{-}=I_{\alpha }(\beta )$.
• $C_{\kappa }^{0}(\alpha )=\{\kappa ^{-}\}\cup \kappa ^{-}$
• Для каждого n конечного $C_{\kappa }^{n+1}(\alpha )\subset M_{0}$ представляет собой наименьшее множество, удовлетворяющее следующим условиям:
  • Сумма любого конечного числа ординалов в $C_{\kappa }^{n}(\alpha )\subset M_{0}$ принадлежит $C_{\kappa }^{n+1}(\alpha )\subset M_{0}$.
  • Для любого $\beta ,\gamma \in C_{\kappa }^{n}(\alpha )$, $\varphi _{\beta }(\gamma )\in C_{\kappa }^{n+1}(\alpha )$.
  • Для любого $\beta ,\gamma \in C_{\kappa }^{n}(\alpha )$, $I_{\beta }(\gamma )\in C_{\kappa }^{n+1}(\alpha )$.
  • Для любого порядкового γ и несчетного регулярного кардинала $\pi \in C_{\kappa }^{n}(\alpha )$, $\gamma <\pi <\kappa \Rightarrow \gamma \in C_{\kappa }^{n+1}(\alpha )$.
  • Для любого $\gamma \in \alpha \cap C_{\kappa }^{n}(\alpha )$ и несчетный правильный кардинал $\pi \in C_{\kappa }^{n}(\alpha )$, $\gamma \in C_{\pi }(\gamma )\Rightarrow \psi _{\pi }(\gamma )\in C_{\kappa }^{n+1}(\alpha )$.
• $C_{\kappa }(\alpha )=\bigcup \limits _{n<\omega }C_{\kappa }^{n}(\alpha )$
• $\psi _{\kappa }(\alpha )=\min(\{\xi \in \kappa \mid \xi \notin C_{\kappa }(\alpha )\})$

Егера Упрощенная ψ

Егера, Это сложное упрощение ψ созданное Денисом Максудовым. Ординал называется α -слабо недостижимым, если он несчетен, регулярен и является пределом γ -слабо недостижимых кардиналов при γ < α . Пусть I ( α , 0) — первый α-слабо недостижимый кардинал, I ( α , β + 1) — первый α -слабо недостижимый кардинал после I ( α , β ) и I ( α , β ) = $sup(\{I(\alpha ,\gamma )\mid \gamma <\beta \})$ для предела β . Ограничьте ρ и π несчетными регулярными ординалами вида I ( α , 0) или I ( α , β + 1). Затем,

• $C_{0}(\alpha ,\beta )=\beta \cup \{0\}$
• $C_{n+1}(\alpha ,\beta )=\{\gamma +\delta \mid \gamma ,\delta \in C_{n}(\alpha ,\beta )\}\cup \{I(\gamma ,\delta )\mid \gamma ,\delta \in C_{n}(\alpha ,\beta )\}\cup \{\psi _{\pi }(\gamma )\mid \pi ,\gamma ,\in C_{n}(\alpha ,\beta )\land \gamma <\alpha \}$
• $C(\alpha ,\beta )=\bigcup \limits _{n<\omega }C_{n}(\alpha ,\beta )$
• $\psi _{\pi }(\alpha )=\min(\{\beta <\pi \mid C(\alpha ,\beta )\cap \pi \subseteq \beta \})$

Ратьена Ψ

Основная статья: Пси-функция Ратьена

Функция Ратьена Ψ основана на наименее слабо компактном кардинале для создания больших счетных ординалов. Для слабо компактного кардинала K функции $M^{\alpha }$, $C(\alpha ,\pi )$, $\Xi (\alpha )$, и $\Psi _{\pi }^{\xi }(\alpha )$ определяются во взаимной рекурсии следующим образом:

• М ⁰ = $K\cap {\mathsf {Lim}}$, где Lim обозначает класс предельных ординалов.
• При α > 0 M ^а это набор $\{\pi <K\mid C(\alpha ,\pi )\cap K=\pi \land \forall \xi \in C(\alpha ,\pi )\cap \alpha ,M^{\xi }{\mathsf {}}$ стационарен в $\pi \land \alpha \in C(\alpha ,\pi )\}$
• $C(\alpha ,\beta )$ это закрытие $\beta \cup \{0,K\}$ в дополнение, $(\xi ,\eta )\rightarrow \varphi (\xi ,\eta )$, $\xi \rightarrow \Omega _{\xi }$ учитывая ξ < K, $\xi \rightarrow \Xi (\xi )$ учитывая ξ < α, и $(\xi ,\pi ,\delta )\rightarrow \Psi _{\pi }^{\xi }(\delta )$ данный $\xi \leq \delta <\alpha$.
• $\Xi (\alpha )=\min(M^{\alpha }\cup \{K\})$.
• Для $\xi \leq \alpha$, $\Psi _{\pi }^{\xi }(\alpha )=\min(\{\rho \in M^{\xi }\cap \pi :C(\alpha ,\rho )\cap \pi =\rho \land \pi ,\alpha \in C(\alpha ,\rho )\}\cup \{\pi \})$.

Сворачивание больших кардиналов

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

• Герхард Йегер и Вольфрам Полерс описал коллапс недоступного кардинала , чтобы описать теоретическую силу теории множеств Крипке-Платека, дополненную рекурсивной недоступностью класса ординалов ( KPi ), ​​что также эквивалентно с точки зрения теории доказательств к $\Delta _{2}^{1}$-понимание плюс вводная планка . Грубо говоря, этот коллапс можно получить, добавив $\alpha \mapsto \Omega _{\alpha }$ сама функция к списку конструкций, к которым $C(\cdot )$ применяется система складывания.
• Майкл Ратьен затем описал коллапс кардинала Мало, чтобы описать теоретическую силу теории множеств Крипке-Платека, дополненную рекурсивной малонесностью класса ординалов ( КПМ ).
• Ратьен позже описал коллапс слабо компактного кардинала для описания ординальной силы теории множеств Крипке – Платека, дополненной некоторыми принципами отражения (концентрируясь на случае $\Pi _{3}$-отражение). Грубо говоря, это происходит путем введения первого кардинала $\Xi (\alpha )$ который $\alpha$-гипер-Мало и добавление $\alpha \mapsto \Xi (\alpha )$ функция сама по себе разрушающейся системы.
• В статье 2015 года Тошьясу Араи создал порядковые схлопывающиеся функции. $\psi _{\pi }^{\vec {\xi }}$ для вектора порядковых номеров $\xi$, которые разрушаются $\Pi _{n}^{1}$- неописуемые кардиналы для $n>0$. Они используются для проведения порядкового анализа теории множеств Крипке – Платека, дополненной $\Pi _{n+2}$- принципы отражения.
• Ратьен исследовал крах еще более крупных кардиналов с конечной целью добиться порядкового анализа $\Pi _{2}^{1}$-понимание (которое с точки зрения теории доказательств эквивалентно дополнению Крипке–Платека $\Sigma _{1}$-разделение).

Ссылки

• Арай, Тошиясу (сентябрь 2020 г.). «Упрощенный порядковый анализ отражения первого порядка». Журнал символической логики . 85 (3): 1163–1185. arXiv : 1907.07611 . дои : 10.1017/jsl.2020.23 . S2CID   118940547 .
• Такеути, Гаиси (1967). «Доказательства непротиворечивости подсистем классического анализа». Анналы математики . 86 (2): 299–348. дои : 10.2307/1970691 . JSTOR   1970691 .
• Ягер, Герхард; Полерс, Вольфрам (1983). «Теоретико-доказательное исследование ( $\Delta _{2}^{1}$-CA)+(BI) и родственные системы». Баварская академия наук. Отчеты о заседаниях классов по математике и естествознанию . 1982 : 1–28.
• Бухгольц, Вильфрид (1986). «Новая система теоретико-доказательных порядковых функций» . Анналы чистой и прикладной логики . 32 : 195–207. дои : 10.1016/0168-0072(86)90052-7 .
• Ратьен, Майкл (1991). «Теоретико-доказательный анализ КПМ». Архив математической логики . 30 (5–6): 377–403. дои : 10.1007/BF01621475 . S2CID   9376863 .
• Ратьен, Майкл (1994). «Доказательство теории отражения» (PDF) . Анналы чистой и прикладной логики . 68 (2): 181–224. дои : 10.1016/0168-0072(94)90074-4 .
• Ратьен, Майкл (1995). «Последние достижения в порядковом анализе: $\Pi _{2}^{1}$-CA и родственные системы» . Бюллетень символической логики . 1 (4): 468–485. : 10.2307 /421132 . JSTOR   421132. . S2CID   10648711 doi
• Кале, Рейнхард (2002). «Математическая теория доказательства в свете порядкового анализа». Синтезируйте . 133 : 237–255. дои : 10.1023/А:1020892011851 . S2CID   45695465 .
• Ратьен, Майкл (2005). «Порядковый анализ устойчивости» . Архив математической логики . 44 : 1–62. CiteSeerX   10.1.1.15.9786 . дои : 10.1007/s00153-004-0226-2 . S2CID   2686302 .
• Ратьен, Майкл (август 2005 г.). «Теория доказательств: Часть III, Теория множеств Крипке – Платека» (PDF) . Архивировано из оригинала (PDF) 12 июня 2007 г. Проверено 17 апреля 2008 г. (слайды выступления, прозвучавшего в Фишбахау)