号称世界上最难的逻辑题

已知:
1.神无所不知只说真话,鬼无所不知只说假话,人有所不知胡乱说话,除此之外三者没有任何区别。他们一定回答且只能回答任何有确定答案的是非题。
2.“Da”和“Ja”一个永远代表“是”另一个永远代表“否”,但你完全不知道二者分别代表哪个。

问题Z:你面前站着神、鬼、人各一,你不知道三者分别是谁,你必须通过提问正确区分出三者。你每次只能对其中一个提问,一共只能问三次,但你每次提问得到的回答只能是“Da”或“Ja”。

如果你觉得Z太难,这里有一个简化版Z’:跟Z类似,但得到的答案只能是“是”或“否”。

如果你还是觉得太难,还有一个更简单的问题Y:你面前有两条路,一条通向天堂,一条通向地狱。路口站着神、鬼各一,你不知道二者分别是谁。你现在只能对其中一个提出一个是非题,判断出哪条路通向天堂。但你提问得到的回答只会是“Da”或“Ja”。

如果你觉得Y也太难,也可以简化为Y’:跟Y类似,但得到的答案只会是“是”或“否”。

附加条件:
如果你解决了Z或Z’,那么请加一个条件:你对其中一个问的问题中不允许同时提及另外两个。
如果你解决了Y或Y’,那么请加一个条件:你对其中一个问的问题中不允许提及另外一个。

问题Y还可以有如下变体Y”:路口只站着一个家伙,你只知道他要么是神要么是鬼。你现在只能向他问一个是非题,判断出哪条路通向天堂。其他不变。

一点提示:
对A提问:『将鬼、人、神分别编号为1,2,3,那么请问B的编号大于C么?』
对A提问:『如果我问你『B是乱说话的人么?』,你会回答什么?』
对任何一个提问:请问『……』这个问题的答案是Da么?

关于贝叶斯主义

扣薪 12:25:58
晃晃对主观贝叶斯主义咋看的?
晃晃 12:31:35
贝叶斯主义是对贝叶斯定理的滥用
晃晃 12:31:50
根本就是用错了
晃晃 12:32:34
贝叶斯定理需要对随机事件的分布猜测一个模型,然后确定模型参数
晃晃 12:33:25
而贝叶斯主义要么没有说如何得到这个模型,要么武断地采用某种特殊模型
晃晃 12:34:52
例如判断太阳明天是否会继续从东方升起,贝叶斯主义的模型就是假定太阳每天升起的概率都相同,然后通过历史积累的数据来计算这个概率有多高
扣薪 12:36:15

晃晃 12:36:46
这不可能是正确的。如果我现在正在做一个工作,每天都经过一个门,但一年以后我会做其他工作不再经过这个门,事先已经计划好了。那么对我来说这一年之内我经过这个门的概率都是高的,而一旦过了一年,我经过这个门的概率就变得很低。
晃晃 12:37:02
如果你假定我每天经过这个门的概率是相同的,那么自然会得到错误的结果
aha 12:37:28

晃晃 12:37:31
你不知道我经过这个门的概率随着时间变化的事实,只是粗暴地假定我按照固定的概率经过这个门
晃晃 12:38:12
贝叶斯主义没有告诉我们如何猜测这个模型
扣薪 12:39:45
nice
晃晃 12:40:50
贝叶斯主义的问题还多着呢
晃晃 12:41:02
什么叫做事件,并没有清楚的定义。
扣薪 12:41:08

晃晃 12:41:30
例如太阳每天从东方升起,是每天算一个事件,还是每小时太阳都按照预测在既定的位置都算一个事件?
晃晃 12:41:45
要是每秒钟都算一个事件,那么事件的数量非常多
扣薪 12:41:41
但貌似这玩艺在医学里有点应用
晃晃 12:42:03
使用贝叶斯定理没有什么错误
扣薪 12:42:21

晃晃 12:42:23
因为只要你对概率分布有合理的知识就可以
晃晃 12:43:07
对于我们已经熟知的东西,只是某些参数不知道的情况下,我们自然可以用贝叶斯定理来确定这些参数
晃晃 12:43:34
但是对于我们完全不了解的问题,就不能用
晃晃 12:44:06
例如有些人用贝叶斯主义计算上帝存在的可能性等等,这些都是混账逻辑
扣薪 12:44:48
(哈哈)
扣薪 12:45:29
他们算出来是接近0吗?
晃晃 12:46:52
不同的假定和对事件的规定计算出来的截然不同
晃晃 12:47:14
范围胡乱地分布在(0,1)之间
晃晃 12:47:28
没有任何参考价值
扣薪 12:47:46
(哈哈)

看来确实很少有人真的能够区分科学和信仰。

就连许多支持科学的人都是把科学当作一种信仰来看待的。

他们的论证大致是:任何理论都有基础,这个基础是不可解释的,只能无条件的相信。

