二階算術(second order arithmetics)是遞歸論研究的內容之一。是刻畫自然數理論的二階形式理論。所使用的語言是二階算術語言L2。它是在一階算術語言L的基礎上，增加二階變元(即取值於函式或謂詞的變數)及相應的量詞而得。
基本介紹
- 中文名：二階算術
- 外文名：second order arithmetics
- 領域：數學
- 學科：遞歸論
- 定義：刻畫自然數理論的二階形式
- 推廣：一階算術
概念,一階算術,遞歸論,初等數論,
概念
二階算術(second order arithmetics)是遞歸論研究的內容之一。是刻畫自然數理論的二階形式理論。所使用的語言是二階算術語言L2。它是在一階算術語言L的基礎上，增加二階變元(即取值於函式或謂詞的變數)及相應的量詞而得。這種二階語言在自然數結構N上也有其自然的解釋。在這種解釋之下為真的L2語句組成一個理論Ω2，即Ω2={φ|N⊨φ為L2語句}。Ω2稱為二階算術理論，簡稱二階算術。類似地，其他高階算術也可仿此定義。
一階算術
一階算術是遞歸論研究的內容之一。是刻畫初等數論的一階形式理論。表述這種理論的語言為一階算術語言L。它除了含有通常一階語言的內容外，還含有等詞=，個體常元0(零)，一元常函式S(後繼)及兩個二元常函詞+(加)和×(乘)。設N為通常的自然數結構，則L可以在N中得到自然的解釋。在這個解釋之下為真的全體一階算術語句(即L語句)構成一個理論Ω，即Ω={φ|N⊨φ & φ為L語句)}，此理論Ω稱為一階算術理論，簡稱一階算術.一階算術Ω由直觀上為真的全體一階算術語句所組成，因此，它是一個協調的、完備的理論(這與佩亞諾算術PA大不一樣).但是，Ω是不可公理化的，即無法從Ω中挑選出一個遞歸可枚舉的語句集合作為公理，從而把Ω中的其他語句全部推出來。因而也不存在一個能行的過程，把Ω的全體語句能行地列舉出來。
遞歸論
數理邏輯的一個分支，是一門研究遞歸函式及其推廣的科學。遞歸函式是一種數論函式，其定義域與值域都是自然數集。只是由於構作函式的方法不同而有別於其他數論函式。將定義域推廣到不限於自然數集時，便是所謂廣義的遞歸函式。
遞歸論這門學科最早可以追溯到原始遞歸式的使用。古代人以及現代的兒童對加法及乘法的理解，實質上就是使用原始遞歸式。但直到16世紀的毛羅利科，尤其是17世紀的帕斯卡才正式使用與遞歸式密切相關的數學歸納法。19世紀德國數學家戴德金和義大利數學家皮亞諾正式使用原始遞歸式來定義加法與乘法，從而發展了自然數理論。1923年，斯科朗提出並初步證明一切初等數論中的函式都可以由原始遞歸式作出，即都是原始遞歸函式。1931年，哥德爾在證明其著名的不完全性定理時，以原始遞歸式為主要工具把所有元數學的概念都算術化了。原始遞歸函式的重要性日益受到人們的重視，人們開始猜測，原始遞歸函式可能窮盡一切可計算的函式。但是，阿克曼提出了非原始遞歸的可計算函式，否定了這個猜測，同時也要求人們探討原始遞歸函式以外的可計算函式。1934年，哥德爾在埃爾布朗的啟示之下，提出了一般遞歸函式的定義。美國的克林於1936年證明了這樣定義的一般遞歸函式與丘奇所定義的λ-可定義函式是相同的，並給出了幾種相等價的定義。這樣的一般遞歸函式後來被稱為埃爾布朗一哥德爾一克林定義。1936年，丘奇、圖靈各自獨立地提出一個論點，即凡可計算的函式都是一般遞歸函式，把遞歸函式論與能行性理論密切地結合起來，從而使遞歸函式的套用範圍大大地擴展了。關於遞歸函式本身的研究的進展則在於定義域的推廣，從而得到遞歸字函式、α遞歸函式和遞歸泛函等等。
隨著集合論的發展，遞歸論也向廣義遞歸論發展。序數上遞歸論對有限概念的推廣在無限語言中得到了重要套用。自然數上遞歸論已在許多方面得到套用。
隨著計算機科學的發展，要求把古典數學能行化。以尼羅德為代表的遞歸論學家開拓了遞歸數學的研究領域。他們把古典數學的基本概念算法化，然後考慮哪些數學定理可以成立，哪些無法成立。遞歸論在計算機科學中的套用主要是用於計算複雜性理論。起初是把圖靈機作為研究計算複雜性的模型，考慮計算的時間、空間複雜性。繼而基於遞歸論，再加上適當的公理又建立了抽象計算複雜性理論。近年來，遞歸論的方法大量用於P與NP問題的研究。
初等數論
數論的基礎部分，常限於用初等數學的方法，而不藉助於其他數學工具，去研究整數性質。它主要包括：整除理論、不定方程、同餘式和連分數等。
早在公元前3世紀的古希臘時代，歐幾里得(Euclid)所著《幾何原本》一書中就記載了對素數無限性的證明、整數的因數分解、求兩個正整數最大公因數的輾轉相除法、關於完滿數的一個著名定理等。此外，還有埃拉托斯特尼篩法，阿基米德(Archimedes)和丟番圖(Diophantus)對不定方程的研究等。在數論發展史上，費馬(Fermat，P.de)、高斯(Gauss，C.F.)和狄利克雷(Dirichlet，P.G.L.)等都做出了貢獻。
中國古代在初等數論方面也有過光輝的成就，例如勾股定理、孫子定理(國外稱為中國剩餘定理)與圓周率的計算結果.數論也是中國近代發展得最早的數學分支之一，從20世紀30年代開始，在解析數論、丟番圖方程、一致分布等方面都有過貢獻。華羅庚在三角和估計與堆壘素數論方面的研究，陳景潤對哥德巴赫猜想的研究，都走在數論研究的前沿。在初等數論中，常採用算術推導方法來論證數論命題。往往首先根據一些感性知識，提出某個數學猜想，然後予以證明。若這個猜想為真，即成為數論中的定理;若這個猜想不成立，即被否定。
數論中的猜想都是關於判斷某個整數性質的命題，意義常常是淺顯易懂的，但其證明卻往往非常困難，需要高深的數學工具。例如，哥德巴赫猜想、費馬猜想等，具有國中數學知識的讀者，都能明白其意義，但是，這些問題卻非常難解，幾百年來，經過不少數學家的努力都尚未徹底解決。儘管如此，數學家們在這方面的努力不是徒勞的，他們在努力證明猜想的過程中，引入了許多新的數學思想，創造了許多新的方法和概念，發展成新的理論，從而推動了數論以至整個數學科學向前發展.例如，篩法已成為機率統計和組合論的重要方法；研究費馬猜想引入的理想數概念已滲入到現代代數、幾何和泛函分析等廣大的數學領域。另一方面，其他各數學分支的研究成果也促進著數論的發展，法爾廷斯(Faltings，G.)利用代數幾何的成就證明了莫德爾(Mordell，L.J.)提出的莫德爾猜想，從而使費馬猜想的研究工作前進了一大步。1995年，懷爾斯(Wiles，A.)終於完滿地證明了費馬猜想。
初等數論是思維的體操，能鍛鍊人們的抽象思維能力和邏輯思維能力，隨著科學技術的發展，在當今計算機時代和信息社會，在計算方法、密碼學、組合數學、通信工程、離散控制系統等許多領域都有廣泛的套用。所以，初等數論不僅是數學工作者，而且也是許多從事套用和實際工作的工程技術人員所不可缺少的數學知識。
