§0.1 數理邏輯簡介
我們這部教材著重闡述如何研究信息，信息如何量化，信息如何傳遞，信息如何編碼等等.而數理邏輯或稱符號邏輯、理論邏輯，是數學中的一個基礎分支，是一門用數學方法研究邏輯或形式邏輯的學科，其研究對象是對證明和計算這兩個直觀概念進行符號化以后的形式系統.數理邏輯是數學的基礎.信息與數理邏輯，這兩者間表面上看似乎毫無聯系，但它們均屬于信息科學，我們通過對數理邏輯的研究，揭示信息的傳遞和編碼的實質，講述在數學中如何進行信息的傳遞和編碼，而編碼就涉及算法，涉及如何計算，從而為信息論的研究提供更多的數學工具和方法.
由于多數數學系學生只在離散數學課程中接觸過一點命題演算和謂詞演算，所以我們先簡單介紹一點數理邏輯.所謂數學方法就是指數學采用的一般方法、符號化和形式化，特別是使用形式化的公理方法.這種系統思想可以追溯到萊布尼茨，之后經典的傳統邏輯變得更為精確、更便于演算.簡而言之，數理邏輯就是精確化、數學化的形式邏輯.它是現代數學和計算機技術的基礎.用數學的方法研究關于推理、證明等問題的學科就叫作數理邏輯.
一、數理邏輯簡介與悖論
數理邏輯的最基礎部分知識就是“命題演算”和“謂詞演算”，這是離散數學中已經介紹過的.這部分工作源于上面講過的形式化的要求和悖論的產生.數理邏輯這門學科建立以后，發展比較迅速，促進它發展的因素也是多方面的.比如，非歐幾何的建立，促使人們去研究非歐幾何和歐氏幾何的無矛盾性.集合論的產生是近代數學發展的重大事件，即數學史上的第三次大危機.這次危機源于集合論悖論的產生.悖論就是邏輯矛盾.集合論本來是論證很嚴格的一個分支，被公認為是數學的基礎，但在1903年，英國唯心主義哲學家、邏輯學家、數學家羅素卻對集合論提出了以他名字命名的“羅素悖論”，這個悖論的提出幾乎動搖了整個數學基礎.
羅素悖論中有許多例子，其中一個很通俗也很有名的例子就是“理發師悖論”：有個小島上有一位理發師，有一天他宣布：他只給小島上不自己刮胡子的人刮胡子.那么就產生了一個問題：理發師究竟給不給自己刮胡子？如果他給自己刮胡子，他就是自己刮胡子的人，按照他的原則，他又不該給自己刮胡子；如果他不給自己刮胡子，按照他的原則，他又應該給自己刮胡子.這就產生了矛盾.
這個悖論用邏輯符號寫出來就是，A=｛A：A
A}.我們容易推導出A∈A當且僅當A∈A.這是數學家不能容忍的.
為什么會出現這種現象呢？這與集合的直覺定義有關.中學數學課本給出的模糊的集合定義為：所有滿足某種性質φ的對象的全體為一個集合.寫成數理邏輯公理（Comprehension公理）就是：如果φ是一性質，則存在一個集合Y=｛x：φ（x）｝.但這是錯誤的，羅素悖論就是其反例.
悖論的提出，促使許多數學家去研究集合論的無矛盾性問題，從而產生了數理邏輯的一個重要分支——公理集合論.我們在此列舉ZFC公理系統，你會很驚訝地看到，我們平時認為對的很多東西竟然都是公理，并非絕對的.
1．外延（extensionality）公理：如果X和Y有相同元素，則X=Y.
2．配對（pairing）公理：對任何a，b，存在一個集合｛a，b｝，恰好含有元素a，b.
3．分離（separation）公理：如果φ是一性質，則對于任何集合X和參數p，存在一個集合Y=｛u∈X：φ（u，p）｝，它包含所有具備此性質的X中的元素u.這條修改過的公理解決了羅素悖論.
4．并集（union）公理：對任何X，存在一個集合Y=∪X，即X中所有元素的并.
5．冪集（power set）公理：對任何X，存在一個集合Y=P（X），X的所有子集合形成的集合.
6．無窮（infinity）公理：存在無窮集合.
7．替換（replacement）公理：如果F是一個函數，則對任何集合X，存在一個集合Y=F[X]=｛F（x）：x∈X｝.
8．正則（regularity）公理：每個非空集合有一個∈關系最小元素.
9．選擇（choice）公理：每個非空集合類，有一個選擇函數.
從此數學基礎就建立在ZFC公理系統之上了.（非歐幾何的產生和集合論的悖論的發現，說明數學本身還存在許多問題，為了研究數學系統的無矛盾性問題，需要以數學理論體系的概念、命題、證明等作為研究對象，研究數學系統的邏輯結構和證明的規律，這樣又產生了數理邏輯的另一個分支——證明論.數理邏輯同時期還發展了許多別的分支，如遞歸論、模型論等，它們看似不同學科，但在更高的層次上看卻完全是互補的、相同的、思想一致的.遞歸論主要研究可計算性的理論，它和計算機的發展和應用有密切的關系.模型論主要是研究形式系統和數學模型之間的關系.數理邏輯近年來發展特別迅速，主要原因是這門學科對于數學其他分支如數論、代數、拓撲學等的發展有重大的影響，特別是對計算機科學的發展起了推動作用.總之，這門學科的重要性已經十分明顯.）
我們現在來看公理化集合論中一個特別的定理：
定理0.1.1 設κ為一個正則（regular）基數，λ＞κ是一個不可達（inaccessible）基數，則存在一個forcing（P，＜）使得：
（a）對于每個滿足κ≤α＜λ的α，其基數為κ（在
[G]中）；
（b）對于每個≤κ或≥λ的基數，基數仍然是原來的基數（在[G]中）.
這種現象稱為基數的坍塌（collapse），非常奇怪的結果，α明明大于κ，怎么可能其基數卻又等于κ.有點數學基礎的人都知道，強信息量的概念或事物易于推導出弱信息量的事物.而在這里，明明α的信息量要大于κ，可現在卻是等于κ的信息量.那為什么出現這種現象？
當我在學習集合論時，我很迷茫！但我的老師跟我說，你既要站在模型的里面看，你又要站在模型的外面看.
這個定理表明，從不同的角度觀察問題，即分別從事物的外面、里面看，信息量是不一樣的.這多少有點像量子力學中的不可測定理，一旦觀察者進入測量，觀察者就進入了舞臺，就影響了試驗，改變了試驗的結果.換個角度看，這表明信息量是相對的，或許根本沒有絕對的方法去尋求信息.后面我們會告訴你，這是事實，對于很多我們喜歡的事物，確實如此，我要告訴你，你找不到絕對的通用的方法.失望之后，我們依舊追求著我們所喜歡的，因為它們真的很精彩.
為了更容易地理解坍塌，我們給了一個不太準確的比方，二維平面上每個向量均可以用基向量i=（1，0）和j=（0，1）表示.從整個平面看，每個向量都是二維的，但從X軸看去，卻好像是一維的.
注意：我們要關注集合論中的坍塌現象、信息的坍塌現象、量子力學三者之間的聯系！信息的特征并不是那么容易把握！
二、遞歸論簡述
由于集合論對于絕大多數學生來講過于艱澀，我們下面通過研究數理邏輯另外一個與計算機有著千絲萬縷聯系、不可分割的分支——遞歸論來研究在數學中如何處理信息，同時也使大家了解計算機處理信息的基本原理.
遞歸論（recursion theory），數理邏輯的重要分支之一，研究解決問題的可行的計算方法和計算的復雜程度的一門學科.這種計算方法又稱算法.算法是個古老的數學概念.16世紀R.笛卡爾創造的解析幾何就是用代數來解決幾何問題的一種典型的算法.但數學中有一些問題長期找不到解決的算法.20世紀30年代K.哥德爾做出重大貢獻，提出了算法的一種精確定義.算法，實際上就是找到一種可以計算的信息，可以量化的信息，可以傳遞的信息.
S.C.克林據此定義了遞歸函數.與此同時，A.M．圖靈用圖靈機（一種理論計算機）來描述算法，并且證明圖靈可計算的函數與遞歸函數等價.圖靈機使人們普遍接受了關于算法的丘奇論題：遞歸函數是可計算函數的精確的數學描述．
遞歸函數是用數理邏輯的方法定義在自然數集上的可計算函數.如果自然數的一個n元集的特征函數是遞歸函數，就稱這個集合為遞歸集，一個遞歸函數的值域，稱為遞歸可枚舉集.遞歸集就是算法可判定的集合.遞歸集都是遞歸可枚舉的，但是存在不是遞歸集的遞歸可枚舉的集合.遞歸論的研究使人們把一些長期未解決的問題化為非遞歸的遞歸可枚舉集，從而嚴格證明了不存在判定這些問題的算法，這些問題稱為不可判定的.遞歸論進一步研究不可判定性，也就是非遞歸的遞歸可枚舉集之間的復雜程度問題.
1944年E.L.波斯特提出不可解度的概念，又給出了相對可計算性的構造方法.這就使人們開始對不可解度進行比較，并研究不可解度的代數結構.這方面出現了有窮損害優先方法、無窮損害優先方法等多種有力的研究手段，出現了許多有趣的研究成果.對可計算的遞歸集，也可以研究其計算的復雜性，考慮圖靈機上計算的時間、空間，就得到計算時間的長短計算所占空間的多少這兩個復雜性.計算復雜性的研究對計算機科學的發展有很大影響和作用.
遞歸論也叫可計算性理論（computability theory）.遞歸論標準讀物就是Soare的Recursively Enumerable Sets and Degrees.之前最好看一些數理邏輯的入門教材.例如：Davis的Computability and Unsolvability，或者Cutland的Computability.否則一進來就是圖靈（Turing）論題、丘奇（Church）論題，可能就會覺得特玄乎.現在遞歸論發展似乎到瓶頸了，純遞歸論好像是越來越難做了，簡單的東西都做完了，剩下的都是硬骨頭.所以現在很多做這方面的人都在試圖將遞歸論應用到其他領域，有代數（computable algebra），組合數學（peano arithmetic），分析和拓撲（computable topology and computable analysis），模型論（effective model theory），能行數學（effective mathematics），解決很多經典數學中的問題是否可以有效（effective）.它還可以應用到計算復雜性中去，這算比較多的，現在搞復雜性的一些專家就是從遞歸論出身的.現在應用的比較成功的、比較熱門的是和隨機性的結合，即算法信息論，也叫描述復雜性.芝加哥大學的Soare主頁上有Downey的一本寫這個的書，可以下載的.據說有人利用遞歸論成功地解決了黎曼（Riemann）幾何中的問題，最終結果看不出任何遞歸論的痕跡.
遞歸論理論起源自哥德爾、丘奇、圖靈、克林和Emil Post在20世紀30年代的工作.他們獲得的基本結果建立了圖靈可計算性.通過能行計算的嚴格定義得到在數學中有些問題是不可有效判定的的最初證明.丘奇和圖靈獨立地證明了停機問題不能能行判定，而Post證明了在Thue系統中確定一個字符串是否有規范形式（類似于在λ演算中一個項是否有規則形式）是不可判定的.
不可解度結構的研究，包括圖靈度、多一度及類似的結構，是這個領域的重要部分.圖靈度的研究發起自Kleen和Post.大量的可計算性理論中的研究已經投入圖靈度的性質的研究中.開始于20世紀70年代，圖靈度的研究焦點已經從局部結構性質轉移到全局性質，比如圖靈度的自同構（automorphism）和0′的可定義性.
在20世紀30年代確定了最初的例子之后，很多數學問題已經被證實是不可判定的.Novikov和Bone在20世紀50年代證實，給出在一個有限出現群中的一個字，沒有有效的過程來判定這個字所表示的元素是否是這個群的單位元素.這個結果被用來證實很多其他問題是不可判定的，比如兩個有限單形（simplicial complex）是否表現同胚空間的問題.在 1970 年，Yuri Matiyasevich對希爾伯特第十問題(1)給出了否定答案，這個否定解答是對Martin Davis、Hilary Putnam和Julia Robinson在1961年給出的部分解答的鞏固.
遞歸論包括可計算性一般概念的研究，比如超算術度（hyper arithmetic degrees）、α-遞歸論和可構造度（constructibility degrees）.
剛剛提到的遞歸論標準讀物，Soare的Recursively Enumerable Sets and Degrees，見［So］.該讀物難度較大，但其中講解了人類研究、構造無窮事物的方法或算法，最難的是
-方法即無窮損害方法，雖然有無窮次損害，但終有一個策略使我們能夠無窮次逼近真路徑.它與集合論類似，研究的是無窮概念，這種方法顯示了人類在追尋無窮信息時采取的無窮損害方法、策略，難度非常大.由于人類思維的局限性，0″″-方法迄今尚未發現.
三、可計算性理論研究方向
簡單地說，遞歸論就是研究一個問題是否能用算法來解決.但遞歸論并不研究“如果一個問題能用算法解決，那么這個算法是怎樣產生的”.遞歸論首先定義了“圖靈機——純符號運算體系”，接著證明了“不可計算性”的存在——世界上存在著算法不能解決的問題，“不可計算”代表了純符號體系的局限性、人類認識世界的局限性.
遞歸論只關心一個問題是否“可計算”，并沒深入研究“算法本身”.對算法本身是如何產生的這一命題“僅僅停留在圖靈機編號”層次上.而且那些“不去解決任何問題”“永遠無法停機的死循環”的“圖靈機編號”更是直接被忽略了，好像是它們根本就不存在——至少不認為它們是“算法”.
另外，遞歸論的基礎是“圖靈機”，但圖靈機的基礎卻不僅僅是“集合”——實際上集合無法獨立“運行”，所以圖靈機還要基于“某種機械或電磁”的“力量”才能運行（把圖靈機想象成某種機器）.
通俗地說，遞歸論主要有這幾個問題：
1．什么是可計算性函數？怎么定義？
2．什么是算法？什么是能行的？
3．如何判斷函數的計算難易程度？
所以，有些函數是可以編碼的、可以在計算機上運行的，其信息是可以傳遞的.
(1) 是否存在有效的過程來判定具有限多個有理數變量的丟番圖方程是否存在有理數解.