然后呢,基本的逻辑推导规则(例如排中律矛盾律之类的东西)也被他们认为是一种信仰,认为这是不可解释只能相信的,于是数学和逻辑也被划归为信仰。

他们相信科学,相信数学,他们认为自己和其他的教徒一样,但是坚信自己所信仰的科学是一种确实比其他宗教更加正确的宗教。

一旦遇到最基本的问题,他们就会说,这是公理,没办法争论,只能相信或者不相信。

以这种方式看待科学的人,往往有可能同时支持马克思的哲学和政治经济学,以为这些也是科学。

--------------------
Q:
如你以前的帖子所说,只要人们互相沟通,就等于都接受了一个默认的共识。也就是说认为:双方是可以沟通的,有沟通的基础。至于这基础是生理上的、方法论上的(比如逻辑)、语法上的、还是其他,都不妨。
即,思考和沟通这些事情本身证明逻辑、公认逻辑是存在的。作为科学的基础,这个共识和需要依赖传说故事的信仰是有所不同的。

A:
事实上,逻辑只是被制造出来的约定,在现实世界中无所谓存在不存在。

数学和逻辑的公理全都是约定。我们根本无须假定某种约定一定能够适用于现实世界的某些情况。我们所作的其实是:把这些约定往某些问题上套,如果套上了,就说明这个问题很可能可以用这套约定来描述,于是我们就继续使用这套约定。如果有一天发现某种情况下这种约定的结论跟某个现实问题不一致,那么可能是因为这个问题不适合这套约定。但这不等于这套约定本身有什么错误,只不过把这套约定用于某些问题是错的。

如果你不愿意使用别人普遍使用的约定,你当然可以发明一种跟其他人不同的约定。但如果别人的约定和你的约定都能够成功滴套在大量相同的问题上不出差错,那么很可能说明你的约定和别人的约定是同构的,能够相互翻译,只是符号和语法的不同。完全不同构的约定系统是不能处处给出相容的结论的。

所有这些约定,单纯从约定本身来看,并没有什么优劣之分。但是,当这些约定用于现实问题的时候,你会发现有些约定的适用范围非常普遍,而另外一些约定适用范围相对狭窄。这说明了现实世界本身·可能·是有某种结构的。但没有任何理由相信现实世界一定(永远)符合某种你所假设出来的某种约定。

逻辑约定,可以说是以知的适用范围最广泛的约定,其次就是关于自然数的约定……。不但如此,如果逻辑和自然数的约定仅仅套用于约定体系内部,也就是说仅仅用于数学,那么压根就不需要对这种应用进行任何现实世界的实践检验。

一种物理理论的核心基本假定,事实上也是一个约定系统,但这样的约定系统的设计目的就是为了套用到现实世界的问题上,因此必须通过现实世界的实践检验。当然,即便一套物理理论最终被证明是错误的,其数学内容如果对数学研究有用,也照样可以变成数学的一个部分,从此不再需要接受现实的检验,但也不能再直接用于对现实问题的预言。

Q:
赞成。就是这个:现实世界本身·可能·是有某种结构的

换句话说,只要人们进行任何思考和交流活动,就只能默认这个约定是“可能的”,否则全部变成南柯一梦。
这个约定的强度,比宗教不知道强多少倍。所以俺不认为很多东西的最终归属就是类似于宗教般的“信或不信”。

A:
也不必默认什么,你不同意别人的约定可以自己创造约定,欢迎你能创造出不同构的约定。

如果你创造不出来,还在到处不自觉滴使用逻辑,你还强说你的系统比逻辑更牛逼显然就是做梦,只能自扇耳光。

这就好像:我们可以想象比图灵机更牛逼的超限计算机,但是除非你真的有一台,否则你拿着一台图灵机愣说这台机器超越了图灵机就是做梦了。

Q:
能不能证明 宇宙本身在某种程度上就是一个图灵机?

A:
宇宙本身完全可以是超限计算机。而这一点是不能被绝对证明或者否定的。

即便宇宙是超限计算机,也不等于我们可以制造超限计算机。

即便给我们一台超限计算机,我们能够对这台超限计算机提供的所有可能的输入和能够区分的所有可能输出也是有限的。这种情况下,对我们来说一台超限计算机未必比普通的图灵机强多少(这个是一个数学问题,我不知道是否已经有了数学结论)。

经典计算机不可能是超限计算机,对于经典物理学系统,虽然物理量被表示为实数,但由于误差的存在,可区分的状态仍然是有限或者可数的。

完全由qubit构成的量子计算机也已经有人证明等价于图灵机。

甚至完全可以有这样的可能:任何一块物质都是超限计算机,我们本身也是,但我们的意识不是(这一点几乎是肯定的),以至于我们能够利用的计算机也无法是超限计算机。这种情况下大概只有上帝才能把我们当作一台超限计算机做它喜欢的计算。

