北田 発見への道 6章

6章 述語計算の完全性

話を少し戻して、述語論理における対象の変域が有限個と可算無限個の場合では、無矛盾性の議論に違いがあることを指摘。加算無限個の場合では、直観主義で排除されている手法を利用している。これを認めるような述語論理を集合論的述語論理と本書では記述し、以下議論の対象とする（ツッコミ：メタの議論で有限のステップを無視しているのでヒルベルトプログラムの範疇を超えた議論をしているという認識でいいんだよね？）。

「Kを理論Tの命題式の集合とする。KがTに対して整合的であれば、Kは対象領域を自然数論Nとするモデルを持つ」ことが示され、これにより完全性が（有限の議論を超えた道具立てで）示されたことになり、「述語論理の命題式Aが恒真であることと定理式であることは同値である」、または「述語論理の命題式Aが定理式であることは、Aが自然数論の任意の構造Mをモデルとすることである」ことが言える。

最後に、ヒルベルト的なメタの取り扱い方だけでいえる以下の定理を紹介して終わり。

「述語論理に証明可能でない式を公理に加えると、形式的自然数論は、ω矛盾する」これもある意味、述語論理の完全性を含意しているものと思われる。

感想：北田先生は直感的な意味でという言葉を使っているが、これは直観主義的な立場でという意味ではなくて、厳密でないがわれわれの理性がこのように把握しうる、という意味で使っている。読み間違いはないがあまり使ってほしい言葉ではない。

結局ゲーデルはある種の完全性を含意するような説明を、有限の立場を超えた道具立てで示した、ということでよいのだろう。結局野谷先生も言っていたように、メタな議論にどのような道具立てを用意するかは悩ましいのであるなあ。

北田 発見への道 5章

5章 述語計算の無矛盾性

今度は述語計算。統語論を定め、推論規則を3つ(MP, GEN, SPEC)提示し、命題論理の公理系11こを引き継ぎ、新たに4つの公理を追加する。

真理値の付与は命題論理の場合よりやや複雑になる。すなわち命題の真理値は、述語関数の意味と、述語関数に渡す定項の意味を与える必要がある。例として 「∃b A(a,b) 」の真理値の付与で、変数の変域が {zero,one} の場合を考える。二変数述語は、引数として、(zero,zero), (zero,one), (one,zero), (one,one) の４通りに対して、どのような真理値を与えるかを考え 2^4 = 16 種類の述語が存在することがわかる。「∃b A(a,b)」はAとしてこの16種類のどの述語に対しても、そして、任意のa への付値（すなわち zero もしくは one）に対しても、その真理値が 1 であるかを分析する。実際には充足はするものの、恒真でないことがわかる。

述語論理の無矛盾性は命題論理の時と同様に示される。すなわち、全ての公理＝11の命題計算の公理＋4つの追加された公理が恒真であることを示す。そののち、3つの推論規則MP, GEN, SPEC に対して真理値が保存されることを示す。これにより全ての定理が恒真であることが示されるので、矛盾式が定理でないことがわかり、無矛盾性が確かめられる。

注：上記の無矛盾性の議論は変数の領域が有限の場合にのみ有効であり、例えば領域がNの場合にどのようになるかは次章で説明する。

上記了解。少し複雑になっただけで、特に引っかかる部分はないかな。野矢先生は述語論理の場合は恒真式ではなく、妥当式と言っていた気がするが・・・まぁいいか。

北田 発見への道4章

4章 命題計算の完全性

拡張命題論理と称するモノから完全性に迫る。すなわち命題式の論理式に対して、命題変数の閉包をとる操作を行うと、（自然数論では変数記号に関する閉包をとる限りこのような事情は発生しない）、任意の式は真理値1か0のみをとるようになる。この議論をつぶさに見ると、「真理値1の閉包命題式は拡張命題論理の定理であり、真理値0の閉包命題式の否定は拡張命題論理の定理である」という予測が得られ、ここから「閉包命題式が真理値1をとることと拡張命題論理の定理であることは同値である」、すなわち「命題論理の命題式Aが恒真式であることと、Aが命題論理の定理であることは同値である」ことが予想される。

実際、「命題論理の恒真式は命題論理の定理式である」ことは数学的帰納法を利用することによって確かめられる（メタでは数学的帰納法は有用な道具立てとされる）。また、命題論理において証明可能でない式を公理に加えると体系が矛盾することを示すことができる。

上記をモデルの言葉でいえば、「命題論理の命題式Aが定理式であることは、Aが自然数論Sの任意の構造Mをモデルとすることと同値である」、または「命題論理の命題式Aが定理式であることは、それが恒真式であることと同値である」

以上、命題論理を自然数論の影とする立場からだとこのように拡張された命題論理を持ち出す必要がある（野矢先生の言葉でいえば、自然数論における命題は、変数の閉包をとる限り---すなわち閉じた式-- である限り、自然数論が真偽を決定することに責任を持つべき数論的命題であることに対応する）。証明とか、ヒューリスティックに関しては納得がいくがもう少しやりようはないのだろうか？命題論理をそれ自体として扱うのではなく、自然数論の影として扱うからこのようになるのだろう。まぁ本の主題がゲーデルの定理であるから仕方ないのかもしれないが、命題論理の枠内だけで完全性定理を証明してほしかった。野矢論理学でも完全性の証明ははしょられているわけだし・・・べつのテキストブックを用意する必要がありそうだ。

