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

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

Иерархия Веблена [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

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

Функция Γ [ править ]

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

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

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

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

Обобщения [ править ]

Конечное количество переменных [ править ]

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

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

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

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

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

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

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

где

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

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

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

• ${\displaystyle (\varphi (s_{1})+\varphi (s_{2})+\cdots +\varphi (s_{k}))[n]=\varphi (s_{1})+\varphi (s_{2})+\cdots +\varphi (s_{k})[n]}$,
• ${\displaystyle \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.}$,
• ${\displaystyle \varphi (s,\beta ,z,\gamma )[0]=0}$и если и является порядковым номером-преемником,${\displaystyle \varphi (s,\beta ,z,\gamma )[n+1]=\varphi (s,\beta -1,\varphi (s,\beta ,z,\gamma )[n],z)}$${\displaystyle \gamma =0}$${\displaystyle \beta }$
• ${\displaystyle \varphi (s,\beta ,z,\gamma )[0]=\varphi (s,\beta ,z,\gamma -1)+1}$а если и являются порядковыми номерами-преемниками,${\displaystyle \varphi (s,\beta ,z,\gamma )[n+1]=\varphi (s,\beta -1,\varphi (s,\beta ,z,\gamma )[n],z)}$${\displaystyle \gamma }$${\displaystyle \beta }$
• ${\displaystyle \varphi (s,\beta ,z,\gamma )[n]=\varphi (s,\beta ,z,\gamma [n])}$если - предельный порядковый номер,${\displaystyle \gamma }$
• ${\displaystyle \varphi (s,\beta ,z,\gamma )[n]=\varphi (s,\beta [n],z,\gamma )}$если и - предельный порядковый номер,${\displaystyle \gamma =0}$${\displaystyle \beta }$
• ${\displaystyle \varphi (s,\beta ,z,\gamma )[n]=\varphi (s,\beta [n],\varphi (s,\beta ,z,\gamma -1)+1,z)}$if - порядковый номер-преемник и предельный порядковый номер.${\displaystyle \gamma }$${\displaystyle \beta }$

Бесконечно много переменных [ править ]

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

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

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

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

Ссылки [ править ]

• Гильберт Левитц, Трансфинитные порядковые числа и их обозначения: для непосвященных , пояснительная статья (8 страниц, в PostScript )
• Pohlers, Вольфрам (1989), теория доказательств , конспект лекций по математике, 1407 , Берлин: Springer-Verlag, doi : 10.1007 / 978-3-540-46825-7 , ISBN 978-3-540-51842-6, MR  1026933
• Шютте, Курт (1977), Теория доказательств , Grundlehren der Mathematischen Wissenschaften, 225 , Берлин-Нью-Йорк: Springer-Verlag, стр. Xii + 299, ISBN 978-3-540-07911-8, Руководство по ремонту  0505313
• Такеути, Гайси (1987), Теория доказательств , Исследования в области логики и основ математики, 81 (второе издание), Амстердам: North-Holland Publishing Co., ISBN 978-0-444-87943-1, MR  0882549
• Сморинский, C. (1982), "Разновидности древесного опыта", Матем. Интеллидженсер , 4 (4): 182-189, DOI : 10.1007 / BF03023553 содержит неформальное описание иерархии Веблена.
• Веблен, Освальд (1908), "Непрерывные возрастающие функции конечных и трансфинитов", Труды Американского математического общества , 9 (3): 280-292, DOI : 10,2307 / 1988605 , JSTOR  1988605
• Миллер, Ларри W. (1976), "Нормальные функции и конструктивные Порядковые нотации", журнал символической логики , 41 (2): 439-459, DOI : 10,2307 / 2272243 , JSTOR  2272243