宇宙本身的量子态·可以·是连续的,而支配宇宙的规律·可以·是无限精确的(有些人误以为量子力学引入了不确定性,现在知道我们并不能确认这一点,不多说了)。这种情况下,如果我们所讨论的宇宙是个孤立的系统,没有输入和输出,那么可以把这样一个宇宙看成有连续统那么多个状态的由基本物理规律支配其状态迁移过程的确定状态机,这当然是一种超限计算机。在这种情况下,宇宙中每一块物质都是一个超限计算机,而由于这块物质不像整个宇宙一样是孤立的,它跟外界有相互作用,使之不再是一个单纯的确定状态机,而是能够接受输入产生输出的“超限图灵机”。

与此同时,我们并不能完全排除宇宙的状态是离散的或者有限的而宇宙的规律是不精确的这种可行性。

在数学上永远都存在一些互不等价的理论无法被当前的所有已知实验挑选出来,所以我们并不能绝对证明这个宇宙是哪种计算机。我们只能说,在某种特定的物理理论之中,宇宙会是一台什么样的计算机。

单纯站在量子力学的立场上,宇宙完全可以是一台上述的超限计算机,但我不知道在量子场论、超弦的那些新限制中会怎样。

图灵机的能力

目前最流行的符号推导软件具有一些基本的公式推导和逻辑推导的能力,但是这些软件还远远谈不上智能。例如以前我使用Mathematica和Maple的时候,许多结果需要用无穷级数来表达的积分之类的东西是无法自动被这些软件推导出来的。

但事实上我们人类所能够写出的无穷项级数才能精确表示的数学表达式,必然可以用有限个符号所刻画。有时候我们使用“…”来表示无穷级数的项,事实上这是因为我们能够在前面几项中看出规律的时候才使用这种缩写,而这种规律自然是有限符号可以刻画的。或者我们看不出其中的规律,只是求出了前面几项,那么我们所得到的结果自然也就不是完整的,仅仅是只需前面几个有限项就能够描述的非精确描述,这种情况下我们所得到的不完整的计算结果仍然是有限符号可以表达的。

这样,只要引入适当的推导规则,那么许多无穷级数解也可能可以被符号推导软件所推导出来。当然,对于现有的符号计算软件,引入适当的推导规则这种事情还要人来做,软件在闲着没事的时候自己不会去尝试发现这些原来所不具备的推导规则。

不过即便软件在闲着的时候会主动做一些发现新规则的探索游戏,仍然受到一个限制:由于计算机本身的可靠性,这些软件基本上是不会出随机错的,其能力会直接受歌德尔不完备性定理的限制。但图灵早在歌德尔不完备性定理刚刚提出不久就曾经澄清过,歌德尔不完备性定理所限制的是那种仅仅能输出正确结果的机器,而不能限制可能输出错误结果的机器(Penrose在这个问题上确凿无疑滴错乐)。因此,一台挂接了真随机数发生器的以一定概率出错的图灵机(例如读写会以一定的概率把1当成0或者把0当成1,状态迁移会以一定的概率迁入错误的状态,状态迁移表会以一定的概率发生不确定的改变),就不再受歌德尔定理的限制。而且不但如此,不挂接真随机数发生器,使用图灵机自己生成伪随机数,也可以在随机预言模型下(Random Oracle)以任意高的精度模拟带有真随机数发生器的图灵机,只有对那些在计算过程中刚好会出现某种匹配了伪随机数发生器算法序列的问题上显示出其局限。

曾经有人以为量子计算机的能力超越图灵机,但有人做过研究之后认为量子计算机的能力并不能超越带有真随机数发生器的图灵机。目前已经严格证明所有完全由qubit构成的系统最多等价于图灵机,但对于一般的量子计算系统是否都等价于图灵机尚未给出最后的答案。

超限计算在计算能力上超越图灵机,但是需要能够识别无限数量的符号或者拥有无限个状态,这里的无限甚至可以不是可数的无限。我们可以讨论超限计算的能力极限,因为这只需要有限个符号。但是我们却没有能力直接利用这种模型进行实际的计算。虽然物理量的值往往被当作实数,但由于误差的存在,导致事实上我们能够区分的取值只是有限个。虽然量子态在量子力学中是无限精度的,但测量所得的结果只能是本征值,本征值要么只是离散,要么是连续但有误差的,量子态的精确信息在测量过程中丢失了。因此我们现在不知道任何一种在物理上实现可以被我们利用的超限计算机的方式。

我猜,有限状态识别有限符号的计算机的能力上限就是图灵机,不可能超越图灵机,不知道是否能够对此做出严格的证明。

逻辑并不是一种信仰

逻辑不是信仰,逻辑规则直接蕴含于人类的语言中。不同语言能够相互翻译说明了它们同构。逻辑学不过是将语言中的推理规则提炼出来而已。人类之所以能够在逻辑推理的基本约定上达成一致就是因为语言的同构。即便是教徒,只要他能够跟别人进行最平凡的日常交流,那么逻辑对于他来说就完全是不可避免的。反对逻辑的人(如果他能够跟别人进行日常交流),说明他根本没意识到自己的每一句话都在使用基本逻辑约定。把逻辑当成信仰的看法不但没有抓住信仰的根本特征,也完全没弄明白逻辑是从何而来的。

