數理邏輯概要

邏輯是所有學科的基礎，它那原始而又不言自明的特點卻阻礙了研究的深入。直到19世紀後期，隨著非歐幾何的發現，以及要為各門分析學科提供一個嚴格理論基礎的願望，數學家們才對邏輯的研究有了一絲興趣。在20世紀初，悖論的出現震驚了數學界！撒謊者悖論、理發師悖論、Cantor關於基數的悖論等等，讓數學家們使出渾身解數去避免它們。

Russel注意到悖論中自我引用的特點，建議每個對象都應該有一個 “類型數”, 說 “X是Y的一個成員” 意味著Y的類型數比X的類型數大。Brouwer則拒絕接受 “排中律 “：P與非P二者必須且隻能居其一；這對有限集是對的，但不能推廣到無窮集。還有人提出，不能假設對於每種性質P(x)，都存在某些個體x滿足該性質；必須要有確定的構造方法才行；人們隻能相信直覺。依我看，集合基數相等的1對1原則，也隻是對有限集成立，對無窮集是不對的，遺憾的是沒有其它方法去定義基數相等。

Hilbert還想為所有的數學學科找到一個完備而又相容（不能推出相互矛盾的兩個結論P與非P）的公理係統。一個數學係統指的是一種演繹機製，包含（1）一個對象集，包含數字、形狀、關係、量詞、標點等，甚至是集合（稱為高階邏輯）。（2）一套符號演算法則或函數關係，即對一個或多個對象進行變換或結合的法則（k元運算）以形成表達式或新的對象；如邏輯連接詞、算子等。（3）一組公理，確定演算或關係所遵循的規則；比如，加法應當滿足交換律、結合律；距離應當滿足對稱性、三角不等式、正定性（至少是可分離性，一致拓撲結構的要求）。（4）一組推導規則R，可以從公理推出新的定理。

現在關於邏輯學的定義是 “推理方法的分析”(Analysis of methods of reasoning)，它注重推理的形式，而不是對象的含義或內容。所謂形式推理，就是從前提S（命題或公式的集合）出發，按照一定的法則R（Rules of inferences），推出新的結論C（命題或公式）；簡記為 S|--(R) C。可推導性（Deducibility）的衡量需要語義上的解釋及真值賦值（truth valuation）。

一種真值賦值指的是從對象（命題符號）集到集合{0， 1}的一個函數。對於一個公式（表達式）A，其賦值由以下規則確定：v(~A) = 1 – v(A), v(A∧B) = v(A)v(B), v(A ∨ B) = v(A) + v(B) - v(A)v(B)，v(A→B) = v(~A ∨ B)，v(A↔B) = v(A→B) v(B→A)，v(AuB) = v(~B →A)，u指的是”unless”，也是一個邏輯連接詞。這些規則其是就是集合運算的公理；蘊含→等價於集合的包含關係。一個公式（命題）A稱為重言式（Tautology），如果對任何賦值v都有v(A) = 1。如果對任何賦值v都有v(A) = 0，則A是一個矛盾式。一個公式是可滿足的，如果存在一種賦值v, 使得v(A) = 1; 也就是說，它的反公式~A不是重言式。

其實，表達式的合法形成也可以數值化。比如給左括號賦值-1，右括號賦值+1, 逗號賦值0；隻有當整個表達式的總賦值為0時，才是有效的（valid）。在模糊邏輯中，一個式子還可以賦予一個分數值；隻有遞歸求和的總值達到一定標準如1時，式子才是有效的。在賦值後的公式集上，還可以開展統計分析。

推斷法則必須規定哪些行為是不被容許的。比如，不能用同音或者同形的字代替單詞，不能有循環定義，不能自相矛盾。在命題邏輯中，有11條推理規則：（1）自反性A|-A, （2）可任意增加前提，（3）否定詞的消去或引入，即S, A|-B, S, A|-~B, 那麽S|-~A，（4）→的引入和消去，（5）且∧的引入和消去，（6）或∨的引入和消去，（7）等價↔的引入和消去。在謂詞邏輯中，還有量詞及等號=的引入和消去規則，共計17條。這其實就是集合運算的同一律、補、交、並、蘊含關係的反映。

