PA学位

計算可能性理論という数学の分野において、PA 次数はペアノ算術の完全な拡張を計算するチューリング次数です (Jockusch 1987)。これらの次数は固定小数点フリー (DNR) 関数と密接に関連しており、再帰理論で徹底的に研究されてきました。

再帰理論では、計算可能関数の標準的な番号付けにおいて、インデックス（プログラム）eを持つ計算可能関数を表し、自然数の集合B を神託として 使用して、 e番目の計算可能関数を表します。${\displaystyle \phi _{e}}$${\displaystyle \phi _{e}^{B}}$

自然数の集合Aが集合Bにチューリング還元可能であるとは、集合Bの神託が与えられたときに集合Aの特性関数χ _Aを計算する計算可能な関数が存在する場合です。つまり、となるeが存在します。この関係はA ≤ _T Bと表され、関係 ≤ _Tは前順序です。 ${\displaystyle \chi _{A}=\phi _{e}^{B}}$

2 つの自然数の集合は、それぞれが他方にチューリング還元可能である場合、チューリング同値です。表記A ≡ _T B は、AとBがチューリング同値であることを示します。関係 ≡ _Tは、チューリング同値として知られる同値関係です。チューリング次数は、自然数の集合のコレクションであり、そのコレクション内の任意の 2 つの集合はチューリング同値です。同様に、チューリング次数は、関係 ≡ _Tの同値クラスです。

チューリング次数は、チューリング還元可能性によって部分的に順序付けられます。表記a ≤ _T b は、次数bのセットがあり、次数aのセットを計算することを示します。同様に、 b のすべてのセットがaのすべてのセットを計算する場合にのみ、a ≤ _T b が成立します。

自然数から自然数への関数fは、すべてのnに対して、が成り立つ場合、対角非再帰的 (DNR)であると言われます(ここで、 が定義されていない場合、不等式は定義により成立します)。 fの範囲が集合 {0,1} である場合、 fは DNR ₂関数です。 DNR ₂関数を計算しない DNR 関数があることが知られています。 ${\displaystyle f(n)\not =\phi _{n}(n)}$${\displaystyle \phi _{n}(n)}$

ペアノ算術の完備化とは、ペアノ算術の言語における式の集合であり、その集合は一階述語論理に矛盾がなく、各式について、その式またはその否定のいずれかが集合に含まれるようなものである。ペアノ算術の言語における式のゲーデル番号が固定されると、自然数の集合を持つペアノ算術の完備化を識別し、これらの完備化の計算可能性について話すことができる。

チューリング次数がペアノ算術の完成を計算する自然数の集合である場合、その次数はPA 次数であると定義されます。(これは、次数内のすべての集合が PA の完成を計算するという命題に相当します。) PA の計算可能な完成は存在しないため、計算可能な自然数の集合で構成される次数0 はPA 次数ではありません。

PA は有効な一階理論であるため、PA の完備化は 2 ^<ωの特定の計算可能なサブツリーを通る無限パスとして特徴付けることができます。したがって、PA の次数はまさにこのツリーを通る無限パスを計算する次数です。

PA 次数はチューリング次数において上向きに閉じています。つまり、a がPA 次数であり、a ≤ _T bである場合、b はPA 次数です。

停止問題の次数であるチューリング次数0 ' はPA 次数です。0 'より大きくない PA 次数もあります。たとえば、低基底定理は低 PA 次数が存在することを意味します。一方、Antonín Kučera は、DNR 関数を計算する0 ' 未満の次数が存在するが、これは PA 次数ではないことを証明しました (Jockusch 1989:197)。

Carl JockuschとRobert Soare (1972) は、PA の度合いが DNR ₂関数 の度合いとまったく同じであることを証明しました。

定義により、次数が PA となるのは、ペアノ算術の完備化の木を通るパスを計算する場合のみです。より強い特性として、次数a がPA 次数となるのは、 a が2 ^<ωのすべての無限計算可能部分木を通るパスを計算する場合のみです (Simpson 1977)。

MM Arslanov は、どの ce 集合が完全であるか (つまり、 のチューリング同値) の特徴付けを行いました。 ce 集合 の場合、が DNR 関数を計算するのは の場合のみであり、特に、すべての PA 次数は DNR ₂であるため DNR となり、唯一の ce PA 次数は となります。 ${\displaystyle \varnothing '}$${\displaystyle A\subseteq \mathbb {N} }$${\displaystyle A\equiv _{\mathrm {T} }\varnothing '}$${\displaystyle A}$${\displaystyle \varnothing '}$

• 基底定理（計算可能性）
• ケーニッヒの補題

• Carl Jockusch (1987)、「不動点のない関数の次数」、Logic Colloquium '87、Fenstad、Frolov、Hilpinen 編、North-Holland、ISBN  0-444-88022-4
• Carl Jockusch と Robert Soare (1972)、「Π ⁰ _{1 の}クラスと理論の次数」、アメリカ数学会誌、v. 173、pp. 33–56。
• Stephen G. Simpson (1977)、「解決不可能性の度合い: 結果の調査」、Handbook of Mathematical Logic、Barwise (ed.)、North-Holland、pp. 631–652。ISBN 0-444-86388-5