演绎推理和因果关系

http://bbs.oursci.org/newreply.php?postid=30829

------------------------------------
30829-疑问 又是问题: 演绎推理和因果性 是什么样的关系?
作者:uncutstone
时间:2004-12-29 11:50

------------------------------------
30886- 不知道你所说的因果性是什么概念……
作者:荒唐
时间:2004-12-30 08:10

演绎推理是根据一些假定得出假定成立时必然成立的判断。至于是谁是因谁是果,跟前提和条件之间并没有对应关系。

例如,你发现米饭烧糊了(前提),结合一些环境因素以及以往的经验(前提),可以推断出烧干锅了(结论);你做饭时发现烧干锅了(前提),结合一些环境因素和以往的经验(前提),也可以推断出米饭会被烧糊(结论)。虽然我们认为烧干锅是米饭糊的原因之一,而不是结果,但结果仍然可以做为前提,原因仍然可以做为结论。

所以前提、结论并不等价于因、果。虽然在包含了如何判断谁是因、谁是果的判断规则的逻辑系统中,也可能可以利用演绎推理来得出哪个是因哪个是果,但因和果却不一定是前提和结论的关系。

因果关系的通常理解除了逻辑上的蕴含关系之外,还跟时间顺序有关。如果我们要在严格定义因果关系的同时,不破坏这个概念在日常不精确语言中的中心含义,就必须把时序也考虑进去。我没有仔细研究过日常语言中因果关系的核心含义是什么,不能随便给出一个因果关系的定义,但我想时序可能是不可忽略的要素。前提和结论虽然在语言中似乎也有先后之分,但是在数学中这两个概念跟时序没有任何联系,只是由于它们借用了不精确的日常概念,从而容易引起误解。

爱因斯坦说过:
只要数学的命题是涉及实在的,他们就不是可靠的;只要他们是可靠的,他们就不涉及实在。

我认为因果关系应该是一种描述实在(物理世界)的概念,他们跟前提和结论这种数学世界的概念的是不可等同看待的。

关于逻辑中的蕴含关系

http://bbs.oursci.org/newreply.php?postid=30793

------------------------------------
30793- 另一个迷思, 请教
作者:uncutstone
时间:2004-12-28 19:04

有两个真值函数 p , q.
如果 p->q 取真值, 不表示p 是 q 的原因。
p->q 永取真值, 也不表示p 是 q 的原因。
p=>q, 也不表示 p 是q 的 原因。
-> 表示逻辑连接词 if ..then ..
=>表示逻辑推论

举一个例: 1+1 =2 => 饭可以吃。 谁也不是谁的原因。

还是感觉违反直觉。按照通常的理解, p=>q, 那么p 是q的一个原因。

愚钝啊。 🙁

------------------------------------
30876-高兴 我尝试解释一下:
作者:荒唐
时间:2004-12-29 21:32

我怕我们使用的符号不一致,
所以先说一下命题逻辑的符号约定:
 非:~
 与:&   a&b严格等价于~(a->~b)、~(~a|~b)
 或:|   a|b严格等价于~a->b、~(~a&~b)
蕴含:->   a->b严格等价于~a|b、~(a&~b)、(a<->b)|b
等价:<->   a<->b严格等价于(a&b) | (~a|~b)

约定从上到下运算优先级从高到低。
只要有~运算外加&、|、->三者之一,就可以推出其余逻辑运算符

上面这些命题逻辑的符号,包括->,都是一种运算符号,他们的左项和右项无需有任何关系。

a->b的含义是,只要不是a真b假,a->b的值就是真,并非a能推导出b或者a是b的前提。把->当作if…then…实际上很容易引起误解。
所以“1+1=2 -> 饭可以吃”这个公式并非表示前者是后者的前提,仅仅表示如果前者是“1+1=2”后者是“饭可以吃”就可以让这个公式取“真”值。仅此而已。

你所提到的符号=>,含义应该是下面两个符号之一(我的书里面大部分使用下面这两种符号):
逻辑后承:|=
逻辑推论:|-(也就是推出)
这两个符号定义不同,但命题逻辑的完备性定理证明了这两个符号是等价的。
一个命题是一组命题的逻辑后承(|=)表示如果该组命题为真,那么该命题就必为真。
而一个命题是一组命题的逻辑推论(|-)表示这组命题按照直接推导规则能够在有限步骤内得到该命题。
命题逻辑所定义直接推导规则只有一个:a, (a->b) |- b
(一阶逻辑增加一条基本推导规则:A |- (for all x)A。)

