第一節 邏輯

一般來說，邏輯包括語言、演繹系統和語義。語言是合式公式的集合，而公式是有窮長的字符串。推演系統是證明的集合，證明是公式集Ф和公式?之間的有序對，推演本身是證明的序列。如果存在從Ф到?的推演，則?是Ф的推演后承；如果?是空集的推演后承，則?是定理。如果不存在公式?，使得?和﹁?都是Ф的推演后承，則Ф是一致的。如果合式公式的集合和推演的集合是遞歸的，則推演系統是能行的；如果推演系統是能行的，則定理集是遞歸可枚舉的。語義是模型的集合，而模型是論域和解釋的集合。語義后承是由滿足關系定義的，滿足關系與賦值密切相關。如果任給賦值s，M都滿足?，則M是?的模型；如果任給賦值s，M都滿足Ф的成員，則M是Ф的模型。如果滿足Ф的任意模型和賦值也滿足?，則?是Ф的語義后承；如果?是空集的語義后承，則?是有效的。?是有效的，當且僅當?的全稱閉包是有效的。如果存在滿足Ф的成員的模型和賦值，則Ф是可滿足的。?是可滿足的，當且僅當?的存在閉包是可滿足的。如果定理都是邏輯真理，并且推演后承是語義后承，則邏輯是可靠的；如果邏輯真理是定理，并且語義后承是推演后承，則邏輯是完全的。

二階邏輯是在擴張一階邏輯的基礎上得到的，不同的擴張方式可以得到不同的二階邏輯。下面分別介紹自由變元邏輯、標準二階邏輯和分支二階邏輯。[1]

自由變元邏輯是在一階邏輯的基礎上增加關系變元和函數變元而得到的。除一階邏輯的形成規則外，還包括如下形成規則：

如果f是n元函數變元并且t1，…，tn是項，則ft1，…，tn是項。

如果R是n元關系變元并且t1，…，tn是項，則Rt1，…，tn是原子公式。

如果語言只包含關系變元，不包含函數變元，則可以用n+1元關系變元表示n元函數變元；如果語言只包含一元關系變元，不包含多元關系變元，則可以用n元組表示n元關系變元。

標準二階邏輯是在自由變元邏輯的基礎上增加二階量化而得到的。除自由變元邏輯的形成規則外，還包括如下形成規則：

如果?是公式并且R是關系變元，則?R?是公式。

如果?是公式并且f是函數變元，則?f?是公式。

與一階邏輯的情況類似，可以用二階全稱量詞定義二階存在量詞：

?R?=：﹁?R﹁?

?f?=：﹁?f﹁?

另外，在標準二階邏輯中，等詞是可以定義的：

（t=s）=：?X（Xt?Xs）

也就是說，在標準二階邏輯中，等詞是可以通過定義引入的；換言之，帶等詞的標準二階邏輯和不帶等詞的標準二階邏輯沒有實質性區別。

分支二階邏輯是在標準二階邏輯的基礎上為每個關系變元增加下標，它表示關系變元的層次，例如X0，…，Xn。分支二階邏輯一般不包括帶下標的函數變元。

標準二階邏輯的公理系統是在一階邏輯公理系統的基礎上增加如下關于二階量詞的公理：

?X?（X）→?（T），其中T對X代入自由，或者T是關系常項

從?→Ψ推出?→?XΨ（X），其中X不在?中自由出現。

?f?（f）→?（h），其中h對f代入自由，或者h是函數常量

從?→Ψ推出?→?fΨ（f），其中f不在?中自由出現。

在此基礎上還增加關于關系的概括公理：

?R?x1…?xn（Rx1…xn??（x1，…，xn）），其中R不在?（x1，…，xn）中自由出現。

它斷定，任意可表達公式都可以斷定一個關系的存在。還可以增加關于函數的概括公理：

?R（?x1…?xn?！yRx1…xny→?f?x1…?xnRx1…xnfx1…xn）

它斷定，任意滿足特定條件的關系都可以斷定一個函數的存在。標準二階邏輯的概括公理也被稱為非直謂概括公理。另外，還可以增加選擇公理：

?R（?x1…?xn?yRx1…xny→?f?x1…?xnRx1…xnfx1…xn）

它斷定，如果存在滿足特定條件的y，則存在一個函數f，它可以挑選出這樣的y。

標準二階邏輯不需要關于等詞的公理，因為根據等詞的定義可以推出關于等詞的公理，其中需要用到概括公理。

對于自由變元邏輯，因為它沒有二階量化，所以無法在其中表達概括公理。但是可以在其中表達如下代入規則：

從?（X）推出?（Ψ（x）），其中Ψ對X在?中代入自由。[2]

它斷定，任意可表達公式都可以替換自由關系變元。還可以增加如下函數變元消除規則：

從?推出?*，其中?*是用關系變元替換?中的函數變元所得到的結果。

事實上，由于沒有二階量化，自由變元邏輯中的所有自由變元都被前束全稱量詞約束，也就是說，?（X）相當于?X?（X），﹁?（X）相當于?X﹁?（X），?（X）→Ψ（X）相當于?X（?（X）→Ψ（X））。

