不完全性定理

便宜上数字は0と1だけ使います。
文字列をデジタルに変換したと思えばいいかもしれません。
一冊目・0101010101・・・・・
二冊目・0010010011・・・・・
三冊目・1011011010・・・・・
以下無限に重複無く、延々と冊数が増えていきます。
今度の本の作り方は、
Ｎ冊目のＮ番目の数字が0ならば1に、1ならば0に換えます。
つまり、一冊目の一番目は0ですから1に、
二冊目の二番目も0ですから1に・・・という風に換わっていきます。
こうして作った本もまた、どれとも重複しない本になります。

ここで何処を換えていったのかに注目しますと、
対角線の部分を換えていった事に気づかれると思います。
よってこの様な方法を対角線論法と言うそうです。
長文スマソ。

わかりましたでしょうか。。。。

「無限論の教室」と「ゲーデルの哲学」が読める
講談社現代新書をよろしくだね。
読み返してみよう。

前から思ってたんだけどさ・・・
なんで「不完全性定理」と「不確定性原理」って混同視されるんだろう？
文字からして違ってるのに・・・
文系の香具師ってのは文字も読めないんかなぁ？

わかりました！
ではラッセルのパラドックスの
対角線論法による証明をお願いします。

１２３じゃないですが、
カントールの実数の話だと
それぞれの本の文字列は無限にあるという設定になる。
（そんな本はあり得ないとか考えるとわけわからなくなる。
この地球上に存在する全て本の文字列をひとつにつなぎあわせても
それは有限の文字の列にしかならない。それはともかく）
数列の方はそれぞれ無限個の数字が並んでいるとする。
並び方のパターンは、１つの位につき二通り（０か１）あって
それが無限個並んでいるから、いわば２の無限乗になる。
２＾n（n→∞）
（１文字なら２＾１＝２
　２文字なら２＾２＝４
　３文字なら２＾３＝８
　……
　その極限が２＾n（n→∞）　）

>>123-127
まあそうなんだけど、この手の文脈で対角線というのはもうちょっと抽象的に、
形式 F(a,b) に対して diag_F(a) := F(a,a) で定義される diag_F のことだよ。

例えば F(a,b) := (a∈b) とするとき、F(a,b) は a,b に関する命題だから、
diag_F(x) = (x∈x) は集合 x に関する命題。diag_F によって内包が
指示される集合 D := {x; diag_F(x)} が存在するので、D の補集合 D^ が存在する。
よって diag_F(D^) ⇔ D^∈{x; diag_F(x)} ⇔ D^∈D ⇔ ¬D^∈D^ ⇔ ¬diag_F(D^)
これは矛盾。これがいわゆるラッセルパラドックス。

でもラッセルパラドックスの「証明」なんてものはないよ。

一方、対角線論法というのは対角線を用いて全射が存在しないことを示す
背理法のこと。

集合というものについて、少し考えます。
集合とは、何かの集まりだと考えて下さい。
例えば、偶数の集合とは、偶数の集まりです。
そして、集合を作っている対象を、その集合の「要素」と言います。
偶数の集合の要素は、2とか4とか8とかになります。
続きます

確かに１３２が言うように本の例が適切かどうか疑問だけど，要点はつかみやすいよね．
ようはカントールの対角線論法は自然数と実数が一対一に対応しないということの論証．
まず0から1までの区間を考える．この区間は数直線と同じ濃度であることはまあ証明できる．
だから実数の大きさを考えるときは0から1までの区間を考えればよい．そこでその区間の点が
自然数と一対一に対応できたと仮定しよう．すると次のような表ができるだろう：

1:0.000000000・・・・・
2:0.101010101・・・・・
3:0.010010011・・・・・
4:0.101101101・・・・・
・・・・・

すると123が説明したような仕方でこの表のどれとも異なっている実数を
0から1までの区間に常に見つけることができる．ところで仮定から，その
実数はある自然数に対応づけられているはずだ．その自然数をnとしよう．
しかし今見出された実数はn番目の場所で最初にnに対応づけられている実数と
異なっているのであるから，nには二つの異なった実数が対応づけられること
になる．しかしこれは最初の仮定と矛盾する．