此时a & (a->b)确实可以作为b成立的前提条件,b确实可以看做是他们的逻辑结论。而如果写“1+1=2 |- 饭可以吃”是错误的,没有这样的推导规则。这样写才是正确的:“(1+1=2 -> 饭可以吃), (1+1=2) |- (饭可以吃)”

意思是说,只要你规定了“如果1+1=2为真,那么饭可以吃就必为真”这件事情是必然的,那么此时只要“1+1=2”也确实为真,就一定可以逻辑第推断出“饭可以吃”这个逻辑结论。

这个逻辑推论的真实性是并非直接是因为“1+1=2”,而是基于上面的两个前提的真实性。上面的真实性是你规定出来的,并非逻辑系统能够判断出来的。

------------------------------------
30892- 这里有点误解, 我解释一下
作者:uncutstone
时间:2004-12-30 09:58

我写的 ‘1+1=2’ 和 “饭可以吃”, 意思是这两个命题分别都是永真命题。
所以命题 ‘1+1=2’ ->“饭可以吃”, 也是永真的。
那么根据 ‘|-’ 的定义, 如果p-> q 永真,有 p |- q.
所以我有 ‘1+1=2’ |- “饭可以吃”。 也就是说, 如果任意两个命题 A , B 永真, 就会有 A |- B, B |-A. 一个永真命题可以推导出任何一个永真命题。

我的理解, 一个永真的蕴涵就是一个逻辑推论。这个地方有一点自相似性, 容易让人糊涂。

------------------------------------
30923-哈哈 嘿嘿,你对永真的理解错了啦……
作者:荒唐
时间:2004-12-30 13:51

形式逻辑中的永真式(重言式)是指逻辑系统内部的公式,永真式中任何一个项无论取什么样的值,式子本身都保持真。

例如A<->A、A|~A、~(A&~A)这些都是永真式。

而“米饭能吃”核“1+1=2”这两个命题在逻辑系统内部根本是不可能判断真假的,所以它们根本不是(逻辑系统的)永真式。

------------------------------------
33050- “蕴含”可以理解成“如果…那么…”
作者:荒唐
时间:2005-01-25 16:30

日常生活中的“如果…那么…”在“如果”不成立的时候没什么用处,但在逻辑运算中,“如果”不成立也有真值,其真值为“假”。

“推出”(|-)也可以看作是“如果…那么…”,但“推出”这个东西不是用来参与逻辑运算的。

推导规则就是把“|-”和“->”二者联系起来的东西。

推导规则是说,如果“如果A那么B”为真,同时“A”也为真,那么我们可以“推出”一个逻辑结论:“B”为真。

你只需把逻辑公式当做有真假的判断句,由逻辑运算符连接起来的句子也是有真假的逻辑公式,“->”理解为“如果……那么……”并且即使句子错误的也可以利用这个句子的“假”值。

推出“|-”除了它不用来表示逻辑运算,而是用于逻辑推导过程之外,跟“->”没有什么区别就行了。因为如果再使用“->”表示推出,那么推导过程就被这个东西连接成了一个整个的逻辑表达式了,为了避免这种情况出现,就制造了一个专门用于表示推出的符号“|-”。

------------------------------------
32610- 逻辑推导规则并不需要真值表才能定义。
作者:荒唐
时间:2005-01-19 15:20javascript:void(0)

“->”仅仅是“蕴含”这个“逻辑运算”的符号,并不表示“推出”

命题逻辑只有一条基本推导规则(其它规则可以导出):
A, A->B |- B
意思是说,只要有A和A->B二者成立,那么可以推导出B。

一阶逻辑增加一条基本推导规则:
A |- (for all x)A

Goodstein定理

http://bbs.oursci.org/newreply.php?postid=31376

------------------------------------
Goodstein定理——歌德尔不完全定理在皮亚诺公理系统中的一个例子
作者:冷饭
时间:2005-01-05 18:45

从非常非常粗糙的角度讲,歌德尔证明他的不完全定理的方法,就是构造了一个类似“本命题不可被证明”这样一个命题。当然这个陈述是很不严格的,因为现在逻辑中禁止在命题中提到“本命题”这样的玩意,另外,“证明”不是一个在皮亚诺算术系统中定义了的概念。歌德尔证明中的主要思想之一,就是如何解决后一个难点。这个就不具体说了。

在歌德尔不完全定理被证明时,大多数数学家并不太担心自己会实际上碰到这样的既真但又不可被证明的命题,因为这样的命题似乎都是一些很怪的绕来绕去的人造玩意,在数学中被实际研究的问题,应该不会是这样的。现在大多数数学家应该还是这个心态,比如说研究歌德巴赫猜想的很少会去怀疑这个命题会不会是在集合论公理体系下解决不了的。

但是有一些看起来很自然的命题,已经被证明是不能在某些公理体系下证明的。在这里我介绍其中最早被发现的这样的定理之一:Goodstein定理。

