【ゲーデル】@哲学板

ゲーデル関連のスレがないんで作りました。（ｶﾞｲｼｭﾂならｽﾏｿ）

不完全性定理の証明で有名なゲーデル。
彼の業績を哲学板の人はどう捉えているのか？

【参考】
ttp://nadeshiko.sakura.ne.jp/~kaigakai/godel/
ttp://godel.m78.com/
ttp://www.time.com/time/time100/scientist/profile/godel.html

>>1
既出。不完全性定理は厨房が立てるスレッドとして有名らしい･･･

数学板＠不完全性定理
http://natto.2ch.net/math/kako/1007/10075/1007577490.html
哲学板＠ゲーデルの不完全性定理
http://mentai.2ch.net/philo/kako/1014/10140/1014017182.html

んじゃ不完全性定理は抜きにしてゲーデルの哲学を語ろう
不完全性定理を発掘後、トチ狂って数学会からつまはじきにされた天才
20世紀最高の数学者が「神の存在証明に成功した」と触れて回るのは同じ数学者として許せなかったのかねぇ

ゲーヅルかっこいい（＾＾）/

アメリカに移民する時に親友のアインシュタイン(年は全然違う)の口聞きで移民諮問を受けることに
審問官から民主主義に対する意見を聞かれた際(アメリカは共産主義者と非民主主義者には自由ではない)
「私は民主主義の方法に乗り、正当な民主主義の手続きを経て独裁を実行する方法を考えつきました」
と言いかけてアインシュタインにあわてて口を押さえられたという逸話がある
少しは自分の立場を考えぃ

新書そのまま

＞６
私も同じこと思った！

有名なエピソウドだにゃ。
お兄さんが居たらしいけど何をしてたんだろう？

出たよ

>>5
どうもゲーデルは宇宙の複雑性の説明には神の存在を認めざるを得ないと思ってたようです。

中学生の時に純粋理性批判を読んだんだっけ？
晩年には現象学を勉強していた。

ゲーデル　クソデル

ゲー出る

>>5
たしかノイマンも一緒について行ったんじゃなかったっけ？

僕の盟友みたいなものです、
ゲーデルは。

　　　　　　　　　　　　　　　ぅぉぇっぷ
　　　　　　　　　　 〃⌒ ヽフ
　　　　　　　　　　/　 　rノ
　　　　　　　　　Ο Ο＿）***

http://academy.2ch.net/test/read.cgi/philo/1003715006/635n

↑ここを見てちょっと気になったので質問です。
ゲーデルの不完全性定理の適用範囲は、
第1階の自然数論の公理系Z（？）と同じ記号を持つ第1階の公理系、でいいんでしたっけ……？
ふつうに高校で使っていた数学には当て嵌まるのでしょうか（厳密には公理化されてないけど）。

ゲーデルって「理性の限界」が明らかになった！とか騒がれるけど、
カントの理性批判を具体的に示しただけにも見えるんだけど。
論理学って、思いっ切り理性の「推論能力」にかかわってるし。

ども、はじめまして

哲学板＠ゲーデルの不完全性定理
http://mentai.2ch.net/philo/kako/1014/10140/1014017182.html
の335が面白かったので（＾＾ゞ）

＞･･･の初体験の相手のソープ嬢です。

ボク、ソープって行ったことないんだけど、いいですか？
こないだ、ソープ関係のページ見たんだけど、ソープ嬢で
「うほっ。ラブリー」ってコはほとんどいないですね。
どっちかっていうと、上に乗っかられると
「つ、つぶれる・・・」
といいたくなるような人が多いような（ｗ

＞なんていうのかしら、カントン…っていうんですか？
＞手で…その…皮を剥こうとしたら、なんかもの凄く痛がって

ボクも通常時は皮をかむっているけど、カントンではないですね。
ところで、最近どうも早いんですよ。それも単に早いというよりは
前立腺のあたりがムズムズっとして発射する感じ。
それに股ぐらのあたりに違和感があるんです。
これって前立腺炎なんですかね？

＞枯れかけたテッポウユリみたいになったアソコの先の皮が
＞うっすらと開いて、そこから緑がかった精液がドロリと出てきて…。

うわ、これ書いた人って、経験者ですかね？（笑）

精液が黄色や緑色になるって、明らかに性病でしょ。
鼻水が黄色くなったり青っ洟だったりするのと同じじゃないですか？
ちなみにボクはお恥ずかしいことに童貞なので（しかも、素人童貞とか
そういう奴でもない）そういう経験はないです。

あ、そういえばこないだ見た無修正ＤＶＤのコが
とあるソープにいるとか。たしかホムペもあったよ。
ただその店高いんだよな。ＤＶＤは安かったんだけど（ｗ

２週間の御無沙汰でした。

この間試しに一週間くらい禁オナニーしてみたんだよね。
そしたら、前立腺の調子はいいみたいなんだけど。
でも、久しぶりにかいたら、早いのは相変わらずだったなあ（笑）

pjjjj

こんなスレがあったのか、知らんかった。

「哲学板＠ゲーデルの不完全性定理」で
>柄谷も東浩紀も間違ってる。
と書いているが、具体的にどこが間違いかは指摘されていなかったのは残念。
東の「ゲーデル的決定不可能性・脱構築」は比喩としては
あながち間違ってるとは言えないかもしれないが
柄谷の「言語・数・貨幣」での用い方は明白に間違っている。
>あるテクストの完結的な意味（構造）を、
>同じテクストからそれと背反するような意味（構造）を
>引き出すことによって、「決定不可能性」に追い込み
完結的な意味とそれと背反するような意味の双方を
テクストから引き出せるということは、端的に「矛盾」であって
「決定不可能性」ではない。
「決定不可能性」とは、証明も否定の証明も導き出せないことであって
証明も否定の証明も共に導き出せる「矛盾」とは異なる。

どうも、柄谷は、「矛盾」と「決定不可能性」を取り違えたようである。
そして決定的な誤謬に至る。
「ディスコンストラクション」は「形式化されれば、ゲーデルの証明に帰着する」
しかし、柄谷によれば「ディコンストラクション」は「矛盾」を導き出すことであり
従って、体系の無矛盾性を否定するものであって
ゲーデルの不完全性定理とは何の関係もない。

付け加えておくと
柄谷はゲーデルの「不完全性定理」自体は
「言語・数・貨幣」における記述も見ても
一応、ちゃんと理解していると思われる。
ただ、それを「ディコンストラクション」と
容易に繋げてしまったところが問題。

ゲンツェンの無矛盾性の方の証明とどう関係あるんだっけ？

結局「数学は論理学に還元できない」ことを
証明した人でいいの？

>５
オレもそれ読んだ。

http://godel.m78.com/

>>24
ゲンツェンは超限帰納法を用いることで、無矛盾性を証明した。
で、超限帰納法とは？・・・と聞かれても、数学ドキュソの漏れが説明するよか
googleで調べた方がいいでしょう（ｗ

>>25
「還元できない」というより
有限な計算能力しかない人間には、数学的体系をすべて知り尽くすことはできない
とでも言ったらいいのかなあ。
哲学的な意味については、まだまだ今後の課題だと思う。

それから、ゲーデルの不完全性定理からは
自然数論のモデルが一意的に決まらないことが帰結されるから
柄谷の解釈も、間違いとは言えない。
ただ、モデル解釈については柄谷は何も触れていないし
ごく素朴に読む限りでは、どうなんかなあと思う。

>>24
確か、当該体系内では無矛盾性を証明できないが（不完全性定理）、
当該体系より広い体系で、ε_0までの超限帰納法により証明したのがゲンツェン……だったような。
この証明方法は「有限の立場」は固守していたので評価された。

>>28
> 有限な計算能力
計算能力が無限なら、ヒルベルトプランはOKなのか？といってみるテスト

ちょっと自己訂正
>ただ、モデル解釈については柄谷は何も触れていないし
「直観的なモデル」について、ちょこっと触れてるね。
正確には「モデルの一義性」について触れていないということ。

>>30
「計算能力が無限」というのがどういうことなのか明確には分からないから
なんとも言えないなあ。
少し哲学的に考えてみると、「有限な計算能力」というのは
カントの言うところの「理性の限界」と同じことなんじゃないかな。
理性（ratio）とは論証する能力、すなわち計算能力であり
計算によっては無限は（直接には）捉えられないと。
そんでもって、知性（intellectus）によって無限を捉えられるか
すなわち、知的直観で無限を捉えられるかという問題について
そんな能力は知性にはない（知的直観を認めない）
というのがカントおよびヒルベルトプランの考え方、といったところか。

>>31
ゲーデルとヒルベルトとカントはおんなじ結論に達したといってみるテスト

>>32
うーん、「おんなじ結論に達した」とは言えないかな。

けれど、例えば、「不完全性定理」は
自然数論を含む無矛盾な形式的体系において
その体系の公理系から独立した命題（決定不能命題）がいくらでも作れる
ということを示したんだけど、
このことは、カントの「数学はアプリオリな総合判断」という言明を
立証しているのじゃないか、ということが挙げられる。
これは、なかなか面白い事態を示していると思うのだけど
漏れの知る限り、このことを指摘している論は読んだことがないな。
まあ、ただの勉強不足ではあるのだけども（ｗ

>>33
どう立証してるか逝って味噌

>>34
いや、まあ、単純には立証できるもんでもないだろうけど
公理系から独立した命題があるということは
分析判断だけでは捉えられない命題があると言い換えられるんじゃないかな。

ところで、柄谷の考えは、
（形式化の極限の例としての）ゲーデルの「不完全性定理」が
形式体系における自己言及の禁止を破ることで
メタレベルとオブジェクトレベル、根拠づけるものと根拠づけられるもの
との固定的な関係を無効にして、形式体系の無-根拠性（不完全性）を示し
形式体系を自壊に追い込むことで、自己差異的な差異体系をあらわにする
というものであろう。

しかし、疑問が二点ある。
一つ目は、「不完全性定理」が自己言及の禁止を破ったと
単純に言えるかどうかということ。
自己言及の禁止を破ったのは
ゲーデル数や対角線定理などのテクニックの使用にあるのではないか。
「不完全性定理」自体は、そのテクニックによって作られた自己言及論理式の一つに
決定不能命題があることを示したにすぎないのではないか。

二つ目は、形式体系の無-根拠性（不完全性）を示すことが
形式体系の自壊に繋がるのかということ。
そもそも、形式体系は（論理的に）始めから無-根拠性（不完全性）であって
（ギリシア時代から無理数や無限論のパラドックスなど
数学の根拠性を脅かす問題に常にさらされてきたのではなかったか）
その無-根拠性の故に、
根拠を求めようとする欲動（理性の欲動）が生じたのではないだろうか。
（カントの超越論的仮象の問題とも繋がるだろう）
だから、形式体系の自壊というよりも
理性の欲動の挫折とでも言った方がいいのではないだろうか。

>ゲーデル数や対角線定理などのテクニックの使用にあるのではないか。
「対角線定理」→「対角化定理」

僕も参加させてくれ．
>>35
＞メタレベルとオブジェクトレベル、根拠づけるものと根拠づけられるもの
＞との固定的な関係を無効にして

これは誤りだと思う．ゲーデルの結果はむしろメタレベルと対象レベルの差異を
はっきりさせたのだと思う．無効にしたのとはまったく逆だと思う．

いやゲーデルは無効にしたんだよ
稲の間違い

>>39
どこがどう間違っているのか説明してもらわないと何を言いたいのかわからない．
ゲーデル自身がメタレベルと対象レベルの区別を無効にしました，なんて言わない
と思うけど．

稲も説明してなくない？

>>41
まず，ゲーデル化というのは対象言語とメタ言語の翻訳と見なせるけど，例えば
ある対象言語の一座の述語A(x)があってそのゲーデル数がnだったとする．じゃあ
A(n)と表記していいのかというとそうはならない．こういう式を表現するには
まず自然数nに対応した対象言語の項[n]をもってきてA([n])と書かないといけない．
こういう風にして自己言及文をつくるわけだから，一貫してメタ言語と対象言語の
区別はしている．

根拠づけるものがなければ、根拠づけられるものが決まらないって事で、
良いの？
クレタ人のパラドックスもそんな感じだと思うけど。

対象と切り離された無根拠な形式であるからこそはじめて尺度として有用性をもてるんだね｡ 定規に記された単位1ｾﾝﾁ2ｾﾝﾁというものもその「正しさ」を証明できなくとも皆が同じものを使ってれば有効なんだし｡

つまり、対象自身が自己を根拠づけられないからこそ、メタレベルが必要
ってことで良いのかな。
論理ガチガチで行くと、クレタ人のパラドックスは意味が通じないけど、
日常会話のレベルでは、それでも意味を通じさせてしまう何かが働くと。

どうなんかいな、柄谷は「言語・数・貨幣」において
自己言及的パラドックスを批評の根拠性に置くという
いささかアクロバットな離れ業でもって
あらゆる形式化の試みを一挙に批判してしまうことで
自らの批評の試みを自己完結させた
というような印象を受けたのだけれど。

そのときに、「否定性」ではなく「ゲーデルの証明」をもってくることで
一応、神秘主義的になるのを防いで
論理的な思考にとどまろうとはしているのだろうけれど
柄谷は、不完全性定理を自己言及的パラドックスとしか見ていないようだし
しかも、「決定不能性」という決定的な言葉自体が
曖昧でいったいどのような意味で使われているのか不明である
という点で破綻しているように思える。

>>46

不完全性定理って何？

>>47
「証明も否定の証明もできない論理式がある」てのと
「体系が無矛盾ならば自らの無矛盾性を示す論理式は証明できない」
ていうの二つある。
http://godel.m78.com/
あたりをどうぞ。

ていうか、なんか漏れのオナニースレになってるような気もしなくもない（苦笑
まあ、工房の頃に「言語・数・貨幣」を読んで衝撃受けて
以来、しばらく柄谷信者になってしまった経歴があるだけに
なんか、気になってしまうんだよねえ。
若気の至りというか、今読み返すと
どうも強迫観念の塊って感じで、よくこんなのに夢中になったなあ
と感慨に耽ると同時に、なんか過去の自分を清算したい気にもなるのであった。

そうそう、不完全性定理の証明に使われるテクニックのうち
「ゲーデル数」は有名でも
「帰納的関数」や「対角化定理」はあまり知られていないようだ。
実は漏れは「対角化定理」がいまいちよく分からんで
以前に数学板で質問したけど、結局答えてくれる人はいなかった。

でも、この「対角化定理」こそが
自己言及論理式の存在を示す重要な定理なんだよなあ。
「１変数xの論理式Ｆ(x)が任意に与えられたとき、
自由変数を含まない論理式Ａで　　Ａ⇔Ｆ(『Ａ』)---�@
が証明されるものが存在する」
んで、このＡが自己言及する論理式。
「第一不完全性定理」に出てくる、証明も否定もできない論理式は
�@から簡単に作れる。

要は、「論理式の集合Ｋからゲーデル数xの論理式が証明される」
という一変数ｘの論理式　Ｂew.k(x)を作って、その否定を�@のＦ(x)に代入すると
Ａ⇔¬Ｂew.k(『Ａ』)---�A
んで、ＡはＫの選び方によって異なるのでＵ.kと表すと
Ｕ.k⇔¬Ｂew.k(『Ｕ.k』)---�B
このＵ.kが当の証明も否定もできない論理式。
で、その内容は¬Ｂew.k(『Ｕ.k』)すなわち、「自分を証明することはできない」
つまり「自分を証明できない」は証明も否定もできない
というのが「第一不完全性定理」の内容。

>>49>>50
その程度のことはだれでも知ってるって＾＾

>>51
それだったら、対角化定理について教えておくれ。
証明の大筋は対角線論法を用いるようなんだけれど
論理式に論理式を対応させる任意の一意対応Φにたいして
Φ(A)=A
となる論理式Aが存在するってのは
ブラウアーの不動点定理と同じ構造なんじゃないかって思ったんだけど
そこんとこ、どうよ？
あと、対角線論法を用いるということは
実数体を含んだ体系では、対角線論法が使えないことになるけど
このことと、実数体では完全性が証明されることは関係あるの？

対角化定理って不動点定理そのもの．というか一種

実数体では完全性が証明されるって，算術の無矛盾性のことかな？
要は超限帰納法っている数学的帰納法よりもつよい帰納法を使うから無矛盾性が
証明できるの．だから自分自身の内部では証明できないということとは矛盾しない．

柄谷のｹﾞｰﾃﾞﾙ問題はいわく「輝かしい敗北の記録」（by浅田）｡つまりその試みの破綻によって逆に背理法的に証明してしまうものがあった｡形式性に還元できない問題も存在するのだと｡そして「他者」が現れた｡ｹﾞｰﾃﾞﾙからｳｨﾄｹﾞﾝｼｭﾀｲﾝへの転回｡

文芸評論家にしてはよくやったってこと？

>>53
サンクス

>対角化定理って不動点定理そのもの．というか一種
ふうん、やっぱしそうだったんか。
漏れは数学ドキュソだから今まで気が付かなかったんだけど
自由変数をもつ論理式を関数と見なすと
論理式が論理式族を論理式族に写すというのは
関数が関数族を関数族に写すのと全く同型なんだね。
ということは、チャーチのラムダ計算と関連があるのは感覚的にすぐにわかる。
自己言及性に拘った見方をすると、なんだか眩暈がしそうでクラクラするけど（ｗ
ちょっと見方を変えれば、数学の構造の面白さが垣間見えるよなあ。

あと、超限帰納法を使った無矛盾性の証明の概要を
よかったら、教えて下さい。

>>55
文芸批評家兼マルキストとして、言語や価値形態論を突き詰めていった果てが
「言語・数・貨幣」なんだろうけど
素手で数学畑にまで殴りこむ無謀さは、柄谷ならしめるところ（ｗ
ま、そういう無謀さが好きだったりするんだけれどね。
形式化の極限にゲーデルの不完全性定理を見るのは
どう考えても無理があると思うけど
無謀な思考のおりなす冒険譚として読めば今でも面白いんじゃないかな。

ラムダ計算では、数は関数の冪として定義されるんだけど
これって、ドゥルーズの「力＝累乗」(puissance)の概念と
関連があるのかもね。
意外なところで、意外な発見をして面白いな。

