ゲーデルの第1不完全性定理の具体例はありますか

数学には正しいとも正しくないとも判断できない命題があるそうですが（ゲーデルの第1不完全性定理）、具体的にこのような命題を見いだせていますか。もしそうならその命題の内容を素人にもわかりやすく教えてください。

No.5 ベストアンサー 回答者： stomachman 回答日時： 2024/01/28 14:52

> 解読にチャレンジしてみます

と仰るのであれば、仕掛けの全体像を概観しておくのも良いかなと思います。

　肝心なのは、証明とは一体何なのか、ということ。その意味を厳密に定めるには「形式的体系」（ヒルベルトの形式主義）という概念が必要です。形式的体系とは、
(1) 使える記号の集まり。（これらの記号を一列にならべて有限の長さの記号列を作ります。）
(2) ある記号列が命題であるための文法規則。（命題であっても、真だとは限りません）
(3)「公理」と呼ばれる命題の集まり。
(4)「推論規則」と呼ばれる、いくつかの命題から別の命題を構成する機械的な記号操作の集まり。（どの公理にどの推論規則を適用するかは自由。）
これらを定めたものです。
　公理から出発して、推論規則を繰り返し適用することによってある命題Pが得られたとき、Pをこの形式的体系における「定理」と呼ぶ。そして、公理から命題Pに至る推論規則の適用の列を「証明」と呼びます。（証明とはルールに従って記号列を並べて行くゲームのようなもの、ってことです。）
　ですから、形式的体系が異なれば、そもそも何が命題であるかが異なりますし、証明できる命題も異なります。特に、ある命題PとPの否定とが両方とも定理であるような形式的体系もあり、そういうのは「矛盾を含む形式的体系」と呼ばれます。（もちろん興味があるのは、矛盾を含まないヤツです。）

　さて、形式的体系Sをひとつ固定します。そして
　　　X:「Xは形式的体系Sでは証明不可能である」
という言明を考えます。この言明Xが形式的体系Sにおける命題として表現できたとしましょう。すると、もし形式的体系SでXが証明できれば、Xは定理であり、なのでXが主張する通り、形式的体系SでXは証明不可能だということが分かった。しかし、実際にXを証明しちゃったんですから、あれれ、これは矛盾です。すなわち「もし形式的体系SでXが証明できれば」という前提が間違っているのであって、Xは形式的体系Sで証明できないに違いない。一方、Xが形式的体系Sで証明できないということは、Xの言っていることは正しい。結局、Xは形式的体系Sにおいて、正しいのに証明できない命題である。
…という仕掛けです。

　この仕掛け自体は、言葉遊びかナゾナゾのようなものであって、大昔から色々なバリエーションが知られている。つまり自然言語の範疇に入っている。ですが、この話が厳密に成立するためには、その前提として「言明Xが形式的体系Sにおける命題として表現できた」という仮定が必要です。そして、実際、Xが「自然数の算術を含むようなどんな形式的体系においても命題として構成できる」ことを示したのが、ゲーデルの証明だというわけです。

　不完全性定理がヤバイのは、数学をどう修正したって、Xが命題として成立してしまうからです。自然数の算術を含まないような体系なんて、そんなもん、もはや数学とは言えないでしょう。

　ところで、ややこしいのは、この証明それ自体は「形式的体系Sにおける証明」ではない、ということ。ではゲーデルがやったのはどういう体系における証明なのか。その体系を「超数学」と呼びます。このネーミングは（数学のような）形式的体系自体を対象として扱う数学、というほどのキモチです。

この回答へのお礼

親切なアドバイスに感謝します。非常にわかりやすい説明で、ゲーデルが何かすごいことを証明したということを実感した思いです。数学そのものを対象に、それを論理学の手法で解明するという感じですかね。対象が形式的体系というところがとてつもなく広大という感じがします。公理系や数理論理学の基礎知識が必要のようですから、まずはその辺から勉強してみようと思います。ありがとうございました。

お礼日時：2024/01/28 23:07

No.4 回答者： rinkun 回答日時： 2024/01/28 08:58

真偽(正しい正しくない)と証明可能性について。

命題Aに対して普通はAとnot Aの何れか一方は真でもう一方は偽です。
# これが排中律です
しかし証明可能性に関しては
Aが証明可能
not Aが証明可能
Aもnot Aも証明可能でない
の3通りがあります。
# Aとnot Aの両方が証明可能であれば公理系が矛盾しています