任取一个自然数n,比方说266,我们把它写成以2为底的幂次的和,其实就是转成2进制:
266 = 2^8+2^3+2
现在右边还有比2大的数字比如说8啊3啊,就进一步转换变成
266 = 2^2^3 + 2^(2+1)+2
还有一个3,继续写成
266 = 2^2^(2+1) + 2^(2+1)+2

可以知道,无论什么自然数都可以唯一地写成这样的形式。同样地,如果不是以2为底而是以其他大于2的自然数为底,也可以做同样的事情。

现在我要把刚才那个式子的右边中的所有2都改写成3,那就成了
3^3^(3+1) + 3^(3+1)+3
再减去一个小小的1,就成了
3^3^(3+1) + 3^(3+1)+2
这就是现在这个数以3为底的这种展开。

现在把这个式子的右边中的所有3都改写成4,那就成了
4^4^(4+1) + 4^(4+1)+2
再减去一个小小的1,就成了
4^4^(4+1) + 4^(4+1)+1
这就是现在这个数以4为底的这种展开。

现在把这个式子的右边中的所有4都改写成5,那就成了
5^5^(5+1) + 5^(5+1)+1
再减去一个小小的1,就成了
5^5^(5+1) + 5^(5+1)
这就是现在这个数以5为底的这种展开。

现在把这个式子的右边中的所有5都改写成6,那就成了
6^6^(6+1) + 6^(6+1)
再减去一个小小的1,就成了
6^6^(6+1) + 6^(6+1) – 1
这可不是现在这个数以6为底的这种展开,因为有一个-1。所以展开来,它就是:
6^6^(6+1) + 5*6^6 + 5*6^5 + 5*6^4 + 5*6^3 + 5*6^2 + 5*6 + 5
这就是现在这个数以6为底的这种展开。

现在把这个式子的右边中的所有6都改写成7,那就成了
7^7^(7+1) + 5*7^7 + 5*7^5 + 5*7^4 + 5*7^3 + 5*7^2 + 5*7 + 5
减去一个小小的1,就成了
7^7^(7+1) + 5*7^7 + 5*7^5 + 5*7^4 + 5*7^3 + 5*7^2 + 5*7 + 4
这就是现在这个数以7为底的这种展开。

……

这么我们可以一直继续下去,数字似乎变得越来越大,增大的速度也越来越快,比方上面以7为底的那个数字要比7^7^8大,而7^7^8如果要用十进制写出来,需要用四百八十多万位数字,要印成了书都成煌煌巨著了。因为底数增加1,原来的数字就会增加很多,减去一个小小的1根本是九牛拔一毛无所谓。

但是,但是,Goodstein定理说,对任意的自然数n,当然266也包括在内,如果我们一直重复这个过程,我们最后总会到达0!

让我们来验证一下:对于n=0,1,2,3,都没什么好说的,很快掉到0。
n=4,第一排数字是步数,也就是现在是以几为底的表示了,第三排是那个式子,第二排是式子用十进制表示出来的值。

2  4    2^2
3  26  2*3^2 + 2*3 + 2
4  41   2*4^2 + 2*4 + 1
5  60   2*5^2 + 2*5
6  83   2*6^2 + 6 + 5
7  109   2*7^2 + 7 + 4
8  139   2*8^2 + 8 + 3
9  173   2*9^2 + 9 + 2
10  211  2*10^2 + 10 + 1
11  253  2*11^2 + 11
12  299  2*12^2 + 11
13  348  2*13^2 + 10
:   :    :
23  1058  2^23^2
24  1151  24^2 + 23*24 + 23
25  1222  25^2 + 23*25 + 22
:   :    :
47  3290  47^2 + 23*47
48  3407  48^2 + 22*48 + 47
:   :    :
95  11115  95^2 + 22*95
96  11327  96^2 + 21*96 + 95
:   :    :

注意到从第三步开始有个大项2*3^2,这个项中只有“3”这个地方以后会大起来,其他的一直保持不变,直到第24步的时候,这个项没有了,大项换成了 24^2,然后这一项里也就“24”这地方会变。然后这样下去大约要4亿多步以后,跟在这个平方项后面的那些杂碎都完蛋了,它成了孤家寡人,然后减一个小小的一,这个平方项就不见了。然后再这么下去,大约要再过10^121步,它才变成了0。

通过验证4,我们可以看见一个图景。就象我们看着倒记时的数字式电子跑表的时候,秒位上的数字滴答得很快,一秒秒减下来,等到0秒,再过1秒的时候,分位上的数字减1,可是秒位上的又变成59了,然后又是60秒后,分位上的数字也成0了,再过1秒,小时位上数字减1,分位和秒位上都又成99了。不过慢是慢,迟早会通通变0的。仔细观察刚才关于4的序列,我们发现Goodstein定理的序列中,也有一个类似的钟,只是它的每“分钟”,都要值许多许多“秒钟”,每“小时”要值许多许多“秒钟”,以至于我们感到这个钟不走了,甚至不是倒记时,而是向前走的!