数学屋の人に
「いつまでも、ゲーデルなんて化石みたいのやってんじゃねえ。
だから哲学やってるヤシは馬鹿なんだ。
前原昭二なんか読んでばかりいないで
田中一之の『数の体系と超準モデル』でも読んで、出直して来い」
と言われました。

ゲーデルの不完全性定理は、もう時代遅れなんでしょうか。

>>58
数学板＠不完全性定理では哲学板は馬鹿にされてた・・・
でも、数学屋の議論は正確を旨とするから、参考にはなる。
田中の本のことは漏れも聞いたことある。
今度読んでみようかな。

しかし、このスレ人気ないなあ（ｗ

つーか、以前のゲーデルスレで誰かが書いてたけど、
不完全性定理って、哲学的に高度な事を言ってる訳じゃ
ないからじゃないの？
そりゃ数学的に理解しようとすると、難しいのかも知れないけどさ。

＞ゲーデルの結果はむしろメタレベルと対象レベルの差異を
＞はっきりさせたのだと思う

結局こういう事でしょ。当たり前っちゃあ当たり前というか。

>>60
>不完全性定理って、哲学的に高度な事を言ってる訳じゃ
>ないからじゃないの？
>そりゃ数学的に理解しようとすると、難しいのかも知れないけどさ。
そうかなあ、漏れは逆だと思う。
不完全性定理自体を数学的に理解するのは、比較的易しい。
ゲーデルの論文も、漏れのような数学ドキュソが読んでも理解できる。
（まあ、完全に正確に理解してるかどうか分からんが）
しかし、数学的な構造の中で不完全性定理がもつ意味を
哲学的に理解するのは難しいと思う。

例えば、ゲーデルの証明は一階の論理における証明だが
これが二階の論理における構造とどう関ってくるかなどを
哲学的に考察するのは、一筋縄ではいかないと思う。
（不完全性定理によって自然数論の非標準モデルの存在が示されるが
これとクリプキのプラス・クワスの問題との関連性など考えると
コミュニケーションのレベルでの決定不能性とも繋がってるのかもしれない）
「メタレベルと対象レベルの差異」といったような
単純な概念では捉えきれないのは明らかだろう。

たしかに数学専門にやっている人には
ごく単純で素朴なプラトン主義者が多いのは実情だけれども
だからといって、数学そのものの構造のもつ複雑さを
単純化して捉えてしまうのは、どうかと思う。

>>61
＞例えば、ゲーデルの証明は一階の論理における証明だが
＞これが二階の論理における構造とどう関ってくるかなどを
＞哲学的に考察するのは、一筋縄ではいかないと思う。

単純な帰結として，二階の論理は不完全になるんだよ．つまり，真である文集合と証明可能な
文集合が一致しないという意味での不完全．

＞（不完全性定理によって自然数論の非標準モデルの存在が示されるが
＞これとクリプキのプラス・クワスの問題との関連性など考えると
＞コミュニケーションのレベルでの決定不能性とも繋がってるのかもしれない）
＞「メタレベルと対象レベルの差異」といったような
＞単純な概念では捉えきれないのは明らかだろう。

２２は途中までまともなことを言ってるのに，突然議論が飛躍してしまう．そもそもコミュニケーション
のレベルと「メタレベルと対象レベルの差異」がどうつながってるのかわからない．

＞たしかに数学専門にやっている人には
＞ごく単純で素朴なプラトン主義者が多いのは実情だけれども

これはどこで仕入れた情報なの＾＾？　

ああやっぱり稲さんがつっこんでしまった

>>62
>単純な帰結として，二階の論理は不完全になるんだよ．
>つまり，真である文集合と証明可能な文集合が一致しないという意味での不完全．
うん、それは分かってます。
漏れが考えてたのは、二階論理において超限帰納法を用いると
無矛盾性が証明される体系（実数の構造など）があるということ。
まあ、漏れはまだ二階論理については、よく知らないから
あやふやではあるけど・・・

というわけで、よければ、二階論理について、いろいろ教えて下さい。
あと超準モデルや超限帰納法を用いた無矛盾性の証明の概要なども<(_ _)>
いやー、実を言うと、田中の本をさっそく見たんですけど
難しくて・・・
「学部」上級用の教科書らしいんですが
数学ドキュソの漏れにとっては、あまりに記述が圧縮されてて
理解するのが大変です。
でも、やっぱ、この程度は読んどかないと、あきまへんかねえ。

>そもそもコミュニケーションのレベルと
>「メタレベルと対象レベルの差異」がどうつながってるのかわからない．
？？
「メタレベルと対象レベルの差異」の問題にすべて還元できないんじゃないか
ってことの例示として
クリプキの示したようなコミュニケーションの問題があるということを
言いたかったんであって
両者がつながっているとは言ってないはずなんですけど・・・

>これはどこで仕入れた情報なの＾＾？　
数学科のダチなどから、よく聞いてますけど。

対角化定理は不動点定理の一種であるということは
スマリヤンが何度も強調してたんですね。
知らなかったです。
逝ってきます・・・

>>57
スレの流れとは関係ないが
http://academy.2ch.net/test/read.cgi/philo/1027100953/60-n

ちんこ統計調査中
ぜひとも協力してください！！
今のところ
右：56；左：172；その他：28
計254ちんこ
右：22％；左67％；その他：11％
【緊急】お前らのちんこは右寄り？左寄り？【報告】
http://natto.2ch.net/test/read.cgi/denpa/1025699638/

>>66
サンクス
「差異と反復」は、読み返してみよう。
そういえば、ヴィトも論考で
数は操作の冪だとか書いてなかったけな。

>>59
化石とか言う奴は厨房だと思われ。絶対に勉強しなきゃいけない
基本中の基本の定理だからな。

だが、まあ、数学やからすれば、ピタゴラスの定理で議論してるような
印象を持つことは否定できないなあ。

>>69
数学基礎論は半世紀程の間に
爆発的に進展してるみたいだからねえ。
二階算術やら逆数学やら、かなり面白そうな展開を示しているけど
文系の者にとっては、フォローするのは、むちゃ大変そう・・・

しかし、不思議に思うのが
素粒子論では、超弦理論やＭ理論なんかの啓蒙書は結構でてるのに
数学基礎論では、啓蒙書はそろいもそろって不完全性定理どまりなこと。
うーん、分析哲学屋さんが、サービス精神発揮して
何か書いてくれないものだろうか・・・

素粒子の啓蒙書だって別に分析哲学者が書いてるわけじゃないでしょ。
つうか田中先生の本2冊じゃだめなの？

物理方面は、専門教育受けてる科学ジャーナリストとか沢山いるけど
数学は、そういう人は少ないんじゃないかな。
分析哲学者に期待するのは、哲学的な意味や
全体的な展望などを解説してくれること。
田中の本は、あくまで数学科や情報系の学生向けの「教科書」だからね。
まあ、でも濃い内容で、勉強やりがいはありそう。

そうそう、グレッグ・イーガンは
セルオートマタや量子論のアイデア使ったＳＦで人気あるけど
基礎論の最近の成果とか使ったＳＦ書いてくれないかなあ。
「ルミナス」は面白かったけど
もっと過激なヤシキボンヌ

>>72
ラッカーはだめですか？

哲学者が書く本ってヤらしくない？
ﾈﾁﾈﾁｳｼﾞｳｼﾞしてるというか、怨念がこもっているというか･･･

>>74
おまえの書き込みみたいに？

>>73
漏れは典型的なハードＳＦファンなんで
ラッカーは、ちょっと食わず嫌いをしてた。
でも、現在『ハッカーと蟻』を読書中。
『思考の道具箱』は面白そうだね。今度読んでみよう。
数学や情報科学の専門家がＳＦ書くというのは
やっぱしアメリカの懐の深さを感じるなあ。
まあ、森毅は好きだけどね。

ところで、基礎論の（ネット）有名人といえば
山口人生おいて他になし（ｗ
漏れが前に読んだことある『チューリング・マン』の
共同翻訳者だったというから、驚いた。
数学板でも、かなーり弄ばれてるね（ｗ
うん、でもなんか可愛そうでもあるなあ。
研究者として社会復帰するのは無理だろうけど
物書きとして復帰して、基礎論ネタで面白いの書いてほしいと個人的には思ってるが。

決定不全な体系は、どれだけ列挙されてるの？列挙して囲い込めば
いいではないかい。違う？

ホフスタッターの『ゲーデル・エッシャー・バッハ』を購入。
読みやすいけど長すぎるぞｺﾞﾙｧ!

>>76
＞ ところで、基礎論の（ネット）有名人といえば

別にネットでなくても有名人だ。何でもネットのが先と思うべからず。

>>77
あくまで素人考えだけど
「決定不全な体系を囲い込む」というように、純粋化（？）を目指すというよりも
例えば
二階算術における無矛盾なある体系でどこまで数学の諸定理が導出できるだろうか
というような
手持ちの体系でどこまでうまくやれるかという
プラグマチィックな考え方をしてるように思えるな。
で、「数学の定理の証明にどれだけの公理が必要か」と考える逆数学の発送は
特にそういうプラグマチックな思想を体現してるように思える。
このような状況を、ゲーデルが生きていたら、なんと思うだろうかねえ。

>>78
『ゲーデル・エッシャー・バッハ』は恥ずかしながら読んだことない。
面倒くさがり屋の漏れは、長いのは苦手（ｗ
実は『ミルプラトー』や『否定弁証法』『論理学研究』なんかの
巨大本（？）は最後までキッチリ読み通したことがないからなあ。
その点で言うと、分析系は漏れの性格にあってるかもしれないな（ｗ

>>79
いやー、漏れはネットで初めて知ったもので（汗
やっぱし、前々から業界では有名だったんすかねえ。

ふと、
哲学板＠ゲーデルの不完全性定理
http://mentai.2ch.net/philo/kako/1014/10140/1014017182.html
を読んでみたけど
はぁひゃー、すんごい泥仕合だなあ・・・
いやはや、漏れがこのスレで絡まれなかったのは、幸運か。

マッタリ進行もいいけど、それだけじゃつまらないから
とりあえず、スマリヤンと田中の本でも読んでいくことにしょうかな。
『リーディングス　数学の哲学　ゲーデル以降』
に収録されてる諸論文について議論したいところではあるが
なんか怖そうな人たちに絡まれてボロボロにされそうだから
後回しにしよう。

漏れが書いたレス読み返してみると
ツッコまれそうなとこが、かなーりあるなあ・・・
うー怖い怖い

あらかじめ、漏れは哲学は趣味でやってるだけで
しかも基礎論をちゃんと勉強し始めて、まだ１ヶ月も経ってないと
（数理論理学は工房の頃に遊びで齧ってはいたけど
そもそも東の「ゲーデル的脱構築」なるタームに疑問をもったのが
基礎論をちゃんと学んでみる気になったきっかけだったんだし）
自己弁護をしとこう（ｗ

図書館で「証明論入門」（竹内外史＆八杉満利子）をかりてきた。
この本の定評はどうなのでしょう？
（区立の図書館なのでこんなものしかない。大学生がうらやましいぞ）

あんたがあのスレの基地害に絡まれることはないと思うが

>>84＞>>82=22

>>84
もうでてこないだろ。当時結構あった基礎論や論理スレすべてに出没して、
自分好みのスレ立ててたけどいまや影も形もないからねえ（笑）

まっとうになったか、入院したのかのどちらかであろうよ。

入院してくれてたらどれだけいいか

誰か>>83に答えてやれよ。
古典的だけど読むに値するいい本、って新しく出てる教科書でも
すすめてあるくらいじゃない？

>80 77

アラン・チューリングのやったことだね♪数学史を参考にしてね。

>>89
数学史にも多少興味があります。
近代以降の数学の展開を概観するには、どんな本がいいでしょうか？

スマリヤンの『ゲーデルの不完全性定理』を
読んでいこうと思うんだけど
記述があまりに、あっさりしてるんで
逆に内容の理解は、ちょっと大変そう。
訳書の記述を一部言い換えたりして、漏れの稚拙なコメントつけたけど
間違ったところがあれば、教えて下さい。
とりあえず、第１章の最初の定理ＧＴの直前まで。

体系Ｌ、証明可能な文の集合Ｐ、反証可能な文の集合Ｒ、真である文の集合Ｔ

＝＝＝＝＝前提＝＝＝＝＝

文Ｈ(n)が真であるとき、述語Ｈは数nに対して「真である」
nがＨを「充足する」という。
ある数集合Ａに対して
Ｈ(n)∈Ｔ⇔n∈Ａ・・・�@
が成立するとき、ＨはＡを言及する。

Def　集合Ａが体系Ｌのある述語によって言及されているとき
ＡはＬにおいて「言及可能」と呼ばれる。

Def　体系Ｌのすべての証明可能な文が真であり、すべての反証可能な文が偽であるとき
Ｌを「正確である」という。

ゲーデル数nの式をＥnとおく。
式Ｅn(n)はＥnの「対角式」と呼ばれる。
任意の数nに対して、対角式Ｅn(n)のゲーデル数をd(n)（対角関数）とおく。
任意の数集合Ａに対して、d(n)∈Ａをみたす全ての数nの集合をＡ#とおく。
任意の数nに対して
n∈Ａ#⇔d(n)∈Ａ・・・�A
すべての証明可能な文のゲーデル数の集合をＰとおく。
数集合Ａの自然数全体の集合Ｎにたいする補集合をＡ~であらわす。

■■コメント■■
�@において、Ｈ(n)∈Ｔを満たす全てのＨ(n)の集合をＴＨとすると
Ｈ：Ａ→ＴＨ　という写像関係を見出せる。
�Aにおいて、d：Ａ#→Ａ　という写像関係を見出せる。

「正確である」とは、(Ｐ⊆Ｔ)∧(Ｒ⊆¬Ｔ)と表せる。
このことは、真である文と証明可能な文が
（あるいは、偽である文と反証可能な文が）
かならずしも一致しないことを意味する。
すなわち、体系が正確であるときに
真であるにもかかわらず証明可能でない文があるための条件を調べることが
重要になってくる。

>>92
機種依存文字はやめれ
あと(1)が何を言っているかちょっと判然としない

がんがれ

結局何を読んでおくべきなんでしょう？

老婆心ながら言うが、すまりやんのあの本では序章のパズルが極めて重要なので、
もしもあれをすっとばして１章からやろうって言うのならば、仕切りなおして
序章からきちんと読んだほうがいい。

>>93
すんません、今後きーつけます（汗
コメントはちょっと不正確ですね。
修正します。
数学はドキュンなんで、不正確、間違いなど多々あると思いますが
もしあれば、どしどし指摘して下さい。

>>95
ゲーデル入門者は、まず
前原昭二の『数学基礎論入門』と横瀬健・横田一正の『ゲーデルの世界』が
よろしいのではと思います。
前原の本は命題論理・述語論理・自然数論など
不完全性定理を学ぶ上で前提となる知識を易しく書いています。
『ゲーデルの世界』は
集合論とパラドックスの関係、証明の概要などが書かれています。
付録でゲーデルの論文が掲載されています。

92をちょっと修正

(1)において、すべてのnについて、Ｈ(n)∈Ｔを満たすＨ(n)の集合をＴＨ
Ｈ(n)∈¬Ｔを満たすＨ(n)の集合をＦＨとすると
Ｈ：Ａ→ＴＨ　かつ　Ａ~→ＦＨ
という写像関係を見出せる。
(2)において
d：Ａ#→Ａ　かつ　Ａ#~→Ａ~
という写像関係を見出せる。

◆定理ＧＴ◆
体系Ｌが正確であり、集合Ｐ#~がＬで言及可能であるとき、
真であるにもかかわらず、Ｌで証明可能でない文が存在する。

[証明]
体系Ｌにおいて述語Ｈが集合Ｐ#~を言及することから、
任意の数nについて
Ｈ(n)が真である⇔n∈Ｐ#~・・・(3)
(3)は任意の数nについて成り立つため
Ｈのゲーデル数hをnに代入しても成り立つ。（対角化）
Ｈ(h)が真である⇔h∈Ｐ#~・・・(4)
ところで(2)より
h∈Ｐ#~⇔d(h)∈Ｐ~・・・(5)
ここでd(h)はＨ(h)のゲーデル数であるから
(5)はＨ(h)はＬで証明可能でないことを示す。従って
Ｈ(h)が真である⇔Ｈ(h)はＬで証明可能でない・・・(6)
仮定よりＬは正確であが、(6)の対偶
Ｈ(h)は真でない⇔Ｈ(h)はＬで証明可能である
は仮定に反する。従って
真であるにもかかわらず、Ｌで証明可能でない文Ｈ(h)が存在する

■■コメント■■
体系Ｌが正確であるということは
証明可能/反証可能と真/偽の集合が必ずしも一致しないが
真∧反証可能あるいは偽∧証明可能な文はないことを示す。
このことは、証明でも分かるように
第一不完全性定理の対偶が成り立たないことを示す

(3)の対偶
Ｈ(n)が真でない⇔n∈Ｐ#
は成り立つ。すなわち
証明可能な文のゲーデル数によって、充足されない場合もあれば
証明可能でない文のゲーデル数によって、充足される場合もあるということ。
ところで、(4)の対偶
Ｈ(h)が真でない⇔h∈Ｐ#
は体系Ｌが正確であるという仮定に反し、成り立たない。
つまり、Ｈ(h)は必ず真になるのである。

「集合Ｐ#~がＬで言及可能であるとき」という仮定は
「真であるにもかかわらず、Ｌで証明可能でない文が存在する」
すなわちゲーデルの第一不完全性定理が成り立つ条件である。
この仮定の意味は明らかではないが
第２章において、以下の３つの条件に応じて検証される。
Ｇ1:体系Ｌで言及可能なすべての集合Ａに対して、集合Ａ#はＬで言及可能である
Ｇ2:体系Ｌで言及可能なすべての集合Ａに対して、集合Ａ~はＬで言及可能である
Ｇ3:集合Ｐは体系Ｌで言及可能である。

条件Ｇ1・Ｇ2が成り立つならば
体系Ｌで言及可能なすべての集合Ａに対して集合Ａ#~がＬで言及可能なことが示される
このとき、集合Ｐが体系Ｌで言及可能ならば、Ｐ#~もＬで言及可能である。

100を修正
>証明可能な文のゲーデル数によって
→証明可能な対角式の述語のゲーデル数によって

>証明可能でない文のゲーデル数によって
→証明可能でない対角式の述語のゲーデル数に

