算術的階層
算術的階層（Arithmetical hierarchy）は、数理論理学において、集合を定義する数式の複雑さに基づいて集合を分類する手法です。クリーネ階層とも呼ばれ、この分類が可能な集合は算術的であるとされます。再帰理論やペアノ算術のような形式理論の研究において、中心的な役割を果たしています。
算術的階層では、ペアノ算術の言語で記述された数式を分類します。この階層は、自然数 n を用いて Σ_n^0 および Π_n^0 と表記されます。ギリシア文字は細活字で表され、式に集合パラメータが含まれないことを示しています。
式 φ が有界量化子のみを含む式と論理的に等価である場合、φ は階層 Σ_0^0 および Π_0^0 に属します。階層 Σ_n^0 と Π_n^0 は、全ての自然数 n に対して以下のように帰納的に定義されます。
あらゆる式は等価な冠頭標準形に変換できるため、集合量化子を含まないすべての式は少なくとも1つの階層に分類されます。式に無意味な量化子を追加できることから、Σ_n^0 または Π_n^0 に分類される式は、n よりも大きい任意の m に対して、Σ_m^0 と Π_m^0 にも分類可能です。したがって、最も重要な分類は最小の n に対応する階層であり、そこから他の分類が決定されます。
ペアノ算術の言語で書かれた式 φ(n) によって、集合 X が n ∈ X ↔ N ⊨ φ(n) のように定義されるとします。これは、X の要素が φ を満たす数であることを意味します。一階算術で定義可能な自然数の集合 X は、自然数 n を用いて、階層 Σ_n^0, Π_n^0, Δ_n^0 に分類されます。
Δ_n^0 に属する式という概念は、実質的に意味を持ちません。なぜなら、これは先頭の量化子が全称量化子か存在量化子のいずれかである式を意味するからです。Δ_n^0 に属する集合は、Σ_n^0 に属する式と Π_n^0 に属する式の両方で定義される集合を指します。
自然数の有限な直積集合の算術的階層は、複数の自由変項を持つ式を用いて定義されます。k 個の自由変項を持つ式を使用することで、k タプルの自然数の集合に対する算術的階層を定義できます。
集合 X が集合 Y に対して再帰的相対性を持つとは、Y を一種の神託機械として X を決定できることを意味します。この概念を算術的階層全体に拡張し、Y に対して X が Σ_n^0, Δ_n^0, Π_n^0 である場合をそれぞれ Σ_n^(0,Y), Δ_n^(0,Y), Π_n^(0,Y) と記述します。このために、整数の集合 Y を固定し、ペアノ算術の言語に Y のメンバーシップ述語を追加します。X が Σ_n^(0,Y) に属するとは、この拡張された言語で記述された Σ_n^0 の式によって定義されることを意味します。つまり、X が Σ_n^(0,Y) に属するとは、Y への所属を問うことが許可された Σ_n^0 に属する論理式で定義されることを意味します。
例えば、Y を整数の集合とし、X をある Y の元で割り切れる数の集合とします。このとき、X は式 φ(n) = ∃m∃t(Y(m) ∧ m × t = n) で定義されるため、X は Σ_1^(0,Y) に属します。実際には、二つの量化子を n で制限できるので、Δ_0^(0,Y) に属します。
算術還元性は、チューリング還元性と超算術還元性の中間的な概念です。集合が算術的であるとは、ペアノ算術の言語で書かれた式で定義されるか、何らかの整数 n に対して Σ_n^0 または Π_n^0 に属することを意味します。集合 X が集合 Y において算術的であるとは、X ≤_A Y で表され、Y のメンバーシップ述語で拡張されたペアノ算術の言語で書かれた式で X を定義できることを意味します。これは、ある整数 n に対して X が Σ_n^(0,Y) または Π_n^(0,Y) に属することと同等です。X ≤_A Y は、X が Y に算術還元可能であることを意味します。
X ≤_A Y は反射的かつ推移的な関係であり、関係 X ≡_A Y ⇔ X ≤_A Y ∧ Y ≤_A X を定義すると、これは同値関係となります。この関係における同値類を算術次数と呼びます。これらは ≤_A のもとで半順序的です。
数式の算術的階層
算術的階層では、ペアノ算術の言語で記述された数式を分類します。この階層は、自然数 n を用いて Σ_n^0 および Π_n^0 と表記されます。ギリシア文字は細活字で表され、式に集合パラメータが含まれないことを示しています。
式 φ が有界量化子のみを含む式と論理的に等価である場合、φ は階層 Σ_0^0 および Π_0^0 に属します。階層 Σ_n^0 と Π_n^0 は、全ての自然数 n に対して以下のように帰納的に定義されます。
- - ψ が Π_n^0 であるとき、∃n₁...∃nₖψ という形式と論理的に等価な式 φ は階層 Σ_(n+1)^0 に属します。
- - ψ が Σ_n^0 であるとき、∀nₗ...∀nₖψ という形式と論理的に等価な式 φ は階層 Π_(n+1)^0 に属します。
あらゆる式は等価な冠頭標準形に変換できるため、集合量化子を含まないすべての式は少なくとも1つの階層に分類されます。式に無意味な量化子を追加できることから、Σ_n^0 または Π_n^0 に分類される式は、n よりも大きい任意の m に対して、Σ_m^0 と Π_m^0 にも分類可能です。したがって、最も重要な分類は最小の n に対応する階層であり、そこから他の分類が決定されます。
自然数の集合の算術的階層
ペアノ算術の言語で書かれた式 φ(n) によって、集合 X が n ∈ X ↔ N ⊨ φ(n) のように定義されるとします。これは、X の要素が φ を満たす数であることを意味します。一階算術で定義可能な自然数の集合 X は、自然数 n を用いて、階層 Σ_n^0, Π_n^0, Δ_n^0 に分類されます。
- - X が Σ_n^0 に属する式で定義可能ならば、X は階層 Σ_n^0 に分類されます。
- - X が Π_n^0 に属する式で定義可能ならば、X は階層 Π_n^0 に分類されます。
- - X が Σ_n^0 と Π_n^0 の両方に属するならば、X は追加の階層 Δ_n^0 に分類されます。
Δ_n^0 に属する式という概念は、実質的に意味を持ちません。なぜなら、これは先頭の量化子が全称量化子か存在量化子のいずれかである式を意味するからです。Δ_n^0 に属する集合は、Σ_n^0 に属する式と Π_n^0 に属する式の両方で定義される集合を指します。
自然数の有限な直積集合の算術的階層は、複数の自由変項を持つ式を用いて定義されます。k 個の自由変項を持つ式を使用することで、k タプルの自然数の集合に対する算術的階層を定義できます。
相対化算術的階層
集合 X が集合 Y に対して再帰的相対性を持つとは、Y を一種の神託機械として X を決定できることを意味します。この概念を算術的階層全体に拡張し、Y に対して X が Σ_n^0, Δ_n^0, Π_n^0 である場合をそれぞれ Σ_n^(0,Y), Δ_n^(0,Y), Π_n^(0,Y) と記述します。このために、整数の集合 Y を固定し、ペアノ算術の言語に Y のメンバーシップ述語を追加します。X が Σ_n^(0,Y) に属するとは、この拡張された言語で記述された Σ_n^0 の式によって定義されることを意味します。つまり、X が Σ_n^(0,Y) に属するとは、Y への所属を問うことが許可された Σ_n^0 に属する論理式で定義されることを意味します。
例えば、Y を整数の集合とし、X をある Y の元で割り切れる数の集合とします。このとき、X は式 φ(n) = ∃m∃t(Y(m) ∧ m × t = n) で定義されるため、X は Σ_1^(0,Y) に属します。実際には、二つの量化子を n で制限できるので、Δ_0^(0,Y) に属します。
算術還元性と次数
算術還元性は、チューリング還元性と超算術還元性の中間的な概念です。集合が算術的であるとは、ペアノ算術の言語で書かれた式で定義されるか、何らかの整数 n に対して Σ_n^0 または Π_n^0 に属することを意味します。集合 X が集合 Y において算術的であるとは、X ≤_A Y で表され、Y のメンバーシップ述語で拡張されたペアノ算術の言語で書かれた式で X を定義できることを意味します。これは、ある整数 n に対して X が Σ_n^(0,Y) または Π_n^(0,Y) に属することと同等です。X ≤_A Y は、X が Y に算術還元可能であることを意味します。
X ≤_A Y は反射的かつ推移的な関係であり、関係 X ≡_A Y ⇔ X ≤_A Y ∧ Y ≤_A X を定義すると、これは同値関係となります。この関係における同値類を算術次数と呼びます。これらは ≤_A のもとで半順序的です。
関連項目
- - 再帰理論
- - ポストの定理
参考文献
- - G.Japaridze, "The logic of the arithmetical hierarchy", Annals of Pure and Applied Logic 66 (1994), pp.89-112.
- - Moschovakis, Yiannis N. (1980年). Descriptive Set Theory. North Holland. ISBN 0-444-70199-0
- - Rogers, H. (1967年). Theory of recursive functions and effective computability. McGraw-Hill
もう一度検索
【記事の利用について】
タイトルと記事文章は、記事のあるページにリンクを張っていただければ、無料で利用できます。
※画像は、利用できませんのでご注意ください。
【リンクついて】
リンクフリーです。