最新帖子 精华区 社区服务 会员列表 统计排行
  • 577阅读
  • 0回复

无穷大能比大小吗?

楼层直达
级别: 论坛版主

2016-12-21 算法与数学之美
作者:应行仁

无穷,超越了人类直观想象的极限。从几千年前的哲人开始,悖论敲打着理性的头脑。研究实用学问的人都小心翼翼地绕开,直到牛顿以物理的脚步跨越了冥想中阿基里斯无法迈过的间隙。在微积分打开的灿烂世界里,数学家仍然忧心忡忡地观察牛顿闭着眼睛跨过的间隙,企图在这不可知的深渊上架起一座桥梁。这最根本的基石落在了集合论上。


无穷大指比任何自然数都要大的量,要了解这个量是怎么来的,就要从集合谈起。集合论是现代数学的基础。无穷集合的处理决定了极限、测度、分析、概率、几何,这些严谨理论的理解。学理工很多人接触过无穷集合的概念,也许知道些背后的公理,只是一般的课程都语焉不详,网上文章抄来抄去,在表面字义上引申发挥。其实这些知识并不深奥,与其雾里看花,不如花一点时间在逻辑上弄懂。这篇普及文只假定你有简单的集合概念【1】,除此不需要其他预备知识,按照纯数学教科书证明的思路,加上点形象的说法,让你很快了解这里的概念,从逻辑上想通之间的关系。要想有收获,下面内容要在头脑用逻辑里过一遍。

有限集合和自然数集合的元素,都是可以被逐个数到的。如果一个集合里的元素都能够按某种次序数到,在数学上称为“可数的”(Countable),这集合便称为“可数集”或“可列集”。 整数是可数的,因为从0开始,依1、-1、2、-2、3、-3…,一正一负地走远,任何整数都能按这规则被数到。偶数可以用同样方法数过,它也是可数的。轮流对两个集合上元素依序点数走遍全体,说明了可数集的并集也是可数的。这个通俗化的语言定义中有个关键词“被数到”,就是说集合中任何一个具体的元素,都会按这规则对应着一个有限的序数。

由集合可以定义一个数,称为集合的“基数”或者“势”(Cardinal number),集合A的势记为|A|。有限集合的势是集合中元素的数量,是个正整数。自然数集合N有无穷多个元素,数量是无穷大,它的势记为ℵ0(这个希伯来字母ℵ念作“阿列夫”),|N|=ℵ0。空集的势是0, |ϕ| =0。

势能比较吗?康托尔(Cantor)提出个一一对应的办法。如果两个集合的元素存在着一个一一对应的关系【2】,即如果按照某种规则,一个集合中任何一个元素都能在另一集合中找到唯一的一个元素与之相应,反过来也一样,则说这它们的势相等。如果集合A对集合B有这样的对应规则,则集合B的势可能比A大,记为|B|≥|A|;但反过来时却没有这样对应规则的,则说集合B的势比A大,记为|B|>|A|,俗称集合B比A多。例如:每个公民有张身份证,公民的集合和身份证的集合等势;5个苹果的集合比红、黄、绿3种颜色的集合势大;网上马甲集合的势比博主集合的势大;ℵ0 > n,n是任何自然数。不难证明势的大小关系“≥”和“>”如同自然数的大小一样,具有反对称性和传递性;“≥”还有返身性。

在可数集的定义中,集合的元素被逐个数到的办法,就是它与自然数一一对应的映射,所以可数集的势都是一样的,与自然数等势,为ℵ0. 我们知道偶数只是整数的一部分,自然数也只是整数的一部分,它们都是可数集,势相等。这是无穷集合的一个反直觉的性质:局部可以和全体一样多!所以,涉及到无穷时必须很小心,直觉不可靠,只能凭借于逻辑了。

有理数也是可数的。将不可通约的正的真分数,按照分母和分子从小到大排列如下:

1/2,1/3,2/3,1/4,3/4,1/5,2/5,3/5,4/5,1/6,5/6,1/7,2/7,……

