クリーネのO

集合論と計算可能性理論において、クリーネの は、${\displaystyle {\mathcal {O}}}$順序表記法とみなされる自然数の標準的な部分集合です。これには、あらゆる計算可能な順序数、つまりチャーチ–クリーネ順序数、未満の順序数 に対する順序表記法が含まれます。は順序表記法の計算可能なシステムで表現できない最初の順序数であるため、 の要素は標準的な順序表記法とみなすことができます。 ${\displaystyle \omega _{1}^{\text{CK}}}$${\displaystyle \omega _{1}^{\text{CK}}}$${\displaystyle {\mathcal {O}}}$

Kleene (1938) は、すべての計算可能な順序数 (チャーチ–クリーネ順序数未満の順序数) の表記法を説明した。この表記法では、有限の記号列ではなく、自然数のサブセットを使用する。残念ながら、一般に、ある自然数が順序数を表すのか、2 つの数が同じ順序数を表すのかを効果的に判断する方法はない。しかし、Kleene の における任意の 2 つの表記法の順序数の和、積、累乗 (順序数の算術を参照) を表す表記法を見つけることはできる。また、順序数の表記法が与えられた場合、より小さい順序数ごとに 1 つの要素を含み、効果的に順序付けられた、計算可能に列挙可能な表記法の集合が存在する。 ${\displaystyle {\mathcal {O}}}$

クリーネの順序数表記法の基本的な考え方は、順序数を効率的に構築することです。 の要素について、が表記される順序数は です。および(クリーネの の部分順序) は、以下が成り立つ最小の集合です。^{[引用が必要]}${\displaystyle p}$${\displaystyle {\mathcal {O}}}$${\displaystyle p}$${\displaystyle |p|}$${\displaystyle {\mathcal {O}}}$${\displaystyle <_{\mathcal {O}}}$${\displaystyle {\mathcal {O}}}$

• ${\displaystyle 0\in {\mathcal {O}}\land |0|=0}$。
• ${\displaystyle i\in {\mathcal {O}}\land |i|=\alpha \rightarrow 2^{i}\in {\mathcal {O}}\land |2^{i}|=\alpha +1\land i<_{\mathcal {O}}2^{i}}$
• が- 番目の部分計算可能関数であるとします。が全関数で の場合、${\displaystyle \{e\}}$${\displaystyle e}$${\displaystyle e}$${\displaystyle {\textrm {range}}(\{e\})\subset {\mathcal {O}}\land \forall n(\{e\}(n)<_{\mathcal {O}}\{e\}(n+1))}$${\displaystyle 3\cdot 5^{e}\in {\mathcal {O}}\land \forall n,\{e\}(n)<_{\mathcal {O}}3\cdot 5^{e }\land |3\cdot 5^{e}|=\lim _{k}|\{e\}(k)|}$
• ${\displaystyle p<_{\mathcal {O}}q\land q<_{\mathcal {O}}r\rightarrow p<_{\mathcal {O}}r}$

この定義の利点は、与えられた順序数の前のものを計算可能に列挙できること（順序ではないが）と、表記法が下向きに閉じていること（つまり、の表記法があり 、の表記法がある場合）である。自然数の（部分的な）順序付けのインデックスの集合など、代替の定義もある。^[1]${\displaystyle <_{\mathcal {O}}}$${\displaystyle \gamma}$${\displaystyle \alpha <\gamma }$${\displaystyle \alpha }$

クリーネの要素は記法と呼ばれ、順序数の定義を与えることを目的としています。 ${\displaystyle p}$${\displaystyle {\mathcal {O}}}$${\displaystyle |p|}$

後継表記法とは、 が後継順序数となる表記法です。Kleene の では、後継順序数は、その直前の順序数の表記法によって定義されます。具体的には、後継表記法は、他の表記法 の形式であるため、 となります。 ${\displaystyle |p|}$${\displaystyle \alpha +1}$${\displaystyle {\mathcal {O}}}$${\displaystyle p}$${\displaystyle 2^{q}}$${\displaystyle q}$${\displaystyle |p|=|q|+1}$

