アルファ再帰理論

再帰理論において、α 再帰理論は、許容順序数 のサブセットへの再帰理論の一般化です。許容集合 は関数 の下で閉じており、 はゲーデルの構成可能階層のランクを表します。がクリプキ-プラテック集合論のモデルである場合、 は許​​容順序数です。以下では、は固定されていると見なされます。 ${\displaystyle \alpha}$${\displaystyle \Sigma _{1}(L_{\alpha })}$${\displaystyle L_{\xi}}$${\displaystyle \alpha}$${\displaystyle L_{\alpha}}$${\displaystyle \alpha}$

再帰の研究対象はのサブセットです。これらのセットにはいくつかの特性があると言われています。 ${\displaystyle \alpha}$${\displaystyle \alpha}$

• 集合が上で定義可能であり、定義にからのパラメータが含まれる場合、その集合は-再帰的に列挙可能であると言われる。 ^[1]${\displaystyle A\subseteq \alpha }$${\displaystyle \alpha}$${\displaystyle \Sigma _{1}}$${\displaystyle L_{\alpha}}$${\displaystyle L_{\alpha}}$
• A と(におけるその相対補集合) の両方が -再帰的に列挙可能である場合、 A は-再帰的です。の定義により、-再帰集合は のメンバーであることに注意してください。${\displaystyle \alpha}$${\displaystyle \alpha \setminus A}$${\displaystyle \alpha}$${\displaystyle \alpha}$${\displaystyle \alpha}$${\displaystyle L_{\alpha +1}}$${\displaystyle L}$
• の要素は-有限と呼ばれ、古典的な再帰理論における有限数と同様の役割を果たします。${\displaystyle L_{\alpha}}$${\displaystyle \alpha}$
• の要素は-算術と呼ばれる。^[2]${\displaystyle L_{\alpha +1}}$${\displaystyle \alpha}$

にマッピングされる関数にも同様の定義がいくつかある: ^[3]${\displaystyle \alpha}$${\displaystyle \alpha}$

• からへの部分関数は、そのグラフが上で -定義可能である場合に限り、 -再帰的に列挙可能、または-部分再帰的^{[4] で}ある。${\displaystyle \alpha}$${\displaystyle \alpha}$${\displaystyle \alpha}$${\displaystyle \alpha}$${\displaystyle \Sigma _{1}}$${\displaystyle (L_{\alpha },\in )}$
• からへの部分関数は、そのグラフが上で -定義可能である場合に限り、 -再帰的です。古典的な再帰理論の場合と同様に、任意の全-再帰的列挙可能関数は -再帰的です。${\displaystyle \alpha}$${\displaystyle \alpha}$${\displaystyle \alpha}$${\displaystyle \Delta _{1}}$${\displaystyle (L_{\alpha },\in )}$ ${\displaystyle \alpha}$${\displaystyle f:\alpha \rightarrow \alpha }$${\displaystyle \alpha}$
• さらに、からへの部分関数が-算術的であるためには、関数のグラフが上で -定義可能であるようなものが存在する必要があります。${\displaystyle \alpha}$${\displaystyle \alpha}$${\displaystyle \alpha}$${\displaystyle n\in \omega }$${\displaystyle \Sigma _{n}}$${\displaystyle (L_{\alpha },\in )}$

再帰理論と α 再帰理論の間には追加のつながりを描くことができますが、それらを形式化するための明確な定義はまだ書かれていない可能性があります。

• で定義可能な関数は、原始再帰関数と同様の役割を果たす。^[3]${\displaystyle \Delta _{0}}$${\displaystyle (L_{\alpha },\in )}$

R が再帰的に列挙可能であり、 R のすべてのメンバーがH、J、Kがすべて α 有限である 形式である場合、 R は簡約手順であると言います。${\displaystyle \alpha}$${\displaystyle \langle H,J,K\rangle }$

次のような簡約手順 が存在する場合、A はBにおいて α 再帰的であると言われる:${\displaystyle R_{0},R_{1}}$

${\displaystyle K\subseteq A\leftrightarrow \exists H:\exists J:[\langle H,J,K\rangle \in R_{0}\wedge H\subseteq B\wedge J\subseteq \alpha /B],}$

${\displaystyle K\subseteq \alpha /A\leftrightarrow \exists H:\exists J:[\langle H,J,K\rangle \in R_{1}\wedge H\subseteq B\wedge J\subseteq \alpha /B].}$

