ヴェブレン関数

数学において、ヴェブレン関数は、オスワルド・ヴェブレンがヴェブレン（1908）で導入した正規関数（順序数から順序数への連続的 な厳密に増加な 関数）の階層です。 φ ₀が任意の正規関数である場合、任意の非ゼロの順序数αに対して、φ _αはβ < αに対してφ _βの共通の不動点を列挙する関数です。これらの関数はすべて正規です。

φ ₀ ( α )=ω ^αの特別なケースでは、 この関数族はヴェブレン階層として知られています。関数φ _1はε 関数と同じです: φ ₁ ( α )= ε _α。^[1]の場合。^{[2]このことと φ} _βが厳密に増加しているという事実から、順序付けが得られます: (および)または(および)または(および)のいずれかの場合に限ります。^[2]${\displaystyle \alpha <\beta \,,}$${\displaystyle \varphi _{\alpha }(\varphi _{\beta }(\gamma ))=\varphi _{\beta }(\gamma )}$${\displaystyle \varphi _{\alpha }(\beta )<\varphi _{\gamma }(\delta )}$${\displaystyle \alpha =\gamma }$${\displaystyle \beta <\delta }$${\displaystyle \alpha <\gamma }$${\displaystyle \beta <\varphi _{\gamma }(\delta )}$${\displaystyle \alpha >\gamma }$${\displaystyle \varphi _{\alpha }(\beta )<\delta }$

共終性ω を持つ順序数の基本列は、順序数を極限とする、厳密に増加する ω 列として区別されます。α とすべてのより小さな極限順序数の基本列があれば、 ω とαの間に明示的な構成的一対一関係を作成できます(つまり、選択公理を使用しない)。ここでは、順序数のヴェブレン階層の基本列について説明します。αの基本列によるnの像は、α [ n ]で示されます。

ヴェブレン階層に関連して使用されるカントール標準形のバリエーションは、すべての非ゼロ順序数αは、k >0が自然数であり、最初の項以降の各項が前の項以下であり、各項が最後の項に対して基本シーケンスを提供できる場合、その項をそのようなシーケンスに置き換えて、${\displaystyle \alpha =\varphi _{\beta _{1}}(\gamma _{1})+\varphi _{\beta _{2}}(\gamma _{2})+\cdots +\ヴァルファイ _{\beta _{k}}(\gamma _{k})}$${\displaystyle \varphi _{\beta _{m}}(\gamma _{m})\geq \varphi _{\beta _{m+1}}(\gamma _{m+1})\,, }$${\displaystyle \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) = αとなる順序数αを列挙します。 Γ ₀はFeferman–Schütte 順序数、つまりφ _α (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 )}$

を空の文字列、または をコンマで区切られた 1 つ以上のゼロからなる文字列とし、を空の文字列、または を含む をコンマで区切られた 1 つ以上の序数からなる文字列とします。2項関数はとの両方が空の文字列である場合に と記述できます。有限ヴェブレン関数は次のように定義されます。 ${\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 }$

たとえば、は関数 の - 番目の不動点、つまり です。次に は、その関数 の不動点、つまり関数 の を列挙します。そして、のすべての の不動点を列挙します。一般化されたヴェブレン関数の各インスタンスは、最後の非ゼロ変数で連続しています (つまり、1 つの変数が変化し、それ以降の変数がすべて常にゼロに保たれる場合)。 ${\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}}$は、1つ以上のコンマで区切られた序数で構成される文字列であり、各${\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)}$が後続順序数であり、が極限順序数である場合。${\displaystyle \gamma }$${\displaystyle \beta }$

より一般的には、ヴェブレンは、有限個を除いてすべてがゼロである限り、 φ は超限順序数列 α _{βに対しても定義できることを示した。そのような順序数列が非可算な}正規基数κ より小さいものから選択される場合、その列は κ ^κより小さい単一の順序数として符号化される可能性があることに注意してください (順序数の累乗)。つまり、 κ ^κから κ への関数 φ を定義していることになります。

