非再帰的順序数

数学、特に集合論において、非再帰的順序数はすべての再帰的順序数よりも大きい大きな可算順序数であるため、再帰的順序数表記法を使用して表現することはできません。

最小の非再帰的順序数はチャーチ・クリーネ順序数 で、アロンゾ・チャーチとSC クリーネにちなんで名付けられました。その順序型はすべての再帰的順序数の集合 です。再帰的順序数の次数が再帰的であるため、チャーチ・クリーネ順序数は極限順序数です。これは超算術的 ではない最小の順序数でもあり、の後の最小の許容順序数でもあります( の場合、順序数は許容可能と呼ばれます)。の -再帰的部分集合はの部分集合とまったく同じです。^[1]${\displaystyle \omega _{1}^{\mathsf {CK}}}$${\displaystyle \omega}$${\displaystyle \alpha}$${\displaystyle L_{\alpha }\models {\mathsf {KP}}}$${\displaystyle \omega _{1}^{\mathsf {CK}}}$${\displaystyle \omega}$${\displaystyle \Delta _{1}^{1}}$${\displaystyle \omega}$

この表記は、すべての可算順序数の集合である最初の非可算順序数を参照しており、これはチャーチ-クリーネ順序数がすべての再帰的順序数の集合であるのと同様である。いくつかの古い文献ではチャーチ-クリーネ順序数を と表記している。^[2]${\displaystyle \omega _{1}^{\mathsf {CK}}}$${\displaystyle \omega _{1}}$${\displaystyle \omega _{1}}$

集合 に対して、を問い合わせる神託状態を持つチューリングマシンから計算可能な場合、集合 は -計算可能となります。相対化されたチャーチ・クリーネ順序数は、 -計算可能関係の順序タイプの上限です。フリードマン・ジェンセン・サックスの定理は、すべての可算許容順序数 に対して、となる集合が存在することを述べています。^[3]${\displaystyle x\subseteq \mathbb {N} }$${\displaystyle x}$${\displaystyle x}$${\displaystyle \omega _{1}^{x}}$${\displaystyle x}$${\displaystyle \alpha}$${\displaystyle x}$${\displaystyle \alpha =\omega _{1}^{x}}$

${\displaystyle \omega _{\omega }^{\mathsf {CK}}}$は、スティーブン・G・シンプソン^{[要出典]によって最初に定義されたチャーチ・クリーネ順序数の拡張です。これは許容される順序数の最小の限界ですが、この順序数は許容されません。あるいは、これは、が}-理解のモデルとなるような最小のαです。^[1]${\displaystyle L_{\alpha }\cap {\mathsf {P}}(\omega )}$${\displaystyle \Pi _{1}^{1}}$

番目の許容順序数は と表記されることもある。^{[4] [5]}${\displaystyle \alpha}$${\displaystyle \tau_{\alpha}}$

再帰的に「x 」順序数は、通常「 x 」が大きな基数特性を表す場合、非再帰的順序数の一種です。^{[6] Rathjenはこれらの順序数を「} xの再帰的に大きな対応物」と呼んでいますが、^[7]ここでの「再帰的に大きな」の使用は、順序数が再帰的であるという概念と混同しないでください。

順序数が許容可能かつ許容可能な数の極限である場合、その順序数は再帰的にアクセス不可能と呼ばれます。あるいは、 が番目の許容順序数である場合に限り、 が再帰的にアクセス不可能です。 ^[5]または である場合に限り、 です。これは、各集合がクリプキ-プラテック集合論のモデルに含まれていることを述べるクリプキ-プラテック集合論の拡張です。 (「すべての集合は遺伝的に可算である」)という条件下では、 が-内包のモデルである場合に限り、 が再帰的にアクセス不可能です。^[8]${\displaystyle \alpha}$${\displaystyle \alpha}$${\displaystyle \alpha}$${\displaystyle \alpha}$${\displaystyle L_{\alpha }\models {\mathsf {KPi}}}$${\displaystyle L_{\alpha }\vDash {\textrm {V=HC}}}$${\displaystyle \alpha}$${\displaystyle L_{\alpha }\cap {\mathsf {P}}(\omega )}$${\displaystyle \Delta _{2}^{1}}$

順序数が再帰的に超アクセス不可能なのは、それが再帰的にアクセス不可能であり、かつ再帰的にアクセス不可能な数の限界である場合、または 番目に再帰的にアクセス不可能である場合です。「超アクセス不可能な基数」と同様に、この用語についてはさまざまな著者が対立しています。 ${\displaystyle \alpha}$${\displaystyle \alpha}$${\displaystyle \alpha}$

順序数が許容可能であり、任意の -再帰関数に対して となる許容順序数が存在するとき、その順序数は再帰的マハロであると呼ばれる（つまり、 はの下で閉じている）。^[2]マハロネス階層を反映して、順序数が許容可能であり、任意の-再帰関数に対して となる許容順序数が存在するとき、その順序数は再帰的マハロであり、 はの下で閉じており、すべての に対して再帰的マハロである。^[6]${\displaystyle \alpha}$${\displaystyle \alpha}$${\displaystyle f:\alpha \rightarrow \alpha }$${\displaystyle \beta <\alpha }$${\displaystyle \left\{f(\gamma )\mid \gamma \in \beta \right\}\subseteq \beta }$${\displaystyle \beta }$${\displaystyle f}$${\displaystyle \alpha }$${\displaystyle \gamma }$${\displaystyle \gamma }$${\displaystyle \alpha }$${\displaystyle f:\alpha \rightarrow \alpha }$${\displaystyle \beta <\alpha }$${\displaystyle \beta }$${\displaystyle f}$${\displaystyle \beta }$${\displaystyle \delta }$${\displaystyle \delta <\gamma }$

