超算術理論

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

超算術理論の中心となるのは、超算術集合と呼ばれる自然数の集合である。この集合のクラスを定義する方法は3つあり、それらは互いに同等である。これらの異なる定義間の関係性を研究することが、超算術理論の研究の動機の一つとなっている。

超算術集合の最初の定義では、解析的階層を使用します。自然数の集合はレベルに分類されます。${\displaystyle \Sigma _{1}^{1}}$この階層構造において、存在量化子のみを含む2階算術式で定義可能であり、他の量化子を含まない場合、集合はレベルに分類されます。$\displaystyle \Pi _{1}^{1}}$分析階層の集合は、全称集合量化子のみを含む2階算術の式で定義可能であり、他の集合量化子は含まない。集合は${\displaystyle \Delta _{1}^{1}}$両方である場合${\displaystyle \Sigma _{1}^{1}}$そして$\displaystyle \Pi _{1}^{1}}$超算術集合はまさに${\displaystyle \Delta _{1}^{1}}$セット。

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

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

順序表記とは、可算順序数を自然数で効果的に記述する方法である。超算術階層を定義するには、順序表記体系が必要となる。順序表記が持つべき基本的な性質は、順序数をより小さな順序数で効果的に記述することである。以下の帰納的定義は典型的な例であり、ペアリング関数を用いる。${\displaystyle \langle \cdot ,\cdot \rangle }$。

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

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

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

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

• δ = 0 の場合${\displaystyle 0^{(\delta )}=0}$は空集合です。
• δ = λ + 1 の場合$\displaystyle 0^{(\delta )}}$チューリングジャンプは${\displaystyle 0^{(\lambda )}}$セット$0^(1)$そして$0^(2)$は${\displaystyle 0'}$そして${\displaystyle 0''}$、 それぞれ。
• δが極限順序数である場合、${\displaystyle \langle \lambda _{n}\mid n\in \mathbb {N} \rangle }$δより小さい順序数の列を表記eで表す。${\displaystyle 0^{(\delta )}}$ルールによって与えられる${\displaystyle 0^{(\delta )}=\{\langle n,i\rangle \mid i\in 0^{(\lambda _{n})}\}}$これは、セットの実効的な結合です。${\displaystyle 0^{(\lambda _{n})}}$。

建設中${\displaystyle 0^{(\delta )}}$δの固定表記に依存し、各無限順序数には多くの表記があり、クリフォード・スペクターの定理はチューリング次数が${\displaystyle 0^{(\delta )}}$δのみに依存し、特定の表記法には依存しないため、${\displaystyle 0^{(\delta )}}$チューリング次数まで明確に定義されている。^{[ 2 ]}

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

させて${\displaystyle L_{\alpha }}$を示す${\displaystyle \alpha }$構築可能な階層の 番目のレベルとし、${\displaystyle n:{\mathcal {O}}\to \omega _{1}^{CK}}$クリーネの Oの要素からそれが表す順序数への写像とする。${\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}}$これはレヴィの公式階層に属する。^{[ 4 ]}

スペクター・ガンディの定理は、部分集合が${\displaystyle x}$の${\displaystyle \mathbb {N} }$定義可能${\displaystyle \Pi _{1}^{1}}$式は、ある場合に限り成り立つ。${\displaystyle \Sigma _{1}}$式${\displaystyle \phi (u)}$そのため${\displaystyle n\in x}$もし${\displaystyle L_{\omega _{1}^{CK}}\vDash \phi (n)}$[ ^{5 ]定理3.7.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が挙げられる。${\displaystyle \mathbb {N} }$集合Tは、集合とチューリング同値である。${\displaystyle 0^{(\omega )}}$そのため、超算術的階層では上位には位置づけられていないが、タルスキの不確定性定理によって算術的に定義できるものでもない。

超算術理論の基本的な結果は、上記の３つの定義が同一の自然数の集合を定義することを示している。これらの同値性はクリーネによるものである。別の特徴付けは、ススリン・クリーネの定理によって与えられる。

完全性の結果も理論の基礎となる。自然数の集合は${\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}}}$順序数を表す表記法としての自然数の集合
• 計算可能な関数が${\displaystyle \phi _{e}\colon \mathbb {N} ^{2}\to 2}$自然数の整列の特性関数を計算します。これらは再帰的順序数のインデックスです。
• ベール空間の要素のうち、自然数の整列（有効な同型写像を使用）の特性関数である要素の集合${\displaystyle \mathbb {N} ^{\mathbb {N} }\cong \mathbb {N} ^{\mathbb {N} \times \mathbb {N} })}$。

結果が知られている${\displaystyle \Sigma _{1}^{1}}$これらの完全性の結果から境界が導かれる。${\displaystyle \Sigma _{1}^{1}}$順序表記の集合Sには、${\displaystyle \alpha <\omega _{1}^{CK}}$Sのすべての要素は、より小さい順序数を表す表記である。${\displaystyle \alpha }$どのような場合でも${\displaystyle \Sigma _{1}^{1}}$ベール空間のサブセットT は、整列の特性関数のみで構成されており、${\displaystyle \alpha <\omega _{1}^{CK}}$Tで表される各序数は以下より小さい${\displaystyle \alpha }$。

の定義${\displaystyle {\mathcal {O}}}$自然数の集合Xに対して相対化することができます。順序表記の定義において、極限順序数に関する条項が変更され、順序表記のシーケンスの計算可能な列挙においてX をオラクルとして使用できるようになります。Xに対して順序表記である数の集合は、次のように表されます。${\displaystyle {\mathcal {O}}^{X}}$順序数の上限は${\displaystyle {\mathcal {O}}^{X}}$と表記される${\displaystyle \omega _{1}^{X}}$; これは、以下より小さい可算序数ではありません${\displaystyle \omega _{1}^{CK}}$。

の定義${\displaystyle 0^{(\delta )}}$任意の集合に対して相対化することもできる${\displaystyle X}$自然数の。定義の唯一の変更点は、${\displaystyle X^{(0)}}$は空集合ではなくXとして定義されるため、${\displaystyle X^{(1)}=X'}$はXのチューリングジャンプであり、以下同様です。${\displaystyle \omega _{1}^{CK}}$Xに関する階層は、より小さいすべての序数を通っています。${\displaystyle \omega _{1}^{X}}$。

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

セットXを受け取り、${\displaystyle {\mathcal {O}}^{X}}$は、チューリングジャンプとの類推からハイパージャンプとして知られています。ハイパージャンプとハイパーデグリーの多くの性質が確立されています。特に、ハイパーデグリーに関するポストの問題には肯定的な答えがあることが知られています。すなわち、自然数の任意の集合Xに対して、自然数の 集合Yが存在し、${\displaystyle X<_{\text{HYP}}Y<_{\text{HYP}}{\mathcal {O}}^{X}}$。

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

• H. ロジャーズ・ジュニア、1967年。『再帰関数と有効計算可能性の理論』、第2版1987年、MIT Press。ISBN 0-262-68052-1（ペーパーバック）、ISBN 0-07-053522-1
• G. Sacks、1990年。 『高次再帰理論』、 Springer-Verlag。ISBN 3-540-19305-7
• S. シンプソン、1999年。『2階算術のサブシステム』、シュプリンガー・フェルラーク。
• CJ Ash、JF Knight、2000年。『計算可能な構造と超算術階層』、Elsevier。ISBN 0-444-50072-3

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