“它的每‘分钟’,都要值许多许多‘秒钟’,每‘小时’要值许多许多‘分钟’”

不仅如此,它的每‘分钟’要值多少‘秒钟’不是固定的,越晚走掉的每一“分钟”,值的“秒钟”,要比前面的“分钟”要多得多,就好比在那个电子秒表里,第一次秒数走到0再过1秒时,分数减1,秒数变59,而第二次秒数走到0再过1秒时,分数减1,秒数却变成1000,第三次秒数走到0再过1秒时,分数减 1,秒数变成10000……(Goodstein序列中这个秒数增加的速度要比这个快得多)。同样,“小时”对“分钟”也是一样。而且还可以有“小时”以上的级别,象“天”“月”“年”。这样,如果你老是注意着“秒数”,就很容易觉得它越来越大,这倒数记时怎么也数不到0。

验证从5开始的序列……这个就算了吧。

Goodstein定理的叙述完全可以在皮亚诺公理系统中进行,它只牵涉到对数字的加减乘的运算,没有必要用到集合论,但是对于它的证明却用到了集合论。在1982年,两位数学家证明了,如果不用集合论,只在皮亚诺公理系统中,是不可能证明此定理的。

------------------------------------
31770- Goodstein定理的证明大纲
作者:bamboo
时间:2005-01-10 15:28

背景知识:

超穷序数
所有集合A都可加以良序,亦即(1)A的任意两个不同元素都可以比较大小及(2)A的任一子集S都有一个最小元素。如果集合A是有限的,良序化后便与某一自然数(在这里的意思包括0)相对应(包括元素大小的顺序)。个别自然数0,1,2,3,…构成有限序数。自然数整体(包括其顺序)是最小的无限序数,记之为ω={0,1,2,3,…}。在自然数之后还有其它无限序数(超穷序数),例如ω+1={0,1,2,3,…,ω}及ω+2={0,1,2,3,…,ω,ω+1}。如果集合A是无限的,良序化后便与某一超穷序数相对应。当然同一个集合A可以有不同的良序,如果A是无限的,那么不同的良序化后便可能相对应不同的序数。

超穷序数的生成
0,1,2,3,…,ω,ω+1,ω+2,…,ω+ω=ω2,ω2+1,ω2+2,…,ω3,…,ω.ω=ω^2,…,ω^2+ω,…,ω^3,…,ω^ω,…, ω^(ω+1),…,ω^(ω^2),…,ω^(ω^2)+ω^2+ω,…,ω^(ω^2+ω),…,ω^(ω^3),…,ω^(ω^ω)=ω^^3,…, ω^(ω^(ω^ω))=ω^^4,…,ω^^ω=ε0,以及更大的超穷序数。由序数构成的集合按序数大小排列已经是良序化了。

超穷归纳法
我们熟悉的数学归纳法可以用集合论的语言表述为:设S是自然数集合Z的一个子集,如果(1)0是S的元素,及(2)从k是S的元素可推出k+1是S的元素,那么(3)S=Z。数学归纳法是Peano算术系统的公理之一。
对于良序化的集合也有类似的性质:设A是良序化的集合,S是A的一个子集,如果(1)A的最小元素是S的元素,及(2)x是A的元素而从所有在A中比x小的元素是S的元素可推出x也是S的元素,那么(3)S=A。这便是良序集合的超穷归纳法。
易证数学归纳法是超穷归纳法的特殊形式,但从数学归纳法不能推出超穷归纳法,因为数学归纳法不能跨越从有限到无限的鸿沟。

Peano算术系统的协调性(Consistency)
Godel证明了不能仅由Peano算术系统的公理出发证明其本身的协调性。但Gentzen证明了藉助超穷归纳法(只需假设直到ε0成立,不需对更大的序数作任何假设),可以证明Peano算术系统的协调性。

由序数构成的严格递减序列
因为由序数构成的集合按序数大小排列已经是良序化了,可以运用超穷归纳法
证明,由序数构成的严格递减序列的长度是有限的。(比对:由有理数构成的严格递减序列的长度可以是无限的,但由自然数构成的严格递减序列的长度必然是有限的。)

Goodstein定理的集合论证明大纲:

在Goodstein序列中把所有进制底数(即第一个Goodstein数中的2,第二个Goodstein数中的3,等等)换成ω,把底数以外的数字保留而加以合适的解释(要注意运算的顺序,3ω跟ω3是不同的,前者其实等于ω,后者等于ω+ω+ω),例如以5为底,2*5^(3*5)+4*5+1便换成(ω^(ω3))2+ω4+1=ω^(ω+ω+ω)+ω^(ω+ω+ω)+ω+ω+ω+ω+1。整个Goodstein序列便换成另一条由序数构成的严格递减序列。因为这种序列的长度是有限的,所以原先的Goodstein序列的长度也是有限的,便推出任一正整数在Goodstein变换下终于会达到0的结论。

