给真的想了解一点哥德尔工作的人

Tension 评论 哥德尔、艾舍尔、巴赫 3 2009-12-16 12:54:43
Apophenia
Apophenia (不器) 2009-12-30 00:42:19

谢谢你的评论
觉得很有帮助

one
one 2010-03-12 11:44:45

三、作者的用的类比其实并不精妙,侯世达将“哥德尔句”喻为“怪圈”,已被指出乃是一种错误的描述。

作者是把哥德尔自己给出的证明方式比喻为怪圈。作者认为配数法是个怪圈(以下均为作者观点,或者说在下眼中的作者观点)。形式化系统的数论命题和用配数法表示的数论命题是不同层次的数学命题,就像3位空间模型中怪圈的两个面。用配数法在《数学原理》的形式化系统中构造哥德尔句子,是以数学分析元数学。这种做法和把不包含自身的“一般集合”的集合放进“一般集合”中去讨论是一样的。从一个层次到另一个更高的层次,再从它返回到低层次,形当于在怪圈的两个相背的面上走一圈回到起点。作者在螃蟹的唱机里面描述了这个怪圈的形成。在下认为乌龟和螃蟹的唱机大战是作者创意的闪现之一。

Tension
Tension 2010-03-12 20:20:00

回复楼上

前几天同学之间谈起一个问题:我们究竟应怎样定义“相似”?当我们说“一个东西和另一个东西相似”的时候究竟是什么意思?或者“相似”这个概念根本不能再被还原?
大家随便侃了一阵,也没有再深入地追下去。
之所以说起这个,是想说:两个东西,你说它们像,我说他们不像,本来就有点扯不清。况且我对你的一些表述很难理解,也即是:

“形式化系统的数论命题”——什么意思?在哥德尔讨论到的形式化系统中,每条定理都能解释为一条数论命题,形式化系统本身都是无意义的符号组合与变换,中间没有什么数论命题
“用配数法表示的数论命题”——借助配数法,有些元数学命题可以用一个数论命题表达,没有什么“用配数法表示的命题”
“不同层次的数学命题”——算术中的数学命题没什么不同层次,1+1=2是一个算术命题,假设它在一个所谓的“层次”上,还有与之不在同一层次上的算术命题?如有,请举例。
“就像3位空间模型中怪圈的两个面”——怪圈不是只有一个面吗?
“用配数法在《数学原理》的形式化系统中构造哥德尔句子”——配数法的作用是让系统能表达系统本身的元数学命题,哥德尔句子的构造还得其他的工作。
“这种做法和把不包含自身的“一般集合”的集合放进“一般集合”中去讨论是一样的”——暂且不问“如何一样”这种扯不清的问题,只想问这种“把不包含自身的“一般集合”的集合放进“一般集合”中去”的讨论在哪里有?严格地公理集合论一定不会有这种讨论,哥德尔的证明可是很严格的,它会和这种(假如确实存在的)对集合的不严格的处理一样?
“从一个层次到另一个更高的层次,再从它返回到低层次”——或者可以这么说(?):“从一个低层次的东西到另一个更高的层次的东西,再从它返回到低层次的某个东西”。注意,即使如此,第一个“东西”和第三个“东西”可以不是一个东西,一定就回到起点了吗?考察哥德尔的证明过程,其中不包含循环,对此可参考前文所列文献。




one
one 2010-03-19 10:54:26

“形式化系统的数论命题”——什么意思?在哥德尔讨论到的形式化系统中,每条定理都能解释为一条数论命题,形式化系统本身都是无意义的符号组合与变换,中间没有什么数论命题

我们讨论的是Godel给出的不完全性第一定理的证明,Godel用来证明第一定理的形式系统是罗素和怀特海的《数学原理》,此书包含对皮亚诺公设的推导,因此包含许多数论命题。

