7,129
个编辑
更改
跳到导航
跳到搜索
第488行：
第488行： − + − + 第500行：
第500行： − + 第507行：
第507行： − + − + 第548行：
第548行： − + − + 第558行：
第558行： − + 第569行：
第569行： − + − + 第583行：
第583行： − + − +
→哥德尔定理2
首先，我们需要简单介绍一下哥德尔定理的背景。哥德尔定理所讨论的对象是关于自然数的一套公理系统。此公理系统是由关于自然数性质的命题构成的（我们可以把这些命题简单地理解为一些合法的字符串）。例如：
首先，我们需要简单介绍一下哥德尔定理的背景。哥德尔定理所讨论的对象是关于自然数的一套公理系统。此公理系统是由关于自然数性质的命题构成的（我们可以把这些命题简单地理解为一些合法的字符串）。例如：
<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>表示非。再例如：
<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,b: (a+b)=(a+b)</math>
:<math> \forall a,b: (a+b)=(a+b)</math>
对于任意的自然数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>
<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来替换）
最后，我们可以用基本符号和运算构造一个命题函数（可计算函数）：<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>
例如，考虑一个语句：
例如，考虑一个语句：
<math> \sim (a+1)=0</math>
:<math> \sim (a+1)=0</math>
在该语句中a是一个不受任何量词约束的自由变元。假设这一公式的哥德尔编号为1199，那么将1199这个数字代入到原公式中（也就是让a=1199），就得到公式：
在该语句中a是一个不受任何量词约束的自由变元。假设这一公式的哥德尔编号为1199，那么将1199这个数字代入到原公式中（也就是让a=1199），就得到公式：
<math> \sim (1199+1)=0</math>
:<math> \sim (1199+1)=0</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_o T(n)= ''\sim \exists m:T(m,Q(n))''</math>
:<math>Q_o T(n)= ''\sim \exists m:T(m,Q(n))''</math>
其中<math>n</math>为该句子中的自由变元。我们记该句子的哥德尔编号为：<math>q_o t</math>，就可以得到哥德尔句子：
其中<math>n</math>为该句子中的自由变元。我们记该句子的哥德尔编号为：<math>q_o t</math>，就可以得到哥德尔句子：
<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>