ゲーデルの不完全性定理について : MATHEMATICS.PDF

トップページ > コラム > ゲーデルの不完全性定理について

ゲーデルの不完全性定理について

時代背景

　１７世紀の末ごろから，ライプニッツやニュートンによって微分や積分の概念が誕生し，その有用性が認められるようになると，無限を扱うことによって生じる問題が避けては通れないものになりました．

　１９世紀後半，カントールが「ものの集まり」という素朴な意味での「集合」という概念を導入し，無限個のものの集まり，つまり「無限集合」を考えました．彼は，ものの個数の比較を無限へと拡張させた「基数（濃度）」や，自然数の整列性を拡張させた「順序数」を定義し, 集合論を確立しました．

　例えば，彼は実数の全体が自然数の全体より真に大きな無限集合であることを，基数の概念を用いて定式化し，有名な「対角線論法」を用いて証明しました．

　カントールの集合論は数学全般に大きな利益をもたらしました．集合を利用することによって，数学の諸概念がとても円滑に，かつ統一的に記述されました．

　しかしながら欠陥もありました．ブラリ・フォルティ，ラッセル，リシャールらによって，カントールの集合論に起因するいくつかのパラドックスが発見されました．

　これらのパラドックスがきっかけで，２０世紀に入り，数学の基礎を見なおそうという気運が高まりました．こうして，数学を基礎付ける考え方として論理主義，直観主義，形式主義という３つの立場が生まれました．

　論理主義とは，数学を論理によって基礎付けするという立場です．

　この時代，論理学とは，ものごとを形式的に研究すること全般を指していました．論理主義は，数学を完全に記号化することを志していました．

　この主義を支持した有名な数学者にはフレーゲ，デデキント，ラッセルなどがいます．

　ラッセルは，論理主義に基づきながら，パラドックスを「型（type）」という概念の導入によって解決しようとしました．１９１０年頃，彼はホワイトヘッドとの共著「プリンキピア・マテマティカ」において，論理学の基本原則から出発し，自然数論, 実数論, 解析幾何学などを再構築しました．

　直観主義は，ブラウアーによって主張されました．

　直観主義では，対象の存在を，その対象が実際に構成される場合にのみ認めます．また，推論の中で命題Ｐに対してＰまたはＰの否定のどちらか一方が必ず成り立つという「排中律」を無条件で使用することを禁止します．

　この立場に立って再構築された数学は非常に堅固で，パラドックスが生まれる余地がありません．しかしながら制約も多く, 数学における結果の多くが直観主義では成り立たないことが知られています．

　コンピュータの発展により，現在，直観主義は非常に興味を持たれています．というのも，直観主義によって展開できる数学は，コンピュータによって展開できるからです．

　形式主義は，ヒルベルトによって提唱されました．

　形式主義では, 数学の命題を記号列で表現し，推論は記号列の変形規則であり，公理は記号列の変形の出発点であるとします．命題の意味や内容を推論の根拠にはしません．

　パラドックスを回避するために，記号列の変形を有限回に限定しました．これを「有限の立場」といいます．

　そして数学における証明を，推論に従って並べられた記号列の列であると定義しました．

　数学の理論を表現するための記号の集まりとその変形規則の集まりとをひとまとめにしたものが「形式的体系」と呼ばれるものです．

　ヒルベルトは，数学の理論を形式的体系として表現し，記号列の変形や組み合わせ的な操作で取り扱うことを考えました．彼は「超数学」，つまり，形式化された証明を対象とする理論を構築することを提案しました．

　数学の理論を形式的体系によって表現し，その体系の無矛盾性を有限の立場に従って超数学的に証明することで，もとの数学の理論を正当化しようと考えました．この考え方は「ヒルベルトのプログラム」と呼ばれています．

定理について

　ゲーデルの不完全性定理は，超数学における定理です．しかしながら，この定理は，ヒルベルトのプログラムのある種の限界を示していました．

　１９３１年にゲーデルは二つの不完全性定理を証明しました．

　ます，第一不完全性定理とは，「自然数論の公理を含む無矛盾な形式的体系には決定不可能な論理式が存在する」というものです．

　なお，論理式とは，数学の命題を形式的に表現したもののことです．論理式Ｐが決定不可能であるとは，Ｐ自身もその否定も証明できないことをいいます．

　例えば，自然数論の公理，ツェルメロ－フレンケルの集合論の公理，群論の公理など，実用的な体系の多くに対してこの定理を適用することができます．

　実際には，ゲーデルはω-無矛盾という仮定のもとで第一不完全性定理を証明しました． ω-無矛盾は無矛盾より強い条件です．それをロッサーが１９３６年に無矛盾にまで拡張しました．

　ゲーデルの第二不完全性定理とは，「自然数論の公理を含む無矛盾な形式的体系の無矛盾性は，その体系内では証明できない」というものです．

　これは，自然数論の公理を含む数学の理論が，少なくとも有限の立場では自分自身の正しさを示すことは不可能であることを意味します．

　もちろん，与えられた形式的体系の範囲を超えるような論法を用いれば，その体系の無矛盾性が証明できることもあります．

　そのような例として，１９３６年に行われた，ゲンツェンによる自然数論の無矛盾性の証明があります．ゲンツェンは，「超限帰納法」と呼ばれる，数学的帰納法を自然数の範囲を超える順序数へと拡張した論法によって，有限の立場で証明を行いました．

　ゲーデルの不完全性定理の証明について簡単に触れたいと思います．

　証明における主なステップは，次の通りです．

数学を形式的に表現することに関して，「各自然数ごとに表現可能」という概念を導入する．
「原始帰納的」と呼ばれる関数が各自然数ごとに表現可能であるという，「表現定理」を証明する．
数学の証明の一部を「ゲーデル数」と呼ばれる数に対応させることで証明をある意味で計算できるようにする．
カントールの対角線論法のアイデアを用いて，「対角化定理」と呼ばれる，論理式における不動点定理のようなものを証明する．
決定不可能な論理式，つまり自分自身もその否定も体系内では証明できないような論理式 U を構成する．（第一不完全性定理）
「体系は無矛盾である」という命題を体系内の論理式として表現する. その論理式を C とおく.
「 C が体系内で証明できるならば U も体系内で証明できる」ということを証明する. このとき，U は体系内では証明できない論理式だから，C もまた体系内では証明できない論理式である. （第二不完全性定理）

　上の証明のステップ６において，「形式的体系が無矛盾である」という命題を表現する論理式の選び方は一通りではありません．

　クライゼルは，無矛盾性を表現する論理式で，ゲーデルが不完全性定理の証明で用いた論理式とは別のものをとると，それが自然数論の公理を含む形式的体系のなかで証明できる場合があることを注意しました．

　ですから厳密には，第二不完全性定理は，無矛盾性を表現する論理式のうちのあるものは，自然数の公理を含む無矛盾な形式的体系からは証明できない，となります．

　これは，数学の命題を形式的に表現する絶対的な方法が確定しているわけではないことを示唆しています．