【論理学】ゲーデルの不完全性定理を解説!ラッセルのパラドクスとの違いは?【簡単ではない】

エンジニアであれば誰もが一度は手に取るであろう(?)Noam Nissen著『コンピュータシステムの理論と実装』では、NANDゲートからコンピュータを作り上げます。

AmazonでNoam Nisan, Shimon Schocken, 斎藤 康毅のコンピュータシステムの理論と実装 ―…

NAND回路
NAND回路

コンピュータは電子回路により論理演算を実現しているわけですが、その基礎である論理演算とはそもそも何なのでしょうか? そこで論理学からしっかり学んでみようと思い、大学時代に友人から勧められて一度読んだ野矢 茂樹著『論理学』を読み直してみることにしました。

Amazonで茂樹, 野矢の論理学。アマゾンならポイント還元本が多数。茂樹, 野矢作品ほか、お急ぎ便対象商品は当日お届け…

本書は哲学者である野矢茂樹先生が書いた論理学の入門書で、著者曰く「ずぶの素人のための現代論理学への初めの一歩」 とのことです。論理学を本格的に学ぶためのものではなく、論理学の世界を観光する気分で読む本らしいのですが…難易度としては気楽な旅行というよりかは、命がけの冒険のように思えます笑 大学では周囲の一定数の人が本書を読んでいた記憶があるのですが、どうも強者ぞろいだったようです。

本書はまず命題論理、述語論理の解説から始まり、最終章にてゲーデルの不完全性定理を概観して終わります。なんちゃら論理については本書を読めば理解できるかと思いますが、ゲーデルの不完全性定理についてはかなり気合を入れて読まないと理解不能です。

ゲーデルの不完全性定理を何となくの理解で流してしまっても人生には(恐らく)何の影響もありませんが、どうしてももう少し深く理解したいという気持ちが抑えられないので、無謀ながらブログの記事にして発信を試みようと思います。

本記事はあくまでゲーデルの不完全性定理をざっくりと説明したものです。ゲーデル数を使ったより具体的な解説については現在記事を執筆中であり、完成した際にはこちらにリンクを掲載いたします。

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

1931年に数学者のクルト・ゲーデル(Kurt Gödel, 1906-1978)が『Principia Mathematicaの形式的に決定不可能な命題とその関連システムについて』という論文で提唱したのが、「ゲーデルの不完全性定理」です。『Principia Mathematica』(数学原理)は数学者であるホワイトヘッドとラッセルの共著で、一連の公理(最も基本的な仮定)と推論規則だけであらゆる数学的概念を記述しようと試みたものです。ゲーデルは彼らの仕事に対して「どんなに工夫して論理を組み立てても、肯定も否定も証明できない命題が存在する」と言ってのけたのです。

ゲーデルの不完全性定理には第一不完全性定理と第二不完全性定理の2つがあります。まずは定理がどのようなものかを確認しておきましょう。

自然数論の公理系\(N\)が\(\omega\)無矛盾であるならば、\(A\)も\(\lnot A\)も公理系\(N\)においては証明できないような\(N\)の閉じた式\(A\)が存在する。
自然数論の公理系\(N\)の無矛盾性は公理系\(N\)においては証明できない。
いったい何が言いたいのかさっぱりわかりませんね。一言でまとめると「自然数論の公理系は不完全である」ということです。本記事ではこの主張について掘り進め、第一、第二不完全性定理の厳密な証明には触れないこととします。
さて、「自然数論の公理系は不完全である」という主張を理解するためには、以下の3つの言葉の意味を明確にする必要があります。
  • 自然数論
  • 公理系
  • 不完全性

1つ1つ順番に見ていくことにしましょう。

公理と公理系

いきなり順番が前後していますが、自然数論の前に公理系について解説しておきます。公理系とは、一連の議論の前提となる公理のまとまりのことです。公理というのは大本の仮定のことで、「これは正しいとみなしましょう」と人が勝手に決めたものになります。例えばユークリッド幾何学には5つの公理(公準)からなる公理系があります。

  1. ある1点から任意の1点に直線を引くことができる。
  2. 線分を延長して直線にすることができる。
  3. ある1点を中心としてある半径で円を描くことができる。
  4. 全ての直覚は等しい。
  5. ある線分が2本の線分と交わり、同じ側の内部に作る角の和が2直角より小さいとき、これら2本の線分を延長すると、角の和が2直角より小さい側で交わる。

