ロジックおすすめ本の紹介

お知らせ

現在, おすすめ本の紹介を募集しています. ご協力くださる方は, 連絡先へお願い致します.

概要

はじめに

このページは, おそらく独学の人が多いであろう, ロジック(数学基礎論, 数理論理学. 当ページではロジックに統一します)初心者の方のために, 研究者または大学院生によるおすすめ本の紹介を集めています.

  • ロジックを学びたいが, どんな本を読んだら良いかわからない.
  • 興味は定まったが, どんな本があるのかよく知らない.
  • 1冊読み終わったが, どんな本を読めば次のステップとして良いのかわからない.
という人を主な対象としていますが, それ以外の人にもきっと役に立つと思います.

分類

ロジックには, 証明論, モデル理論, 計算理論, 集合論の4大分野があります. 当ページはそれに従い, 分野毎の紹介としてまとめています. また, どれにも当てはまらない(すべてに当てはまる)本はその他に分類しました.

内容が少ないうちはこのページ一箇所にまとめておきますが, 数が増え次第, ページを分割する予定です. 分野が一目でわかりやすいように, 次のような色分けがしてあります: 証明論, モデル理論, 計算理論, 集合論, その他.

内容

紹介の内容について.

[本のタイトル]
タイトル / 本の著者 / 出版社 の順で表します.
[分野]
上で示した分類以上に細かな分類などが当てはまります.
[おすすめ対象者]
「全体像が知りたい人」や, 「細かいことが知りたい人」など, おすすめしたい対象の人を表します.
[紹介文]
おすすめポイントを詳しく説明します.

コンテンツ

[本のタイトル]
Quantum Computation and Quantum Information / Michael A. Nielsen, Isaac L. Chuang / Cambridge University Press
[分野]
量子計算理論・量子情報理論
[おすすめ対象者]
量子計算理論・量子情報理論を学び始める人
[紹介文]

量子計算理論・量子情報理論を学ぶための基礎知識とこの 分野における基本的な成果が平易にまとめられている本です. この分野の標準的な教科書とみなされています. 分厚い本で 内容が膨大なので, 自分の興味のある部分を中心に, 必要に 応じて基礎知識の与えられている部分に戻りながら読むと 良いと思います.もし洋書に抵抗がある場合は, 下記のように 3分冊の翻訳が出版されているので, そちらを読むと良いでしょう.

  • 量子コンピュータと量子通信I -量子力学とコンピュータ科学-
  • 量子コンピュータと量子通信II -量子コンピュータとアルゴリズム-
  • 量子コンピュータと量子通信III -量子通信・情報処理と誤り訂正-

Michael A. Nielsen, Isaac L. Chuang 共著, 木村達也 訳 / オーム社

[次に読むおすすめ本]

この本の参考文献をたどると良いと思います. また, 興味のある 論文を arXiv で探して読んでみることをおすすめします.

[本のタイトル]
現代数理論理学序説 / 古森雄一, 小野寛晰 / 日本評論社
[分野]
証明論・非古典論理
[おすすめ対象者]
非古典論理の流れを知りたい人・Curry-Howard対応を知り, 論理への応用を知りたい人
[紹介文]

1,2章は古典論理と直観主義論理の証明システムについての話題であるが, Curry-Howard対応やグリベンコの定理を用いて自然演繹の正規化やsequent計算のcut除去を証明するなど, 他の本には見ない現代的な手法を用いている. 3章はラムダ計算の話が非常にコンパクトにまとめられているが, 書いてある内容はとても深い. 4章は非古典論理の話題が豊富に書かれている. トピックスは, 直観主義論理・様相論理・部分構造論理・中間論理・普遍代数など, 非古典論理についてこれ程幅広い話題を取り扱っている和書は他に見たことがない. 証明は少なく, 自力で埋めなければならない部分も多いが, この本をガイドブックに勉強をすれば, とても広い知識が身に着くと思われる.

[次に読むおすすめ本]

参考文献を見てください.

[本のタイトル]
Lambda-calculus and Combinators, an Introduction / J. R. Hindley, J. P. Seldin / Cambridge University Press
[分野]
ラムダ計算・combinatory logic
[おすすめ対象者]
ラムダ計算を初めて勉強する人
[紹介文]

ラムダ計算と combinatory logic の話題を直観的にわかりやすく丁寧に説明してくれる. とにかく初学者にお勧めしたい一冊である. 内容もとても豊富で, 計算論の道具としての理論・ラムダ計算と combinatory logic の対応関係・ラムダ計算のモデル・ 型付きの理論など基本的な話題は全て収まっていると思う.