>>96
やはり、序章から読んだ方がよいでしょうか。
「あ、そう」という程度で軽く読み流したもので（汗
とりあえず、１章を終わらせてから
序章に取り掛かることにします。

>>96
すまりやんのあの本」ってなんですか？正確な書名をお願いいたします。

>>97
前原昭二の『数学基礎論入門』と横瀬健・横田一正の『ゲーデルの世界』

これ以外に読むべきものはありますか？

>>103
＞すまりやんのあの本」ってなんですか？正確な書名をお願いいたします。
>>90 をみれ。

>>91
＞証明可能な文の集合Ｐ
＞すべての証明可能な文のゲーデル数の集合をＰとおく。

異なる対象を同じ記号で表すのは、混乱の元ですよ。
>>92のＰは前者で、>>99-100のＰは後者ですね。
文の集合とゲーデル数の集合の違いは、特に意識して書き分けないと
初学者はわけ分からなくなると思います。

序文はとりあえず飛ばして次いきませんか？

>>103
いやー、漏れも数学基礎論を学びはじめたばかりだから
どんな本がいいか、よく知らないんすよ。

>>105
文の集合はＰ$のように、後ろに$を付けることにします。

【今までの全般的な訂正】
Ｐ#~、Ａ#~は全てＰ~#、Ａ~#の誤りです。

[ゲーデル文の定義]
数集合Ａに対して、
文Ｅnが真である⇔文Ｅnのゲーデル数がＡの要素である・・・(7)
（文Ｅnが真でない⇔文Ｅnのゲーデル数がＡの要素でない）
のとき、文ＥnはＡのゲーデル文と呼ぶ。
(7)は
Ｅn∈Ｔ$⇔n∈Ａ・・・(8)
と表せる。

■■コメント■■
集合Ａのゲーデル文は「この文のゲーデル数はＡの要素である」
ということを意味していると考えられる。
実際、文が真ならば、その文のゲーデル数はＡの要素であり
文が偽ならば、そのゲーデル数はＡの要素でない。
このように、ゲーデル文は自己言及する文である。

◆補助定理Ｄ[対角化補助定理]◆
(a)任意の集合Ａに対して、
集合Ａ#が体系Ｌで言及可能であれば、Ａのゲーデル文が存在する。
(b)体系Ｌが条件Ｇ1をみたすならば、
Ｌで言及可能なすべての集合Ａに対して、Ａのゲーデル文が存在する。

[証明]
(a)体系Ｌにおいて、集合Ａ#を言及する述語をＨ、その述語のゲーデル数をhとおく。
ここでd(h)はＨ(h)のゲーデル数である。
任意の数nに対して
Ｈ(n)は真である⇔n∈Ａ#・・・(9)
が成り立つから、nにhを代入した
Ｈ(h)は真である⇔h∈Ａ#・・・(10)
も成り立つ。ここで、
h∈Ａ#⇔d(h)∈Ａ・・・(11)
より
Ｈ(h)は真である⇔d(h)∈Ａ・・・(12)
従って、Ａのゲーデル文Ｈ(h)が存在する。

(b)上記の証明より明らかである。

■■コメント■■
補助定理Ｄを用いれば、定理ＧＴの証明が容易になる。
集合Ｐ~#がＬで言及可能なとき、補助定理Ｄ(a)より
集合Ｐ~のゲーデル文Ｇが存在する。
ゲーデル文Ｇは
「この文のゲーデル数は集合Ｐ~の要素である」すなわち
「この文は証明可能でない」という意味内容である。

補助定理Ｄ(b)は、条件Ｇ1が成り立つ体系Ｌでは
全ての述語は自己言及する文を作れる、
すなわち、全ての述語は対角化可能であることを意味する。

◆定理Ｔ（タルスキーの定理の抽象形式）◆
(a)集合Ｔ~#は体系Ｌで言及可能でない。
(b)条件Ｇ1が成立するとき、集合Ｔ~は体系Ｌで言及可能でない。
(c)条件Ｇ1と条件Ｇ2が成立するとき、集合Ｔは体系Ｌで言及可能でない。

[証明]
前提として、集合Ｔ~のゲーデル文は存在しないことに注意。
存在すると仮定すると、真でありかつ真でない文が存在することになり、矛盾。

(a)集合Ｔ~#が体系Ｌで言及可能であれば、補助定理Ｄ(a)より
集合Ｔ~のゲーデル文が存在することになり、矛盾。

(b)集合Ｔ~が体系Ｌで言及可能であると仮定すると、条件Ｇ1より
集合Ｔ~#も言及可能となるが、これは(a)に反する。

(c)集合Ｔが体系Ｌで言及可能であると仮定すると、条件Ｇ2より
集合Ｔ~も言及可能となるが、条件Ｇ1より定理Ｔ(b)も成り立ち、矛盾。

■■コメント■■
定理Ｔ(c)は
「十分に強い体系において、体系の真理概念はその体系内では定義できない」
と表現されることがあるが
条件Ｇ1,Ｇ2は「十分に強い」という表現を十分に満たしている。
ちなみに、定理Ｔ(b)は、条件Ｇ1だけでも
偽概念を体系内では定義できないことを意味する。
すなわち、全ての述語が自己言及する文を作れるとき
偽概念を体系内で定義できないし、更に条件Ｇ2が加わると
真概念も体系内で定義できなくなる。

ここで、「言及可能」について考察する。
Ｈ(n)∈Ｔ$⇔n∈Ａ・・・(1)
は、内包の公理
∃y∀x[x∈y⇔Ｆ(x)]・・・(13)
と、関連がある。
内包の公理は
「ある条件Ｆ(x)が与えられたとき、その条件によって一つの概念yが規定される」
ということを意味している。
一方、言及可能の定義とは
「ある概念Ａが与えられたとき、その概念を言及する述語Ｈが存在するならば
その概念Ａは言及可能である」
ということを意味している。
これらのことから明らかなのは
「任意の条件＝述語に対応する概念は存在するが、その逆は必ずしも成り立たない」
ということである。
そして、定理Ｄ(c)で示されるように、
対応するような条件＝述語が存在しないような概念の一つが「真理概念」である。

関係ないがスマリヤンのパズルの本は面白かった。高かったけど。
文庫にしれ。

>>106
序文が重要だって言ってるのに。あのパズルが整理する条件を数学的に
精緻化するという構成の教科書なんだから。たしか。

いや、今手元に本がないんで記憶で言ってるけど。

ふう、ようやく１章が終わり。
問題も何問かあるけど、解いてたら大変そうだし
とりあえず、早く全部読み終わりたいんで、省略。

しかし、このスレ読んでる人っているのかなあ。
漏れが書いたコメントは、もしかしたら間違ってるかもしれないんで
そこんとこ、ヨロシク。

[定義]
体系Ｌにおいて、証明可能かつ反証可能である文が存在しないとき
（集合Ｐ$と集合Ｒ$が互いに素なとき）
Ｌは「無矛盾」と呼ばれ、それ以外のときＬは「矛盾」とよばれる。
（体系Ｌが正確ならば無矛盾であるが、逆は必ずしも成り立たない）

文Ｘが体系Ｌにおいて証明可能または反証可能であるとき、
Ｘは「決定可能」と呼ばれ、それ以外のときＸは「決定不可能」と呼ばれる。

体系Ｌにおいて、すべての文が決定可能であるとき、
Ｌは「完全」と呼ばれ、それ以外のとき「不完全」と呼ばれる。

◆定理１◆
体系Ｌが正確であり、集合Ｐ~#がＬで言及可能であるとき、Ｌは不完全である。

[証明]
仮定より定理ＧＴが成り立つから、真であるがＬで証明可能でない文Ｇが存在する。
Ｌは正確だから、文ＧはＬにおいて反証可能でない。
従って、Ｌにおいて決定不可能な文Ｌが存在し、Ｌは不完全である。

■■コメント■■
定理１はゲーデルの第一不完全性定理に相当する。
「正確」であるという仮定は、
ゲーデルの証明では「ω無矛盾」という弱い仮定に置き換えられる。
また「集合Ｐ~#がＬで言及可能」という仮定は、
より一般的な「表現可能」という仮定に置き換えられる。

Def 反証可能な文のゲーデル数の集合をＲとする。

◆定理１'(定理１の双対定理）◆
体系Ｌが正確であり、集合Ｒ#がＬで言及可能であるとき、Ｌは不完全である。
特に、体系Ｌが正確であり、述語Ｋが集合Ｒ#を言及するとき
その対角式Ｋ(k)はＬで決定不可能である。
（ｋはＫのゲーデル数）

[証明]
集合Ｒ#を言及する述語をＫとすると、
補助定理Ｄ(a)より、集合Ｒのゲーデル文Ｋ(k)が存在する。
よって
Ｋ(k)は真である⇔Ｋ(k)は反証可能である・・・(14)
または、
Ｋ(k)は真でない⇔Ｋ(k)は反証可能でない・・・(15)
ここで、体系Ｌは正確であるから(14)は成り立たたない。
従って、真でなく反証可能でもない文Ｋ(k)が存在する。
ところで、Ｌは正確であるから、真でない文Ｋ(k)は証明可能ではない。
従って、文Ｋ(k)はＬにおいて決定不可能であり、Ｌは不完全である。

■■コメント■■
(14)と(15)は対偶であるが、Ｌが正確という仮定から
一方の(15)が成り立たないことになる。
「真でなく反証可能でもない文Ｋ(k)が存在する」というのは
定理ＧＴの双対定理にあたる。


Ｇ1:体系Ｌで言及可能なすべての集合Ａに対して、集合Ａ#がＬで言及可能である。
Ｇ3':集合Ｒは体系Ｌで言及可能である。
という二つの条件を仮定するとき、体系Ｌにおいて集合Ｒ#は言及可能となる。
このとき、正確な体系Ｌは定理１'により不完全である。

119の訂正
>一方の(15)が成り立たないことになる。
(15)→(14)

>>115
＞問題も何問かあるけど、解いてたら大変そうだし

誰か手伝ってくれるからといてみなよ。その方が面白いし、
問題の中に重要な話が出てくることもあるし。

>121
とりあえず、問題を３問だけ解いて見ました。
いやー、数学の問題解くのって、入試の時以来だから
案外手間取ってしまった（汗
まあ、せめてヒントくらい載ってれば
全部解いてみようという気になるかもしれんけど
重要そうな問題だけは、解いてみようかな。

それから、114さんには悪いけど
序文のパズルは、それほど面白くはないし、飛ばしてしまおう。

１章では、抽象的な体系がある性質をもてば
不完全性が生じることを示したわけで
以降の章で、具体的な数学的体系について
１章で示された性質をもつことが論じられてます。

★問題１★
次の二つの条件をみたす正確な体系Ｌを仮定したとき
Ｌは不完全であることを証明せよ。
１：集合Ｐ#はＬで言及可能である。
２：任意の述語Ｈに対して、次のような述語Ｈ'が存在する
「すべての数nに対して、文Ｈ(n)がＬで反証可能であるときに限って、文Ｈ'(n)がＬで証明可能である」


[解答]
条件１より、Ｐ#を言及する述語をＨaとすると、任意の数nで
Ｈa(n)は真である⇔n∈Ｐ#・・・(16)
が成り立つ。
条件２より、述語Ｈaについて、任意の数nで
Ｈa(n)は反証可能である⇔Ｈb(n)は証明可能である・・・(17)
が成り立つような述語Ｈbが存在する。
述語Ｈbのゲーデル数をhbとし、文Ｈb(hb)のゲーデル数をd(hb)とする。
(16)において、nにhbを代入すると
Ｈa(hb)は真である⇔hb∈Ｐ#⇔d(hb)∈Ｐ⇔Ｈb(hb)は証明可能である。・・・(18)
(17)において、nにhbを代入すると
Ｈa(hb)は反証可能である⇔Ｈb(hb)は証明可能である・・・(19)
(18)と(19)より
Ｈa(hb)は真である⇔Ｈa(hb)は反証可能である
よって、Ｈa(hb)は、真かつ反証可能、または、偽かつ反証可能でない、かである。
Ｌが正確であることから、偽かつ反証可能でない文Ｈa(hb)が存在する。
また、文Ｈa(hb)は偽であるため証明可能ではない。
よってＬには決定不能な文Ｈa(hb)が存在するから、不完全である。

★問題２★
全ての数nに対して、n∈Ａであるときに限って文Ｈ(n)が体系Ｌで証明可能であるとき、述語Ｈは集合Ａを「表現する」という。
体系Ｌが無矛盾であり、集合Ｒ#がＬで表現可能であれば、Ｌが不完全であることを証明せよ。


[解答]
集合Ｒ#を表現する述語をＨとすると、任意の数nに対して
Ｈ(n)は証明可能である⇔n∈Ｒ#・・・(20)
が成り立つ。述語Ｈのゲーデル数をh、文Ｈ(h)のゲーデル数をd(h)とする。
(20)において、nにhを代入すると
Ｈ(h)は証明可能である⇔h∈Ｒ#・・・(21)
ここで
h∈Ｒ#⇔d(h)∈Ｒ⇔Ｈ(h)は反証可能である・・・(22)
より、(21)と(22)から
Ｈ(h)は証明可能である⇔Ｈ(h)は反証可能である
よって、Ｈ(h)は、証明可能かつ反証可能、または、証明可能でなく反証可能でもない
のいずれかである。
Ｌは無矛盾であるから、文Ｈ(h)は証明可能でなく反証可能でもない。
従って、Ｌには決定不可能な文Ｈが存在し、不完全である。

★問題３★
集合Ｒ#の任意の超集合が、集合Ｐ#と互いに素であり、体系Ｌで表現可能であれば、Ｌが不完全であるとこを証明せよ。
（集合Ａが集合Ｂの部分集合であるとき、ＢはＡの超集合と呼ばれる）


[解答]
集合Ｒ#の任意の超集合をＲＳとする。
集合ＲＳを表現する述語をＨとすると、任意の数nに対して
Ｈ(n)は証明可能である⇔n∈ＲＳ・・・(23)
が成り立つ。述語Ｈのゲーデル数をh、文Ｈ(h)のゲーデル数をd(h)とする。
(23)において、nにhを代入すると
Ｈ(h)は証明可能である⇔h∈ＲＳ・・・(24)
ところで
Ｈ(h)は証明可能である⇔d(h)∈Ｐ⇔h∈Ｐ#・・・(25)
が成り立つから、(24)と(25)より
h∈ＲＳ⇔h∈Ｐ#
しかし、ＲＳとＰ#は互いに素だから
h≠∈ＲＳ⇔h≠∈Ｐ#　（≠∈は「要素でない」という苦し紛れの記号）
ここで
h≠∈Ｐ#⇔d(h)≠∈Ｐ
より、Ｈ(h)は証明可能でない。
また、Ｒ#⊆ＲＳより
h≠∈ＲＳ⇒h≠∈Ｒ#⇔d(h)≠∈Ｒ
より、Ｈ(h)は反証可能でない。
従って、Ｌは決定不可能な文Ｈ(h)が存在するから、不完全である。

数日サボっただけで、だいぶ下がったなあ。

１章では、抽象化された言語での不完全性を示したけど
２章以下では、ペアノの数論という具体的な数学的言語で不完全性を示します。
まず２章では、タルスキーの定理の証明を試みます。

てなわけで、まず最初は
加法・乗法・累乗法に基づく第１階数論の言語ＬＥについて定義するわけです。
まあ、しばらく定義ばかりが続きます。