“用配数法表示的数论命题”——借助配数法,有些元数学命题可以用一个数论命题表达,没有什么“用配数法表示的命题”
关于这个,侯世达在书中已经说得非常清楚。我引用原文——
“哥德尔洞察到,只要数能够用来代表陈述,那么一个数论陈述就可以是关于一个数论陈述的了 〔 甚至可以是关于它本身的)。换句话说,编码的概念是哥德尔构造的核心部分。在哥德尔编码 ― 通常称做“哥德尔配数” ― 中,数是用来代表符号和符号序列的。这样,每个数论陈述作为一个特定的符号序列,获得了一个可资查询的哥德尔数,这有点象电话号码或行车执照。这种编码方式可以使人们从两个不同的层次去理解数论陈述:把它理解成数论陈述,同时也可以理解成关于数论陈述的陈述。”
——这段文字将配数法的形式意义说明得非常清晰。我所说的“用配数法表示的数论命题”是“关于数论陈述的陈述”,本身也是“数论陈述”。

one
one 2010-03-19 11:12:33

“不同层次的数学命题”——算术中的数学命题没什么不同层次,1+1=2是一个算术命题,假设它在一个所谓的“层次”上,还有与之不在同一层次上的算术命题?如有,请举例。
这条同上一条。但是类似的,如果非要将0和1表示的机器语言与由类的组块构成的C#看作是同一层次上的计算机语言,那么也只能断言草履虫和食蚁兽是同一层次的。

“就像3位空间模型中怪圈的两个面”——怪圈不是只有一个面吗?
指的是直观上的正面与背面。

“用配数法在《数学原理》的形式化系统中构造哥德尔句子”——配数法的作用是让系统能表达系统本身的元数学命题,哥德尔句子的构造还得其他的工作。
Godel的论证中,G是用配数法构造的。

“这种做法和把不包含自身的“一般集合”的集合放进“一般集合”中去讨论是一样的”——暂且不问“如何一样”这种扯不清的问题,只想问这种“把不包含自身的“一般集合”的集合放进“一般集合”中去”的讨论在哪里有?严格地公理集合论一定不会有这种讨论,哥德尔的证明可是很严格的,它会和这种(假如确实存在的)对集合的不严格的处理一样?
“一般集合......”是罗素集合悖论的不严格的说法(事实上我的任何说法从数学角度看都必定是不严格的,因为语言本身就是“数学不严格的”);Godel使用G的方式与罗素使用“一个包含所有一般集合的集合”的方式是“类似”的。

one
one 2010-03-19 11:15:06

关于最后的“层次”,我不能说什么,那已经超出了我的“层次”所能讨论的范围。关于“相似”这样的概念也“相似”。那是哲学家的事情。

Tension
Tension 2010-03-19 21:22:03

拜读了回应,我收获很多,别的不想多说了,“但是类似的,如果非要将0和1表示的机器语言与由类的组块构成的C#看作是同一层次上的计算机语言。。。”你这个“类似”后面的内容我不懂,所以也不知道类似在哪里。
我只想说,系统中的算术命题(暂且就按你的习惯这么说吧),和通过配数法的帮助构造出的表达元数学命题的算术命题,都是初等算术命题,它们确实是一个层次的东西。如果不是的话,构造出的表达元数学命题的算术命题也就不能再回到形式系统去找一个“形式替身”(事实上,有些元数学命题把它们算术化以后,就不是一个初等算术命题了,这样的算术命题是不能回到数学原理的系统中找“形式替身”的,或者说,这个系统是无法表达这些算术命题的,幸运的只是证明中要用到的表达元数学命题的算术命题都是初等的)
什么一个低层次到高层次又到低层次,本来是很简单能说清楚的东西,非要弄得这么玄妙,而且根本还会产生误导的作用。你最后的那条回复似乎表明了对“哲学”的不屑,但为什么对上述那种充满神奇的玄思的语句又如此欣赏呢?

Tension
Tension 2010-03-19 21:26:49

顺便说一句,难得有个人可以就这些“呆”问题争论一下,我感觉很愉快

seesee
seesee (简单做人,简单思考。) 2010-12-06 11:21:38

哥德尔证明

EPA
EPA 2012-02-06 18:18:42

@空想家 你的意思我好像明白一些,你的意思是哥德尔分析用的是一般的数学技巧来分析元数学。但是元数学构造了一切数学定理(包括哥德尔用的数学技巧),因此这种技巧必然是有争议的。

