二階述語論理
述語論理を数学界に初めてもたらしたのはチャールズ・サンダース・パースであり、彼は現代とよく似た記法を用いていた(彼はまた Second-order logic という用語も生み出した)。パースの数年前にゴットロープ・フレーゲの研究成果が発表されていたが、これはバートランド・ラッセルとアルフレッド・ノース・ホワイトヘッドが広く紹介するまであまり知られていなかった。現代ではフレーゲの業績の方がよく知られている。フレーゲは量化の種によって異なる変項を使っていたが、彼には2種類の異なる論理を扱っているという認識はなかった。ラッセルのパラドックスによって、その体系に問題があることが明らかとなった。論理学者らは問題を解決すべく、フレーゲの論理に制限を加える各種方法を検討し、それが一階述語論理となった。一階述語論理では、集合や属性は量化できないことになった。このような論理の階層化がこのころ初めてなされるようになった。
一階述語論理を使うと、集合論を公理的体系として形式化できることがわかり(完全性の問題はあるが、ラッセルのパラドックスほど悪いことではない)、公理的集合論が生まれ、集合は数学の基盤となった。算術、メレオロジー、その他の様々な論理的理論が一階述語論理の範囲内で公理的に定式化でき、ゲーデルやスコーレムが一階述語論理に固執したこともあって、二階や高階の述語論理はほとんど省みられなかった。
この状況を決定付けたのは、ウィラード・ヴァン・オーマン・クワインなどの論理学者である。クワインは Fx のような述語言語文について、x を変項またはオブジェクトの名前とみなし、それ故に量化可能とし、「全ての物について...が成り立つ」という意味だとしたが、F は単なる不完全な文の「省略形」であるとし、オブジェクトの名前とは考えなかった(属性のような抽象的オブジェクトとも考えなかった)。例えばそれは「...は犬である」かもしれない。しかし、そのような概念に量化を考えても何の意味もない。このような立場は、フレーゲの概念と事物を区別する立場と同じである。従って、述語を変項として扱うことは、個体変項だけが占めていた位置を共有することを意味する。そのような考え方は Boolos によって拒絶されている。
近年、二階述語論理は一種の回復の途上にある。この傾向をもたらしたのは George Boolos による二階の量化の解釈であり、彼は一階の量化と同じドメインでの複数形の量化として二階の量化を解釈した。Boolos はさらに一階述語論理では記述できない文を例に挙げ、完全な二階述語論理の量化でのみそれらを表現可能であるとした。しかし、その一部は二階述語論理を持ち出すまでもなく、一階述語論理に若干の拡張を加えるだけで表現可能である。
有限な構造についての二階述語論理の各種形式の表現能力は、計算複雑性理論と密接に関係している。記述計算量の研究では、複雑性クラスを説明するのにそれに属する言語を表現できる論理体系の能力で表す。そのため、二階述語論理を前提として次のような複雑性クラスを説明できる。
NP は、存在量化二階述語論理で表現できる言語の集合である(Fagin の定理、1974年)。
co-NP は、全称量化二階述語論理で表現できる言語の集合である。
PH は、二階述語論理で表現できる言語の集合である。
PSPACE は、二階述語論理に推移閉包演算子を追加したもので表現できる言語の集合である。
EXPTIME は、二階述語論理に最小不動点演算子を追加したもので表現できる言語の集合である。
クラス間の関係は論理の表現能力にも直接影響を及ぼす。例えば、PH=PSPACE であることが明らかになれば、推移閉包演算子を追加しても二階述語論理の表現能力には何の違いもないことが明らかになるだろう。