A Mathematical Introduction to Logic（数理論理学入門）

引用

Enderton, H. B. (2001). A Mathematical Introduction to Logic (2nd ed.). Harcourt/Academic Press.

章の要約

第2版は約300ページのコンパクトな教科書である。序文と序論の後に、0から番号を振った5つの章があり、その後に参考文献の案内、記号一覧、索引が続く。出版社は、論理を学んだことはないが数学的推論の経験はある読者を対象とし、第1版よりも講義での使い方に柔軟性があると説明している。計算複雑性やデータベース問合せといった計算機科学の話題の材料と、集合についての入門的な補足も加えられている。各章の長さは大きく異なり、内容の重みを知る手がかりになる。

第0章：Useful Facts about Sets（集合に関する有用な事実）

論理の各章が拠って立つ集合論の背景をまとめた10ページの短い章。なじみのない概念に出会ったときに参照するもので、集合論の講義ではない。

第1章：Sentential Logic（文の論理）

56ページ。最初に学ぶ論理体系として命題論理を扱う。内容には、真理値割り当て、文の構文解析アルゴリズム、コンパクト性と実効性が含まれる。

第2章：First-Order Logic（一階論理）

115ページで最も長い章。一階の言語、真理とモデルを扱う。本文の3分の1を超え、本書の中心である。

第3章：Undecidability（決定不能性）

決定不能性を主題とする100ページ。後半の節には第二不完全性定理と冪乗の表現が含まれ、この章は不完全性の結果にまで至る。

第4章：Second-Order Logic（二階論理）

25ページの短い最終章。二階の言語、Skolem関数、多ソート論理、一般構造を含む。

主要概念

第0〜1章：集合と文の論理

• 真理値割り当て：文記号に真理値を割り当てる方法で、論理式がいつ真になるかの定義に用いる。
• 構文解析アルゴリズム：記号列が適格な文かどうかを判定し、その構造を復元する手続き。
• コンパクト性：文の集合が充足可能であることを、その有限部分集合の充足可能性と結びつける性質。

第2章：一階論理

• 一階の言語：量化子を持つ形式言語で、数学的構造についての主張を書き表すために使う。
• 真理とモデル：文が構造の中で成り立つのはいつかの定義と、理論のモデルという概念。

第3〜4章：決定不能性と二階論理

• 第二不完全性定理：理論が自身の無矛盾性を証明できることへの制約で、第3章で扱われる。
• Skolem関数と多ソート論理：二階の言語を扱う最終章に現れる道具。

批判的分析

長所

• 論理の初学者向け。 出版社は、論理を学んだことはないが数学的推論の経験がある読者向けだと述べており、第2版は今日の数学・哲学専攻の学部生にとってより取り組みやすいものとされている。
• 柔軟な使い方。 紹介文は、改訂版が柔軟性を高め、講義での使い方を選べる点を強調している。
• 計算機科学とのつながり。 出版社は計算複雑性とデータベース問合せの材料を強調しており、数学や哲学の学生だけでなく理論計算機科学の学生にも関連が深い。
• コンパクトで釣り合いが取れている。 317ページ、5章で通読できる短さであり、ページ数から各章の重みが見える。一階論理と決定不能性で、およそ3分の2のページを占める。

短所

• 扱う主題は5つだけ。 内容は集合、文の論理、一階論理、決定不能性、二階論理である。モデル理論、集合論、計算可能性をそれ自体の分野として学びたい読者は別の本が必要で、本書の参考文献の案内が出発点になる。
• 証明技法への手引きは少ない。 数学的推論の経験を前提としているので、まだ証明を書いたことのない学生は、先に証明の書き方を扱った本を読むべきである。

コースにおける位置づけ

Enderton は、このリストの中での形式論理の教科書で、すでに証明を書ける学生向けである。Hammack の Book of Proof と Velleman の How to Prove It は、本書が前提とする証明の技法と基本的な論理を教える。Leary と Kristiansen の A Friendly Introduction to Mathematical Logic は、学部上級向けの数理論理の最初の講義のためのオープン教科書で、Enderton の進みが速すぎるときのより穏やかな代替または併読書になる。

リスト中のほかの純粋数学、数学的推論、数と証明の本は、論理より広い範囲を扱う。言語、構造、証明の形式的な研究を、不完全性と決定不能性を頂点として学ぶことが目標なら、Enderton を選ぶとよい。

本書の使い方

出版社は、読者を計算機科学、哲学、数学の学部生と大学院生としている。読者は数学的な証明に慣れている必要がある。集合の基本的な知識があると役立ち、第0章が不足を補う。

• 中核： 第1・2章が最初の課程をなし、合わせて約170ページ。
• 次に： 第3章は不完全性と決定不能性を扱い、計算可能性と結びつく。本書の最も有名な結果はここにある。
• 選択： 二階論理の第4章。第0章は必要なときだけ。

読書の時間は章番号ではなくページ数で計画すること。第2章だけで第0・1・4章の合計より長い。構文と意味論についての議論は、受け身で読むのではなく、自分で書き出して練習すること。モデル理論、集合論、計算可能性については、巻末の参考文献の案内を利用するとよい。