Goodstein定理不能由Peano算术系统公理推出的证明思路:

简而言之,就是若从Goodstein定理即「所有Goodstein序列都收敛于0」出发,可以推论出超穷归纳法直到ε0成立。若Goodstein定理能够由Peano算术系统公理推出,根据Gentzen的工作结果,即可证明Peano算术系统本身的协调性,但这与Godel的工作结果相矛盾。因此 Goodstein定理不能由Peano算术系统公理推出。

------------------------------------
但是我有一个疑问,换底之后,递减的过程中出现的“-1”是如何消除的?因为并没有“ω-1”这种东西啊?

------------------------------------
31838- 项数是固定的
作者:bamboo
时间:2005-01-11 09:31

令G为原Goodstein自然数序列,F为进制底数换成ω后的序数序列。要知道F(k+1)不是由F(k)-1而来,而是由G(k+1)换底而来,因此不会产生ω-1的问题。

以266为例:
G(1) = 266 = 2^2^(2+1) + 2^(2+1)+2
F(1) = ω^ω^(ω+1) + ω^(ω+1)+ω
G(2) = 3^3^(3+1) + 3^(3+1)+2
F(2) = ω^ω^(ω+1) + ω^(ω+1)+2
G(3) = 4^4^(4+1) + 4^(4+1)+1
F(3) = ω^ω^(ω+1) + ω^(ω+1)+1
G(4) = 5^5^(5+1) + 5^(5+1)
F(4) = ω^ω^(ω+1) + ω^(ω+1)
G(5) = 6^6^(6+1) + 5*6^6 + 5*6^5 + 5*6^4 + 5*6^3 + 5*6^2 + 5*6 + 5
F(5) = ω^ω^(ω+1) + (ω^ω)5 + (ω^5)5 + (ω^4)5 + (ω^3)5 + (ω^2)5 + ω5 + 5
G(6) = 7^7^(7+1) + 5*7^7 + 5*7^5 + 5*7^4 + 5*7^3 + 5*7^2 + 5*7 + 4
F(6) = ω^ω^(ω+1) + (ω^ω)5 + (ω^5)5 + (ω^4)5 + (ω^3)5 + (ω^2)5 + ω5 + 4

原G序列收敛到0的项数是固定的,F序列跟G序列一样,也是固定的。

二元关系学习总结

preorder(预序): reflexive, transitive

partial order(偏序,对应图论的有向无环图): preorder + anti-symmetric
total preorder(完全预序): preorder + total
equivalence(等价): preorder + symmetric

complete(全互连,对应图论的完全连通图): total preorder + symmetric or equivalence + total
equality(相等): equivalence + anti-symmetric or partial order + symmetic
total order(全序): partial order + total or total preorder + anti-symmetric

注意,上述关系中的后三个关系所用到的某些属性已经不是独立的了,例如相等关系用自反性、对称性、反对称性就可以导出传递性(因为对称性和反对称性限制了关系只能发生在每个元素自身上,自反性则保证了每个元素自身都满足这个关系。结果没有可能发生传递,因此传递性自然被满足。)

上面的提到的各种关系R所用到的各种属性:
reflexive(自反性): for all x in X it holds that xRx
transitive(传递性): for all x, y and z in X it holds that if xRy and yRz then xRz.
symmetric(对称性): for all x and y in X it holds that if xRy then yRx
anti-symmetric(反对称性): for all x and y in X it holds that if xRy and yRx then x = y
total(完全性): for all x and y in X it holds that xRy or yRx (or both)

二元关系的其它一些常见属性:
irreflexive(非自反性): for all x in X it holds that not xRx
coreflexive(伴自反性): for all x and y in X it holds that if xRy then x = y
asymmetric(非对称性): for all x and y in X it holds that if xRy then not yRx

1
2
3
4
5
6
7
8
9
10
11
     PR
    /|\
   / | \
  /  |  \
 /   |   \
 PA  TP  EV
 |\  /\  /|
 | \/  \/ |
 | /\  /\ |
 |/  \/  \|
 TO  EQ  CP

PR: preorder
PA: partial order
TP: total preorder
EV: equivalence
TO: total order
EQ: equality
CP: complete connection

/: anti-symmetric
|: total
\: symmetric

一个重要的未讨论过的关系:

well order(良序): total order + well-founded

well-founded(良基关系):every non-empty subset of X has a minimal element with respect to R; that is, for every non-empty subset S of X, there is an element m of S such that for every element s≠m of S, the pair (s,m) is not in R.

If a set is totally ordered, then the following are equivalent:
1. The set is well-ordered. That is, every nonempty subset has a least element.
2. Transfinite induction works for the entire ordered set.
3. Every strictly decreasing sequence of elements of the set must terminate after only finitely many steps (assuming the axiom of dependent choice).

其它关系:
* Dependency relation, a symmetric, reflexive relation.
* Independency relation, a symmetric, irreflexive relation.
这两种关系是互补的。