[已注销]
[已注销] 2012-03-06 13:20:13

哥德尔第一其实不重要,也不复杂,只罗素悖论语句的可列集(自然数)版。只是出现时机很对,当时人类对逻辑学困惑。

松儿
松儿 (是只猫) 2012-03-31 10:26:33

简而言之,哥德尔定理的核心是层次与指代的混淆。就像我们看双语字典,一个词可以用一句话来解释,但是那一句话里面的词呢,是不是又可以用同一本字典里面的另外的语句来解释。最终的结果,便是陷入了哥德尔的怪圈。
而这个定理最头疼的地方就是,它非“它” 了。其实就连描述哥德尔定理的语言也会陷入哥德尔定理之中。
哥德尔定理的哲学意义则是在讨论逻辑的界限问题。这里可以和现代的量子力学相类比,量子力学的哲学意义则是在讨论逻辑的最小单元。
逻辑是属于个[-无穷,+无穷]中的哪一个段呢?就此看来,哥德尔定理和量子力学理论的效用和成就是等价的。

Tension
Tension 2014-02-20 20:17:00

时间过了快三年,回头看,自己写的东西有些都看不太明白了。

斯宾诺莎的镜片
斯宾诺莎的镜片 2014-04-30 13:23:40

楼主读完smith的书了吗?另外说一个极微小的纰漏吧,人大出的布莱克韦尔《哲学逻辑》里,斯穆里安的那篇文章应该是《哥德尔的不完全性定理》,斯穆里安自己有本书也叫这个名。

引心
引心 (一叶且或扬意,虫声有足引心) 2017-02-28 10:52:34

吓尿!

李怡
李怡 (在此记录自己的阅读) 2017-08-02 17:48:43

2L和楼主你们在有QQ的时代应该互相加为好友

Shoreline
Shoreline (hi~) 2017-08-18 00:20:47

本人没有任何高等数学或者计算机语言的基础。但这本书我也看了大半年,跟着作者的思觉得自己大概理解了不完全性定理的含义和证明方法,我试着在2000字内说清楚它
我将十分感激如果有人愿意花时间看完,如果看完真的能了解哥德尔定理我就更喜出望外了。。。
----------------------------------------------------
哥德尔不完全性定理:“数论的所有一致的公理化形式系统都包含不可判定的命题”

想知道其意思先了解几个概念(简化过的狭义解释)
* 数论:描述自然数(0,1,2...)性质的陈述。。如(3是素数,1792是两个自然数的平方)
* 形式系统:由确定的推理规则和特定的符号组成的系统,用来反映自然数的性质(这本书提到的都是数论的形式系统,如等下证明会用到的TNT系统就是由+,=,~,?等符号(想想高中学过的全称量词与存在量词)还有表示所有自然数的符号组成的)
* 定理:形式系统中根据规则推导出来的公式。每一条定理都说了一句关于数论陈述的真话(表述了正确的自然数性质 ,也叫真理,如“1792是两个自然数的平方”就是一条TNT系统的定理,因为这句话是正确的,但是在TNT系统中 这句话是用TNT系统的符号写出来的)
* 形式系统的完全性:形式系统中的每一条定理表述了一条真的数论陈述,那如果全世界所有真的数论陈述都可以被一个系统中的定理表述出来,这个系统就是完全的
* 形式系统的不完全性:不完全性就是说,有真理不能被定理表述出来

那么哥德尔不完全性定理:“数论的所有一致的公理化形式系统都包含不可判定的命题“就可理解为:所有数论的形式系统中都至少有一句话,你没办法判定它是不是定理(不能说它不是定理,也不能它说是)
其实这个句话就是在说:“我不是一条定理”(我们把它取名为"G"),你没有办法判定是因为

1.如果G是定理 则说明它说了一句真话 → 矛盾

2,如果G不是定理 那他就的确说了一句真话 → 那他就是不能被系统定理表示的真话——系统不完全性的原因

所以只要找出这句话就可以证明这个定理,找出这句话的意思是用形式系统的符号(这里用的是TNT系统)把G写出来


