[科普中国]-相对解析分层

相对解析分层(relativized analytical bierarchy)是解析分层概念的相对化。即对相对算术关系依量词复杂性进行的递归论分层。

概念相对解析分层(relativized analytical bierarchy)是解析分层概念的相对化。即对相对算术关系依量词复杂性进行的递归论分层。具体地，对自然数集A，相对A的解析分层Σ1,An，π1,An与Δ1,An可递归定义如下：1

1.Σ1,A0=π1,A0={R：R为相对A的算术关系}。

2.Σ1,An+1={(∃′f)R(f，f1，f2，…，fk，x1，x2，…，xm)：R∈π1,An}。

3.π1,An+1={(ᗄ′f)R(f，f1，f2，…，fk，x1，x2，…，xm)：R∈Σ1,An}。

4.Δ1,An=Σ1,An∩π1,An。

Σ1,An，π1,An与Δ1,An中的关系分别称为Σ1,An关系，π1,An关系与Δ1,An关系。此外，用Δ1,Aw表示∪{Σ1,An∪π1,An：n∈w}，即所有相对A的解析关系的集合。

解析分层解析分层亦称解析谱系。按照量词复杂性对解析关系所作的递归论分层。与算术分层类似，任何解析关系可以用算术关系加上有穷个交替出现的二阶函数量词ᗄ′与∃′表示，依照量词个数，可以将该解析关系纳入具体的解析分层Σ1n或π1n中。形式地，具体的解析分层Σ1n，π1n，Δ1n可递归定义如下：

1.Σ10=π10={R：R为算术关系}。

2.Σ1n+1={(∃′f)R(f，f1，f2，…，fk，x1，x2，…，xm)：R∈π1n}.

3.π1n+1={(ᗄ′f)R(f，f1，f2，…，fk，x1，x2，…，xm)：R∈Σ1n}。

4.Δ1n=Σ1n∩π1n.

Σ1n，π1n与Δ1n中的关系分别称为Σ1n关系、π1n关系与Δ1n关系，此外，Δ1w定义为：∪{Σ1n∪π1n：n∈ω}，即所有解析关系的集合。此外，对n≥1，Σ1n关系可表示成下形范式：

(∃′f1)(ᗄ′f2)…(Qnfn)(Qx)

R(f1，…，fn，fn+1，…，fn+p，x，x1，…，xq)，

其中若n为偶数，Q1n为ᗄ′，Q0为∃0；若n为奇数，Q1n为∃′，Q0为ᗄ0；而R为递归关系。π1n关系也可表示成以ᗄ′开头的类似表达式.解析分层还具有如下封闭性：

1.Σ1n，π1n，Δ1n对合取、析取运算与一阶量词封闭。

2.Δ1n对否定运算封闭。

3.R∈Σ1n，当且仅当ᒣR∈π1n；

R∈π1n，当且仅当ᒣR∈Σ1n。

4.对n≥1，Σ1n对二阶量词∃′封闭，πn对二阶量词ᗄ′封闭。

关于解析分层的其他性质，参见“解析枚举定理”。此外，与算术分层不同，Δ11≠Σ10=π10=Δ10，Δ11的关系称为超算术关系。2

递归关系递归关系是序列的项之间的一种关系。指序列的任一项均被其前若干项所确定的那种关系。对于数列{an|n=0，1，2，…}，若当n≥0时，恒有关系式：

an+k=F(an+k-1，…，an)，

这里k为正整数，F为元an+k-1，…，an的代数函数，且an必在式中出现，则an+k=F(an+k-1，…，an)称为数列{an|n=0，1，2，…}的一个逆归关系。若给定此递归关系，且给出a0，a1，…，ak-1的一组初值，则数列{an|n=0，1，2，…}完全确定。例如，递归关系an+2=an+1+an及初值a0=a1=1完全确定数列1，1，2，3，5，8，…，称为斐波那契数列。使用计算机，根据给定递归关系和初值计算相应的数列的项很方便。因此，递归关系是研究数列的一个有力工具。

算术关系算术关系是递归关系的推广。是可以通过对递归关系添加有穷个量词定义的关系，即可以表示Q1x1Q2x2…QnxnR(x1，x2，…，xn，a1，a2，…，an)形的关系，其中R为递归关系，Q1，Q2，…，Qn为一阶量词∃或ᗄ。等价地，算术关系亦是可以从递归关系出发，经有限次否定与射影运算得到的关系。算术关系的定义是由美国逻辑学家、数学家克林(Kleene，S.C.)与波兰数学家莫斯托夫斯基(Mostowski，A.)给出的。

从可判定(或可计算)的角度上说，递归关系具有最小的复杂性，但递归关系对(不受限)量词不封闭，而算术关系类则为递归关系类对量词封闭的最小扩张，因此算术关系的概念可看做递归关系概念的推广。实际上，任何算术关系也恰为一阶算术可定义关系，这也是“算术”一词的来源。3

相对算术关系算术关系概念的相对化。对自然数集A和关系R，若R可表示成(Q1x1)(Q2x2)…(Qnxn)S(x1，x2，…，xn，a1，a2，…，am)的形式，其中Q1，Q2，…，Qn为量词ᗄ或∃，S为相对A递归的关系，则称R为相对于A的算术关系。若集合B是相对于A的(一元)算术关系，即B可表示成：{x：(Q1y1)(Q2y2)…(Qnyn)S(y1，y2，…，yn，x)}其中Q1，Q2，…，Qn为量词，S为相对于A递归的n+1元关系，则称B为相对于A的算术集，并记为B≤aA，亦称B可算术化归到A。由算术化归关系可导出算术等价的概念。对集合A，B，若A≤aB，并且B≤aA，则称A，B算术等价，记为A≡aB。

本词条内容贡献者为:

尚华娟 - 副教授 - 上海财经大学