关于分层理论介绍

[拼音]：fenceng lilun

[外文]：theory of hierarchies

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

因为所谓算术集恰是自然数集 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)记成α，并将一前束范式的前束词中，相同的一串量词收缩为一个如

这样，一谓词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，都存在一个型（型）谓词，它不能在其对偶形式()中得到表示。换言之，对每一正整数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为一元函数集(嶅NN)，这时我们可以把所考虑的谓词 P(α1，α2，…，αm，α1，α2，…，αn)推广为算术于和解析于C 中任意有限多个函数的谓词。这时所得到的相应的分层，分别称为C－算术分层和C－解析分层，并且分别记作和

关于集合NN算术分层和 NN解析分层分别相应于无理数空间中的有限波莱尔集合射影集。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，с，…是表示集合的变元）即可得到莱维的分层。