AがB内で再帰的である場合、これは と書きます。この定義により、Aが(空集合)内で再帰的となるのは、Aが再帰的である場合に限ります。ただし、A が B 内で再帰的であることは、A が であることと同じではありません。 ${\displaystyle \scriptstyle A\leq _{\alpha }B}$${\displaystyle \scriptstyle \varnothing }$${\displaystyle \Sigma _{1}(L_{\alpha }[B])}$

Aが正則であるとは、言い換えれば、Aのすべての初期部分がα 有限である 場合であると言います。${\displaystyle \forall \beta \in \alpha :A\cap \beta \in L_{\alpha }}$

ショアの分割定理: A が再帰的に可算かつ正則であるとする。再帰的に可算であって、${\displaystyle \alpha}$${\displaystyle \alpha}$${\displaystyle B_{0},B_{1}}$${\displaystyle A=B_{0}\cup B_{1}\wedge B_{0}\cap B_{1}=\varnothing \wedge A\not \leq _{\alpha }B_{i}(i<2).}$

ショアの密度定理: A、C をα-正則再帰的可算集合とすると、となる正則 α-再帰的可算集合Bが存在する。 ${\displaystyle \scriptstyle A<_{\alpha }C}$${\displaystyle \scriptstyle A<_{\alpha }B<_{\alpha }C}$

バーワイズは、 上で -定義可能な集合は上で -定義可能な集合とまったく同じであることを証明した。ここで はより上の許容順序数を表し、 はレヴィ階層から来ている。^[5]${\displaystyle \Sigma _{1}}$${\displaystyle L_{\alpha ^{+}}}$${\displaystyle \Pi _{1}^{1}}$${\displaystyle L_{\alpha}}$${\displaystyle \alpha^{+}}$${\displaystyle \alpha}$${\displaystyle \Sigma }$

極限計算可能性は部分関数にも一般化されている。^[6]${\displaystyle \alpha \to \alpha }$

-再帰の計算的解釈は、長さ の 2 つのシンボル テープを持つ「 -チューリング マシン」を使用して、極限計算ステップでセルの内容、状態、およびヘッド位置の極限劣位を取ることによって行われます。 が許容される場合、集合が-再帰的であるためには、それが -チューリング マシンによって計算可能であり、 が-チューリング マシンによって計算可能な関数の値域である場合に限り、 -再帰的に列挙可能です。^[7]${\displaystyle \alpha}$${\displaystyle \alpha}$${\displaystyle \alpha}$${\displaystyle \alpha}$${\displaystyle A\subseteq \alpha }$${\displaystyle \alpha}$${\displaystyle \alpha}$${\displaystyle A}$${\displaystyle \alpha}$${\displaystyle A}$${\displaystyle \alpha}$

α-再帰理論における未解決の問題（2019年現在）は、許容順序数に対する埋め込み予想であり、これはすべての許容順序数に対して、-列挙次数の自己同型が-列挙次数の自己同型に埋め込まれるかどうかという問題である。^[8]${\displaystyle \alpha}$${\displaystyle \alpha}$${\displaystyle \alpha}$

-再帰におけるいくつかの結果は、2階算術に関する同様の結果に変換できます。これは、 2階算術の言語における整数の集合からなる分岐解析階層と の関係によるものです。 ^[9]${\displaystyle \alpha}$${\displaystyle L}$${\displaystyle L}$

実際、一階述語論理のみを扱う場合、対応は十分近いため、 上のいくつかの結果に対して、算術階層とレヴィ階層は互換性を持つことができます。たとえば、自然数の集合が式で定義可能であるのは、それが上で -定義可能である場合のみです。ここで、 はレヴィ階層のレベルです。^[10]より一般的には、HF 上の ω の部分集合を式で定義できることは、式を使用して算術的に定義できることと一致する。^[11]${\displaystyle L_{\omega }={\textrm {HF}}}$${\displaystyle \Sigma _{1}^{0}}$${\displaystyle \Sigma _{1}}$${\displaystyle L_{\omega}}$${\displaystyle \Sigma _{1}}$${\displaystyle \Sigma _{n}}$${\displaystyle \Sigma _{n}^{0}}$

• ジェラルド・サックス『高等再帰理論』、シュプリンガー・フェアラーク、1990年 https://projecteuclid.org/euclid.pl/1235422631
• Robert Soare,再帰的に列挙可能な集合と次数、Springer Verlag、1987 https://projecteuclid.org/euclid.bams/1183541465
• キース・J・デブリン著『構築可能な階層構造の微細構造入門』（p.38）、ノースホランド出版、1974年
• J. バーワイズ、許容集合と構造。1975