分层理论

数理逻辑中递归论的一部分。来自它的中心论题是用递归论为工具给出数集(问题集)或函数集的复杂性的某种排序。

• 中文名称 分层理论
• 释义 数理逻辑中递归论的一部分
• 实质 理论
• 详细内容 见正文

简介

　　数理逻辑就研向件评群质语伟斗中递归论的一部分。它的来自中心论题是用递归论为工具给出数集（问题集）或函数集血附的复杂性的某种排序。

详解

　　因为所谓算术集恰是自然数集 N中由一阶公式定义的自然数集，而解析集则是由二阶公360百科式定义的自然数集。算术集构成解析集类的一个更易于定义的子类。同时，由于所有的递归集场林都是算术集，如把它们看成有同样儿啊始好希之精标复杂的可定义性并用作讨论的起点，这将是自然的。

　　同样的，一个递归可枚举集A恰为{x｜扽yRxy}，其中R为一般递归谓词,所十以一切递归可枚举集也是算术的，而由于一阶公式对于逻辑运算塡和量词彐(自然数变元)具有封闭性怕求化使低，所以任一算术集的补和射影依然是算术的，如此等等。在使用适当约定和稍作引伸之后，即可得到度量集合（数的或问题的）复杂性的一种排序称之为算术分层。类似地可以建立解析分层，从而S.C.克林就利用递归论成功地建立了分层理论及其相应的推广。

　　因为集合或函数均可唱花左系革风套用谓词来表述，故以下的讨论将就谓词而言且将沿用递归函数中的符号和概念。

　　设α,b,с,…,x,y,z;αi,bi,сi,…,xi,yi,zi（i=1,2,…）为自然数集N上的变元（0型变元）,易坏该上阻利皮边矿α，β,…,α1，α2,…ξ,η,…为一元数论函数集N上的变元(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)记成α,并将一前束范式的前束词中，相同的一串量词收缩为一个如

分层理论

分层理论

　　这样，一谓词P是算术的即是可表成下列形式之一：

分层理且双讲吸即短论

　　,其中R为一般递归谓词,同时，根据量词的个数k及公式最外边的量词是扽 还是凬而分别记成

分层理论

　规染妈停什燃府船　型或

分层理论

　　型（

分层理论

　　型的对偶形式）。例如,形如 扽xR的谓词全体记作

分层理论

　　，而形如凬x扽yR的谓词全体则记作

分层理论

　　。

　　把可以用两种形式

分层理论

　　及

分层理论

　　来表示的谓词全体记作

分层理论

　　。

　　例如,易见

分层理论

　　（此即把递归集定义作最简单的算术集）。

　　又如，

分层理论

　　（此即一谓词属于

分层理论

　　的充要条件为它是一般递归的）。

　　在k≥1的情形，置括何音保恒存在一个枚举类

分层理论

　　（或

分层理论

　　移技管开艺磁执向刘转）的全体谓词的枚举谓词。例如，对于

分层理论

　　和m=n=1而言,存在一个原始递归谓词S(α,z,α,x,y)，使得当任给一个一般递归谓词R(α,α,x,y)时，恒有自然数ƒ，使得

分层理论

　　此即枚举定理。在这个定理中，可将S(α,ƒ,α,x,y)取为T屶(z,α,x,y)则有分层定理。

分层定理

　　对每一k≥0，都存在一个

分层理论

　　型（

分层理论

来自　　型）谓词,它不能在其对偶形式

分层理论

　　360百科(

分层理论

　　)中得到表示。换言之，对每一正整数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散宜刘)，这时我们可以把所考虑的谓词 P(α1,α2,…,αm,α1,α2,…,αn)推广为算术于和解析于C 中任意有限多个函数的谓词。这时所得到的相应的分层度封成贵胶比海难苗，分别称为C－算术分层和C－解析分层，并且分别记作

分层理论

　　和

分层理论

　　关于集合N算术分层和 N连培起较掉解析分层分别相应于无理数空间中的有限波莱尔集合射影集。J.W.艾图督井爱眼怕式迪生称之为古典描述集合论。与之相应的，关于集合的(即C=═时)算术分层和解析分层的理论便称之为村乐价采老书光即娘能行描述集合论。

　　如果只考虑自然数谓词(即在P中，m=0的情形)，则可定义lK+1(α)为

分层理论

　　型谓词(k≥0),它在

分层理论

　　型的谓词中具有最高级的递归不可解度，且其不可解度确实比 LK(α)高，因而lK(k=0,1,2,…)决定了递归不可解度的算术分层。克林用可构造序数的记法系统把lk序列推广到以可构造序数作下标的不可解度分层即递归不可解度的超算术分层记作{Hy｜y∈O}，如果一函数或谓词对于某y∈O，递归于hy，则称此函数或谓词是超算术的。使得一谓词为超算术的其充要条件为它可以在墹姌中表示。

　　克林应用具有任意 k型变元(k=0,1,2,…)的一般递归函数的理论，对具有任意型变元的谓词建立了分层理论，使得原来的分层理论得到了进一步的推广。

　　如果把上述的α,b,с,…，看成是集合变元（即α,b，с，…是表示集合的变元）即可得到莱维的分层。