哥德尔数

在形式数论中，哥德尔编号是对某些形式语言的每个符号和公式指派一个叫做哥德尔数(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.