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

Question

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

stomachman · Accepted Answer

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

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

肝心なのは、証明とは一体何なのか、ということ。その意味を厳密に定めるには「形式的体系」（ヒルベルトの形式主義）という概念が必要です。形式的体系とは、
(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における証明」ではない、ということ。ではゲーデルがやったのはどういう体系における証明なのか。その体系を「超数学」と呼びます。このネーミングは（数学のような）形式的体系自体を対象として扱う数学、というほどのキモチです。

rinkun · Answer

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

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

stomachman · Answer

> もっとよい参考書

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

rinkun · Answer

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

stomachman · Answer

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

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

> その命題の内容

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

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

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

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

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

> もっとよい参考書

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

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

似たような質問が見つかりました

このQ&Aを見た人はこんなQ&Aも見ています

関連するカテゴリからQ&Aを探す

このQ&Aを見た人がよく見るQ&A

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング