• ベストアンサー
  • 暇なときにでも

ゲーデルの証明不能命題

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

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

  • 回答数3
  • 閲覧数397
  • ありがとう数1

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

  • ベストアンサー
  • 回答No.1
  • uzo
  • ベストアンサー率30% (10/33)

例示はできないと聞いています。 ドキアデス『ペトロス伯父とゴールドバッハの予想』(早川書房)に ゲーデルが不完全性定理を証明したときの、 ある数学者の受けた衝撃のエピソードが紹介されていて なかなか迫力がありました。 特におっしゃる疑問の後段については、 同様の疑念を主人公の数学者(ゴールドバッハ予想に取り組んでいる) が抱き、それに対して、フォン・ノイマンから 「証明不可能かどうか知ることは不可能であることを証明しました」 という手紙が主人公に届き、打ちのめされる姿を描いており、 なかなか鮮烈でした。

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

質問者からのお礼

ご回答ありがとうございました。 ご指摘の本を読んでみます。 フェルマー予想を最終的に証明したワイルズなども 証明可能な方に賭けたのですね。

関連するQ&A

  • 命題計算の或る形式的体系に関して

    こんばんは。いま私は、松本和夫著「数理論理学」(共立出版)を勉強しているのですが、その中で理解出来ない部分があったので、質問させてください。 この本の中で、以下の様な諸公理と推論規則MPを定めて、そこで証明可能な論理式が全てトートロジーとなるような無矛盾な命題計算の体系Hpを作るところがあります。 A、B、Cを論理式、⇒を含意として          公理1 A⇒(B⇒A)     公理2 (A⇒(B⇒C))⇒((A⇒B)⇒(A⇒C))                                                                            公理3 (¬B⇒¬A)⇒((¬B⇒A)⇒B)                                                                                                 推論規則MP A、A⇒B |-B これ等の公理と推論規則から導かれる形式的体系Hpでは演繹定理も成り立ちます。                                                                        さて本題の質問です。本書では、無矛盾な体系Hpに於いて証明可能な論理式の一つとして次のものが挙げられています。                                            定理 ¬A⇒(A⇒B)                                                                                             証明  (1)¬A 仮定 (2)A 仮定 (3)A⇒(¬B⇒A)公理1 (4) ¬A⇒(¬B⇒¬A)公理1   (5)¬B⇒A (2)と(3)にMP (6)¬B⇒¬A (1)と(4)にMP (7)(¬B⇒¬A)⇒((¬B⇒A)                                                  ⇒B)公理3  (8)(¬B⇒A)⇒B (6)(7)にMP (9)B (5)と(8)にMP                                                                                            故に ¬A、A|-B  これに演繹定理を2回用いて上の定理を得る。 qed                                                                     私が納得出来ないのはこの証明なのですが、最初に¬AとAが同時に成り立つと仮定していますよね。ですがHpは無矛盾なのだから、Hpにおいて¬AとAとが共に成立することなどあり得ない筈です。よってこの証明は無意味だと思うのですが、どうでしょうか?  随分ごたごたした記述で申し訳ありませんが、何卒ご回答お願いします。

  • ゲーデルの不完全性定理で出てくる「証明できない」

    ゲーデルの不完全性定理の証明に関する本をいろいろ読んでみましたが(あまり厳密なものは読んでいませんが)、どの本を読んでいても理解が先に進まず立ち止まってしまうところがありました。それは、「証明できない」ということの定式化(言葉がこれで正しいのかわかりませんが)についてです。 ある論理式が「証明できる」というのは、使用できる「公理」と「変形規則(推論というのでしょうか、これも言葉が正確かすみません覚えていません)」を有限回使用してその論理式に実際に到達できること、という理解をしており、これは理解できます。 これに対してある論理式が「証明できない」というのは、以下の(A)(B)(C)のどの意味なのでしょうか。 (A)使用できる「公理」と「変形規則」を有限回使用してもその論理式に実際に到達できない、ということ。 (B)その論理式の否定が証明できる、ということ。 (C)その論理式が証明できない、ということを示す何らかの論理式に、使用できる「公理」を「変形規則」を有限回使用して実際に到達すること。 (A)かなとも思いますが、それってどのように理解すればよいのでしょうか。1000回使用して到達できなくても、1001回使用すれば到達できるかも知れないのでは?  (B)ではないと思っていますが自信がありません。 (C)は実際には(A)だったり(B)だったりする?。。判断ができません。 昔の一時期、結構悩みました。現在再チャレンジしていており同じ個所で悩んでいます。もやもやを晴らして頂ければ大変うれしいです。

  • 私が知りたいのは ゲーデルの不完全性定理の幾何学での理解です。

    私が知りたいのは ゲーデルの不完全性定理の幾何学での理解です。 (1)第2不完全性定理では 次の表現があり『公理系Nにおいて、その無矛盾性を証明することは不可能である』、そのなかで問題として『 真であるが証明不可能な主張とは何か。』に対して 答え『公理』とあり 自己言及を表現していることは 理解し易いのです。幾何学では5公理です。この理解はたぶん正しいと思います。 ところが (2)私がよく分らないのは 第1不完全性定理です。『形式的体系Sにおいて、形式的体系Sが無矛盾である限り、「形式的体系Sにおいて命題は証明可能である。」という命題も「形式的体系Sにおいて命題は証明不可能である。」という命題も証明不可能である。』 と表される(別表現もありますが)とあります。 ここで現れる命題は抽象的言語であってよく分らないのです。例えばユークリッド幾何学においてはこの具体例は何でしょうか。私の理解は 「例えば無限遠点において平行線は交わるは証明可能である」はその例のようにおむのですが。つまり 例題には ユークリッド幾何学では未定義の無限遠点が現れており 証明はできない のです。いくら公理を増やして定義を明白にしても 未定義の領域はある ということです。 もう一つの例ですが 無限遠点は扱わないという6番目の公理を追加したとしても 例えば 「X・X=-1 は根がない は証明可能である」も証明できない と思うのです。なぜなら複素数は未定義だからです。つまり 『公理で定義されても未定義域は必ずある』が第一不完全性定理の一つの別表現ではないか と思うのです。この理解が間違っているのかどうか どなたかにお教えて頂きたかったのですが 

