计算机科学与人物

计算机起源的数学思想(二)

2009年8月18日 阅读(48)

 转载请注明作者:phylips@bmy

弗雷格的突破与绝望

弗雷格的一生主要发表了这样三本著作:《概念演算–一种模仿算术语言构造的纯思维的符号语言》(1879)、《算术的基础–对数概念的逻辑数学研究》(1884)《算术的基本规律》(l卷 1893,2卷1903)。

其中概念演算,将普通数学中的一切演绎推理都包含在内,成为第一个完备的逻辑体系。布尔以普通代数为基础,用代数符号来表示逻辑关系。与此相反,弗雷格想以他的逻辑为基础而把代数构造出来。实际上这成为日后一个重要的学派"逻辑主义",在他们看来逻辑与数学的关系就像一门学科的基本部分和高等部分之间的关系。

弗雷格的逻辑体系,表现在今天就是我们数理逻辑中的命题演算和谓词演算(用数学的方法研究关于推理、证明等问题的学科就叫做数理逻辑。也叫做符号逻辑)。弗雷格第一次用精确的句法构造出形式化的人工语言,使得逻辑推理表示为机械演算即所谓的推理规则成为可能。从这个观点看,概念文字是我们今天使用的计算机程序设计语言的前身。

弗雷格希望可以自然数提出一种纯粹逻辑的理论,从而证明算术,微积分乃至一切数学都可以看成逻辑的一个分支。于是弗雷格便希望可以用纯逻辑的术语来定义自然数,然后再用他的逻辑导出它们的性质。例如3这个数将被解释为逻辑的一部分。弗雷格的思想是把3定义为所有元素数为3的集合的集合。实际上这就是《算术的基础–对数概念的逻辑数学研究》这部著作的主要内容。

然而正是这样的一些工作,1902年,年轻的伯特兰.罗素据此提出那个著名的罗素悖论。弗雷格的算术使用了集合的集合这样一种概念。罗素指出,用集合的集合进行推理很容易导致矛盾。罗素的悖论可以这样描述:如果一个集合是它自身的一个成员,那么就把集合成为异常的,否则它就是正常的。那么由所有正常集合组成的集合是正常还是异常的呢?

如果是正常的,那么它应该包含自身,这样它就应该是异常的。如果是异常的,那么它就不会包含自身,这样它就应该是正常的。无论哪个结果都导致了矛盾。实际上罗素构造这个悖论的方法,与之后哥德尔,图灵构造不可判定命题却有着神似的地方。然而这一矛盾却表明弗雷格构造的算术体系所基于的那些前提是靠不住的,并给弗雷格带来了巨大的打击。

虽然弗雷格的逻辑已经很完备,但仍然具有一些局限性。他的规则并没有提供判定某个结论能否从给定的前提中推导出来的计算步骤。另外能否找到一种计算方法,它能够说明在弗雷格的逻辑中某一推理是正确的呢?其结果是这样一则证明:没有这样的一般方法存在。然而正是在证明这样一条否定性的结论过程中,阿兰图灵发现原则上可以设计出一种通用机,它可以执行任何可能的计算。

弗雷格的研究开启语言哲学的大门,后来人们在寻找证明逻辑推理正确性的过程中,图灵发现了通用机,也就是今天计算机的数学模型。

康托尔,对无限的探索

康托尔进入无限的世界,开始无限的数目的研究。他发现自然数与实数具有不同的基数,以及由此提出的连续统假设,即实数和自然数之间不存在具有其他基数的集合。这也是1900年,希尔伯特提出的23个问题中的第一问题。这个问题直到今天并未完全解决,1938年哥德尔和1963年保罗科恩的重大发现表明,如果连续统假设问题可以被解决,就必须超越普通数学的方法。