この5つはすべて正しいものと仮定されているため、証明する必要はありません。これらを駆使すると、ピタゴラスの定理やオイラーの定理などを導き出すことができます。ちなみに定理は公理から演繹的に推論されたものであり、公理と同様常に正しくなります。

ユークリッド幾何学の公理系以外に有名なものとしては、公理的集合論のZFC公理系があります。ZFC公理系は現代数学の基礎とも言える非常に重要な公理系ですが、ゲーデルの第二不完全性定理により”完全ではない”ことが示されています。

自然数と自然数論

自然数は0, 1, 2, 3, …と無限に続く(0を含む)正の整数です。厳密にはペアノの公理から定義されるものですが、ここでは簡単に非負整数のこととさせていただきます。

自然数論とは即ち数を扱っている話のことであり、数学も自然数論に含まれます。

関連記事

この記事はすでに「ゲーデルの不完全性定理」の概要をご存じの方向けの内容となっております。そのため定理の大まかな意味や、誕生した歴史的背景などを知りたい場合は、まず以下の記事からご覧ください。 [sitecard url=https://t[…]

アイキャッチ_【論理学】ゲーデルの不完全性定理が前提とする自然数論の公理系とは?【ロビンソン算術と原始帰納的算術】

不完全性と無矛盾性

まず完全性とは、ある論理体系において「任意の命題の肯定または否定が証明できる」性質のことを言います。つまり「肯定も否定も証明できない命題が存在する」論理体系があった場合、その論理体系は不完全と言えます。

似たような概念に無矛盾性があります。これはある公理系において\(A\)と\(\lnot A\)が共に真となることはない、つまり論理の整合性が取れている性質を言います。不完全である、というのはそもそもある命題が\(A\)と\(\lnot A\)かが判定できないことを指すので、注意して下さい。

例えばAさんとBさんがじゃんけんをして勝負がついたとき、Aさんが勝ったor負けたと確実に分かるのが「無矛盾」、Aさんが勝ったのか負けたのか分からないのが「不完全」です。

以上の3点を踏まえると「自然数論の公理系は不完全である」とは、「数学において、どのような公理を元に論理体系を組み立てたとしても、(その論理体系の中でだけでは)肯定も否定もできないような命題が存在してしまう」ということになります。

ゲーデルの不完全性定理をGoogleで検索すると、なぜか「神は存在しない」という関連ワードが表示されます。どうもこれは良くある誤解らしいのですが、ゲーデルの不完全性定理はあくまで「自然数論の公理系」に限定されたものであり、前提が異なる場合にはそもそも議論の俎上に載せられないのでご注意ください。

ゲーデルの不完全性定理が生まれた背景

ゲーデルの不完全性定理が生まれた背景には、ラッセルのパラドクス、ヒルベルト・プログラムの影響がありました。順番に見ていきましょう。

ラッセルのパラドクス

バートランド・ラッセル (Bertrand Russell, 1872-1970)は数学者であり、先述した『Principia Mathematica』の著者の1人です。1902年、数学者であるフレーゲは著書『算術の基本法則』を執筆し、数学を論理学に基礎づける試みをしていましたが、ラッセルがその試みに対して矛盾を指摘したのです。その矛盾を指摘した方法は、現代においてラッセルのパラドクスとして知られています。具体的な内容は以下の通りです。

ある集合\(M\)を次のように定義します。

$$ M = \{ x \mid x \notin x \} $$

なお\(x\)自体も集合であり、\(M\)は集合の集まり(集合族)とします。\(M\)の定義を日本語で書き下すと「集合\(M\)は、自分自身を要素として持たないような集合\(x\)の集まり」となります。このままではまだ少しわかりにくいので、\(x\)の例を挙げて、\(M\)に含まれるか見てみましょう。

  • 犬の集合:「犬の集合」自体は「犬」ではないので、「犬の集合」には含まれない。→\(M\)に含まれる。
  • 犬でないものの集合:「犬でないものの集合」自体は「犬でないもの」なので、「犬でないものの集合」に含まれる。→ \(M\)に含まれない。

ではここで、\(x\)に\(M\)を入れてみるとどうなるでしょうか? 自分自身を要素として含まないものの集合\(M\)に\(M\)自身は含まれるのでしょうか?

\(M \in M\)の場合

\(M \in M\) と仮定すると、\(M\)は自身を要素として含んでしまっているため、自身を要素として持たない集合を集めた\(M\)の定義と矛盾します。

\(M \notin M\)の場合

\(M \notin M\) と仮定すると、\(M\)の定義から\(M\)は\(M\)に含まれることになり、仮定と矛盾します。

以上のように、集合\(M\)が\(M\)自身を含もうが含まなかろうが、矛盾が生じてしまうのです。ラッセルのパラドクスのより身近な形として、床屋のパラドックスが知られています。自分で髭をそらない人に限定して髭をそる床屋がいるとすると、床屋自身の髭をそるのは誰になるのか?というパラドックスです。

ゲーデルの不完全性定理の文脈でラッセルのパラドクスが取り上げられることがありますが、前者は「肯定か否定か、証明できないものが存在する」という定理であるのに対して、後者は「肯定と否定が両立することが導き出される」という推論(パラドクス)であり、全く別次元のものとなります。しかし、ラッセルのパラドクスにおける、「自己言及」という構造はゲーデルの不完全性定理の証明でも用いられているので、全く関連性がないという訳ではありません。

ヒルベルト・プログラム

数学を論理学に基礎づけるというフレーゲの試みは、ラッセルの指摘により座礁したかと思われました。しかし数学を論理的に体系化するという試みは続けられ、実際新たに考案されたZFC公理系(現代数学の基礎となる公理系)によりラッセルのパラドクスは解消されました。

ダフィット・ヒルベルト (David Hilbert, 1862-1943年)はドイツの数学者で、ヒルベルトの23の問題や、ユークリッド空間を拡張したヒルベルト空間等で知られています。彼は1920年頃から、数学の無矛盾性・完全性を証明するべく、公理系から数学を組み立て直すことを始めました。これは後にヒルベルト・プログラムと呼ばれるようになります。このプログラムにはアッカーマンやノイマンといった著名な数学者も参加していました。

皮肉なことに数学の無矛盾性・完全性を示そうとしたヒルベルト・プログラムは、ゲーデルの活動のモチベーションとなり、1930年ゲーデルの不完全性定理の発表をもって結果的に数学の不完全性を証明してしまいました。

ゲーデルの不完全性定理の証明(概略)

冒頭から何度か申し上げている通り、この記事ではゲーデルの不完全性定理の証明について細かくは取り上げません。代わりに大まかな証明の流れと、キーとなる発想「ゲーデル数化」についてお話します。

「この式は証明不能である」を構成する

ゲーデルの不完全性定理は「自然数論の公理系は不完全である」ことを証明したものでした。ここで「不完全」とは「肯定も否定もできない、証明不能な命題が存在する」ことであったことを思い出してください。つまりある自然数論の公理系において、「この式は証明不能である」を意味する式が構成できれば証明完了となります。そのためにゲーデルはあらゆる式、証明をそれぞれ一意の数と対応付ける方法を考案しました。それがゲーデル数化です。

ゲーデル数化

ゲーデルはいくつかの原始的な記号(0, ‘, +, \(\times\), =, (, ), \(\rightarrow\), \(\lnot\), \(\forall\), \(x_i\))に1, 2, 3 … と自然数を対応付けました。これらの数字を素数の指数とすることで、自然数と一意に対応付けたのがゲーデル数です。例えば\( 0 = 0 \)という式について考えてみましょう。ここで(0, =, 0)と対応する自然数は<1, 5, 1>となります。ここから、

$$  2^1 \times 3^5 \times 5^1 = 2 \times 243 \times 5 = 2430 $$

となります。ここで得られた2430こそが、\( 0 = 0 \)という式を表すゲーデル数となります。この方法を応用すると、あらゆる式、証明を自然数として構成することが可能になります。「そんなことが上手くいくのか?」と思われるかもしれませんが、ゲーデル数をUTF-8等の文字コードと考えればしっくりくるのではないでしょうか? 今皆さんが読んでいるこの文章も、コンピュータの中では0と1の羅列、即ち2進数の数字に他ならないですよね。

このゲーデル数を駆使して「この式は証明不能である」という式を構成することで、「自然数論の公理系は不完全である」ということを示すことができるのです。

最後に

以上、ゲーデルの不完全性定理についてざっくりと解説させていただきました。非常に抽象的で難解な話であるため、分かりづらい説明も多かったかもしれません。

今後も学習を続け、近いうちにゲーデル数を用いた証明の詳細についても記事にすることを予定しております。記事が出来上がった際はぜひご覧ください!

参考