順序表記

この方法で続けることもできますが、そうすると関数の数が無限になってしまいます。そこで、代わりに単項関数を二項関数に統合してみましょう。超限再帰により、${\displaystyle \alpha }$超限再帰を使用できる${\displaystyle \beta }$定義する${\displaystyle \xi (\alpha ,\beta )}$最小の序数となる${\displaystyle \gamma }$そのため${\displaystyle \alpha <\gamma }$そして${\displaystyle \beta <\gamma }$そして${\displaystyle \gamma }$は値ではありません${\displaystyle \xi }$より小さいもの${\displaystyle \alpha }$または同じ${\displaystyle \alpha }$より小さい${\displaystyle \beta }$。

したがって、定義する${\displaystyle \xi }$表記法は以下のとおりです。

• 「${\displaystyle 0}$「は${\displaystyle \xi }$ゼロを表す表記法。
• 「A」と「B」が置き換えられた場合${\displaystyle \xi }$-表記法${\displaystyle \alpha }$そして${\displaystyle \beta }$「ξAB」では、結果は${\displaystyle \xi }$-表記法${\displaystyle \xi (\alpha ,\beta )}$。
• 他にはない${\displaystyle \xi }$-表記法。

機能${\displaystyle \xi }$はすべての順序数のペアに対して定義され、1対1です。常に引数よりも大きな値を返し、その範囲は0とイプシロン数以外のすべての順序数です。

1つは${\displaystyle \xi (\alpha ,\beta )<\xi (\gamma ,\delta )}$どちらかの場合

• ${\displaystyle \alpha =\gamma }$そして${\displaystyle \beta <\delta }$、 または
• ${\displaystyle \alpha <\gamma }$そして${\displaystyle \beta <\xi (\gamma ,\delta )}$、 または
• ${\displaystyle \alpha >\gamma }$そして${\displaystyle \xi (\alpha ,\beta )\leq \delta }$。

この定義に基づくと、最初のいくつかのξ表記は次のようになります。

0 の場合は「0」。1 の場合は「ξ00」。ξ(0,1)=2 の場合は「ξ0ξ00」。 ξ(1,0)=ωの場合は「ξξ000」。 3 の場合は「ξ0ξ0ξ00」。 ω+1 の場合は「ξ0ξξ000」。 ω・2なら「ξξ00ξ00」。 ω ^ωの場合は「ξξ0ξ000」。 「ξξξ0000」${\displaystyle \omega ^{\omega ^{\omega }}.}$

一般的に、${\displaystyle \xi (0,\beta )=\beta +1}$。特別な状況に応じて k = 0 または 1 または 2の場合、ξ(1+α,β) = ω ^{ω α} ·(β+k) となります: α がイプシロン数で β が有限の場合、k = 2。それ以外の場合、β が ω ^{ω α+1}に有限数を加えた 倍数である場合、k = 1 になります。 それ以外の場合、k = 0。

つまり：

${\displaystyle \alpha +1=\xi (0,\alpha ).}$

$\displaystyle 1\leq \gamma <\omega ^{\omega ^{\beta +1}}\land n<\omega \implies \omega ^{\omega ^{\beta +1}}\cdot \alpha +\omega ^{\omega ^{\beta }}\cdot (\omega \cdot \gamma +n)=\xi (1+\beta ,\omega ^{\omega ^{\beta +1}}\cdot \alpha +(\omega \cdot \gamma +n)).}$

${\displaystyle (0<\alpha \lor \beta <\omega ^{\beta })\land n<\omega \implies \omega ^{\omega ^{\beta +1}}\cdot \alpha +\omega ^{\omega ^{\beta }}\cdot (n+1)=\xi (1+\beta ,\omega ^{\omega ^{\beta +1}}\cdot \alpha +n).}$

${\displaystyle \beta =\omega ^{\beta }\land n<\omega \implies \omega ^{\omega ^{\beta }}\cdot (n+2)=\xi (\beta ,n).}$

ξ表記法を用いると、 ε₀より小さい任意の順序数を、わずか2つの記号（「0」と「ξ」）からなるアルファベットで命名することができます_。これらの表記法にイプシロン数を列挙する関数を追加すると、追加された関数では命名できない最初のイプシロン数より小さい任意の順序数に命名できるようになります。この最後の性質、つまり順序​​数の最初のセグメント内に記号を追加すると、そのセグメント内に名前が付けられるという性質は、完全性（ソロモン・フェファーマンにちなんで）と呼ばれます。

