超算術理論

計算可能性理論において、超算術理論はチューリング計算可能性の一般化である。これは、二階算術における定義可能性や、クリプキ-プラテック集合論などの集合論の弱体系と密接な関係がある。これは、効果的な記述集合論における重要なツールである。^[1]

超算術理論の中心的な焦点は、超算術集合として知られる自然数の集合です。この集合のクラスを定義する方法は 3 つあり、これらの異なる定義間の関係を研究することが、超算術理論を研究する動機の 1 つです。

超算術集合の最初の定義では、解析階層を使用します。自然数の集合は、存在集合量指定子のみを使用し、他の集合量指定子を使用せずに2 階算術の式で定義できる場合、この階層のレベルに分類されます。集合は、普遍集合量指定子のみを使用し、他の集合量指定子を使用せずに 2 階算術の式で定義できる場合、解析階層 のレベルに分類されます。集合は、と の両方である場合にです。超算術集合は、まさに集合です。 ${\displaystyle \Sigma _{1}^{1}}$${\displaystyle \Pi _{1}^{1}}$${\displaystyle \Delta _{1}^{1}}$${\displaystyle \Sigma _{1}^{1}}$${\displaystyle \Pi _{1}^{1}}$${\displaystyle \Delta _{1}^{1}}$

超算術集合の定義は、計算可能性の結果に直接依存しません。2 番目の同等の定義は、超算術集合が無限反復チューリング ジャンプを使用して定義できることを示しています。この 2 番目の定義は、超算術集合が算術階層を拡張した階層に分類できることも示しています。超算術集合は、まさにこの階層でランクが割り当てられた集合です。 ${\displaystyle \Delta _{1}^{1}}$

超算術階層の各レベルは可算順序数(順序数) によってインデックス付けされますが、すべての可算順序数が階層のレベルに対応するわけではありません。階層で使用される順序数は、順序数の具体的かつ効果的な説明である 順序表記法を持つものです。

順序記法は、自然数による可算順序数の効果的な記述です。超算術階層を定義するには、順序記法のシステムが必要です。順序記法が持つべき基本的な特性は、順序数をより小さな順序数で効果的に記述することです。次の帰納的定義は典型的なもので、ペアリング関数 を使用します。 ${\displaystyle \langle \cdot ,\cdot \rangle }$

• 数字 0 は序数 0 を表す表記です。
• n が順序数λの表記である場合、 はλ + 1の表記です。${\displaystyle \langle 1,n\rangle }$
• δ が極限順序数であるとします。 δの表記は という形式の数です。ここでe は、各nに対して となるような全計算可能関数のインデックスです。はδより小さい順序数λ _nの表記であり、δ は集合 のsupです。${\displaystyle \langle 2,e\rangle }$${\displaystyle \phi _{e}}$${\displaystyle \phi _{e}(n)}$${\displaystyle \{\lambda _{n}\mid n\in \mathbb {N} \}}$

これは、限界順序数の表記法だけでなく、すべてのレベルで有効な結合をとることによって定義することもできます。^[2]

各表記は自然数なので、順序表記は可算個しかありません。したがって、表記を持つすべての順序数の上限となる可算順序数が存在します。この順序数はチャーチ–クリーネ順序数として知られ、 と表記されます。この順序数は依然として可算であり、記号 は最初の非可算順序数 との類似性にすぎないことに注意してください。順序表記であるすべての自然数の集合は と表記され、クリーネのと呼ばれます。 ${\displaystyle \omega _{1}^{CK}}$${\displaystyle \omega _{1}}$${\displaystyle {\mathcal {O}}}$${\displaystyle {\mathcal {O}}}$

順序記法は、反復チューリングジャンプを定義するために使用されます。階層を定義するために使用される自然数の集合は、各 に対してです。は、^[3]または の表記法に対してと表記されることもあります。^[2] δ がeと表記されているとします。これらの集合は、Davis (1950) と Mostowski (1951) によって最初に定義されました。^[2]集合はe を使用して次のように 定義されます。${\displaystyle 0^{(\delta )}}$${\displaystyle \delta <\omega _{1}^{CK}}$${\displaystyle 0^{(\delta )}}$${\displaystyle H(\delta )}$${\displaystyle H_{e}}$${\displaystyle e}$${\displaystyle \delta}$${\displaystyle 0^{(\delta )}}$

