一階述語論理 一階述語論理に関する定理

ウィキペディア

一階述語論理

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/05/15 09:03 UTC 版)

一階述語論理に関する定理

以下、健全性定理と完全性定理以外の重要な定理を列挙する。

1. コンパクト性定理 ： 文の集合 Σ のすべての有限部分集合がモデルを持つならば、Σ 自身もモデルを持つ。
2. レーヴェンハイム・スコーレムの定理 ： κ を無限基数とする。論理式全体の集合の濃度が κ であるような一階の言語における文の集合がモデルを持つなら、それは濃度 κ 以下のモデルも持つ。
3. 恒真論理式全体の集合は（言語にアリティ 2 以上の述語が一つでも含まれていると）決定可能でない。つまり、任意に論理式が与えられたとき、それが恒真であるか否かを判定するアルゴリズムは存在しない（「チューリングマシンの停止問題」を参照）。この結果はアロンゾ・チャーチとアラン・チューリングがそれぞれ独立に導き出した。正確には、恒真論理式のゲーデル数全体の集合は帰納的でないということである。
4. それでも、与えられた論理式が恒真であるとき、かつそのときにのみ 1 (yes) を出力して停止するアルゴリズムは存在する。ただし、恒真でない論理式を入力した場合はこのアルゴリズムは停止しないかもしれない。これを、恒真論理式全体の集合は準決定可能であるという。これは正確に述べれば、恒真論理式のゲーデル数全体の集合が帰納的可算であるということである。
5. 1 変数述語記号だけを非論理記号に持つ言語の恒真論理式全体の集合は決定可能である。

他の論理との比較

• 型つき一階述語論理は変項や項に型または種を導入したものである。型の個数が有限個であれば普通の一階述語論理と大きな違いはなく、有限個の単項述語で型を記述し、いくつかの公理を追加すればよい。真理値として Ω という特殊な型を持つ場合があるが、その場合の論理式は Ω 型の項となる。
• 弱二階述語論理は有限個の部分集合の量化を許すものである。
• 単項二階述語論理は部分集合、すなわち単項述語の量化のみを許すものである。
• 二階述語論理は部分集合および関係、すなわち全ての述語の量化を許すものである。
• 高階述語論理は述語を引数とする述語など、さらに一般化したものの量化を許す。
• 直観主義的一階述語論理は古典命題計算ではなく直観主義を導入するものである。例えば、¬¬φ は必ずしも φ と等しいとは限らない。
• 様相論理は様相演算子を追加したものである。これは、直観的に説明すれば、「～は必然的である」および「～は可能である」を意味する演算子である。
• 無限論理は無限に長い文を許す。例えば無限個の論理式の連言や選言が許されたり、無限個の変項を量化できたりする。
• 新たな量化子を加えた一階述語論理は、例えば「……であるような多くの x が存在する」といった意味の新たな量化子 Qx, ..., を持つ。

こうした論理の多くは、一階述語論理の何らかの拡張と言える。これらは、一階述語論理の論理演算子と量化子を全て含んでいて、それらの意味も同じである。リンドストレムは、一階述語論理の拡張には、レーヴェンハイム・スコーレムの下降定理とコンパクト性定理の両方を満足するものが存在しないことを示した。この定理の内容を精確に述べるには、論理が満たしていなければならない条件を数ページにわたって列挙する必要がある。例えば、言語の記号を変更しても各文の真偽が基本的に変わらないようになっていなければならない。

一階述語論理のいくぶんエキゾチックな等価物には、次のものがある。順序対構成をもつ一階述語論理は、特別な関係として順序対の射影を持つ関係代数（これはタルスキと Givant によって構築された）と精確に等価である。