[次に読むおすすめ本]

参考文献を見てください.

[本のタイトル]
Higher Recursion Theory / Gerard E. Sacks / Perspectives in Logic
[分野]
計算可能性理論
[おすすめ対象者]
既に算術的階層くらいまで計算論を学んでおり, もう少し深い計算論を知りたいという人
[紹介文]

本書は, 既に計算論に関して, 算術的階層くらいまでの入門的内容を既に学習しており「これから超算術的階層を学ぼう」あるいは 「超算術的階層の先に何があるのかを知りたい」という段階にある人向けの教科書です. すぐに目に付く量化子の記法の古臭さに臆してしまうかもしれませんが, 独特な記法に慣れてさえしまえば, 丁寧で読みやすい本だと気付かされると思います. 章構成も非常に明快で, 算術的階層程度の知識があれば, すぐに魅力的な話題に取り掛かれる名著です.

Part Aは, 超算術的階層に関する標準的な教科書としての利用価値も高く, とりあえずPart Aだけ読んでみる, というのも一つの手だと思います. Part B以降の話題も幅広く, 『メタ再帰理論』『α-再帰理論』『E-再帰理論』『高階計算論』など, 計算論における重要概念を網羅的に取り扱っていますので, 是非目を通してみて頂きたい一品です.

Part B以降の詳細としては, まず, 超算術的階層の理論をゲーデルの構成可能宇宙 L 上の計算論の観点から再検討する, という視野の転回に始まり, 計算論の世界が次々に広がっていく怒涛の展開に興奮させられます. 目から鱗が落ちるような話題が多いのですが, Part Cの話題などはかなり技巧的で, あらかじめ計算論の入門書などで, チューリング次数構造の理論を学んでおかないと, 読むのに少し苦労すると思います. 特にChapter VIII, IXのα-再帰理論における次数構造の理論や Chapter XIの強制法のE-再帰理論への応用などは技術的な話題に終始し, 応用的な話題への広がりもあまり大きくないため, 苦行だと感じれば, 軽く眺める程度で良いと思います. Chapter XIIは, 超限型の計算論に関する重要で魅力的な話題が載っているのですが, 登場が最後の最後なので, 辿り着くまでのハードルが高いのが欠点です.

とにかく本書は, 話題が豊富で魅力的な教科書なので, 腕に自信がある方は挑戦してみてもいいと思います. また, 先を見据えて, 今後, ゲーデルのLの微細構造の理論あるいは算術の超準モデル上の次数の理論(逆再帰理論) などを学ぼうと考えているという場合にも, この教科書には一通り目を通しておいてもいいかもしれません. とにかく, 前世紀におけるSacks系列の計算論的研究の集大成, という風味を醸し出しており, 噛めば噛むほど味が出る名著です.

[次に読むおすすめ本]
  • Computable Structures and the Hyperarithmetical Hierarchy / C. J. Ash, and J. F. Knight / Studies in Logic and the Foundations of Mathematics
  • Admissible Sets and Structures / John Barwise / Perspectives in Logic
  • Constructibility / Keith J. Devlin / Perspectives in Logic
  • Fine Structure and Class Forcing / Sy D. Friedman / De Gruyter Series in Logic and Its Applications
  • Elementary Induction on Abstract Structures / Yiannis N. Moschovakis / Dover Books on Mathematics
[本のタイトル]
Recursion Theoretic Hierarchies / Peter Hinman / Perspectives in Logic
[分野]
計算可能性理論
[おすすめ対象者]
初学者でも読めるが, 計算論をある程度知ってから読むと, また別の味わいがある
[紹介文]

本書は, 計算論の入門書で, 計算可能性の定義といった導入的話題から丁寧に書かれています. 初学者でも独習可能なように, 極めて多くのページ数を割いて初歩的話題から綿密に描写されていますが, 具体例などが殆ど無く, 抽象的な議論が延々進んでいく形式ですので, 初学者の場合, 少し退屈だと感じるかもしれません. また, 記法が極めて独特な上, かなり形式的に記述されているため, 読みづらいと感じる人は多いと思います.

