23/12/13 11:00:46.58 BJtZkva3.net
つづき
他の論理との比較
・型つき一階述語論理は変項や項に型または種を導入したものである。型の個数が有限個であれば普通の一階述語論理と大きな違いはなく、有限個の単項述語で型を記述し、いくつかの公理を追加すればよい。真理値として Ω という特殊な型を持つ場合があるが、その場合の論理式は Ω 型の項となる。
・二階述語論理は部分集合および関係、すなわち全ての述語の量化を許すものである。
・高階述語論理は述語を引数とする述語など、さらに一般化したものの量化を許す。
こうした論理の多くは、一階述語論理の何らかの拡張と言える。
URLﾘﾝｸ(ja.wikipedia.org)
二階述語論理（英: second-order predicate logic）
二階論理の表現能力
二階述語論理は一階述語論理よりも表現能力が高い。
歴史と論争
フレーゲは量化の種によって異なる変項を使っていたが、彼には2種類の異なる論理を扱っているという認識はなかった。ラッセルのパラドックスによって、その体系に問題があることが明らかとなった。論理学者らは問題を解決すべく、フレーゲの論理に制限を加える各種方法を検討し、それが一階述語論理となった。一階述語論理では、集合や属性は量化できないことになった。このような論理の階層化がこのころ初めてなされるようになった。
一階述語論理を使うと、集合論を公理的体系として形式化できることがわかり（完全性の問題はあるが、ラッセルのパラドックスほど悪いことではない）、公理的集合論が生まれ、集合は数学の基盤となった。算術、メレオロジー、その他の様々な論理的理論が一階述語論理の範囲内で公理的に定式化でき、ゲーデルやスコーレムが一階述語論理に固執したこともあって、二階や高階の述語論理はほとんど省みられなかった。
近年、二階述語論理は一種の回復の途上にある。この傾向をもたらしたのは George Boolos による二階の量化の解釈であり、彼は一階の量化と同じドメインでの複数形の量化として二階の量化を解釈した。Boolos はさらに一階述語論理では記述できない文を例に挙げ、完全な二階述語論理の量化でのみそれらを表現可能であるとした。しかし、その一部は二階述語論理を持ち出すまでもなく、一階述語論理に若干の拡張を加えるだけで表現可能である。
計算複雑性理論への応用
有限な構造についての二階述語論理の各種形式の表現能力は、計算複雑性理論と密接に関係している。記述計算量の研究では、複雑性クラスを説明するのにそれに属する言語を表現できる論理体系の能力で表す。そのため、二階述語論理を前提として次のような複雑性クラスを説明できる
(引用終り)
以上