一階述語論理には、2つの顔があります。
- 統語論(シンタックス):論理式を、意味を考えずに 記号の列 として扱う。どんな記号列が論理式か、どう書き換えれば「証明」になるかを、規則だけで決める。
- 意味論(セマンティクス、モデル論):論理式を、ある 構造 の上で真か偽かが決まるものとして扱う。「正しい」とは、どの構造でも真になることだと考える。
同じ論理式に、「証明できる」()と「正しい」()という、まったく別の方法で定義された2つの性質が与えられます。この2つが一致する、というのが 完全性定理 です。
この記事では、言語の定義から始めて、統語論と意味論を並べて組み立て、最後に両者をつなぐ健全性定理と完全性定理にたどり着きます。各節では、統語論の概念か意味論の概念かを意識できるように書いていきます。
| 統語論(記号) | 意味論(構造) | |
|---|---|---|
| 対象 | 項・論理式(記号列) | 構造・領域の要素 |
| 基本の関係 | (導出できる) | (すべてのモデルで成り立つ) |
| 「矛盾しない」 | 無矛盾(矛盾が導出できない) | 充足可能(モデルがある) |
| 道具 | 公理と推論規則 | 充足関係の帰納的な定義 |
| つなぐ定理 | 健全性: | 完全性: |
1. 言語
まず、使ってよい記号を決めます。記号は、どの理論でも共通の 論理記号 と、扱う対象ごとに選ぶ 非論理記号 に分かれます(文献 [12])。
論理記号
- 変数:(可算無限個)
- 論理結合子:(でない)、(ならば)、(かつ)、(または)、(同値)
- 量化子:(すべての)、(ある)
- 等号:
- かっこ:、、および区切りの
非論理記号(シグネチャ)
- 定数記号:
- 関数記号:(それぞれ引数の個数 が決まっている)
- 関係記号(述語記号):(それぞれ引数の個数 が決まっている)
非論理記号の集まりを 言語 と呼ぶことにします。例を挙げます。
| 理論 | 言語 |
|---|---|
| 群 | 定数 、2変数関数 、1変数関数 |
| 順序 | 2変数関係 |
| 算術 | 定数 、1変数関数 (次の数)、2変数関数 、 |
| 集合論 | 2変数関係 |
この段階では、 はまだ「小さい」という意味を持たず、ただの記号です。意味は3章で構造が与えます。
2. 統語論:項と論理式
2.1 項
項 は、領域の「もの」を指す表現です。
算術の言語なら、、、、 などが項です。読みやすさのため、 は と書きます。
2.2 論理式
論理式 は、真か偽かが問題になる表現です。
たとえば、群の公理は群の言語の論理式で書けます。
2.3 自由変数と束縛変数
論理式 では、 は に 束縛 されていて、 は 自由 です。自由変数の集合 は、再帰的に定義できます。
- 原子論理式:現れる変数すべて
- 、(ほかの結合子も同様)
自由変数を持たない論理式を 文 といいます。文は、構造さえ決まれば真か偽かが決まります。自由変数を持つ論理式は、その変数に何を入れるかが決まるまで真偽が決まりません(3.3 で見ます)。
の自由変数が に含まれることを、 と書いて表します。
2.4 代入と変数の捕獲
論理式 の自由な をすべて項 で置き換えたものを、 と書きます。ここに1つ落とし穴があります。
は「 より大きいものがある」という意味です。 に項 を素朴に代入すると、
となり、「自分自身より大きいものがある」という、まったく別の意味になってしまいます。代入した が、もともとあった に 捕獲 されたためです。
そこで、次の条件を付けます。
代入可能でないときは、先に束縛変数の名前を付け替えて( を にして)から代入します(文献 [12])。こうすれば となり、意味が保たれます。
この条件は、ただの技術的な注意ではありません。4章の公理 Q1 と、5章の健全性定理で、ちょうどこの条件が必要になります。
2.5 「一階」の意味
一階述語論理の量化子が動くのは、領域の要素だけ です。「すべての性質 について」や「すべての部分集合について」とは言えません。
たとえば、算術の帰納法は、二階述語論理なら1つの文で書けます(文献 [16])。
一階述語論理では が書けないので、論理式 ごとに1つずつ書いた無限個の公理(公理図式)で代用します。
この違いは小さく見えますが、大きな帰結をもたらします。一階述語論理は完全性定理が成り立つ代わりに、無限の構造の大きさを区別できません。そのことは レーヴェンハイム=スコーレムの定理の記事 で詳しく扱います。
3. 意味論:構造と充足
ここからは、記号に意味を与えます。
3.1 構造
等号 は論理記号なので、どの構造でも「同じ要素である」と解釈します。
同じ言語にも、さまざまな構造があります。順序の言語 なら、、、 はどれも構造です。 を「より大きい」と解釈した も、 を「割り切る」と解釈した構造も、同じように構造です。記号の意味は、構造を選ぶまで決まりません。
3.2 割り当てと項の値
自由変数を持つ論理式の真偽を決めるには、変数に要素を割り当てる必要があります。関数 を 割り当て といいます。割り当て のもとで、項 の値 を再帰的に定めます。
- 変数:
- 定数:
- 関数:
また、 の の値だけを に変えた割り当てを と書きます。
3.3 充足関係(タルスキの定義)
いよいよ、「構造 で、割り当て のもとで が成り立つ」こと、 を定義します。これも論理式の組み立て方に沿った再帰的な定義です。
左辺は記号の世界の話、右辺は集合(領域の要素)の世界の話です。この定義は、記号の を、領域についての本当の「すべて」に翻訳する 規則だといえます。
この方法は、タルスキが1933年の論文で与えたものです。タルスキは、真理を直接定義するのではなく、自由変数を持つ論理式にも使える「割り当てが論理式を充足する」という関係を再帰的に定義し、文が真であることを、すべての割り当てが充足することとして定めました(文献 [4]、[10])。量化子の節で、自由変数を持つ論理式 の値が必要になるので、文の真理だけでは再帰が回らないからです。今日使われている「構造の中での真理」の形は、タルスキとヴォートの1956年の論文に基づいています(文献 [5]、[10])。
3.4 文の真偽、モデル、意味論的帰結
文 には自由変数がないので、 は割り当て によりません(論理式の組み立て方に沿った帰納法で示せます)。そこで単に と書き、「 は で 真 である」といいます。
ここから、意味論の基本概念が定義されます。
たとえば、 を群の公理とすると、 のモデルとは、ちょうど群のことです。そして
が成り立ちます(どの群でも、右単位元は左単位元でもある)。一方、可換性について
です。これを示すには、可換でない群を1つ挙げれば十分です(たとえば3次の対称群 )。
さらに、構造 で真になる文をすべて集めたものを、 の 理論 といいます。2つの構造で同じ文が真になるとき()、それらは 初等同値 であるといいます。同型な構造は初等同値ですが、逆は一般に成り立ちません。この「文では区別できない別の構造」がどれだけあるかを教えるのが、レーヴェンハイム=スコーレムの定理です。
4. 統語論:形式的な証明
今度は意味を忘れて、記号の書き換えだけで「証明」を定義します。証明の体系には、ヒルベルト流、自然演繹、シーケント計算、タブロー、導出原理(レゾリューション)など、いくつもの流儀があります(文献 [12])。ここでは、完全性定理の記事 と同じ ヒルベルト流 を使います。
4.1 公理と推論規則
論理記号は 、、、 だけを基本にし、ほかは略記とみなします(たとえば は の略)。
ヒルベルト流の体系
公理( には任意の論理式を入れる)
- A1:
- A2:
- A3:
- Q1:( は の に代入可能)
- Q2:( は に自由に現れない)
- E1:
- E2:( は原子論理式で、 は の のいくつかを に置き換えたもの)
推論規則
- MP(モーダスポネンス): と から
- Gen(汎化): から
ここで を文の集合に限っているのは、Gen を安全に使うためです。前提 に が自由に現れないので、「 について何も仮定していないから、すべての について言える」という汎化が正当になります。
4.2 導出の例
と から、 を導出します。
| 番号 | 論理式 | 理由 |
|---|---|---|
| 1 | 前提 | |
| 2 | Q1() | |
| 3 | 1、2 に MP | |
| 4 | 前提 | |
| 5 | Q1() | |
| 6 | 4、5 に MP | |
| 7 | 6、3 に MP | |
| 8 | 7 に Gen |
各行は、 や が何を意味するかを一切考えずに、規則が当てはまるかどうかだけで確かめられます。導出が正しいかどうかは機械的に判定できる ことが、統語論の大きな特徴です。
4.3 無矛盾性と、導出の有限性
ある について と がどちらも成り立つとき、 は 矛盾している といい、そうでないとき 無矛盾 であるといいます。無矛盾性は、意味論の「充足可能」に対応する、統語論の概念です。
もう1つ、統語論ならではの性質があります。導出は有限の列なので、前提 のうち有限個しか使いません。
当たり前に見えますが、意味論の にはこの性質が見た目からは分かりません。この性質が、完全性定理を通じて、意味論の コンパクト性定理 を生みます(5.3)。
5. 2つの面をつなぐ
ここまでで、2つの「帰結」がそろいました。
一方は記号の有限の操作、もう一方は(無限かもしれない)すべての構造についての主張です。この2つの関係を述べるのが、健全性定理と完全性定理です。
5.1 健全性定理:証明できるものは正しい
Q1 の確認で、2.4 の「代入可能」の条件が効いています。条件がなければ、Q1 から が出てきます。これは で前件が真、後件が偽なので、健全性が崩れます。
健全性定理の対偶から、3.4 の tip の主張が出ます。(反例のモデルがある)なら、(証明できない) です。群の公理から可換性が証明できないのは、 があるからです。また、モデルを持つ は無矛盾です。矛盾 と がどちらもモデルで真になることはないからです。
5.2 完全性定理:正しいものは証明できる
健全性定理の逆が成り立つかどうか、つまり一階述語論理の証明の体系が「正しいことをすべて証明できるだけの力を持つか」という問いは、ヒルベルトとアッカーマンが1928年の教科書『理論論理学の基礎』で、初めて正確な形で書き表しました(文献 [2]、[11])。これに答えたのが、ゲーデルの1929年の博士論文の主定理、完全性定理 です(文献 [3]、[11])。
健全性定理と合わせると、 となり、統語論と意味論の2つの「帰結」は完全に一致します。完全性定理は、次の形でも述べられます(文献 [13])。
この形にすると、冒頭の表の「無矛盾」と「充足可能」の行が一致する、という主張になります。健全性定理が「充足可能なら無矛盾」を、完全性定理が「無矛盾なら充足可能」を受け持っています。
証明の方針は、記号そのものを材料にしてモデルを作る ことです。無矛盾な から出発して、閉項(変数を含まない項)を領域の要素とし、「 を拡大した集合に入っている原子文は真」と決めて構造を作ります。統語論の対象(項)が、そのまま意味論の対象(領域の要素)になるわけです。ゲーデルの元の証明と、今日標準のヘンキンの証明(文献 [8])は、完全性定理の2つの証明 で詳しく解説しています。
5.3 完全性定理から分かること
完全性定理を通すと、統語論の性質が意味論の定理に、意味論の性質が統語論の定理に変わります。
コンパクト性定理(統語論 → 意味論) 4.3 の「導出は有限個の前提しか使わない」を、完全性定理で意味論に移すと、次の定理になります(文献 [13])。
レーヴェンハイム=スコーレムの定理(構成の副産物) 完全性定理の証明で作るモデルは、記号(閉項)からできているので、言語が可算なら可算になります。ここから、「モデルを持つ可算の言語の理論は、可算のモデルを持つ」ことが分かります。詳しくは レーヴェンハイム=スコーレムの定理の記事 をどうぞ。
証明の探索(意味論 → 統語論) 「妥当な文」は「証明できる文」と同じものです。証明は有限の記号列で、正しいかどうかは機械的に判定できるので、すべての記号列を順に調べていけば、妥当な文はいつか必ず証明が見つかります。つまり、妥当性は「半決定可能」です(文献 [12])。
ただし、妥当で ない 文については、探索がいつまでも終わらないことがあります。実際、任意の文が妥当かどうかを判定する一般の手順は存在しないことが、1936年にチャーチとチューリングによって示されました(決定問題の否定的解決。文献 [6]、[7]、[14])。
5.4 注意:「完全性」と「不完全性」
ゲーデルには 不完全性定理(1931年)もあるので、名前が紛らわしいところです。2つの「完全」は、別のものを指しています(文献 [13])。
| 完全性定理(1929年) | 不完全性定理(1931年) | |
|---|---|---|
| 何が完全か | 証明の体系:妥当な文がすべて証明できる | 理論:どの文 についても、 か のどちらかが証明できる |
| 主張 | 一階述語論理の体系は完全である | 自然数の算術を含む(一定の条件を満たす)理論は完全でない |
2つは矛盾しません。算術の理論で も も証明できないとき、完全性定理により、 が真になるモデルと偽になるモデルの両方があります。つまり、本来の自然数とは別の「標準的でない」モデルで、 の真偽が変わっているのです(文献 [13])。
まとめ
- 一階述語論理は、統語論(記号列としての項・論理式と、機械的に確かめられる導出 )と、意味論(構造の上での真偽と、意味論的帰結 )の2つの面から組み立てられる。
- どちらも、論理式の組み立て方に沿った 帰納的な定義 の上に乗っている。充足関係は、記号の ・ を、領域についての本当の「すべて」「ある」に翻訳する。
- 代入可能 の条件は、意味を保つための統語論の条件で、健全性定理の証明で効いてくる。
- 健全性定理()は、反例のモデルで「証明できない」ことを示す道具になる。完全性定理()は、記号からモデルを作ることで示され、コンパクト性定理、レーヴェンハイム=スコーレムの定理、妥当性の半決定可能性を生む。
- 次に読むなら:
参考文献
本文中の「文献 n」は、以下の番号に対応します。内容と書誌情報は、各ページの記載で確認しました(2026年11月16日)。
一次文献(原論文)
- G. Frege, Begriffsschrift, eine der arithmetischen nachgebildete Formelsprache des reinen Denkens, Halle, 1879.(英訳は J. van Heijenoort 編 From Frege to Gödel, Harvard University Press, 1967 に収録)
- D. Hilbert, W. Ackermann, Grundzüge der theoretischen Logik, Springer, Berlin, 1928.(英訳 Principles of Mathematical Logic, Chelsea, 1950)
- K. Gödel, "Die Vollständigkeit der Axiome des logischen Funktionenkalküls", Monatshefte für Mathematik und Physik, 37 (1930), pp. 349–360.(1929年の博士論文 "Über die Vollständigkeit des Logikkalküls" を書き直したもの)
- A. Tarski, 『演繹科学の言語における真理の概念』(ポーランド語), Prace Towarzystwa Naukowego Warszawskiego, Wydział III Nauk Matematyczno-Fizycznych, 34, Warszawa, 1933.(増補した英訳 "The concept of truth in formalized languages" は、A. Tarski, Logic, Semantics, Metamathematics: Papers from 1923 to 1938, Oxford University Press, 1956(第2版 Hackett, 1983), pp. 152–278 に収録)
- A. Tarski, R. Vaught, "Arithmetical extensions of relational systems", Compositio Mathematica, 13 (1956), pp. 81–102.
- A. Church, "A note on the Entscheidungsproblem", The Journal of Symbolic Logic, 1 (1936), pp. 40–41.
- A. M. Turing, "On Computable Numbers, with an Application to the Entscheidungsproblem", Proceedings of the London Mathematical Society, Series 2, 42 (1936–37), pp. 230–265.
- L. Henkin, "The Completeness of the First-Order Functional Calculus", The Journal of Symbolic Logic, 14(3) (1949), pp. 159–166. doi:10.2307/2267044 Cambridge Core
二次文献・解説
- "Classical Logic", Stanford Encyclopedia of Philosophy.(言語・論理式の帰納的な定義と一意的な読み方の定理、自然演繹の体系、意味論、健全性・完全性・コンパクト性・レーヴェンハイム=スコーレムの定理)SEP
- W. Hodges, "Tarski's Truth Definitions", Stanford Encyclopedia of Philosophy(2001年初出、2022年改訂).(タルスキの1933年の充足の定義と、今日の「構造の中での真理」の形がタルスキとヴォートの1956年の論文に基づくこと)SEP
- "Kurt Gödel", Stanford Encyclopedia of Philosophy.(完全性の問いがヒルベルトとアッカーマンの1928年の教科書で初めて正確に述べられたこと、博士論文の主定理が完全性定理であること)SEP
- "First-order logic", Wikipedia(英語版).(論理記号と非論理記号、代入と変数の捕獲、証明の体系の種類、妥当性の半決定可能性、歴史の概略)Wikipedia
- "Gödel's completeness theorem", Wikipedia(英語版).(定理のさまざまな形、コンパクト性定理との関係、不完全性定理との「完全」の意味の違い)Wikipedia
- "Entscheidungsproblem", Wikipedia(英語版).(決定問題と、チャーチとチューリングによる否定的解決)Wikipedia
- "Begriffsschrift", Wikipedia(英語版).(量化された変数が初めて現れたこと)Wikipedia
- "Second-order logic", Wikipedia(英語版).(二階の帰納法の公理)Wikipedia
1〜4章の定義、4.1 の公理系、5.1 の健全性定理の証明は、一階述語論理の標準的な教科書で扱われる事項です。公理系は流儀によって細部が異なります。