ただし, 他の計算論の入門書と一線を画している点は, 話題の選択が秀逸かつ極めて広範であり, その領域は, 算術的階層, 算術的強制法, 超算術的階層, 帰納作用素, 解析的階層, 記述集合論, 有限型の計算論, 順序数上の計算論と, 古典計算論の多様な分野を網羅するものとなっていることです. 計算可能性の入門的話題から始まって, これほどの発展的話題を網羅する教科書は他にはまず無いと思います.

Part AとPart Bは, 計算可能性の入門的話題から, 超算術的階層, 解析的階層, 記述集合論といった, 他の入門書でも補える内容となっていますが, Part Bの後半部分で描かれるΔ^1_2の下からの到達不能性の話題などの選択は割と個性的で, 一見の価値はあると思います. Part Cの内容は, 超算術的階層の理論の一般化としての正規有限型の汎函数の計算論が展開されており, 特にスーパージャンプによるジャンプ作用素の階層などを学ぶ際には非常に良い教科書となると思います. また, これらの階層的計算論は最終章で順序数上の計算論の観点から統一的に再構築され, 各種の計算可能性概念と再帰的到達不可能順序数や再帰的マーロ順序数などといった巨大順序数との関連が示されるなど, 心踊らされる内容が詳細に記載されています.

一見, 形式的すぎて読みづらいと感じるかもしれませんが, 前世紀の計算論の研究の深みを知るために, どんな話題が載っているかだけでも眺めて楽しんで欲しいと思います. この本の記法が気に入らなければ, 目次だけでも目を通して, 各トピックについて別の文献を探して学ぶ, という利用法でも良いと思います.

[次に読むおすすめ本]
  • Computation in Higher Types / Johan Moldestad / Lecture Notes in Mathematics 574
  • Elementary Induction on Abstract Structures / Yiannis N. Moschovakis / Dover Books on Mathematics
  • Descriptive Set Theory / Yiannis N. Moschovakis / Mathematical Surveys and Monographs
  • Higher Recursion Theory / Gerard E. Sacks / Perspectives in Logic
[本のタイトル]
Admissible Sets and Structures / John Barwise / Perspectives in Logic
[分野]
計算可能性理論・無限論理のモデル理論・弱い集合論
[おすすめ対象者]
超算術的階層に親しんでおり, Kripke-Platek集合論に興味を持っている人
[紹介文]

本書は, 計算可能性理論, モデル理論, 集合論が交錯する, Kripke-Platek集合論(KP)と呼ばれる理論(のモデル理論的側面)に関する基本的教科書です. 基本的には, 超算術的階層, 帰納集合の理論が如何に美しく抽象化されるかを描く教科書ですので, 超算術的階層に関する一通りの話題を知っていた方が楽しめると思います. とはいえ, KP集合論の導入部分から多くのページ数を割いて, 極めて丁寧に解説がなされているため, 予備知識をほとんど持たない読者でも読み進めることは可能です. 本書の導入から引用すれば, 大学院の初年度で, 計算論, モデル理論, 集合論の初歩に一通り触れた程度の学生を読者として想定しているようです.

本書は, 前世紀の中旬を少し超えた頃に, 計算論, モデル理論, 集合論の間の垣根が一時的に取り払われた, そんなある一時代に執筆されたもので, KP集合論の手法が後の時代のロジック全体の中心となり重要な役割を担うことを願って書かれた意欲的な教科書です.

Part Aでは, KP集合論の初歩的な性質や無限論理の導入などが150ページ以上に渡って丁寧に記述されていますが, その長さから, 少し退屈に感じる読者も多いかもしれません. Part B以降は, KP集合論の美麗な理論が目まぐるしく展開されます. たとえば, Part Bでは, KPのモデル上で, 計算論, 超算術的階層の理論が美しく展開され, 再帰的巨大順序数や帰納集合との対応などが示されます. Part Cでは, 計算論の枠を飛び出し, KPのモデル上の無限論理の一般論が展開されます.

現代のロジックでは, この種の無限論理のモデル理論の影響力は, 当時と比較すると若干小さくなっている感じはありますが, 現代の状況がどうあれ, この教科書の魅力は色褪せずに残っていると思います. とにかく, 若かりし日のBarwiseの情熱の片鱗を感じられる名著で, 一見の価値はあると思います.

