數理邏輯中遞歸論的一部分。它的中心論題是用遞歸論為工具給出數集（問題集）或函式集的複雜性的某種排序。
基本介紹
- 中文名：分層理論
- 釋義：數理邏輯中遞歸論的一部分
- 實質：理論
- 詳細內容：見正文
簡介,詳解,分層定理,完備形式定理,
簡介
數理邏輯中遞歸論的一部分。它的中心論題是用遞歸論為工具給出數集（問題集）或函式集的複雜性的某種排序。
詳解
因為所謂算術集恰是自然數集 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型變元的量詞（函式量詞）則將增加定義的複雜性，從而引進解析分層。
關於亦有：前束詞中一串同類量詞可收縮凳拜鞏成一個；對任一算術謂詞，存在一個原始遞歸謂詞使有扽(,)可表為扽扽((),)即為 扽(,)等事實可以利用。故可將全體解析謂詞依以下形式分類：
(2)
其中為算術謂詞,為一般遞歸謂詞。這裡,同樣地可用及來表示(2)中所出現的謂詞,,只不過這時的是1型變元的量詞個數。這時,,其為一切算術謂詞的類，仍為的射影，而則為的對偶。對於,(≥1)亦有枚舉定理、分層定理以及完備定理等。而(2)也就給出了所有解析謂詞（解析集）的一個分類，稱之為解析分層。
分層理論
分層理論分層理論 
分層理論
分層理論
分層理論
分層理論
分層理論分層理論 分層理論 分層理論
分層理論分層理論分層理論分層理論分層理論分層理論分層理論分層理論分層理論分層理論分層理論設為一元函式集(嶅)，這時我們可以把所考慮的謂詞(,,…,,,,…,)推廣為算術於和解析於中任意有限多個函式的謂詞。這時所得到的妹槳危相應的分層，分別稱為－算術分層和－解析分層，並且分別記作和
分層理論
分層理論
分層理論分層理論關於集合算術分層和解析分層分別相應於無理數空間中的有限波萊爾集合射影集。J.W.艾迪生稱之為古典描民戒頌贈述集合論。與之相應的，關於集合的(即=═時)算術分層和解析分層的理論便稱之為能行描述集合論。
如果只考慮自然數謂詞(即在中，m=0的情形)，則可定義()為型謂詞(≥0),它在型的謂詞中具有最高級的遞歸不可解度，且其不可解度確實比()高，因而(=0,1,2,…)決定了遞歸不可解度的算術分層。克林用可構造序數的記法系統把序列推廣到以可構造序數作下標的不可解度分層即遞歸不可解度的超算術分層記作{|∈}，如果一函式或謂詞對於某∈，遞歸於，則稱此函式或謂詞是超算術的。使得一謂詞為超算術的其充要條件為它可以在墹姌中表示。
分層理論分層理論 分層理論
分層理論分層理論分層理論克林套用具有任意型變元(=0,1,2,…)的一般遞歸函式的理論，對具有任意型變元的謂詞建立了分層理論，使得原來的分層理論得到了進一步的推廣。
如果把上述的,,с,…，看成是集合變元（即,，с，…是表示集合的變元）即可得到萊維的分層。
當已經用到1型變元的量詞（函式量詞）則將增加定義的複雜性，從而引進解析分層。
關於亦有：前束詞中一串同類量詞可收縮成一個；對任一算術謂詞，存在一個原始遞歸謂詞使有扽(,)可表為扽扽((),)即為 扽(,)等事實可以利用。故可將全體解析謂詞依以下形式分類：
(2)
其中為算術謂詞,為一般遞歸謂詞。這裡,同樣地可用及來表示(2)中所出現的謂詞,,只不過這時的是1型變元的量詞個數。這時,,其為一切算術謂詞的類，仍為的射影，而則為的對偶。對於,(≥1)亦有枚舉定理、分層定理以及完備定理等。而(2)也就給出了所有解析謂詞（解析集）的一個分類，稱之為解析分層。分層理論 分層理論 分層理論 分層理論 分層理論 分層理論 分層理論 分層理論 分層理論 分層理論 分層理論
分層理論分層理論分層理論分層理論分層理論分層理論分層理論分層理論分層理論分層理論分層理論設為一元函式集(嶅)，這時我們可以把所考慮的謂詞(,,…,,,,…,)推廣為算術於和解析於中任意有限多個函式的謂詞。這時所得到的相應的分層，分別稱為－算術分層和－解析分層，並且分別記作和分層理論 分層理論
分層理論分層理論關於集合算術分層和解析分層分別相應於無理數空間中的有限波萊爾集合射影集。J.W.艾迪生稱之為古典描述集合論。與之相應的，關於集合的(即=═時)算術分層和解析分層的理論便稱之為能行描述集合論。
如果只考慮自然數謂詞(即在中，m=0的情形)，則可定義()為型謂詞(≥0),它在型的謂詞中具有最高級的遞歸不可解度，且其不可解度確實比()高，因而(=0,1,2,…)決定了遞歸不可解度的算術分層。克林用可構造序數的記法系統把序列推廣到以可構造序數作下標的不可解度分層即遞歸不可解度的超算術分層記作{|∈}，如果一函式或謂詞對於某∈，遞歸於，則稱此函式或謂詞是超算術的。使得一謂詞為超算術的其充要條件為它可以在墹姌中表示。分層理論 分層理論 分層理論
分層理論分層理論分層理論克林套用具有任意型變元(=0,1,2,…)的一般遞歸函式的理論，對具有任意型變元的謂詞建立了分層理論，使得原來的分層理論得到了進一步的推廣。
如果把上述的,,с,…，看成是集合變元（即,，с，…是表示集合的變元）即可得到萊維的分層。