對一個形式推演係統，通常有四種要求或性質：可靠性(Soundness)、兼容性（Consistency）、完備性（Completeness）、有效公理化(effectively axiomization)。所謂可靠性指的是，在這個演繹係統中任何可以形式化證明的命題，在所有釋義以及這個理論所基於的真質賦值為真，即為重言式。

一個公式集S是兼容性的，指的是不能從它同時推出一個命題及其否命題。可以證明，如果S是可滿足的(Satisfiable)，那麽S一定是兼容的。一個公式集S是可滿足的，要求存在一種真值的賦值方式v，使得對其中每個公式A，都有v(A) = 1。

一個係統的完備性（Completeness）指的是，任何重言式T都是可以證明的，即有一個形式推理的序列，T位於序列的最後。重言式可以認為是語義上完備的，而這裏要求公理係統能夠形式證明所有的重言式（Tautologies），是語法意義上完備的。

在分析學中，一個集合的完備性指的是，其中的任何收斂序列都有極限在集中，也就是對極限運算是封閉的。在邏輯學中，也可以要求所有算子的值域能夠涵蓋所有的表達式（公式），此時稱為係統是歸納的（Inductive）。此外還有緊性的要求：任何閉集的每個開覆蓋都有有限覆蓋；在邏輯學中，緊性的要求則是，任何證明可以在有限步內完成; 也就是說，一個公式子集S是可滿足的，當且僅當它的每個有限子集是可滿足的。

一個係統可以有效地公理化，指的是其公式（定理、表達式）的集合是可數遞歸的；也就是說，在一個推斷或者證明的過程中，或一個命題公式的序列F1，F2, …, Fn, … 中，每個公式Fn要麽是一條公理，要麽是前麵某些公式、按照規則R推出的結論。Peano算術、Zermelo-Fraenkel集合論（ZFC）、Euclid幾何都是可以遞歸生成的，分析學卻不能。

哥德爾的不完備性定理說，包含Peano算術係統的形式係統不可能四條性質都具備。第一條不完備定理表明，任何一個允許定義自然數的體係必定是不完備的：它包含了不能在此係統內以一階謂詞邏輯形式證明的命題，並且該命題的否命題也不能在該體係內以一階謂詞邏輯的形式證明。在歐幾裏得幾何中，如果把平行公設去掉，就得到一個不完備的體係。不完備的體係可能隻意味著尚未找出所有必須的公理而已；但在多數情況下，例如在數論或者實分析中，永遠不可能找出公理的完整集合。換句話說，每一次將一個命題作為公理加入，將總有另一個命題出現在所能形式證明的範圍之外。

如果加入無窮條公理（例如，所有真命題）到公理列表中，確保所有命題都可證明為真或假，但得到的公理列表將不再是可數遞歸的。給出任意一條命題，將沒有機械的方法判定它是否是係統的一條公理。即使給出一個證明，一般來說也無法檢查它是否正確。

哥德爾第二定理說：如果一個（強度足以證明基本算術公理的）公理係統可以用來證明它自身的兼容性，那麽它是不兼容的。於是，為了確立係統S的兼容性，就要構建另一個係統T，但是T中的證明並不是有效的，除非不使用S就能確立T的兼容性。比如，自然數上的皮亞諾公理的兼容性可以在ZFC集合論中證明，但不能單獨在自然數理論範圍內證明。ZFC也不能在自身內證明其兼容，但如果增加一條“存在一個無法達到的基數”，則可以證明兼容性。

物理學家們說，任何公式都是有用的，哪管它什麽完備性；不兼容的係統隨處可見，不能可數遞歸生成又如何。發散的、連續求和的式子，也是隨手寫來，不能積分化也行啊！物理學科尚且難以統一（Grand Unification），何況數學。玩玩邏輯推理，以防大腦衰退，詭辯也是可以的；這才是邏輯的有用性。