哥德尔数

在形式数论中，哥德尔编号是对某些形式语言的每个符号和公式指派一个叫做哥德尔数(GN)的唯一的自然数的函数。这个概念是哥德尔为证明他的哥德尔不完备定理而引入的。

可计算函数集合的编号有时叫做哥德尔编号或有效编号。哥德尔编号可以被解释为一个编程语言，带有指派哥德尔数到每个可计算函数作为在这种编程语言中计算这个函数的值的程序。Roger 等价定理特征化了是哥德尔编号的可计算函数集合的编号。

[编辑] 哥德尔编码

哥德尔使用基于素数因数分解的哥德尔编码系统。他首先把唯一的自然数指派到在他所处理的算术的形式语言中的每个基本符号。

为了编码是符号序列的整个公式，哥德尔使用了如下系统。给出正整数的序列 x₁x₂x₃...x_n，哥德尔对这个序列的编码是第 n 个素数自乘这个序列中对应值的次数:

依据算术基本定理，用这种方式获得的任何数都可以唯一的因数分解到素因子，所以可以有效的从其哥德尔数恢复最初的序列。

哥德尔特别的在两个级别使用这个方案: 首先编码表示公式的序列，其次编码表示证明的序列。这允许他证明在关于自然数的命题和关于自然数的定理的可证明性的命题之间的对应，这个证明的关键观察。

有更复杂的(但更“简洁”)的方式来构造序列的哥德尔数。

[编辑] 唯一性的缺乏

哥德尔编号不是唯一的。一般性的想法是把公式映射自然数上。假设有 K 个基本符号。可替代的哥德尔编码可以通过把每个基本符号映射到基数为 K 的记数系统的一个数字来构造，这样由 n 个符号的字母串构成的公式 将被映射成数

[编辑] 形式系统应用

还有，哥德尔编号蕴涵了形式系统的每个推论规则都可以被表达为自然数的函数。如果 f 是哥德尔映射并且如果公式 C 可以推导自公式 A 和 B，通过推论规则 r，就是说

，

则有某个自然数的算术函数 g_r 使得

g_r(f(A),f(B)) = f(C)。

接着，因为这个形式系统是形式算术的，它能做关于数和它们相互的算术联系的陈述，可以得出这个系统也可以通过哥德尔编号的方式，间接的做关于自身的陈述: 就是说，形式系统的一个命题可以做出断言，在从哥德尔映射的角度查看的时候，能转换成关于同一个形式系统的其他命题，甚至是自身的断言。所以，通过这种方式一个形式算术可以做关于自身的断言，而成为自引用的，就象二阶逻辑。这提供给哥德尔(和其他逻辑学家)一种探索和发现关于形式系统的一致性和完备性性质的一种方法。

[编辑] 例子

[编辑] 步骤 1

哥德尔数是参照命题演算和形式算术的符号而构造的.每个符号都被指派了一个自然数:

逻辑符号	数 1:12
	1 ("非")
	2 ("所有")
	3 ("如果-那么")
	4 ("或")
	5 ("与")
(	6
)	7
S	8 ("后继")
0	9
=	10
.	11
+	12
命题符号	大于 10 且被 3 整除的数
P	12
Q	15
R	18
S	21
个体变量	大于 10 且被 3 除余 1 的数
v	13
x	16
y	19
谓词符号	大于 10 且被 3 除余 2 的数
E	14
F	17
G	20

以此类推(NB 命题演算的语法确保了在 "P" 和 "+" 之间没有歧义,即使都指派了数 12)。

[编辑] 步骤 2

算术陈述/语句被参照素数系列指派唯一的哥德尔数。这基于一种简单的编码，它在本质上理解为
素数1 ^字符1 * 素数2 ^字符2 * 素数3 ^字符3
以此类推。 例如陈述
x, P(x) 变成了
2² * 3¹⁶ * 5¹² * 7⁶ * 11¹⁶ * 13⁷，因为
{2, 3, 5, 7, 11, ...} 是素数系列，而 2, 16, 12, 6, 16, 7 是有关的字符代码。这是个巨大但完全确定的数(14259844433335185664666562849653536301757812500)。

注意通过算术基本定理，这个天文数字可以被分解到唯一的素数因数中；所以转换哥德尔数回它的字符序列是可能的。

[编辑] 步骤 3

最后，算术陈述的序列也被进一步指派哥德尔数，比如序列
陈述1 (GN1)
陈述2 (GN2)
陈述3 (GN3)
(这里的 GN 指示一个哥德尔数)
得到哥德尔数 2^GN1*3^GN2*5^GN3，我们称之为 GN4。哥德尔不完备定理的证明依赖于，对在形式算术中，有些陈述的集合在逻辑上蕴涵或证明其他陈述。比如可以证实 GN1, GN2 和 GN3 在一起，也就是 GN4 证明 GN5。因为这是在其自己的符号所授权的数之间的一个可证实的联系，例如 R。接着我们可以写 R(v,x) 来表达 "x 证明 v"。在 x 和 v 是哥德尔数 GN4 和 GN5 的情况下我们可以说 R(GN5,GN4)。

[编辑] 参见

• 邱奇数

[编辑] 引用

• 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.