相對解析分層

概念

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

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

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

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

4.Δ^1,A_n=Σ^1,A_n∩π^1,A_n。

Σ^1,A_n，π^1,A_n與Δ^1,A_n中的關係分別稱為Σ^1,A_n關係，π^1,A_n關係與Δ^1,A_n關係。此外，用Δ^1,A_w表示∪{Σ^1,A_n∪π^1,A_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對二階量詞ᗄ′封閉。

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

遞歸關係是序列的項之間的一種關係。指序列的任一項均被其前若干項所確定的那種關係。對於數列{a_n|n=0，1，2，…}，若當n≥0時，恆有關係式：

a_n+k=F(a_n+k-1，…，a_n)，