極限表記法は、 が極限順序数となるような表記法です。クリーネの では、極限順序数の表記法は、 に制限されるより小さい順序数の表記法の計算可能な列になります。任意の極限表記法は の形式であり、ここで番目の部分計算可能関数は、 の順序で厳密に増加する表記法の無限列を列挙する全関数です。順序数列の極限はです。 ${\displaystyle |p|}$${\displaystyle {\mathcal {O}}}$${\displaystyle \beta }$${\displaystyle \beta }$${\displaystyle p}$${\displaystyle 3\cdot 5^{e}}$${\displaystyle e}$${\displaystyle \{e\}:\mathbb {N} \rightarrow \mathbb {N} }$${\displaystyle \langle q_{0},q_{1}...\rangle }$${\displaystyle <_{\mathcal {O}}}$${\displaystyle \langle |q_{0}|,|q_{1}|...\rangle }$${\displaystyle |p|}$

は を意味しますが、を意味するものではありません。 ${\displaystyle q<_{\mathcal {O}}p}$${\displaystyle |q|<|p|}$${\displaystyle |q|<|p|}$${\displaystyle q<_{\mathcal {O}}p}$

が であるためには、との演算を繰り返し適用することによってから に到達可能でなければなりません。言い換えると、が によって与えられたの定義で最終的に参照されるとき、 となります。 ${\displaystyle q<_{\mathcal {O}}p}$${\displaystyle q}$${\displaystyle p}$${\displaystyle 2^{n}\mapsto n}$${\displaystyle 3\cdot 5^{e}\mapsto \{e\}(i)}$${\displaystyle i\in \mathbb {N} }$${\displaystyle q<_{\mathcal {O}}p}$${\displaystyle q}$${\displaystyle |p|}$${\displaystyle p}$

任意の について、 のとき、 との演算を繰り返し に適用することでからに到達可能であるとします。この関係はではと一致しますが、計算可能に列挙可能です。つまり、 の場合、コンピュータ プログラムは最終的にこの事実の証明を見つけることになります。 ${\displaystyle p,q\in \mathbb {N} }$${\displaystyle q\prec p}$${\displaystyle q}$${\displaystyle p}$${\displaystyle 2^{n}\mapsto n}$${\displaystyle 3\cdot 5^{e}\mapsto \{e\}(i)}$${\displaystyle i\in dom(\{e\})}$${\displaystyle \prec }$${\displaystyle <_{\mathcal {O}}}$${\displaystyle {\mathcal {O}}}$${\displaystyle \prec }$${\displaystyle q\prec p}$

任意の表記 について、すべては内の表記です。 ${\displaystyle p\in {\mathcal {O}}}$${\displaystyle q\prec p}$${\displaystyle {\mathcal {O}}}$

の場合、は以下の条件がすべて満たされる場合にのみ の表記になります。${\displaystyle p\in \mathbb {N} }$${\displaystyle p}$${\displaystyle {\mathcal {O}}}$

• すべての に対して、は、 の累乗、またはのいずれかです。${\displaystyle q\preceq p}$${\displaystyle q}$${\displaystyle 0}$${\displaystyle 2}$${\displaystyle 3\cdot 5^{e}}$${\displaystyle e\in \mathbb {N} }$
• 任意の に対して、であれば はに関して全かつ厳密に増加します。つまり、任意の に対して です。${\displaystyle q\preceq p}$${\displaystyle q=3\cdot 5^{e}}$${\displaystyle \{e\}}$${\displaystyle \prec }$${\displaystyle \{e\}(i)\prec \{e\}(i+1)}$${\displaystyle i\in \mathbb {N} }$
• この集合は整基礎集合であるため、無限降順列は存在しません。${\displaystyle \{q\in \mathbb {N} :q\prec p\}}$${\displaystyle ...\prec q_{1}\prec q_{0}\prec p}$

