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

数学

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

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 のつづきでもあるが、独立した記事として読めるように書いたつもり。

本務先のページにいずれ書き加えたいこと（おまけ編）

数学

本務先の研究室サーバに置いている「書評」のページの「おまけ」の部分に書き加えたいけど、必要な調査ができていないために、まだ、書けないでいることがある。「よくある間違い」のベージに「体系に数学的帰納法が入っていることが不完全性定理の本質である」を入れたいのだが、「よくある」かどうかが確認できていない。

この間違いが流布している現場を確認できていない。だれがこの間違いを言ったかは教えてもらったのだが、出典を聞くのを忘れていた。探しているが、まだ、みつけていない。

流布の現場が確認できたら、間違いであることの解説を書くのは簡単だ。「RobinsonのQ」の一言で終わる。id:ytb:20081209:p1 で教えていただいた "Weak theories and essential incompleteness" (Vitezslav Svejdar) の紹介も解説に加えると、もっと良いかも。

本務先のページにいずれ書き加えたいこと

数学

本務先の研究室サーバに置いている「書評」のページに書き加えたいけど、まだ考えがまとまっていないことを、とりあえず、ここに書いておく。考えがまとまったら本務先ページに反映させたい。

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

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

書き加えたいことはいくつかあるが、いずれもこれに関すること。

三つめについて

初期には、最後の一つがなく「二つのセンス」だった。

三つめを加えたきっかけは、何かの文書を読んだことだった。その文書では、シンタックスとセマンティクスの区別は何ページも使ってきっちりと解説し、また、オブジェクトレベルとメタレベルもきちんと区別して解説していた。それなのに、どうも変だと感じた。じっくり読んで、その文書の書き方では、シンタックスとセマンティクスの区別とオブジェクトレベルとメタレベルの区別を、同じものだと読者に誤解させるおそれがあることが理由だとわかった。そこで、三つめのセンスを自分のページに書き加えた。

その文書が何だったかが、今となってはわからない。数学啓蒙書の可能性が高いのだが、心当たりを何冊か探して読んだが、まだ、該当するものをみつけることができないでいる。

リハビリに適した本について

三つの必須なセンスを持たなくても、日常的な論理の感覚をたよりに数理論理学がわかっているつもりになることはできると書いた。そして、その状態からのリハビリに適した入門書を二冊紹介した。

嘘は書いていないのだが、今の書き方では、その二冊の本に上記の三つのセンスについて論じている部分があると誤解されるおそれがある。内容を絞ってそのかわりにみっちり解説した入門書を読むと、なぜか、上記の三つのセンスがいつのまにか身に付くだろうという主旨なのだが、そこを誤解のないよううまく表現できないでいる。

数理論理学とプログラミング、特に基幹ソフトウェアのプログラミングについて

対象も論理、それを分析する手段も論理、を循環論法のように感じる人がいるそうだが、私は、そのように感じたことは一度もなかった。Cで書かれたCコンパイラをブートストラップでビルドするのと、同じ感覚だったからだ。

また、若いころに出会った先人たちにも、ロジシャン兼システム系プログラマのような人が多かった。

個人的な経験を（過度に）一般化して、プログラミング、特にOSや言語処理系などの基幹ソフトウェアのプログラミングの経験は数理論理学を学ぶのに役立つと、かつては思っていた。最近、そうでもないのではと思ってきた。単に、ロジシャンに必要な能力とシステム系プログラマに必要な能力に、共通部分が多いだけではないかと考えが変わってきた。

完全性定理って、そんなに難しいものなの？

数学

小島寛之さんも、理論の完全性と理論のモデルに対する完全性（証明論的完全性と意味論的完全性）を混同しています。「ゲーデル本食い歩き - hiroyukikojimaの日記」より、該当部分を引用します。

命題論理の場合、「命題論理の完全性定理」によって、正しい命題(付値が1である命題)には必ず証明が存在するから、φまたは¬φのどちらかは正しいので、どちらかは証明できてしまう。

たとえば、\varphi として p を考えるだけで、引用文が間違いであることがわかります。原始論理式 p に対して、非論理公理なしで p も \neg p も証明できるはずがありません。

吉永良正さんも、『ゲーデル・不完全性定理』( isbn:4061329472 )で、まったく同じ間違いをしています。

「命題論理の完全性定理」をちゃんと理解していれば、こんなとんでもない間違いはしないんですけどね。完全性定理って、その主張を理解することすら困難な難しい定理ですか？ 数学啓蒙書で実績のある二人が、そろってまったく同じ間違いを犯すほど，難しい定理なんですか？

2011年12月16日追記：
吉永良正さんの間違いについては、「書評」からたぐっていけるところに書いているので、必要な方は参照ください。小島寛之さんの間違いにもそのまま適用できます。

説明いろいろ

数学

具体例？

学生さんにとある証明を解説していたときのことです。

「『PでありQでないものは存在しない』と『Pであるものは必ずQである』は同じことだよね」と説明してもわかってもらえませんでした。そこで、「『タクシー運転手で自動車運転免許を持たない人はいない』と『タクシー運転手はみな自動車運転免許を持っている』は同じことだよね」というと、「エウレカ！」でした。

人間の認知の特性を見たと思いました。

情報科学科限定？

上とは別件で、対象レベルとメタレベルの区別の説明の際に使った例です。

wcコマンドのソースコードのサイズを調べるためにwcコマンドを使って

wc wc.c

を実行した時、実行したwcコマンドにとって wc.c は単なるテキストファイルであって、それがC言語で書かれたプログラムであることも、wcコマンドを実装していることも、知ったこっちゃないよね。「知ったこっちゃない」は否定ではないよね。

情報科学科の学生さんには理解してもらえたけど、数学科に行って同じ説明をして理解してもらえる自信はありません。