A Friendly Introduction to Mathematical Logic（やさしい数理論理学入門）

引用

Leary, C. C., & Kristiansen, L. (2015). A Friendly Introduction to Mathematical Logic (2nd ed.). Milne Library, SUNY Geneseo. オープン教科書（CC BY-NC-SA）。

章の要約

本書は8つの章、短い付録、一部の演習の解答（約75ページ）、参考文献からなり、全体で約365ページである。初期の章ではほとんどの節が演習で終わり、各章は議論の行き先を説明する「Summing Up, Looking Ahead」の節で閉じられる。第2版は、2000年に出たLearyの第1版に、計算可能性についての新しい章と解答を加えて拡充したものである。

第1章：構造と言語

一階論理の語彙を整える。一階の言語を記号の集まりとして定義し、続いて項と論理式を帰納的に定義し、帰納法を項や論理式についての命題が証明できるように一般化する。数論の言語（0、後者関数、加法、乗法、べき乗、順序をもつ）が、全編を通じて使われる例になる。そのあと構造、変数の割り当て、構造における真理を定義し、代入と、量化子の下で変数が捕捉されてしまう問題を扱い、論理的含意と妥当性で終わる。

第2章：演繹

証明とは何かを問うことから始め、形式的な演繹を定義する。論理公理（等号の公理と量化子の公理）と推論規則（命題的帰結と量化子の規則）を示し、健全性定理と、この体系のいくつかの性質、すなわち等号が同値関係であることと演繹定理の一形を証明する。最後に非論理公理を扱い、ベクトル空間と、算術のための弱い公理系Nを例に用いる。

第3章：完全性とコンパクト性

完全性定理をヘンキンの方法で証明する。無矛盾な文の集合を極大無矛盾な集合に拡張し、項からモデルを構成する。そこからコンパクト性が導かれ、算術の非標準モデルを構成することと、一階の文の集合では自然数を一意に定められないことを示すのに使われる。章は、部分構造、初等部分構造、下向きおよび上向きのレーヴェンハイム–スコーレムの定理で終わる。

第4章：2つの視点から見た不完全性

完全性の章に不完全性の章が続く理由を説明し、完全な公理系を定義して、証明できない真の文を見つけるという目標を設定する。有界および非有界の量化子による論理式の複雑さを導入し、演繹を数としてコード化することに基づく道筋を示し、計算可能な関数を通るもう1つの道を予告し、数の有限列を1つの数としてコード化する方法を示す。章は公理系Nとその強さを思い出して終わる。この後、読者は第5・6章に進むことも、第7章に飛ぶこともできる。

第5章：構文的不完全性：下準備

論理式に基づく道筋の技術的な中核である。表現可能な集合と関数を導入し、それらを計算機プログラムや同値な計算モデル（再帰関数、チューリング機械、ラムダ計算）と非形式的に関連づけ、ゲーデル数の仕組みを築く。項、論理式、公理、演繹のコード化がNで表現できることを段階的に示し、ある数がある論理式の演繹のコードであるとき、かつそのときに限って成り立つ論理式で締めくくる。

第6章：不完全性定理

自己言及補題を証明し、それを使って自身の証明不可能性を主張する文を構成する。Peter Smith の書評によれば、続いて第一不完全性定理を意味論的な形と構文論的な形で与え、算術の決定不可能性、タルスキの定理、ロッサーの改良、ベリーのパラドクスに基づくブーロスの不完全性の証明を扱い、第二不完全性定理を導出可能性条件を仮定して証明する。

第7章：計算可能性理論

第2版で新たに加わった章で、約70ページある。短い歴史の節から μ-再帰関数、s-m-n定理、クリーネの標準形定理へ進み、集合 K の計算不可能性が示される。これは、決定問題（Entscheidungsproblem）の決定不可能性、不完全性の2つ目の証明、ヒルベルトの第10問題に使われる（Smith の書評）。

第8章と巻末

第8章「Summing Up, Looking Ahead」は、これまでの筋をまとめ、さらに読むべき文献を示す。付録「Just Enough Set Theory to Be Dangerous」のあとに、一部の演習の解答と参考文献が続く。

主要概念

第1–2章：言語、構造、演繹

• 一階の言語と構造：一方は記号と論理式という構文、他方はそれを解釈する数学的なモデル。
• 論理的含意と妥当性：ある論理式が他の論理式から従うとは、それらを満たすすべての構造と割り当てで真であること。
• 演繹：各項が公理であるか、規則によって前の項から得られる論理式の有限列で、証明を形式化したもの。
• 健全性：演繹できるものは、すべてのモデルで真である。

第3章：完全性とコンパクト性

• 完全性定理：公理の集合から論理的に従うものは、そこから演繹できる。
• コンパクト性定理：文の集合がモデルをもつのは、そのすべての有限部分集合がモデルをもつときに限る。
• 非標準モデル：自然数と初等同値だが同型ではない構造。
• レーヴェンハイム–スコーレムの定理：他の濃度をもつ初等部分構造や初等拡大が存在すること。

第4–6章：不完全性

