更改
跳到导航
跳到搜索
第405行：
第405行： − <math>∀a:~(a+1)=0</math>+ − + − − 如： 第421行：
第419行： − 另外，我们对任意一个合法的字符串都赋予一个真值，来表示该字符串所表达的语句是否为一个真的+ − − 关于自然数的命题。例如，命题： 第431行：
第427行： − 就是一个真命题。所以，我们知道：所有的系统中的合法命题都可以分成真假两类。+ − 我们称一个公理系统是一致的，是指命题A和~A（即非A）不会同时都是该系统中的定理。这也就意味着该公理系统不包含逻辑矛盾。我们称一个公理系统是完备的，是指任意的真的命题都是该系统中的定理，也就是所有的真命题都可以通过推导而产生出来。+ − 我们当然希望能够构建出一个足够强有力的公理系统，使得它的内部既不包含不一致的逻辑矛盾，同时又可以包含所有的关于自然数的真的命题。但是，可惜的是，哥德尔定理告诉我们，对于任何足够强有力的公理系统来说，一致性和完备性不能同时被满足。+ 第443行：
第439行： − 那么，如果我们假设G不是系统中的定理呢？我们看到G就在陈述一个事实：G不是系统中的定理，而我们知道这一事实必然是真的。于是，我们得到了一个真的命题，然而此命题却并不是该系统的定理，也就是说该公理系统是不完备的。+ 第449行：
第445行： − + 第477行：
第473行： − 显然Q函数本身也有一个哥德尔编号，记为q，那么Q(q)就是“我”的表达了，这是因为经过Q函数计算得出的数字Q(q)恰恰就是Q(q)这个公式自己的哥德尔编号。（如果不能理解这一点，请参考第2节语言的自指）+ 第493行：
第489行： − 于是，通过将蒯恩句子增加了一个“不是定理”的判断，我们便构造出类似的自指悖论出来。有关哥德尔定理的表述以及证明的细节请参考《哥德尔、艾舍尔、巴赫——集异璧之大成》一书的第十四章。+ − (3)图灵停机问题与哥德尔定理之间的比较+ + + 第504行：
第502行： − 接下来的蓝色单元格表示的是系统所具备的另外一种基本属性，即意义判断。在计算机程序的世界中，我们知道程序可以分为停机的程序和不停机的程序两种；而对于命题语句来说，它们又可以分成真命题和假命题两种。这种意义判断是一个非常微妙的东西，因为，任意拿来一个程序或者是命题，我们观察者确信它们会存在着一种意义，或者是程序停机或者是命题正确。尽管在很多情况下，我们并不能马上给出这样的判断。例如，对于很复杂的程序来说，尽管我们已经等了100天，它没有停机，但是我们并不知道它会不会在第101天内停下来。但是，我们会倾向于认为任何的单元都具备某种意义或者价值，而且我们迫切地希望这种意义判断能够让系统自身告诉我们答案，也就是希望存在一个计算机程序H能够自动给出任意程序X作用到y上是否停机；或者是希望公理体系中的定理能够自动帮我们判断所有的命题是否为真，这就是语句“m:T(m,n)”的作用。尽管这个梦想最终必将破灭。我们看到，这种意义判断是破坏性自指系统特有的，而构建性自指系统不具备的重要属性之一。+
无编辑摘要
首先，我们需要简单介绍一下哥德尔定理的背景。哥德尔定理所讨论的对象是关于自然数的一套公理系统。此公理系统是由关于自然数性质的命题构成的（我们可以把这些命题简单地理解为一些合法的字符串）。例如：
首先，我们需要简单介绍一下哥德尔定理的背景。哥德尔定理所讨论的对象是关于自然数的一套公理系统。此公理系统是由关于自然数性质的命题构成的（我们可以把这些命题简单地理解为一些合法的字符串）。例如：
∀a:~(a+1)=0
即对于任意的自然数a，a+1不为0；其中∀是任意量词，∀a就表示任意的自然数a。~表示非。再例
即对于任意的自然数a，a+1不为0；其中∀是任意量词，∀a就表示任意的自然数a。~表示非。再例如：
∃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都成立，就是可以从公理中推出的定理。
另外，我们对任意一个合法的字符串都赋予一个真值，来表示该字符串所表达的语句是否为一个真的关于自然数的命题。例如，命题：
∀a,∃b:a+b=0
∀a,∃b:a+b=0
∀a,∃b:~(a+b)=0
∀a,∃b:~(a+b)=0
就是一个真命题。所以，我们知道：'''所有的系统中的合法命题都可以分成真假两类'''。
我们称一个公理系统是'''一致的'''，是指命题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的。首先，哥德尔如何用谓词逻辑语句来表达出“是系统中的定理”这个性质的呢？
首先，我们可以将任意一个有关自然数陈述的命题编码成自然数（哥德尔配数）。例如“∀a,∃b:~(a+b)=0”可以编码为11223„„。
首先，我们可以将任意一个有关自然数陈述的命题编码成自然数（哥德尔配数）。例如“∀a,∃b:~(a+b)=0”可以编码为11223......。
其次，任何一个由若干语句构成的推导过程也可以用更大的自然数来编码。例如，我们看两步推导：
其次，任何一个由若干语句构成的推导过程也可以用更大的自然数来编码。例如，我们看两步推导：
假设这个新公式的哥德尔编号为3445。因此我们定义当函数Q作用到1199这个数字上面的时候就得到3445，也就是Q(1199)=3445。注意，实际上这个Q(x)就是与上一小节中的蒯恩程序等价的蒯恩函数。
假设这个新公式的哥德尔编号为3445。因此我们定义当函数Q作用到1199这个数字上面的时候就得到3445，也就是Q(1199)=3445。注意，实际上这个Q(x)就是与上一小节中的蒯恩程序等价的蒯恩函数。
显然Q函数本身也有一个哥德尔编号，记为q，那么'''Q(q)就是“我”的表达了，这是因为经过Q函数计算得出的数字Q(q)恰恰就是Q(q)这个公式自己的哥德尔编号'''。（如果不能理解这一点，请参考第2节语言的自指）
这样，我们便可以把“我”和“不是定理”连接起来构成一个新句子：
这样，我们便可以把“我”和“不是定理”连接起来构成一个新句子：
G=“我不是一个定理”。
G=“我不是一个定理”。
于是，通过将蒯恩句子增加了一个“不是定理”的判断，我们便构造出类似的自指悖论出来。有关哥德尔定理的表述以及证明的细节请参考《[https://book.douban.com/subject/1291204/ 哥德尔、艾舍尔、巴赫——集异璧之大成]》一书的第十四章。
====图灵停机问题与哥德尔定理之间的比较====
下面，我们就来比较一下图灵停机问题以及哥德尔定理证明过程中所用到的共同的自指技巧，请看下表1。
下面，我们就来比较一下图灵停机问题以及哥德尔定理证明过程中所用到的共同的自指技巧，请看下表1。
表1给出了图灵停机问题与哥德尔定理，以及证明这两个结论时所用的自指悖论技巧的全部细节对照表。
表1给出了图灵停机问题与哥德尔定理，以及证明这两个结论时所用的自指悖论技巧的全部细节对照表。
序还是命题语句，它们都是由一些基本的符号拼接而成的，同时这些符号串都能够充当动词——也就是它们可以对别的符号串进行运算操作。另外，至关重要的一点是，这两个系统都能够通过编码的手段而谈论其自身。
序还是命题语句，它们都是由一些基本的符号拼接而成的，同时这些符号串都能够充当动词——也就是它们可以对别的符号串进行运算操作。另外，至关重要的一点是，这两个系统都能够通过编码的手段而谈论其自身。
接下来的蓝色单元格表示的是系统所具备的另外一种基本属性，即'''意义判断'''。在计算机程序的世界中，我们知道程序可以分为停机的程序和不停机的程序两种；而对于命题语句来说，它们又可以分成真命题和假命题两种。这种意义判断是一个非常微妙的东西，因为，任意拿来一个程序或者是命题，我们观察者确信它们会存在着一种意义，或者是程序停机或者是命题正确。尽管在很多情况下，我们并不能马上给出这样的判断。例如，对于很复杂的程序来说，尽管我们已经等了100天，它没有停机，但是我们并不知道它会不会在第101天内停下来。但是，我们会倾向于认为任何的单元都具备某种意义或者价值，而且我们迫切地希望这种意义判断能够让系统自身告诉我们答案，也就是希望存在一个计算机程序H能够自动给出任意程序X作用到y上是否停机；或者是希望公理体系中的定理能够自动帮我们判断所有的命题是否为真，这就是语句“m:T(m,n)”的作用。尽管这个梦想最终必将破灭。我们看到，这种意义判断是破坏性自指系统特有的，而构建性自指系统不具备的重要属性之一。
其次，让我们来看黄色部分的单元格。它们都是利用蒯恩技术来构建自指的核心部分。这个技术与我们前两节谈论的建构性自指部分并没有本质的区别。
其次，让我们来看黄色部分的单元格。它们都是利用蒯恩技术来构建自指的核心部分。这个技术与我们前两节谈论的建构性自指部分并没有本质的区别。