【記号】
１３種類の記号を用いる
0　'　(　)　f　,　v　〜　⊃　∀　＝　≦　♯
式(0),(0'),(0''),(0'''),…は「数値」と呼ばれ
順に自然数「0,1,2,3,…」の形式的名称を表している。
「プライム」(')は後続関数の名称である。
(ｆ')は加法記号「＋」、(ｆ'')は乗法記号「・」、(ｆ''')は累乗記号「Ｅ］によって省略される。
加算無限個の式v.1,v.2,…,v.nは、「変数」と呼ばれる。
「v.1,v.2,v.3,…」の形式的名称は(v'),(v''),(V''')…である。

【項と論理式】
次の二つの規則によって生成される式は「項」と呼ばれる。
１全ての変数と数値は項である。
２もしt.1とt.2が項であれば(t.1＋t.2),(t.1・t.2),(t.1Ｅt.2),t.1'も項である。

変数を含まない項は「定項」または「閉じた項」と呼ばれる。

任意の項t.1とt.2に対してt.1＝t.2またはt.1≦t.2の形式の式は「原始論理式」と呼ばれる。
「論理式」の集合は、次の二つの規則によって帰納的に生成される。
１.すべての原始論理式は、論理式である。
２.ＦとＧが論理式でv.1が変数であれば、〜Ｆ,(Ｆ⊃Ｇ),∀v.1Ｆも論理式である。

【変数の自由出現と束縛出現】
任意の項tまたは原始論理式Ａに対して、tまたはＡにおける全ての変数v.iの出現は「自由出現」と呼ばれる。
論理式∀v.iＦにおけるすべての変数v.iの出現は「束縛出現」と呼ばれる。

【文】
変数が自由出現しない論理式は「文」である。
文は「閉じた論理式」と呼ばれる。閉じていない論理式は「開いた論理式」と呼ばれる。
【代入】
変数v.i1,…,v.inのみが自由出現する論理式をＦ(v.i1,…,v.in)で表すとき、v.i1,…,v.inに数値[k.1],…,[k.n]を順に代入した結果を
Ｆ([k.1],…,[k.n])
で表す。
このとき文Ｆ([k.1],…,[k.n])は論理式Ｆ(v.i1,…,v.in)の「代入例」と呼ばれる。

【省略記号】
（Ｆ.1∨Ｆ.2) :＝df (〜Ｆ.1⊃Ｆ.2)
（Ｆ.1∧Ｆ.2) :＝ df〜(Ｆ.1⊃〜Ｆ.2)
Ｆ.1≡Ｆ.2 :＝df ((Ｆ.1⊃Ｆ.2)∧(Ｆ.2⊃Ｆ.1)
∃v.iＦ :＝df 〜∀v.i〜Ｆ
t.1≠t.2 :＝df 〜t.1＝t.2
t.1＜t.2 :＝df ((t.1≦t.2)∧(〜t.1＝t.2))
t.1^t.2 :＝df t.1Ｅt.2
(∀v.i≦t)Ｆ :＝df ∀v.i(v.i≦t⊃Ｆ)
(∃v.i≦t)Ｆ :＝df 〜(∀v.i≦t)〜Ｆ

【指示】
すべての定項cは次の二つの規則によって自然数を一意的に指示する。
１.数値[n]は自然数nを指示する。
２.項c.1とc.2が順に自然数n.1とn.2を指示するとき、(c.1＋c.2)はn.1＋n.2、(c.1・c.2)はn.1・n.2、(c.1Ｅc.2)はn.1^n.2、c.1'はn.1＋１を指示する。

【言語ＬＥにおける真理概念】
言語ＬＥの真理条件は以下の通りである。
Ｔ0:１．原始文c.1＝c.2（c.1とc.2は定項）はc.1とc.2が等しい自然数を指示するときに限って真である。
２．原始文c.1≦c.2はc.1に指示される自然数がc.2に指示される自然数以下であるときに限って真である。
Ｔ1:否定文〜Ｘは、Ｘが真でないときに限って真である。
Ｔ2:含意文Ｘ⊃Ｙは、Ｘが真でないかＸとＹがともに真であるときに限って真である。
Ｔ3:全称文∀v.iＦは、全ての数nに対して文Ｆ([n])が真であるときに限って真である。

（条件Ｔ0は原子文の真理条件を直接定義している。条件Ｔ1,Ｔ2,Ｔ3は非原子文の真理条件を、度数のより低いすべての文の真理条件によって定義している）

【正確】
すべての数n.1,…,n.kに対して文Ｆ([n.1],…,[n.k])が真であるとき、論理式Ｆ(v.i1,…,v.ik)を「正確である」という。

【同等】
２個の文は、共に真であるか共に偽であるときに限って（論理的に）「同等」と呼ばれる。
同じ変数が自由出現する２個の開いた論理式Ｆ(v.i1,…,v.ik)とＧ(v.i1,…,v.ik)が同等であるとは、
全ての数n.1,…,n.kに対して、文Ｆ([n.1],…,[n.k])と文Ｇ([n.1],…,[n.k])が同等であることを意味する。

★問題１★
１．任意の文ＸとＹに対して、文Ｘ∧Ｙは、ＸとＹが共に真であるときに限って真であることを証明せよ。
２．任意の文ＸとＹに対して、文Ｘ∨Ｙは、ＸまたはＹが真であるときに限って真であることを証明せよ。
３．変数v.iのみが自由出現する任意の論理式Ｆに対して、文∃v.iＦは少なくとも１個の数nに対してＦ([n])が真であるときに限って真であることを証明せよ。

[解答]
１．Ｘ∧Ｙは真⇔〜(Ｘ⊃〜Ｙ)は真⇔Ｘ⊃〜Ｙは真でない⇔Ｘは真、かつ、Ｘは真でないかＹは真⇔ＸとＹは共に真

２．Ｘ∨Ｙは真⇔〜Ｘ⊃Ｙは真⇔Ｘが真、または、Ｘは真でなくＹは真⇔ＸまたはＹは真

３．∃v.iＦは真⇔〜∀v.i〜Ｆは真⇔∀v.i〜Ｆは真でない⇔ある数nに対して〜Ｆ([n])は真でない⇔ある数nに対してＦ([n])は真である

　哲学板から数学を除外する運動をしたらどうでしょう。
純粋な論理学も除外しようよ。哲学を目的としない論理学は無用。
　な〜んていきなり現われてそんなこというわけないでしょ。ちょっと
いやみを言ってみただけでした。

不完全性定理の証明自体にどれだけ哲学的意義があるかは分からないけど、
タルスキの真理の理論は哲学としても重要でしょう。
「真」という概念を形式的に扱えるようにした理論なのですから。
一般向けのゲーデル本では、タルスキの結果との関連性について述べたものが
あまり無いみたいだけど、スマリヤンのあの本はタルスキの結果についても
きちんと書いてあるみたいだし、板違いという事もないと思いますよ。

という訳で、がんばって下さい。＞22さん

ちょっと気になったんですが、「Aである時に限って、B」というのを
「A⇔B」という意味で使ってるみたいですが、その本ではそうなっているんですか？
「A⇔B」は、英語では「B if and only if A」（iffと略す事も多い）と書いて
訳す時は「Aの時、かつその時に限って、B」などとするのが一般的だと思うんです。
「Aである時に限って、B」だと「B only if A」、つまり「B⇒A」を表している
という場合もあると思うんですが、どうなんでしょう？

原著と訳本を比べてみればいいんだけど、手元にないしなあ。
大学の図書館にあったはずだけど、もう卒業したから行く事ないし。

>>132
応援ありがとうございます。
漏れも不完全性定理自体が哲学的にどんな（どれほどの）意義があるのか
よく分かりません。
ただ、こんなこと言うと顰蹙買いそうですが、
不完全性定理について正確な理解なしに、
勝手な憶測だけで不毛な議論がなされる傾向があるように思います。
それで、正確な理解を得る為だけでも
スマリヤンの本を読んでいくのは意義があるのではと思ってます。

>>133
本文中に「同値関係は「ときに限って」または記号「⇔」で表す」
と書いています。
原著を見ればいいのでしょうけど
専門に勉強してるわけじゃないんで、そこまではやれません。
他にも訳文が変なところは散見するようです。

>>127
細かい突っ込み。

＞加算無限個の式v.1,v.2,…,v.nは、「変数」と呼ばれる。

「式」ではなく、文字とか記号とか表現とかのほうがよい。
「式」というと、ある特定の性質を満たす文字列（つまり、
論理式）と誤解されるから。

＃論理の学習では、細かい用語の統一が重要。そうしないと、
＃特に、メタ絡みの議論ができなくなる。

原著では、"expressions" と書かれている。

>>134
原著だと「iff」だね。

>>135
索引を見ると"expression"を「式」としているようです。
しかし、たしかに「式」ではなくて「記号」の方がよさそうですね。
漏れは論理初心者なんで、何かあれば教えて下さい。

問題は一部省略してます。
答えはもちろんヒントもないんで、解答はあまり自信はないです。
誰か添削してくれたら助かります。

【集合への言及】
変数v.1のみが自由出現する任意の論理式Ｆ(v.1)に対して
Ｆ(v.1)は文Ｆ([n])を真にする全ての数nの集合を「言及する」という。
よって、論理式Ｆ(v.1)が集合Ａを言及するのは、全ての数nに対して
Ｆ([n])が真である⇔n∈Ａ
が成立するときに限る。

【関係式への言及】
正則論理式Ｆ(v.1,…,v.n)は文Ｆ([k.1],…,[k.n])を真にする全ての数のn順序対(k.1,…,k.n)の集合を「言及する」という。
よって、正則論理式Ｆ(v.1,…,v.n)が関係式Ｒ(x.1,…,x.n)を言及するのは、
全ての数k.1,…,k.nに対して
Ｆ([k.1],…,[k.n])が真である⇔Ｒ(k.1,…,k.n)
が成立するときに限る。

【数論的Ｅおよび数論的】
集合と関係式が、言語ＬＥの論理式に言及されるときには数論的Ｅと呼び、累乗記号「Ｅ」の出現しない言語ＬＥの論理式に言及されるときには数論的と呼ぶことにする。

関係式ｆ(x.1,…,x.n)＝ｙが数論的Ｅであるとき（n順序対の自然数から自然数への）関数ｆ(x.1,…,x.n)も数論的Ｅと呼ばれる。

以下、（自然数の）任意の「性質Ｐ」を数論的Ｅと呼ぶ場合は、性質Ｐを持つ自然数の集合が数論的Ｅであることを意味する。
関係あるいは性質をまとめて「条件」と呼ぶこともある。

★問題２★
１．関係式「(x)DIV(y)」が数論的であることを証明せよ。
２．素数の集合が数論的であることを証明せよ。


[解答]
１．
∃v.3(v.3・v.2＝v.1)をＦ.1(v.1,v.2)とすると、全ての数k.1,k.2に対して
Ｆ.1([k.1],[k.2])が真である⇔(k.1)DIV(k.2)
が成立するから、関係式(x)DIV(y)は論理式Ｆ.1(v.1,v.2)に言及される。
よって、(x)DIV(y)は数論的である。

２．
〜∃v.2(１＜v.2∧Ｆ.1(v.1,v.2))をＦ.2(v.1)として
素数の集合をＡとすると、全ての数kに対して
Ｆ.2([k])が真である⇔k∈Ａ
が成立するから、素数の集合は論理式Ｆ.2(v.1)に言及される。
よって、素数の集合は数論的である。

★問題３★
任意の自然数の集合Ａと任意の（自然数から自然数への）関数ｆ(x)に対して
ｆ(n)∈Ａをみたす全ての数nの集合をｆ^-1(Ａ)で表す。
このとき、集合Ａと関数ｆが数論的Ｅであれば、集合ｆ^-1(Ａ)も数論的Ｅであることを証明せよ。


[解答]
仮定より、全ての数k.1,k.2,k.3に対して
Ｆ.1([k.1])が真である⇔k.1∈Ａ
Ｆ.2([k.2],[k.3])が真である⇔ｆ(k.2)＝k.3
が成立するような論理式Ｆ.1(v.1),Ｆ.2(v.1,v.2)が存在する。
∀v.2(Ｆ.1(v.2)∧Ｆ.2(v.1,v.2))をＦ.3(v.1)とする。
このとき、全ての数kに対して
Ｆ.3([k])が真である⇔ｆ(k)∈Ａ⇔k∈ｆ^-1(Ａ)
が成立するから、集合ｆ^-1(Ａ)は論理式Ｆ.3(v.1)に言及される。
よって、ｆ^-1(Ａ)は数論的Ｅである。

★問題４(1)★
任意の数論的Ｅ関数ｆ(x)とｇ(y)に対して、関数ｆ(ｇ(y))が数論的Ｅであることを証明せよ。


[解答]
条件より、全ての数k.1,…,k.4に対して
Ｆ.1([k.1],[k.2])が真である⇔ｆ(k.1)＝k.2
Ｆ.2([k.3],[k.4])が真である⇔ｇ(k.3)＝k.4
が成立するような論理式Ｆ.1(v.1,v.2),Ｆ.2(v.1,v.2)が存在する。
∀v.3(Ｆ.1(v.1,v.3)∧Ｆ.2(v.3,v.2))をＦ.3(v.1,v.2)とする。
このとき、全ての数k.1,k.2に対して
Ｆ.3([k.1],[k.2])が真である⇔ｆ(ｇ(k.1))＝k.2
が成立するから、関数ｆ(ｇ(y))は論理式Ｆ.3(v.1,v.2)に言及される。
よって、ｆ(ｇ(y))は数論的Ｅである。

★問題５★
数論的Ｅ無限集合Ａおよび任意の数y（Ａに含まれるか否かにかかわらず）に対して、yよりも大きいＡの要素xが必ず存在することを証明せよ。
このとき「xはyよりも大きいＡの最小数である」という関係式Ｒ(x,y)について
Ｒ(x,y)が数論的Ｅであることを証明せよ。


[解答]
yよりも大きいＡの要素xが存在しないと仮定すると
Ａの要素の数はy以下になるが、Ａは無限集合であるから、矛盾する。
よって、yよりも大きなＡの要素xは必ず存在する。

集合Ａを言及する論理式をＦ.1(v.1)とする。
「xはyよりも大きいＡの最小数である」
⇔「xはyよりも大きいＡの要素であり、かつ、xより小さくてyよりも大きいＡの要素は存在しない」
であるから、
(v.2＜v.1∧Ｆ.1(v.1))∧〜∃v.3(v.2＜v.3∧v.3＜v.1∧Ｆ.1(v.3))
をＦ.2(v.1,v.2)とすると、全ての数k.1,k.2に対して
Ｆ.2([k.1],[k.2])が真である⇔Ｒ(k.1,k.2)
が成り立つ。
よって、関係式Ｒ(x,y)は論理式Ｆ.2(v.1,v.2)に言及されるから
Ｒ(x,y)は数論的Ｅである。

訂正

問題２の１．の解答で
>∃v.3(v.3・v.2＝v.1)
とあるのは
∃v.3(１≦v.3∧v.3・v.2＝v.1)
です。

もう一つ訂正（汗

問題２の２．の解答で
>〜∃v.2(１＜v.2∧Ｆ.1(v.1,v.2))
とあるのは
v.1≠０∧〜∃v.2(１＜v.2∧v.2＜v.1∧Ｆ.1(v.1,v.2))
です。

実際生活の中でその難解な論理が使えるのか？ってスレ参加者に聞きたい
です。煽りではなく。

＞【数論的Ｅおよび数論的】

Arithmetic と arithmetic ですな。原著では。普通は「算術的」とする
けどね。

数論だと普通はNumber Theoryのこととおもうが。まあ、訳者のバックボーン
しだいで訳語は変わるから。

＃工学系なのかな？工学のほうの訳語はちょと違うからな。

＞あんたがあのスレの基地害に絡まれることはないと思うが

誰か呼んだか（笑）

＞もうでてこないだろ。

でてきてやったぞ（笑）

＞当時結構あった基礎論や論理スレすべてに出没して、
＞自分好みのスレ立ててたけどいまや影も形もないからねえ（笑）

前半は正しい。後半は誤り。スレを立てたことはない。

＞まっとうになったか、入院したのかのどちらかであろうよ。

オレはヤマジンじゃない（笑）

＞入院してくれてたらどれだけいいか

生きたまま、火葬場で焼いたろか（笑）

＞前原昭二なんか読んでばかりいないで
＞田中一之の『数の体系と超準モデル』でも読んで、出直して来い

そもそも、前原とか田中とか、日本語の本を読んでんじゃねえよ（笑）

132=133です。

＞本文中に「同値関係は「ときに限って」または記号「⇔」で表す」
＞と書いています。

そう明記されてるなら、問題ないですね。
「iff」をいちいち「〜の時、かつその時に限り」などと訳すのは
一般読者には煩わしいだけだと判断したのかも知れません。

訳者の高橋昌一郎氏は國學院大学文学部の教授ですね。
哲学として論理学を学んだ人なのでしょう。

訂正ばっかで恥ずかしいです（汗
問題４(1)の解答で
>∀v.3(Ｆ.1(v.1,v.3)∧Ｆ.2(v.3,v.2))
とあるのは
∃v.2(Ｆ.1(v.2)∧Ｆ.2(v.1,v.2))
です。いやー、数学ドキュソぶりを発揮してしまいました。

>>146
「数論的」より「算術的」とした方がいいでしょうね。

>>148
漏れは論理初心者なんでお手柔らかにお願いします。
（数学・情報科学どころか哲学も専門ではありませんので）
ちなみに、Shoenfieldの「Mathematical　Logic」や
Hodgesの「Model　Theory」あたりが定評ある教科書と聞いていますが
どうなんでしょうか。
まあ、スマリヤンと田中の本を読み終えてからの話ですから
だいぶ後のことでしょうけど。
あ、スマリヤンの続編も読んでみたいですね。

ともかくも、ようやくゲーデル数の導入までたどり着きました。やれやれ

【ｂ基底への連結】
関数：
m＊<b>n
は、任意の数b≧２に対して、b進法で構成される数mに続いてb進法の数nを表記するb進法の数と定義する。
ｌ<b>(n)が数nの（b進法における）長さを表すとき
m＊<b>n＝m・b^ｌ<b>(n)＋n
である。

◆命題１◆
任意の数b≧２に対して、関係式x＊<b>y＝zは算術的Ｅである。

[証明]
任意の数b≧２に対して証明する
１．数xがbの累乗である条件をPow<b>(x)とおく。
そこで条件Pow<b>(x)は、論理式∃y(x＝b^y)が真であるときに限って成立することから、算術的Ｅである。

２．（xとyの関係を表す）関係式「yはxよりも大きいbの累乗の最小数である」をｓ(x,y)とおくと
関係式b^ｌ<b>(x)＝yは、
条件(x＝０∧y＝b)∨(x≠０∧ｓ(x,y))・・・(26)
と同等である。
ここで、関係式ｓ(x,y)は
条件Pow<b>(y)∧x＜y∧∀z((Pow<b>(z)∧x＜z)⊃y≦z)・・・(27)
と同等であるが、条件(27)は算術的Ｅである。
よって、条件(26)は算術的Ｅであり
関係式b^ｌ<b>(x)＝yは算術的Ｅである。

３．関係式x・b^ｌ<b>(y)＋y＝z（すなわちx＊<b>y＝z)は
条件∃z.1∃z.2(b^ｌ<b>(y)＝z.1∧x・z.1＝z.2∧z.2＋y＝z)・・・(28)
と同等である。
条件(28)は算術的Ｅであるから、関係式x＊<b>y＝zは算術的Ｅである。

◆系１◆
任意の数n≧２とb≧２に対して(x.1,…,x.n,yに対する(n＋１)対の)関係式：
x.1＊<b>x.2＊<b>…＊<b>x.n＝y・・・(29)
は算術的Ｅである。
（x＊<b>y＊<b>zは(x＊<b>y)＊<b>zの省略である）

[証明]
n≧２に対する帰納法による。
n＝２の場合はすでに証明された。
n≧２の場合、
関係式x.1＊<b>x.2＊<b>…＊<b>x.n＝yは算術的Ｅであると仮定する。
このとき
x.1＊<b>x.2＊<b>…＊<b>x.n＊<b>x.n+1＝y
⇔∃z(x.1＊<b>x.2＊<b>…＊<b>x.n＝z∧z＊<b>x.n+1＝y)
であるから、関係式x.1＊<b>x.2＊<b>…＊<b>x.n＊<b>x.n+1＝yも算術的Ｅである。
よって、関係式(29)は算術的Ｅである。

【ゲーデル数化】
算術的Ｅな文（すなわち言語ＬＥの文）は、「数」について言及するのであって、ＬＥの式について言及するわけではない。
式にゲーデル数を割り当てる目的は、文が（直接的にゲーデル数を言及することによって）間接的に式を言及できるようにすることである。

言語ＬＥは13種類の記号によって形式化されている。
そこで基底13を用いた連結によって、記号列をゲーデル数化する。
13進法表記では10進法表記の10,11,12の代わりにη,ε,δを用いる。
よって、13個の記号には、次のゲーデル数を割り当てる。
０:1　':0　（:2　):3　ｆ:4　,:5　v:6　〜:7　⊃:8　∀:9　＝:η　≦:ε　＃:δ

任意の数n＞０に対して、nをゲーデル数に持つ式をＥ.nと定義する。


