二階述語論理とは？ わかりやすく解説

二階述語論理（にかいじゅつごろんり、英: second-order predicate logic）あるいは単に二階論理（にかいろんり、英: second-order logic）は、一階述語論理を拡張した論理体系であり、一階述語論理自体も命題論理を拡張したものである^[1]。二階述語論理もさらに高階述語論理や型理論に拡張される。

一階述語論理と同様に議論領域（ドメイン）の考え方を使う。ドメインとは、量化可能な個々の元の集合である。一階述語論理では、そのドメインの個々の元が変項の値となり、量化される。例えば、一階の論理式 ∀x (x ≠ x + 1) では、変項 x は任意の個体を表す。二階述語論理は個体の集合を変項の値とし、量化することができる。例えば、二階の論理式 ∀S ∀x (x ∈ S ∨ x ∉ S) は、個体の全ての集合 S と全ての個体 x について、x が S に属するか、あるいは属さないかのどちらかであるということを主張している。最も一般化された二階述語論理は関数の量化をする変項も含んでいる（詳しくは後述）。

二階論理の表現能力

二階述語論理は一階述語論理よりも表現能力が高い。例えば、ドメインが全ての実数の集合としたとき、一階述語論理を使って「それぞれの実数には加法の逆元が存在する」ということを ∀x ∃y (x + y = 0) と表せる。しかし、「空でなく上に有界な実数の集合があるとき常にその集合には上限が存在する」という命題を表すには、二階述語論理が必要となる。ドメインが全ての実数の集合としたとき、次の二階の論理式がこの命題を表している。

${\displaystyle \forall A{\Big [}(\exists w(w\in A)\land \exists z\,\forall w(w\in A\rightarrow w\leq z))\rightarrow \exists x\,\forall y([\forall w(w\in A\rightarrow w\leq y)]\leftrightarrow x\leq y){\Big ]}.}$カテゴリ