[次に読むおすすめ本]
  • Higher Infinite: Large Cardinals in Set Theory from Their Beginnings / Akihiro Kanamori / Springer Monographs in Mathematics
  • Model Theory for Infinitary Logic / Jerome H. Keisler / Studies in Logic and the Foundations of Mathematics
  • Computable Structures and the Hyperarithmetical Hierarchy / C. J. Ash, and J. F. Knight / Studies in Logic and the Foundations of Mathematics
  • Elementary Induction on Abstract Structures / Yiannis N. Moschovakis / Dover Books on Mathematics
  • Descriptive Set Theory / Yiannis N. Moschovakis / Mathematical Surveys and Monographs
  • Higher Recursion Theory / Gerard E. Sacks / Perspectives in Logic
[本のタイトル]
General Recursion Theory: An Axiomatic Approach / Jens E.Fenstad / Perspectives in Logic
[分野]
計算可能性理論
[おすすめ対象者]
超算術的階層や抽象計算論にある程度親しんでいる人
[紹介文]

本書は, 超算術的階層の理論あるいは型2計算論の一般化としての抽象計算論の教科書で, また, Spector理論の話題が載っている貴重な計算論の教科書でもあります. Spector pointclassは現在, 記述集合論における重要概念のひとつとなっていますが, 起源を辿れば, 元々計算論家であったMoschovakisによる1960年代の抽象計算論の研究の過程で誕生したものです. 本書は, Spector理論の在りし日の姿が描かれた, 趣き深い名著です.

本書は, 計算可能性の定義といった導入的話題から丁寧に記述され, Spector理論を中心に広範な話題の書かれた非常に優れた入門書です. ただし, 最大の問題点は, 算術的階層や解析的階層といった計算論の極めて重要な話題をすっ飛ばして, 最初から抽象計算論を展開しているため, 超算術的階層や射影集合論などの入門的話題については, 適宜, 他の教科書で補完しておく必要があります. また, 所々でゲーデルのLや基本的な強制法の知識程度は持っていること前提で話が進んでいる部分があるため, その辺りの知識を持たない読者は, 必要に応じて, 他の教科書を参照する必要があります.

Part Aでは具体例の現れないまま, 類似の話題が幾度も繰り返されるので, かなり退屈に感じるかもしれません. Part B以降で, Spector理論とSpector class, 型2計算論から始まり, Part C以降は, 認容集合上の計算, α-再帰理論における次数構造, 高階計算論, E-再帰理論と, 標準的な話題は一通り網羅されています. それぞれの分野から重要な話題をうまく抽出し, 独特な方法で調理しているので, 計算論に慣れ親しんでから再び読み返してみると, 新たな発見があるかもしれません. ただ, 本書はタイトルの通り, やや公理的に理論を展開しようとする傾向があり, 具体例が見え辛く, 表面をなぞっただけではあまり頭に染み込んできません. じっくり噛み締めて味わうと, 徐々に深みが伝わってくる教科書だと思います.

[次に読むおすすめ本]
  • Computation in Higher Types / Johan Moldestad / Lecture Notes in Mathematics 574
  • Descriptive Set Theory / Yiannis N. Moschovakis / Mathematical Surveys and Monographs
  • Recursion on the Countable Functionals / Dag Normann / Lecture Notes in Mathematics 811
  • Higher Recursion Theory / Gerard E. Sacks / Perspectives in Logic
[本のタイトル]
Subsystems of Second Order Arithmetic / S. G. Simpson / Cambridge University Press
[分野]
逆数学
[おすすめ対象者]
逆数学を学びたい人
[紹介文]

逆数学にかんする結果や手法が広くまとめられている, 基本的かつ決定的な本. 辞書的に使える一方で, 通読するのは初学者には大変かもしれない. 逆数学の概要を知るには, Chap.Iを読めばよいでしょう. Chap.II.5-10あたりがむずかしくて挫折しやすいかもしれません. そういうときは逆数学の醍醐味である「逆」が出てくるChap.IIIに飛んで, 好きな分野の好きな定理の逆数学現象を読んでいくと, がぜんやる気が出てくると思います.

[次に読むおすすめ本]

逆数学にかんする書籍は

  • [1] 逆数学と2階算術 / 田中一之
  • [2] ゲーデルと20世紀の論理学3, II 逆数学と2階算術(山崎武) / 田中一之編
があります. SOSOAを半分も読めば, 逆数学にかんする論文も読めると思います.

[本のタイトル]
情報科学における論理 / 小野寛晰 / 日本評論社
[分野]
様相論理・非古典論理
[おすすめ対象者]
様相論理を学びたい人, 今までに古典論理だけを学んできた人
[紹介文]