• δ = 0の場合は空集合になります。${\displaystyle 0^{(\delta )}=0}$
• δ = λ + 1の場合、 はのチューリングジャンプです。 および の集合はそれぞれおよびです。${\displaystyle 0^{(\delta )}}$${\displaystyle 0^{(\lambda )}}$${\displaystyle 0^{(1)}}$${\displaystyle 0^{(2)}}$${\displaystyle 0'}$${\displaystyle 0''}$
• δが極限順序数である場合、 は表記eで与えられるδ未満の順序数のシーケンスとします。集合は規則 で与えられます。これは集合 の有効な結合です。${\displaystyle \langle \lambda _{n}\mid n\in \mathbb {N} \rangle }$${\displaystyle 0^{(\delta )}}$${\displaystyle 0^{(\delta )}=\{\langle n,i\rangle \mid i\in 0^{(\lambda _{n})}\}}$${\displaystyle 0^{(\lambda _{n})}}$

の構成はδの固定された表記法に依存し、各無限順序数は多くの表記法を持つが、クリフォード・スペクターの定理は、のチューリング次数はδのみに依存し、使用される特定の表記法には依存せず、チューリング次数まで明確に定義されていることを示している。^[2]${\displaystyle 0^{(\delta )}}$${\displaystyle 0^{(\delta )}}$${\displaystyle 0^{(\delta )}}$

超算術階層は、これらの反復チューリングジャンプから定義されます。自然数の集合X は、 X がにチューリング還元可能である場合、 に対して、超算術階層のレベルδに分類されます。そのようなδ の最小値は常に存在します(存在する場合)。この最小のδが、 Xの計算不可能性のレベルを測定します。 ${\displaystyle \delta <\omega _{1}^{CK}}$${\displaystyle 0^{(\delta )}}$

を構成可能な階層の 番目のレベルとし、をクリーネの Oの元からそれが表す順序数への写像とします。 の部分集合が超算術的であるためには、それが の元である必要があります。 の部分集合が式によって定義可能であるためには、その像が 上で -定義可能である必要があります。ここで、は式のレヴィ階層から来ています。 ^[4]${\displaystyle L_{\alpha}}$${\displaystyle \alpha}$${\displaystyle n:{\mathcal {O}}\to \omega _{1}^{CK}}$${\displaystyle \mathbb {N} }$${\displaystyle L_{\omega _{1}^{CK}}}$${\displaystyle \mathbb {N} }$${\displaystyle \Pi _{1}^{1}}$${\displaystyle n}$${\displaystyle \Sigma _{1}}$${\displaystyle L_{\omega _{1}^{CK}}}$${\displaystyle \Sigma _{1}}$

クリーネによる超算術集合の 3 番目の特徴付けでは、高次のタイプの計算可能な関数を使用します。タイプ 2 関数は次の規則によって定義されます。 ${\displaystyle {}^{2}E\colon \mathbb {N} ^{\mathbb {N} }\to \mathbb {N} }$

${\displaystyle {}^{2}E(f)=1\quad }$もし、 f ( i ) > 0となるようなiが存在するならば、

${\displaystyle {}^{2}E(f)=0\quad }$f ( i ) > 0となるようなi が存在しない場合。

クリーネは、タイプ 2 関数に対する計算可能性の正確な定義を使用して、自然数の集合が超算術的であるためには、それが に対して計算可能である必要があること、またその場合に限ることを示しました。 ${\displaystyle {}^{2}E}$

すべての算術集合は超算術的ですが、他の多くの超算術集合も存在します。超算術的で非算術的な集合の一例は、標準の自然数 において真であるペアノ算術の式のゲーデル数の集合Tです。集合T は集合 とチューリング同値であるため、超算術階層では上位にありませんが、タルスキの定義不可能定理によって算術的に定義可能ではありません。 ${\displaystyle \mathbb {N} }$${\displaystyle 0^{(\omega )}}$

超算術理論の基本的な結果は、上記の 3 つの定義が同じ自然数の集合を定義していることを示しています。これらの同値性は Kleene によるものです。

完全性の結果も理論の基礎となる。自然数の集合が完全であるとは、それが解析階層のレベルにあり、すべての自然数の集合がその集合に多対一還元可能である場合である。ベール空間 ( ) の完全部分集合の定義も同様である。超算術理論に関連するいくつかの集合は完全である。 ${\displaystyle \Pi _{1}^{1}}$${\displaystyle \Pi _{1}^{1}}$${\displaystyle \Pi _{1}^{1}}$${\displaystyle \Pi _{1}^{1}}$${\displaystyle \mathbb {N} ^{\mathbb {N} }}$${\displaystyle \Pi _{1}^{1}}$

• クリーネの、順序数の表記である自然数の集合${\displaystyle {\mathcal {O}}}$
• 計算可能関数が自然数の整列順序の特性関数を計算するような自然数eの集合。これらは再帰的順序数のインデックスです。${\displaystyle \phi _{e}(x,y)}$
• 自然数の整列順序の特性関数であるベール空間の要素の集合（有効同型を使用）。${\displaystyle \mathbb {N} ^{\mathbb {N} }\cong \mathbb {N} ^{\mathbb {N} \times \mathbb {N} })}$