可以對標準二階邏輯的概括公理進行某種限制，例如直謂概括公理：

?X?x（Xx??（x）），其中?（x）不包含二階量詞。

也就是說，只有自由變元邏輯的公式可以斷定一個關系的存在。包括直謂概括公理的二階邏輯被稱為直謂二階邏輯。直謂二階理論是一階理論的保守擴張。

在分支二階邏輯中，可以增加分支直謂概括公理：

?Xi?x（Xix??（x）），其中Xi的層次高于?（x）中出現的變元的層次。

另外，還可以增加還原公理：

?Xn?Y0?x（Y0x?Xnx）

它斷定，任給n層關系，都存在一個與之等價的0層關系。

二階邏輯的語義包括標準語義和非標準語義，其中非標準語義又分為亨金語義和一階語義。

標準模型是M≤D，I＞，其中D是一階變元的取值范圍，是二階變元的取值范圍，I是解釋。令s是賦值。項t的指稱記為d（t）。滿足關系?的定義是：

如果d（t）∈s（X），則M，s?Xt。

如果任給與s合同（除X外）的s′，都有M，s′??，則M，s??X?。

如果任給與s合同（除f外）的s′，都有M，s′??，則M，s??f?。

如果任給s，M，s??，則M是?的模型。如果任給M，任給s，都有M，s??，則?是標準有效的。如果存在M，存在s，使得M，s??，則?是標準可滿足的。如果任給M，任給s，如果M，s?Ф，則M，s??，則?是Ф的標準后承。

滿足關系之于標準二階邏輯正如擬滿足關系之于自由變元邏輯。擬滿足關系的定義是：

如果任給與s合同（除二階變元外）的s′，都有M，，則M，。

顯然，M，當且僅當M，s??X?（X）。擬有效、擬可滿足和擬后承的定義與標準有效、標準可滿足和標準后承的定義類似。

亨金模型是HM≤D，D，f，I＞，其中D是一階變元的取值范圍，D是關系變元的取值范圍，f是函數變元的取值范圍，I是解釋。令s是亨金模型的賦值。亨金滿足關系?H的定義是：

如果d（t）∈s（X），則HM，s?HXt

如果任給與s合同（除X外）的s′，HM，s′?H?，則HM，s?H?X?

如果任給與s合同（除f外）的s′，HM，s′?H?，則HM，s?H?f?

亨金有效、亨金可滿足和亨金后承的定義與標準有效、標準可滿足和標準后承的定義類似。擬亨金滿足關系之于亨金滿足關系?H正如擬滿足關系之于標準滿足關系?。

如果D是D上的所有關系，f是D上的所有函數，則亨金模型HM被稱為完整模型FM。令M是標準模型，FM是相應的完整模型。完整模型和標準模型之間存在如下關系：

任給公式?，任給賦值s，M，s??當且僅當FM，s?H?。

亨金語義和標準語義之間存在如下關系：如果?是亨金有效的，則?是標準有效的；如果?是標準可滿足的，則?是亨金可滿足的；如果?是Ф的亨金后承，則?是Ф的標準后承。

一階模型是FOM≤D，D，f，＜I，p，a＞＞，其中D是一階變元的取值范圍，D是關系變元的取值范圍，F是函數變元的取值范圍，I是解釋，p是D×D的子集，即“謂述”關系的解釋，a是從D×f到D的函數，即“應用”函數的解釋。令s是一階模型的賦值，令t的指稱是d（t）。如果f是函數變元，則f（t）的指稱是a（d（t），s（f））。一階滿足關系?FO的定義是：

如果（d（t），s（X））∈p，則FOM，s?FOXt。

如果任給與s合同（除X外）的s′，FOM，s′?FO?，則FOM，s?FO?X?。

如果任給與s合同（除f外）的s′，FOM，s′?FO?，則FOM，s?FO?f?。

一階有效、一階可滿足和一階后承的定義與標準有效、標準可滿足和標準后承的定義類似。

令t在亨金模型下和一階模型下的指稱都是d（t）。令f（t）在亨金模型下的指稱是dH（f（t）），f（t）在一階模型下的指稱是dFO（f（t））。令sH是亨金模型的賦值，sFO是一階模型的賦值。關于項，有如下關系：

dH（f（t））=dFO（f（t））當且僅當a（dFO（t），sFO（f））=sH（f）（dH（t））

關于原子公式，有如下關系：

FOM，s?FOXt

當且僅當（d（t），s（X））∈p

當且僅當d（t）∈s（X）

當且僅當HM，s?HXt

一階模型和亨金模型之間存在如下關系：

任給亨金模型HM，都存在一階模型FOM，任給亨金模型的賦值s，都存在一階模型的賦值s′，使得任給公式?，HM，s?H?當且僅當FOM，s′?FO?。

任給一階模型FOM，都存在亨金模型HM，任給一階模型的賦值s，都存在亨金模型的賦值s′，使得任給公式?，FOM，s?FO?當且僅當HM，s′?H?。

