查看“哥德尔数”的源代码

{{NoteTA
|G1 = IT
|G2 = Math
|1 = zh-hans:代码; zh-hant:代碼;
}}
在[[数论|形式数论]]中，'''哥德尔编号'''是对某些[[形式语言]]的每个符号和[[公式_(数理逻辑)|公式]]指派一个叫做'''哥德尔数(GN)'''的唯一的[[自然数]]的[[函数]]。这个概念是[[哥德尔]]为证明他的[[哥德尔不完备定理]]而引入的。 

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

==哥德尔编码==

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

为了编码是符号序列的整个公式，哥德尔使用了如下系统。给出正整数的序列 <math>x_1 x_2 x_3 ... x_n</math>，哥德尔对这个序列的编码是第 ''n'' 个素数自乘这个序列中对应值的次数:
:<math>\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}</math>
依据[[算术基本定理]]，用这种方式获得的任何数都可以唯一的因数分解到素因子，所以可以有效的从其哥德尔数恢复最初的序列。

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

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

==唯一性的缺乏==

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

:<math> 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. </math>

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

==形式系统应用==

还有，哥德尔编号蕴涵了形式系统的每个推论规则都可以被表达为自然数的函数。如果 ''f'' 是哥德尔映射并且如果公式 ''C'' 可以推导自公式 ''A'' 和 ''B''，通过推论规则 ''r''，就是说
:<math> A, B \vdash_r C \ </math>，
则有某个自然数的算术函数 ''g<sub>r</sub>'' 使得
:<math> g_r(f(A),f(B)) = f(C) </math>。

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

==例子==
哥德尔数是参照[[命题演算]]和[[形式算术]]的符号而构造的.每个符号都被指派了一个[[自然数]]:
{| class="wikitable"
|-
! 逻辑符号 !! 数1:12
|-
| <math>\lnot</math> || 1（非）
|-
| <math>\forall</math> || 2（所有）
|-
| <math>\supset</math> || 3（如果-那么）
|-
| <math>\vee</math> || 4（或） 
|-
| <math>\wedge</math> || 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
|}
以此类推

算术陈述/语句被参照[[素数]]系列指派唯一的哥德尔数。这基于一种简单的编码，它在本质上理解为 <br>
'''素数1 <sup>字符1</sup> * 素数2 <sup>字符2</sup> * 素数3 <sup>字符3</sup>'''<br> 以此类推。
例如陈述 <br>
'''<math>\forall</math>x, P(x)''' 变成了<br>
'''2<sup>2</sup> * 3<sup>16</sup> * 5<sup>12</sup> * 7<sup>6</sup> * 11<sup>16</sup> * 13<sup>7</sup>'''，因为 <br>{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|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.

[[Category:數理邏輯|G]]