二階邏輯

在邏輯和數學中，二階邏輯是一階邏輯的擴充套件，一階邏輯是命題邏輯的擴充套件。二階邏輯接著被高階邏輯和型別論所擴充套件。一階邏輯和二階邏輯都使用了論域。最一般的二階邏輯還包括量化在函式上的變數，和在下面語法章節解說的變數。二階邏輯的表達能力.二階邏輯比一階邏輯更有表達力。例如，如果論域是所有實數的集合，我們可以在一階邏輯中斷言每個實數都有一個加法逆元：∀"x" ∃"y"("x" + "y" = 0)，但是需要二階邏輯來斷言實數的集合的上確界性質，它聲稱實數的所有有界的、非空集合都有上確界。如果論域是所有實數的集合，下列二階邏輯句子表達了最小上界性質：formula_2在二階邏輯中，有可能寫出聲稱“論域是有限的”或“論域有可數勢的”這樣的形式句子。要說論域是有限的，可使用聲稱從論域到自身的所有單射函式都是滿射的句子。要聲稱論域有可數勢，可以使用聲稱在所有的論域的兩個無限子集之間存在雙射的句子。從向上勒文海姆–斯科倫定理得出在一階邏輯內不可能特徵化有限性或可數性。語形.二階邏輯的語法規定那些表示式是合式公式。除了一階邏輯的語形之外，二階邏輯包括了很多新「種類」的變數。包括：對於剛才定義的每類變數，允許使用全稱和/或存在量詞來建造公式。所以有很多種類的量詞，每類變數兩個。在二階邏輯中的「句子」同一階邏輯一樣也是沒有自由變數的合式公式。在「一元二階邏輯」中，只增加了給論域的子集的變數。有所有種類的變數的二階邏輯有時叫做「完全二階邏輯」來區別於一元二階邏輯。同於一階邏輯，二階邏輯可以在特定二階語言中包含非邏輯符號。但是它們是受限制於它們形成的所有項必須要麼是一階項。語義.二階邏輯的語義建立每個句子的意義。不像只有一個標準語義的一階邏輯，二階邏輯有兩個常用的不同語義：「標準語義」和「Henkin語義」。在這些語義中，一階量詞和邏輯連結詞的解釋是同於一階邏輯的。只有在二階量詞變數的新量詞需要定義語義。在標準語義中，量詞取值於適當種類的“所有”集合或函式上。所以一旦確立了一階變數的論域，餘下的量詞的意義就固定了。這種語義給予了二階邏輯強大的表達能力，本文采用了這種語義。在Henkin語義中，每個二階變數種類都有它自己取值的特定論域，它可以是所有此類的所有集合或函式的真子集。Leon Henkin定義了這種語義並證明了對一階邏輯成立的哥德爾完全性定理和緊緻性定理，在有Henkin語義的二階邏輯中繼續有效。這是因為Henkin語義幾乎等同於多種類一階語義，它透過增加額外的變數種類來模擬二階邏輯的新變數。帶有Henkin語義的二階邏輯不比一階邏輯有更大表達能力。Henkin語義經常用在二階算術的研究中。演繹系統.邏輯的演繹系統是確定哪些公式序列構成有效證明的一組推理規則和邏輯公理。很多演繹系統可以用於二階邏輯，儘管它們都不能針對標準語義是完備的。每個這種系統都是可靠的，這以為它們可以證明的任何句子在適當的語義中都是邏輯有效的。可用的最弱的演繹系統由標準的一階邏輯演繹系統擴充上對二階項的代換規則。這種演繹系統常用於二階算術的研究中。Shapiro (1991)和Henkin考慮的演繹系統想擴充的一階演繹系統增加了內涵公理和選擇公理二者。這些公理對於二階語義是可靠的。它們對於Henkin語義是可靠的，只要考慮的是滿足內涵和選擇公理的Henkin模型。為什麼二階邏輯不能歸約成一階邏輯.一個樂觀的人可能嘗試按下述方法把二階邏輯歸約成一階邏輯。把論域從所有實數的集合擴充套件為所有實數集合的集合。向語言增加一個新的二元謂詞：成員資格關係。這樣，二階的句子就成為一階的了。但要注意這個論域被斷言為包括實數的「所有」集合。這個需求沒有被簡約到到一階句子! 真有某種方式來完成這種簡約嗎?經典的Löwenheim-Skolem定理蘊含了這是沒有的。這個定理蘊含了有某個「R」的可數無限子集，它的成員我們稱為“內在數”，和某個內在數集合的可數無限蒐集，它的成員我們稱為“內在集合”，而由內在數和內在集合組成的這個論域滿足實數和實數集合所滿足的所有一階句子。特別是，它有效的滿足一種最小上界公理：有“內在”上界的所有非空“內在”集合都有最小“內在”上界。所有內在數的集合的可數性。這個構造密切關聯於斯科倫悖論。所以實數和實數的集合的一階理論可以有很多模型，其中一些是可數的。但是實數的二階理論只有一個模型。這可以從只有一個阿基米德完備有序域的經典定理，和所有阿基米德完備有序域的在二階邏輯中可表達的事實得出。這證實了實數的二階理論不能簡約到一階理論，在實數的二階理論之後一個模型但對應的一階理論有很多模型的意義上。有很多極端例子證實帶有標準語義的二階邏輯要比一階邏輯表達能力強。有一個有限二階理論其唯一的模型是實數的，如果連續統假設成立，而它沒有模型如果連續統假設不成立。這個理論由把實數刻畫為完備阿基米德有序域加上聲稱這個域是第一個不可數勢的公理的所有有限理論構成，這個例子展示了二階邏輯中的一個句子是否是相容的是非常微妙的問題。下一節中描述二階邏輯的另外的限制。二階邏輯和元邏輯結論.作為哥德爾不完全性定理的必然結果，你不要打算讓二階公式的“可證明性”能給出同時滿足下面三個想要的特性的"語言的標準釋義":有時候這表達為二階邏輯不容許完備的證明論。在這方面二階邏輯不同於一階邏輯，至少這是邏輯學家避免使用它的一個理由。。在1950年Leon Henkin用Henkin語義給出對二階邏輯的充分的個體的所有集合的集合。他的這個證明同對一階函式演算做的證明在一起進行的。這兩個結論包含在他的學位論文中。二階邏輯的歷史和有爭議的價值.當謂詞邏輯被弗雷格介紹給數學社群的時候，他確實使用不同的變數來區分在物體上量化和在屬性和集合上的量化；但是他自己沒有去區分出兩類不同的邏輯。在發現羅素悖論之後，認識到了他的系統有些毛病。最終邏輯學家建立了以各種方式做限制的弗雷格邏輯—現在叫做一階邏輯—除去了這個問題：集合和謂詞在一階邏輯中不能被單獨量化。現在標準的邏輯的階數等級就是從那時開始的。發現了集合論可以在一階邏輯的設施內公式化為公理化系統階邏輯的工作的普遍放棄。這種捨棄由一些邏輯學家活躍的推動著，最著名的是蒯因。蒯因推進了這種觀點，在謂詞語言句子比如"Fx"中，x被認為是一個變數或指稱一個物體的名字，所以可以被量化，如“對於所有的東西，情況是. . .”。但是F被認為是一個不完整句子的“一個縮寫”，不是一個物體。所以要使用一個謂詞作為變數就要讓它佔據只有個別的變數可以佔據的一個名字的位置。這種推理被Boolos拒絕了。近年來二階邏輯有某種程度的恢復，由George Boolos把二階量化解釋為在同一階量化一樣的域上的複數量化所支援。Boolos進一步指出句子的非一階可表達性，比如“有些罪犯只相互傾慕”和“有些Fianchetto人進入倉庫而沒有任何別人陪同”。這-{只能}-用二階量化的完全力量來表達。量化同樣足以表達特定類的非一階可表達的句子而不使用二階量化)。但是，已經說過在有些數學分支中比如拓撲學中，需要二階邏輯的能力來做完整的表達。這方面的工作已經由Stephen G. Simpson在逆數學的名義下完成了。已經證明了二階邏輯不只對-{表}-達經典數學的某些重要部分是必須的，而且它也可以用做模型論和數學基礎的工具。存在性片段在有限結構上的能力.單類二階邏輯是沒有全稱量詞的二階邏輯。在詞formula_3之上，所有的MSO公式都可以轉換成確定的有窮自動機。它可以再轉換成EMSO公式。所以EMSO和MSO在這種詞上是等價的。對於樹作為輸入，這個結果同樣成立。但是，在有限網格formula_4之上，這個性質不再成立，因為瓦片系統識別的語言不閉合於補集之下。因為全稱量詞等價於否定的存在量詞，它不能被表達，全稱和存在量詞的交替生成了在formula_4上的更大的一類語言。應用於複雜性理論.二階邏輯的各種形式的表達力密切的連繫於計算複雜性理論。特別是：在這些語言類之間的聯絡直接影響了邏輯的相對的表達力；例如，如果PH=PSPACE，則向二階邏輯增加的傳遞閉包運算元不使它更有表現力。