证明:
数学符号能表述“5是素数”这样的数论陈述,但怎么表述“我不是一条定理”这种意思?这好像是文字才能办得到的事,要怎么用数学的陈述来谈论数学陈述自己呢? 哥德尔发现了用数学公式谈论数学公式自己的方法!他用数学符号表述出了 “我不是一条定理”

1,表述“不是一条定理”: 表示“是定理”要用到“证明对”的概念:
如果n是一条定理 ,那么就有一个陈述(公式)可以和n形成一对证明对
这句话用形式系统的符号表示就可以写成公式┋存在一个a 让{a,n}形成证明对┋
所以某陈述不是一条定理就可以写成公式┋不存在一个a 让{a, 某陈述}形成证明对┋
( 注意!:1.此处为方便理解,把形式系统的数论陈述用中文表示出来,所有用TNT系统的符号表述的语言都会用前后加上加上符号 “┋”,原本的陈述都是 ~?a .... } 这样的符号组成的公式
2.“证明对”本身具有一种原始递归的数学性质可以保证说出来的都是真话,比如像┋存在一个a 让{a,1+1=3}形成证明对┋这样的公式是不合法的,你可以理解为这样的假公式写不出来!)

2,表述“我” :要用到"汇摁"的概念,"汇摁" 就是把自己带入它自己的意思
公式:┋汇摁{x,n}┋意思是:含有自变量的公式x把自己带入自己的自变量后就是n
(注意!:x把自己带入自己不会造成x里面有x里面有x ...这样的无限循环,因为公式X并不是直接带入自身,而是用自己的哥德尔编码的数字形态带入自己的,这个待会解释)

接下来我们先写出一个陈述(公式):┋不存在一个a让{a, n}形成证明对 并 汇摁{x,n}┋
意思是 :当n是公式x带入它自己的自变量时,n就不是定理
这个公式的名字叫做"G的服号串" 简称 “G服”
最后一步:把G服带入X!我们就得到了传说中的"G" :┋不存在一个a 让{a, n}形成证明对 并 汇摁{G服,n}┋
它的意思就是: 当n是公式G服带入它自己的自变量时,n就不是定理,而此时n就是G服带入他自己的自变量!所以此时n就不是定理!
所以这条陈述G:┋不存在一个a 让{a, n}形成证明对 并 汇摁{G服 ,n} ┋就是我们要找的说”我不是定理“的那句话 ,哥德尔不完全性定理证明完毕,G的存在就是形式系统不完全的原因!
(把G拆开看更明白:┋不存在一个a 让{a, n}形成证明对┋说的是 :n 不是一条定理
┋汇摁{G服,n}┋说的是 :n 就是这个句子自己,是对n的解释,即我)

最后详细讲下要如何表示┋汇摁{G服 ,n}┋中的G服:
G服就是公式┋不存在一个a 让{a, n}形成证明对 并 汇摁{x,n}┋
现在要用G服自己带入自己的x,可这要怎么带呢?如果直接带进去就成了:
┋不存在... 汇摁{不存在... 汇摁{不存在...汇摁{...,n} ,n} ,n}...}┋
这会是个无限循环的怪圈,没办法写出来
哥德尔的办法是用G服的哥德尔编码的TNT数字形式带入:
第一步: G服 → G服的哥德尔编码 : 哥德尔编码就是把公式符号用特定的数字指代,比如 存在 是110 ,a 是 666, x 是 303... ,所有的TNT符号都有自己的编码数字,那最后G服就能被写成 110 xxx xxx....xxx 这样一连串的数字代码
第二步:G服的哥德尔编码 → G服的哥德尔编码的TNT数字形式 :因为G服全是TNT符号,只能用TNT符号带入,现在把所那一串xxx都变成TNT符号,把数字翻译成TNT的符号,现在110的含义就不是存在了,而就是数字110,用TNT的符号表示110(TNT系统用S+0表示自然数是,1是S0,2是SS0,110就是0前面110个S)翻译完后G服就被写成 SSS...0 SS...0 . . . . . SS...0 ,这才是要带入G服本身的东西
所以汇摁{x,n}的意思实际上是:含有自变量的公式x把自己哥德尔编码的TNT数字形式带入自己的自变量后就是n。这样的变形可以近似理解为把 滚 →gun → 哥屋恩。还是中文形式,但换一种方式表示。
------------------------END----------------------------
在以上有限的字数里能讲明白哥德尔利用配数法构造出自指的数论句子从而证明定理的过程,但没办法说明的是:
1.为什么“证明对”可以把“XXX不是定理”这种话翻译成数学公式:这涉及到形式系统和算数的性质等价还有关于原始递归中有穷循环和无穷循环的问题
2.为什么“汇摁”可以表示“把自己带入自己的自变量”的意思。它长什么样,这也涉及到原始递归中有穷循环和无穷循环的问题还有康托尔的对角线论证

