Godel定理之拙见
首先声明，本人不是逻辑论专家，写这个一方面基于以往的一些了解，另一方面也是边看边写。对于Godel不完备定理的理解纯属一孔之见。
其次，总的来说，我的观点是，对于Godel不完备定理。主要的不在于这个定理的推论，而在于我们通常并没有搞清楚这个定理到底说了些什么。这是因为我们通常看到的对于这个定理的叙述使用的是自然语言而非精确的数学表达式。比如说，该定理的叙述中，“真的命题”，什么是“真”？又比如，“证明”一词的含义并不是我们通常理解的证明，而是要弱得多。稍稍准确一点，命题中的所谓可证明，实际上应该叫做“可构造”。
既然我们误解了Godel定理，或者说我们对于Godel定理的理解是不完备的，所以通常的很多所谓推论也不一定仍然有意义。比如Hawking对这个定理的看法，在我看来，属于彻底的错误。
最后再声明一下，虽然在以后的帖子中，我要说某某说法是错误的。但这仅仅是个人观点。说不定错的不是他们。:)
| 论坛嘉宾: 萍踪浪迹 gauge 季候风 |
|
gauge  发表文章数: 596
|
|
||
|
gauge 发表文章数: 596
|
Godel第一不完备性定理：任何一个内部一致的形式体系，若包含了基本算术公理体系，则该体系不是完备的。亦即，存在一个命题，这个命题是真的，但不可证明。
Godel定理涉及到一些基本术语。先简介如下。 理论，theory 陈述，statement 在理论中可证明，provable in the theory 一致，consistent 可构造，can be constructed Godel命题，Godel sentence 基本算术，elementary arithmetic 理论，是指由一些陈述构成的集合，其中可能有无穷多个陈述。理论中的某些被设置为公理而无需证明。某些陈述可由这些公理导出，这样的陈述称之为一个定理。定理等价于真(true)的陈述。一个公理体系的全部出发点实际上不仅仅包含公理，还包含其基本的记号以及定义。由此可知Godel定理中的证明一词的含义和我们通常理解的并不相同。 可以证明，确切地说，在某个给定的理论体系中是可以证明的，其含义是指，可以由该理论体系的基本记号、定义以及公理，使用标准一阶逻辑导出。一个理论被称为一致，是指在这个理论中，不能证明互相矛盾的陈述。 可以构造的陈述，是指，存在一些机械的过程，可以由给定的公理、原始记号、定义以及一阶逻辑，构造出该陈述。 真的但是不可证明的陈述被称为“Godel命题”。事实上，存在无穷多个这样的“Gedel命题”。基本算术体系，是指在自然数集合上，赋予加法和乘法两种运算的理论体系。
|
||
|
gauge 发表文章数: 596
|
通常对于Godel不完备定理的讨论，严谨的说法是其定理否定了Hilbert计划。不严谨的说法比比皆是，比如认为Godel不完备定理证明了机器能力的局限等等。
Hilbert计划起源于以证明了不动点定理而闻名的荷兰数学家Brouwer提出的一个数学哲学观点，称之为直觉主义。Brouwer认为存在性的证明是不完美的，或者说是值得怀疑的。比如其本人所证明的不动点定理，单位球到自身的连续映射必定有一个不动点。定理断言存在一个不动点，然而无论是该定理还是定理的证明都没有告诉我们这个不动点到底是空间中的哪个点。换言之，这个证明不是一个构造性的证明。我们再举个例子来看构造和非构造证明。Weierstrass构造了一个连续然而处处不可导的函数，这是一个构造性的证明，我们可以明确的看到这个函数。Banach则证明了，几乎所有连续函数函数都是处处不可微的。这个证明就是非构造性的。虽然这种函数很多，但由Banach的证明，我们一个这样的函数都没有看到。在Brouwer看来，Banach定理是无意义的。Brouwer后来更是走向极端，宣称放弃他赖以成名的不动点定理，因为它不是构造性的。再如，微分方程解的存在性，Brouwer认为必需把解构造出来才是有意义的。通常证明存在性的方法是，假定不存在，然后导致矛盾。然后由这个矛盾得到存在性。这当然是无懈可击的证明。但是对于Brouwer来说，既然他已经反对了这种非构造新证明，他就必须反对这种证明方式。因为这样的证明必然导致非构造性的存在性。从逻辑上看，通过矛盾来反证的基础是排中律。排中律的含义是一个陈述P, 则P或者NotP(P的否定)必有而且只有一个成立。放弃排中律给证明带来了很大的困难。放弃排中律得到的形式逻辑体系是不完备的。放弃排中律导致一个命题否定两次不一定回到原命题，即NotNotP不一定和原命题P等价。这是很糟糕的。为此，Brouwer在他的直觉逻辑体系中又增加了否定之否定即原命题这一条。这一行为被讽刺为“Brouwer荒谬之荒谬”。 Brouwer进一步认为，全部数学理论应该建立在其直觉逻辑的基础之上。Brouwer由此否认几乎全部的数学，事实上只有少数理论可以由Brouwer的直觉逻辑体系得到。虽然Brouwer的观点看起来不那么惹人喜欢。但这不代表其没有影响力。Brouwer的观点激怒了很多的数学家，包括Hilbert. 作为回击，Hilbert提出一个计划，希望由有限、组合的方式，先证明最简单的算术是一个内部一致的理论，然后以此为基础证明数学分析的一致性，尔后进一步证明整个数学的一致性。Hilbert计划中的证明就是纯粹构造式的。由前面的分析可知，这个计划中的数学证明没有排中律参与。 用现在的语言来叙述，Hilbert计划实际上是要寻求一些算法，这些算法可以构造出真的算术命题。Penrose举过一个例子。1966年美国数学家罗伯特.伯格尔(Robert Berger)证明了平面上能够按某些给定的基本图形拼图(tiling)的多米诺问题(Domino Problem)，却不可能由预先设计好的计算程序给出来。也就是说，只能一步一步用人的脑筋去拼合，这实际上就是直接证明了存在一个不可计算的数学方法。但是也可以用机器的电脑一步一步拼接出来，没有任何理由可以说明机器一定不能拼出来。 另一个非构造性的例子，复变函数理论中对于代数基本定理的证明。我们知道可以由Cauchy不等式来证明，也可以由简单的代数拓扑来证明，其完全不同的证明方式不下5个。但这些证明都不告诉我们多项式的解到底是什么。而Galois证明的代数方程一般无根号解实际上就是在某种程度上否认了可构造解的存在性。 我个人认为可构造性是理解Godel不完备定理中的关键。
|
||
|
linhaier  发表文章数: 155
|
haotie,will be going on?
 逝者如斯夫
