哥德尔配数法

某些非自然数对象转化为自然数的能行方法，因K．哥德尔在证明不完全性定理时最先使用而得名。哥德尔是利用正整数的素因子分解式来完成配数工作的。以下以PA系统的配数为例，简单介绍哥德尔的配数方法。

设=｛0，′，+，·，=｝是一阶形式数论PA的语言。首先将每个初始符号s与一个奇数对应(称为s的号码，记为gn(s))：

s：(，)，0，′，+，·，=，gn(s)：3 5 7 9 11 13 15

s：→，，v，v，v，……

gn(s)：17 19 21 23 25 27……

然后对每个符号串ss…s，定义其号码(哥德尔数)为

gn(ss…s)=··……

(其中P(n)表示第n个素数)。例如公式

α：v(v′=v)

的号码为

gn(α)=2·3·5·7·11·13·17·19·23。

对于公式序列Φ=〈α，……，α〉，定义其号码(哥德尔数)为

gn(Φ)=·，……

。

于是每个表达式、每个公式序列都对应着唯一的一个自然数。这就使有关PA的许多语法性质都可以转化为自然数或自然数集的性质，从而可以在PA内讨论某些PA的语法问题。也就是说PA具有一定的“自我反省”的能力。这是哥德尔不完全性定理的证明中的一个重要步骤。

哥德尔配数法当然也可以用于其他的符号语言。一般说来，任给非空的字母表∑，∑上的字与字序列都可以通过配数转化为自然数，从而可以定义递归的字函数、字集合，递归可枚举的字集合等等，通常说PA的定理集是递归可枚举集也正是在这种配数意义下讲的。配数使一些非自然数的问题转化为自然数问题，因而也叫“算术化”。

除了上述的正整数素分解式，还可以用其他方法来为符号串配数，例如配对函数，事实上，这类配数方法有无穷多种，关键在于配数的方法必须是能行的，1对1的。也就是说，任给一个对象(公式，公式序列等)可以能行地算出其号码，不同的对象有不同的号码；反之，任给一个自然数，也可以能行地确定它是否是一个号码，如果是，还应由该自然数能行地找到这个对象(公式，公式序列等)。