様相論理について学びたい人は, まずこの本を手に取ると良いです. 命題論理から始まり, 説明が丁寧なので, ロジックを初めて学ぶ人にとっても良い本です. 様相論理・非古典論理周辺の様々なトピックを扱っており, また, 歴史やコラムを時折挟んであり, 読み物としても楽しめます. 一階述語論理だけを勉強してきた人にとっても, 非古典論理の面白さを体感できる良書だと思います.

[次に読むおすすめ本]
参考文献に挙げられている本を見てみると良いのではないでしょうか.
[本のタイトル]
A Shorter Model Theory / Wilfrid Hodges / Cambridge University Press
[分野]
モデル理論
[おすすめ対象者]
モデル理論に興味はあるが, 分厚い本に抵抗感のある人
[紹介文]
  1. 分厚くない.
  2. 説明が親切.
  3. その先を知りたい人のために, 次に読むと良い本を各章ごとに紹介してくれている.
[次に読むおすすめ本]

この本で紹介されている本・論文を読むと良いと思います. また, この本の分厚いバージョンである同著者の Model Theory (Cambridge University Press) を見るのも良いかもしれません.

[本のタイトル]
Mathematical Logic / Joseph R. Shoenfield / CRC Press
[分野]
ロジック全般
[おすすめ対象者]
細かいことが気になる人, ロジック全般の専門知識を付けたい人
[紹介文]

ロジック全般の基礎知識が自己完結かつコンパクトにまとめてある古典的な教科書です. 論理的な飛躍が少なく, ちゃんと手を動かして証明を書き下しながら読んでいけば, 高校生でも読むことが出来ると思います. 数学書で使われる英語は難しくないので, 最初は大変かもしれませんがすぐに慣れます. 記述が現代的でない点もありますが, これだけの量の内容を自己完結かつコンパクトにまとめている本を私は他に知らないので, 現在でも入門書として最適な本の1つであると思います. 読み終えるためには相当な時間が必要だと思うので(私の場合, 友人とセミナーで読み, 半年ぐらいかかった気がします), 簡単にこの本を薦めることはできないのですが, ロジックという研究分野全体を知りたい, という意欲的な方にお薦めします. ただ, 証明論・非古典論理に関してはほぼ扱っていないので, 他の本で別に学んでください.

[次に読むおすすめ本]
興味を持った分野の専門書・入門書へ進んでください.
[本のタイトル]
数学のロジックと集合論 / 田中一之, 鈴木登志雄 / 培風館
[分野]
ロジック全般・集合論
[おすすめ対象者]
集合論, ロジックの初歩をざっと掴みたい人
[紹介文]

ロジックの基本的な事柄が, 学部1年, 2年の学生が予備知識なしに読めるような内容にかみ砕いて書いてある本です. ロジックの「入門書」は独学の学生が読むには手に余るような本ばかりなので, それら「入門書」の入門書として活用できます. ですが, 形式的証明の体系に関してはGentzen-Taitの証明系がもとになっていて, 「形式的証明は難しい!」と思われがちなので, その部分だけは自然演繹などのキーワードで調べ, 別に勉強することをおすすめします.

[次に読むおすすめ本]

広い視点でロジックを見回したい人には, さまざまな分野についての事柄が書いてある,

[1] ゲーデルと20世紀の論理学 1〜4巻 / 田中一之[編] / 東京大学出版会

を読むのが良いと思います. また, この本を読んで集合論に興味を持った人は

[2] Set Theory: An Introduction to Independence Proofs / K. Kunen / North-Holland,

[3] Set Theory / T. Jech / Springer

を読むのが良いと思います. こうした本にチャレンジするための基礎知識は, "数学のロジックと集合論"を読めば十分身についています. とくに, [2]は邦語訳

[4] 集合論 — 独立性証明への案内 / 藤田博司 / 日本評論社

があるので, 「洋書はちょっと…」という人でも安心してチャレンジできます.

連絡先

ご意見, ご感想や, 本の紹介をしてくださる大学院生・研究者の方は, 以下の連絡先にお願いします. 本の紹介をしてくださる場合は, 本のタイトル, 分野, おすすめ対象者, 紹介文と, 次に読むおすすめ本を書いて送ってください.

このページで, 既に紹介されている本の紹介でも大歓迎です.

管理人:

鈴木 仁哉 (東北大学理学研究科数学専攻 数学基礎論研究室 D1)

e-mail:

fom-suzuki dc.tohoku.ac.jp