相對解析分層

相對解析分層(relativized analytical bierarchy)是解析分層概念的相對化。即對相對算術關係依量詞複雜性進行的遞歸論分層。

基本介紹

  • 中文名:相對解析分層
  • 外文名:relativized analytical bierarchy
  • 領域:數學
  • 學科:算術
  • 定義:解析分層概念的相對化
  • 性質:遞歸論分層
概念,解析分層,遞歸關係,算術關係,相對算術關係,

概念

相對解析分層(relativized analytical bierarchy)是解析分層概念的相對化。即對相對算術關係依量詞複雜性進行的遞歸論分層。具體地,對自然數集A,相對A的解析分層Σn,πn與Δn可遞歸定義如下:
1.Σ00={R:R為相對A的算術關係}。
2.Σn+1={(∃′f)R(f,f1,f2,…,fk,x1,x2,…,xm):R∈πn}。
3.πn+1={(ᗄ′f)R(f,f1,f2,…,fk,x1,x2,…,xm):R∈Σn}。
4.Δnn∩πn
Σn,πn與Δn中的關係分別稱為Σn關係,πn關係與Δn關係。此外,用Δw表示∪{Σn∪πn:n∈w},即所有相對A的解析關係的集合。

解析分層

解析分層亦稱解析譜系。按照量詞複雜性對解析關係所作的遞歸論分層。與算術分層類似,任何解析關係可以用算術關係加上有窮個交替出現的二階函式量詞ᗄ′與∃′表示,依照量詞個數,可以將該解析關係納入具體的解析分層Σn或πn中。形式地,具體的解析分層Σn,πn,Δn可遞歸定義如下:
1.Σ00={R:R為算術關係}。
2.Σn+1={(∃′f)R(f,f1,f2,…,fk,x1,x2,…,xm):R∈πn}.
3.πn+1={(ᗄ′f)R(f,f1,f2,…,fk,x1,x2,…,xm):R∈Σn}。
4.Δnn∩πn.
Σn,πn與Δn中的關係分別稱為Σn關係、πn關係與Δn關係,此外,Δw定義為:∪{Σn∪πn:n∈ω},即所有解析關係的集合。此外,對n≥1,Σn關係可表示成下形範式:
(∃′f1)(ᗄ′f2)…(Qnfn)(Qx)
R(f1,…,fn,fn+1,…,fn+p,x,x1,…,xq),
其中若n為偶數,Qn為ᗄ′,Q為∃;若n為奇數,Qn為∃′,Q為ᗄ;而R為遞歸關係。πn關係也可表示成以ᗄ′開頭的類似表達式.解析分層還具有如下封閉性:
1.Σn,πn,Δn對合取、析取運算與一階量詞封閉。
2.Δn對否定運算封閉。
3.R∈Σn,若且唯若ᒣR∈πn
R∈πn,若且唯若ᒣR∈Σn
4.對n≥1,Σn對二階量詞∃′封閉,πn對二階量詞ᗄ′封閉。
關於解析分層的其他性質,參見“解析枚舉定理”。此外,與算術分層不同,Δ1≠Σ000,Δ1的關係稱為超算術關係。

遞歸關係

遞歸關係是序列的項之間的一種關係。指序列的任一項均被其前若干項所確定的那種關係。對於數列{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.)給出的。
從可判定(或可計算)的角度上說,遞歸關係具有最小的複雜性,但遞歸關係對(不受限)量詞不封閉,而算術關係類則為遞歸關係類對量詞封閉的最小擴張,因此算術關係的概念可看做遞歸關係概念的推廣。實際上,任何算術關係也恰為一階算術可定義關係,這也是“算術”一詞的來源。

相對算術關係

算術關係概念的相對化。對自然數集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。

相關詞條

熱門詞條

聯絡我們