但是对于理解本书的核心概念,我认为对证明过程了解到这个程度就已经足够
奉上我对本书完整的解读:
https://book.douban.com/review/8743596/(真心憋了8个月!!)

艾芙奈森特
艾芙奈森特 (Go with the flow.) 2017-08-28 08:00:46

很多人觉得看不懂就是好,大家都觉得好我就要去看。对我而言,一本书不对胃口也没有实际用处就不看。更何况就像你说的中译本的翻译读起来很奇怪,书中的表达和描述常显得随意和缺乏连贯性。太多人把这本书捧上天不免有皇帝的新衣之嫌,而你可能就是那个唯一敢说真话的孩子。

斯宾诺莎的镜片
斯宾诺莎的镜片 2017-08-28 22:52:54
很多人觉得看不懂就是好,大家都觉得好我就要去看。对我而言,一本书不对胃口也没有实际用处... 很多人觉得看不懂就是好,大家都觉得好我就要去看。对我而言,一本书不对胃口也没有实际用处就不看。更何况就像你说的中译本的翻译读起来很奇怪,书中的表达和描述常显得随意和缺乏连贯性。太多人把这本书捧上天不免有皇帝的新衣之嫌,而你可能就是那个唯一敢说真话的孩子。 ... 艾芙奈森特

中译本好像没有随意的问题,有问题的主要是霍夫斯塔德自己写作时的类比等。
看这本书前,最好有初步的逻辑基础,就如作者所言。至少看了内格尔的那本哥德尔证明。这本书写的还是不错的。

Tension
Tension 2017-08-30 06:39:25
楼主读完smith的书了吗?另外说一个极微小的纰漏吧,人大出的布莱克韦尔《哲学逻辑》里,斯穆... 楼主读完smith的书了吗?另外说一个极微小的纰漏吧,人大出的布莱克韦尔《哲学逻辑》里,斯穆里安的那篇文章应该是《哥德尔的不完全性定理》,斯穆里安自己有本书也叫这个名。 ... 斯宾诺莎的镜片

三年又三年了。你说的对,smullyan的书名我写错了。smith的书后来没看了。尽管自己现在做的东西离哥德尔定理所属的领域已经很远,但还是对它的相关问题保持着一定程度的兴趣。我猜包括我在内很多学逻辑的人,第一次真正感受到逻辑的魅力,就是在初次接触哥德尔定理的时候。有一个愿望,就是有机会能开一个相关的课程,这好像能有种让人达成某种圆满的感觉。

斯宾诺莎的镜片
斯宾诺莎的镜片 2017-09-06 22:02:49
三年又三年了。你说的对,smullyan的书名我写错了。smith的书后来没看了。尽管自己现在做的东... 三年又三年了。你说的对,smullyan的书名我写错了。smith的书后来没看了。尽管自己现在做的东西离哥德尔定理所属的领域已经很远,但还是对它的相关问题保持着一定程度的兴趣。我猜包括我在内很多学逻辑的人,第一次真正感受到逻辑的魅力,就是在初次接触哥德尔定理的时候。有一个愿望,就是有机会能开一个相关的课程,这好像能有种让人达成某种圆满的感觉。 ... Tension

那就保持期待,说不定有机会来做客聆听。(也许现实里也见过.....毕竟国内的逻辑圈不大)