Функция Веблена

В математике функции Веблена — это иерархия нормальных функций ( непрерывных строго возрастающих функций от ординалов к ординалам), введенная Освальдом Вебленом в работе Веблена (1908) . Если φ ₀ — любая нормальная функция, то для любого ненулевого ординала α φ _α — это функция, перечисляющая общие неподвижные точки φ _β при β<α. Все эти функции являются нормальными.

Иерархия Веблена

В частном случае, когда φ ₀ (α)=ω ^а это семейство функций известно как иерархия Веблена . Функция φ ₁ аналогична функции ε : φ ₁ (α) = ε _α . Если $\alpha <\beta \,,$ затем $\varphi _{\alpha }(\varphi _{\beta }(\gamma ))=\varphi _{\beta }(\gamma )$. Из этого, а также из того факта, что φ _β строго возрастает, мы получаем порядок: $\varphi _{\alpha }(\beta )<\varphi _{\gamma }(\delta )$ тогда и только тогда, когда либо ( $\alpha =\gamma$ и $\beta <\delta$) или ( $\alpha <\gamma$ и $\beta <\varphi _{\gamma }(\delta )$) или ( $\alpha >\gamma$ и $\varphi _{\alpha }(\beta )<\delta$).

Фундаментальные последовательности иерархии Веблена

Фундаментальная последовательность для ординала с конфинальностью ω — это выделенная строго возрастающая ω-последовательность, имеющая своим пределом ординал. Если у вас есть фундаментальные последовательности для α и всех меньших предельных ординалов, то можно создать явную конструктивную биекцию между ω и α (т. е. не использовать выбранную аксиому). Здесь мы опишем фундаментальные последовательности иерархии ординалов Веблена. Образ n под фундаментальной последовательностью для α будет обозначаться α[ n ].

Вариант нормальной формы Кантора, используемый в связи с иерархией Веблена, таков: каждое ненулевое порядковое число α можно однозначно записать как $\alpha =\varphi _{\beta _{1}}(\gamma _{1})+\varphi _{\beta _{2}}(\gamma _{2})+\cdots +\varphi _{\beta _{k}}(\gamma _{k})$, где k >0 — натуральное число и каждый член после первого меньше или равен предыдущему, $\varphi _{\beta _{m}}(\gamma _{m})\geq \varphi _{\beta _{m+1}}(\gamma _{m+1})\,,$ и каждый $\gamma _{m}<\varphi _{\beta _{m}}(\gamma _{m})\,.$ Если для последнего члена можно указать фундаментальную последовательность, то этот член можно заменить такой последовательностью, чтобы получить $\alpha [n]=\varphi _{\beta _{1}}(\gamma _{1})+\cdots +\varphi _{\beta _{k-1}}(\gamma _{k-1})+(\varphi _{\beta _{k}}(\gamma _{k})[n])\,.$

Для любого β, если γ является пределом с $\gamma <\varphi _{\beta }(\gamma )\,,$ тогда пусть $\varphi _{\beta }(\gamma )[n]=\varphi _{\beta }(\gamma [n])\,.$

Такая последовательность не может быть предусмотрена для $\varphi _{0}(0)$ = о ⁰ = 1, поскольку он не имеет конфинальности ω.

Для $\varphi _{0}(\gamma +1)=\omega ^{\gamma +1}=\omega ^{\gamma }\cdot \omega \,,$ мы выбираем $\varphi _{0}(\gamma +1)[n]=\varphi _{0}(\gamma )\cdot n=\omega ^{\gamma }\cdot n\,.$

Для $\varphi _{\beta +1}(0)\,,$ мы используем $\varphi _{\beta +1}(0)[0]=0$ и $\varphi _{\beta +1}(0)[n+1]=\varphi _{\beta }(\varphi _{\beta +1}(0)[n])\,,$ т.е. 0, $\varphi _{\beta }(0)$, $\varphi _{\beta }(\varphi _{\beta }(0))$, и т. д..

