更改
跳到导航
跳到搜索
第409行：
第409行： − + 第426行：
第426行： − − 就是一个真命题。所以，我们知道：'''所有的系统中的合法命题都可以分成真假两类'''。 − − 我们称一个公理系统是'''一致的'''，是指命题A和~A（即非A）不会同时都是该系统中的定理。这也就意味着该公理系统不包含逻辑矛盾。我们称一个公理系统是'''完备的'''，是指任意的真的命题都是该系统中的定理，也就是所有的真命题都可以通过推导而产生出来。 − − 我们当然希望能够构建出一个足够强有力的公理系统，使得它的内部既不包含不一致的逻辑矛盾，同时又可以包含所有的关于自然数的真的命题。但是，可惜的是，哥德尔定理告诉我们，'''对于任何足够强有力的公理系统来说，一致性和完备性不能同时被满足'''。 − − 哥德尔是如何证明这个定理的呢？关键就在于哥德尔利用这个公理系统的基本语法构建了一个哥德尔句子： 第453行：
第445行： − 首先，我们可以将任意一个有关自然数陈述的命题编码成自然数（哥德尔配数）。例如“∀a,∃b:~(a+b)=0”可以编码为11223......。+ − ∀a,∃b:~(a+b)=0+ − ∃b:~(3+b)=0（将上一条语句中的任意变量a用特殊的数3来替换）+ − 最后，我们可以用基本符号和运算构造一个命题函数（可计算函数）：T(m,n)，我只要把任何一个推导过程的编码m以及命题语句的编码n输入到该函数T(m,n)中，T就能够计算出该系统从公理出发，在经历了m所代表的推导过程之后就能够推导出n所代表的结论。这样，语句：+ − ∃m:T(m,n)+ − 接下来，我们来看这个公理系统如何表达“我”这个关键的词语。哥德尔巧妙的构造了一个自然数函数Q(n)，Q(n)表达的是将n这个自然数代入到以n为编码的函数N(x)之中所得句子的哥德尔编号，也就是说Q(n)=c(N,n)，其中c(N,n)为句子N(n)的哥德尔编号。+ − ~(a+1)=0+ − ~(1199+1)=0+ − 假设这个新公式的哥德尔编号为3445。因此我们定义当函数Q作用到1199这个数字上面的时候就得到3445，也就是Q(1199)=3445。注意，实际上这个Q(x)就是与上一小节中的蒯恩程序等价的蒯恩函数。+ − 显然Q函数本身也有一个哥德尔编号，记为q，那么'''Q(q)就是“我”的表达了，这是因为经过Q函数计算得出的数字Q(q)恰恰就是Q(q)这个公式自己的哥德尔编号'''。（如果不能理解这一点，请参考第2节语言的自指）+ − QоT(n)=“~m:T(m,Q(n))”+ − + − 让我们来翻译一下这句话：不存在一个自然数m使得：m和Q(qоt)构成证明对。也就是说Q(qоt)不是系统中的定理。而Q(qоt)是什么呢？根据函数Q的定义，Q(qоt)就是把qоt这个数代入到qоt所对应的语句中的自由变元之后得到的那个语句的哥德尔编码。而我们知道qоt代入它自己QоT(n)，并替换自由变元n之后得到的那个数就是G自己的哥德尔编号，所以G也可以翻译为：+
→哥德尔定理2
即对于任意的自然数a，a+1不为0；其中∀是任意量词，∀a就表示任意的自然数a。~表示非。再例如：
即对于任意的自然数a，a+1不为0；其中∀是任意量词，∀a就表示任意的自然数a。~表示非。再例如：
<math>\exists a \forall b \forall c:\sim a=(b+2) (c+2) </math>
<math>\exists a \forall b \forall c:\sim a=(b+2) (c+2) </math>
存在着自然数a，使得对于任意给定的自然数b和c：a=(b+2)(c+2)都不成立，也就意味着存在着质数。从一组基本的语句出发（即公理，前面的第一个句子就是系统中的一个公理），按照既定的推理规则（字符串的替换规则）我们就能得到非常丰富的有关自然数的判断语句，我们称这些推导出的语句为定理。
存在着自然数a，使得对于任意给定的自然数b和c：a=(b+2)(c+2)都不成立，也就意味着存在着质数。从一组基本的语句出发（即公理，前面的第一个句子就是系统中的一个公理），按照既定的推理规则（字符串的替换规则）我们就能得到非常丰富的有关自然数的判断语句，我们称这些推导出的语句为定理。
<math>\forall a, \exists b:\sim (a+b)=0</math>
<math>\forall a, \exists b:\sim (a+b)=0</math>
就是一个真命题。所以，我们知道：'''所有的系统中的合法命题都可以分成真假两类'''。
就是一个真命题。所以，我们知道：'''所有的系统中的合法命题都可以分成真假两类'''。
下面，我们就来看看哥德尔是如何构造出哥德尔语句G的。首先，哥德尔如何用谓词逻辑语句来表达出“是系统中的定理”这个性质的呢？
下面，我们就来看看哥德尔是如何构造出哥德尔语句G的。首先，哥德尔如何用谓词逻辑语句来表达出“是系统中的定理”这个性质的呢？
首先，我们可以将任意一个有关自然数陈述的命题编码成自然数（哥德尔配数）。例如“<math> \forall a, \exists b: \sim (a+b)=0 </math>”可以编码为11223......。
其次，任何一个由若干语句构成的推导过程也可以用更大的自然数来编码。例如，我们看两步推导：
其次，任何一个由若干语句构成的推导过程也可以用更大的自然数来编码。例如，我们看两步推导：
<math> \forall a,\exists b:\sim (a+b)=0 </math>
<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>\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> \sim (a+1)=0</math>
在该语句中a是一个不受任何量词约束的自由变元。假设这一公式的哥德尔编号为1199，那么将1199这个数字代入到原公式中（也就是让a=1199），就得到公式：
在该语句中a是一个不受任何量词约束的自由变元。假设这一公式的哥德尔编号为1199，那么将1199这个数字代入到原公式中（也就是让a=1199），就得到公式：
<math> \sim (1199+1)=0</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_о T(n)= \sim \exists m:T(m,Q(n))</math>
其中n为该句子中的自由变元。我们记该句子的哥德尔编号为：qоt，就可以得到哥德尔句子：
其中n为该句子中的自由变元。我们记该句子的哥德尔编号为：qоt，就可以得到哥德尔句子：
G=QоT(qоt)=“~m:T(m,Q(qоt))”
<math>G=Q_о T(q_о t)= \sim \exists m :T(m,Q(q_о t)) </math>
让我们来翻译一下这句话：不存在一个自然数m使得：<math>m</math>和<math>Q(q_о t)</math>构成证明对。也就是说<math>Q(q_о t)</math>不是系统中的定理。而<math>Q(q_о t)是什么呢？根据函数Q的定义，<math>Q(q_о t)</math>就是把<math>q_о t</math>这个数代入到<math>q_о t</math>所对应的语句中的自由变元之后得到的那个语句的哥德尔编码。而我们知道<math>q_о t</math>代入它自己<math>Q_о T(n)</math>，并替换自由变元<math>n</math>之后得到的那个数就是<math>G</math>自己的哥德尔编号，所以<math>G</math>也可以翻译为：
G=“G不是一个定理”或者，干脆翻译为：
G=“G不是一个定理”或者，干脆翻译为：