词条 | 分层理论 |
释义 | 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是算术的即是可表成下列形式之一: ![]() ![]() ![]() ![]() ![]() ![]() 把可以用两种形式 ![]() ![]() ![]() 例如,易见 ![]() 又如, ![]() ![]() 在k≥1的情形,恒存在一个枚举类 ![]() ![]() ![]() ![]() 分层定理 对每一k≥0,都存在一个 ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() 所以,这就得到了一个方便的分层(1)来给算术谓词(算术集)分类。这个分层称为算术分层。 完备形式定理 对于每一个k≥1,都存在一个关于 ![]() ![]() ![]() ![]() ![]() ![]() 当P已经用到1型变元的量词(函数量词)则将增加定义的复杂性,从而引进解析分层。 关于 1型变元亦有:前束词中一串同类量词可收缩成一个;对任一算术谓词R,存在一个原始递归谓词S使有扽yS(y,α)可表为扽α扽xS(α(x),α)即为 扽αR(α,α)等事实可以利用。故可将全体解析谓词依以下形式分类: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() 设C为一元函数集(嶅NN),这时我们可以把所考虑的谓词 P(α1,α2,…,αm,α1,α2,…,αn)推广为算术于和解析于C 中任意有限多个函数的谓词。这时所得到的相应的分层,分别称为C-算术分层和C-解析分层,并且分别记作 ![]() ![]() 关于集合NN算术分层和 NN解析分层分别相应于无理数空间中的有限波莱尔集合射影集。J.W.艾迪生称之为古典描述集合论。与之相应的,关于集合的(即C=═时)算术分层和解析分层的理论便称之为能行描述集合论。 如果只考虑自然数谓词(即在P中,m=0的情形),则可定义 ![]() ![]() ![]() 克林应用具有任意 k型变元(k=0,1,2,…)的一般递归函数的理论,对具有任意型变元的谓词建立了分层理论,使得原来的分层理论得到了进一步的推广。 如果把上述的α,b,с,…,看成是集合变元(即α,b,с,…是表示集合的变元)即可得到莱维的分层。 |
随便看 |
百科全书收录78206条中英文百科知识,基本涵盖了大多数领域的百科知识,是一部内容开放、自由的电子版百科全书。