« 2009年9月 | トップページ | 2009年11月 »

2009年10月

第一不完全性定理

今回の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は恒真でも恒偽でもない論理式」はキメラな気がする。
そうするとまずくなってくるなあ。やはり難題。パラドクスはどこへ?

続きを読む "第一不完全性定理"

| | コメント (0) | トラックバック (0)

可換ブール

二項ブール演算は、16種類。

そのうち、可換律の成立しているものは、8種類。

それぞれ次のように呼ばれ(表記され)ている。

PTTFF
QTFTF
FALSEFFFF
ANDTFFF
NORFFFT
EQTFFT
XORFTTF
ORTTTF
NANDFTTT
TRUETTTT

| | コメント (0) | トラックバック (0)

運動できる子は勉強もできる?

某TV局Kの番組で、例の体力テストと学力テストの全国調査を引用して、「運動できる子は勉強もできる」というような主張を流していた。しかも、原稿読みのアナウンサーではなく、専門家として出演していた大学教員が口にしていた。

残念ながら、これは典型的な誤りの一例と思われる。

これまでにも度々言及していると思うが(たとえばこれとか)、群レベルの相関と(群の効果を除いた)個人レベルの相関は、独立である。
だから、群の集計データだけを引用していては、個人レベルの主張(クラスの中で、運動できる子は勉強もできている、みたいな)の根拠にならない。
実際は、個人レベルでもそのように相関したデータになっているのかもしれない。そこを調べることまではしていないので、その点、事実がどうなのかは知らない。だから、結論そのものが正しい可能性は私の中でまだ残っているが、結論と根拠の結びつけが間違っている。

ちょっと検索してみると、ウェブ上にもこれと同様の根拠で同様の主張をしている記事が多数あるようだ(もちろん丁寧に群レベルの主張にとどめている方もいらっしゃる)。
やはり「よくある誤り」殿堂入りは確実かな。


| | コメント (0) | トラックバック (0)

categorical

読書会の宿題の件ですが、

「範疇的」と訳すべきのようだ。Tさん、すみません、ありがとうございます。

Wikipediaによれば、Löwenheim–Skolem theoremの記事の中に、この用語はOswald Veblenが由来だと書かれている。

現在、モデル論を再勉強しています。

ところで、この例に限らず、categoryという言葉が、いろんなところで、いろんな意味で使われている。
最も多義性に注意しなければならない術語の1つではないかと思われる。
どうしてこんなことになってしまったのかという歴史的なことは不勉強なので・・・。
私にはアリストートルくらいしかわかりません。

どなたかご指導下さい。

| | コメント (0) | トラックバック (0)

« 2009年9月 | トップページ | 2009年11月 »