「Aもnot Aも証明可能でない」ような命題Aは決定不能な命題と呼ばれます。ゲーデルの不完全性定理は、自然数論を展開できる程度に複雑な公理系では決定不能な命題が存在することを示します。
例えばZFC集合論では連続体仮説は決定不能です。例え連続体仮説を公理に追加してもまた別の決定不能命題が出てきて、決定不能な命題のない完全な公理系を用意して数学を基礎付けることが簡単でないこと示しています。

この回答へのお礼

親切な説明をありがとうございます。命題の真理と証明可能性の関連については正直よくわからないのですが（Aが証明可能なら自動的にnot Aも証明可能になるということはないらしい・・・つまり排中律を仮定しない?!）、これは数理論理学の知識がないためと思います。非常に興味が出てきたので、もっと勉強したいと思います。

お礼日時：2024/01/28 10:04

No.3 回答者： stomachman 回答日時： 2024/01/27 21:44

> もっとよい参考書

「素人にもわかりやすく」という程度のおつもりなら、「ふうん、そうなんだ」で納得したことにしておくのがよろしいでしょう。その先を求めるのであれば、まずはゲーデル自身の著書をじっくり読んでみるのがいいんじゃないでしょうか。予備知識はほとんど要らないんですし。「不完全性定理」クルト・ゲーデル (岩波文庫)

この回答へのお礼

回答ありがとうございます。仮に不完全性定理の意味がお話し的にわかったとしても、やはりどう証明したのかということが気になります。岩波文庫にゲーデルの原論文の翻訳があるとのことなので、入手して解読にチャレンジしてみます。

お礼日時：2024/01/28 10:02

No.2 回答者： rinkun 回答日時： 2024/01/27 19:55

ゲーデルの不完全性定理は正しいか正しくないかは議論していません。

証明可能性を議論しています。
ゲーデルの第一不完全性定理は「適当な仮定を満たす公理系には、自身もその否定も証明できない命題がある」です。
その命題の具体的な例としては「その公理系が無矛盾である」という命題があり、それが第二不完全性定理でもあります。
適当な仮定には、公理系が初等算術を含むとか、帰納的に定義されているとか、無矛盾であるとかがあります。ゲーデルの当初の議論では、無矛盾より強いω無矛盾が仮定されていましたが、後にロッサーにより無矛盾の仮定で良いことが示されています。これはロッサーの定理、あるいはゲーデル・ロッサーの定理とも呼ばれます。

この回答へのお礼

回答をありがとうございます。知識がないので、「正しいか正しくないか」と「証明可能性」の違いがよくわかりませんが（証明できないということは、けっきょく正しいか正しくないかわからないということではないでしょうか）、実例として適当な仮定を満たす公理系が無矛盾であることが証明できない（しかもそれが第2不完全性定理である！）というのは大変参考になりました。大いに興味がわいたので、参考書で勉強したいと思います。

お礼日時：2024/01/27 21:00

No.1 回答者： stomachman 回答日時： 2024/01/26 22:00

> 具体的にこのような命題を見いだせて

います。てか、それを構成してみせたことで証明になってるんです。

> その命題の内容

要するに「この命題は証明不可能である」 という意味を持つ命題です。これが命題として成立するようにするために、ゲーデルは、自然数の算術を含む体系では、あらゆる命題を自然数に対応づけ、さらに命題の証明を数の計算に対応づける、という仕掛けが作れることを、構成的に示しました。なので、ご質問の定理は自然数の算術を含む体系のどれについても成り立ちます。

ゲーデルはさらに、同じ定理がどこまで簡単な体系（自然数の算術を含まない）でも成立するか、という研究をやっており、他の人たちもいろんな体系を提案しています。

この回答へのお礼

回答ありがとうございます。ゲーデルは証明不可能な命題を実際に作ってみせたのですね。そうすると具体的に証明不可能な命題とはどういうものかを知るためには、ゲーデルの第1不完全性定理の内容を理解すればよいということでしょうか。がぜん興味がわいてきました。

この定理を理解するためには、数理論理学の知識が必要のようですが、わたしが持っている論理に関する知識はそれよりずっと前段階の中内伸光『ろんりと集合』で学んだものです（数学で証明不可能な命題があるということは、この本で知り、今回質問しました）。未読の野矢茂樹『論理学』（東大出版会）をもっています。この本はゲーデルの定理を理解するのに役立つでしょうか。もっとよい参考書があれば紹介してください。

お礼日時：2024/01/27 13:53