ゲーデル数

問題提起：数学は自分自身について語れるか

「この命題は証明できない」という命題を、数学の形式体系の中で構成できるだろうか。一見すれば不可能に思える。数学は命題について語るメタ言語であり、命題はそのオブジェクトレベルにある。メタレベルの命題（「証明できない」）をオブジェクトレベル（通常の数学的命題）に持ち込むことは、レベルの混同を犯すように思われる。

クルト・ゲーデルは1931年に、巧妙な符号化技術を用いてこの不可能に見えることを実現した。その技術がゲーデル数（Gödel Numbering）である。

解決としてのゲーデル数

ゲーデル数の発想はシンプルだが深遠だ。形式体系の中の全ての記号・式・証明を自然数として符号化してしまえばよい。

具体的には、各記号に固有の素数を割り当て、記号列全体を各記号の番号を指数とした素数の積として表す。例えば記号の列（a, b, c）が素数（2, 3, 5）に対応するなら、記号列「abc」は 2^a × 3^b × 5^c というゲーデル数で表現できる。素因数分解の一意性（算術の基本定理）により、任意の自然数から元の記号列を一意に復元できる。

こうして形式体系の命題・証明がすべて自然数と対応する。すると「式Xが証明可能である」という命題は「ゲーデル数Nを持つ式が、ゲーデル数Pを持つ証明によって導出できる」という純粋に算術的な命題に翻訳できる。算術の中で算術を語れるようになった。

これで「この命題は証明不可能である」という自己言及的命題を算術の体系内に構成できる。この命題が真ならば体系は不完全（証明できない真命題がある）であり、偽ならば体系は矛盾する。一貫した体系では前者しかありえない。これがゲーデルの第一不完全性定理だ。

深掘り：符号化という知的戦略

ゲーデル数が示した知的戦略は、「あるシステムを別のシステムの語彙で語る」というものだ。この戦略は数学史において繰り返し登場する。

デカルト座標はユークリッド幾何学をアラビア数字の算術として表現した。フーリエ変換は関数を周波数成分として表現する。情報理論のビット符号化は全ての情報を2進数として表現する。ゲーデル数はこの戦略を「数学の体系を数学の対象として」という極限まで推し進めた。

再帰との関係も重要だ。ゲーデル数によって形式体系が「自分自身を計算対象として処理できる」ようになる。これは再帰的なプログラムが自分自身を引数として受け取れることの数学的先駆けであり、チューリングの万能機械の概念に直接繋がる。

自己言及がゲーデル数によって「無害化」されたとも言える。自己言及は通常パラドックスを生むが、ゲーデルは自己言及を算術に落とし込むことで、パラドックスではなく「決定不能性」という数学的に意味のある結果を引き出した。

他書・概念との接続

ゲーデル数は奇妙な環の実装だ。形式体系という階層の「底」（基本的な算術命題）から「上」（体系自身についての命題）まで上昇すると、数としてのゲーデル番号を通じて「底」に戻ってくる。この循環構造がホフスタッターをGEBへと駆り立てた中心的アイデアだ。

TNT（タイポグラフィカル・ナンバー・セオリー）はゲーデル数が機能する具体的な形式体系だ。GEBでホフスタッターはTNTを使って不完全性定理の議論を展開した。

チューリングテストとの接続も見逃せない。チューリングが停止問題の決定不能性を証明したのは、プログラムを入力として扱う（自己言及）という発想であり、これはゲーデル数の計算論的変奏だ。

残された問い

ゲーデルの定理は「真だが証明できない命題がある」と言う。しかし「真」とはここでどういう意味か。形式体系の外から見ればその命題は真だが、これは形式体系を超えた直観に訴えることだ。人間の数学的直観は形式体系を超えているのか、それとも十分に複雑な形式体系によって記述できるのか。ペンローズはゲーデルを根拠に前者を主張し、チューリング主義者は後者を支持する。この論争は意味と形式の問いと結びついて今も続いている。