基本介紹
- 中文名：算術關係
- 外文名：arithmetical relation
- 所屬學科：數學
- 所屬問題：數理邏輯(遞歸論)
- 相關概念：遞歸關係，量詞，算術性等
- 提出者：克林，莫斯托夫斯基
基本介紹,相關性質與概念,相對算術關係,算術性,算術表示定理,
基本介紹
算術關係是可以通過對遞歸關係添加有窮個量詞定義的關係，即可以表示
形的關係，其中R為遞歸關係，
為一階量詞∃或ᗄ。等價地，算術關係亦是可以從遞歸關係出發，經有限次否定與射影運算得到的關係。算術關係的定義是由美國邏輯學家、數學家克林(S.C.Kleene)與波蘭數學家莫斯托夫斯基(A.Mostowski)給出的。從可判定(或可計算)的角度上說，遞歸關係具有最小的複雜性，但遞歸關係對(不受限)量詞不封閉，而算術關係類則為遞歸關係類對量詞封閉的最小擴張，因此算術關係的概念可看做遞歸關係概念的推廣，實際上，任何算術關係也恰為一階算術可定義關係(參見“算術表示定理”)，這也是“算術”一詞的來源。
相關性質與概念
相對算術關係
相對算術關係(relativized arithmetical relation)是算術關係概念的相對化。對自然數集A和關係R，若R可表示成
的形式，其中為量詞ᗄ或∃，S為相對A遞歸的關係，則稱R為相對於A的算術關係。若集合B是相對於A的(一元)算術關係，即B可表示成：
其中為量詞，S為相對於A遞歸的
元關係，則稱B為相對於A的算術集，並記為
，亦稱B可算術化歸到A。由算術化歸關係可導出算術等價的概念。對集合A，B，若
，並且，則稱
算術等價，記為
。
算術性
算術性(arithmeticity)是遞歸論術語，反映數論謂詞(關係)能否由一階算術理論來表示的性質，數論謂詞P具有算術性(即稱P為算術謂詞、或算術關係)，是指存在一個一階算術公式φ在Ω中表示P，即對任何自然數n，
成立，若且唯若
(
為
0)是Ω中的真語句，所有丟番圖關係都是算術關係，從而由馬蒂雅塞維奇(A.Matijasevich)-魯賓孫(J.B.Robinson)-戴維斯(M.D.Davis)-普特南(H.Putnam)關於希爾伯特第10問題的解答知，所有遞歸關係都是算術關係。實際上，所有算術關係都是由遞歸關係出發經過邏輯運算而得到的，關於算術性的最引人注目的結論是波蘭學者塔爾斯基(Tarski，A.)於1933年證明的定理：算術的真假性不是算術的，即不存在一個算術公式φ，使
，若且唯若(在某種確定的編碼之下)以
為編碼的算術公式β是算術地真的(即
)。
算術表示定理
算術表示定理(arithmetical representation theorem)指算術關係可用一階算術公式表示的定理。它指出：一關係
為算術關係(即R在算術分層中)，若且唯若
在一階算術中可定義.即存在一階算術中的公式
，使得對任何自然數
，
為真，若且唯若
在一階算術中為真，這也是“算術分層”與“算術關係”一詞的來源，算術表示定理是美籍奧地利數學家哥德爾(
)於1931年證明的。
