哥德爾數

在形式數論中，哥德爾編號是對某些形式語言的每個符號和公式指派一個叫做哥德爾數(GN)的唯一的自然數的函數。這個概念是哥德爾為證明他的哥德爾不完備定理而引入的。

可計算函數集合的編號有時叫做哥德爾編號或有效編號。哥德爾編號可以被解釋為一個程式語言，帶有指派哥德爾數到每個可計算函數作為在這種程式語言中計算這個函數的值的程式。Roger 等價定理特徵化了是哥德爾編號的可計算函數集合的編號。

哥德爾編碼

哥德爾使用基於質數因數分解的哥德爾編碼系統。他首先把唯一的自然數指派到在他所處理的算術的形式語言中的每個基本符號。

為了編碼是符號序列的整個公式，哥德爾使用了如下系統。給出正整數的序列 $x_{1}x_{2}x_{3}...x_{n}$ ，哥德爾對這個序列的編碼是第 n 個質數自乘這個序列中對應值的次數:

\mathrm {enc} (x_{1}x_{2}x_{3}...x_{n})=2^{x_{1}}\cdot 3^{x_{2}}\cdot 5^{x_{3}}\cdot ...\cdot {p_{n}}^{x_{n}}

依據算術基本定理，用這種方式獲得的任何數都可以唯一的因數分解到質因子，所以可以有效的從其哥德爾數恢復最初的序列。

哥德爾特別的在兩個級別使用這個方案: 首先編碼表示公式的序列，其次編碼表示證明的序列。這允許他證明在關於自然數的命題和關於自然數的定理的可證明性的命題之間的對應，這個證明的關鍵觀察。

有更複雜的（但更「簡潔」）的方式來構造序列的哥德爾數。

唯一性的缺乏

哥德爾編號不是唯一的。一般性的想法是把公式對映自然數上。假設有 K 個基本符號。可替代的哥德爾編碼可以通過把每個基本符號對映到基數為 K 的記數系統的一個數字來構造，這樣由 n 個符號的字母串構成的公式 $s_{1}s_{2}s_{3}\dots s_{n}$ 將被對映成數

h(s_{1})\times K^{(n-1)}+h(s_{2})\times K^{(n-2)}+\cdots +h(s_{n-1})\times K^{1}+h(s_{n})\times K^{0}.

換句話說，藉由將K 個基本符號以某種固定順序擺放，那麼每個方程式就會產生唯一對應的哥德爾數。但是如果將K 個基本符號以另一種固定順序擺放，則會產生另一種哥德爾編號。

形式系統應用

還有，哥德爾編號蘊涵了形式系統的每個推論規則都可以被表達為自然數的函數。如果 f 是哥德爾對映並且如果公式 C 可以推導自公式 A 和 B，通過推論規則 r，就是說

A,B\vdash _{r}C\

，

則有某個自然數的算術函數 g_r 使得

g_{r}(f(A),f(B))=f(C)

。

接着，因為這個形式系統是形式算術的，它能做關於數和它們相互的算術聯絡的陳述，可以得出這個系統也可以通過哥德爾編號的方式，間接的做關於自身的陳述: 就是說，形式系統的一個命題可以做出斷言，在從哥德爾對映的角度檢視的時候，能轉換成關於同一個形式系統的其他命題，甚至是自身的斷言。所以，通過這種方式一個形式算術可以做關於自身的斷言，而成為自參照的，就像二階邏輯。這提供給哥德爾(和其他邏輯學家)一種探索和發現關於形式系統的一致性和完備性性質的一種方法。

例子

哥德爾數是參照命題演算和形式算術的符號而構造的，每個符號都被指派了一個自然數:

邏輯符號	數1:12
$\lnot$	1（非）
$\forall$	2（所有）
$\supset$	3（如果-那麼）
$\vee$	4（或）
$\wedge$	5（與）
(	6
)	7
S	8（後繼）
0	9
=	10
+	11
×	12
命題符號	大於12且被3整除的數
P	15
Q	18
R	21
S	24
個體變數	大於12且被3除餘1的數
v	13
x	16
y	19
謂詞符號	大於12且被3除餘2的數
E	14
F	17
G	20

以此類推

算術陳述/陳述式被參照質數系列指派唯一的哥德爾數。這基於一種簡單的編碼，它在本質上理解為
質數1 ^字元1 * 質數2 ^字元2 * 質數3 ^字元3
以此類推。例如陳述
$\forall$ x, P(x) 變成了
2² * 3¹⁶ * 5¹⁵ * 7⁶ * 11¹⁶ * 13⁷，因為
{2, 3, 5, 7, 11, ...} 是質數系列，而 2, 16, 12, 6, 16, 7 是有關的字元代碼。這是個巨大但完全確定的數(14259844433335185664666562849653536301757812500)。

注意通過算術基本定理，這個天文數字可以被分解到唯一的質數因數中；所以轉換哥德爾數回它的字元序列是可能的。

如果我們將此表的"非"指派為二，"所有"指派為一，這樣可以建立另一種哥德爾編碼，但是每個字元序列的哥德爾數仍舊是唯一的。

參見

邱奇數

引用

Gödel, Kurt, "über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I", Monatsheft für Math. und Physik 38, 1931, S.173-198.

進一步閱讀

Gödel, Escher, Bach: an Eternal Golden Braid, by Douglas Hofstadter. This book defines and uses an alternative Gödel numbering.
Gödel's Proof by Ernest Nagel and James R. Newman. This book provides a good introduction and summary of the proof, with a large section dedicated to Gödel's numbering.