選択公理の本(書評ではない)

読んだ(または、眺めた)ことのあるものを並べておきます。

Axiom of Choice (Lecture Notes in Mathematics)

Axiom of Choice (Lecture Notes in Mathematics)

The Axiom of Choice (Dover Books on Mathematics)

The Axiom of Choice (Dover Books on Mathematics)

Consequences of the Axiom of Choice (Mathematical Surveys & Monographs)

Consequences of the Axiom of Choice (Mathematical Surveys & Monographs)

選択公理と数学―発生と論争、そして確立への道

選択公理と数学―発生と論争、そして確立への道

教科書(近刊)

なんだか、面白そうな教科書が三冊も近刊です。

『数理論理学』(戸次大介)

東京大学出版会のこれから出る本のページに、数理論理学の教科書があがっています

数理論理学

数理論理学

目次から推測すると、学部の半期の講義の教科書を想定したもののようですね。

カット除去定理を日本語で読める教科書が増えるのはうれしい。

ゲーデルに挑む』(田中一之)

東京大学出版会のこれから出る本のページには、ゲーデル本もあがっています

ゲーデルに挑む: 証明不可能なことの証明

ゲーデルに挑む: 証明不可能なことの証明

こちらは目次が未掲載で、どんな感じか想像もできません。

内容紹介に「原論文の日本語訳とともにその内容について徹底解説」とあるということは、当然、PMですよね。

『今度こそわかるゲ−デル不完全性定理』(本橋信義)

なぜか、版元のWWWページではみつけられなかったけど、複数のネット書店で予約受付中です。たとえば、紀伊國屋書店BookWebでの予約ページ

今度こそわかるゲーデル不完全性定理 (今度こそわかるシリーズ)

今度こそわかるゲーデル不完全性定理 (今度こそわかるシリーズ)

予約ページの「詳細」が全然詳細でないので、内容が想像つきません。早く版元のページにでも目次が載らないかな。
2012年3月6日追記:やっと版元のWWWページにあがりました。目次も載っています。

ETCの項目がさらに増えた

Encyclopedia of Triangle Centersの項目数が2011年12月26日付けで、3910になっています。2011年12月21日付けから128増えています。三部構成になる日も近いかも。

ところで、なにやらページがおかしくなっているようですね。タグが閉じていないところがあるし、ファイルの先頭と末尾にゴミが入っています。

ETCがついに二部構成に

Encyclopedia of Triangle Centers (ETC) が、2011年12月21日付けで、ついに二部構成になりました。

ETCは、三角形の中心の事典です。エバンズビル大学の Clark Kimberling 教授が、大学内と思われるURLのWWWページで公開しています。三角形の中心の解説つきリストが本体部分で、他に解説文書がいくつか付属している構成になっています。

その本体部分が、ついに、二つのHTML文書に分割されました。今回の更新の前までは、一つのHTML文書でした。掲載されている中心が今回の更新でついに3782個になり、一ページに収めるのは無理と判断されたのでしょう。

ところで、中心を数えるときの助数詞は「個」でいいの?

数理論理学の三大基本定理を扱う順番

学生向けレクチャーの計画の再検討が必要かと弱気になってきたので、手許の教科書を調べてみました。

Logic and Structure (Universitext)

Logic and Structure (Universitext)

完全性定理(第3章)、自然演繹の正規化定理(第6章)、不完全性定理(第7章)


数理論理学 (現代基礎数学)

数理論理学 (現代基礎数学)

完全性定理(第5章)、不完全性定理(第6章)、カット除去定理(第9章)


数学基礎論

数学基礎論

完全性定理(第1章)、不完全性定理(第3章)、カット除去定理(第8章)


やっぱり、完全性定理からが定番ということで、予定通り完全性定理からでいいかな?

数理論理学の三大基本定理の難しさ

完全性定理って、そんなに難しいものなの?」に自分で回答していたことに、いまごろ気づきました。

http://taurus.ics.nara-wu.ac.jp/staff/kamo/shohyo/logic-1.html から引用

数理論理学を学ぶために最低限必要なセンスが三つある。

  • シンタックスとセマンティクスが区別できること
  • オブジェクトレベルとメタレベルが区別できること
  • シンタックスとセマンティクスの区別と、オブジェクトレベルとメタレベルの区別が、区別できること

このセンスがないと、数理論理学がそもそも何を対象としているかすら理解できなくなる。

ところが、上記のセンスをもたないために数理論理学が理解できない状態に陥った人でも、わかったつもりになることは、できてしまう。普通の人には日常的な論理の感覚がある。そのため、数理論理学を学びはじめてしばらくは、日常的な論理の感覚をたよりにすれば、理解できたと錯覚できるのである。最初の段階をそれでしのいでしまうと、完全性定理のあたりで完全に理解できなくなり、壁にぶつかったと感じてしまう。本人は、今まではわかっていたのに急にわからなくなったと感じるだろうが、実は、最初からわかっていなかったのである。

数理論理学の三大基本定理(完全性定理、不完全性定理、カット除去定理)のうち、完全性定理だけがシンタックスとセマンティクスを結ぶ定理で、残りの二つはシンタックスだけで完結した記述ができます(「完結した記述ができる」は「完結している」ではない。念のため)。シンタックスとセマンティクスの区別の理解が不十分だと、完全性定理のステートメントすら理解できないのですね。

証明のテクニカルな複雑さだけで、完全性定理が三つのうち最も易しいと思っていました。甘かったようです。

研究室の学生向けのレクチャーの計画を考え直す必要があるかな?

完全な理論の作り方

無矛盾な一階の理論Tが以下の二条件をみたすとする。

  1. 任意の閉原子論理式\varphiに対して、T\vdash\varphi または T\vdash\neg\varphi が成り立つ。
  2. \exists x \psi(x) の形の任意の閉論理式に対して、ある閉項tが存在して、T\vdash\exists x \psi(x)\leftrightarrow\psi(t) が成り立つ。

このとき、Tは完全な理論である。なぜならば、任意の閉論理式\varphiに対して、条件2を繰り返し適用することで、T\vdash \varphi\leftrightarrow\varphi' をみたし量化子を含まない \varphi' を得る。\varphi' に出現する各原子論理式\varphi'_iに対し、T\vdash\varphi'_i ならば真を、 T\vdash\neg\varphi'_i ならば偽を割り当てる。その下での \varphi' の付値が真ならば T\vdash\varphi' が成り立ち、偽ならば T\vdash\neg\varphi' が成り立つことが、命題論理の完全性定理から導かれる。

ところで、任意の無矛盾な一階の理論に対して、そのHenkin拡大は条件1,2をみたす無矛盾な理論である。すなわち、任意の無矛盾な一階の理論Tに対して、Tの拡大T'が存在して、T'は完全かつ無矛盾である。ただし、理論の拡大において定数記号の追加は許す。

PAも一階の理論なので、以上の議論が適用できる。すなわち、PAが無矛盾ならば、PAの完全かつ無矛盾な拡大が存在する。

命題論理は一階述語論理のサブセットであることから、以上の議論は命題論理の理論にも適用できる。命題論理において、条件2は自明に成り立っている。命題論理の原子論理式は p の形のものだけなので、条件1は次のように書き換えられる。

  1. 任意の命題変数pに対して、T\vdash p または T\vdash\neg p が成り立つ。

つまり、この辺の議論はPAと命題論理でパラレルに展開できるものであって、PAと命題論理の違いをことさらに際立たせるものではないということ。

蛇足: id:wd0:20111214:a のつづきでもあるが、独立した記事として読めるように書いたつもり。