書記の読書記録#1066『スマリヤン 数理論理学講義』（上下巻）

レイモンド・M・スマリヤン『スマリヤン 数理論理学講義』（上下巻）のレビュー

スマリヤン 数理論理学講義 上巻

スマリヤン数理論理学講義 下巻

レビュー

本書は，論理学者やパズル作家として有名な著者による集大成と言えるものである。上巻では命題論理や述語論理の初歩から解説されており，初学者読みやすい構成となっている。下巻では，その応用や再帰的関数論やコンビナータ論理について詳しく説明しており，特色を持っている。また，練習問題も本文の内容に含まれており，適切な難易度で教育的な効果が期待できる。

もくじ

上巻

第I部 一般的な予備知識

第1章 数理論理学の起源
集合論／集合に対するブール演算／ベン図／ブール等式／問題の解答

第2章 無限集合
無限集合の大きさ／カントルの大発見／連続体問題／ベルンシュタイン-シュレーダーの定理／問題の解答

第3章 問題発生！
パラドックス／ハイパーゲーム／集合論の二つの体系／問題の解答

第4章 数学の基礎知識
関係と関数／数学的帰納法／有限降下原理／ボールゲーム／ケーニヒの補題／有限生成木／一般化帰納法／整礎な関係／コンパクト性／問題の解答

第II部 命題論理

第5章 命題論理事始め
恒真式／tとfを含む論理式／嘘つきと正直者と命題論理／論理結合子の相互依存関係／否定論理和／否定論理積／そのほかの結果／16種類の論理結合子／問題の解答

第6章 命題論理のタブロー
標識付き論理式／タブロー法の例／論理的帰結／標識なし論理式を用いるタブロー／命題論理のタブローによる証明／統一表記／論理式の次数／妥当性と完全性／コンパクト性／双対タブロー／問題の解答

第7章 公理論的命題論理
一様公理系／一様公理系U_1／一様公理系U_2／問題の解答

第III部 一階述語論理

第8章 一階述語論理事始め
∀と∃の導入／∀と∃の相互依存関係／関係を表す記号／一階述語論理の論理式／変数の自由な出現と束縛された出現／解釈／恒真式／一階述語論理の公理系／問題の解答

第9章 重要な結果
一階述語論理のタブロー／量化子に対するタブロー規則／統一記法／タブロー法の完全性／ヒンティッカ集合／有限領域における充足可能性／レーヴェンハイム-スコーレムの定理とコンパクト性定理／ブール付値と一階述語付値／正則性定理／公理系S_1の完全性／問題の解答

第IV部 体系の不完全性

第10章 一般的状況での不完全性
ゲーデル式機械／いくつかの一般的な基本結果／統語論的不完全性定理／分離可能性／ω無矛盾性／一階述語論理にもとづく体系／ゲーデルの証明の核心／ω不完全性／ロッサーによる構成／問題の解答

第11章 一階算術
二値ゲーデル符号化／タルスキの定理／問題の解答

第12章 形式体系
初等形式体系／数を元とする集合と数の間の関係／初等形式体系の算術化／派生定理／問題の解答

第13章 ペアノ算術
ペアノ算術の公理図式と推論規則／問題の解答

第14章 進んだ話題
対角化と不動点／無矛盾性の証明不可能性／問題の解答

監訳者解説


文献
索引

下巻

第１部 命題論理と一階述語論理の進んだ話題

　　第１章 　命題論理の進んだ話題
　　第２章 　一階述語論理の進んだ話題

第２部 再帰的関数論とメタ数学

　　第３章 　再帰的関数論、決定不能性、不完全性
　　第４章 　 初等形式体系と再帰的枚挙可能性
　　第５章 　 再帰的関数論
　　第６章 　二重化による一般化
　　第７章 　メタ数学とのつながり

第３部 コンビネータ論理の構成要素

　　第８章 　コンビネータ論理事始め
　　第９章 　さまざまなコンビネータ
　　第１０章 　賢者，預言者，それらの二重化
　　第１１章 　完全体系と部分体系
　　第１２章 　コンビネータ，再帰的関数論，決定不能性

本記事のもくじはこちら：

書記の読書記録まとめ｜Writer_Rinka｜note