>>133
＞diag_F によって内包が指示される集合 D := {x; diag_F(x)} が存在するので、
＞D の補集合 D^ が存在する。

がよくわからない．なんで補集合が存在すると言えるんだ？

>>136
その指摘は正しい。すべての集合を集めたものを全体集合とした時の補集合であるから
補集合といういい方は適切ではなかった。

ただし、すべての集合を集めたものを集合とみなす場合にラッセルパラドックスが
起こるのだから、全体集合を指示すれば補集合と呼ぶことは正しい。
当時は何が集合で何が集合でないかは明らかではなかったのがこの話の本質ではある。

ちなみにゲーデルは集合というものを実在概念と考えていて、
集合の諸性質は発明されるのではなく科学上の発見と同じように
発見されるものだと考えていたそうだ。

>>133さんの様に論理学を用いた説明の方がいいでしょうか？
僕は論理学すらわからない無知ですが、
演算子を使わないでも、それなりに不完全性定理の一部を理解できたので、
その方法で説明を試みました。
この様な説明はナンセンスでしょうか。

ラッセルのパラドクスの「証明」はありませんね。
ご指摘ありがとうございます。

>>138
う〜ん，微妙だな．

＞当時は何が集合で何が集合でないかは明らかではなかったのがこの話の本質ではある

だけど現在でも「集合とは何か」ということが非常に明確だというわけではないと思うけどな．
むしろ僕が言いたかったのは全体集合とか補集合とか「指示する」という概念を使わなくても
ラッセルのパラドックスは出てくるじゃないかということなんだけどね．

>>139
要はプラトニズムということね．

>>141
どうなのだろう。
「自分で自分のひげを剃らない人すべてのひげを剃る床屋のひげは誰が剃るのか」
という有名な喩えも同じ概念を用いていると思うのだけど。概念の名前を出すか
出さないかの違いではないかなあ。

集合が何かが非常に明確というわけではないというのはまあそうかも知れない。
集合や算術のように十分に複雑な対象は、ある時点と比べてより明確になることは
あるだろうが、完璧に明確になったと断言できる日は来ないだろう。

>>140
ナンセンスではないと思う。人それぞれに分かりやすいやりかたがあるのだから。

ただし対角線論法の例として>>135のように実数を使うのはあまり分かりやすくはない。
なぜなら記数法には2進法でいえば 0.0111... = 0.1000... という曖昧性があって、
これを逃れるためにはひと工夫が必要。

>>143
ありがとうございます。
それでは、多少曖昧な説明になりますが、続きます。

野矢氏の「無限論の教室」から引用すれば
「まあ、このハードルは無理して飛ばなくてもかまいません、
全部バタバタ倒してっちゃってもいいくらいです」
でしょうか。

>>134の続きです。
色んな集合を考えていきますと、場合によっては、
ある集合の要素に自分自身が入っている場合も考えられます。
例えば「犬」という集合の要素は、ポチとかラッシーとかの個々の犬です。
この場合、「犬」という集合そのものは要素ではありません。

しかし、「犬ならざるもの」という集合を考えますと、その要素は、
猫とか本とかですし、「犬ならざるもの」という集合それ自体も、
犬では無いので、「犬ならざるもの」という集合の要素として、
自分自身も入っていなくてはいけません。

この様にして、自分自身を要素としてもたない集合（偶数とかです）と
自分自身を要素としてもつ集合（犬ならざるものとかです）とが、
区別されてある事になります。続きます。

そこでラッセルは、自分自身を要素としてもたない集合を集めて、
集合を作ろうとします。これを「ラッセル集合」と命名しましょう。
つまり
ラッセル集合＝自分自身を要素としてもたない集合の集合
です。続きます。

ある集合Ｘがラッセル集合の要素だとします。
この時、ある集合ＸはＸ自身の要素ではありません。
つまり
「Ｘ」は「ラッセル集合」の要素である＝「Ｘ」は「Ｘ」の要素でない
と、なります。