对于我们普通人来说,最有用的大概是康托尔在证明实数与自然数基数不同的过程中所采用的对角线方法,这种方法是1891年,康托尔在一篇4页的论文中发表的。而对角线方法,在以后的故事中仍然会被用到,它将会被哥德尔用来解决一致性问题时构造系统内不可证命题,然后阿兰.图灵又再次使用了哥德尔的方法构造出了不可判定命题。而关于连续统假设的研究也引发了关于图灵机的构想。现在我们可以看到康托尔的工作与计算机的起源在这里产生了联系。

关于对角线方法,我们从自然数集来看,我们可以发现自然数与自然数的子集组成的集合之间具有不同的基数,假设我们把自然数与不同的自然数子集建立一个对应关系,1: M1 2: M2….,采用对角线方法,我们总是可以构造出一个新的自然数集,它没有任何自然数与之对应,我们这样产生这个新的自然数集:如果i属于Mi,那么排除i,否则包含i,容易看到这样产生的一个集合不同于任何的Mi。可见由一切自然数集组成的集合的基数要大于自然数的基数。

实际上康托尔并不是第一个关注到无限的数目特殊性的人,早在17世纪,莱布尼茨就发现偶数和自然数是一一对应的,正如他所说:对于任何一个数,都存在一个与之对应的偶数,那就是它的二倍。因此所有数的数目并不比偶数的数目更多,也就是说整体没有部分大。但是他得出了这样一个结论:所有自然数的数目这一概念是不一致的,讨论一个无限集中元素的数目是没有意义的。但是康托了选择了另一条路,他承认某些无限集将与它的一个子集具有相同的元素数目。正是基于这样一个大胆的选择,他才创立了关于无限的新理论。

当康托尔提出这些观点之后,立刻引来了各方面的责难。与弗雷格类似,人们发现用康托尔的超限数进行不加限制的推理会导致荒谬的结果。比如如果存在一个由所有基数组成的集合,那么它的基数该是多少呢?它必须比所有基数都大,但 一个基数又怎么可能比所有基数都大呢?后来罗素又指出这样的一个问题:是否存在一个所有集合的集合?如果存在,那么倘若把对角线方法应用于它,会出现什么结果?这样我们会得到一个不同于所有那些已经拥有标签的集合的集合。正是在考虑这种情况时,罗素发现他那个关于由一切不是自身的集合组成的集合的著名悖论,也就是他向弗雷格传达的那个悖论。这里我们看到,弗雷格和康托尔之间被罗素悖论联系起来。而关于这个悖论的讨论和思考,则引发了数学史上的第三次危机。

大卫 希尔伯特

希尔伯特是20世纪的数学领袖,1900年他在数学家大会上指出的23个问题,其中第二个便是关于算术一致性的问题。即關於一個公理系統相容性的問題,也就是判定一個公理系統內的所命題是彼此相容無矛盾的,希爾伯特希望能以嚴謹的方式來證明任意公理系統內命題的相容性。

希尔伯特纲领所提出的主要问题就是算术一致性问题。为了解决这个问题,希尔伯特发展出了元数学,一致性证明将在元数学内部完成。1928年,希尔伯特和他的学生阿克曼出版了一本逻辑课本,书中提出了关于弗雷格<<概念文字>>的基本逻辑(后来被称为一阶逻辑)两个主要问题,一个就是,证明一阶逻辑的完备性,即任何一个从外部看来有效的公式都可以只用课本里提出规则从系统内部导出。第二个问题以希尔伯特的判定问题而闻名,即对于一个一阶逻辑的公式,如果找到一种方法,可以在定义明确有限步骤内判定这个公式是有效的。这两个问题分别为哥德尔和图灵解决,而在解决第二个问题的过程中,图灵提出了图灵机的概念。

后来在1928年的国际数学家大会上,希尔伯特又提出一个关于形式系统的问题,这个系统建立在把一阶逻辑应用于现在被称为皮亚诺算术或者PA的自然数公理系统的基础之上。希尔伯特希望可以证明PA是完备的,也就是说任何一个可以在PA中表出的命题或者可以在PA中被证明为真,或者可以被证明为假。两年后,这个问题被一个叫哥德尔的年轻人解决了,但答案却完全不像希尔伯特料想的那样。

You Might Also Like