二階邏輯

二階邏輯允許有各種解釋；它經常被認為包含在域的子集上，或在來自這個域到自身的函式上的量化，而不只是在這個域的個別成員之上。例如，如果這個域是所有實數的集合，通過如下書寫你可以在一階邏輯中斷言每個實數的加性逆元的存在性

但你需要使用二階邏輯來斷言實數的最小上界性質:

並在點的位置插入一個陳述，如果 A 是非空並且它在 R 中有一個上界，則A 在 R 中有一個最小上界。

在數理邏輯中，二階邏輯是命題邏輯或一階邏輯的擴展，它包含在謂詞位置上（而不是像一階邏輯那樣只能在項的位置上）的變數，和約束它們的量詞。所以： 我們可以表達關於 Jones 的二值原理： 對於所有性質，Jones 要么有它要么沒有它。

基本介紹

• 中文名：二階邏輯
• 外文名：Two order logic
• 提出者：弗雷格
• 套用學科：邏輯學
• 適用領域範圍：學術研究

基本定義

作為另一個例子，我們用一階邏輯可以把一個句子/斷定寫成:

但是我們不能對謂詞做同樣的事情。就是說，下列表達式:

不是一階邏輯的句子。但它是二階邏輯的合法的句子。

套用於複雜性理論

二階邏輯的各種形式的表達力密切的連繫於計算複雜性理論。特別是:NP是用存在性二階邏輯可表達的語言集合。 co-NP是用全稱二階邏輯可表達的語言的集合。 PH是用二階邏輯可表達的語言的集合。PSPACE是用帶有增加的傳遞閉包運算元的二階邏輯可表達的語言的集合。EXPTIME是用帶有增加的最小不動點運算元的二階邏輯可表達的語言的集合。 在這些語言類之間的聯繫直接影響了邏輯的相對的表達力；例如，如果PH=PSPACE，則向二階邏輯增加的傳遞閉包運算元不使它更有表現力。

歷史和價值

當謂詞邏輯被弗雷格(獨立的和更有影響力的 Peirce，他提出了術語二階邏輯)介紹給數學社區的時候，他確實使用不同的變數來區分在物體上量化和在屬性和集合上的量化；但是他自己沒有去區分出兩類不同的邏輯。在發現羅素悖論之後，認識到了他的系統有些毛病。最終邏輯學家建立了以各種方式做限制的 Frege 邏輯— 現在叫做一階邏輯—除去了這個問題: 集合和謂詞在一階邏輯中不能被單獨量化。現在標準的邏輯的階數等級就是從那時開始的。

發現了集合論可以在一階邏輯的設施內公式化為公理化系統(損失了某種完備性，但是不至於向羅素悖論那么糟糕)，並且真就這么做了(參見Zermelo-Fraenkel 集合論)，因為集合是數學的關鍵。算術、mereology 和各種其他強力邏輯理論可以被公理化的公式化，而不用使用比一階量化更多的邏輯設施，隨著哥德爾和 Skolem 忠於一階邏輯，導致了對二(或更高)階邏輯的工作的普遍放棄。

這種捨棄由一些邏輯學家活躍的推動著，最著名的是蒯因。蒯因推進了這種觀點，在謂詞語言句子比如 Fx 中，"x" 被認為是一個變數或指稱一個物體的名字，所以可以被量化，如"對於所有的東西，情況是 . . ." 。但是 "F" 被認為是一個不完整句子的一個縮寫，不是一個物體(甚至不是抽象的物體如性質)的名字。例如，它可能意味著" . . . 是個狗"，認為在這種事物上可以做量化是沒有什麼意義的。(這種立場同弗雷格自己對概念-物體區別的討論是非常一致的)。所以要使用一個謂詞作為變數就要讓它占據只有個別的變數可以占據的一個名字的位置。這種推理被 Boolos 拒絕了。

現狀

近年來二階邏輯有某種程度的恢復，由 George Boolos 把二階量化解釋為在同一階量化一樣的域上的複數量化所支持。Boolos 進一步指出句子的非一階可表達性，比如 "有些罪犯只相互傾慕" 和 "有些 Fianchetto 人進入倉庫而沒有任何別人陪同"。 這只能用二階量化的完全力量來表達。(實際上這不是真的，因為一般性的量化和偏序的(或分支的)量化同樣足以表達特定類的非一階可表達的句子而不使用二階量化)。

但是，已經說過在有些數學分支中比如拓撲學中，需要二階邏輯的能力來做完整的表達。這方面的工作已經由 Stephen G. Simpson 在逆數學的名義下完成了。已經證明了二階邏輯不只對表達經典數學的某些重要部分是必須的，而且它也可以用做模型論和數學基礎的工具。