ここで「Ｘ」に「ラッセル集合」そのものを代入します。
すると、
「ラッセル集合」は「ラッセル集合」の要素である＝「ラッセル集合」は「ラッセル集合」の要素でない
となります。
同様に「Ｘ」がラッセル集合の要素でない、としても矛盾します。
以上がラッセルのパラドクスだそうです。

ラッセルのパラドクスが対角線論法だという所は、
起きてからさせて下さい。

>記数法には2進法でいえば 0.0111... = 0.1000... という曖昧性があって、
これを逃れるためにはひと工夫が必要。
実数の連続性を前提として、
有限小数は全部無限小数表示に直しておけばいい。

１２３の説明わかりやすい。
厳密性はあとで数記号でやればいいし。

もっと教えてホスイ。

http://homepage.mac.com/hiroyuki44/

集合を0と1の列で表現するやり方があります。
集合がある対象を要素にもつときに「1」で表し、
集合がある対象を要素にもたないときに「0」で表します。
例えば、「犬」という集合ですと、
ポチ1、ラッシー1、偶数0、素数0、などとなります。
そして、各対象を適当に並べて、
例えば、ラッシー、偶数、素数、ポチと並べたならば、
「犬」という集合で考えるならば、1001、という列で表現できます。
続きます。

>>149
それじゃ駄目

．０００００００００…
．０１１１１１１１１…
．１０１００１１１１…
．０１０１１１１１１…
．１０１１１１１１１…
．１０１００１１１１…
．０１１０００１１１…
．０１１０１１０１１…
　・
　・
　・

対角線の反転
．１００００００００… は表のどこにも出ないが、２番目の
．０１１１１１１１１… と等しい。
このような望まない事態がすべて排除できることを保証する必要がある。

あらゆる対象を適当に並べていきます。
>>152で言い忘れましたが、対象といいますと、
2とか4とかポチとかですし、集合も対象化されてしまいますから、
偶数とか犬とかも対象です。
ここで、例えば「犬」という集合を0と1の列で考えます、
並べていった対象の三番目に「犬」がくるとすれば、
>>145で書きました様に、
「犬」という集合は自分自身を要素としてもたないので0になります。
つまり、
??0???・・・・・となります。

また、あらゆる対象を適当に並べていきます。
今度はラッセル集合を0と1の列で考えます。
先に、やり方を言いますと、
「犬」が三番目にきて、「犬」の0と1の列の三番目が0ならば、
ラッセル集合の三番目は1になります。つまり、0と1を反転させます。
何故かといいますと、繰り返しになりますが、
「犬」という集合は自分自身を要素としてもたないので三番目が0、
ですから、ラッセル集合の三番目が1という事は、

三番目にきた「犬」という集合を要素にもつ
　　　　　　　‖
自分自身を要素してもたない集合を、要素にもつ
という事です。

もう少し、ラッセル集合の0と1の列を考えます。
法則的に書きますと、
ある集合「Ｘ」が対象化されてＡ番目に並べられた時、
ある集合「Ｘ」の0と1の列のＡ番目を反転せよ。となります。
少し、やってみます。
仮に、一番目が「犬ならざるもの」
二番目が「偶数」
三番目が「犬」、四番目が・・・・・と並んでいるとします。
この並びですと、「犬ならざるもの」の0と1の列の一番目は1、
「偶数」の0と1の列の二番目は0、
「犬」の0と1の列の三番目は0になります。
よってラッセル集合の0と1の列は、011・・・・になります。
>>146のラッセル集合の定義からして、
「犬ならざるもの」「偶数」「犬」という、要素を
ラッセル集合がもつ、もたないを考えますと、
0と1の列のとおり011・・・、もたない、もつ、もつ、・・・・・
となります。

>>154-156
「あらゆる対象」のなかには個々の実数（あるいはすべての長さ）が
含まれるが実数に自然数で番号づけ出来ないことは別途示されるから
そのやりかたではラッセルパラドックスを提示できない。

むしろ床屋の例の方が適切。
「ａがｂのひげを剃る」の対角線「ｘがｘのひげを剃る」を考えるなら
人間は可付番な対象なので濃度に関する困難は起こらないし、
ラッセルパラドックスと本質的に同じ論理構造を示すことが出来る。

