ヴェブレン関数

Mathematical function on ordinals

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

ヴェブレン階層

φ ₀ ( α )=ω ^αの特別な場合において、 この関数族はヴェブレン階層として知られています。関数φ _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 +\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) = αとなる順序数αを列挙します。 Γ ₀は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]}\,.}$

一般化

有限個の変数

有限個の引数を持つヴェブレン関数 (有限ヴェブレン関数) を構築するには、2 項関数を上記のように定義します。 ${\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]

簡略化

以下は超限ヴェブレン関数の簡略化されたバージョンです。

これを修正し、すべての順序数のクラスから自身への（有限台を持つ）関数を入力として用いるようにします。このような関数は、以下のように、（真のクラスではなく）集合によって符号化できます。

• 集合は順序付けられた順序数のペアの有限（空の可能性もある）集合である。
• このような順序付きペアの最初のメンバーとして順序数が複数回出現しない、つまりエンコードされた関数は単一値である。
• 順序付きペアの 2 番目の位置の序数は 0 になることはありません。つまり、順序付きペアが存在しない場合に 0 の値が示されます。
• セットを関数として使用する場合、入力序数は順序付きペアの最初のメンバーと比較され、一致する場合は 2 番目のメンバーが値として返されます。それ以外の場合は値は 0 になります。

このような集合にsとt を使用し、順序数に α、β、γ、δ を使用すると、定義は次のようになります。

${\displaystyle s<t\iff s(\alpha )<t(\alpha ){\text{ where }}\alpha =\max\{0,\beta \vert s(\beta )\neq t(\beta )\}}$;

${\displaystyle D_{\phi }(s)=\max\{0,\alpha ,\beta \vert \langle \alpha ,\beta \rangle \in s\}}$;

${\displaystyle \phi (s)=\inf \,\{\gamma \,\vert \,D_{\phi }(s)\leq \gamma \land 0<\gamma \land \forall \delta <\gamma (\delta +\delta <\gamma )\land \forall t<s(D_{\phi }(t)<\gamma \implies \phi (t)<\gamma )\}}$γはωの累乗であることに注意してください。

このシステムの表記法は、ゼロ項関数 0 で始まり、2 項関数の加算 + を使用して、超限ヴェブレン関数 φ をこれらのセットコード化関数に適用することで得られる ω の累乗を結合します。

${\displaystyle 1=\omega ^{0}=\phi (\{\})}$;

${\displaystyle 2=1+1}$;

${\displaystyle \omega =\omega ^{1}=\phi (\{\langle 0,1\rangle \})}$;

${\displaystyle \omega ^{2}=\phi (\{\langle 0,2\rangle \})}$;

${\displaystyle \epsilon _{0}=\phi (\{\langle 1,1\rangle \})=\phi (\{\langle 0,\epsilon _{0}\rangle \})}$固定点。

${\displaystyle \epsilon _{1}=\phi (\{\langle 1,1\rangle ,\langle 0,1\rangle \})}$;

${\displaystyle \Gamma _{0}=\phi (\{\langle 2,1\rangle \})}$;

${\displaystyle \Gamma _{1}=\phi (\{\langle 2,1\rangle ,\langle 0,1\rangle \})}$;

${\displaystyle SVO=\phi (\{\langle \omega ,1\rangle \})=\phi (\{\langle 0,SVO\rangle \})}$小さなヴェブレン順序数はイプシロン数です。

${\displaystyle SVO\cdot 2=SVO+SVO}$;

${\displaystyle SVO^{2}=\phi (\{\langle 0,SVO\cdot 2\rangle \})}$。

などなど。

φ はある値を何回とることができますか？その値は常に ω の累乗です。

${\displaystyle \omega ^{0}=1=\phi (\{\});0<\alpha \implies \omega ^{\alpha }=\phi (\{\langle 0,\alpha \rangle \})}$。

したがって、ωのべき乗は常に少なくとも1回はφの値を持ちます。イプシロン数はその不動点であるため、常に少なくとも2回はφの値を持ちます。順序数の中には、φの値が無限に多く含まれるものもあります。例えば、Ωは無数回だけ値を持ちます。

