相對解析分層

概念

相對解析分層(relativized analytical bierarchy)是解析分層概念的相對化。即對相對算術關係依量詞複雜性進行的遞歸論分層。具體地，對自然數集A，相對A的解析分層Σ_n，π_n與Δ_n可遞歸定義如下：

1.Σ₀=π₀={R：R為相對A的算術關係}。

2.Σ_n+1={(∃′f)R(f，f₁，f₂，…，f_k，x₁，x₂，…，x_m)：R∈π_n}。

3.π_n+1={(ᗄ′f)R(f，f₁，f₂，…，f_k，x₁，x₂，…，x_m)：R∈Σ_n}。

4.Δ_n=Σ_n∩π_n。

Σ_n，π_n與Δ_n中的關係分別稱為Σ_n關係，π_n關係與Δ_n關係。此外，用Δ_w表示∪{Σ_n∪π_n：n∈w}，即所有相對A的解析關係的集合。

解析分層亦稱解析譜系。按照量詞複雜性對解析關係所作的遞歸論分層。與算術分層類似，任何解析關係可以用算術關係加上有窮個交替出現的二階函式量詞ᗄ′與∃′表示，依照量詞個數，可以將該解析關係納入具體的解析分層Σ_n或π_n中。形式地，具體的解析分層Σ_n，π_n，Δ_n可遞歸定義如下：

1.Σ₀=π₀={R：R為算術關係}。

2.Σ_n+1={(∃′f)R(f，f₁，f₂，…，f_k，x₁，x₂，…，x_m)：R∈π_n}.

3.π_n+1={(ᗄ′f)R(f，f₁，f₂，…，f_k，x₁，x₂，…，x_m)：R∈Σ_n}。

4.Δ_n=Σ_n∩π_n.

Σ_n，π_n與Δ_n中的關係分別稱為Σ_n關係、π_n關係與Δ_n關係，此外，Δ_w定義為：∪{Σ_n∪π_n：n∈ω}，即所有解析關係的集合。此外，對n≥1，Σ_n關係可表示成下形範式：

(∃′f₁)(ᗄ′f₂)…(Q_nf_n)(Qx)

R(f₁，…，f_n，f_n+1，…，f_n+p，x，x₁，…，x_q)，

其中若n為偶數，Q_n為ᗄ′，Q為∃；若n為奇數，Q_n為∃′，Q為ᗄ；而R為遞歸關係。π_n關係也可表示成以ᗄ′開頭的類似表達式.解析分層還具有如下封閉性：

1.Σ_n，π_n，Δ_n對合取、析取運算與一階量詞封閉。

2.Δ_n對否定運算封閉。

3.R∈Σ_n，若且唯若ᒣR∈π_n；

R∈π_n，若且唯若ᒣR∈Σ_n。

4.對n≥1，Σ_n對二階量詞∃′封閉，π_n對二階量詞ᗄ′封閉。

關於解析分層的其他性質，參見“解析枚舉定理”。此外，與算術分層不同，Δ₁≠Σ₀=π₀=Δ₀，Δ₁的關係稱為超算術關係。