• かつ の場合、ですが、逆は成立しない可能性があります。${\displaystyle |i|=\alpha }$${\displaystyle |j|=\beta }$${\displaystyle i<_{\mathcal {O}}j\,,}$${\displaystyle \alpha <\beta }$
• ${\displaystyle <_{\mathcal {O}}}$は 上に木構造を誘導するので、 は整基礎です。${\displaystyle {\mathcal {O}}}$${\displaystyle {\mathcal {O}}}$
• ${\displaystyle {\mathcal {O}}}$極限順序数でのみ分岐し、極限順序数の各表記では無限に分岐します。${\displaystyle {\mathcal {O}}}$
• すべての計算可能関数には可算な数のインデックスがあるため、各無限順序数は可算な数の表記を受け取ります。有限順序数は、通常 と表記される一意の表記を持ちます。${\displaystyle n}$${\displaystyle n_{\mathcal {O}}}$
• 表記を受けない最初の順序数はチャーチ・クリーネ順序数と呼ばれ、 と表記されます。計算可能な関数は可算個しかないので、順序数は明らかに可算です。${\displaystyle \omega _{1}^{\text{CK}}}$${\displaystyle \omega _{1}^{\text{CK}}}$
• クリーネの表記法で と表記される順序数は、まさに計算可能順序数です。(すべての計算可能順序数が と表記されるという事実は、後続極限と有効極限の下でのこの順序数表記法の閉包から生じます。)${\displaystyle {\mathcal {O}}}$
• ${\displaystyle <_{\mathcal {O}}}$は計算可能列挙可能ではありませんが、のちょうど 個の要素と一致する計算可能列挙可能な関係が存在します。${\displaystyle <_{\mathcal {O}}}$${\displaystyle {\mathcal {O}}}$
• 任意の表記 に対して、以下の表記の集合は計算可能に列挙可能です。しかし、クリーネの は、全体としては(解析的階層を参照) であり、次の理由により算術的ではありません。${\displaystyle p}$${\displaystyle \lbrace q\mid q<_{\mathcal {O}}p\rbrace }$${\displaystyle p}$${\displaystyle {\mathcal {O}}}$${\displaystyle \Pi _{1}^{1}}$
• ${\displaystyle {\mathcal {O}}}$は-完全（すなわち、であり、すべての集合はそれにチューリング還元可能である）^[2]であり、のすべての部分集合は事実上 で有界である（スペクターの結果）。${\displaystyle \Pi _{1}^{1}}$${\displaystyle {\mathcal {O}}}$${\displaystyle \Pi _{1}^{1}}$${\displaystyle \Pi _{1}^{1}}$${\displaystyle \Sigma _{1}^{1}}$${\displaystyle {\mathcal {O}}}$${\displaystyle {\mathcal {O}}}$
• 実際、任意の集合は多対一に還元可能である。^[2]${\displaystyle \Pi _{1}^{1}}$${\displaystyle {\mathcal {O}}}$
• ${\displaystyle {\mathcal {O}}}$は、任意の特定の順序表記法の集合を簡単な方法でマッピングできるという意味で、順序表記法の普遍的なシステムです。より正確には、 が計算可能な整列順序付けのインデックスである場合に がのメンバーであり、集合 の初期セグメントと順序同型であるような計算可能な関数が存在します。${\displaystyle f}$${\displaystyle e}$${\displaystyle f(e)}$${\displaystyle {\mathcal {O}}}$${\displaystyle <_{e}}$${\displaystyle \{p\mid p<_{\mathcal {O}}f(e)\}}$
• 計算可能な関数 があり、これは の要素に対して順序加算を模倣し、 という特性を持ちます。(Jockusch)${\displaystyle +_{\mathcal {O}}}$${\displaystyle {\mathcal {O}}}$${\displaystyle \max\{p,q\}\leq p+_{\mathcal {O}}q}$

