分層理論

　　數理邏輯中遞迴論的一部分。它的中心論題是用遞迴論為工具給出數集（問題集）或函數集的複雜性的某種排序。

　　因為所謂算術集恰是自然數集N中由一階公式定義的自然數集，而解析集則是由二階公式定義的自然數集。算術集構成解析集類的一個更易於定義的子類。同時，由於所有的遞迴集都是算術集，如把它們看成有同樣複雜的可定義性並用作討論的起點，這將是自然的。

　　同樣的，一一個遞歸可枚舉集A恰為{x｜彐yRxy}，其中R為一般遞歸謂詞，所以一切遞歸可枚舉集也是算術的，而由於一階公式對於邏輯運算¬和量詞彐(自然數變元)具有封閉性，所以任一算術集的補和射影依然是算術的，如此等等。在使用適當約定和稍作引伸之後，即可得到度量集合（數的或問題的）復雜性的一種排序稱之為算術分層。類似地可以建立解析分層，從而S.C.克林就利用遞歸論成功地建立瞭分層理論及其相應的推廣。

　　因為集合或函數均可用謂詞來表述，故以下的討論將就謂詞而言且將沿用遞歸函數中的符號和概念。

　　設α，b，с，…，x，y，z；α_i，b_i，с_i，…，x_i，y_i，z_i（i=1，2，…）為自然數集N上的變元（0型變元），α，β，…，α₁，α₂，…ξ，η，…為一元數論函數集N^N上的變元(1型變元)。若具有0型和1型兩種變元的謂詞P（α₁，α₂，…，α_m，α₁，α₂，…，α_n）（m，n≥0，m+n＞0）由一般遞歸模式出發，經過有限次使用邏輯運算：→，∨，∧，¬ 和量詞運算彐x，∀x，彐ξ，∀ξ，而得到，則稱謂詞P是解析謂詞。特別地，當P未用函數量詞彐ξ，∀ξ時，則稱之為算術謂詞。

　　由於每一個一階公式都有等價的前束范式，故可隻限於討論前束范式的情形並簡稱公式為謂詞，把序列(α₁，α₂，…，α_m，α₁，α₂，…，α_n)記成α，並將一前束范式的前束詞中，相同的一串量詞收縮為一個如

\ n

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

，其中 R為一般遞歸謂詞，同時，根據量詞的個數 k及公式最外邊的量詞是彐 還是∀而分別記成 型或 型（ 型的對偶形式）。例如，形如 彐 xR的謂詞全體記作 ，而形如∀ x彐 yR的謂詞全體則記作 。

　　把可以用兩種形式

及 來表示的謂詞全體記作 。

　　例如，易見

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

　　又如，

（此即一謂詞屬於 的充要條件為它是一般遞歸的）。

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

（或 ）的全體謂詞的枚舉謂詞。例如，對於 和 m= n=1而言，存在一個原始遞歸謂詞 S( α， z， α， x， y)，使得當任給一個一般遞歸謂詞 R( α， α， x， y)時，恒有自然數 f，使得

此即枚舉定理。在這個定理中，可將 S( α， f， α， x， y)取為 T屶( z， α， x， y)則有分層定理。

　　分層定理　對每一k≥0，都存在一個

型（ 型）謂詞，它不能在其對偶形式 ( )中得到表示。換言之，對每一正整數 k+1而言，有不是 的 型謂詞，也有不是 的 型謂詞。當然，有既不是 也不是 的 ( )型謂詞。亦有既不是 也不是 的 型謂詞，且有不是 的 型和 型謂詞。

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

　　完備形式定理　對於每一個k≥1，都存在一個關於

( )的完備謂詞，即存在一個一元的 ( )，使得任一 型（ 型）謂詞都可由將該謂詞的變元代以一適當的原始遞歸函數來表示，等等。

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

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

　 (2)

其中 Q為算術謂詞， R為一般遞歸謂詞。這裡，同樣地可用 Σ 及 Π 來表示(2)中所出現的謂詞， ，隻不過這時的 k是1型變元的量詞個數。這時， ，其為一切算術謂詞的類， 仍為 Π 的射影，而 則為 的對偶。對於 Σ ， Π ( k≥1)亦有枚舉定理、分層定理以及完備定理等。而(2)也就給出瞭所有解析謂詞（解析集）的一個分類，稱之為解析分層。

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

和

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

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

l _{K +1}( α)為 型謂詞( k≥0)，它在 型的謂詞中具有最高級的遞歸不可解度，且其不可解度確實比 L _K( α)高，因而 l _K( k=0，1，2，…)決定瞭遞歸不可解度的算術分層。克林用可構造序數的記法系統把 l _k序列推廣到以可構造序數作下標的不可解度分層即遞歸不可解度的超算術分層記作{ H _y｜ y∈ O}，如果一函數或謂詞對於某 y∈ O，遞歸於 h _y，則稱此函數或謂詞是超算術的。使得一謂詞為超算術的其充要條件為它可以在Δ ₁ ¹中表示。

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

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