これらの完全性の結果から、境界と呼ばれる結果が導かれます。順序数表記の任意の集合Sに対して、 Sのすべての要素が未満の順序数の表記となるような が存在します。整列順序の特性関数のみで構成されるベール空間の任意の部分集合Tに対して、 Tで表される各順序数が未満となるが存在します。 ${\displaystyle \Sigma _{1}^{1}}$${\displaystyle \Sigma _{1}^{1}}$${\displaystyle \alpha <\omega _{1}^{CK}}$${\displaystyle \alpha }$${\displaystyle \Sigma _{1}^{1}}$${\displaystyle \alpha <\omega _{1}^{CK}}$${\displaystyle \alpha }$

の定義は、自然数の集合Xに相対化できます。つまり、順序表記の定義において、極限順序数の節が変更され、順序表記のシーケンスの計算可能な列挙で、X を神託として使用できるようになります。Xに相対的な順序表記である数の集合はと表されます。で表される順序数の上限は と表され、これは より小さくない可算順序数です。 ${\displaystyle {\mathcal {O}}}$${\displaystyle {\mathcal {O}}^{X}}$${\displaystyle {\mathcal {O}}^{X}}$${\displaystyle \omega _{1}^{X}}$${\displaystyle \omega _{1}^{CK}}$

の定義は、任意の自然数の集合に相対化することもできます。定義における唯一の違いは、 が空集合ではなくXとして定義されていることです。したがって、 はXのチューリングジャンプであり、以下同様です。 で終了するのではなく、 はXに対する階層構造で未満のすべての順序数にわたって実行されます。 ${\displaystyle 0^{(\delta )}}$${\displaystyle X}$${\displaystyle X^{(0)}}$${\displaystyle X^{(1)}=X'}$${\displaystyle \omega _{1}^{CK}}$${\displaystyle \omega _{1}^{X}}$

相対化された超算術的階層は、超算術的還元可能性を定義するために使用されます。集合XとY が与えられたとき、 Xが にチューリング還元可能であるようなが存在する場合のみ、 であると述べます。 の場合、という表記法を使用して、XとY が超算術的に同値であることを示します。 これは、チューリング同値よりも大まかな同値関係です。たとえば、自然数のすべての集合は、そのチューリングジャンプと超算術的に同値ですが、そのチューリングジャンプとチューリング同値ではありません。超算術的同値性の同値類は、超次数として知られています。 ${\displaystyle X\leq _{\text{HYP}}Y}$${\displaystyle \delta <\omega _{1}^{Y}}$${\displaystyle Y^{(\delta )}}$${\displaystyle X\leq _{\text{HYP}}Y}$${\displaystyle Y\leq _{\text{HYP}}X}$${\displaystyle X\equiv _{\text{HYP}}Y}$

集合Xを にする関数は、チューリング ジャンプとの類推によりハイパージャンプとして知られています。ハイパージャンプとハイパー次数の多くの特性が確立されています。特に、ハイパー次数に関するポストの問題には肯定的な答えがあることが知られています。つまり、自然数の集合Xごとに、 となる自然数の 集合Y が存在するということです。 ${\displaystyle {\mathcal {O}}^{X}}$${\displaystyle X<_{\text{HYP}}Y<_{\text{HYP}}{\mathcal {O}}^{X}}$

超算術理論は、許容順序数の定義可能な部分集合の研究であるα再帰理論によって一般化されます。超算術理論は、 αがである特殊なケースです。 ${\displaystyle \omega _{1}^{CK}}$

• H. Rogers , Jr. , 1967.再帰関数と効果的な計算可能性の理論、第 2 版 1987 年、MIT Press。ISBN 0-262-68052-1  (ペーパーバック)、ISBN 0-07-053522-1 
• G.サックス、1990年。高等再帰理論、シュプリンガー・フェアラーク。ISBN 3-540-19305-7 
• S. Simpson、1999年。「Subsystems of Second Order Arithmetic」、Springer-Verlag。
• CJ Ash、JF Knight、2000年。計算可能構造と超算術階層、Elsevier。ISBN 0-444-50072-3 

• 記述的集合論。イリノイ大学シカゴ校の David Marker によるメモ。2002 年。
• 数学論理学 II。ダグ・ノーマン著、オスロ大学。2005 年。
• アントニオ・モンタルバン：カリフォルニア大学バークレー校、YouTubeコンテンツクリエイター