内のパスはのサブセットであり、 によって完全に順序付けられ、先行要素に関して閉じています。つまり、 がパスのメンバーである場合、はのメンバーでもあります。 のどのメンバーよりも上 ( の意味で)にある の要素が存在しない場合にパスは最大であり、そうでない場合はは最大ではありません。 ${\displaystyle {\mathcal {O}}}$${\displaystyle {\mathcal {P}}}$${\displaystyle {\mathcal {O}}}$${\displaystyle <_{\mathcal {O}}}$${\displaystyle p}$${\displaystyle {\mathcal {P}}}$${\displaystyle q<_{\mathcal {O}}p}$${\displaystyle q}$${\displaystyle {\mathcal {P}}}$${\displaystyle {\mathcal {P}}}$${\displaystyle {\mathcal {O}}}$${\displaystyle <_{\mathcal {O}}}$${\displaystyle {\mathcal {P}}}$${\displaystyle {\mathcal {P}}}$

• パスが非最大となるのは、が計算可能列挙可能 (ce) である場合のみです。上記の説明から、のすべての要素が非最大パスを決定し、すべての非最大パスがそのように決定されることがわかります。${\displaystyle {\mathcal {P}}}$${\displaystyle {\mathcal {P}}}$${\displaystyle p}$${\displaystyle {\mathcal {O}}}$${\displaystyle {\mathcal {P}}}$
• を通る極大パスが存在する。それらは極大なので、非CEである。${\displaystyle 2^{\aleph _{0}}}$${\displaystyle {\mathcal {O}}}$
• 実際、長さ以内には最大経路が存在します。(Crossley、Schütte)${\displaystyle 2^{\aleph _{0}}}$ ${\displaystyle {\mathcal {O}}}$${\displaystyle \omega ^{2}}$
• ゼロでない順序数ごとに、長さ以内に最大パスが存在します。(Aczel)${\displaystyle \lambda <\omega _{1}^{CK}}$${\displaystyle 2^{\aleph _{0}}}$${\displaystyle {\mathcal {O}}}$${\displaystyle \omega ^{2}\cdot \lambda }$
• さらに、長さが の倍数でないパスの場合、 は最大ではありません。(Aczel)${\displaystyle {\mathcal {P}}}$${\displaystyle \omega ^{2}}$${\displaystyle {\mathcal {P}}}$
• 各 ce 次数 に対して、パスが多対一次数 を持つようなの要素が存在します。実際、各計算可能順序数 に対して、 という表記法が存在します。(Jockusch)${\displaystyle d}$${\displaystyle e_{d}}$${\displaystyle {\mathcal {O}}}$${\displaystyle {\mathcal {P}}=\lbrace p\mid p<_{\mathcal {O}}e_{d}\rbrace }$${\displaystyle d}$${\displaystyle \alpha \geq \omega ^{2}}$${\displaystyle e_{d}}$${\displaystyle |e_{d}|=\alpha }$
• が通過する経路が存在します。Uniform Reflection の反復に基づく計算可能に列挙可能な理論の進行を考えると、そのような経路はそれぞれ、真の文の集合に関して不完全です。(Feferman & Spector)${\displaystyle \aleph _{0}}$${\displaystyle {\mathcal {O}}}$${\displaystyle \Pi _{1}^{1}}$${\displaystyle \Pi _{1}^{0}}$
• 各初期セグメントには、単に ce であるだけでなく計算可能なパスが存在します。(Jockusch)${\displaystyle \Pi _{1}^{1}}$${\displaystyle {\mathcal {O}}}$
• 他にもさまざまなパスが存在することが示されており、それぞれが特定の種類の還元特性を持っています。(下記の参考文献を参照)${\displaystyle {\mathcal {O}}}$

• 計算可能な順序数
• 大きな可算順序数
• 序数表記