${\displaystyle D_{\phi }(s)<\phi (s)\land s<t\implies \phi (t)\neq \phi (s)}$。

したがって、D _φ < φ の場合、それは φ がその値をとることができる最後の時です。したがって、D _φ = φ は、複数回値をとる順序数では標準です。D _{φ > φ}は決して起こりません。しかし

${\displaystyle \not \exists s(D_{\phi }(s)<\Omega =\phi (s))}$

他にも多くの順序数があり、それらはすべて非常に強い極限です。

φ ( s )の値を生成するためのsの好ましい形は、D _φ ( s ) < φ ( s )となるものである。順序定理は以下の通りである。

${\displaystyle D_{\phi }(s)<\phi (s)\land D_{\phi }(t)<\phi (t)\implies (\phi (t)<\phi (s)\iff (t<s\land D_{\phi }(t)<\phi (s))\lor (s<t\land \phi (t)\leq D_{\phi }(s)))}$;

${\displaystyle t<s\implies ((D_{\phi }(t)<\phi (s)\implies \phi (t)<\phi (s))\land (D_{\phi }(t)=\phi (s)\implies \phi (t)=\phi (s))\land (D_{\phi }(t)>\phi (s)\implies \phi (t)>\phi (s)))}$;

${\displaystyle 0<\phi (s)}$;

${\displaystyle \alpha +\beta <\phi (s)\iff \alpha <\phi (s)\land \beta <\phi (s)}$。

α が優先形式を持たない順序数である場合、次のようになります。

${\displaystyle D_{\phi }(s)<\alpha \implies \phi (s)<\alpha }$;

${\displaystyle \phi (\{\langle \alpha ,1\rangle \})=\alpha }$;

${\displaystyle \{\langle \alpha ,1\rangle \}<s\implies \alpha <\phi (s)}$;

${\displaystyle D_{\phi }(s)<\alpha \land \gamma <\min\{\alpha ,\beta \,\vert \,\langle \beta ,\delta \rangle \in s\}\implies \phi (s\cup \{\langle \gamma ,\alpha \rangle \})=\alpha }$;

${\displaystyle t\neq \{\}\land \max\{0,\beta \,\vert \,\langle \beta ,\delta \rangle \in t\}<\gamma <\min\{\gamma +1,\beta \,\vert \,\langle \beta ,\delta \rangle \in s\}\implies \alpha <\phi (s\cup \{\langle \gamma ,\alpha \rangle \}\cup t)}$;

優先形式を持たないイプシロン数の順序は、それらのイプシロン数がどのように指定されるかによって決まります。

さらなる拡張

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版), アムステルダム: 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
• マスマン、ジェイド・シルヴィ；クォン、エイドリアン・ワン（2023年10月20日）「ヴェブレン関数の拡張」arXiv：2310.12832

引用

1. スティーブン・G・シンプソン著『二次算術のサブシステム』（2009年、387ページ）
2. M. Rathjen, 弱マーロ基数に基づく序数表記法 (1990, p.251). 2022年8月16日にアクセス。
3. M. Rathjen、「The Art of Ordinal Analysis」（2006 年）、2006 年国際数学者会議会議録に掲載。
4. N. ダーショウィッツ、M. 岡田、「項書き換え理論の証明理論的手法」（1988年）。p.105
5. Avigad, Jeremy (2001年5月23日). 「順序記法の再帰を用いた許容集合論の順序解析」(PDF) . Journal of Mathematical Logic . 2 : 91--112. doi :10.1142/s0219061302000126.
6. D. マドール、「A Zoo of Ordinals」 (2017). 2022 年 11 月 2 日にアクセス。
7. ランツィ、フロリアン、ストラーム、トーマス (2019). 「小さなヴェブレン順序数のための柔軟な型システム」(PDF) .数理論理学アーカイブ. 58 ( 5–6 ): 711–751 . doi :10.1007/s00153-019-00658-x. S2CID  253675808.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Veblen_function&oldid=1325008757"