けれどもすべての集合に関係するパラドックスというためには
やはり「ａ∈ｂ」の対角線「ｘ∈ｘ」を考えなければならない。
すべての集合は可付番ではないので対角線という呼称はあくまで
暗喩であって、対象を列挙した表で対角線を図示できるわけではない。

ラッセル集合もまた、対象化されて並ぶわけですが、
>>156に書きました
Ａ番目に並べらた時、0と1の列のＡ番目を反転せよ
と、>>127に書きました
Ｎ冊目のＮ番目の数字を反転せよ
は、同じだという事がわかりますでしょうか。
つまり、ラッセル集合の0と1の列を作るとは、
対角線論法の手口と同じです。

>>158の最初に書きました様に、並ぶはずなのですが、
対角線論法の手口と同じならば、そうしてできた集合は、
どれとも重複しない事になります。
しかし、>>155で書きました様に、あらゆる対象を適当に並べたはずなので、
ラッセル集合の0と1の列は矛盾してしまいます。
むりやりラッセル集合を並べますと、
Ａ番目に並べられた、ラッセル集合の0と1の列を反転しようにも、
>>147で書きました様に、ラッセルのパラドクスとなります。
以上で終わりです。長文スマソ。。。

スマリヤンの訳本だと「対角化」て言葉が使われてるね

>>157
157さんのおっしゃるとおり、実数を自然数で番号づけできない事は、
>>159までの私が書きました、野矢氏の本にも掲載されておりました。
その本では、途中から座標平面を使っての説明でした。
原本そのままに書こうと思っていたのですが、
座標平面を文体で表す事により、とてもわかりずらくなってしまいました。
そこで、どうにか座標平面を使わずに説明しようとした結果、
いらぬ混乱と誤解を招きました。
でしゃばりすぎた事をお詫びします。

diagonalization の訳だからね

>>161
いやいや、一般の対角化は座標平面のように図示できるものではないよ。
例えば座標平面のすべての部分集合は座標平面とも対等ではないから。
すべての集合の集まりには任意に大きな濃度の集合が含まれている。
それらは表でも図でも書き表せない。

森毅，『無限集合』，数学ワンポイント双書 4，共立出版
竹内外史，『新装版 集合とはなにか』，ブルーバックス，講談社
Seymour Lipschutz，『集合論』，マグロウヒル大学演習，オーム社
志賀浩二，『集合への30講』，朝倉書店
レイモンド・スマリヤン，『無限のパラドックス』，白揚社
ダグラス・ホフスタッター，『ゲーデル・エッシャー・バッハ』，白揚社
ジョージ・ガモフ，『宇宙=1,2,3…無限大』，G・ガモフ・コレクション 3，白揚社
ルディ・ラッカー，『無限と心』，現代数学社
ルディ・ラッカー，『ホワイトライト』，ハヤカワSF文庫，早川書店
Georg Cantor，『カントル 超限集合論』，現代数学の系譜 8，共立出版

良スレsage

「この文は偽である」は真ですか？それとも偽ですか？

ﾑｼﾞｭｰﾝ

というわけでタルスキの定義不可能性定理と
ゲーデルの不完全性定理の関係について教
えて下さい。

>>168
簡単に説明するね．まずどちらも対象言語とメタ言語を本質的に区別するという点では同じだ．
だけどタルスキの真理述語とゲーデルの証明可能述語では次の点で重要な違いがある：つまり，
真理述語は問題とされている対象言語の述語ではありえない．もしそんなものがあるとその言
語は矛盾する．だからタルスキのは真理述語の定義不可能性と言われる．だけどゲーデルの証
明可能述語は，言語がある程度強くなるとその中でちゃんと定義できる．そして最終的にそれは
事実対象言語の適格な式として存在してるけれど，その言語が矛盾してるのでない限り証明する
ことも反証することもできない式だということが示される．

哲オタの数学アレルギーは凄まじいものがあるね

入試制度のせいだと思われ

私も不完全なのか…??

ゲーデルはほとんどの問題を解いてしまった。

>>173

pp

itasugi

なんかねたない？

私は??