分層理論

簡介

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

詳解

因為所謂算術集恰是自然數集 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型變元的量詞（函式量詞）則將增加定義的複雜性，從而引進解析分層。
關於亦有：前束詞中一串同類量詞可收縮成一個；對任一算術謂詞，存在一個原始遞歸謂詞使有扽(,)可表為扽扽((),)即為扽(,)等事實可以利用。故可將全體解析謂詞依以下形式分類：

分層理論

分層理論

基本介紹

簡介

詳解

分層定理

完備形式定理

相關詞條

熱門詞條