« 可換ブール | トップページ | 帰無仮説が正しいと言えない理由 »

第一不完全性定理

今回のfam話は、しばしば発見しつつも、他所で見つからない形の指摘は思い浮かばなかったので書いてなかったのだが(ウォッチャーさん達には当然のことだと思っていたわけではない)、Tさんが勉強のために結城さんの本を買うと宣うのを耳にしたところから、筆をとる結果に。

このたび結城さんが「数学ガール/ゲーデルの不完全性定理」を出された記念・・・というわけではなく偶然に、結城さんのはてな日記に「長男に説明する」的な記事があるのを見つけていた。
http://d.hatena.ne.jp/hyuki/20070209
子供への(長男が子供かどうかは存ぜぬが)説明としては、これ以上込み入らせずに正確な表現をするのは難題だ、というのは確かだと思う。しかし、大人がこの記事を読んでいるとすると、そのまま受け取ってもらうと困る点があるのもまた確かかと。
もちろん、本の中では結城さんが誤解を盛り込んでいないことを期待しているし、まだ読ませてもらっていないのだがおそらくそうだろう。省略なしで証明しているらしいから。


ではでは、
見たことない形でまとめてみました。

Pは証明可能¬Pは証明可能Pは恒真Pは恒真でも恒偽でもないPは恒偽
××UVUSUU
×PVPSPU
×RVRSRU
IVISIU

Pは形式体系(formal system)の任意の論理式(formula)。(閉としていない点にご注意)
あるPは、UVからIUの12マスのどれか1つだけに必ず入ります。つまり、12マスがそれぞれ論理式の集合であり、論理式全部の集合を分割したものと思ってください。
φという記号は空集合、すなわち、それに当てはまる論理式は無い、という意味。

ある体系の上の論理式でこの12マスがどのように埋められるかは、まったく自由ではなく、よく使われる体系では制約がある。
例えば、Pかつ¬Pから何でも証明できる体系では(古典論理上の体系など)、IVかISかIUにあてはまる論理式が1つでもあるならば(すなわち下に書く無矛盾でないなら)、IV、IS、IU以外のすべてがφになる。
また、Pが恒真だと¬Pは恒偽、逆もまた然り、となるような意味論を与えた体系では、Pを¬Qと置いてみればわかるが、PVとRU、PUとRV、などの埋まり方のパターンがある。


以上の準備のもとで、

体系が無矛盾(consistent)とは、IV=IS=IU=φのこと。

体系が健全(sound)とは、無矛盾でPS=PU=φのこと。

体系が完全(complete)とは、UV=RV=φのこと。

理論が完全(complete)とは、無矛盾でUV=US=UU=φのこと。

んで、なんとかうまくこれらを全部満たして、論理式が PV と RU にしか入らない理論をつくりたい、っと。

さて、
第一不完全性定理は"ある類の"無矛盾な理論の不完全性について述べるもの。
上の理論の完全性の定義からわかるように、無矛盾な理論が不完全とは、UV≠φまたはUS≠φまたはUU≠φのこと。
結城さんが書かれている「真なのに証明できない命題がある」という説明は、「真」の意味するところによるが、「UV≠φ」か、あるいは、「UV≠φまたはUS≠φ」と読める。
一方、無矛盾な理論が不完全というのは、UV=US=φかつUU≠φの場合もあり。
ただし、不完全性定理に関しては、但し書きによって普通に数学で使いたい体系に話が限定されていて、そこでは「UV=φ⇔UU=φ」が成立しているから、「UV≠φまたはUS≠φ」のほうの意味と解釈してさしあげればこの説明は間違いではない。キツイか?

ああ、でも、「Pは恒真でも恒偽でもない論理式」はキメラな気がする。
そうするとまずくなってくるなあ。やはり難題。パラドクスはどこへ?

余談だが、不完全性定理(incompleteness theorem)という名前は、体系の(意味論的)完全/不完全と用語がかぶっていて、そのせいで誤解を量産していて、よろしくない(と他のところでも訴えている方が多くいらっしゃる)。
というか、complete という用語はもうあちこちで使われまくり。
統語論的/意味論的とか、体系の/理論のとか、そういう修飾をもとめるよりも、全決定可能/不可能とか違う用語にしたほうが望ましいのではなかろうか。

文に対しては、決定可能/不可能という言葉が使われる。例えば Gödel の論文のタイトル(の英訳)で undecidable が使われている。
http://www.research.ibm.com/people/h/hirzel/papers/canon00-goedel.pdf
でもこの decidable という用語も、同じ分野で使われうる少なくとも2通りの意味があって、一つは上の意味で、もう一つは前に書いた決定問題での決定可能/不能の意味。概念的には関係しているようには思うけど。(専門的にはどうなのかな?)

なもんで、undecidable もやめて、independent という用語を使う、という人もいるようだが、しかし independent もいろんなところで使われる用語だから多義で・・・とたらい回しか。

|

« 可換ブール | トップページ | 帰無仮説が正しいと言えない理由 »

Η 数理の諸問題」カテゴリの記事

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.f.cocolog-nifty.com/t/trackback/26863/31972949

この記事へのトラックバック一覧です: 第一不完全性定理:

« 可換ブール | トップページ | 帰無仮説が正しいと言えない理由 »