■■コメント■■
系１により、式Ｅ.nに対してゲーデル数nを対応させる関係式は算術的Ｅである。
よって、ＬＥの任意の論理式を間接的に言及する論理式が存在することになる。

>>150
あちゃー、間違えてばっかしやん（汗

>問題４(1)の解答で
>>∀v.3(Ｆ.1(v.1,v.3)∧Ｆ.2(v.3,v.2))
>とあるのは
>∃v.2(Ｆ.1(v.2)∧Ｆ.2(v.1,v.2))
∃v.3(Ｆ.1(v.1,v.3)∧Ｆ.2(v.3,v.2))
ですよね。
そんでもって、問題３の解答
>∀v.2(Ｆ.1(v.2)∧Ｆ.2(v.1,v.2))
が
∃v.2(Ｆ.1(v.2)∧Ｆ.2(v.1,v.2))
となるんですよね。

後から後から間違いがポロポロ見つかるなあ（汗

>>143
>∃v.3(１≦v.3∧v.3・v.2＝v.1)
∃v.3([1]≦v.3∧v.3・v.2＝v.1)

>>144
>v.1≠０∧〜∃v.2(１＜v.2∧v.2＜v.1∧Ｆ.1(v.1,v.2))
v.1≠[0]∧〜∃v.2(１＜v.2∧v.2＜v.1∧Ｆ.1(v.1,v.2))

いやー、記号の使用に慣れるには
地道に問題をこなしていかないとあかんな。

おっと
>v.1≠[0]∧〜∃v.2(１＜v.2∧v.2＜v.1∧Ｆ.1(v.1,v.2))
v.1≠[0]∧〜∃v.2([1]＜v.2∧v.2＜v.1∧Ｆ.1(v.1,v.2))

>>132
＞タルスキの真理の理論は哲学としても重要でしょう。
＞「真」という概念を形式的に扱えるようにした理論なのですから。

やれやれ、ここにもいたか哲学知らずの数学小僧（笑）

＞一般向けのゲーデル本では、
＞タルスキの結果との関連性について述べたものが
＞あまり無いみたいだけど、
＞スマリヤンのあの本はタルスキの結果についても
＞きちんと書いてあるみたいだし

やれやれ、実は数学知らずの知ったかブリブリか（笑）

　スマリヤンは不完全性定理を示すのにタルスキの方法を用いると
いっているが、それはいわゆるタルスキのモデルの理論とは関係がない。

一般人はまず、スマリヤンの本のｐ３〜６の「ゲーデル・パズル」を読め。

読んでわかった奴は、後を読む必要はない。
本論はパズルの話を数学的に七面倒臭く解説しているだけ。

読んでわからん奴は、後を読んでも無駄。諦めろ
あれよりわかりやすい話は、後には絶対出てこない（笑）

なんだ>>96も同じこといってんじゃん。

そういえば、GEBは厚いとか文句垂れてる諸君。
本はアタマから読むものと決めてかかってないか？

もちろん、世の中には裏道ってのもある。
まず第１４章の前の「G線上のアリア」を読め。
それから第１４章を読め。

まあ、もうちょっと余裕がある読者は
第１３章の前の「アリアとさまざまの変奏」から読んでもいいかな。

とはいえ、そのあたりはいわば前段であって、著者の主張は
実はゲーデル以後、第１６章の「自己言及と自己増殖」以降
のところにある。

Part�Tの命題論理だの述語論理だのとかいう部分はすっとばしてもいい。
個人的には「無の捧げもの」と第９章の「無門とゲーデル」は好きだが
本論とは直接関係ない。

ただ、いっておくが、GEBはすっとばして読んでもツマランぞ。
GEBは、ナーゲル・ニューマンみたいにゲーデルの不完全性定理
”だけ”を解説するための本じゃない。（別にナーゲル・ニューマン
の本が悪いとはいわんが、特に面白いとは思わない）

>>133
＞大学の図書館にあったはずだけど、もう卒業したから行く事ないし。

ほう、133は大学出たのか。
もっとも、大学出たから、分かっているということにはならんな。

かくいうこの私自身、大学時代に図書館にGEBがあったにもかかわらず、
「ただただ著者のヨタ話を書き連ねただけの無駄に厚い本」
くらいにしか思わず、まじめに読むことすらしなかった。
サークルの後輩Aが、自己印刷プログラムの話をしたときも、
くだらぬヨタ話くらいにしかおもわなかった。
今だったら、そいつを「プチ天才」とかいってキスしてやりたいくらいだ。
ゲーデルの定理もぜんぜんわかっていなかった。
チューリング機械の停止判定アルゴリズムがないとか、
述語論理の充足可能性判定ができないとかいうのは知ってたが
それらがゲーデルの定理の系であることも知らなかった。
一番のポカは、λ計算の不動点作用素を習ったのに
それがゲーデルの不完全性定理の証明から出たものだと
ぜんぜん気づかなかったことだ（汗）
今では、ゲーデルに関しては厨房程度の理解しかないと認めよう
しかし、世間の連中は消防程度の無理解である。
消防と厨房の違い？そうだな
連立一次方程式の解き方がわかるのが消防
二次方程式ｘ＾２＝２の解が無理数だと分かるのが厨房
いっとくけど、これはただのヨタではないよ。

>>159
９６ですが、激しく同意でござる。貴殿ほど拙者は害基地ではないので
やわらかく物を言わせてもらったが、その心は貴殿と同じであった。

あまりいじめないでやっておくれ。

>>159,162
ゲーデル・パズルは有名なパズルなんですね。
知らなかったです。逝ってきます（汗

というわけで、ゲーデル・パズルについて書きました。
計算理論については何も知らないので
不完全性定理が具体的に
チューリングマシンの停止問題とどう繋がるのかは分かりません。
暇があれば、計算理論についても少し学んでみたいですね。

【ゲーデル・パズル】
〜　Ｐ　Ｎ　（　）
の５種類の記号を組み合わせた、空ではない有限の記号列を「式」と呼び
「式」を印字する機械を考える。
機械がある式Ｘを印字することができるとき、Ｘは「印字可能」と呼ばれる。
機械には、印字可能な式を印字するプログラムが組み込まれている。

形式Ｘ（Ｘ）の式は、Ｘの標準形と呼ばれる。
次の４種類の形式の式は「文」と呼ばれる。
(A)Ｐ（Ｘ）
(B)ＰＮ（Ｘ）
(C)〜Ｐ（Ｘ）
(D)〜ＰＮ（Ｘ）
非形式的に「Ｐ」は「印字可能である」、「Ｎ」は「標準形である」
「〜」は「でない」と解釈される。

文の真理条件を以下のように定義する。
(a)Ｐ（Ｘ）は真である⇔Ｘは印字可能である
(b)ＰＮ（Ｘ）は真である⇔Ｘ（Ｘ）は印字可能である
(c)〜Ｐ（Ｘ）は真である⇔Ｘは印字可能でない
(d)〜ＰＮ（Ｘ）は真である⇔Ｘ（Ｘ）は印字可能でない

偽である文を決して印字しないようにプログラミングされていると仮定する。
このとき、機械は全ての真である文は印字できるだろうか？
その答えは「できない」である。
では、真であるにもかかわらず機械が印字できない文とは、どんな文か？

■■コメント１■■
ゲーデル・パズルにおける機械に組み込まれたプログラムは
不完全性定理が成立するような最小限の性質を持った体系であると考えられる。