順序数が-反射的である場合、または同等に、^[2] 2-許容的 である場合、その順序数は再帰的に弱コンパクトと呼ばれます。これらの順序数は強い再帰的マロネス特性を持ち、αが-反射的である場合、再帰的に-マロです。^[6]${\displaystyle \alpha }$${\displaystyle \Pi _{3}}$${\displaystyle \Pi _{3}}$${\displaystyle \alpha }$${\displaystyle \alpha }$

順序数が安定であるとは、がの基本部分構造であり、 と表記される場合を言う。 [ ^9]これらは、モデル理論の文脈で現れる最大の名前付き非再帰的順序数の一部であり、例えば、任意の計算可能公理化可能な理論 の場合、より大きい。^{[10]命題 0.7}。安定順序数には様々な弱化がある: ^[1]${\displaystyle \alpha }$${\displaystyle L_{\alpha }}$${\displaystyle \Sigma _{1}}$${\displaystyle L}$${\displaystyle L_{\alpha }\preceq _{1}L}$${\displaystyle \min\{\alpha :L_{\alpha }\models T\}}$${\displaystyle T}$

• 可算順序数は、の場合にのみ-stableと呼ばれます。 ${\displaystyle \alpha }$${\displaystyle (+1)}$ ${\displaystyle L_{\alpha }\preceq _{1}L_{\alpha +1}}$
  • 最小の-安定順序数は、最小の再帰的に弱コンパクト順序数よりもはるかに大きい。最小の-安定順序数は、すべての有限の に対して -反射的であることが示されている。^[2]${\displaystyle (+1)}$${\displaystyle (+1)}$${\displaystyle \Pi _{n}}$${\displaystyle n}$
  • 一般に、可算順序数は の場合に限り -安定と呼ばれます。${\displaystyle \alpha }$${\displaystyle (+\beta )}$${\displaystyle L_{\alpha }\preceq _{1}L_{\alpha +\beta }}$
• 可算順序数は、 が最小の許容順序数である場合に限り、 -安定と呼ばれます。最小の-安定順序数は、最小の-安定または任意の定数に対する最小の-安定よりもはるかに大きくなります。${\displaystyle \alpha }$${\displaystyle (^{+})}$${\displaystyle L_{\alpha }\preceq _{1}L_{\alpha ^{+}}}$${\displaystyle \beta ^{+}}$${\displaystyle >\beta }$${\displaystyle (^{+})}$${\displaystyle (+1)}$${\displaystyle (+\beta )}$${\displaystyle \beta }$
• 可算順序数は、 が2 つの最小の許容順序数である場合に限り、 -安定と呼ばれます。最小の-安定順序数は、最小の -反射順序数よりも大きくなります。${\displaystyle \alpha }$${\displaystyle (^{++})}$${\displaystyle L_{\alpha }\preceq _{1}L_{\alpha ^{++}}}$${\displaystyle \beta ^{++}}$${\displaystyle >\beta }$${\displaystyle (^{++})}$${\displaystyle \Sigma _{1}^{1}}$
• 可算順序数は、 が最小の再帰的にアクセス不可能な順序数である場合に限り、アクセス不可能安定と呼ばれます。最小のアクセス不可能安定順序数は、最小の -安定順序数よりも大きくなります。${\displaystyle \alpha }$${\displaystyle L_{\alpha }\preceq _{1}L_{\beta }}$${\displaystyle \beta }$${\displaystyle >\alpha }$${\displaystyle (^{++})}$
• 可算順序数は、 が最小の再帰的マーロ順序数である場合に限り、マーロ安定と呼ばれます。最小のマーロ安定順序数は、最小のアクセス不可能安定順序数よりも大きくなります。${\displaystyle \alpha }$${\displaystyle L_{\alpha }\preceq _{1}L_{\beta }}$${\displaystyle \beta }$${\displaystyle >\alpha }$
• 可算順序数は、次の場合に限り二重安定と呼ばれます。最小の二重安定順序数は、最小のマーロ安定順序数よりも大きくなります。${\displaystyle \alpha }$${\displaystyle (+1)}$${\displaystyle L_{\alpha }\preceq _{1}L_{\beta }\preceq _{1}L_{\beta +1}}$${\displaystyle (+1)}$

さらに大きな非再帰的順序数には以下のものがある: ^[1]

• 最小の非射影順序数となる最小の順序数。${\displaystyle \alpha }$${\displaystyle L_{\alpha }\preceq _{1}L_{\beta }}$${\displaystyle \beta }$
• 順序数が安定順序数の極限である場合、または集合がにおいて非有界である場合、順序数は非射影です。${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle \alpha }$${\displaystyle X=\left\{\beta <\alpha \mid L_{\beta }\preceq _{1}L_{\alpha }\right\}}$${\displaystyle \alpha }$
• 分岐解析の順序数。 と表記されることが多い。 これは、 が第 2 階の内包 のモデル、または、べき集合の公理を持たない であるような最小のものである。${\displaystyle \beta _{0}}$${\displaystyle \beta }$${\displaystyle L_{\beta }\cap {\mathsf {P}}(\omega )}$${\displaystyle L_{\beta }\models {\mathsf {ZFC^{-}}}}$${\displaystyle {\mathsf {ZFC}}}$
• となる最小の順序数。この順序数は新井俊康によって特徴づけられた。^[11]${\displaystyle \alpha }$${\displaystyle L_{\alpha }\models {\mathsf {KP}}+{\text{'}}\omega _{1}{\text{ exists'}}}$
• となる最小の順序数。${\displaystyle \alpha }$${\displaystyle L_{\alpha }\models {\mathsf {ZFC^{-}}}+{\text{'}}\omega _{1}{\text{ exists'}}}$
• 最も安定性の低い順序数。