ゲーデルの不完全性定理の構成

ゲーデルの不完全性定理の証明において中心的な役割を果たすのが、ゲーデル数化と呼ばれる手法です。これは、数学的な記号、論理式、証明など、形式体系におけるあらゆる対象に一意の自然数を対応させる方法です。

具体的には、素数と指数を用いることで実現されます。まず、形式体系で用いられる各記号に一意の自然数を割り当てます。例えば、記号 “∀” には 1、記号 “=” には 2、変数 “x” には 3 というように対応付けます。

次に、記号列（例えば、論理式や証明）に対して、その記号列を構成する各記号に対応する数を素数の累乗として順番に掛け合わせていきます。例えば、記号列 “∀x(x=x)” に対しては、

– “∀” → 1,
– “x” → 3,
– “(” → 5,
– “x” → 3,
– “=” → 2,
– “x” → 3,
– “)” → 7

のように対応付けられているとすると、この記号列に対応するゲーデル数は

2¹ * 3³ * 5⁵ * 3⁷ * 2² * 3³ * 7⁷

となります。このようにして、任意の記号列に対して一意の自然数を対応付けることができます。

ゲーデルの不完全性定理は、「証明可能である」という概念自身を形式体系内で表現できることを示しています。これは、「論理式Aが証明可能である」という命題を表現する論理式 Proof(A) を形式体系内で構成できることを意味します。

具体的には、ゲーデル数は形式体系内の対象を自然数で表現できるため、Proof(A) は「ゲーデル数gが、Aの証明に対応する記号列のゲーデル数である」ということを表現する論理式として構成できます。

ゲーデルは、ゲーデル数化を用いることで、「自分自身は証明できない」という自己言及的な文を形式体系内で構成しました。この文は、ゲーデルの不完全性定理の証明において重要な役割を果たします。

具体的には、まず「xは、yをゲーデル数とする論理式の証明のゲーデル数ではない」という関係を表す論理式を考えます。この論理式を Sub(x, y) とします。

次に、この Sub(x, y) を用いて、新たな論理式 G を次のように定義します。

G ≡ ∀x(¬Sub(x, g))

ここで、g は G 自身のゲーデル数です。つまり、G は「G自身のゲーデル数を持つ論理式の証明は存在しない」ということを主張する論理式となっています。

ゲーデルは、上記で構成した自己言及文 G を用いることで、次の2つの定理を証明しました。

**第一不完全性定理:**
ある程度の強さを持つ無矛盾な形式体系において、証明も反証もできない命題が存在する。

**第二不完全性定理:**
ある程度の強さを持つ無矛盾な形式体系は、自身の無矛盾性を証明できない。

これらの定理は、形式体系の限界を示すものであり、数学の基礎に関する深い考察を促すものでした。