その他の回答 (2)

  • 回答No.3
  • aster
  • ベストアンサー率70% (374/533)

  ゲーデルの不完全性定理で出てくる、ある公理系では、必ず、その公理系の定理であることと、その否定が定理であるような命題が「構成できる」という時の、「構成できる命題」は、構成できるという前提での議論で、構成できるなら、そのような命題は、公理系内では、真とも偽ともどちらも言えるので、真偽判断ができないのです。 従って、「具体的な例」というものは、証明の構成上ありません。或る特定の公理系で、真とも偽とも判断できない命題というのは具体的にありえると思いますし、提示できます。 しかし、「いかなる公理系」でも、形式的構成で、その公理系では真偽判断不能な公理系内の命題が必ず存在するというのは、一般的な話で、あくまで、これは素人の意見ですが、ゲーデルの証明は、証明になっていないというのが私見です(わたしは、直観的構成的な考えになります)。 ある形の命題を形式的な形で述べてみて、そういう命題は、真だとすると、その結果、偽となり、偽だとすると、その結果、真になるというのが証明で、ここでは、「具体的な命題」を構成するという話は一切ありません。 これは、ラッセルのパラドックスと言われる、「自分自身を要素として含む集合」を考えると矛盾が出てくるというのと、似ています。そういう集合は具体的にどういう集合かというと、そんな集合は具体的に考えられないのです。 そういう集合が「ある」とすると、パラドックスが出てくるのですが、集合Aがそういう集合だとすると、その要素を外延的に列挙すれば、あるいは定義的に定めれば、Aは具体的に表現できそうですが、外延的に考えると明らかなのですが、Aが具体的に定義されるには、その前に、Aが定義されていないといけないということになります。 ラッセルのいう自分自身を含む集合は、まさに、この「自分自身を含む集合」という定義でしか定義できず、具体的に挙げることができません。 それと同様なことというか、ゲーデルの証明に出てくる、真偽決定不能の命題も、そういう定義の仕方で定義しているので、具体的には、構成できないのです。(証明法からして、「あるとすれば」ですから、構成はされていません)。 また、そんな命題があると、矛盾になるので、「ない」とも言えません。何故なら、矛盾するそういう命題が形式的に(どんな形かは一切言及なく)考えられるのですが、これが「矛盾」するので、証明が成立するというのが、ゲーデルの不完全性定理だからです。 >いまだ解かれていない数学上の難問がありますが、これらが論理式Aであるかどうかは、結局のところ証明できた時点でしか判定できないのでしょうか。 これは、また別の話です。ある定理が証明可能かどうか、というのは、「実は定理か、そうでないかの証明の問題」で、ゲーデルのいう形式命題がそれに妥当するとかしないとかとは、まったく別問題です。 定理か定理でないか、証明できていない、というのは、人間の知力の限界の問題で、あるいは、知力の限界の彼方に、定理とも定理でないとも証明できない命題だったということが分かるというような「数学理論」が出てくるかも知れません。 しかし、それはゲーデルの定理とは、一応別の話です。何故なら、ゲーデルの定理は、知力の限界の内側の話だからです。すでに、ゲーデルの定理は証明されていて、その証明で使っている、形式的な命題定義の形は分かっています。  

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

  • 回答No.2
  • ranx
  • ベストアンサー率24% (357/1463)