0とωに関する「指数多項式」は_、 ε₀より小さい順序数を表す順序表記法を提供します。これらを記述する方法は数多くあり、指数多項式の代わりに、根付き木、入れ子括弧、または上述の表記法を用いることができます。

2変数ヴェブレン関数（ヴェブレン 1908 ）は、フェファーマン・シュッテ順序数より小さい順序数に対する順序表記体系を与えるために使用できます。有限または超限数の変数のヴェブレン関数は、小ヴェブレン順序数および大ヴェブレン順序数より小さい順序数に対する順序表記体系を与えます。

アッカーマン（1951）は、ヴェブレンが以前に記述したシステムよりもやや弱い順序表記法を記述した。彼のシステムの極限は、アッカーマン順序数と呼ばれることがある。

バッハマン（1950）は、不可算順序数を用いて新しい可算順序数を生成するという重要なアイデアを導入した。彼の当初のシステムは、各順序数に収束する特別な数列を選択する必要があったため、かなり扱いにくかった。フェファーマンらが後に導入した表記法は、この複雑さを回避した。

竹内（1987）は「順序図」として知られる順序表記体系を記述し、その極限は竹内-フェファーマン-ブッフホルツ順序である。^{[ 1 ]}この体系は後にフェファーマンによって簡略化された。

フェファーマンは、ブッフホルツ (1986)で次のように説明されているシータ関数を導入しました。順序数αに対して、θ _αは順序数を順序数に写像する関数です。多くの場合、θ _α ( β ) はθ α βと表記されます。集合C ( α , β ) は、αに関する帰納法によって、順序数の加算とξ < αの関数θ _ξの演算によって 0、 ω ₁、ω ₂、...、ω _ωから生成できる順序数とβより小さい順序数の集合として定義されます。また、関数θ _γは、 δ ∉ C ( γ , δ )となる順序数δを列挙する関数として定義されます。このシステムの問題点は、順序数表記と縮約関数が同一ではないため、この関数は順序数表記として適格ではないことです。関連する序数表記は不明である。

ブッフホルツ（1986）は、フェファーマンのシータ関数の簡略化として、以下の順序表記法を説明した。定義：

• Ω _ξ = ω _ξ ξ > 0の場合、 Ω ₀ = 1

αが序数、v が最大でもωの序数に対する関数ψ _v ( α )は、 αの帰納法によって次のように定義されます。

• ψ _v ( α ) はC _v ( α )に含まれない最小の順序数です

ここで、C _v ( α ) は、

• C _v ( α ) にはΩ _vより小さいすべての順序数が含まれる
• C _v ( α ) は順序加算に関して閉じている
• C _v ( α ) は、 αより小さい引数に適用される関数ψ _u ( u ≤ ωの場合) に関して閉じている。

このシステムはフェファーマンのシステムとほぼ同じ強さを持っている。${\displaystyle \theta \varepsilon _{\Omega _{v}+1}0=\psi _{0}(\varepsilon _{\Omega _{v}+1})}$v ≤ ωの場合。しかし、このシステムは強力ではあるものの、順序表記法としては適格ではありません。ブッフホルツは関連する順序表記法を作成しましたが、それは複雑です。定義は本文に記載されています。

クリーネ (1938)は、すべての再帰的順序数 (チャーチ-クリーネ順序数より小さいもの) の表記体系を記述しました。残念ながら、上記で説明した他のシステムとは異なり、ある自然数が順序数を表しているかどうか、または 2 つの数が同じ順序数を表しているかどうかを一般的に効果的に判断する方法はありません。しかし、クリーネの表記体系で与えられた任意の 2 つの表記の順序和、積、およびべき乗 (順序算術を参照)を表す表記を効果的に見つけることができます。${\displaystyle {\mathcal {O}}}$; また、任意の順序数の表記法が与えられた場合、より小さい各順序数に対応する要素を 1 つずつ含み、実質的に順序付けられた表記法の再帰的に列挙可能な集合が存在する。クリーネの${\displaystyle {\mathcal {O}}}$これは、標準的な（そして計算が非常に困難な）表記法の集合を表します。有限個の記号列の代わりに自然数のサブセットを使用し、再帰的ではないため、やはり再帰的な順序表記法とはみなされません。