二階述語論理とは？一階述語論理との違いも！（2階述語論理：高階論理：量化子の対象：意味論の違いなど）

二階述語論理とは？一階述語論理との違いも！（2階述語論理：高階論理：量化子の対象：意味論の違いなど）

二階述語論理は、個々の対象だけでなく、性質・関係・集合そのものについても量化できる論理体系です。

一階述語論理より豊かな表現力を持つ一方で、完全性やモデル理論の扱いには重要な違いがあります。

数学基礎論、形式意味論、計算機科学、哲学などで登場するため、量化子が何を対象にするのかを押さえることが理解への近道になるでしょう。

二階述語論理の全体像

それではまず二階述語論理の全体像について解説していきます。

個体以外にも広がる量化の対象

一階述語論理では、全称量化子や存在量化子が指すのは、原則として個体です。

たとえば「すべての人は死ぬ」という文は、各人を変数に代入しながら考えます。

これに対して二階述語論理では、性質・述語・関係・集合を変数として扱える点が中心的な特徴です。

「ある性質Pが存在して、Pを満たすものだけが特定の条件を満たす」といった表現も、形式的に書けます。

ここでいう二階とは、難易度が二段階という意味ではありません。

変数が個体だけでなく、個体に当てはまる述語の側にも及ぶことを表す名称です。

二階述語論理は英語でsecond-order logicと呼ばれ、2階述語論理という表記も使われます。

高階論理という言葉と近い場面もありますが、厳密には二階論理より広い概念を指すことがあります。

述語変数と関係変数の役割

二階述語論理では、P、Q、Rのような記号を述語変数として用います。

P(x)は「個体xが性質Pを持つ」という読み方になります。

さらにR(x,y)のような二項関係変数を使えば、二つの個体の間に成り立つ関係そのものを量化できます。

たとえば親子関係、順序関係、到達可能性などを、固定された一つの関係としてではなく、変化しうる関係として論じられます。

対象について語るだけでなく、対象を分類する仕方についても語れることが、二階述語論理の表現力につながります。

この性質により、有限性や自然数の帰納法のような概念を、より直接的に記述できる場合があります。

数学と情報分野での位置付け

数学では、自然数論や集合論に関係する公理化で二階論理が話題になります。

代表例はペアノ算術の二階的な定式化です。

帰納法をすべての部分集合や性質について要求できるため、意図した自然数の構造を強く特徴付けられます。

計算機科学では、記述計算量理論において二階論理が重要な役割を果たします。

グラフの性質を表現する論理式と、計算量クラスとの対応を調べる研究では、存在二階論理などが利用されます。

ただし、表現力が高いことは常に扱いやすさを意味するわけではありません。

証明可能性、決定可能性、計算手続きの設計では、表現力の強さが課題を増やすこともあります。

一階述語論理との相違点

続いては一階述語論理との相違点を確認していきます。

変数が指す範囲の違い

最も基本的な違いは、変数と量化子の届く範囲です。

一階述語論理の変数x、y、zは、議論の領域に含まれる個体を指します。

領域が人間なら、人間が変数の値になります。

領域が自然数なら、0、1、2などの自然数が変数の値です。

二階述語論理では、個体変数に加え、個体の集合や性質を受け取る変数も導入します。

そのため「すべての部分集合」「ある二項関係」といった内容を一つの論理式で表せます。

比較項目	一階述語論理	二階述語論理
量化子の主な対象	個体	個体、性質、集合、関係
述語記号	通常は固定された記号	変数として量化できる
表現力	比較的抑えられる	非常に高い
完全性定理	標準的意味論で成立	標準的意味論では成立しない
用途	モデル理論、証明論、基礎的形式化	数学構造の特徴付け、記述計算量理論

この違いは記号の量が増えるというだけではありません。

何を存在するものとして認めるかという意味論の前提にも関わります。

表現できる性質の違い

一階述語論理では、ある構造が有限であることを一つの文で表すことはできません。

これはコンパクト性定理と深く関係しています。

