Gedeer Peishu 哥德尔配数使用素数幂 的乘积来表示自然数的任意有限序列xo，x1，…，xn 的所有方案。表示本身称为序列x。，xl，…，x，的 哥德尔数，通常记为（x。，x，，…，x。）。
哥德尔配数简介
在形式数论中，哥德尔编号是对某些形式语言的每个符号和公式指派一个叫做哥德尔数(GN)的唯一的自然数的函数。这个概念是哥德尔为证明他的哥德尔不完备定理而引入的。
可计算函数集合的编号有时叫做哥德尔编号或有效编号。哥德尔编号可以被解释为一个编程语言，带有指派哥德尔数到每个可计算函数作为在这种编程语言中计算这个函数的值的程序。Roger 等价定理特征化了是哥德尔编号的可计算函数集合的编号。
哥德尔配数哥德尔编码
哥德尔使用基于素数因数分解的哥德尔编码系统。他首先把唯一的自然数指派到在他所处理的算术的形式语言中的每个基本符号。
为了编码是符号序列的整个公式，哥德尔使用了如下系统。给出正整数的序列
，哥德尔对这个序列的编码是第n个素数自乘这个序列中对应值的次数：依据算术基本定理，用这种方式获得的任何数都可以唯一的因数分解到素因子，所以可以有效的从其哥德尔数恢复最初的序列。
哥德尔特别的在两个级别使用这个方案： 首先编码表示公式的序列，其次编码表示证明的序列。这允许他证明在关于自然数的命题和关于自然数的定理的可证明性的命题之间的对应，这个证明的关键观察。
有更复杂的（但更“简洁”）的方式来构造序列的哥德尔数。
哥德尔配数唯一性的缺乏
哥德尔编号不是唯一的。一般性的想法是把公式映射自然数上。假设有K个基本符号。可替代的哥德尔编码可以通过把每个基本符号映射到基数为K的记数系统的一个数字来构造，这样由n个符号的字母串构成的公式
将被映射成数换句话说，借由将K个基本符号以某种固定顺序摆放，那么每个方程式就会产生唯一对应的哥德尔数。但是如果将K个基本符号以另一种固定顺序摆放，则会产生另一种哥德尔编号。
哥德尔配数形式系统应用
还有，哥德尔编号蕴涵了形式系统的每个推论规则都可以被表达为自然数的函数。如果f是哥德尔映射并且如果公式C可以推导自公式A和B，通过推论规则r，就是说
，则有某个自然数的算术函数gr使得 。接着，因为这个形式系统是形式算术的，它能做关于数和它们相互的算术联系的陈述，可以得出这个系统也可以通过哥德尔编号的方式，间接的做关于自身的陈述: 就是说，形式系统的一个命题可以做出断言，在从哥德尔映射的角度查看的时候，能转换成关于同一个形式系统的其他命题，甚至是自身的断言。所以，通过这种方式一个形式算术可以做关于自身的断言，而成为自引用的，就像二阶逻辑。这提供给哥德尔(和其他逻辑学家)一种探索和发现关于形式系统的一致性和完备性性质的一种方法。
哥德尔配数例子
哥德尔数是参照命题演算和形式算术的符号而构造的.每个符号都被指派了一个自然数:
逻辑符号 | 数 1:12 |
|---|---|
1 ("非") | |
2 ("所有") | |
3 ("如果-那么") | |
4 ("或") | |
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* 素数2* 素数3
以此类推。 例如陈述
变成了2* 3* 5* 7* 11* 13，因为{2, 3, 5, 7, 11, ...} 是素数系列，而 2, 16, 12, 6, 16, 7 是有关的字符代码。这是个巨大但完全确定的数(14259844433335185664666562849653536301757812500)。
注意通过算术基本定理，这个天文数字可以被分解到唯一的素数因数中；所以转换哥德尔数回它的字符序列是可能的。
如果我们将此表的"非"指派为二，"所有"指派为一，这样可以建立另一种哥德尔编码，但是每个字符序列的哥德尔数仍旧是唯一的。
