数理論理学を習得するためには、その前に、数学の言葉を操り数学の考え方を駆使できるようになる必要があります。数理論理学は数学の一分野ですので、それについては数学の他の分野と変わることはありません。
幸い、数学の言葉と数学の考え方を学ぶことに特化して使える教科書が出版されています。目についたものを並べてみます。おそらく、他にもあるでしょう。
数理論理学を学ぶために最低限必要なセンスが三つある。
ところが、上記のセンスをもたないために数理論理学が理解できない状態に陥った人でも、わかったつもりになることは、できてしまう。普通の人には日常的な論理の感覚がある。そのため、数理論理学を学びはじめてしばらくは、日常的な論理の感覚をたよりにすれば、理解できたと錯覚できるのである。最初の段階をそれでしのいでしまうと、完全性定理のあたりで完全に理解できなくなり、壁にぶつかったと感じてしまう。本人は、今まではわかっていたのに急にわからなくなったと感じるだろうが、実は、最初からわかっていなかったのである。
その状態からリハビリするには、内容を絞って基本的な考え方を詳細に説明した入門書を読むのが良い。それに適した本を二冊紹介する。
日本語で書かれた入門書としては、評者の知るかぎりもっとも内容を絞ったものである。内容を絞ったぶんだけ説明が詳しい。
情報科学を学ぶにあたって必要な数学の分野で、「論理」というキーワードにひっかかるものを広く解説したもの。二部構成で、第1部「論理代数と論理設計」と第2部「数理論理学からの話題」からなる。
内容の広さが特徴である。事典類は別として、順序回路と様相論理が同じ本に載っている例を、評者は他に知らない。情報科学に必要な論理数学の分野のカタログとしても便利に使える。
ただし、世の中にはこの種の入門書を必要としない人も存在する。 どういうわけか数理論理学を学ぶ前から上記のセンスをもっている人がそうである。そんな人には、簡潔で要点をついた記述の初級教科書のほうが適している。そんな人は、ここで紹介した二冊は教科書ではなく読み物として楽しむとよい。
最密充填教科書です。よく味わって読んでください。 指導者に恵まれればとても役立つ教科書になります。独習にはつらいかもしれません。
カット除去定理（数理論理学の基本定理）の詳細な証明を日本語で読むことのできる、 現時点で入手が容易な、数少ない本の一冊です。
不完全性定理の詳細な教科書です。現在入手が容易な日本語で書かれている不完全性定理を解説した教科書のうちでは、最も精密なものでしょう。
Gödelの原論文と同じく、Whitehead & Russell流の型の理論における不完全性定理を証明しています。初学者にはその部分がつらいかもしれません。なぜ、そうしているかは著者が本書の中で説明しており、それはそれなりに説得力があります。つらい人も、ついでに、型の理論をかじることができて幸運と無理矢理思い込んででも、がんばって、読みましょう。
それはそれとして、この本とは別に、ZFの不完全性定理を書いた本があって、並べて楽しむことができると面白いかと思う。だれか、書いてくれないかな。
広い意味での数理論理学のうち情報科学と関係の深い分野が、圏論を除いてほぼ網羅された教科書です。情報科学の特に理論系を志す人が必要な知識を得るには重宝するでしょう。
多数の分野を一冊にまとめるために、論理展開もコンパクトになるよう工夫されています。そのために、読み込むにはそれなりの数学的センスは必要です。
さらに学びたい人のための文献のリストがついていないのが欠点です。
一冊の教科書で、完全性定理と不完全性定理とカット除去定理が三つとも載っています。お買い得です。
数理論理学入門から超準解析の導入までを最短で突っ走っている本です。超準解析の入門書ではありません。あくまでも数理論理学の入門書ですが、一冊の本としてのゴールを超準解析の入り口に置いているものです。
斬新な入門的教科書です。論理に対する現代的な取り扱いを詰め込んでいます。伝統的な教科書に慣れた人には異質なものに見えることもあるでしょう。
従来の教科書の多くは、読者が持っている日常的な論理の感覚を活用して導入を行い、そこから抽象化を進めていくよう書かれています。本書はそうではありません。導入部から、読者が日常的な感覚に引きずられないよう構成されています。
ページ数が少ないという意味で、薄い教科書です。内容は薄くありません。
完全性定理に絞った入門書です。全部で6章から成っています。第1章から第4章までで、後で完全性定理の説明をするために必要となることがらが、効率良く説明されています。第5章が完全性定理の証明です。第6章で、完全性定理の応用として超準解析を紹介しています。
完全性定理を効率的に学ぶのに適した教科書です。そのぶん、枝葉を落としていますので、落とされた部分を必要とする読者は、他書で補わなくてはなりません。逆にいえば、たくさんのことが書かれた厚い本をいきなり読むことに躊躇する初学者が、最初に読む本として使えます。
二部構成になっています。第II部がすごいです。第I部にも、本書ならではの特長がちらほらと現れていますが、第II部ではそれが爆発的に発現しています。
第II部では、証明体系についてとても詳しく書かれています。 最小論理・直観主義論理・古典論理それぞれについて、ヒルベルト流体系と自然演繹とゲンツェン流シーケント計算との等価性が示されています。ヒルベルト流体系と自然演繹とゲンツェン流シーケント計算をすべて扱っているだけでも数理論理学の初歩の教科書としてはあまり多くないことですが、本書は、それだけでなく、三つの体系の等価性を三つの論理で詳しく説明しています。数理論理学の初歩の教科書でここまでのことを入門者に読めるように書いてあることこそ、本書の価値といえるでしょう。
数理論理学の教科書としては、定番なんだろうなあ。
Undergraduate Texts in Mathematics シリーズの一冊だが、一部の天才の人を除き、学部生で最初から最後まで読み通すのはつらいだろう。
最初から最後まで読み通すのがつらい人は、二部構成のうち、Part A (I〜VIII)をみっちり読むと良い。特に、VIII Syntactic Interpretations and Normal Forms で、手を抜かないことが重要である。VIIIはテクニカルな細かい議論が続くため、初学者は、当たり前のことをくどく書いてあると錯覚することが多い。しかし、テクニカルな細かい議論をきちんと追う能力が、より複雑な議論に入ったときに、効いてくる。
Part B (IX〜XIII)のうち、IX〜XIIは、興味を持った章から読めば良い。Part B は、XIIIをのぞいて、章ごとに独立して読むことができるようになっている。それぞれ、扱っているトピックについての導入と呼べる内容である。分野紹介だと思うと良い。
一冊の教科書で、完全性定理と不完全性定理と自然演繹の正規化定理が三つとも載っています。お買い得です。
一階述語論理の論理式の解釈で付値を使うか名前を使うかの表のページを作りました。
型なしラムダ計算を日本語の本で学ぼうとすると、これが定番でしょう。
計算論の入門的教科書です。情報工学系の学科の半期の講義の教科書に適しているでしょう。また、現場の技術者が「理論家になりたいのではないが、基礎理論は知らないよりも知っているほうがかっこいい」と思った時に、計算論とは何かを知るための独習書としても、使えるでしょう。
題名に「C言語による」とありますが、正確にはC言語ではありません。C言語風の構文をもち構造化された制御構造をもつレジスタマシンです。プログラミング言語に詳しい人の視点では、C言語風の構文と制御構造をもちbignumを唯一のデータ型とするミニ言語です。不自然なものではなく、実際に動く処理系を作ることに難しさはないでしょう。
現実にありそうな言語を使って説明していることは、プログラミング経験のある人には、導入でびっくりせずにすむ良い効果があるでしょう。情報系の人にとっては、そこがこの本の利点となるでしょう。
計算論の入門的教科書です。数学科や情報科学科の半期の講義の教科書に適しているでしょう。
（後日加筆予定）
自然数の関数の計算可能性の定義については、いわゆる「Churchの提唱」で結着済みである。有理数については 符号・分子・分母 の三つ組で表現できるので、自然数の場合に帰着できる。では、実数の場合はどうすれば良いだろうか。こちらについては、結着済みとまではいえないが、有力な考えかたがある。実数を有理数による近似列で表現して、自然数の関数の計算可能性に帰着する方法である。実数を有理数によって任意の精度で近似できる事実を活用するのである。
アイディアだけは第二次大戦前にTuringがあたためていたようだが、本格的に研究成果が出てきたのは、1954年のRiceの論文で、計算可能な実数全体が実閉体をなすことが発見されてからといえるだろう。つまり、研究の歴史は、まだ、約半世紀しかない。長い数学の歴史にとってはつい最近である。まだ立ち上がったばかりの分野で、今なら基本的な定理の発見者になれる可能性が高い。おいしい分野だと思う。
まだ、えり好みできるほと多数の教科書が出版されていないので、あるものを並べる。
とりあえず、私がかつて集合論を学ぶのに使った本の紹介。
一部の天才の人を除き、予備知識なしでいきなりこの本を読むのはつらい。 この本の第1章の内容を1冊使って解説した教科書を事前に読んでおいたほうが良いと思うが、何が良いだろう。