ユークリッド幾何学における第5公準(平行線の公理)などは、その例と考えてよいと思います。 あとは、カントールの予想なども集合論の枠内では証明できないことが証明されていますね。 証明可能性を示す一般的な手順は存在しないとしても、個々には証明不可能を証明できる場合も あるということだと思います。

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

関連するQ&A

  • 数学でいう「証明」と論理学でいう「証明」は異なるものでしょうか?

    数学で使われる「証明」という言葉と論理学で使われる「証明」という言葉は意味が異なるものであると思うのですが,間違いでしょうか? 公理系で挙げられる代表的な恒真式と推論規則に基づいて,別の恒真式を導くことが論理学でいう「証明」ですよね? そして論理学的な「証明」によって得られるものは恒真式(定理)だと思います.恒真式とは情報の価値としてはゼロ(自明)です. これに対して,数学で「証明」されるものは恒真式ではないですよね?数学における「証明」とは論理学における「演繹」に相当すると思うのですが,この考えも間違いでしょうか? ご教授お願いします.

  • 数学でいう「証明」と論理学でいう「証明」は異なるもの?

    数学で使われる「証明」という言葉と論理学で使われる「証明」という言葉は意味が異なるものであると思うのですが,間違いでしょうか? 公理系で挙げられる代表的な恒真式と推論規則に基づいて,別の恒真式を導くことが論理学でいう「証明」ですよね? そして論理学的な「証明」によって得られるものは恒真式(定理)だと思います.恒真式とは情報の価値としてはゼロ(自明)です. これに対して,数学で「証明」されるものは恒真式ではないですよね?数学における「証明」とは論理学における「演繹」に相当すると思うのですが,この考えも間違いでしょうか? ご教授お願いします.

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

    ゲーデルの不完全性定理の証明のアイデアが知りたいと思い、適当な入門書(基礎論の教科書ではないです。)を読んでいるのですが、 まず、定理の主張が「形式的体系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のある論理式のゲーデル数であるかどうか」をコンピュータに判定させること(とてつもなく時間がかかりそうですが)可能だと思うので上のような論理式は作れると思うのですが、実際に作るとどんな論理式になるのか興味があります。

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

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

  • ユークリッド幾何学にまつわる不完全性定理的理解について

    ユークリッド幾何学にまつわる不完全性定理的理解について ゲーデルの不完全性定理の対象となる数学は『公理系Nが無矛盾である』が前提です。ユークリッド幾何学は 一階述語論理で表されることが出来る自然数の部分集合であって、ゲーデルの不完全性定理の対象である 公理Nの無矛盾である 論理の対象になってないとなり それ以上のユークリッド幾何学の論理的理解が進みません。そこでゲーデル理解を拡張して『公理系Nが無矛盾ではない』として不完全性定理を理解すると(須田隆良氏、中西章氏など) (1)ゲーデルの第一不完全性定理の解釈==>公理系Nが無矛盾であろうがなかろうが 公理系Nにおいて、「公理系Nにおいて命題は証明可能である。」という命題も、「公理系Nにおいて命題は証明不可能である。」という命題も証明不可能である (2)第2不完全性定理の解釈==>公理系Nが無矛盾であろうがなかろうが その無矛盾性を証明できない となります。これらはゲーデル不完全性対象から外れておりますが、対象外のユークリッド幾何学を理解するには都合がよい と思うのです。 (2)によりユークリッド幾何学の公理の無矛盾性は証明できない。 (1)によりユークリッド幾何学の未定義領域(非ユークリッド幾何学、虚数、無限遠点とか)は 公理系Nにふくまれ 多くの証明できない命題があることになります。もちろん 公理定義内では完全性理論は保証されています。 なぜ このようなユークリッド幾何学に こだわる かと申しますと 世の中の 論理(数学、哲学、論理を用いた論文 など)は ユークリッド幾何学的なものが 圧倒的に多いと思うのです。これら論文は ほとんどは一階述語理論で表され かつ ゲーデル不完全性定理 対象論理ではないのです。それら論文の特に(2)に関わる自己証明は出来ない ということは重要であると思うのです。もちろん 自己証明が出来ないと言って間違いとはなりません が 常に 冷静に謙虚に 主張理論の原点を見直すことに 繋がっていると思うのです。勿論、論理構成が出来ていないシロモノは 論外であります。    以上のように理解しているのですが、ユークリッド幾何学にまつわるゲーデル不完全性定理の場外理解は問題ないでしょうか。諸先生のコメント頂けましたら幸甚です。

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

    不完全性定理って結局、数学は不完全であるということが証明されたってことですよね?だとしたら、これから数学を研究することに何の意味があるのでしょうか?

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

    入門書を読んで理解を深めてから質問しようと思っていたのですが、なにぶん多忙かつ 魯鈍であるため、ほとんど理解していない状態での質問をお許しください。 ゲーデルの不完全性定理の入門書を読むと、一般人向けの説明として次のように記述されて います。 ●自然数論を含むような数学的体系の無矛盾性を、その体系内で証明することはできない。 これは、分かりやすいく言うとどういうことなのでしょうか。論理記号式を使用しないと 説明は無理ですか。 不完全性定理は「自己参照」とか「自己言及」を行なった際に生じる、避けられない 困難性や矛盾の存在を言い表しているのだと思いますが、次のような(安直とも言える) 拡大解釈を許すような、普遍性のある定理なのでしょうか。 ●認識主体が自分自身を完全に認識することはできない。(認識) ●哲学が哲学を完全に定義することはできない。(定義) ●体制が自己の正当性を自分で証明することはできない。(証明)

  • ゲーデルの定理

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

  • 私がよく分らないのは ゲーデルの第1不完全性定理です。『形式的体系Sに

    私がよく分らないのは ゲーデルの第1不完全性定理です。『形式的体系Sにおいて、形式的体系Sが無矛盾である限り、「形式的体系Sにおいて命題は証明可能である。」という命題も「形式的体系Sにおいて命題は証明不可能である。」という命題も証明不可能である。』 と表される(別表現もありますが)とあります。 ここで現れる命題は抽象的言語であってよく分らないのです。例えばユークリッド幾何学においてはこの具体例は何でしょうか。私の理解は 『例えば無限遠点において平行線は交わるは証明可能である』はその例のように思うのですが 間違っているでしょうか。 問題は 無限遠点が公理を用いて表されるか どうか という先輩のご指摘があり公理をあらためてみてみますと 公理2に線分を限りなく伸ばすことができる とあります。つまり無限遠点は「公理2の限りなく線分を伸ばした点」と理解され 公理の定義を用いることで表されるとおもうのです。間違っているでしょうか。参考までに公理を挙げておきます。 <ユークリッド 幾何学の公理> (公理1)与えられた2点に対して、それらを結ぶ線分をちょうど1つ引くことができる。 (公理2)与えられた線分は、どちらの側にも限りなく伸ばすことができる。 (公理3)平面上に2点が与えられたとき、一方を中心とし、他方を通る円をちょうど1つ書くことができる。 (公理4)直角はすべて相等しい。 (公理5(平行線公理))直線外の1点を通り、その直線に平行な直線は1本に限る

  • 論理数理学(命題論理・述語論理)のテキストやHPを探しています!

    こんにちは。 私は経済学部の大学四年生です。 就職活動が長引き、前期末試験はほとんど無出席で挑む今日この頃ですが、どの先生も情状酌量の余地がなく(涙)、必死こいてテストで点数をとるしかないようなので、特に難しいこの科目は、ネットで助けを仰ぐことにしました。 探しているのは、以下のものをカバーしている練習問題つきのテキストです。 先生が自分でかき集めた講義内容なので、内容が飛び飛びです。 具体的には、最後に載せる問題が解ければ(証明できれば)、試験の問題はないそうです。 (論理的思考法) 論理とは何か 命題論理の言語 連言の推論規則 含意の推論規則 選言の推論規則 否定の推論規則 述語論理の言語 全称の推論規則 存在の推論規則 証明の練習 で、問題は「次のようなNK証明図を書きなさい」 ∃x(Fx∧Gx)├∃yGy などです。割り算のようなものが3~5段ほど縦に並んだ数式になります。 ネットで色々探しましたが、飛び飛びのものや深すぎるものが多く、これに必要なものだけを効率よく集めたものになかなか出会えません。 その上、分野があいまいで、図書館でもなかなかそれらしい本と出合うことが出来ません。 よろしければ、アドバイスをいただきたく存じます。 よろしくお願いいたします。