好きをブチ抜く

「好き」をブチ抜く

本、映画、科学、哲学、心理、すごい人の考え方など。あらゆる情報を編集したい。

不完全性定理を間違って使わないために 【利用と誤用の不完全ガイド】

記事の内容

一般の人の間でも、かなり有名な定理といえば、ゲーデルの不完全性定理です。

 

数学のとある限界を示した定理であり、その深遠さから、様々なアナロジーに用いられることも多いです。

 

しかし、これは数学の定理です。

 

よって、正確に使うには、数学の概念を正確に抑える必要があります。

 

そこで、今回は、不完全性定理を正確に抑えるとともに、様々な誤用を整理してくれるとてもいい本を紹介したいと思います。

 

・人間の思考と不完全性定理

・神と不完全性定理

・数学に関する懐疑

・ゲーデル、心、コンピュータ

 

これらの議題は大変刺激的ですが、誤用がふくまれることが多いです。

 

・数学的に不完全性定理を知りたい人

・不完全性定理にインスピレーションを受けたさまざまなアイデアを吟味したい人

 

以上の方におすすめな記事になります。それでは、目次をご覧ください。

 

 

 

 

ゲーデルの定理 利用と誤用の不完全ガイド

 

 

「革命」ばかりが語られてきた不完全性定理について、本来の定理としての醍醐味を語る。ゲーデル、チューリングをはじめとする驚くべき頭脳がシステムの性質を探る、創造性あふれる営みを垣間見る旅。しかも数々の誤用例を素材に、ゲーデルの定理では言えないことまでを徹底的に点検し、定理の射程を明らかにしている。認知科学、物理学、神学、ポストモダン批評など、思いつくかぎりの分野から誤用・誤解の事例がとりあげられている。誰もが陥りやすい錯覚や、緻密な考察の末の誤りも多く、著名な科学者の文章でさえ例に漏れない。同じ轍を踏まないためにもゲーデルの定理を引用する際にはとりわけ必読の書である。

 

 

こちらの本から、数学、計算論に関する議論を今回はまとめてみたい。

 

 

 

不完全性定理そのものをしりたい方は、まずはこちらをどうぞ。

www.buchinuku.work

 

 

 

 

 

算術の問題の論理的特性

 

ゴールドバッハの予想

「2より大きなすべての偶数は2つの素数の和である」

 

計算可能 アルゴリズムでチェックできるような性質のこと

 

ゴールドバッハの予想などは、計算可能な性質Pについて、「すべての自然数が性質Pをもつ」という形の言明である。こうした形の言明をゴールドバッハ類の言明と仮に呼ぶ。

 

・ゴールドバッハ類の言明は、もし偽であれば、反例を示し、計算を実行することで原理的に反証できる

・反例が存在するときには、それを規則的に見つけることができる

・真である場合には、それがどのように証明できるのかを前もって知ることはできない

 

 

 

 

 

形式体系に公理を追加する

 

・基本事実

AがSで証明可能であることと、S+notAが矛盾することは同値である。したがって、AがSで決定不能であることは、S+AとS+notAが両方とも無矛盾であることと同値である。

 

AがSで証明可能 ⇔ S + not A は矛盾

Tで「AならばE」が証明可能 ⇔ T + A でEが証明可能

 

 

 

 

 

無矛盾性とゴールドバッハ類の言明

 

一般的には、ある形式体系の無矛盾性だけからは、言明Aがその体系で証明可能だからといって、言明Aが真であるとは言えない。

 

しかし、ある種類の言明であるならば、証明可能性から真であることが保証される。それが、ゴールドバッハ類の言明だ。

 

よって、

 

偽であるゴールドバッハ類の言明は、基本的な算術を含む任意の理論において反証されるので、そのような理論においてあるゴールドバッハ類の言明が決定不能であれば、その言明は真ということになる

 

決定不能だという証明があれば、それは同時に予想の証明になる!!

 

 

 

 

 

 

完全で無矛盾な形式体系もある!

 

「実数の初等理論」などがそうだ。

 

ただし、この理論の表現力では、自然数を表現することができない。

 

 

 

 

 

 

決定不能な非算術的言明

 

不完全性定理が示すことは、Sがその算術部分で不完全になること。

そして、Sの仕様から、Sで決定できないような特定のゴールドバッハ類の算術的言明を具体的に作れる。

 

よって、非算術的言明、非数学的言明に関しては、不完全性定理からはなにも知識を得られない。

 

 

 

 

 

真理と決定不能性

 

本来は、形式体系における決定不能性と真理は関係ない。

 

