更改

现在让我们进入数理逻辑的领域，去领略另外一个利用破坏性自指进行的完美推理：哥德尔定理（参见：《[https://book.douban.com/subject/1291204/ 哥德尔、艾舍尔、巴赫——集异璧之大成]》和《[https://book.douban.com/subject/3029210/ 哥德尔证明]》）。

现在让我们进入数理逻辑的领域，去领略另外一个利用破坏性自指进行的完美推理：哥德尔定理（参见：《[https://book.douban.com/subject/1291204/ 哥德尔、艾舍尔、巴赫——集异璧之大成]》和《[https://book.douban.com/subject/3029210/ 哥德尔证明]》）。

首先，我们需要简单介绍一下哥德尔定理的背景。哥德尔定理所讨论的对象是关于自然数的一套公理系统。此公理系统是由关于自然数性质的命题构成的（我们可以把这些命题简单地理解为一些合法的字符串）。例如：

首先，我们需要简单介绍一下哥德尔定理的背景。哥德尔定理所讨论的对象是关于自然数的一套公理系统。此公理系统是由关于自然数性质的命题构成的（我们可以把这些命题简单地理解为一些合法的字符串）。例如：

<math>\forall a:\sim (a+1)=0</math>

<math>\forall a:\sim (a+1)=0</math>

即对于任意的自然数a，a+1不为0；其中<math>\forall</math>是任意量词，<math>\forall a</math>就表示任意的自然数a。<math>\sim</math>表示非。再例如：

即对于任意的自然数a，a+1不为0；其中<math>\forall</math>是任意量词，<math>\forall a</math>就表示任意的自然数a。<math>\sim</math>表示非。再例如：

存在着自然数a，使得对于任意给定的自然数b和c：a=(b+2)(c+2)都不成立，也就意味着存在着质数。从一组基本的语句出发（即公理，前面的第一个句子就是系统中的一个公理），按照既定的推理规则（字符串的替换规则）我们就能得到非常丰富的有关自然数的判断语句，我们称这些推导出的语句为定理。

存在着自然数a，使得对于任意给定的自然数b和c：a=(b+2)(c+2)都不成立，也就意味着存在着质数。从一组基本的语句出发（即公理，前面的第一个句子就是系统中的一个公理），按照既定的推理规则（字符串的替换规则）我们就能得到非常丰富的有关自然数的判断语句，我们称这些推导出的语句为定理。

例如下面的语句：

例如下面的语句：

对于任意的自然数a和b，a+b=b+a都成立，就是可以从公理中推出的定理。

对于任意的自然数a和b，a+b=b+a都成立，就是可以从公理中推出的定理。

另外，我们对任意一个合法的字符串都赋予一个真值，来表示该字符串所表达的语句是否为一个真的关于自然数的命题。例如，命题：

另外，我们对任意一个合法的字符串都赋予一个真值，来表示该字符串所表达的语句是否为一个真的关于自然数的命题。例如，命题：

<math>\forall a,\exists b: a+b=0</math>

<math>\forall a,\exists b: a+b=0</math>

翻译成自然语言就是：“对于任意的自然数a，都存在着一个自然数b，使得a+b=0”。那么，我们知道这个命题就是假的，这是因为我们能够举出反例，当a=1的时候，就不会存在正整数b使得a+b=0成立。而对于命题：

翻译成自然语言就是：“对于任意的自然数a，都存在着一个自然数b，使得a+b=0”。那么，我们知道这个命题就是假的，这是因为我们能够举出反例，当a=1的时候，就不会存在正整数b使得a+b=0成立。而对于命题：

<math>\forall a, \exists b:\sim (a+b)=0</math>

<math>\forall a, \exists b:\sim (a+b)=0</math>

就是一个真命题。所以，我们知道：'''所有的系统中的合法命题都可以分成真假两类'''。

就是一个真命题。所以，我们知道：'''所有的系统中的合法命题都可以分成真假两类'''。

我们称一个公理系统是'''一致的'''，是指命题A和~A（即非A）不会同时都是该系统中的定理。这也就意味着该公理系统不包含逻辑矛盾。我们称一个公理系统是'''完备的'''，是指任意的真的命题都是该系统中的定理，也就是所有的真命题都可以通过推导而产生出来。

我们称一个公理系统是'''一致的'''，是指命题A和~A（即非A）不会同时都是该系统中的定理。这也就意味着该公理系统不包含逻辑矛盾。我们称一个公理系统是'''完备的'''，是指任意的真的命题都是该系统中的定理，也就是所有的真命题都可以通过推导而产生出来。

我们当然希望能够构建出一个足够强有力的公理系统，使得它的内部既不包含不一致的逻辑矛盾，同时又可以包含所有的关于自然数的真的命题。但是，可惜的是，哥德尔定理告诉我们，'''对于任何足够强有力的公理系统来说，一致性和完备性不能同时被满足'''。

我们当然希望能够构建出一个足够强有力的公理系统，使得它的内部既不包含不一致的逻辑矛盾，同时又可以包含所有的关于自然数的真的命题。但是，可惜的是，哥德尔定理告诉我们，'''对于任何足够强有力的公理系统来说，一致性和完备性不能同时被满足'''。

哥德尔是如何证明这个定理的呢？关键就在于哥德尔利用这个公理系统的基本语法构建了一个哥德尔句子：

哥德尔是如何证明这个定理的呢？关键就在于哥德尔利用这个公理系统的基本语法构建了一个哥德尔句子：

G=“我不是系统中的定理”

G=“我不是系统中的定理”

下面，我们就来看看究竟G是不是此公理系统中的定理？假如G是定理，也就意味着我们可以从公理出发推导出G这句话。如果接受了G，那么根据G自己的判断，G又不是系统中的定理，也就意味着系统可以得到了~G（非G）。也就是说G和~G会同时存在于系统中。于是，这意味着我们的公理系统包含着逻辑矛盾，因此该系统是不一致的。

下面，我们就来看看究竟G是不是此公理系统中的定理？假如G是定理，也就意味着我们可以从公理出发推导出G这句话。如果接受了G，那么根据G自己的判断，G又不是系统中的定理，也就意味着系统可以得到了~G（非G）。也就是说G和~G会同时存在于系统中。于是，这意味着我们的公理系统包含着逻辑矛盾，因此该系统是不一致的。

那么，如果我们假设G不是系统中的定理呢？我们看到G就在陈述一个事实：G不是系统中的定理，而我们知道这一事实必然是真的。于是，我们得到了一个真的命题，然而此命题却并不是该系统的定理，也就是说该公理系统是'''不完备的'''。

那么，如果我们假设G不是系统中的定理呢？我们看到G就在陈述一个事实：G不是系统中的定理，而我们知道这一事实必然是真的。于是，我们得到了一个真的命题，然而此命题却并不是该系统的定理，也就是说该公理系统是'''不完备的'''。

所以，哥德尔证明了任何此类包含自然数性质的公理系统都不能同时具备一致性和完备性。

所以，哥德尔证明了任何此类包含自然数性质的公理系统都不能同时具备一致性和完备性。

下面，我们就来看看哥德尔是如何构造出哥德尔语句G的。首先，哥德尔如何用谓词逻辑语句来表达出“是系统中的定理”这个性质的呢？

下面，我们就来看看哥德尔是如何构造出哥德尔语句G的。首先，哥德尔如何用谓词逻辑语句来表达出“是系统中的定理”这个性质的呢？

首先，我们可以将任意一个有关自然数陈述的命题编码成自然数（哥德尔配数）。例如“<math> \forall a, \exists b: \sim (a+b)=0 </math>”可以编码为11223......。

首先，我们可以将任意一个有关自然数陈述的命题编码成自然数（哥德尔配数）。例如“<math> \forall a, \exists b: \sim (a+b)=0 </math>”可以编码为11223......。

其次，任何一个由若干语句构成的推导过程也可以用更大的自然数来编码。例如，我们看两步推导：

其次，任何一个由若干语句构成的推导过程也可以用更大的自然数来编码。例如，我们看两步推导：

<math> \forall a,\exists b:\sim (a+b)=0 </math>

<math> \forall a,\exists b:\sim (a+b)=0 </math>

<math> \exists b:\sim b+3=0 </math>（将上一条语句中的任意变量a用特殊的数3来替换）

<math> \exists b:\sim b+3=0 </math>（将上一条语句中的任意变量a用特殊的数3来替换）

如果第一条语句的编码是11223，第二条语句的编码是23543，则这两步推导就可以表示成数字：11223023543，其中0为不同行之间的分隔符。所以自然数11223023543就唯一地表示出了一个两步的推导。

如果第一条语句的编码是11223，第二条语句的编码是23543，则这两步推导就可以表示成数字：11223023543，其中0为不同行之间的分隔符。所以自然数11223023543就唯一地表示出了一个两步的推导。

最后，我们可以用基本符号和运算构造一个命题函数（可计算函数）：<math> T(m,n) </math>，我只要把任何一个推导过程的编码<math>m</math>以及命题语句的编码<math>n</math>输入到该函数<math>T(m,n)</math>中，<math>T</math>就能够计算出该系统从公理出发，在经历了m所代表的推导过程之后就能够推导出n所代表的结论。这样，语句：

最后，我们可以用基本符号和运算构造一个命题函数（可计算函数）：<math> T(m,n) </math>，我只要把任何一个推导过程的编码<math>m</math>以及命题语句的编码<math>n</math>输入到该函数<math>T(m,n)</math>中，<math>T</math>就能够计算出该系统从公理出发，在经历了m所代表的推导过程之后就能够推导出n所代表的结论。这样，语句：

<math>\exists m:T(m,n) </math>

<math>\exists m:T(m,n) </math>

所表达的就是“n所对应的语句是该系统中的一个定理”。

所表达的就是“n所对应的语句是该系统中的一个定理”。

接下来，我们来看这个公理系统如何表达“我”这个关键的词语。哥德尔巧妙的构造了一个自然数函数<math>Q(n)</math>，<math>Q(n)</math>表达的是将<math>n</math>这个自然数代入到以<math>n</math>为编码的函数<math>N(x)</math>之中所得句子的哥德尔编号，也就是说<math>Q(n)=c(N,n)</math>，其中<math>c(N,n)</math>为句子<math>N(n)</math>的哥德尔编号。

接下来，我们来看这个公理系统如何表达“我”这个关键的词语。哥德尔巧妙的构造了一个自然数函数<math>Q(n)</math>，<math>Q(n)</math>表达的是将<math>n</math>这个自然数代入到以<math>n</math>为编码的函数<math>N(x)</math>之中所得句子的哥德尔编号，也就是说<math>Q(n)=c(N,n)</math>，其中<math>c(N,n)</math>为句子<math>N(n)</math>的哥德尔编号。

例如，考虑一个语句：

例如，考虑一个语句：

假设这个新公式的哥德尔编号为3445。因此我们定义当函数<math>Q</math>作用到1199这个数字上面的时候就得到3445，也就是<math>Q(1199)=3445</math>。注意，实际上这个<math>Q(x)</math>就是与上一小节中的蒯恩程序等价的蒯恩函数。

假设这个新公式的哥德尔编号为3445。因此我们定义当函数<math>Q</math>作用到1199这个数字上面的时候就得到3445，也就是<math>Q(1199)=3445</math>。注意，实际上这个<math>Q(x)</math>就是与上一小节中的蒯恩程序等价的蒯恩函数。

显然<math>Q</math>函数本身也有一个哥德尔编号，记为<math>q</math>，那么'''Q(q)就是“我”的表达了，这是因为经过Q函数计算得出的数字Q(q)恰恰就是Q(q)这个公式自己的哥德尔编号'''。（如果不能理解这一点，请参考第2节语言的自指）

显然<math>Q</math>函数本身也有一个哥德尔编号，记为<math>q</math>，那么'''Q(q)就是“我”的表达了，这是因为经过Q函数计算得出的数字Q(q)恰恰就是Q(q)这个公式自己的哥德尔编号'''。（如果不能理解这一点，请参考第2节语言的自指）

这样，我们便可以把“我”和“不是定理”连接起来构成一个新句子：

这样，我们便可以把“我”和“不是定理”连接起来构成一个新句子：

<math>G=Q_o, T(q_o t)= ''\sim \exists m:T(m,Q(q_o t))''</math>

<math>G=Q_o, T(q_o t)= ''\sim \exists m:T(m,Q(q_o t))''</math>

让我们来翻译一下这句话：不存在一个自然数<math>m</math>使得：<math>m</math>和<math>Q(q_o t)</math>构成证明对。也就是说<math>Q(q_o t)</math>不是系统中的定理。而<math>Q(q_o t)</math>是什么呢？根据函数<math>Q</math>的定义，<math>Q(q_o t)</math>就是把<math>q_o t</math>这个数代入到<math>q_o t</math>所对应的语句中的自由变元之后得到的那个语句的哥德尔编码。而我们知道<math>q_o t</math>代入它自己<math>Q_o T(n)</math>，并替换自由变元<math>n</math>之后得到的那个数就是<math>G</math>自己的哥德尔编号，所以<math>G</math>也可以翻译为：

让我们来翻译一下这句话：不存在一个自然数<math>m</math>使得：<math>m</math>和<math>Q(q_o t)</math>构成证明对。也就是说<math>Q(q_o t)</math>不是系统中的定理。而<math>Q(q_o t)</math>是什么呢？根据函数<math>Q</math>的定义，<math>Q(q_o t)</math>就是把<math>q_o t</math>这个数代入到<math>q_o t</math>所对应的语句中的自由变元之后得到的那个语句的哥德尔编码。而我们知道<math>q_o t</math>代入它自己<math>Q_o T(n)</math>，并替换自由变元<math>n</math>之后得到的那个数就是<math>G</math>自己的哥德尔编号，所以<math>G</math>也可以翻译为：

G=“G不是一个定理”或者，干脆翻译为：

G=“G不是一个定理”或者，干脆翻译为：

G=“我不是一个定理”。

G=“我不是一个定理”。

于是，通过将蒯恩句子增加了一个“不是定理”的判断，我们便构造出类似的自指悖论出来。有关哥德尔定理的表述以及证明的细节请参考《[https://book.douban.com/subject/1291204/ 哥德尔、艾舍尔、巴赫——集异璧之大成]》一书的第十四章。

于是，通过将蒯恩句子增加了一个“不是定理”的判断，我们便构造出类似的自指悖论出来。有关哥德尔定理的表述以及证明的细节请参考《[https://book.douban.com/subject/1291204/ 哥德尔、艾舍尔、巴赫——集异璧之大成]》一书的第十四章。