• ベストアンサー
  • 困ってます

ゲーデルの不完全性定理に現れる決定不能命題の数学的具体例を教えてください

最近、クルト・ゲーデルにはまっている者です、これが、なかなか難しくて困っています、ゲーデルが不完全性定理で表現した「真であるにもかかわらず証明できない」と言われる決定不能命題は、メタ数学を使って、A≡¬Bew(「A」)などなど、これ以外にも色々な表現方法で表されています、  しかし、具体的に、これを数学の中に表すスキルを私はもっていません、京大の林晋先生は、以前、掲示板上で簡単に決定不能な式を簡単にチョコチョコと作って、紹介していましたが・・・、忘れてしまいました(T.T)バカです。    どなたか決定不能な命題を数学上に作り出せるようなスキルが身につく書籍などを知っている方はおられませんでしょうか    それから、いまいち、抽象的で分かりにくい決定不能命題を数学的(メタ数学でなく)に表現した実例を一つでも知っている方はいませんでしょうか、私は数学的知識は大変乏しいのですが、どんな難しい数学的な実例でもかまいませんので、どなたか教えてください、また、どのような文献からその命題を知ったのか教えていただけるとさらにありがたいです。どうかよろしくお願いします。

共感・応援の気持ちを伝えよう!

質問者が選んだベストアンサー

  • ベストアンサー
  • 回答No.2

後半について。僕も初心者ですが。 まず、何かの数学的命題が「独立」という為には、言語と公理系を決めねばなりません。 どういう言語上で、どういう公理から独立なのか、ということです。 言語は普通は一階述語論理ですよね。(これには異論があるかも知れません。二階算術の公理系に対しても、独立命題が見つかっているようです。下のURL参考) 公理は、いろいろありますが、有名なのはZFC(集合論の公理系)とPA(算術の公理系。ペアノの公理系)ですよね。 ZFC上独立な命題は、巨大基数公理たちなど沢山あるでしょうが、有名なのは#1の方の仰るように、連続体仮説ですね。(コーエンの仕事) PA上独立な命題は、有名なのはパリスとハーリントンの定理で示された、ラムゼーの定理の一変種ですね。その仕事以降、他にも色々見つかっているようです。 ZFCというのはZF(ツェルメロ・フレンケルの公理系)に、AC(Axiom of Choice 選択公理)を付け加えたものですが、ZF上ACは独立であることが、ゲーデルによって証明されています。 僕の知っているのはこんなところです。

参考URL:
http://members.at.infoseek.co.jp/nbz/ref/hprogram.html

共感・感謝の気持ちを伝えよう!

質問者からのお礼

なるほど、グラフ理論の中に秘密めいた定理が存在していたとは知りませんでした、僕の知ってるグラフ理論はケーニヒスベルクに毛が生えたぐらいですから・・・ 何か変な妄想になってしまいますが・・集合を一つの数とみなし(皆さんが言っている巨大基数の事だと思います)それらに、加減乗除を定義して新たに何かの世界を発見できる可能性がある様な感覚がしてしまいます、おもしろいです、 URLは大変ありがとうございました、ものすごく知的栄養を補給できました。

その他の回答 (4)

  • 回答No.5

No.3です。補足します。 決定不能命題の具体例を、という御質問に対して: 基礎的な事柄で「公理」になっている命題の中に見つけることが出来ると思います。 幾何学の「平行線の公理」は歴史的に最も有名なものではないでしょうか。非ユークリッド幾何学が発展しましたから。 算術の公理の中でも、加算や乗算の「交換法則の公理」は、分かりやすい例として挙げられると思います。他の基本公理から正否が決定できません。そして、非可換代数が発展しました。 集合論では、他の回答者さんのご指摘にもある通り、幾つもありますね。そもそも、最小の超限基数(いわゆるアレフゼロ)の存在は有限基数(自然数)からは普通決定できません。最初の到達不能基数ですから。超限基数を認めることから始まった集合論で近年巨大基数の公理の検討が盛んなのも興味深いです。 少し注意して探せば、あまり難しくない(歴史的に議論済みの)決定不能命題は結構見つかるのでは....

共感・感謝の気持ちを伝えよう!

  • 回答No.4

#2です。 ZFC集合論上で、ほとんどの数学が展開できることから、 ZFC上独立な命題は、ほとんどの数学者から、「数学から独立な命題」とみなされるようです。 一言補足まで。

共感・感謝の気持ちを伝えよう!

質問者からの補足

と言う事は・・・決定不能命題がたくさんあると言う事ですか・・・怖い・・・

  • 回答No.3

“「真であるにもかかわらず証明できない」と言われる決定不能命題”というような言い方は、誤解を招きやすいので使わない方が良い、と野崎昭弘氏が注意を促されています。(『不完全性定理』ちくま学芸文庫版p242脚注) 「真」と分かっているのだったらその命題は証明されているはずなのに、それが証明できない、とは?...と「突っ込み」がはいりかねませんね。 「連続体仮説」も、ZFC公理系では真偽が決定不能というだけで、選択公理を否定した公理系を採用した集合論においては、偽と決定可能です。