|
||
|
kanex  发表文章数: 447
|
个人感觉 Godel定理 可能意义很小，只有理论价值，就像拓扑学里面的一些变态构造一样。
其实所谓"证明"，就是寻找Boolean Algebra在某Model中的一个faithful Representation。 like a great ring of pure and endless light
|
||
|
星空浩淼 发表文章数: 799
|
先不管gauge兄最后所持观点是否正确，前面的论述写得非常好。
gauge兄既然打开了这个话题。不妨全方位地展开（篇幅长没有关系，时间跨度长也没有关系），让大家有一个完整的了解，然后大家再参与深入思考和讨论。这样做是值得的，因为这个话题影响深远，兴趣范围早已经超出逻辑学范围。对自己也是一个锻炼，理清思想脉络。 以前在这里也多次提及这个话题，但从来没有系统论述过Godel定理，没有详细介绍过与之有关的背景来龙去脉，这时的讨论很容易停留在一知半解上。我曾经有过在这里系统论述介绍它的野心，但过去钻研和学习逻辑时（92年－95年）获得的知识与体会，现在差不多都忘了。即使在当年的基础上，我也得先进一步学习钻研才行，但没有这个时间条件，如果我是搞数学的还差不多。总之我这方面的知识和能力都有限。另一方面，我相信，gauge兄是最有有能力和资格做这件事的。为此，你可能要全方位多消化一些资料，从相关的哲学思想到逻辑和数学本身，甚至它的应用（记得有一本书《可计算性与不可解性》，图书馆应该有，里面关于Godel定理的论述有一定深度，反正我当年看了一半就看不下去）。我认为这样做对你自己是值得的。如果你最后有什么不同看法，可以拿到国外发表。 也许仅凭看你写的这个系列，我可以很大程度的回忆和新学到相关的东西，那样的话我可以尽量参与讨论。的确，正因为Godel定理的名声远远逻辑范围，科学家和哲学界许多人都感兴趣与好奇，结果导致各种误解和胡乱联系。 One may view the world with the p-eye and one may view it with the q-eye but if one opens both eyes simultaneously then one gets crazy
|
||
|
AndrewAA 发表文章数: 27
|
我觉得数理逻辑的研究的主要目的是消除我们的某些疑虑
他不能告诉我们怎么证明那些变态的定理 但是可以告诉我们我们这样去证明是没有问题的 至少谁都不希望证明了黎曼猜想之后被告知证明所用的数学基础是错的 或者被告知数学的基础本身就是错的 事实上当年很多人就是因为数学的基础不牢固而恐慌 不得不承认，在这个方面布尔巴基作了相当好的工作 作为数理逻辑的重要定理，godel定理从这个角度来说是很重要的 另外，我觉得数理逻辑的研究主要目的不应该是去研究逻辑是什么样的 而是想方设法调整逻辑的结构让他来符合我们现在的习惯 至少我不相信有人会为一个完全不一样但是完美无缺的逻辑系统全盘否定我们现在的数学 目标：谎话组组长（lie group master)...
|
||
|
gauge 发表文章数: 596
|
再论直觉主义
对于直觉主义，一个更好的称呼是：有限可构造主义。 Kronecker是最早的直觉主义者，他只接受整数，认为自然数是上帝创造的，整数是直觉上清楚的因而是可以接受的。Kronecker认为其他都是人造的，可疑的，因而是不可接受的。基于其哲学观点，Kronecker以其全部力气反对Cantor的集合论。Kronecker甚至认为应该从数学中将无理数砍掉，因为无理数不能够通过有限多个步骤构造出来。 Poincare对直觉主义有不少的嘲讽。不述。 H.Weyl也是持有直觉主义观点的数学家。 Brouwer给出了直觉主义的最系统的阐述。简而言之，直觉主义的观点就是通过有限多个步骤可以构造，才是有意义的。直觉主义认为数学定理的正确性和有效性存在于人类的智力中。 无限，确切的说，完成了的无限，实的无限，是直觉主义不允许的。比如，下述的两个陈述： 1，素数只有有限多个； 2，素数有无限多个。 在一个正常人看来，这两个陈述必有而且只有一个成立。但是在Brouwer看来不然，他认为这两个陈述都是没有意义的。 再如，直觉主义认为，无限多个自然数中必有一个取到最小值。 我们可以如此总结直觉主义，摒弃排中律，否定实无限，坚持可构造性。 当然，直觉主义并不完全否定无限。但直觉主义认可的无限是指潜在的没有完成的无限。比如数学归纳法中的无限，由n到(n+1), 在直觉主义看来，这不代表无限，仅仅是一个符号而已。 Hilbert计划其实就是要完成直觉主义。
|
||
|
木木 发表文章数: 159
|
Poincare对直觉主义有不少的嘲讽。不述。
==== 他不也是个直觉主义筒子吗，自扇大耳刮子玩？ 看直觉主义关于实无限还有无理数等的那说法，这意思极端化了还不干脆把抽象思维的有效性给否定了得了。嗷，你可以抽象的数学的思考现实世界，就不允许别人抽象的思考数学世界啊？你数学上证明了现实世界有什么规律时，也不是在现实世界中构造啥具体实验证明的，难道把数学方法全盘从科学里驱逐出去？ 充满了声音和狂热，里面空无一物。
|
||
|
gauge 发表文章数: 596
|
再论一致性
理论的一致性也就是无矛盾，确切的说该理论中不能导出互相矛盾的两个命题。如何证明一个理论体系是无矛盾的呢？举几个例子。 非欧几何的无矛盾性是通过归结到欧氏几何来完成的。亦即通过Poincare模型或者Klein模型，在欧氏几何中重新解释其中的某些术语，这些术语可以与非欧几何的术语一一对应。因而只要欧氏几何无矛盾，则非欧几何也是一致的。这是相对一致性。因为欧氏几何的一致性还需要证明。 欧氏几何的一致性可以由解析几何实现为三维欧氏空间上的代数体系的无矛盾性。进而可以归结为实数系统的一致性。再进一步，由实数理论，又可以归结为自然数体系的一致性。这些都是相对一致性。 所以剩下的就是证明自然数体系的一致性。 上述的归结过程必然需要在某个地方终止，也就是说不可能一直使用相对一致性。终止过程对应的理论的无矛盾性不再可以通过其他的理论来证明，只能在其自身范围内完成。所以，问题是如何在自然数体系内完成其一致性的证明。 Hilbert在1922年提出他的计划，并认为很快就可以得到这个一致性的证明。Hilbert的计划是，由形式化来完成这个任务。 附，Poincare的直觉主义和Weyl,Brouwer,Kronecker的直觉主义完全不是一回事。所以上一个帖子中特别提出，后面几个人的直觉主义可以叫做有限可构造主义。Poincare也讽刺罗素等人的逻辑主义，认为这些人是要把数学归结为同义反复。
|
||
|
源流 发表文章数: 11
|
gauge兄的Godel定理的见解令我耳目一新,确实精辟.我一直认为:哥德尔定理令希尔伯特计划落空是说,任何一个公理体系可以达到自洽,但不能做到唯一性.举个例子,也说欧氏几何和非欧几何,二维空间中的三角形内角之和为180度与不为180度的两个理论体系是自洽的.对于基本算术体系,也存在与之矛盾但自洽的理论体系.现在看到楼主的文章,的确令人兴奋,期待楼主的高见.
|
||
|
星空浩淼 发表文章数: 799
|
gauge兄后面的论述开始有点“急着赶路”的感觉啊！都快要变成古龙的风格了。
One may view the world with the p-eye and one may view it with the q-eye but if one opens both eyes simultaneously then one gets crazy
|
||
|
gauge 发表文章数: 596
|
形式体系
一个形式体系的构成要素为：初始符号、形成规则、初始公式/公理、变形规则。 我们来看一个简单的形式体系。下述的形式体系记作SFT. (simple formal theory). 初始符号只有一个：X 公理A：X 所谓形成规则是指由初始符号如何构成有意义的字符串。对SFT而言，不需要形成规则，或者说所有的字符串都是有意义的。 变形规则，一共两条： D1, 可由X变形为XX. D2, 可由XX变形为X. 由公理X出发，通过变形得到的就是这个形式体系中的定理。例如，由公理A与变形规则D1可证明定理XX. 再用一次D1可证明定理XXX. 注意到变形规则D2并不产生新的定理。 容易看出这个简单体系的全部定理为， X, XX, XXX, XXXX, … 显然可以简单的给上述定理一个编号。比如，X=0, XX=1, XXX=2, …于是我们看到这个形式体系可以实现为自然数体系。而变形规则D1表示计算自然数n的后继n’=n+1. 有很多人认为，形式体系中的定理比如SFT中的XXXX, 是没有意义的，仅仅是一个符号串而已。只有将之实现为自然数或其他具体的体系时，才被认为是有意义的。我个人认为形式体系仍然是有意义的。形式体系和具体的公理体系之间的关系，可以用理论物理与客观世界之间的关系来类比，虽然则两种关系并不完全一致，但其中包含的核心精神是相同的。 为了更好的理解形式体系。我们进一步分析上述简单体系。 首先，SFT体系中的全部定理我们已经列出了，除此以外都不是。比如X(XX)不是SFT体系中的定理。因为括号不是这个体系中的符号。 其次，定理XXX的证明是由初始公式X使用两次变形规则D1得到的。 我们给出一个另外的证明。假设XXX不是定理，并由此导致矛盾。这个矛盾就说明了XXX是一个定理。考虑XX, 若XX是定理，则由变形规则D1可知XXX为定理。既然我们假设XXX不是定理，所以必然有XX也不是定理。同样的论证可知，X也不是定理。但这与SFT体系的初始公式相矛盾。这就证明了XXX确实是一个定理。 显然的确给出了XXX是一个定理的证明。 但是这个证明在形式主义看来是不合法的，或者说是没有意义的。因为形式体系中的证明只能由已经证明的定理通过变形规则得到。 --- 附，更正。在前面的某个短文中，有一句话不完整。 原文，“再如，直觉主义认为，无限多个自然数中必有一个取到最小值。” 更正，“再如，直觉主义认为，无限多个自然数中必有一个取到最小值这样的命题也是没有意义的。”
|
||
|
木木 发表文章数: 159
|
那形式逻辑还能做啥用啊，自己玩？还有什么样的形式体系需要形式逻辑？可真严密，这所谓的形式体系连形式逻辑都不允许使用，啥都自己动手，严密的让人觉着一点都不直觉，更象人造品！
充满了声音和狂热，里面空无一物。
|
||
|
gauge 发表文章数: 596
|
再论形式体系
我们已经指出在形式体系中，新定理只能通过对已经证明的定理使用变形规则得到。没有其他的证明方式。这是一种很强的构造性。即使纯粹演绎逻辑的三段论也是不允许的，除非在变形规则中包含了三段论。Hilbert的形式体系与Brouwer的直觉主义相比而言，对于证明有更加严格、狭窄的含义。不仅仅其中没有排中律，而且规定了定理只能通过变形规则得到。新的定理只能通过已经被证明的定理变形得到。这是一种很强的构造性。 形式体系的其他例子 Lorenzen体系。 初始符号：a,b 形成规则，也称为语法规则：由a,b构成的有限长度的字符串。 初始公理：ab 变形规则 L1, 若X是一个定理，则aXa也是一个定理。 L2, 若X是一个定理，则Xb也是一个定理。 这是一个稍稍复杂点的体系。容易决定这个体系中哪些有意义的字符串是可由初始公理变形得到的定理。 象棋。 初始符号：象棋的棋子以及棋盘以及一个放置死掉棋子的篓子。这里每一个符号都只有一个。虽然其中卒有10个-每一方各5个，但我们认为这10个卒是互不相同的，同时这些卒的走法是相同的。 初始公理：棋子最初放置在棋盘上的位置。注：通常的比赛中棋子一开始处于固定的位置。但我们也可以研究残局，这时棋子的位置就依赖于残局的选取了，并且一部分棋子在篓子中。 语法规则：棋子在棋盘以及篓子中，棋盘上每一个位置只能放置最多一个棋子，但可以不放。 变形规则：象棋的棋规。比如，兵卒一次只能移动一步，没过河以前不能横着移动；马只能跳“日”字；象只能飞“田”字；以及红黑棋子轮流移动；吃子法则-将某些子放入篓子中；棋局终止法则，等等。 因而象棋是一个形式体系。这个体系中有很多有意义但不是定理的棋子放置方式。比如一方的象在另一方的半个棋盘内。
|
||
|
gauge 发表文章数: 596
|
算术体系的形式化
算术体系的形式化。我们通常使用的算术体系是在一种朴素的水平上进行的。直到Peano给出算术的公理体系，这种状况才发生了变化。Peano给出5条公理来描述算术，从而使得算术建立在公理体系之上。我们仅仅叙述Peano的第4个公理：对任意自然数m,n, 若m’=n’,则m=n.此处，m’表示m的后继，亦即m+1. 但这还不是形式化体系。形式化体系将所有的对象都当作一个符号或者符号串。对算术体系，其中的符号为： 逻辑符号: $\forall$表示任意，$\neg$表示逻辑非，$-->$表示逻辑蕴涵。 括号: (表示左括号,)表示右括号。括号充分反映了形式化的特点，亦即所有的对象包括括号都要被形式化。 逗号:, 等号，$P_1^2$表示等号= 变元符号，$x_1,x_2,…$一共可数无限多个变元。 常元符号，$a_1$表示数0. 函数符号，$f_1^1$表示后继运算，亦即$f_1^1(x_1)=x_1+1$. $f_1^2$表示求和，为二元函数，即$f_1^2(x_1,x_2)=x_1+x_2$. $f_2^2$表示乘积，即$f_2^2(x_1,x_2)=x_1x_2$. 注意，对形式体系而言，上面的说法是不严谨的。比如\forall并具有什么特别的含义，仅仅是一个符号而已。我们给出的解释语言是为了理解起来方便一些。 这样，Peano的公理4就可以用形式化的语言叙述为， (\forall x_1)(\forall x_2)((f_1(x_1)=f_1(x_2))-->(x_1=x_2)) 同样Peano的其他公理以及加法、乘法公理也都可以明确表述出来。 当然还需要给出语法规则和变形规则。我们略掉这些繁琐的细节。 现在我们有两个体系，其一是用Peano公理表述，其二是用形式化的语言表述的算术体系。前者可以看作后者的一个模型、一个解释。通常的自然数1,2,3在形式化体系中表示为 f_1^1(a_1),f_1^1(f_1^1(a_1)),f_1^1(f_1^1(f_1^1(a_1))) 这种书写方式比较累赘，在不引起混淆时，人们依然采用通常的记号1,2,3来表示这些对象。同样的记号也用在函数$f_1,f_2,f_3$上。 这样的一个形式化体系称为一阶算术，或者基本算术。其中只有求和以及相乘两种运算。在这样的算术体系中，素数是没有意义的概念。这个体系中全部的记号、定义、规则都已经给出了，不能再加入新的对象。加入新的定义，比如定义素数，得到的将是另一个形式体系。当然新的形式体系可以看作基本算术体系的一个扩张。
|
||
|
星空浩淼 发表文章数: 799
|
再接再厉。中途进来支持一下！
One may view the world with the p-eye and one may view it with the q-eye but if one opens both eyes simultaneously then one gets crazy
|
||
|
gauge 发表文章数: 596
|
Godel不完备性定理之一
一共有两个不完备性定理。 Godel的第一个不完备定理：在包含基本算术且一致的形式体系中，存在一个命题P, 使得，P以及notP都不是该形式体系中的定理。或者可以等价地说该形式体系不是完备的。 为了准确的理解这个定理，我们作一些解释。 一个形式体系包含基本算术，是指，可以将基本算术体系嵌入到这个形式体系中。 命题P是指符合语法规则的一个陈述。 notP是指命题P的否定，亦即“命题P是错误的”。 形式体系中的定理，是指可由形式体系中的公理，经过有限多次变形得到的命题。 形式体系中的命题如果是一个定理，则称为一个可以证明的命题。因而在一个形式体系总，证明一词的含义是指，可由初始公理通过有限多次使用变形规则得到。和我们通常理解的证明并不相同。 一致，是指不存在命题P,使得P以及notP都是该形式体系中的定理。 由这些解释，Godel不完备定理也常常被叙述为 Godel第一不完备定理的第二个叙述方式：在包含基本算术且一致的形式体系中，存在一个命题P, 使得，P以及notP都不能在形式体系内部得到证明。 我们进一步作一些解释。无论如何，一个命题或者正确，或者错误。正确的命题，称为真的命题。而错误的命题则称为假的或者非真的命题。考虑Godel不完备定理中的命题P. 如果P是真命题，则我们得到该形式体系中的一个真的但不可证明的命题，这个命题就是P. 如果P是假命题，则notP是真命题，因而我们仍然得到该形式体系中的一个真的但不可证明的命题，这个命题就是notP. 因而我们得到Godel不完备定理的另一个叙述方式 Godel第一不完备定理的第三个叙述方式：在包含基本算术且一致的形式体系中，存在真的但不可证明的命题。 很多人对于Godel不完备定理的讨论都以此为出发点，但却很少去深究这个看起来简单明了的叙述方式中每一个词语的准确含义。这是导致Godel不完备定理被夸大到不恰当的程度的一个主要原因。另一方面，Godel定理中的用语，特别是“真”、“证明”这两个词的意义与我们通常看到的并不相同，这也是造成混乱的一个重大原因。究其缘由，应该与Hilbert有关。因为这些基本术语来源于Hilbert形式化计划。而Hilbert本人深信，其形式化计划最终可以给出数学严格性的终极证明。事实上，如果Hilbert形式化计划不是被否定，而是得到了肯定的话，我想将没有任何人可以任何理由反对数学具有彻底的完全的一致性和完备性。既然是Hilbert提出了这个计划，以及这个计划的基础知识和准备工作，也是Hilbert为之命名，同时Hilbert又深信这个计划最终可以得到数学严格性的终极证明，因而原本应该称作“可构造”的，却被Hilbert命名为“可证明”。关于Godel定理或者说形式体系中“证明”这个词语的来源，在此要特别说明，纯属个人揣测，至少迄今我没有见到任何文献提及此事。 将Godel不完备性定理中的“证明”一词换作不容易引起混淆的“构造”，可以给出 Godel第一不完备定理的第四个叙述方式：在包含基本算术且一致的形式体系中，存在真的但不可构造的命题。 如果我们见到的Godel定理是这样叙述的，肯定会减少很多不必要的混乱。
|
||
|
dfj 发表文章数: 186
|
>Godel的第一个不完备定理：在包含基本算术且一致的形式体系中，存在一个命题P, 使得，P
>以及notP都不是该形式体系中的定理。或者可以等价地说该形式体系不是完备的。 >... >一致，是指不存在命题P,使得P以及notP都是该形式体系中的定理。 问一下： 这里有没有写错？ >Godel第一不完备定理的第四个叙述方式：在包含基本算术且一致的形式体系中，存在真的但 >不可构造的命题。” 可否简单的理解为，这个形式体系中存在一些真的命题，其具体内容（或具体表述）我们无法得知？ 就好比，我们知道任何多项式方程在复数域中都有根，但是对于超过四次的一般方程没办法通过有限次的加减乘除和根式运算得到其根的表达形式——或者粗略的说成“有解但是解不出”。 可以这样理解吗？
|
||
|
gauge 发表文章数: 596
|
不好意思，又来批判Penrose,记得以前有人曾专门发起一个批判Penrose的粒子物理学的运动。:)
对于Godel不完备定理，有大量荒谬的推论。其中之一是以此来证明人工智能是不可能的，或者机器不可能具有思考能力。比如Penrose在其《The Emperor's New Mind》中的论证。这些论证通常如下进行。 机器是Turning机。 由不完备定理，存在真的、不可证明的命题。因为形式体系与Turing机本质上是等价的。因而这些命题不能由机器证明。 但是人可以证明这些命题。所以人的思维不能被机器或者一个公理体系充分表达。因而人不是会计算的机器，所有的机器也不能拥有和人一样的智力。 上述论证中的每一个都可以承认，除了最后的结论。 Penrose的书出版于1989年。但是Turning早在1947年就已经指出上述论证的错误。事实上，Godel不完备定理需要的条件：体系的内部一致性。然而人类是极其容易犯错误的。人类的直觉极易犯错。比如那些最牛的逻辑学家：Frege,Curry,Church,Rosser先后提出了庞大的公理体系，但是后来被证明是错误的。如果允许电脑犯错，那么Godel定理的条件不再成立，其结论也就没有意义了。 附，顺便说几句Penrose的《皇帝新脑》一书。 Penrose的《皇帝新脑》一书，出版于1989年，中文版出版于1993年。中文版的前言称该书的出版是国际书界的一件大事，剑桥大学在几年后曾专门为此书召开了一次学术会议。本书的内容从人工智能、逻辑到物理学、宇宙学以及神经科学，当然还有哲学。Penrose的目标是讨论哲学、科学上最重大的问题之一，人类的意识问题。Martin.Gardner为此书写的前言中称Penrose的书，是到该书出版为止，对于强人工智能做出的最有力的攻击。Penrose极力反对强人工智能。强人工智能认为机器可以具有人的意识和智能。弱人工智能认为机器可以表现得像一个人，但是不具有人的意识和智能。还有一种更强的观点，声称人就是一台机器。Penrose对于强人工智能的攻击从几个方面进行。其一，基于Searle中文屋子这个思想试验。其二，基于Godel不完备性定理。Penrose又一次展示了大无畏的革命精神。对于Penrose的论证，我只有一个评语：惨不忍睹。有兴趣的读者可以自己去翻阅该书的前几章，并以挑出其中的逻辑漏洞来训练自己的推理能力。当然效果不一定好，因为那些漏洞比较简单。难以想象Penrose为什么老犯这些低级错误。 而那些数理逻辑专家则见猎心喜，有不少针对Penrose的反驳意见。首先，Penrose是大人物，对之搞批斗很有意义；其次， Penrose犯了低级错误，批判起来容易。这和物理学家批判Penrose的粒子物理，何其相似。简直都有点搞笑了。 Penrose引用的Searle中文屋子的思想试验被Martin.Davies在《逻辑的引擎》一书的最后一章批得体无完肤。而他基于Godel不完备定理的论证又被Turning早在40年前就批判了。真的很惨。 顺便说一句，我认为Penrose的论证不严谨，但是，这并不代表我同意强人工智能的观点。
|
||
|
gauge 发表文章数: 596
|
通常很多人认为Godel定理中的那个命题是很抽象而且不能具体写出来的。这是严重的错误。在基本算术体系中，可以明确地写出来一个真的但不可证明的命题。比如Goodstein定理。可参考
http://www.answers.com/topic/goodstein-s-theorem 我们在所有的帖子中都在使用“构造”这样的说法，并一直在解释这是形式体系中“证明”一词的真正含义。构造，也可以叫做，算法，二者表达的是同一个含义，都表示在有限多个步骤之后得到结论。
|
||
|
gauge 发表文章数: 596
|
荒谬的推论1
Hawking等人认为，Godel不完备性定理表明终极理论是不可能的。Hawking的错误比起Penrose来更加不着边际，看起来就像犯了不完备恐惧症，或者可以叫做不完备焦虑症。物理学甚至数学都不是形式体系，Godel定理的条件并不满足。Hawking的观点可以参考其本人在2002年的Dirac讲座上的演讲 Hawking, "Gödel and the end of physics" 然而Hawking不是孤立的，Freeman Dyson持有类似观点。Freeman Dyson在纽约书评上为Brian Greene的The Fabric of the Cosmos写道： Gödel’s theorem implies that pure mathematics is inexhaustible. No matter how many problems we solve, there will always be other problems that cannot be solved within the existing rules. … because of Gödel's theorem, physics is inexhaustible too. The laws of physics are a finite set of rules, and include the rules for doing mathematics, so that Gödel's theorem applies to them. [NYRB,May 13, 2004]. 按照Dyson的论证，很容易推论出TOE是不存在的。 又比如Scientific America的一个senior, John Horgan在其所著The End of Science一书中写道： Gödel's theorem denies us the possibility of constructing a complete,consistent description of physical reality. 以及Stanley L. Jaki, A Late Awakening to Gödel in Physics. 我反对这些人的论证，并不代表赞同有一个TOE. 仅仅是想表明，Godel定理不蕴含这些夸张的推论。
|
||
|
gauge 发表文章数: 596
|
荒谬的推论2
有人认为，Godel定理给出了人类知识的绝对上限。对此，可以对比Heisenberg不确定原理。Heisenberg不确定原理给出了人类对于世界的认识的一个绝对的界限吗？没有。因为那就是世界的本来面貌。客观世界的不确定性与我们测不测没有任何关系。
|
||
|
gauge 发表文章数: 596
|
荒谬的推论3
有人认为，Godel定理告诉我们有一些真的数学定理是永远无法证明的。甚至有人猜测Goldbach猜想或者Riemann假设就是这样的命题。想一想在Wiles之前有不少人把Fermat问题也作为其中的一个命题就知道这纯属无稽之谈了。反面的例子，比如Gooodstein定理，这是一个被严格证明了的数学定理，但在形式系统中不可“证明”。 由于“存在不可证明的数学定理”，某些后现代主义据此怀疑客观实在性。所以当我们在沾沾自得的用Godel不完备定理得到某些炫目的结论时，应该想到自己仅仅是全世界各种各样的具有不完备情结的人之一。 基督教会则据此为自己辩护：theologians can be comforted in their failure to systematize revealed truth because mathematicians cannot grasp all mathematical truths in their systems either. 看来教会对数学家的评价很高嘛。不完备定理还被用来证明上帝的存在性，因为只有他能决定哪些是真理。然而我们也可以反过来使用不完备定理，并以此证明上帝不是全能的。
|
||
|
gauge 发表文章数: 596
|
荒谬的推论4
Godel本人的错误。在1960的Gibbs讲座上Gödel本人宣称：“either mind infinitely surpasses any finite machine or there are absolutely unsolvable number theoretic problems.” 可以看出Godel使用了隐含假设：精神不能杯机器实现，然而这是无法证明的，至少Godel没有给出一个可以和他的不完备定理的证明同样坚实的证明。
|
||
|
gauge 发表文章数: 596
|
这个系列基本上到此为止。一个简单的后记。写这个系列的一个原因是Godel定理本身是很有趣的，但遭到了广泛的误解和夸张。另外，写这个系列是作为曾经计划写的一些其他内容，比如热力学第二定律中的小概率这个部分以及概率论中的各种概率分布函数，并没有完成，也没有打算继续写这些相关内容。因而将Godel定理的讨论作为一个补偿。Godel定理与其他领域也有关系，比如计算机理论特别是Turning机的停止问题，以及信息论中也有相应的表现形式。有兴趣的读者可以自己作进一步的了解，当然也可以发贴上来讨论。
|
||
|
gauge 发表文章数: 596
|
主要参考资料。
http://www.cs.auckland.ac.nz/CDMTCS/chaitin/georgia.html http://www.cscs.umich.edu/~crshalizi/notebooks/godels-theorem.html http://www.ncsu.edu/felder-public/kenny/papers/godel.html Penrose, The emperor’s new brain, 1989. 马丁·戴维斯（美）,逻辑的引擎—第一推动丛书·第四辑.张卜天译. http://www.ltn.lv/~podnieks/gt1a.html#BM1_4 http://www.cscs.umich.edu/~crshalizi/notebooks/godels-theorem.html http://www.answers.com/topic/goodstein-s-theorem Stanley L. Jaki, A Late Awakening to Gödel in Physics Stephen Hawking, "Gödel and the end of physics" http://www.damtp.cam.ac.uk/strings02/dirac/hawking/ 刘新文,哥德尔的遗产及哥德尔百年纪念, http://www.logic-china.info/events/symposiums/2006-godel.htm
|
||
|
XXFF  发表文章数: 226
|
很高兴有专业人员谈Godel！
有时间好好读，顺便问一下： ：：在基本算术体系中，可以明确地写出来一个真的但不可证明的命题。比如Goodstein定理 ================================================================================= 欧氏空间里也有例子吗？ XXFF
|
||
|
星空浩淼 发表文章数: 799
|
今天终于把guage兄的这个系列系统地看了一遍，写得不错。guage兄的作品有一个特点：在看似不经意之中，常常暗藏玄机。尽管如此，guage兄的有些看法我不太赞同。
也许其他有些没有系统了解过Godel不完备定理的人，很容易如guage兄所说凭字面意思误解它，但就我而言，我看完这个帖子之后，我可以说，我本人对Godel不完备定理的认识与理解，与本文所介绍的并无不同，只是对guage兄的一些个人感想有些不赞同。 例如，guage兄一再强调，这里涉及到的“证明”这个术语，跟我们通常所说的“证明”含义不同。但是在我看来，这没有不同。逻辑学中的“证明”，是把通常的证明过程抽象化、形式化，提炼出本质，其实跟数学中证明某一道具体的数学题，含义没有分别。我们可以通过同构映射的方式，把一道数学题的证明过程形式化（或“翻译”）为一道逻辑推理过程（即利用公理、符号、变形规则等进行的符号串演算），这个过程就是逻辑学上的所谓证明。 至于什么样的“证明”才能算作是一个“证明”，那又是另外一回事。一种观点是，证明某个东西存在，而不必管这个东西到底是什么，这也可以看作是一个证明；另一种看法与之不同，认为光证明其存在，这个证明过程还没有完结，必须还得把这个东西到底是什么给找出来，证明才算结束。后者即是guage兄详细介绍过的构造主义观点。 我有点迷惑的是，Hilbert应该知道这样一个事实：可以证明素数有无穷多个，但是到底素数集合是什么，不存在一种算法来给出它。换句话说，给出一个数，不存在一个算法来判断它是不是素数。既然如此，那他为什么还试图给出所谓“Hilbert计划”：要寻求一些算法，这些算法可以构造出（所有）真的算术命题？ One may view the world with the p-eye and one may view it with the q-eye but if one opens both eyes simultaneously then one gets crazy
|
||
|
gauge 发表文章数: 596
|
差不多过了2个月了。回头再谈谈Godel定理与Heisenberg uncertaity.
我们在前面的一个帖子中谈到二者之间的一个类比。注意到，我们给出的是一个类比，而不是说这两个理论之间本身有什么关系。我们的类比是说，Godel定理被很多人用来证明人类对于世界的认识不可能是完备的，同样Heisenberg uncertainty也被某些人用来作出同样的推论，前者如Hawking,后者比如Einstein.对于Godel定理的Hawking误解，我们已经讨论过了。关于Heisenberg原理，Einstein认为这表明我们对于世界的认识是不完备的，是因为Einstein认为世界的本质不是概率性质的。注意，我们没有说是因为Einstein误解了Heisenberg.我的意思是，如果世界本来就是概率性质的，那么Heisenberg原理就是对于世界的描述，并不表示我们对于世界的认识的一个极限。两种论点还是有很大区别的。与其说Godel定理或者Heisenberg定理表明人类的认识有一个绝对的极限，还不说有计算复杂性导致的那些几乎不可计算的问题才表明了人类认识的极限。
|
||
|
星空浩淼 发表文章数: 799
|
关于对Heisenberg uncertainty和互补性原理的理解，有人用量子力学中的相对性来理解，即如同狭义相对论中的坐标变换和观察者等概念，不同观察者处于不同参照系上，看到的情形自然有所不同。这里傅立叶变换类比于相对论中的坐标变换，只是前者前者是动量空间和坐标空间之间的变换，后者是不同时空坐标系之间的变换。
Note that since the transition from real quantities to self-adjoint operators is with respect to a particular frame, the fact that a particular observable is represented by some specific operator also must be taken relative to a frame. One may view the world with the p-eye and one may view it with the q-eye but if one opens both eyes simultaneously then one gets crazy
|
||
|
gauge 发表文章数: 596
|
形式体系的另外几个例子。
1，搭积木 2，建房子 3，DNA序列 4，半群、群 可以说大部分人都不能很好的理解形式体系的含义，再举这几个例子。搭积木、建房子的例子是我自己想到的，不一定很恰当。
|
||
|
ni_o  发表文章数: 33
|
有一段时间没来学习了，看到这么好的贴，真是令人心潮澎湃！感谢。
命运取决于选择。
|
Re: Godel定理之拙见 
Re: Godel定理之拙见 
Re: Godel定理之拙见