「印字可能」を「証明可能」と解釈する。
「文の集合」は(A)から(D)によって定義される。
また、真理条件より「真である文の集合」Ｔ$が導入される。
「証明可能な式の集合」Ｐ\に対して
(a),(c)より、Ｐ\,Ｐ\~が言及可能であることが分かり
(b),(d)より、Ｐ\@,Ｐ\~@が言及可能であることが分かる。
(今までＡ#等と表記していたのをＡ@等と表記することにする）

// Ｐ(Ｘ)∈Ｔ$⇔Ｘ∈Ｐ\
// 〜Ｐ(Ｘ)∈Ｔ$⇔Ｘ∈Ｐ\~
// ＰＮ(Ｘ)∈Ｔ$⇔Ｘ(Ｘ)∈Ｐ\⇔Ｘ∈Ｐ\@
// 〜ＰＮ(Ｘ)∈Ｔ$⇔Ｘ(Ｘ)∈Ｐ\~⇔Ｘ∈Ｐ\~@


この体系は正確であり、集合Ｐ\~@が言及可能であるから
１章で示された定理ＧＴにより
真であるにもかかわらず証明可能でないＰ\~のゲーデル文〜ＰＮ(〜ＰＮ)が存在する。

//　(d)より任意の式Ｘに対して
//　〜ＰＮ(Ｘ)は真である⇔Ｘ(Ｘ)∈Ｐ\~
//　Ｘに〜ＰＮを代入すると（対角化）
//　〜ＰＮ(〜ＰＮ)は真である⇔〜ＰＮ(〜ＰＮ)∈Ｐ\~
//　⇔〜ＰＮ(〜ＰＮ)は証明可能な式でない
//　ところで、(D)より〜ＰＮ(〜ＰＮ)は文であるから
//　真であるにもかかわらず証明可能な文〜ＰＮ(〜ＰＮ)が存在する。

■■コメント２■■
「反証可能な式の集合」Ｒ\を
〜Ｘ∈Ｐ\⇔Ｘ∈Ｒ\
と定義すると、(b)より
ＰＮ(〜Ｘ)は真である⇔Ｘ(Ｘ)∈Ｒ\⇔Ｘ∈Ｒ\~
よって、集合Ｒ\~は言及可能であるから、１章の定理１’により
体系Ｌにおいて決定不可能な文ＰＮ(〜ＰＮ)が存在する。

証明可能な文を入力すると、その文を印字して停止し、
反証可能な文を入力すると、印字しないで停止するようにプログラムする。
その場合、決定不可能な文を入力すると、
プログラムはいつまでも停止せずに無限ループに陥ると考えられる。

すげーッ､みんな､頭良すぎるー､何がなんだか、わからん

>>163
スマリヤンは様々なパズル仕立ての本でゲーデルの定理などの
論理の解説本を書いているよ。

「パズル仕立て」ってだけで、全然簡単じゃないと言うのが定評だよ（笑
読みやすく段階的に並べられてるけど、中高生で何とかなるようなレベル
じゃないなあ。

>>166
＞ ＰＮ(〜Ｘ)は真である⇔Ｘ(Ｘ)∈Ｒ\⇔Ｘ∈Ｒ\~

↑ここ、少し変ですよ。
ＰＮ(〜Ｘ)は真である⇔〜Ｘ(〜Ｘ)∈Ｐ\⇔Ｘ(〜Ｘ)∈Ｒ\
ですよね？ＰＮ(〜ＰＮ)が印字不可能なのは、
単にＰＮ(〜ＰＮ)が偽であり体系が正確だからでしょう。

>>168
数学科のダチに言わせれば、このスレで読んでるスマリヤンの本は
「中高生向けの易しい入門書」だそうです。
いやはや、数学得意な人間は別世界の住人ですね（笑
漏れのような数学・論理ドキュソは趣味に留めて、
深入りしない方がいいのかも。

>>169
たしかに、単純な間違いです。
指摘していただき、ありがとうございます。
>ＰＮ(〜Ｘ)は真である⇔〜Ｘ(〜Ｘ)∈Ｐ\⇔Ｘ(〜Ｘ)∈Ｒ\
ＸにＰＮを代入して
ＰＮ(〜ＰＮ)は真である⇔ＰＮ(〜ＰＮ)は反証可能である
体系は正確だから
ＰＮ(〜ＰＮ)は偽であるにもかかわらず反証可能でない
となるんですよね。

スマリヤンはタルスキの真理集合を用いて不完全性定理を証明しているので
参考までに、タルスキの論文「真理の意味論的観点と意味論の基礎」
の有名な箇所を抜粋します。
（『現代哲学基本論文集�U』にある翻訳です）

【真理の意味論的観点と意味論の基礎】
真理の理論を、数学的諸分野のあるきわめて包括的なクラスの形式
化された言語に適用することによって、より多くの重要な結果を得
ることができる。このクラスから除外されるのは、初等的な性格を
もち、きわめて初等的な論理構造をもつ分野のみである。このクラ
スに属する分野に対しては、「真理の観念は決して証明可能の観念
と合致しない」ということがわかる。なぜならば、証明可能な文は
全て真であるが、証明可能でなくてしかも真であるような文がある
からである。よって、こうした分野はどれも、無矛盾であるが不完
全である、ということが帰結する。つまり、たがいに矛盾する二つ
の文のうちせいぜい一方だけが証明可能であるが、それに加えて、
たがいに矛盾する文の組でいずれも証明可能ではないようなものが
存在するのである。(注)

【真理の意味論的観点と意味論の基礎（注）】
こうして、真理の理論は、形式化された数学的分野の無矛盾性証明
のための一般的方法を提供する。しかしながら、この方法で得られ
る無矛盾性の証明が、いくらかでも直観的価値をもちうるのは−−
すなわち、問題となっている分野が実際に無矛盾である、とわれわ
れを納得させたり、その信念を強化したりできるのは−−、対象言
語をその部分として含まないようなメタ言語を使って、真理を定義
するのに成功した場合だけである。なぜならば、この場合にのみ、
メタ言語の演繹的仮定は、対象言語のそれよりも、直観的により単
純でより明らかでありうる−−「本質的豊富さ」の条件が形式的に
満足されているにもかかわらず−−からである。

形式化された分野の包括的なクラスの不完全性は、ゲーデルの基本
的な定理の本質的内容を成すものである。真理の理論がかくも直に
ゲーデルの定理に導く、という事実の説明はごく単純である。真理
の理論からゲーデルの結果を導出するのに、真理の定義は、対象言
語と同じだけしか「豊富」でないようなメタ言語の中では与えられ
ない、という事実が本質的に使用される。しかしながら、この事実
を確立するのに、ゲーデルによって(はじめて)用いられたのと非常
に密接に関連する論法が適用されたのである。また、真理の観念は
ゲーデルの証明に明示的に現れることはないが、かれは、明らかに
真理の観念についてのある直観的考察に導かれて、証明を行った、
ということも付け加えておこう。

>>170
＞数学科のダチに言わせれば、このスレで読んでるスマリヤンの本は
＞「中高生向けの易しい入門書」だそうです。
＞いやはや、数学得意な人間は別世界の住人ですね（笑

んなこたない。若いうちは若さを過大評価するからそういうセリフが
でやすいだけ。

３０すぎると中高生に無理ということが身にしみてわかる。特に、
教育の現場で実際に若い子と触れてるとね。

>>170
＞数学科のダチに言わせれば、このスレで読んでるスマリヤンの本は
＞「中高生向けの易しい入門書」だそうです。

それって「美女か野獣か」のことじゃない？
http://www.amazon.co.jp/exec/obidos/ASIN/4627018606/qid=1033078315/sr=1-4/ref=sr_1_2_4/250-6678260-7300231

いや、別にゲーデルの不完全性定理が、
大学教養レベルでも中高生レベルでもいいんだけどさ。
（ちょっと前、ゲーデルなんてＴ大では教養レベルとかいうヤツがいて
何のことをいってるのかと思ったら、どうも立花隆ゼミのことらしい（笑）
はあ、せめて野矢さんの哲学の講義なら許してあげようと思ったんだが）

てゆーか、今度中学高校で「情報」って科目ができるらしいじゃない。
そこで、ゲーデルの不完全性定理をさわりでもとりあげられれば面白い。
自己印刷プログラムなんて、ちょっとハッカー気分じゃん（笑）

その点では、中高生むきには「ものまね鳥をまねる」もいいかな。
http://www.amazon.co.jp/exec/obidos/ASIN/4627019017/qid=1033078315/sr=1-5/ref=sr_1_2_5/250-6678260-7300231

>>173

てゆーか、数学科の奴って不完全性定理なんてウザいとおもってんだよ。
ほら、全知全能感に満ちたナルシストだからさ（笑）

でも、そういうナルシシズムがないと、数学で新しい結果なんて出せないかもな。
つまり、学者は正常であってはだめで、どこかイッちゃってないといけない。

とはいえ、世の中には、ただイッちゃってるだけって奴も多いよな（笑）

>>175
＞とはいえ、世の中には、ただイッちゃってるだけって奴も多いよな（笑）

激しく同意（大笑）

不完全性定理
http://science.2ch.net/test/read.cgi/math/1007577490/l50

>>173
>んなこたない。若いうちは若さを過大評価するからそういうセリフが
>でやすいだけ。
でも、数学や論理って、厨房・工房のうちに
もろに才能の差がでてくるような気がします。
ＳＥＧや大数の学コンには、とんでもないヤシもいましたからね。
まあ、漏れがゲーデルなんかに興味持つのは
ルサンチマンなのかも知れません（汗

>>174
いやあ、『ゲーデルの不完全性定理』のことです。
まあ、工房の頃から杉浦の『解析入門』読んでたヤシですから
自信家の戯言と受け取っときましょう（笑
ところで、スマリヤンはパズルの本をやたらと沢山書いてますね。
そうそう、ゲーデル・パズルを具体的にＣでプログラミングすると
どんなのになるんでしょうか。
漏れはプログラミングも苦手なので教えて下さい（汗

というわけで、ようやく「タルスキの定理」までこぎつけました。
３章からは、いよいよペアノ算術における不完全性に入ります。

【表現関数】
任意の論理式Ｆ(v.1)と任意の数nに対して、文Ｆ([n])は
∀v.1(v.1＝[n]⊃Ｆ(v.1))・・・(30)
と同等である。文(30)をＦ@([n])と省略する。

任意の数eとnに対して、eをゲーデル数に持つ式をＥとおき、式Ｅ@([n])のゲーデル数をr(e,n)とおく。
よって、任意の数xとyに対して、数r(x,y)はＥ.x@([y])のゲーデル数である。


◆命題２◆
関数ｒ(x,y)は算術的Ｅである。
（関数ｒ(x,y)は言語ＬＥの「表現関数」とよばれる）

[証明]
式Ｅ.x@([y])は、式∀v.1(v.1＝[y]⊃Ｅ.x)である。
ここで「∀v.1(v.1＝」のゲーデル数をkとおく。
含意記号「⊃」のゲーデル数は８であり、右括弧「）」のゲーデル数は３である。
数値[y]のゲーデル数は13^yであり、式Ｅ.xのゲーデル数はxである。
つまり、式Ｅ.x@([y])のゲーデル数はk＊13^y＊8＊x＊3であり、よって
ｒ(x,y)＝k＊13^y＊8＊x＊3
したがって、関係式ｒ(x,y)＝ｚは明らかに数論的Ｅである。

【対角化とゲーデル数】
ｄ(x)＝ｒ(x,x)とおく。この関数ｄ(x)は「対角関数」である。
関数ｒ(x,y)が算術的Ｅであることから、d(x)も明らかに数論的Ｅである。
任意の数nに対して、ｄ(n)はＥ.n@([n])のゲーデル数を表している。
任意の数集合Ａに対して、ｄ(n)∈Ａをみたすすべての数nの集合をＡ@とおく。


◆補助定理１◆
もし集合Ａが算術的Ｅであれば、集合Ａ@も算術的Ｅである。
（１章の条件Ｇ１に相当）

[証明]
集合Ａ@は、∃y(ｄ(y)＝y∧y∈Ａ)を満たす全てのxの集合である。
ここで、対角関数ｄ(x)が算術的Ｅであることから、
関係式ｄ(x)＝yを言及する論理式Ｄ(v.1,v.2)が存在する。
集合Ａを言及する論理式をＦ(v.1)とおく。すると、集合Ａ@は
∃v.2(Ｄ(v.1,v.2)∧Ｆ(v.2))
に言及される。

◆定理１◆
すべての算術的Ｅ集合Ａに対して、Ａのゲーデル文が存在する。
（１章の補助定理Ｄに相当）

[証明]
集合Ａを算術的Ｅとおく。補助定理１により、集合Ａ@も算術的Ｅである。
このとき、集合Ａ@を言及する論理式をＨ(v.1)とおき、そのゲーデル数をhとおくと
Ｈ@([h])は真である⇔h∈Ａ@⇔d(h)∈Ａ
ところで、d(h)はＨ@([h])のゲーデル数である。
したがって、Ｈ@([h])は集合Ａのゲーデル文である。

◆定理２[タルスキーの定理]◆
真である算術的Ｅ文のゲーデル数の集合Ｔは、算術的Ｅではない。
（１章の定理Ｔに相当）

[証明]
まず、集合Ｔ~のゲーデル文は存在しない。
なぜなら、存在すると仮定すると、その文は真であるときに限って真ではなく、矛盾するからである。
集合Ｔ~は算術的Ｅであると仮定する。定理１より集合Ｔ~のゲーデル文が存在することになり、矛盾する。よって、集合Ｔ~は算術的Ｅでない。
ところで、算術的Ｅ集合のクラスは、明らかに補元について閉じている。
なぜなら、もし論理式Ｆ(v.1)が集合Ａを言及するならば、その否定〜Ｆ(v.1)はＡの補集合Ａ~を言及するからである。
よって、集合Ｔは算術的Ｅでない。


■■コメント■■
体系の証明可能な文のゲーデル数の集合は、集合Ｔと異なり、算術的Ｅである。
（「ゲーデル数xの式は証明可能」という意味の論理式が存在する）
したがって、タルスキーの定理により、論文「真理の意味論的観点と意味論の基礎」に書かれているように「真理の観念は決して証明可能の観念と合致しない」のである。

★問題６★
本章のゲーデル数化の方法を用いて、基底10のゲーデル数化により、偶数の集合のゲーデル文Ｘを求めよ。
このとき、文Ｘのゲーデル数が偶数であるときに限ってＸは真となる。
さて、文Ｘは真か偽か？
（ゲーデル数の割り当て8,9,η,ε,δの代わりに89,899,8999,89999,899999
を用いる）


[解答]
偶数の集合をＡとし、Ａを言及する論理式Ｆ(v.1)を
∃v.2(v.2・[2]＝v.1)とする。
対角関数ｄ(v.1)に対して、関係式ｄ(v.1)＝v.2を言及する論理式をＤ(v.1,v.2)とする。このとき、集合Ａ@を言及する論理式は
∃v.2(Ｄ(v.1,v.2)∧Ｆ(v.2))である。
この論理式をＨ(v.1)とおき、そのゲーデル数をhとおく。
Ｈ@([h])は真である⇔h∈Ａ@⇔ｄ(h)∈Ａ
ｄ(h)はＨ@([h])のゲーデル数であるから、
偶数の集合のゲーデル文はＨ@([h])である。
この文のゲーデル数は（＊<10>を＊と省略する）
ｄ(h)＝ｒ(h,h)＝k＊10^h＊89＊h＊3＝(k＊10^h＊89＊h)・10＋3
よって、ゲーデル文Ｘのゲーデル数は奇数であるから、文Ｘは偽である。

★問題７★
次のような算術的Ｅ関数ｆ(x)を求めよ：
任意の数nに対して、nが自由変数v.1のみを含む論理式Ｆ(v.1)のゲーデル数であれば、
ｆ(n)は、論理式Ｆ(v.1)が言及する集合のゲーデル文のゲーデル数である。


[解答]
Ｆ(v.1)が言及する集合をＡとする。
集合Ａ@は∃y(ｄ(x)＝y∧y∈Ａ)を満たす全てのxの集合であるから、
ｄ(v.1)＝v.2を言及する論理式をＤ(v.1,v.2)とすると
集合Ａ@は論理式
∃v.1(Ｄ(v.2,v.1)∧Ｆ(v.1))・・・(31)
に言及される。
(31)をＨ(v.2)とおき、ゲーデル数をhとする。
「∃v.1(Ｄ(v.2,v.1)∧」のゲーデル数をkとすると、ゲーデル数hは
h＝k＊n＊3
である。
Ｈ@([h])は真である⇔h∈Ａ@⇔ｄ(h)∈Ａ
ここでｄ(h)はＨ@([h])のゲーデル数であるから、
Ｈ@([h])は集合Ａのゲーデル文である。
よって、
ｆ(n)＝ｄ(h)＝ｄ(k＊n＊3)
であり、ｆ(x)は数論的Ｅ関数である。

>>178
＞ＳＥＧや大数の学コンには、とんでもないヤシもいましたからね。

それは一万人に一人というレベルだな。

＞まあ、工房の頃から杉浦の『解析入門』読んでたヤシですから

余談だが、不完全性定理は数学的には面白みはない（笑）

たとえば君はカントールの実数の非可算性の証明や
ラッセルのパラドックスの話は数学的に面白いと
思うかい。それと同じ。

でも、それだから「つまらない」ということにはならない。
つまり、この手のトリックの面白さは数学というよりは、
言語の面白さなんだ。だから言語障害系の数学小僧には
わからないことなんだ（笑）

>>178
＞ゲーデル・パズルを具体的にＣでプログラミングすると
＞どんなのになるんでしょうか。

真偽の判定とかいうのは面倒なので、少々設定を変えよう。
用意するのは、以下のプログラム

Eval(c)　ソースcを解釈、実行するcプログラム
Trans(x)　値xに()を付け加えるプログラム
Subst(c､v)　ソースcの変数を値vに書き換えるプログラム

これらは具体的に書けるが面倒なので省略（笑）

対角関数d(x)をSubst(x,x)とする。

次のプログラムを実行してみたまえ。

Trans(Eval(d("Trans(Eval(d()))")))

停止しないはずである。

>>185
>余談だが、不完全性定理は数学的には面白みはない（笑）
たしかに、数学屋からすれば、数ある定理のうちの一つという感覚でしょうね。
例えば、連続体仮説とゴールドバッハ予想とでは
哲学的には明らかに前者が面白いでしょうが
（ていうか、後者は数学者以外は全く興味をもてないのでは）
数学的には後者の方が面白いと感じる人が多いのではないでしょうか。

>>186
ありがとうございます。
プログラムを実行するプログラムにおいて、
再帰的関数Eval(c)において無限再帰に陥ると考えればいいのですね。
(ソース自体に実行関数があるわけだから、
Eval(c)は再帰的でなければならず、
更に対角関数によって、Eval(c)の再帰の深さが際限なく深くなるわけですから）
観点を変えると
自己書き換えが可能なインタプリンタのプログラム言語があって
それを実行するプログラムと考えればいいのですね。
ということは、そのプログラムは
万能チューリング・マシンをシミュレートするプログラムと言えるのかな。
（漏れはプログラミングは良く知らないので間違った解釈かもしれませんが）

最近読んだ『ロボットにつける薬』という本に
自己書き換えするプログラムのことが書いていました。
常に暴走の危険性があるし、デバッグも大変そうなので実用性は低いでしょうが
素人考えでは、インタプリンタの言語としてなら
有る程度は実用化できるのではないでしょうか。
しかし、そんなプログラム言語はあるのでしょうかね。
まあ、もしあれば、遊びで使うには面白そうではありますけど。

３章から、ようやくペアノ算術における不完全性の証明に入ります。
まずは、加法・乗法に加えて累乗法も公理に加えた算術体系においての証明です。
累乗法を公理とすることで、ゲーデル数の扱いが簡易におこなえるため
まず最初に、累乗法を含むペアノ算術で証明するわけです。

【公理体系Ｐ.Ｅ.】
累乗法に基づくペアノの算術または「Ｐ.Ｅ.」と呼ばれる公理体系を形式化する。
この体系は、19種類の正確な「公理形式」（無限にある公理の図式）と、
すでに証明された正確な論理式から新たに正確な論理式を導く２つの「推論規則」から構成される。
グループ�T・�Uの公理形式は論理公理と呼ばれ、１階述語論理の形式化をおこなう。
グループ�V・�Wの公理形式は算術公理と呼ばれる。
以下の公理形式において、Ｆ，Ｇ，Ｈは任意の論理式、v.i,v.jは任意の変数、tは任意の項を表す。


◆グループ�T・命題論理の公理形式◆
Ｌ1:(Ｆ⊃(Ｇ⊃Ｆ))
Ｌ2:(Ｆ⊃(Ｇ⊃Ｈ))⊃((Ｆ⊃Ｇ)⊃(Ｆ⊃Ｈ))
Ｌ3:((〜Ｆ⊃〜Ｇ)⊃(Ｇ⊃Ｆ))

◆グループ�U・１階述語論理（等号を含む）の公理形式◆
Ｌ4:(∀v.i(Ｆ⊃Ｇ)⊃(∀v.iＦ⊃∀v.iＧ))
Ｌ5:(Ｆ⊃∀v.iＦ)　(変数v.iはＦで出現しない）
Ｌ6:∃v.i（v.i＝t)　(変数v.iはtで出現しない）
Ｌ7:(v.i＝t⊃(Ｘ.1v.iＸ.2⊃Ｘ.1tＸ.2))

■■コメント■■
公理形式の意味は以下のように解釈される。
Ｌ1:推論において結論が真ならば、いかなる前提からの推論も真である。
Ｌ2:Ｆが真でＧからＨが推論されるとき、ＦからＧが推論されるならば、ＦからＨが推論されるという、三段論法が成り立つ。
Ｌ3:いわゆる対偶である。
Ｌ4:全称量化子は分配できる。
Ｌ5:全称量化子を付加することができる。
Ｌ6:充足するモデルが存在する。
Ｌ7:変数が項に等しいとき、変数１個の出現を項に置き換えることができる。（置換）

◆グループ�V・算術の公理形式◆
Ｎ1:(v.1'＝v.2'⊃v.1＝v.2)
Ｎ2:〜[0]＝v.1'
Ｎ3:(v.1＋[0])＝v.1
Ｎ4:(v.1＋v.2')＝(v.1＋v.2)'
Ｎ5:(v.1・[0])＝[0]
Ｎ6:(v.1・v.2')＝((v.1・v.2)＋v.1)
Ｎ7:(v.1≦[0]≡v.1＝[0])
Ｎ8:(v.1≦v.2'≡(v.1≦v.2∨v.1＝v.2')
Ｎ9:((v.1≦v.2)∨(v.2≦v.1)
Ｎ10:(v.1Ｅ[0])＝[0]'
Ｎ11:(v.1Ｅv.2')＝((v.1Ｅv.2)・v.1)

◆グループ�W・帰納法の公理◆
∀v.i(v.i＝v.1'⊃∀v.1(v.1＝v.i⊃Ｆ))　(変数v.iはＦで出現しない）
の形式の任意の論理式をＦ@(v.1')とおく。
このとき、公理形式は次のようになる。
Ｎ12:(Ｆ@([0])⊃(∀v.1(Ｆ(v.1)⊃Ｆ@(v.1'))⊃∀v.1Ｆ(v.1)))

◆推論規則◆
体系Ｐ.Ｅ.は次のような２つの推論規則を持つ。
規則１:「肯定化」式Ｆと(Ｆ⊃Ｇ)から式Ｇを導く
規則２:「一般化」式Ｆから式∀v.iＦを導く

■■コメント■■
Ｎ1:任意の二つ数の後者が等しいならば、その二つの数は等しい。後者の定義。
Ｎ2:任意の数の後者はゼロではない。０元以外の存在。
Ｎ1とＮ2はペアノの公理である。

Ｎ3:加法における０元の存在。
Ｎ4:加法の帰納的定義。
Ｎ5:乗法における０元の存在。
Ｎ6:乗法の帰納的定義。
Ｎ7:大小関係における最小元(０元)の存在。
Ｎ8:大小関係の帰納的定義。
Ｎ9:任意の数において必ず大小関係が成り立つ。
Ｎ10:累乗における０元の存在。
Ｎ11:累乗の帰納的定義。
Ｎ3からＮ11までは、関数の帰納的定義によって定義されるが
ここでは、あらかじめ公理として導入される。

帰納法の公理において定義されたＦ@(v.1')はＦ(v.1)の全ての自由出現変数v.1に項v.1'を代入した論理式Ｆ(v.1')と同等である。
帰納法とは、Ｆ(v.1)はv.1が０のとき成り立ち
更に、任意の数で成り立つときその数の後者でも成り立つならば
すべての数でＦ(v.1)が成り立つ、という意味である。

体系Ｐ.Ｅ.の「証明」とは、
公理と推論規則によって構成された論理式の有限列を意味する。
列の最後の論理式がＦであるような証明（論理式Ｆの証明と呼ばれる）
が存在するとき、Ｆは「証明可能」と呼ばれる。
論理式Ｆの否定が証明可能であるとき、Ｆは「反証可能」と呼ばれる。

>>188
Evalは万能関数といわれている。
つまり万能チューリングマシンと同じようなもの。

ところで>>186の例だが、もし
Eval(d("Eval(d())"))
だったらどうなると思うね？（笑）

哲板の常連になって１ヶ月たったので
そろそろ、コテハンを名乗ろうかと思います。
てなわけで、これからは「ぺん(ぺん)」で通します。
よろしくお願いします。

>>194
>Evalは万能関数といわれている。
ＬＩＳＰという言語にある関数なんですね。
いやー、まったく知らなかったです（汗
ＬＩＳＰといのは、やたらと括弧が多い、人工知能の研究用に開発された言語
ということを、耳学問で聞いてただけですから。
今は、Schemeとかいう言語があるようですが
一度使ってみたいですねえ。
理系のダチに頼んで、何とか手に入らないものか…

>ところで>>186の例だが、もし
>Eval(d("Eval(d())"))
>だったらどうなると思うね？（笑）
この場合、ゲーデル・パズルのＮ(Ｘ)が
ＸをＸ(Ｘ)ではなくＸＸに変換すると考えられるんですよね。
んでもって、EvalをＰとみなすと
ＰＮ(ＰＮ)すなわちＰ(ＰＮＰＮ)は"ＰＮＰＮ"を印字して停止するわけだから
"Eval(d(Eval(d())))"を実行して停止するわけですよね。

>>196
＞ＬＩＳＰという言語にある関数なんですね。

別に、LISP 特有の命令じゃないよ。Perl にもありますがなにか。

何でも実行してしまうので、外部から入力された値を直接 eval には
喰わせてはならないというのは常識でござる。

今更ながらの注文だけど、下付きの数字を表現するのに、ドットはやめれ。
とてもよみにくい。数式の最後にドットついてるだろ？そのドットや、
ドット記法のドットを想起させて非常につらい。

数学板の質問スレで推奨されている、v1 もしくは、 v_1 にしてくれ。

>>190
＞Ｌ6:充足するモデルが存在する。

モデル関係ないと思うが。「項 t と等しいものが存在する」ってことではないか？

さて、等号付き述語論理の公理系が出てきたわけだが、この公理系で、
別のスタイルの公理系では公理となる、

t=t (tは任意の項）

はどうやって証明出来るのでせうか？

1．∃v_i（v_i＝t)　L6　
2．a＝t　1から
3．a＝t⊃t＝t　1とL7から(X_1 v_i X_2をv_1＝t)　
4．t＝t

でいいんじゃないかな．ホントはもう少し丁寧にやった方が
いいけど，後は補足しておいてよ．

http://www.tigers-fan.com/~xxccxxc

女子中高生とHな出会い
　　ロリロリ児童とHな？
　　2チャンネルで超有名

>>199
>モデル関係ないと思うが。「項 t と等しいものが存在する」ってことではないか？
たしかに、モデルは関係ないですね。
ちょっと勇み足でした（汗
単に「等号を満たす値が存在する」といったところでしょう。

>t=t (tは任意の項）
>
>はどうやって証明出来るのでせうか？
練習問題として解いてみました。

>>200
1.から2.を導くのは、直観的には明らかなんですが、
純粋に公理と推論規則だけで導くのは、難しそうです。
というわけで、少し回り道の証明になりました。

★練習問題★
まず、任意のＦ，Ｇで
(Ｆ⊃Ｆ)，(〜〜Ｆ⊃Ｆ)，((Ｆ⊃Ｇ)⊃(〜Ｇ⊃〜Ｆ))
が成り立ちます。
証明はどの教科書にも載ってると思うので省略します。

v_iは項tに出現しない変数として
Ｌ7:(v_i＝t⊃(v_i＝t⊃t＝t))
v_i＝tをＦ1、t＝tをＦ2とすると
(Ｆ1⊃(Ｆ1⊃Ｆ2))・・・(32)
Ｌ2において、Ｆ,Ｇ,ＨにそれぞれＦ1,Ｆ1,Ｆ2を代入すると
(Ｆ1⊃(Ｆ1⊃Ｆ2))⊃((Ｆ1⊃Ｆ1)⊃(Ｆ1⊃Ｆ2))・・・(33)
規則１と(32),(33)より、((Ｆ1⊃Ｆ1)⊃(Ｆ1⊃Ｆ2))
規則１より、(Ｆ1⊃Ｆ2)・・・(34)
(34)の対偶が成り立つから、(〜Ｆ2⊃〜Ｆ1)
規則２より、∀v_i(〜Ｆ2⊃〜Ｆ1)・・・(35)
規則１とＬ4,(35)より、(∀v_i〜Ｆ2⊃∀v_i〜Ｆ1)・・・(36)
(36)の対偶が成り立つから
(〜∀v_i〜Ｆ1⊃〜∀v_i〜Ｆ2）
従って、(∃v_i(v_i＝t)⊃∃v_i(t＝t))
Ｌ6より、∃v_i(t＝t)・・・(37)
ところで、Ｌ5において、Ｆに〜Ｆ2を代入すると
(〜Ｆ2⊃∀v_i〜Ｆ2)
対偶をとって、(〜∀v_i〜Ｆ2⊃〜〜Ｆ2)
従って、(∃v_i(t＝t)⊃t＝t)・・・(38)
規則１と(37),(38)より
定理：t＝t
が証明された。

任意の論理式に対応したゲーデル数の関係式が算術的Ｅであることを示すため
すこしテクニカルな技法を用います。
（ゲーデルの証明では、帰納的関数を用いるところです）

今までは、いかにも形式的な議論だったわけですが
この辺から、ちょっと数学っぽくなります（笑

【ゲーデル数の関係式】
●def.　(x)Ｂ<b>(y)
b進法表記において数xが数yを「始める」とは、xのb進法表記がyのb進法表記の最初の切片であることを意味する。
数0は、0を除く数を始めない。
b進法表記において数xが数yを始めるとき、この条件を「(x)Ｂ<b>(y)」と表記する。

●def.　(x)Ｅ<b>(y)
b進法表記において数xが数yを「終える」とは、xのb進法表記がyのb進法表記の最後の切片であることを意味する。
b進法表記において数xが数yを終えるとき、この条件を「(x)Ｅ<b>(y)」と表記する。

●def.　(x)Ｐ<b>(y)
b進法表記において数yを始める数を数xが終えるとき、xはyの「部分」と呼ばれる。
b進法表記において数xが数yの部分であるとき、この条件を「(x)Ｐ<b>(y)」と表記する。

◆命題１◆
任意の数b≧2とn≧2に対する次の関係式は、すべて算術的Ｅである。
(x)Ｂ<b>(y)
(x)Ｅ<b>(y)
(x)Ｐ<b>(y)
(x_1＊<b>x_2＊<b>…＊<b>x_n)Ｐ<b>(y)


[証明]
(x)Ｂ<b>(y)⇔x＝y∨(x≠0∧(∃z≦y)(∃w≦y)(Pow<b>(w)∧(x・y)＊<b>z＝y))
(x)Ｅ<b>(y)⇔x＝y∨(∃z≦y)(z＊<b>x＝y)
(x)Ｐ<b>(y)⇔(∃z≦y)((z)Ｅ<b>(y)∧(x)Ｂ<b>(z))
したがって、関係式(x)Ｂ<b>(y),(x)Ｅ<b>(y),(x)Ｐ<b>(y)は全て算術的Ｅである。
更に
(x_1＊<b>x_2＊<b>…＊<b>x_n)Ｐ<b>(y)
⇔(∃z≦y)x_1＊<b>x_2＊<b>…＊<b>x_n＝z∧(z)Ｐ<b>(y)
より、関係式(x_1＊<b>x_2＊<b>…＊<b>x_n)Ｐ<b>(y)も算術的Ｅである。


（省略記法）
b＝13とおき、<b>を省略して、(x)Ｂ(y),(x)Ｅ(y),(x)Ｐ(y)と表記する。
関係式x＊<13>yは、xyと表記する。
関係式〜(x)Ｐ(x)は、(x)Ｐ~(x)と表記し
関係式(x_1＊<13>x_2＊<13>…＊<13>x_n)Ｐ(y)は(x_1x_2…x_n)Ｐ(y)と表記する。

【有限列】
任意の12種の記号による式Ｘ_1,Ｘ_2,…,Ｘ_nに対して
#Ｘ_1,#Ｘ_2,…,#Ｘ_n
はn順序対(Ｘ_1,Ｘ_2,…,Ｘ_n)の形式的な対応を表し、そのゲーデル数は「列数」と呼ばれる。
言い換えると、δが出現しない数n(13進法)の集合をＫ_11とおくと、記号#の出現しない全ての式のゲーデル数は、Ｋ_11の要素となる。
このとき、集合Ｋ_11が含む任意の数の有限列(a_1,…,a_n)に対して数δa_1δ…δa_nδを割り当てて、この数を(a_1,…,a_n)の「列数」と呼ぶ。

●def.　Seq(x)
数xが集合Ｋ_11の要素の有限列の列数であるとき、xを列数と呼ぶ。
xが列数であるという条件を「Seq(x)」と表記する。

●def.　x∈y
数yがxを要素に持つ列の列数であるとき、この条件を「x∈y」と表記する。

●def.　x＜<z>ｙ
xとyが要素である列の列数をzとおく。
この列において、xの最初の出現がyの最初の出現よりも早いとき
この条件を「x＜<z>ｙ」と表記する。

★命題２★
条件Seq(x),x∈y,x＜<z>ｙは、全て算術的Ｅである。


[証明]
Seq(x)⇔
(δ)Ｂ(x)∧(δ)E(x)∧δ≠x∧(δδ)Ｐ~(x)∧(∀y≦x)((δ0y)Ｐ(x)⊃(δ)Ｂ(y))
x∈y⇔Seq(y)∧(δxδ)Ｐ(y)∧(δ)Ｐ~(x)
x＜<z>y⇔x∈y∧y∈z∧(∃w≦z)((w)Ｂ(z)∧x∈w∧〜y∈w)


（省略記法）
式∀x(x∈y⊃(…))を(∀x∈y)(…)と省略し
式∃x∃y(x＜<w>z∧y＜<w>z∧(…))を(∃x,y＜<w>z)(…)と省略する。

【構成列】
●def.　Ｒt(Ｘ,Ｙ,Ｚ)
任意の式Ｘ,Ｙ,Ｚに対して、Ｚが(Ｘ＋Ｙ),(Ｘ・Ｙ),(ＸＥＹ),Ｘ'のときに限って
Ｒt(Ｘ,Ｙ,Ｚ)と定義する。
式Ｒtは「項の構成関係」と呼ばれる。

項の「構成列」は、式の有限列Ｘ_1,…,Ｘ_nであり、
列の要素Ｘ_i(i≦n)は変数または数値であるか、
あるいは、Ｒt(Ｘ_j,Ｘ_k,Ｘ_i)をみたす要素Ｘ_jとＸ_k(j＜i,k＜i)が存在する。
よって項の明確な定義は次のようになる。

●def.　式Ｘを要素にする項の構成列が存在するときに限って、Ｘは「項」である。


●def.　Ｒf(Ｘ,Ｙ,Ｚ)
任氏の式Ｘ,Ｙ,Ｚに対して、Ｚが〜Ｘ,(Ｘ⊃Ｙ),任意の変数v_iに対する∀v_iＸであるときに限って、Ｒf(Ｘ,Ｙ,Ｚ)と定義する。
式Ｒfは「論理式の構成関係」と呼ばれる。

論理式の「構成列」は、式の有限列Ｘ_1,…,Ｘ_nであり、
列の要素Ｘ_i(i≦n)は原子論理式であるか、
あるいは、Ｒf(Ｘ_j,Ｘ_k,Ｘ_i)をみたす要素Ｘ_jとＸ_k(j＜i,k＜i)が存在する。
よって、論理式の明確な定義は次のようになる。

●def.　式Ｘを要素にする論理式の構成列が存在するときに限って、Ｘは論理式である。

何か？
　　　

漏れは本当は、数学や論理はあんまし好きではないんですよね。
最近は他スレで遊んでばかりいますが
また気が向いたら、このスレでの勉強も再開します。

「不完全性定理と言われているものふぉど、永続的なものはない。」と、言うのは
　真ですか？　偽ですか？

Test

>>212
理論であって定理ではないと思われます。

マス

＞２１４
　不完全性理論とは　どういう理論ですか？

誰か問題といて。

誰か問題といて。

しばらく、勉強をほっぽり出して
よそのスレで遊んでばかりいましたが
もう少ししたら、また再開します。
よろしくお願いします。

久しぶりに勉強を再開します。
ようやく、ゲーデル数xの論理式は証明可能である
という関係式が出てきます。
この関係式が出てくると、不完全性定理まで、ほんのちょっとです。

ところで、他のスレで遊んでばかりいるので、漏れも煽られるようになりましたが
ゲーデルばかりやってても面白くないので
クリプキかカントなんかも読んでみたく思ってます。
しかし、恥ずかしながら、ドイツ語は厨房レベルなので
原書でカント読むのはしんどいです（汗
（そもそも、本業の勉強も、だいぶ遅れているのに
あまり哲学に耽ってもいられないし）
まあ、ぼちぼち考えときます。

【体系Ｐ.Ｅ.の構文論の算術化】
Ｐe(x)(ＥxはＰ.Ｅ.の証明可能な論理式)とＲe(x)(ＥxはＰ.Ｅ.の反証可能な論理式）にいたるリストを例示して、それそれの条件が算術的Ｅであることを証明する。
(Ｅxはゲーデル数xをもつ式Ｅ）

任意の数xとyに対して
(Ｅx⊃Ｅy),〜Ｅx,(Ｅx＋Ｅy),(Ｅx・Ｅy),(Ｅx|Ｅ|Ｅy),Ｅx',Ｅx＝Ｅy,Ｅx≦Ｅy
のゲーデル数を、順に
(x)imp(y),neg(x),(x)pl(y),(x)tim(y),(x)exp(y),s(x),(x)id(y),(x)le(y)
とおく。
これら８種類の関数は、すべて算術的Ｅである。

【体系Ｐ.Ｅ.の構文論の算術化(条件のリスト1)】
１．Ｓb(x)：Ｅxは添字の列である。
　　　　　　(∀y≦x)((y)Ｐ(x)⊃(5)Ｐ(y))　　/* 5:,のゲーデル数 */
２．Ｖar(x)：Ｅxは変数である。
　　　　　　(∃y≦x)(Sb(y)∧x＝26y3)　　　/* 26y3:(v[y])のゲーデル数 */
３．Ｎum(x)：Ｅxは数値である。
　　　　　　Pow<13>(x)
４．Ｒ1(x,y,z)：Ｒt(Ex,Ｅy,Ｅz)が成立する。
　　　　　　z＝(x)pl(y)∨z＝(x)tim(y)∨z＝(x)exp(y)∨z＝s(x)
５．Ｓeqt(x)：Ｅxは項の構成列である。
　　　Ｓeq(x)∧(∀y∈x)(Ｖar(y)∨Ｎum(y)∨(∃z,w＜<x>y)Ｒ1(z,w,y))
　　　/* Ｖar(y)∨Ｎum(y):項　(∃z,w＜<x>y)Ｒ1(z,w,y):項より構成される項 */
６．tm(x)：Ｅxは項である。
　　　　　　∃y(Ｓeqt(y)∧x∈y)　　　/* Ｅxの構成列が存在する */
７．f0(x)：Ｅxは原子論理式である。
　　　　　　(∃y≦x)(∃z≦x)(tm(y)∧tm(z)∧(x＝(y)id(z)∨x＝(y)le(z))
８．Ｇen(x,y)：変数wに対して、Ｅy＝∀wＥxが成立する。　/* 推論規則２ */
　　　　　　(∃z≦y)(Ｖar(z)∧y＝9zx)
９．Ｒ2(x,y,z)：Ｒf(Ｅx,Ｅy,Ｅz)が成立する。
　　　　　　z＝(x)imp(y)∨z＝neg(x)∨Ｇen(x,z)
１０．Ｓeqf(x)：Ｅxは論理式の構成列である。
　　　Ｓeq(x)∧(∀y∈x)(f0(y)∨(∃z,w＜<x>y)Ｒ2(z,w,y))
　　/* f0(y):原子論理式　(∃z,w＜<x>y)Ｒ2(z,w,y):論理式より構成される論理式 */
１１．fm(x)：Ｅxは論理式である。
　　　　　　∃y(Ｓeqf(y)∧x∈y)　　　/* Ｅxの構成列が存在する */

【体系Ｐ.Ｅ.の構文論の算術化(条件のリスト2)】
１２．Ａ(x)：ＥxはＰ.Ｅ.の公理である。
　　　　　【公理について】で算術的Ｅであることを証明する。
１３．Ｍ.Ｐ.(x,y,z)：ＥzはＥxとＥyから推論規則１に導かれる。
　　　　　　y＝(x)imp(z)
１４．Ｄer(x,y,z)：ＥzはＥxとＥyから推論規則１に導かれるか、Ｅxから推論規則２に導かれる。
　　　　　　Ｍ.Ｐ.(x,y,z)∨Ｇen(x,z)
１５．Ｐf(x)：ＥxはＰ.Ｅ.の証明である。　　　/* Ｅxは公理の構成列である */
　　　Ｓeq(x)∧(∀y∈x)(Ａ(y)∨(∃z,w＜<x>y)Ｄer(z,w,y))
　　　/* Ａ(y):公理　(∃z,w＜<x>y)Ｄer(z,w,y):公理より構成される論理式 */
１６．Ｐe(x)：ＥxはＰ.Ｅ.で証明可能である。
　　　　　　∃y(Ｐf(y)∧x∈y)　　　/* Ｅxの構成列(証明図)が存在する */
１７．Ｒe(x)：ＥxはＰ.Ｅ.で反証可能である。
　　　　　　Ｐe(neg(x))

【公理について(1)】
条件Ａ(x)が算術的Ｅであることを示すために、Ａ(x)を19の部分に分けて考える。
ここで、n≦7に対しては、Ｅxが公理形式Ｌnの公理である条件をＬn(x)で表し、n≦12に対しては、Ｅxが公理形式Ｎnの公理である条件をＮn(x)で表す。

グループ�T:命題論理の公理形式(Ｌ1〜Ｌ3)
Ｌ1(x)の条件について考える。
ＥxがＬ1の公理であるときに限って、Ｅx＝(Ｅy⊃(Ｅz⊃Ｅy))を満たす論理式Ｅy,Ｅzが存在する。よって、条件は
(∃y≦x)(∃z≦x)(fm(y)∧fm(z)∧x＝(y)imp((z)imp(y)))
公理形式Ｌ2(x),Ｌ3(x)についても同様である。

グループ�U：第１階術語論理(等号を含む)の公理形式(Ｌ4〜Ｌ7)
Ｌ4(x)の条件について考える。
式：∀Ｅy((Ｅz⊃Ｅw)⊃(∀ＥyＥz⊃∀ＥyＥw))　のゲーデル数をψ(y,z,w)とおく。
関数ψ(x,y,z)が算術的Ｅであることは明らかである。よって、
var(y),fm(z),fm(w),x＝ψ(y,z,w)
を満たす数y,z,w(すべてx以下)が存在するときに限ってＬ4(x)は成立する。
残りの公理形式Ｌ5〜Ｌ7についても同様である。

【公理について(2)】
グループ�V：算術の公理形式(Ｎ1〜Ｎ11)
公理形式Ｎ1からＮ11は、それそれが１個の公理を含むだけであり、よって、i≦11に対して公理Ｎiのゲーデル数がｇiであるとき、Ｎi(x)はそのまま条件x＝ｇiを示している。

グループ�W：帰納法の公理形式
式：∀Ｅy(Ｅy＝v_1'⊃∀v_1(v_1＝Ｅy⊃Ｅw))　/*　Ｆ@(v_1')　*/
のゲーデル数をz＝ψ(w,y)
式：∀Ｅy(Ｅy＝0⊃Ｅw)　/* Ｆ@([0]) */
のゲーデル数をz0＝ψ0(w,y)とおく。
関数ψ(x,y),ψ0(x,y)が算術的Ｅであるのは明らかである。
ここで、式：(Ｆ@([0])⊃(∀v_1(Ｅw⊃Ｆ@(v_1'))⊃∀v_1Ｅw)))
のゲーデル数をx＝φ(z0,z,w)とおくと、
関数φ(x,y,z)が算術的Ｅであることは明らかである。
従って、Ｎ12(x)の条件は
fm(w),(2653)Ｐ(w),(92653)Ｐ(w),var(y),z＝ψ(w,y),z0＝ψ0(w,y),x＝φ(z0,z,w)
/* (2653)Ｐ(w):([v_1])Ｐ(w)　(92653)Ｐ(w):([∀(v_1)])Ｐ(w) */
を満たすw,z0,z,y(すべてx以下)が存在することである。

以上より、Ａ(x)の条件は次のようになる。
Ｌ1(x)∨Ｌ2(x)∨…∨Ｎ12(x)
Ａ(x)は算術的Ｅであるのは、明らかである。


◆命題３◆
条件１〜１７はすべて算術的Ｅである。

お見事！！

今日の朝日新聞　be の「読み・解く」小泉批判
　
「構造改革なければ景気回復なし」
「拉致問題の進展なくして日朝交渉の再開なし」
　あのヒトの言葉も、いつも排中律だ。前提と結論のすりかえ、証明不能な循環論理なのだが、本人も永田町も、その背理に気づく論理的な思考能力を欠く。
　勉強せんかい。バートランド・ラッセルとアルフレッド・ホワイトヘッドが１９１０年に書いた『プリンキピア・マテマティカ』（数学原理）で、とうに禁じている論理操作だ。
　「ある集合のすべて（の要素）を含むものは、何であれその集合の一員であってはならない」
　裏返しに言えば、「ある集合が全体を持つと仮定すると、その全体によってしか定義できないような要素を含む場合、その集合は全体を持たない」（プリンキピア・マテマティカ序論第２章）。
　彼が食いちらかした改革とやらも、全体を持たない。


『選択』編集長　阿部重夫は、ゲーデルから見てどうなんでしょう。

「構造改革」は、不完全である。
　「景気回復」は、不完全である。
　　「不完全なければ、不完全なし。」と、言うのは
　　　虚ですか？　実ですか？

　実です。
　　何か？

ご名答！！！！！

流石、世論を喚起すことにおいて、「実」がある。
　何か？

ようやく復活しましたね。初心者です。
相変わらず知的好奇心が旺盛で結構なことです。
僕ももう一段階上に登るための計画を立てております。
そんな暇はないはずなのですが・。
浮気もいいですが、お互い本命の方も忘れないよう
注意しましょう。（と自分に言い聞かせる（笑））
このスレ期待しています。

ご期待に、沿えるよう頑張ります！！！

最近、あまりにサボりまくっているんで、沈没寸前になっていました。
とりあえず、ageときます。

age

ゲーデルの「不完全性定理」は、つまるところヨーロッパの諸科学が近代的知性
による形式化によって打ち立ててきた理論を、その根底から揺り動かすものなのである。
今、〈知〉の最前線を切り開きつつある人々らの作業は、三浦雅士言うところの「
美術についての美術」(「自己についての自己」「言葉についての言葉」)とよく似ている。

すっごい久しぶりに更新します。
ただし、今は、現象学や言語哲学などのほうに
興味が向いているので、今後も続くのかは微妙なところです。

【体系Ｐ.Ｅ.におけるゲーデルの不完全性証明】
体系Ｐ.Ｅ.の証明可能な論理式のゲーデル数の集合をＰe=(x|Ｐe(x))、
反証可能な論理式のゲーデル数の集合をＲe=(x|Ｒe(x))とおく。

体系Ｐ.Ｅ.の構文論の算術化(条件のリスト2)の１６、１７により
ＰeとＲeが算術的Ｅであることが示された。
言語ＬＥにおいて、これらの集合を言及する論理式を
それぞれＰ(v_1),Ｒ(v_1)とおくと、
論理式〜Ｐ(v_1)はＰeの補集合Ｐe~を言及する。

このとき、第二章の補助定理１（もし集合Ａが算術的Ｅであれば、集合Ａ*も算術的Ｅである）により、集合Ｐe~*を言及する論理式Ｈ(v_1)…(32)が存在する。
そして、第二章の定理１の証明(すべての算術的Ｅ集合Ａに対して、Ａのゲーデル文が存在する）により、式(32)の対角式Ｈ@([h])は集合Ｐe~のゲーデル文である。

従って、Ｈ@([h])はＰ.Ｅ.で証明可能でないときに限って真である。
体系Ｐ.Ｅ.が正確である以上、式Ｈ@([h])は真であるにもかかわらずＰ.Ｅ.で証明可能でなく、式〜Ｈ@([h])は偽である以上、これもＰ.Ｅ.で証明可能でない。
（証明終り）

◆定理１　公理体系Ｐ.Ｅ.は不完全である◆

■■コメント■■
定理１は、その証明が最も単純な不完全性定理である。
この単純化は、タルスキーの真理集合を用いたことと、
モンタギューとカリッシュの第１階術語論理(変数の自由出現に項を代入する表記法を用いない、等号を含む公理形式）を用いたことに起因している。
より、標準的な算術の公理体系における不完全性定理を証明するためには
論理式の自由出現変数に項を代入する操作を算術化しなけらばならない。

（＾＾）

あなたが興味関心をもつ対象について、ロゴス・ﾌﾟﾙｰラルあるいは、ロゴス・ゼロの現れを見出し、その現象について記せ。と聞かれたら皆さんはどう答えますか？？

お邪魔してすみませんが、ハオ・ワンの『ゲーデル再考』を\6.5k→\4.5で買いました。
正しい選択でしょうか？あと文系人間がゲーデルを口にするのはやはり禁句でしょうか？

>>242
ハオ・ワンは読んだことないので、なんとも言えません。
たしか、ゲーデルの思想的な部分に言及してたと思いますが
漏れ的には、ゲーデルのプラトニズム的数学観は、
ちょっとキツイ感じです。

>あと文系人間がゲーデルを口にするのはやはり禁句でしょうか？
文系の人間がゲーデルを大々的に使ったのは
行人たんの「内省と遡行」が有名ですが
今読み返すと、かなりの大風呂敷で無理があります。
あまり過大評価せずに、数学基礎論の中での位置づけを
きっちり把握した上でなら、
口にだしてもそんなに叩かれないのではないでしょうか。
（とはいっても、希望的観測ですけど）

ちなみに、このスレで読んでいるスマリヤンの他の本では
『哲学ファンタジー』が文系向けで面白いです。

（＾＾）

>>243
ぺん(ぺん)さん、丁寧なレスありがとうございました! 空谷ｻﾝ、ちとシッタカ入ってる気もしますが・・・。(^_^;)
もひとつついでに、Ｒ.ペンローズが意識の作用プロセスを量子力学で説明しようとした
際に、ゲーデル(不完全性定理)に言及していたと思いますが、もしご存知なら、ぺん(ぺん)さんは、その辺りどう評価しますか？
たしか「意識はマイクロチューブルにおける波動関数の収縮である」とかいうことの基礎理論だったかなぁ・・・。
ゲーデルが絡むのは、数学的理論の核心なのですが、今ひとつ分からなかったという記憶があります。
別の人間にいわせれば、ペンローズがゲーデルの不完全性定理を良く理解していないだけとか・・・。(^_^;)
ご存知でしたら、想うところをちとお聞かせくださいませませ!

>ペンローズがゲーデルの不完全性定理を良く理解していないだけとか

これが定説らしいよ知らないけど

>>264
レスありがとうございます。
人間の意識の超越的存立構造が、チューリングマシンあたりと絡むのだったかなぁ・・・。
漏れもその辺りの数学的証明に基づく理論展開が良く分からないんで、専門の方噛み砕いて教えてくんろ。(-_-;)
眼からウロコ落としてみたいんで・・・。(^^)/~~~

↑264×→>>264○でした。めんごでやんす！

↑トートロジってどーする。264×→>>246○でした。たびたびめんごでやんす！

>>243
＞漏れ的には、ゲーデルのプラトニズム的数学観は、

ゲーデル自身は自分の数学観はぷらとにずむでないといっているぞ。

参照：K・ゲーデル「ラッセルの数理哲学（だったかな）」翻訳あり。

だいたい、「「数学の原理」なんて書いたあんたにぷらとにず
呼ばわりされたくない」というもの。要するに、数学対象の王国が
リアルに存在すると信じるタイプのプラトニズムをゲーデルは信じ
ていないことが分かる。

>>250
数学の哲学に関しては、まったくのドキュソなので
間違って理解しているかもしれません。
ただ、『リーディングス　数学の哲学　ゲーデル以降』を読む限り
「ラッセルの数理論理学」において批判しているのは
タイプ理論における構成主義的態度や無クラス理論だと思います。
逆に、ラッセルの論理に対する実在論的傾向は
賛同しているように見えますが・・・

ともあれ、
「数学対象の王国がリアルに存在すると信じるタイプのプラトニズム」
は、たしかに信じているわけではないでしょうね。
もっと弱められた実在論、上記の本によれば
「プラグマティックな考慮に基づく全体論的実在論」
とでもいうような実在論を信じていたようです。
そういう点では「プラトニズム的数学観」というのは言い過ぎで
「実在論的数学観」とでもしとくべきでした（汗

>>243

ハオ･ワンの本は枕にはちょうどいい厚さです（ｗ
厚さでは、ホフスタッターの本も同じくらいですけど
これは枕に使うには面白すぎる（ｗ

>>245

ペンローズの本は、眉に唾をつけながらお読みください。
ゲーデルの仕事の説明はともかくとして、これが意識の
存在証明になるという理解は、いかがわしい。

>>250-251

ゲーデルはプラトニストだと思いますよ。
ラッセルの言に対する意見に関していえば、
彼がラッセルに対して好意を持っていなかった
と理解すべきでしょう。

>>252
レスありがとうございました。
とりあえずアドバイスを応用して、『皇帝の新しい心』と『心の影』を枕にできるか
試してみることにしまつ。(^_^;)ついでに『リーディングス　数学の哲学　ゲーデル以降』も
持ってるんでコレも敷いてみよかな・・・。
でも全く勝ち目のないペンローズのドンキホーテ的な野心には、イケイケと応援したくなりまつ。
医者達の間で講演した時には、まったく理解されなかったそうでつ。脳よりもﾏｲｸﾛﾁｭｰﾌﾞﾙの多い腸は考えるんかい！とつっこまれたとか・・・。
そういえばペンローズは、参照対象世界のトリッキーな循環の中で、「数学対象の王国がリアルに存在すると信じるタイプのプラトニズム」観の
持ち主であったんじゃなかったかな？

>>254
ペンローズって、実は読んだことないんですよ（汗
ただ、聞き齧った限りでは
ペンローズの「トリッキーな循環」というのは
空谷が「言語・数・貨幣」などで示したような
メタ・レヴェルとオブジェクト・レヴェルの循環構造というのと
結局、同じ構図のように思えるのですけど。
ていうか、「トリッキーな循環」をそのまま図式化すると
「クラインの壷」になるような・・・

どうなんでしょう、
三つ巴的な循環構造でなんでも説明できちゃうという
思考パターンが最初にあって
（容易なラカン解釈なんかも当てはまるかもしれません）
そこにたまたまゲーデルの不完全性定理が使えそうだというので
一時期ブームになったというのが、実態のような気がします。

>>255
レスありがとうございました。
世界(存在)を循環構造にされると、じゃあ真の実在の最終審級はどこなの？とつっこみたくなりますが･･･(^_^;)
漏れは空谷は持ってるけど、読んでないのでした。なんかオリジナルより、変奏が多いのかなという気がして・・・。
あと前に読んだ『フランス現代思想とは何か？』という本の中に、「私はラカンが何をいいたいのか解らない。なぜなら彼の思想を理解できるのは、彼自身と神のみだからである。」
というような箇所があって、禿同と共に爆笑しますた。
「クラインの壷」! 浅田タンの『構造と力』を思いだすなぁ･･･。

>>254
ゲーデルとﾏｲｸﾛﾁｭｰﾌﾞﾙは無関係だよ。
>>255
＞（参照対象世界の）トリッキーな循環というのは
＞メタ・レヴェルとオブジェクト・レヴェルの循環構造
＞というのと結局、同じ構図のように思えるのですけど。

そうだよ。ただ、間にプラトン世界とかいうものを紛れ込ませたに過ぎない。
だから三つ巴である必要はない。循環がミソ。
>>256
＞真の実在の最終審級はどこなの？
無い。それがゲーデルの結果

>>257
レスありがとうごさいました。
もちろんﾏｲｸﾛﾁｭｰﾌﾞﾙとｹﾞｰﾃﾞﾙは無関係と思います。
意識の存在証明を、数学的に取り扱おうとする時、ｹﾞｰﾃﾞﾙを絡めたというところでつよね。
その辺はやはりﾍﾟﾝﾛｰｽﾞが、流行を取り入れた程度の評価でＯＫなのでしょうか？
あと最終審級は、やっぱないんスか。あーここは、どこ？私は誰？
ついでに、コーヘン(コーエン？)が、選択公理を導入することで、不完全定理を失効させたと
聞いたことありますけど、それは本当でしょうか？
『アメリカの数学者』という本には、コーエンが、生前ゲーデルも自分の理論に納得したとありましたが･･･。(^_^;)
そこら辺は、これもまた真の解答の無い解釈次第なのでしょうか？

＞ついでに、コーヘン(コーエン？)が、選択公理を導入することで、
＞不完全定理を失効させたと聞いたことありますけど、それは本当でしょうか？

まったくの誤り。

コーエンが示したのは選択公理の独立性証明。
つまり選択公理を満たさない集合論のモデルの構成。
不完全性定理は関係ない。
ちなみに、ゲーデルは、その昔、選択公理の無矛盾性証明をやった。
これは選択公理を満足するモデルの構成。

245にいっておくが、不完全性定理が失効できると思うのは
証明を知らぬ天然ヴァカだけだ。

>>258
数学ドキュソの漏れが説明しても眉唾ものですから
ここを参照して下さればいいと思います。
ttp://members.tripod.co.jp/nbz/ref/hprogram.html

あと、「不完全定理を失効させた」わけではないけれど
超限帰納法を用いることによって、ペアノ算術の無矛盾性は証明されます。
それから二階ペアノ算術になると範疇性とか
まあいろいろ難しい話がでてくるのですが
そこら辺は、詳しい人に解説キボンヌ

ﾄﾞｷｭｿは無矛盾性にこだわる（ｗ

>>259-262
レスありがとうございました。漏れ自身は、天然DQNなので、皆さんの解説？？？という感じです。
へー、そうなんだと改めて世界の広さを感じました。お邪魔してなければいいけど。(^_^;)
ということは、漏れが読んだコーエンの箇所(『アメリカの数学者たち』)は記憶ちがいかぁ…。
>>262
多分無矛盾であることは、数学的世界観として完全に美的だからなのではないでせうか？
すべての数学者たちの見果てぬ夢・・・。ヒルベルト先生、まんせー！

>>263

いや、単純に、「無矛盾であること」と
「無矛盾であると証明できること」
の区別のできないﾄﾞｷｭｿだけがこだわる
ことでしょう。

それが証拠にゲーデル以後専門家は
そんなヴァカなことにこだわらなくなった。

>>246
成る程、やはり数学的思考の厳密性は奥が深いのですね･･･。(^_^;)

[From DQS To The Smartest People]　
ちと遡って、世界(存在)の真の実在の最終審級の不在、もしくは世界の無根拠性を巡って素朴な疑問があるので教えてください。
ウディ･アレンの『霧と影』という映画のワンシーンに、
「時々僕は、この世界のすべての出来事が床屋の店先で眠っている犬の夢の中の出来事に思えるんだ･･･」というような台詞があったのですが、
究極的な実在の根拠がないとすると、我々が生きているという事実が、「犬の夢の中の出来事」ではないことを、自己言及のパラドックスを回避して
完全に証明する手立てはあるのでしょうか？
それともそんなことは、あまりにも自明であるが故に、証明なんぞは無前提に棄却されるのでしょうか？(デカルト的コギトのように。)

あと>>241の命題は何故放置されているのでしょう？
(命題なのではなく、単にそれ風のﾈﾀなのかナ？？それすら解らんDQSな漏れなのでした･･･。)

究極的な実在には根拠がない。

夢は覚めることによって夢だと気づく。
夢でないなら覚めることはない。

覚めるならば、覚めると分かる。
しかし覚めないならば、覚めないとは分からない。

>>266
レスありがとうございました。
ただ反証として、子供の頃、目覚めたつもりでトイレに行ってションベンしたら見事におねしょしていたということがありました。(^_^;)
目覚めていることを決定する最終審級もなかったという驚愕の事実！ 夢かウツツか？ これはいかに？？？

[From DQS To The Smartest People]　
あともう少しこのテーマを掘り下げさせて下さい。禅の公案風ですが･･･。(^_^;)
ひとつには目覚めたる意識作用(主観性)において、目覚めたる意識状態を決定しようとすると、
ここには必然的に自己言及のパラドックスが発生していると思うのですが･･･。
つまり「意識作用(主観)が、意識作用(主観)を決定する」という、
ｻﾌﾞｼﾞｪｸﾄﾚﾍﾞﾙとｵﾌﾞｼﾞｪｸﾄﾚﾍﾞﾙの自己撞着的な無限循環の状態です。
しかしながらつまるところ、我々は究極的なリアリティを求めようとした場合には、
そうしたサーキットを無限循環するより他にないのでしょうか？
(それとも反省によって取り出され客体化した意識は、もはや既に主観ではない!？)

更に真の実在の最終審級の不在を宣言しているのが、私の〈今・ここ〉の現ｰ存在の意識作用(主観性)ならば、
それこそがまさしく最終審級となってはいないでしょうか？？？(ちとコペンハーゲン解釈風かナ！？)
(別の位相から眺めれば、この問題のすべての過程が言葉で表されているのなら、言語記号の自己生成性に解答を求めることも可能でしょうが･･･)

最終審級が不在である、と同時に私の〈今・ここ〉の現ｰ存在の意識作用(主観性)がそれを決定しているならば、
世界はの究極リアリティは、真/偽の決定の不可能な彼岸にあり(或いはそのｶﾃｺﾞﾘｰを超越してしまい)、
結局は信念体系の問題(あるいは言語によるの関係の第一次性)に帰結する気がするのですが･･･。
となると、解釈学的現象学あたりが、究極のリアリティへ至る論理の王道になるのかナ？？？ ん、何か腑に落ちないような・・・。
いやいや、究極の一点の無い諸点の相互作用か・・・。ﾌﾞﾂﾌﾞﾂ･･･。(-_-;)
HELP ME！

＞意識作用(主観)が、意識作用(主観)を決定する

いま始めて意味のあることを言ったな（ｗ

そもそもｻﾌﾞｼﾞｪｸﾄとｵﾌﾞｼﾞｪｸﾄの区別はない。

「私の〈今・ここ〉の現ｰ存在の意識作用(主観性)」

それしかない、最初も最後もない。

それは信念ですらない。
疑おうとしても疑うことのできないものだからだ。
これこそが神秘であり奇跡なのだ。

>>268
あっ、すみませんいつも意味なくて。でも真なる意味も決定不能では！?
すべては同一平面上の戯れの儚さとか・・・えへへ。(^_^;)
うーん、つまるところ語り得ないことには、口を閉ざすべきである、なのかなぁ･･･。
あとデリダは、ゲーデルに言及してまつかぁ？

>>269
＞でも真なる意味も決定不能では！?

そう。

（沈黙）

わーお！
ちなみに、そこから導き出されるべき哲的姿勢学は、
�@すべては虚しい･･･(ゴータマ・ブッダ)
�Aイケイケどんどん！！！(ニーチェ＆ファイアアーペント)
どちらでしょう？ 漏れはその間をガタガタゆれてまつが･･･(^_^;)

>>271

語り得ないことは語り得ない（ｗ

言葉ですべてを語ろうとすることが虚妄だからといって
すべてが虚妄であることにはならないだろう。

私はただ日々を生きる。（荘子）

>>272
タオ！でつか。その姿勢やよしでつね。
天地は我と並び生じ、万物は我と一たり。(荘子)！
でも、プラトン(あれソクラテス師匠の方？)はただ生きるのではなく、より良く生きるのだと言われたとか？
あ、ゲーデルでプラトン的世界観はＮＧかぁ！おあとがよろしいようで！

>>262
竹内外史やゲンツェンはどきゅんなのかよ？

然り!!!

>>275

ちょっと補足。

無矛盾性を示そうという動機そのものはＤＱＮだが、
実際に示された証明に関しては、当人の思惑とは
異なる意味で意義がある。

　　　

おっと、保守age

（＾＾）