这样它们任何一个都能无一遗漏地被数到,即正真分数是可数的。所有大于1的分数都是正真分数的倒数,这倒数一一对应说明了它们等势,都是可数的。有理数是这两者的并集,再加上0和1。前面说过,可数集的并也是可数的,这就证明了,有理数集合Q也是可数的,|Q|=ℵ0。

无穷集合都是可数的吗?不,实数就不是。这个证明如下:

假如(0,1)区间的实数也是可数的,那么这里任何一个实数对应着一个自然数n,排成一个序列,表中第n个实数就可以表示为F(n)=0.a(n,1)a(n,2)a(n,3)...,这里a(n,k)是序列中F(n)的第k位小数的数字。现在定义一个新的实数b=0.b(1)b(2)b(3)...,其中的b(k)=7如果 a(k,k)=5,否则 b(k)=5。因为b的每一位小数都和顺序表中任何一个实数不一样,这个b不可能在这表中。但顺序表假定是列出了所有(0,1)区间的实数。这个矛盾证明了实数是不可数的。

这是康托尔在1891年的证明用的“对角线法”技巧,其逻辑精彩绝纶,自此以后它的思想被大家借用,解决了一些难题。哥德尔的不完备性定理,其关键部分也是用了对角线法的思想。如果你还一下子转不过来,我再举例说明这个精妙的思想。

如果小于1的正实数是可数的,它可以按某种次序列表出来,比如说这次序表的前6个如下:

F(1)=0.3132789…

F(2)=0.5674321…

F(3)=0.3355212…

F(4)=0.9823133…

F(5)=0.0042523…

F(6)=0.3214563…

……

为了醒目,我将其中的对角线元素a(k,k)用黑体字表示。现在新造出一个实数b来,这个b的第k位小数,是根据顺序表中,第k个实数的第k位的数值(这对角线上的黑体数字)而定,按照上面说的规则构造出的实数是b=0.557575…

这个数b不可能在这顺序表中,因为它如果是表中第n个实数,b=F(n),那它们的第n位小数不相等a(n,n)≠b(n),这是构造b时挖的坑,矛盾了。也就是说实数不是可数的。自然数是实数的一部分,所以实数的势比自然数和有理数大。称为不可数集。实数R的势,称为连续统的势,记为c,|R|=c >ℵ0.

有理数和无理数的并集是实数,有理数是可数的,实数是不可数的,所以无理数也是不可数的。无理数比有理数多,而且“多得多”!

能够成为整系数代数方程根的实数称为代数数,不是代数数的实数称为超越数。当人们正在讨论是否存在超越数时,康托尔手里还没有一个超越数,通过证明代数数是可数的,他就敢断言超越数不仅存在而且是不可数的多。

这集合的势有没有上限?康托尔说没有。把集合A的所有子集看成一个新的集合,记为2A,康托尔以构造罗素悖论的相同思路,用反证法证明了|2A |>|A|,这称为Cantor’s theorem。集合A的所有子集的势也可以记为2|A| =|2A |,当A是有限集合时,不难验证这个整数意义下的等式成立。

实数可以用0和1来表示,每一个实数中的数字为1的位数集合,比如说10.101,一一对应着整数的一个子集,例如是{2,-1,-3},也就是实数与可数集上所有子集集合的势相等,c=2ℵ0。

所有集合的势都可以比较吗?对有限集合肯定没问题,无穷集合中的可数集,实数集,集合和它子集的集合,上面都给出了肯定的答案。其他的无穷集的势呢?它们也是无穷大,既然有不同的无穷大,它们都能比较吗?用数学的术语来说是:集合势的大小关系是良序的吗?这个问题在朴素集合论中不能回答,也不能在ZF公理系统【3】中得到答案,人们在ZF中增加了一条公理叫选择公理CH,它与良序性等价。有了它所有的集合势就都可以比较了。

接下去第二个问题,到底有没有集合的势在c 和 ℵ0之间?康托尔认为没有,这称为连续统假设CH。【4】更强的广义连续统假设GCH是说在|2A |和|A|之间不存在着其他的势。哥德尔在1940年证明了这个假设与集合论ZFC公理下是不矛盾的,科恩在1963年证明了它们是独立的。至今这个问题仍被人们讨论。【4】