Для $\varphi _{\beta +1}(\gamma +1)$, мы используем $\varphi _{\beta +1}(\gamma +1)[0]=\varphi _{\beta +1}(\gamma )+1$ и $\varphi _{\beta +1}(\gamma +1)[n+1]=\varphi _{\beta }(\varphi _{\beta +1}(\gamma +1)[n])\,.$

Теперь предположим, что β — предел:

Если $\beta <\varphi _{\beta }(0)$, тогда пусть $\varphi _{\beta }(0)[n]=\varphi _{\beta [n]}(0)\,.$

Для $\varphi _{\beta }(\gamma +1)$, использовать $\varphi _{\beta }(\gamma +1)[n]=\varphi _{\beta [n]}(\varphi _{\beta }(\gamma )+1)\,.$

В противном случае порядковый номер нельзя описать через меньшие порядковые числа, используя $\varphi$ и эта схема к нему не применима.

Г-функция

Функция Γ перечисляет ординалы α такие, что φ _α (0) = α. Γ ₀ — ординал Фефермана–Шютте , т. е. это наименьшее α такое, что φ _α (0) = α.

Для Γ ₀ можно выбрать фундаментальную последовательность $\Gamma _{0}[0]=0$ и $\Gamma _{0}[n+1]=\varphi _{\Gamma _{0}[n]}(0)\,.$

Для Γ _β+1 пусть $\Gamma _{\beta +1}[0]=\Gamma _{\beta }+1$ и $\Gamma _{\beta +1}[n+1]=\varphi _{\Gamma _{\beta +1}[n]}(0)\,.$

Для Γ _β где $\beta <\Gamma _{\beta }$ это предел, пусть $\Gamma _{\beta }[n]=\Gamma _{\beta [n]}\,.$

Обобщения

Конечное число переменных

Чтобы построить функцию Веблена конечного числа аргументов (финитарную функцию Веблена), пусть двоичная функция $\varphi (\alpha ,\gamma )$ быть $\varphi _{\alpha }(\gamma )$ как определено выше.

Позволять $z$ быть пустой строкой или строкой, состоящей из одного или нескольких нулей, разделенных запятыми $0,0,...,0$ и $s$ быть пустой строкой или строкой, состоящей из одного или нескольких порядковых номеров, разделенных запятыми $\alpha _{1},\alpha _{2},...,\alpha _{n}$ с $\alpha _{1}>0$. Бинарная функция $\varphi (\beta ,\gamma )$ можно записать как $\varphi (s,\beta ,z,\gamma )$ где оба $s$ и $z$ являются пустыми строками.Финитарные функции Веблена определяются следующим образом:

• $\varphi (\gamma )=\omega ^{\gamma }$
• $\varphi (z,s,\gamma )=\varphi (s,\gamma )$
• если $\beta >0$, затем $\varphi (s,\beta ,z,\gamma )$ обозначает $(1+\gamma )$-я общая неподвижная точка функций $\xi \mapsto \varphi (s,\delta ,\xi ,z)$ для каждого $\delta <\beta$

Например, $\varphi (1,0,\gamma )$ это $(1+\gamma )$-я неподвижная точка функций $\xi \mapsto \varphi (\xi ,0)$, а именно $\Gamma _{\gamma }$; затем $\varphi (1,1,\gamma )$ перечисляет неподвижные точки этой функции, т. е. $\xi \mapsto \Gamma _{\xi }$ функция; и $\varphi (2,0,\gamma )$ перечисляет неподвижные точки всех $\xi \mapsto \varphi (1,\xi ,0)$. Каждый экземпляр обобщенных функций Веблена непрерывен по последней ненулевой переменной (т. е. если одна переменная изменяется, а все последующие переменные постоянно поддерживаются равными нулю).

