分層理論

因為所謂算術集恰是自然數集 N中由一階公式定義的自然數集，而解析集則是由二階公式定義的自然數集。算術集構成解析集類的一個更易於定義的子類。同時，由於所有的遞歸集都是算術集，如把它們看成有同樣複雜的可定義性並用作討論的起點，這將是自然的。同樣的，一個遞歸可枚舉集A恰為{x|扽yRxy}，其中R為一般遞歸謂詞，所以一切遞歸可枚舉集也是算術的，而由於一階公式對於邏輯運算塡和量詞彐(自然數變元)具有封閉性，所以任一算術集的補和射影依然是算術的，如此等等。在使用適當約定和稍作引伸之後，即可得到度量集合（數的或問題的）複雜性的一種排序稱之為算術分層。類似地可以建立解析分層，從而S.C.克林就利用遞歸論成功地建立了分層理論及其相應的推廣。因為集合或函數均可用謂詞來表述，故以下的討論將就謂詞而言且將沿用遞歸函數中的符號和概念。設α,b,с,…,x,y,z;αi,bi,сi,…,xi,yi,zi（i=1,2,…）為自然數集N上的變元（0型變元）,α，β,…,α1，α2,…ξ,η,…為一元數論函數集NN上的變元(1型變元)。若具有0型和1型兩種變元的謂詞 P（α1,α2,…,αm,α1,α2,…,αn）（m,n≥0,m+n>0）由一般遞歸模式出發，經過有限次使用邏輯運算：→,∨,∧,塡 和量詞運算扽x,凬x,扽ξ,凬ξ，而得到，則稱謂詞P是解析謂詞。特別地，當P未用函數量詞扽ξ,凬ξ 時，則稱之為算術謂詞。由於每一個一階公式都有等價的前束範式，故可只限於討論前束範式的情形並簡稱公式為謂詞，把序列(α1,α2,…,αm,α1,α2,…,αn)記成α,並將一前束範式的前束詞中，相同的一串量詞收縮為一個如

這樣，一謂詞是算術的即是可表成下列形式之一：

,其中為一般遞歸謂詞，同時，根據量詞的個數及公式最外邊的量詞是扽 還是凬而分別記成

型或

型（

型的對偶形式）。例如，形如 扽的謂詞全體記作

，而形如凬扽的謂詞全體則記作

。

把可以用兩種形式

及

來表示的謂詞全體記作

。

例如，易見

（此即把遞歸集定義作最簡單的算術集）。

又如，

（此即一謂詞屬於

的充要條件為它是一般遞歸的）。

在≥1的情形，恆存在一個枚舉類

（或

）的全體謂詞的枚舉謂詞。例如，對於

和m==1而言，存在一個原始遞歸謂詞(,,,,)，使得當任給一個一般遞歸謂詞(,,,)時，恆有自然數，使得

此即枚舉定理。在這個定理中，可將(,,,,)取為屶(,,,)則有分層定理。

對每一≥0，都存在一個

型（

型）謂詞，它不能在其對偶形式

(

)中得到表示。換言之，對每一正整數+1而言，有不是

的

型謂詞，也有不是

的

型謂詞。當然，有既不是

也不是

的

(

)型謂詞。亦有既不是

也不是

的

型謂詞，且有不是

的

型和

型謂詞。

所以，這就得到了一個方便的分層(1)來給算術謂詞（算術集）分類。這個分層稱為算術分層。

對於每一個≥1，都存在一個關於

(

)的完備謂詞，即存在一個一元的

(

)，使得任一

型（

型）謂詞都可由將該謂詞的變元代以一適當的原始遞歸函數來表示，等等。

當已經用到1型變元的量詞（函數量詞）則將增加定義的複雜性，從而引進解析分層。

關於亦有：前束詞中一串同類量詞可收縮成一個；對任一算術謂詞，存在一個原始遞歸謂詞使有扽(,)可表為扽扽((),)即為 扽(,)等事實可以利用。故可將全體解析謂詞依以下形式分類：

(2)

其中為算術謂詞，為一般遞歸謂詞。這裡，同樣地可用

及

來表示(2)中所出現的謂詞,

,只不過這時的是1型變元的量詞個數。這時,

,其為一切算術謂詞的類，

仍為

的射影，而

則為

的對偶。對於

,

(≥1)亦有枚舉定理、分層定理以及完備定理等。而(2)也就給出了所有解析謂詞（解析集）的一個分類，稱之為解析分層。

設為一元函數集(嶅)，這時我們可以把所考慮的謂詞(,,…,,,,…,)推廣為算術於和解析於中任意有限多個函數的謂詞。這時所得到的相應的分層，分別稱為－算術分層和－解析分層，並且分別記作

和

關於集合算術分層和解析分層分別相應於無理數空間中的有限波萊爾集合射影集。J.W.艾迪生稱之為古典描述集合論。與之相應的，關於集合的(即=═時)算術分層和解析分層的理論便稱之為能行描述集合論。

如果只考慮自然數謂詞(即在中，m=0的情形)，則可定義

()為

型謂詞(≥0),它在

型的謂詞中具有最高級的遞歸不可解度，且其不可解度確實比()高，因而(=0,1,2,…)決定了遞歸不可解度的算術分層。克林用可構造序數的記法系統把序列推廣到以可構造序數作下標的不可解度分層即遞歸不可解度的超算術分層記作{|∈}，如果一函數或謂詞對於某∈，遞歸於，則稱此函數或謂詞是超算術的。使得一謂詞為超算術的其充要條件為它可以在墹姌中表示。

克林應用具有任意型變元(=0,1,2,…)的一般遞歸函數的理論，對具有任意型變元的謂詞建立了分層理論，使得原來的分層理論得到了進一步的推廣。

如果把上述的,,с,…，看成是集合變元（即,，с，…是表示集合的變元）即可得到萊維的分層。