gettyimages

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

真であることと、証明できること

写真:現代ビジネス

さて、不完全性定理の証明のあらすじをご紹介するのが目的の一つなのだが、延々と準備が続いてしまい、すみません。でも、最低限、「論理学とは何か」というイメージだけでも持っていただかないと、ゲーデルの証明のあらすじは説明できない。だから、いましばらく、お付き合い願いたい。 前節までで、数学の基礎である論理学には、2つのまったくちがった方法があることがわかった。 ひとつは「真理関数」によって、命題が正しいかまちがっているかを定義する方法。もうひとつは、「公理」と「推論規則」により、式を変形し、証明をしていく方法。 ここで問題です。 【問題】真であること(T)と証明できること(S)の関係は次のうちどれ？ 図はそれぞれ (1)証明できるのに正しくないことがある (2)正しいのに証明できないことがある (3)正しいことと証明できることが一致 (4)正しいのに証明できないことがあり、証明できるのに正しくないことがある (5)正しいことと証明できることとは互いに無関係(「正しい」は数学用語では「真」) 実は、この問題は引っかけであり、このままでは答えようがない。だが、ゲーデル以前の人々は、数学者も含めて、漠然と(3)、つまり「『正しい』と『証明できる』は同じ概念」だと信じていた。いまでも一般の人々は、(3)が正しいと思っているにちがいない。ただ、この本の読者は、そこに疑いをもっているはずだから、そのかぎりではないが。