分层理论
分层理论
条目
历史版本
数理逻辑中递归论的一部分。它的中心论题是用递归论为工具给出数集（问题集）或函数集的复杂性的某种排序。
详解
因为所谓算术集恰是自然数集 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)记成α,并将一前束范式的前束词中，相同的一串量词收缩为一个如
分层理论