北田 発見への道 3章

3章 命題計算の無矛盾性

いったん命題理論から始める。しかし本書では一貫して自然数論Sを前提に置いているため、命題変数は自然数論における命題と同一視する。命題論理自身もSの影としてみる立場のようだ。

統語論、推論規則（MP１つ）、公理系(11こ）を提示。意味論として真理値表を導入する。全ての公理がトートロジーであることが示せる。また、唯一の推論規則MP の前件が真と仮定した際に、後件が真になる、すなわち真理性が保存されることが示せる。トートロジーたる公理からはじめ、MPを有限回用いて定理を導いていくので、全ての定理がトートロジーであることが示せる。したがって矛盾式が定理でないことが示されるので、無矛盾性・整合性が確かめられる。

真理値表を与える代わりに、モデルという概念を導入して、「命題論理の定理式がトートロジーである」の現代版「命題論理の定理式は、自然数論における任意の構造Mにおいて真である」ことを示す。

全体の議論は非常に明快。うまく公理系、推論規則を選んだから、かな。あと、命題論理だとモデルの概念が簡単になりすぎて逆にわかりづらい・・

北田 発見への道 1-2章

発見への道

1章 不完全性定理とはなにか

・自然数論を含む理論Sを考える

・Sには反証できない命題Gが存在する＝ゲーデルの第一不完全性定理

・これは統語論的不完全性と呼ばれる

・Gは「私は証明できない」という意味の命題

・Gはメタレベルの命題であり、自身をS自身に「写さない限り」いけないはず

・したがって、ゲーデルの不完全性定理は、統語論的な形式的な演算のみによっておこる不完全性でなく、意味論的な仕掛けが存在することが示唆される

極めてまっとうなことを短い文章にまとめている。惜しむらくは、わかる人にしかわからない文章であるように見える。わかる人には知ってることだし、わからない人にはわからないという・・・・

2章 形式的自然数論

・第一不完全性定理は、「Sは矛盾するか不完全かである」ともいえる

・第二不完全性定理は「Sが無矛盾ならばその無矛盾性はSにおいて形式化される方法によっては証明できない」

・ヒルベルトプログラムを打ち砕いたのは、第一ではなく、第二の不完全性定理

・ラッセル「プリンキア・マティマティカ」＝論理主義はもはやオワコン

・とは言え直観主義や形式主義に大きな影響を与えた

・直観主義のブラウアーは痛烈に批判

・ヒルベルトは、それに対して理論の取り扱いを直観主義の方法（有限の取り扱い）で回避しようと考えた

・第二不完全性定理がそれを不可能と指摘した

・Sの説明。統語論、推論規則（MP, GEN, SPEC）、公理の紹介

・推論 |- 、定理についての説明

この辺りはまぁ常識なので特に疑問はない

北田 発見への道の勉強開始

今日からしばらく以下のテキストブックでゲーデル不完全性定理を勉強する

「理系への数学」に連載していたものをまとめたもののようだ。ぱっと見たところ、メタな議論をすることに特化している模様。日本語が多いので読みやすい。ゲーデルナンバリングの振り方に特徴がある。初学者向けではなさそう。短くて読みやすそう。

ブログタイトルでは、「発見への道」と称することにする。

野矢論理学 5章

ゲーデルの不完全性定理の概観。なぞっても面白くないので自分なりに再構成。

自然数論を含む公理系Nは、矛盾しているか、不完全である（ゲーデルの第一の不完全性定理）。そして、Nの無矛盾性は、有限の立場では証明することができない（ゲーデルの第二の不完全性定理）。

そもそも、理論の無矛盾性などのメタな問題の議論は、理論内部で行うような式変形ではなく、他の何らかの手段で検証されるべき性質のものである。とはいえ、我々はヒルベルト的な考え方、すなわち有限の立場で（すなわち数学的帰納法などを使った構成的立場で）メタな議論を行うことを常としている。命題論理や述語論理の完全性や無矛盾性はその方法で示される。一方、自然数論は、その方法では完全性や無矛盾性を示せないとゲーデルが指摘した。なおゲンツェンは、別の立場（超限帰納法）で議論すれば、無矛盾性が示せると指摘した。我々は、理論に対するメタな議論をする際にどのような方法に訴えるべきかについて、再考するべきかもしれない。

第一不完全性定理は、実際に「私は証明できない」という意味の命題が存在することで示される。「・は証明できる」という述語はメタな述語であり、1階述語論理における述語ではないが、ヒルベルト流メタ議論は、自然数論と同一の道具立てを使っているため、「・は証明できる」という述語を自然数論Nにおける述語にすることができる。そして、対角化定理を利用することで、「私が証明できない」という意味の命題の存在を示すことができる。第二不完全性定理は、第一不完全性定理をちょろっと使うとすぐに出てくる。

一応ゲーデルの不完全性定理に関してその定理の意味とそれを取り巻く議論は俯瞰できるようになった。定理の証明はざっと読んだ感じなのでもう少し時間をかけてゆっくり見ていきたい。

野矢先生の本は、対話形式ということもあり、素朴に思うような疑問にきちんと答えてくれるのがありがたい。この本によって不完全性定理の意味を、過大評価せずに見つめなおすことができ、また理論に関するメタ的な理解が深まったように思う。

以上で野矢論理学読了。