gettyimages

理系の「3ワカラン」と呼ばれる「ゲーデルの不完全性定理」。「正しいからといって、それが証明可能であるとは限らない」とは、どういうことなのか？　この度、リニューアル刊行されたロングセラー『不完全性定理とはなにか　完全版』のなかから「不完全性定理」、そして異なる視点からゲーデルと同じ証明にたどり着いた「チューリングの計算停止問題」のエッセンスをこの記事では紹介します。この記事では、ペアノ算術と『プリンキピア・マテマティカ』の話題から、ゲーデルのいった「不完全性」について見ていきます。 【図説】「無限」の考えを数学に持ち込んだ天才・カントール。その天才の発想 *本記事は『不完全性定理とはなにか　完全版』(ブルーバックス)を再編集したものです。

「ペアノ算術」と「ペアノの公理」とは

ジュゼッペ・ペアノ

そもそもゲーデルの1931年の論文は「『プリンキピア・マテマティカ』やその関連体系における、形式的に決定不可能な命題についてI」という題名であり、『プリンキピア・マテマティカ』の「システム(体系)」において、決定不能な命題があることを証明している。それは、「ペアノ算術を含む体系」といいかえていい。 ここでは、この「ペアノ算術」について概要にふれることにする。 ジュゼッペ・ペアノはイタリアの数学者でトリノ大学教授だった。算術を公理化した業績で知られるが、ペアノ曲線にも名前が残っている。 ペアノは次の5つを算術の公理とした。 公理1　数1は自然数だ 公理2　aが自然数ならば(aの次の)a+1も自然数だ 公理3　aとbが自然数で等しくない(a≠b)ならば、aとbの次の数同士も等しくない(a+1≠b+1) 公理4　aが自然数ならばaの次の数は1ではない(a+1≠1) まあ、ここまではさしたる問題もない。算数のふつうの性質を厳密に言い表しただけである。だが、次の公理はどうだろう？

「公理5」では、なにをいっているのか？

公理5　Pを(論理式で定義可能な)性質とする。1がPをみたし、「aがPをみたすならば(aの次の)a+1もPをみたす」ならば、すべての自然数がPをみたす うーん、どこかで見たことがあるような気がする……そうだ、これは学校で教わる「数学的帰納法」ではないのか？ ご名答。この公理5は数学的帰納法の原理なのである。 で、公理1から4までは「矛盾しない」ことがあきらかなのに対して、公理5が入ってきても、ペアノの公理系が矛盾を含まないかどうかは、きちんと証明しないといけない。 そして、この問題に正面から取り組んだのがゲーデルということになる。 その前にプリンキピア・マセマティカについて、簡単に紹介しよう。