至此,无穷大的比较问题似乎已经有了清楚的答案,虽然在公理的依据上有些争论。这是主流数学家对这个问题的答案,在这个基础上建立起了现代数学的大厦。

上述无穷大的反直觉的性质,让一些喜欢直觉的人很不舒服。他们认为无穷集合不能像有限的那样,可以逐个检查验证,上面结果的几个关键证明,都是采用反证法的思辨。荷兰数学家布劳威尔认为经典逻辑是从有限集合的数学抽象出来,没有理由运用到无穷集合中。1908年,他反对把排中律运用于无穷集合上,也就是说在无穷情况下,不能用反证法。抽去了反证法这个支柱,这个无穷集合势的大厦轰然崩溃。现代数学的大部分结果都要重新考证。他认为除了可数集合之外,没有其他无穷集合,数学无穷集合只有一个势,即可数无穷。只有一种无穷大!

康托尔几乎凭借着一己之力掀起思想革命,提供了平定数学界混乱的基础,当时的数学领袖希尔伯特信心满满地带领大家在上面建造新的大厦,布劳威尔的宣言几乎是破坏这安定团结的反动,将数学带回这革命前的混乱,希尔伯特终于忍无可忍地回应:“把排中律排除在数学之外,就像禁止拳手使用拳头。”布劳威尔激进的性格终于使得这矛盾不可协调,被排斥出主流数学界。

布劳威尔是数学直觉主义的创始人,坚持所有数学对象必须是可以构造的,不能用排中律。上世纪三十年代初,由于哥德尔的工作,一些数学家开始重视直觉主义,但与主流数学的汪洋大海相比,直觉主义与后来比较温和的构造主义取得的成果就非常有限了。最令人尴尬的是,布劳威尔一生最伟大的成就——布劳威尔不动点定理,却是用自己所极力反对的,非构造性的方法来证明的。

我们在这里看到数学的矛盾和争论,看到反复斟酌的公理。有人疑惑到底这些公理对不对?到底是信仰还是事实,在矛盾之中,哪个是真理?这是对数学不理解了,数学的研究是从一些非常基本的假设中,应用逻辑来看能够走多远,能够得到什么有用的结论。这些假设只要是自洽的,无关对错,只关是否有用,能否在应用时被接受。构成数学体系称为公理的假设,很多是非常基本近乎定义性的同语反复。还有一些公理被引入,是为了修补支撑已在实践中被广泛应用的数学结果和工具。被排斥的一些公理,不是因为错了,而是假设太强了,在这假设下得不到足够广泛有用的结果。

喜欢数学对一些基础问题感兴趣的朋友,建议花点时间学习“点集拓扑”,即使是只学一两章也可以受益无穷,上述关于无穷集合的内容,只占General Topology【5】,第一章的中间部分,不到几页的内容,除了逻辑的头脑,几乎不需要其他基础。现代的分析数学是建立在在点集之上,由子集定义开集,用开集构造拓扑空间,引进邻域,在此定义收敛,连续,紧,距离,连通性,各种空间。数学系统所的程代展和我都曾经在国内修过分析和泛函,到美国第一年学了两个学期的拓扑,像中学生一样一道道题做,把各块石头都摸过,这让我们对数学有种脱胎换骨的感觉。在这个基础上重学了测度、随机过程、微分几何才觉得脚下是坚实的基础,一切概念和原理都可以回溯追问到集合的公理为止。这时候才感到:数学,不是教你怎么计算的,而是怎么引进假设,合乎逻辑地思考。

【参考资料】

【1】维基百科,集合     http://zh.wikipedia.org/wiki/%E9%9B%86%E5%90%88_(%E6%95%B0%E5%AD%A6)

【2】百度百科,映射http://baike.baidu.com/view/21249.htm

【3】Wiki, Zermelo–Fraenkel set theoryhttp://en.wikipedia.org/wiki/Zermelo%E2%80%93Fraenkel_set_theory

【4】Wiki, Continuum hypothesis http://en.wikipedia.org/wiki/Continuum_hypothesis

【5】Stephen Willard,General Topology, Addison-Wesley(1970)

快速回复

限200 字节
 
认证码:
上一个 下一个