一方で二階述語論理なら、すべての単射が全射であるという性質を利用し、有限性を特徴付ける形式を考えられます。

また、自然数の通常の順序構造を表したい場合も、二階述語論理は力を発揮します。

一階のペアノ算術には、標準的な自然数以外のモデルが存在します。

二階のペアノ公理を標準意味論で解釈すると、自然数の構造を同型を除いて一意に定められます。

ただし、二階述語論理で書けることと、簡単に計算・証明できることは別問題です。

高い表現力には、形式体系としての複雑さが伴います。

完全性とコンパクト性の違い

一階述語論理には、ゲーデルの完全性定理があります。

これは、すべてのモデルで真となる論理式が、適切な証明体系でも証明できることを示す重要な結果です。

さらにコンパクト性定理も成立し、無限個の文の集合が充足可能かどうかを有限部分集合から考えられます。

二階述語論理を標準意味論で解釈する場合、こうした性質は一般には維持されません。

有効な完全証明体系を作れないことは、二階論理を学ぶうえで欠かせない論点です。

つまり、すべての標準的に妥当な二階論理式を、機械的に列挙可能な公理と推論規則だけで完全に捉えることはできません。

量化子の対象と記法

続いては量化子の対象と記法を確認していきます。

個体量化子の読み方

全称量化子∀xは、すべてのxについてという意味です。

存在量化子∃xは、あるxが存在してという意味になります。

一階述語論理では、xに代入されるものは領域内の個体です。

たとえば領域を整数と決めた場合、∀xはすべての整数xについてと読まれます。

述語F(x)がxは偶数であることを意味するなら、式の真偽は各整数に対するFの成否で決まります。

この基本的な仕組みは二階述語論理でも残ります。

二階述語論理は一階の表現を含み、その上に別の種類の量化を追加した体系と考えると理解しやすいでしょう。

述語量化子と集合量化子の読み方

二階述語論理では、∀Pや∃Pのような表記を使います。

ここでPは一項述語変数であり、領域の要素に対して真か偽かを割り当てる対象です。

集合論的に見れば、Pは領域の部分集合と対応します。

したがって∃Pは、ある部分集合Pが存在してという意味として理解できます。

二項述語変数Rなら、Rは領域上の二項関係に対応します。

∀Rは、考えられるすべての二項関係Rについてという読み方です。

述語は単なる名前ではなく、どの対象に当てはまるかという範囲を持つ点が大切です。

この範囲をどう認めるかによって、後で見る標準意味論とヘンキン意味論の違いが生じます。

自由変数と束縛変数の区別

量化子の後に置かれた変数は、その量化子によって束縛されます。

たとえば∀x P(x)では、xは束縛変数です。

一方、Pそのものを量化していない場合、Pは自由な述語変数として残ります。

∀P∀x P(x)のように書けば、Pもxも束縛された閉じた式になります。

二階述語論理では変数の種類が増えるため、どの量化子がどの変数に対応するかを丁寧に追う必要があります。

特に、個体変数と述語変数を混同すると、式の意味が大きく変わります。

論理式を読む際は、変数の階数、量化子の作用域、述語の項数の三点を確認するとよいでしょう。

意味論とモデルの考え方

続いては意味論とモデルの考え方を確認していきます。

標準意味論の特徴

標準意味論では、二階変数は対象領域上で考えられるすべての性質や関係を走ります。

領域Dに対して一項述語変数Pは、Dのすべての部分集合を取り得ます。

二項関係変数Rは、DとDの直積のすべての部分集合を取り得ます。

この解釈は自然で直観的ですが、対象となる集合が非常に大きくなります。

有限でない領域では、べき集合の規模が急速に増えることも無視できません。

標準意味論は強い表現力の源であり、同時に完全性が失われる理由にも関係します。

二階ペアノ公理が自然数を圏論的に特徴付けられるのは、この標準意味論を採用するからです。

ヘンキン意味論の特徴

ヘンキン意味論では、二階変数が走る範囲を、すべての部分集合や関係に限定しません。

