Π 0 1クラス

計算可能性理論において、Π ⁰ ₁クラスは、ある特定の形式の 2 ^ωの部分集合です。これらのクラスは、再帰理論や有効記述集合理論における技術的なツールとして興味深いものです。また、再帰理論を他の数学分野に応用する際にも使用されます (Cenzer 1999、p.  39)。

集合 2 ^{<ω は}、0 と 1 のすべての有限列から構成され、集合 2 ^{ωは、0 と 1 のすべての無限列 (つまり、} ω = {0, 1, 2, ... }から集合{0,1 } への関数) から構成されます。

2 ^<ω上の木とは、初期セグメントを取る操作に関して閉じている2 ^{<ωの部分集合のことである。2 ω}の要素fは、 fのすべての有限初期セグメントがTに含まれる場合、 2 ^{< ω}上の木Tを通るパスである。

(ライトフェイス) Π ⁰ ₁クラスは、 2 ^ωの部分集合Cであり、 C がTを通るパスのみで構成されるような計算可能な木Tが存在する。太字のΠ ⁰ ₁クラスは、2 ^ωの部分集合Dであり、2 ^ωにオラクルfがあり、 fから計算可能な2 ^{< ω}の部分木T が存在し、D がTを通るパスの集合である。

太字のΠ ⁰ _{1クラスは}^2ωの閉集合と全く同じであり、したがってボレル階層における^{2ωの太字のΠ 0} ₁部分集合と同じである。

^2ωのLightface Π ⁰ ₁クラス(つまり、オラクルなしで木を計算できるΠ ⁰ _{1クラス) は}、実質的に閉じた集合に対応します。2ωの部分集合Bは、2 ^{< ω}の要素の再帰的に列挙可能なシーケンス⟨ σ _i : i ∈ ω ⟩が存在し、各g ∈ 2 ^ωがB に含まれるのは、 σ _iがBの初期セグメントとなるようなi が存在しない場合に限る、という条件が満たされる場合に、実質的に閉じています。 

一階述語論理の有効に公理化された理論Tごとに、 Tのすべての完了の集合は$\displaystyle \Pi _{1}^{0}}$クラスごとに。さらに、各クラスについて$\displaystyle \Pi _{1}^{0}}$サブセットSの$2ω$効果的に公理化された理論Tが存在し、 Sの各要素はTの完全性を計算し、Tの各完全性はSの要素を計算します(Jockusch と Soare 1972b)。  

• 算術階層
• 基底定理（計算可能性）

• センザー、ダグラス（1999）「$\displaystyle \Pi _{1}^{0}}$「計算可能性理論におけるクラス」、計算可能性理論ハンドブック、Stud. Logic Found. Math.、第140巻、アムステルダム：North-Holland、 37～85 ページ、 MR 1720779  
• ジョックシュ、カール G.、ソアレ、ロバート I. (1972a)、「会員の学位$\displaystyle \Pi _{1}^{0}}$「クラス。」(PDF)、Pacific Journal of Mathematics、40 (3): 605–616、doi : 10.2140/pjm.1972.40.605
• ジョクシュ、カール G.ソアレ、ロバート I. (1972b)、」$\displaystyle \Pi _{1}^{0}}$「理論のクラスと次数」、アメリカ数学会紀要、173 : 33–56、doi : 10.1090/s0002-9947-1972-0316227-0