共感・感謝の気持ちを伝えよう!

質問者からのお礼

回答ありがとうございます、ん~確かに、誤解を招く表現ですよね、 「真であるにもかかわらず証明できない、偽であるにもかかわらず証明できない」≠「その命題は真または偽である」と言う訳ですね。 排中律を認めないと、背理法が使えないから、ゲーデル論理式を導けなくなってしまうので、言葉上正確でなくなってしまうので、それもまた問題のような気がしてしまいますが・・・・ 一般連続体仮説(GCH)はZFが無矛盾と言う条件を仮定した場合、独立だと証明されていますよ

  • 回答No.1
  • proto
  • ベストアンサー率47% (366/775)

一番有名なのは連続体仮説。

共感・感謝の気持ちを伝えよう!

質問者からのお礼

最初に手をあげてくださってありがとうございましす

関連するQ&A

  • 厳密に数学的なゲーデル命題について

    高橋昌一郎さんの「ゲーデルの哲学」によると、1977年にジェフ・パリスとレオ・ハリントンにより、自然数論において厳密に数学的なゲーデル命題が発見された、とあります。 どのような命題か教えていただけないでしょうか。 または、それを日本語で説明している資料のありかを教えていただきたいと思います。よろしくお願いいたします。

  • ゲーデルの証明不能命題

     不完全性定理(形式的体系においてその公理と推論規則を使って証明も否定もできない論理式Aが存在する。)にいう論理式Aには例えばどんなものがあるのでしょうか?  いまだ解かれていない数学上の難問がありますが、これらが論理式Aであるかどうかは、結局のところ証明できた時点でしか判定できないのでしょうか。

  • この命題は証明できないについて

    ゲーデルの不完全性定理などの話の中で上がる、「この命題は証明できない」の矛盾について、どこが矛盾になるのかよくわかりません。 定義的な読み違いだと思うのですが、自己言及のパラドックス(床屋の〜とか嘘つきの〜)については納得というか理解ができます。 例えば嘘つきのパラドックスでは「私は嘘つきである」という発言が正なら嘘をついているので正直者ということに、偽なら正直者のはずが嘘つきと嘘をついている、と矛盾が生じます。それはわかります。 この命題は証明できない、の場合も同じように考えるのだということはわかるのですが、「この命題」をAと表記したときに、「Aが証明できない」が正であれば「Aは証明できない」ということを「証明できる」ということになります。 「Aが証明できない」を偽だとすると「Aは証明できる」ことになります。 ここまではよいのですが、これは数学的な話であり、正の「Aが証明できないことを(BやCなど別の定理を使って)証明する」ことは可能な気がしますし、偽の「Aは間違いである」と結論付けることにも問題がない気がします。 嘘つきのパラドックスとの差に、他の考え方(上記例で言うとBやCといった命題以外の定理)の持ち込みがあるので、これが読み違いというか悩みの原因だと思うのですが…。 持ち込みがなく、命題のみで行う場合(=自己言及のパラドックスに陥る場合)がゲーデルの不完全性定理に当てはまる場合であり、持ち込みがあり矛盾なく証明または反証ができる場合が解決可能な定義(または予想)という認識であってますか…?? 数学学んでるわけではなく、単純に目に触れて興味持っただけのド素人です。学校教育から離れて久しいですので、ものすごくわかりやすい説明や解説を求めております。。。

  • 数学に使う言葉の英語表現について

    数学に使う言葉で幾つか英語で表現したいものがあるので教えてください。 なるべく自然で短い英語で表したいです。 [1] a=b=c=d a,b,c,dが等しい [2] a=bまたはb=cまたはc=a a,b,cのいずれか2つが等しい。 [3] aは~(条件)を満たす。 [4] ~の定理より [5] ~(命題)が成り立つ [6] t=x^2+1とおく 少し多いですが、教えてくださるとありがたいです。

  • ゲーデルの不完全性定理って?

    いろいろ調べたんですがいろいろあって意味不明です。 数学の定理なんですか?これ。

  • ゲーデルの不完全性定理について

    ゲーデルの不完全性定理について ネットサーフィンをしていたときに、たまたま、ゲーデルの項目を見つけました。 当方、数学は素人なのですが、 ゲーデルの不完全性定理(ある公理系の中には、真偽を明確にできない命題が存在する) を僕たちが生きるこの世界、この宇宙にあてはめて考えると、 この世の中には、論理的には正しいとも間違っているとも証明できないことがらがあるということなのでしょうか。

  • ゲーデルの不完全性定理

    ゲーデルの不完全性定理の証明のアイデアが知りたいと思い、適当な入門書(基礎論の教科書ではないです。)を読んでいるのですが、 まず、定理の主張が「形式的体系Tで通常の自然数を含み、強い意味で無矛盾であり、そこにおける公理や推論規則は帰納的に定義されているかまたはその数が有限であるようなもの、においては文GでGも¬Gも証明できないものが存在する。」 とあるのですが、形式的体系Tがなにを意味しているのかがよくわかりません。これは、形式的と書いてあるのだから文字通り「意味を考えない記号の世界(記号の集まりと、記号を並べて得られる列を変形するいくつかの規則)」と考えればよいのでしょうか? それで、もう一つ質問があるのですが、 まず、準備として記号 ¬,∧,∨,→,∃,∀,(,),0,',+,×,=,x,y,zを用意して、 x,y,zを変数記号と呼びます。 それで、項を次のように定義します。 (i) 0,x,y,zは項。 (ii) t,sが項であるとき、'(t),+(t,s),×(t,s)は項。 (iii)このようにして得られるものだけが項。 (iV)'(t),+(t,s),×(t,s)を簡単にそれぞれt',t+s,t×sと記したりする。また、0',0'',0''',…をそれぞれ1,2,3,…と記す。 また、項tを上の記号の括弧としてではなく、見易さのための補助記号としての(,)を用いることにより、しばしばt(x,y,z)と記したりする。 次に論理式を次のように定義します。 (i)t,sが項のとき、t=sは論理式。 (ii)φとψが論理式でxが変数記号のとき、(¬φ),(φ∧ψ),(φ∨ψ),(φ→ψ),(∀xφ),(∃xφ)は論理式。 (iii)このようにして得られるもののみが論理式 (iV)見易さのために括弧を適当に省略して論理式を記すこともある。 以上により、与えられた記号列が項か論理式かそれ以外のものか判定できるようになります。 準備した記号¬,∧,∨,→,∃,∀,(,),0,',+,×,=,x,y,zを普通に解釈することで、論理式の意味を考えることができるようになります。 ただし、'は後者関数と解釈します。 次に、¬,∧,∨,→,∃,∀,(,),0,',+,×,=,x,y,zに 素数2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53を割り当てます。 記号列が与えられたとき、各記号を上記の対応に従い素数n_1,n_2,n_3,…に置き換え、2^(n_1)*3^(n_2)*5^(n_3)*…を対応させます。対応する数をゲーデル数と呼びます。 以上で準備は終わりで、 質問ができるのですが、 「mがTのある論理式のゲーデル数である」という非形式的な主張は mを素因数分解して各素数の指数を調べることである論理式のゲーデル数であるかどうかがチェックできるので、解釈すると「mがTのある論理式のゲーデル数である」という意味になる論理式が作れる、とあるのですが"具体的"にはどのようにして作るのでしょうか? 私は、論理式の定義が再起的であるから、「mがTのある論理式のゲーデル数であるかどうか」をコンピュータに判定させること(とてつもなく時間がかかりそうですが)可能だと思うので上のような論理式は作れると思うのですが、実際に作るとどんな論理式になるのか興味があります。

  • ゲーデルの定理

    完全性定理では「任意のモデルで真である文はすべて1階述語論理で証明可能である」 不完全性定理では「自然数論を含む体系は無矛盾である限り、真であっても証明できない 命題が存在する」とありました。 それではこの2つの定理をペアノの公理系に当てはめると「全ての真である命題は証明可能」でありながらどこかに「真であっても証明できない命題が存在する」わけですか? 何だか矛盾するような感じがしますが、そんな訳ありませんよね。 どう考えたらよいのか教えてください。 よろしくお願いいたします。

  • 不完全性定理を自然科学に敷衍できるか。

    数学基礎論の林晋先生の「ゲーデルの謎を解く」という本を読んで疑問に感じていることがあります。 この本の最初に「ホーキングの疑問」と銘打って天才物理学者の下記の疑問をゲーデルの不完全性定理になぞらえています。 「本当に完全な統一理論があるならばそれは人類の行動をも決定するだろう。ということは、統一理論自体が、人類の統一理論探求の行方を決定することになる! だとしたら、どうして、人類が正しい結論にたどり着ける、と決まっているだろう?」 もし、統一理論がニュートン力学と初歩的な電磁気学で構成されていたとしたら、そのような世界では、ニュートン力学を理解できるような知性は生まれえないということでしょうか。 自然科学は暫定的な仮説の総体と言っても良いはず。無矛盾を前提に証明された不完全性定理を自然科学に適用するにはもっと慎重であるべきではないかと思います。 統一理論(というより宇宙)の自己言及性という問題があるとすれば、次のような状況ではないかと考えます。宇宙の全要素の状態を超巨大コンピューターに入力できて、宇宙のすべての状態を把握できるようになる。そうするとコンピューター自身も宇宙の一部ですから、そのデータも自分自身に入れなくてはなりません。 つまり人間の能力は余りにも小さいので、自然科学分野では不完全性定理が障害となるような事態はあり得ないと考えています。 以上のような私の考えに対してサゼスチョンがあれば聞かせていただきたいと思います。 勝手ながら、回答は数学科か哲学科の方か同等の知識のある方にお願いいたします。

  • ゲーデルの不完全性定理を詳しく教えてください。

    ゲーデルの不完全性定理を詳しく教えてください。