あらかじめ選ばれた性質や関係の集合だけを二階変数の値として認めます。

その結果、見かけは二階的な言語であっても、一階論理に近い方法でモデル理論を展開できます。

ヘンキン意味論の下では、二階論理にも完全性定理に対応する結果を得られます。

ただし、標準意味論で得られる圏論性や強い特徴付けは、そのまま保証されません。

観点	標準意味論	ヘンキン意味論
述語変数の範囲	すべての部分集合・関係	指定された範囲の部分集合・関係
自然数の圏論的特徴付け	可能	一般には不可能
完全性に対応する性質	一般には成立しない	成立する形で扱える
直観との近さ	集合論的直観に近い	形式的操作に適する

どちらが絶対に正しいというより、研究目的に応じて意味論を区別することが重要です。

圏論性と非標準モデル

ある公理系が圏論的であるとは、同型を除けば一つのモデルしか持たないことを指します。

二階ペアノ公理は標準意味論のもとで圏論的です。

これは、意図した自然数の構造だけを捉えたいときに大きな利点になります。

一方、一階論理では、無限モデルを持つ公理系に対して非標準モデルが現れることがあります。

一階ペアノ算術にも、通常の自然数以外の要素を含むモデルが存在します。

この事実は一階論理の欠点というより、完全性・コンパクト性・ローヴェンハイム・スコーレムの定理と結び付いた性質です。

高階論理との関係

続いては高階論理との関係を確認していきます。

二階論理が占める階層

二階述語論理は、階層化された高階論理の一部として位置付けられます。

一階では個体について量化します。

二階では個体の性質や関係について量化します。

三階では、性質の性質や、述語の集合に関わる対象について量化する考え方が登場します。

このように階数を上げるほど、より抽象的な対象を扱えるようになります。

二階述語論理は、高階論理への最初の本格的な入口といえるでしょう。

ただし文献によっては、高階論理を単純型理論やラムダ計算と結び付けて説明する場合もあります。

単純型理論とのつながり

ラッセルの型理論やチャーチの単純型理論では、対象に型を割り当てます。

個体の型、個体から真偽値への関数の型、さらにその関数を受け取る関数の型というように、対象の種類を明確に分けます。

この発想は、自己言及に由来するパラドックスを避けるためにも役立ちます。

二階述語論理の述語変数は、個体から真偽値へ向かう関数のように見なせます。

型付きの枠組みでは、どの記号がどの種類の引数を受け取れるかが明確になります。

プログラミング言語の型システム、証明支援系、関数型プログラミングとの接点もここにあります。

実務的な使い分け

論理学の入門やデータベース理論の基礎では、一階述語論理をまず学ぶのが一般的です。

構文、意味論、証明、モデルの基本を比較的安定した形で身に付けられるためです。

自然数の特徴付け、集合の量化、記述計算量理論を学ぶ場合には、二階述語論理が必要になります。

さらに定理証明や高機能な仕様記述では、高階論理や型理論を扱うことがあります。

重要なのは、表現力が強い体系を選べば常に有利というわけではない点です。

表したい対象と、証明・計算で必要な性質のバランスを見ながら論理体系を選ぶことが求められます。

二階述語論理の理解の整理

最後に二階述語論理の理解を整理していきます。

二階述語論理とは、個体だけでなく、性質・集合・関係にも量化子を及ぼせる論理体系です。

一階述語論理との最大の違いは、量化子の対象が個体に限られないことにあります。

そのため、有限性や二階ペアノ公理の帰納法のように、一階論理では直接扱いにくい性質を表現できます。

一方で、標準意味論では完全性定理やコンパクト性定理が成立しないという重要な制約もあります。

標準意味論はすべての部分集合や関係を対象にし、ヘンキン意味論は認める範囲を限定するという違いも押さえておきたいところです。

表現力、意味論、証明可能性は切り離せない三つの論点です。

二階述語論理を学ぶ際は、記号だけを追うのではなく、量化子が何を走るのか、どの意味論を採用しているのかを確認すると理解が深まるでしょう。