定義は次のように与えられます: α をゼロで終わる(つまり、α ₀ =0となる)順序数の超限列(つまり、有限台を持つ順序関数)とし、α [γ@0] を最後の 0 が γ に置き換えられた同じ関数を表すものとします。そして、γ↦φ( α [γ@0]) は、すべての関数 ξ↦φ( β )の共通の不動点を列挙する関数として定義されます。ここで、 β は、 αの最小のインデックス付き非ゼロ値を減少させ、より小さいインデックス付きの値を不定値 ξ に置き換えることによって得られるすべてのシーケンスにわたります (つまり、β = α [ζ@ι ₀ ,ξ@ι] は、α _{ι 0がゼロでない最小のインデックス ι 0については、後者が何らかの値 ζ<α ι 0}に置き換えられ、何らかのより小さいインデックス ι<ι ₀については、値 α _ι =0 が ξ に置き換えられることを意味します)。

たとえば、α =(1@ω) が、ω で値が 1、それ以外では値が 0 である超限列を表す場合、φ(1@ω) は、有限個の最終零点を持つすべての関数 ξ↦φ(ξ,0,...,0) の最小の不動点です (これは、有限個の零点を持つ φ(1,0,...,0) の極限、つまり小さいヴェブレン順序数でもあります)。

αがφよりも大きい最小の順序数αを、 αに台がある任意の関数に適用した場合（つまり、超限多変数のヴェブレン関数を使用して「下から」到達できない関数に適用した場合）、これは「大きな」ヴェブレン順序数、または「偉大な」ヴェブレン数と呼ばれることがあります。^[3]

Massmann & Kwon (2023) では、ヴェブレン関数がさらに拡張され、次元ヴェブレンと呼ばれるやや技術的なシステムになりました。このシステムでは、固定点や行番号を取ることができるため、φ (1@(1,0)) などの式が有効になり (大きなヴェブレン順序数を表す)、多次元配列として視覚化されます。バッハマン-ハワード順序数より下の順序数はすべてこのシステムで表現できること、また大きなヴェブレン順序数より下の順序数の表現は元のシステムと見た目は同じであることが証明されました。

この関数はいくつかの重要な値を取ります:

• ${\displaystyle \varphi (1,0)=\varepsilon _{0}}$はペアノ算術の証明論的順序数 であり、カントール標準形およびより小さい順序数で表現できる順序数の限界です。
• ${\displaystyle \varphi (\omega ,0)}$、有限個の関数記号を持つ再帰的経路順序付けの順序型の境界、および原始再帰順序関数の下で閉じた最小の順序数。 ^{[4] [5]}
• フェファーマン・シュッテ順序数 は に等しい。^[6]${\displaystyle \Gamma _{0}}$${\displaystyle \varphi (1,0,0)}$
• 小さなヴェブレン順序数はに等しい。^[7]${\displaystyle \varphi {\begin{pmatrix}1\\\omega \end{pmatrix}}}$

• ヒルベルト・レヴィッツ『超限順序数とその表記法：初心者向け』解説記事（8 ページ、PostScript形式）
• ポーラーズ、ウォルフラム（1989）、証明理論、数学講義ノート、第1407巻、ベルリン：シュプリンガー出版社、doi：10.1007/978-3-540-46825-7、ISBN 978-3-540-51842-6、MR  1026933
• シュッテ、クルト (1977)、証明理論、Grundlehren der Mathematischen Wissenschaften、vol. 225、ベルリン-ニューヨーク: Springer-Verlag、pp. xii+299、ISBN 978-3-540-07911-8、MR  0505313
• 竹内ガイシ（1987）「証明理論」『論理学と数学の基礎研究』第81巻（第2版）、アムステルダム：ノースホランド出版社、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
• マスマン、ジェイド・シルヴィ、クォン、エイドリアン・ワン（2023年10月20日）、ヴェブレン関数の拡張、arXiv：2310.12832{{citation}}: CS1 maint: date and year (link)