それならば、不完全性定理の「Sの言語における真なる言明で、Sでは決定不能なものが存在する」という説明はどうなのか?

 

Sの言語の文が真か偽かの言明を表すと解釈するなら、この説明は正しい。Aも、not Aも決定不能であり、そのどちらかは真になるからだ。

 

言明の真偽の話は、体系の全ての文に拡張させないで、算術部分だけで語ることができる。算術部分なら、哲学的に考えず、素直に真偽について語ることができる。よって、「Sの言語における真なる言明で、Sでは決定不能なものが存在する」といっていい。

 

注意

ある具体的な決定不能な言明Aについて、Aかnot Aのどちらが真であるかを判定できるかは、また別の問題になる。

 

 

算術の言明について「真であること」は、たんに数学的言明が成り立っていることを示す言葉に過ぎない。そこに、哲学的な含みはない。

 

タルスキによる真理の定義はこうだ。

「Aが真である」という言明は、A自身と数学的に同値である。

 

 

 

 

 

 「Gが真である」ことがわかった?

 

ゲーデルの証明が示したことは、「Sが無矛盾であれば、Gは真である」ということだ。「Gが真である」ことを示したわけではない。

 

Sが無矛盾かどうか分からなくても、ゲーデルの証明は成り立つが、そのときはGが真であるかどうかは分からない。

 

 

 

 

 

 

ゲーデル文G

 

ゲーデル文Gは、ゴールドバッハ類の言明として定式化される。

 

文Gは、どんな数pも、SにおけるGの証明のゲーデル数ではないという言明と同値。

 

GがSで証明可能であるなら、「GはSの定理でないという性質」、つまり、Gの否定も証明可能になる。

 

ゲーデル文Gは、「自分自身が真ではない」という嘘つきのパラドックスと呼ばれているものに近いところがある。

 

しかし、嘘つきパラドックスは哲学的に色々と解釈を呼び起こすのに対し、ゲーデル文Gはひとつの算術文であって、他のゴールドバッハ類の言明と同じように問題なく意味を持つ。

 

 

 

 

 

 

第二不完全性定理

 

第一不完全性定理の導出は、P自身が証明可能になる。

 

「もしPが無矛盾ならば、Gである」がPで証明可能。そして、「もしGならば、Pが無矛盾である」もPで証明可能。

 

証明可能でない言明をもつどんな理論も無矛盾であることは、Pでも証明可能な事実だ。よって、Gと「Pが無矛盾」は、Pにおいてじつは同値になる。

 

 

 

 

 

計算的枚挙可能集合、計算的決定可能集合

 

集合Eの要素全てを生成する機械的な手順、つまり計算するようにプログラムできること、だ。

 

数字列全体の集合などがそうだ。

 

計算的決定可能、という概念も重要だ。任意の記号列sが与えられて、sがEに入るかどうかを判定するように計算機をプログラムすることが可能であることだ。

 

例えば、列の有限集合はすべて決定可能。

 

これが、集合の性質としての「決定可能性」だ。これは、型式体系における決定可能性とは異なる。しかし、ある形式体系が決定不能な文を持つことを示すために、決定不能な集合が存在するという事実が使える。

 

 

 

 

 

ゲーデル数化の2つの性質

 

・列が与えられたときに、そのゲーデル数を機械的に計算することができること

・ある数が与えられたときに、それが何かの列のゲーデル数になるかどうかを判定し、どの列かを決定できること

 

 

この条件を満たすとき、列の集合が計算的枚挙可能あるいは決定可能であることと、その集合に属する列のゲーデル数の集合が計算的枚挙可能あるいは決定可能であることが同値になる。

 

 

 

 

 

決定不能性定理

 

・すべての計算的決定可能集合は計算的枚挙可能である

・集合Eが計算的決定可能であるのは、Eとその補集合の両方が計算的枚挙可能であるときであり、その場合に限る

 

 

決定不能性定理

計算的決定可能ではない計算的枚挙可能集合がある

 

よって、任意の列sに対して、sがEに入るかどうかを常にチェックできる機械的手順はない。

 

「kがEに入る」という形の言明に対して真偽を取り違えた判断をしないような形式体系Sにおいて、その形の言明で決定できないものがある。

 

 

 

 

 

 

まとめ

 

ぜひ、詳しい議論は本書へと進んでみてほしい。

とくに、哲学的な議論を楽しむことができるはずです。

 

 

 

 

 

 

 

 

 

 

関連記事

 

www.buchinuku.work

www.buchinuku.work

www.buchinuku.work

www.buchinuku.work