• 正在加载中...
  • 分层理论

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

    编辑摘要

    目录

    简介/分层理论 编辑

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

    详解/分层理论 编辑

    因为所谓算术集恰是自然数集 N中由一阶公式定义的自然数集,而解析集则是由二阶公式定义的自然数集。算术集构成解析集类的一个更易于定义的子类。同时,由于所有的递归集都是算术集,如把它们看成有同样复杂的可定义性并用作讨论的起点,这将是自然的。
    同样的,一个递归可枚举集A恰为{xyRxy},其中R为一般递归谓词,所以一切递归可枚举集也是算术的,而由于一阶公式对于逻辑运算塡和量词彐(自然数变元)具有封闭性,所以任一算术集的补和射影依然是算术的,如此等等。在使用适当约定和稍作引伸之后,即可得到度量集合(数的或问题的)复杂性的一种排序称之为算术分层。类似地可以建立解析分层,从而S.C.克林就利用递归论成功地建立了分层理论及其相应的推广。
    因为集合或函数均可用谓词来表述,故以下的讨论将就谓词而言且将沿用递归函数中的符号和概念。
    α,b,с,…,x,y,z;αi,bii,…,xi,yi,zii=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的谓词全体记作分层理论,而形如凬xyR的谓词全体则记作分层理论
      把可以用两种形式分层理论分层理论来表示的谓词全体记作分层理论
      例如,易见分层理论(此即把递归集定义作最简单的算术集)。
      又如,分层理论(此即一谓词属于分层理论的充要条件为它是一般递归的)。
    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序列推广到以可构造序数作下标的不可解度分层即递归不可解度的超算术分层记作{HyyO},如果一函数或谓词对于某yO,递归于hy,则称此函数或谓词是超算术的。使得一谓词为超算术的其充要条件为它可以在墹中表示。
    克林应用具有任意 k型变元(k=0,1,2,…)的一般递归函数的理论,对具有任意型变元的谓词建立了分层理论,使得原来的分层理论得到了进一步的推广。
    如果把上述的α,b,с,…,看成是集合变元(即α,b,с,…是表示集合的变元)即可得到莱维的分层。

    配图/分层理论 编辑

    相关连接/分层理论 编辑

    添加视频 | 添加图册相关影像

    开放分类 我来补充

    互动百科的词条(含所附图片)系由网友上传,如果涉嫌侵权,请与客服联系,我们将按照法律之相关规定及时进行处理。未经许可,禁止商业网站等复制、抓取本站内容;合理使用者,请注明来源于www.baike.com。

    登录后使用互动百科的服务,将会得到个性化的提示和帮助,还有机会和专业认证智愿者沟通。

    互动百科用户登录注册
    此词条还可添加  信息模块

    WIKI热度

    1. 编辑次数:5次 历史版本
    2. 参与编辑人数:4
    3. 最近更新时间:2015-01-27 21:41:52

    贡献光荣榜

    更多

    互动百科

    扫码下载APP