シリーズ「完全性定理を考える」その1 存在証拠とヘンキン公理
一階述語論理の完全性定理は論理学の最重要定理の一つであり、多くの教科書に証明が載っている。で、当たり前だが教科書によって証明のしかたが異なるので、いろいろな教科書の証明を比較することで理解を深めようというのがこのシリーズである。そういう勉強記録の記事ですよ。
勉強していると愕然としてしまうのだが、述語論理の完全性定理の証明は命題論理のそれよりも格段に難しい。それだけ量化子やら変数の扱いというのはややこしさを孕んでいる。そしてまた変数の扱いをどうするかという点で教科書ごとに個性が出るっぽいのである。
鹿島亮先生の『数理論理学』(朝倉書店)では他の教科書にはない工夫がいろいろ為されている。その工夫がどうすごいのかを頑張って理解したい。

- 作者:鹿島 亮
- 発売日: 2009/10/01
- メディア: 単行本
さて鹿島本。極大無矛盾集合をそのまま使っているわけではなくて、そこに「存在証拠を持つ」という条件を加えたものを KeySet と呼んでそれを使っている。「存在証拠を持つ」の定義は正確に書くといろいろ前提が必要でややこしいが、要するに集合
と
を証明するときである。命題論理の完全性定理では
というのを論理結合子ごとに証明していくが、述語論理ではこれの量化子バージョンが必要になるわけだ。
清水本ではヘンキン公理というのを使っている。というか実は清水本にはヘンキン公理という用語は出てこないのだが、たぶん他の本でヘンキン公理と呼ばれているものだと思う。その公理というのは(鹿島本とスタイルを統一して書くと)
というもの。こう書くと簡単だが、実際は
鹿島本と清水本を比較するとどうだろうか。理論を拡大していく操作が清水本ではヘンキン公理を加えることと完全な理論を作ることの二段階必要なのに対して、鹿島本では一発で済んでいる。となると確かに鹿島本のほうがわかりやすい気がする。どうでしょうか。
というわけで、もっと詳細でボリューミーな記事にしたかったが、まあ勉強記録のためにやっていることなので、ちょっとずつでもどんどん上げていくのがいいかな、という感じなので今回はこんなところで。「また今度」がいろいろ出てきたが、ちゃんと定義や命題を書こうとするとその本がそれまで使ってきた前提も踏まえなければいけなくて難しいということがわかった。それが今回の学びであった。