亨金語義和一階語義之間存在如下關系：?是一階有效的當且僅當?是亨金有效的；?是一階可滿足的當且僅當?是亨金可滿足的；?是Ф的一階后承當且僅當?是Ф的亨金后承。

與二階邏輯相關的元理論包括：可靠性、緊致性、L?wenheim-Skolem性質、完全性、范疇性。

標準語義對于標準二階邏輯是可靠的：

令Ф和?分別是標準二階邏輯的公式集和公式。如果?是Ф的推演

后承，則?是Ф的標準后承。

類似的結論也適用于自由變元邏輯和擬語義。注意，在驗證概括公理時，需要在元語言層面假定公理集合論的分離公理。

算術的語言包括：0（零）、s（后繼函數）、+（加法函數）、×（乘法函數）。算術的公理包括：

?x（sx≠0）

?x（x+0=x）

?x（x×0=0）

?x?y（sx=sy→x=y）

?x?y（x+sy=s（x+y））

?x?y（x×sy=x×y+x）

?X（X0∧?x（Xx→Xsx）→?xXx）

上述公理所構成的理論被稱為二階算術。如果把二階算術表述在自由變元邏輯中，則需要去掉最后一條公理前面的全稱量詞，稱其為自由變元算術。下面的結論說明，二階算術唯一地刻畫了自然數結構：

令M1≤D1，I1＞和M2≤D2，I2＞分別是模型。令01、02，s1、s2，+1、+2，×1、×2分別是零、后繼函數、加法函數、乘法函數在M1和M2下的解釋。如果M1和M2都是二階皮亞諾算術的模型，則M1和M2是同構的，也就是說，存在從D1到D2的函數f，使得f（01）=02，任給D1中的a和b，f（s1a）=s2a，f（a+1b）=f（a1）+2f（b1），f（a×1b）=f（a1）×2f（b1）。

上述結論是由戴德金證明的。根據二階算術的同構性，標準二階邏輯的標準語義不具有L?wenheim-Skolem性質。由于二階邏輯的表達力強于一階邏輯，二階邏輯可以刻畫“有窮”和“無窮”，所以標準二階邏輯的標準語義也不具有緊致性。類似地，同構性、非L?wenheim-Skolem性以及非緊致性也適用于自由變元邏輯和擬語義。另外，根據哥德爾不完全性定理，一階算術的真理集不是遞歸可枚舉的，而二階算術包含一階算術，因此二階算術的真理集也不是遞歸可枚舉的，也就是說，存在真但是不可證的標準二階邏輯的語句。因此，標準語義對于標準二階邏輯是不完全的。如果把自由變元邏輯的關系變元和函數變元改寫為非邏輯符號，則自由變元邏輯變成一階邏輯。因此，擬語義對于自由變元邏輯是完全的。但是自由變元算術的擬后承集也不是遞歸可枚舉的。

對于標準二階邏輯，亨金模型不是可靠的，因為它可能不滿足概括公理或選擇公理。類似地，亨金模型對于自由變元邏輯也不是可靠的。如果亨金模型滿足概括公理和選擇公理，則稱其為忠實于標準二階邏輯；如果亨金模型擬滿足代入規則和函數變元消除規則，則稱其為忠實于自由變元邏輯。由此可以得到可靠性和完全性：

令Ф和?分別是標準二階邏輯的公式集和公式。如果?是Ф的推演后承，則任何滿足Ф的忠實的亨金模型也滿足?。

如果任何滿足Ф的忠實的亨金模型也滿足?，則?是Ф的推演后承。

與標準模型不同，在亨金模型中不能定義等詞。在標準模型中，任給元素a∈D，都存在它的單元集；根據?X（Xt?Xs），{a}可以把t和s識別為相同的。但是在亨金模型中，有可能，所以?X（Xt?Xs）不能把t和s識別為相同的。如果任給賦值s，如果M，s??X（Xx?Xy），則x和y的賦值相同，則稱亨金模型M是等詞標準的。由此可以得到緊致性：

如果任意Ф的有窮子集在忠實的（等詞標準的）亨金模型中都是可滿足的，則Ф在忠實的（等詞標準的）亨金模型中是可滿足的。

令HM′≤D′，D′，F′，I′＞是HM≤D，D，f，I＞的亨金子模型[3]。令k是從HM′到HM的函數。如果任給P∈D′，都有k（P）∈D并且P=k（P）∩D′，任給g∈F′，都有k（g）∈f并且g=k（g）|D′[4]，則稱k是對應函數。令s是賦值。sk是新的賦值，sk與s在一階變元上合同；任給關系變元R，如果s把P賦值給R，則sk把k（P）賦值給R；任給函數變元f，如果s把g賦值給f，則sk把k（g）賦值給R。由此可以得到L?wenheim-Skolem性質：

如果HM≤D，D，f，I＞是亨金模型，則存在亨金子模型HM′≤D′，D′，F′，I′＞和對應函數k使得：（1）D′、D′和F′都是可數無窮的；（2）任給公式集Ф和HM′上的賦值s，HM′，s?HФ當且僅當HM，sk?HФ。

類似地，向上的L?wenheim-Skolem性質也成立。