Порядковый номер $\varphi (1,0,0,0)$ иногда называют порядковым номером Аккермана . Предел $\varphi (1,0,...,0)$ где количество нулей колеблется в пределах ω, иногда называют «маленьким» порядковым номером Веблена .

Каждый ненулевой порядковый номер $\alpha$ меньше малого ординала Веблена (SVO) может быть однозначно записано в нормальной форме для финитной функции Веблена:

$\alpha =\varphi (s_{1})+\varphi (s_{2})+\cdots +\varphi (s_{k})$

где

• $k$ является положительным целым числом
• $\varphi (s_{1})\geq \varphi (s_{2})\geq \cdots \geq \varphi (s_{k})$
• $s_{m}$ строка, состоящая из одного или нескольких порядковых номеров, разделенных запятыми $\alpha _{m,1},\alpha _{m,2},...,\alpha _{m,n_{m}}$ где $\alpha _{m,1}>0$ и каждый $\alpha _{m,i}<\varphi (s_{m})$

Фундаментальные последовательности для предельных ординалов финитной функции Веблена

Для предельных ординалов $\alpha <SVO$, записанная в нормальной форме для финитной функции Веблена:

• $(\varphi (s_{1})+\varphi (s_{2})+\cdots +\varphi (s_{k}))[n]=\varphi (s_{1})+\varphi (s_{2})+\cdots +\varphi (s_{k})[n]$,
• $\varphi (\gamma )[n]=\left\{{\begin{array}{lcr}n\quad {\text{if}}\quad \gamma =1\\\varphi (\gamma -1)\cdot n\quad {\text{if}}\quad \gamma \quad {\text{is a successor ordinal}}\\\varphi (\gamma [n])\quad {\text{if}}\quad \gamma \quad {\text{is a limit ordinal}}\\\end{array}}\right.$,
• $\varphi (s,\beta ,z,\gamma )[0]=0$ и $\varphi (s,\beta ,z,\gamma )[n+1]=\varphi (s,\beta -1,\varphi (s,\beta ,z,\gamma )[n],z)$ если $\gamma =0$ и $\beta$ является порядковым номером преемника,
• $\varphi (s,\beta ,z,\gamma )[0]=\varphi (s,\beta ,z,\gamma -1)+1$ и $\varphi (s,\beta ,z,\gamma )[n+1]=\varphi (s,\beta -1,\varphi (s,\beta ,z,\gamma )[n],z)$ если $\gamma$ и $\beta$ являются порядковыми номерами-преемниками,
• $\varphi (s,\beta ,z,\gamma )[n]=\varphi (s,\beta ,z,\gamma [n])$ если $\gamma$ является предельным ординалом,
• $\varphi (s,\beta ,z,\gamma )[n]=\varphi (s,\beta [n],z,\gamma )$ если $\gamma =0$ и $\beta$ является предельным ординалом,
• $\varphi (s,\beta ,z,\gamma )[n]=\varphi (s,\beta [n],\varphi (s,\beta ,z,\gamma -1)+1,z)$ если $\gamma$ является порядковым номером преемника и $\beta$ является предельным ординалом.

Трансфинитно много переменных

В более общем смысле Веблен показал, что φ можно определить даже для трансфинитной последовательности ординалов α _β , при условии, что все из них, кроме конечного числа, равны нулю. Обратите внимание, что если такая последовательность ординалов выбрана из тех, которые меньше несчетного регулярного кардинала κ, то последовательность может быть закодирована как одиночный ординал меньше κ. ^Мистер (порядковое возведение в степень). Итак, мы определяем функцию φ по κ ^Мистер в κ.

Определение можно дать следующим образом: пусть α — трансфинитная последовательность ординалов (т. е. порядковая функция с конечным носителем) , оканчивающаяся нулем (т. е. такая, что α ₀ =0), и пусть α [γ@0] обозначает та же функция, в которой последний 0 заменен на γ. Тогда γ↦φ( α [γ@0]) определяется как функция, перечисляющая общие неподвижные точки всех функций ξ↦φ( β ), где β пробегает все последовательности, полученные путем уменьшения ненулевого значения α с наименьшим индексом. и замена некоторого значения с меньшим индексом на неопределенное ξ (т. е. β = α [ζ@ι ₀ ,ξ@ι] означает, что для наименьшего индекса ι ₀ такого, что α _{ι 0} не равно нулю, последний был заменен некоторым значением ζ<α _{ι 0} и что для некоторого меньшего индекса ι<ι ₀ значение α _ι =0 было заменено на ξ).

Например, если α =(1@ω) обозначает трансфинитную последовательность со значением 1 в точке ω и 0 всюду, то φ(1@ω) — наименьшая неподвижная точка из всех функций ξ↦φ(ξ,0,. ...,0) с конечным числом конечных нулей (это также предел φ(1,0,...,0) с конечным числом нулей, малый ординал Веблена).

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

Дальнейшие расширения

В Massmann & Kwon (2023) функция Веблена была расширена до несколько технической системы, известной как размерная система Веблена . При этом можно использовать фиксированные точки или номера строк, что означает допустимость таких выражений, как φ(1@(1,0)) (представляющих большой порядковый номер Веблена), визуализируемых как многомерные массивы. Было доказано, что все ординалы ниже ординала Бахмана – Ховарда могут быть представлены в этой системе и что представления для всех ординалов ниже большого ординала Веблена были эстетически такими же, как в исходной системе.

Ценности

Функция принимает несколько важных значений:

• $\varphi (1,0)=\varepsilon _{0}$ - это теоретико -доказательный ординал арифметики Пеано и предел того, какие ординалы могут быть представлены в терминах нормальной формы Кантора и меньших ординалов.
• $\varphi (\omega ,0)$, граница типов порядка рекурсивных упорядочений путей с конечным числом функциональных символов и наименьший порядковый номер, замкнутый относительно примитивно-рекурсивных порядковых функций.
• Порядковый номер Фефермана -Шютте $\Gamma _{0}$ равно $\varphi (1,0,0)$.
• Малый ординал Веблена равен $\varphi {\begin{pmatrix}1\\\omega \end{pmatrix}}$.

Ссылки

• Гильберт Левитц, Трансфинитные ординалы и их обозначения: для непосвященных , пояснительная статья (8 страниц, в PostScript )
• Полерс, Вольфрам (1989), Теория доказательств , Конспекты лекций по математике, том. 1407, Берлин: Springer-Verlag, номер домена : 10.1007/978-3-540-46825-7 , ISBN.  978-3-540-51842-6 , МР   1026933
• Шютте, Курт (1977), Теория доказательств , Основы математических наук, том. 225, Берлин-Нью-Йорк: Springer-Verlag, стр. xii+299, ISBN.  978-3-540-07911-8 , МР   0505313
• Такеути, Гаиси (1987), Теория доказательств , Исследования по логике и основам математики, том. 81 (второе изд.), Амстердам: North-Holland Publishing Co., ISBN  978-0-444-87943-1 , МР   0882549
• Сморинский, К. (1982), «Разновидности древесного опыта», Math. Intelligencer , 4 (4): 182–189, doi : 10.1007/BF03023553 содержит неформальное описание иерархии Веблена.
• Веблен, Освальд (1908), «Непрерывно возрастающие функции конечных и трансфинитных ординалов», Труды Американского математического общества , 9 (3): 280–292, doi : 10.2307/1988605 , JSTOR   1988605
• Миллер, Ларри В. (1976), «Нормальные функции и конструктивные порядковые обозначения», Журнал символической логики , 41 (2): 439–459, doi : 10.2307/2272243 , JSTOR   2272243
• Массманн, Джейд Сильви; Квон, Адриан Ван (20 октября 2023 г.), Расширение функции Веблена , arXiv : 2310.12832 {{citation}}: CS1 maint: дата и год ( ссылка )