• 完全な公理系：その言語のすべての文を証明するか反証する公理系。
• 表現可能な集合・関数：理論の論理式によって、理論がその正しさを証明できるように定義される集合や関数。
• ゲーデル数：記号、論理式、演繹に自然数を割り当て、証明についての主張を数についての主張にすること。
• 自己言及補題：任意の論理式に対して、その論理式が自分自身について成り立つと主張する文が存在する。
• 第一・第二不完全性定理：算術の決定可能で無矛盾かつ完全な公理化は存在せず、十分強い公理系は自身の無矛盾性を証明できない。

第7–8章：計算可能性

• 計算可能（μ-再帰）関数：基本関数から合成、原始再帰、最小化によって作られる関数。
• 標準形定理：すべての計算可能関数は、固定された1つの計算可能な述語と1回の非有界な探索を使って書ける。
• 決定問題（Entscheidungsproblem）：一階論理の妥当性を判定する問題で、否定的に解決された。

批判的分析

長所

• 親しみやすく、ペースのよい叙述。 Peter Smith は Logic Matters の書評で、くつろいだ誘うような語り口を好み、叙述の水準は入門の授業によく合っていると判断し、明快さは模範的だと述べている。著者たちが記法の落とし穴を指摘したり動機を述べたりするのに使う「Chaff」の注釈（たとえば数字の 0 と数 0 を区別する）は、各章の際立った特徴である。
• 同じ目標への2つの道。 著者たちは、不完全性定理への道を第4章のあとで分けている。第5・6章を通る論理式に基づく道と、第7章を通る計算に基づく道である。授業ではどちらかを選ぶことができ、読者は両方の方法を見ることができる。
• 演習と解答。 最初の6章では、ほとんどの節が演習で終わり、第2版では約75ページの解答が加わった。Open Textbook Initiative は多くの演習の解答があると記しており、Smith はそれによって独習にいっそう向くと述べている。
• 表現可能性の丁寧な実演。 Smith は、定義する論理式を直接書き下す第5章の扱いを、利用できる完全な実演のなかで最も使いやすいものの1つと呼び、第2版が対角化補題の証明の印象を和らげていると述べている。
• 無料でコンパクト。 本文はクリエイティブ・コモンズのライセンスで公開されており、著者たちは1学期のうちに不完全性定理に到達することを目指している。

短所

• ヒルベルト流の体系。 演繹の体系は規則の少ない公理的なものである。Smith は、一階論理の形式体系を見たことのない読者には最初は密に感じられるかもしれず、木構造や自然演繹に慣れた学生にはこの選択の説明がほしいかもしれないと注意している。
• 第5章は骨が折れる。 著者たち自身がこの章を、定義が延々と続く密で技術的なものだと述べている。時間を見込んでおくこと。
• 範囲が狭い。 本書が扱うのは、レーヴェンハイム–スコーレムの定理までの一階論理、不完全性定理、そして一部の計算可能性である。モデル理論のさらなる展開と公理的集合論は範囲外で、集合論は短い付録に現れるだけである。
• 命題論理は既知とされる。 命題論理は推論規則の章で簡単に復習されるだけなので、それを知らない読者はまず別の資料が必要になる。
• 第二不完全性定理は仮定した条件に依拠する。 Smith によれば、導出可能性条件は証明されずに仮定されている。

コースにおける位置づけ

このサイトの論理・集合論の本のなかで、Leary と Kristiansen はゲーデルの定理を目指す、数理論理学の最初の授業向けの1冊である。これは証明の書き方を扱う本の次に来る。Hammack の無料の Book of Proof と Velleman の How to Prove It は、論理、集合、証明の方法を非形式的に教えるもので、本書が形式化する背景になる。Liebeck、Eccles、Allenby による証明、集合、数の体系についてのより広い本は、そのもっと早い段階での選択肢である。

最も近い比較対象は Enderton の A Mathematical Introduction to Logic で、命題論理と一階論理、形式的な理論、モデル理論を計算可能性との関連とともに厳密に扱う。Leary と Kristiansen は、不完全性定理へまっすぐ向かい、モデル理論に割く分量が少ない、より目的の絞られた無料の選択肢である。どちらを読んでも、モデル理論、集合論、計算可能性の専門書への準備になる。

本書の使い方

本書は上級の学部生向けに書かれており、序文は不完全性への2つの道を示している。Smith によれば、抽象的な議論に抵抗のない哲学の学生にも読める。当サイトは前提条件として、証明を伴う数学の経験を挙げている。

提案する計画は次のとおりである。

• 中核： 第1–4章。第1–3章は、完全性とコンパクト性に至る一階論理の自己完結した入門である。第1・2章の定義は、後の証明がその正確な形に依存するので、ゆっくり読むこと。Smith は、構造と演繹をすでに知っている読者なら第3章は単独で読めると述べている。
• 不完全性への道を選ぶ： 第4章のあと、第5・6章（論理式とゲーデル数）か第7章（計算可能性）のどちらか。2回目の通読でもう一方を読むとよい。
• 任意： 第8章と付録は短く、主として読者に方向を示すものである。
• 演習： 明示的な演繹や構造を求める問題に取り組み、解答で確かめる。