计数

摘自《数学简单与高深》席南华 著 [P136]

数字的出现无疑与计数有关。计数有时很简单，比如集合{甲，乙，丙}含有三个元素，n个数1，2，…，n的排列数是n的阶乘，有时很不容易，如一个国家的人口数很难得到准确的值。计数是数学分支组合学研究的问题。不管怎么说，对有限集，理论上计数是件简单的事情，一个一个数就行了。但无限集事情就比较麻烦，比如有理数和无理数谁多呢？如果你有一个面积无限的王国，增加或损失几百万平方千米的国土对你都无所谓。

或许你们读过伽莫夫的科普作品《从一到无穷大》，从中可以知道如果一个旅店有无穷多的客房，哪怕住满了客人，仍能安排一个新来的客人：把原来住1号房的客人换到2号房，住2号房的客人换到3号房，…，这样1号房就可以空出来给新来的客人住了。如果一个旅店的客房数有限，这样的事情就办不到了。这些事实表明有限的世界和无限的世界有本质的不同。

怎样比较无限的集合呢？我们不能像有限集那样斤斤计较多一个元素少一个元素，那不是无限的本质。德国数学家康托尔（Cantor）找到了比较无限集大小的办法，建立了集合论。

康托尔利用映射来比较集合的多少，这个办法对有限集和无限集都管用。康托尔利用一一映射建立了等势的概念。一个集合A到集合B的映射称为一一映射如果它把不同的元素映到不同的元素，并且B里面每个元素都有A里的元素映过来。两个集合称为等势如果它们之间有一一映射。两个有限集等势的充要条件是它们所含的元素个数一样。

对无限集，等势是个有趣的概念，准确把握了无限的本质，忽略了次要的因素。

等势的集合只是表明两者势力相当，犹如兵来将挡，水来土掩，不表明两者有一样多的元素。实际上一个无限集合可以和它的子集等势，如整数集和自然数集等势，它们之间的一一映射可以构造如下：0映到0，负整数a映到正奇数2|a|-1，正整数a映到正偶数2a。和自然数或它的子集等势的集合称为可数集。这是一个容易理解的概念。下面很有意思的结果是康托尔证明的。

定理2（康托尔，1874）（1）有理数集合是可数集。

─

（2）有理数域的代数闭包Q是可数集。

（3）实数集不是可数集。

1877年，在一封给戴德金（Dedekind）的信中康托尔还证明了单位线段中的点集和n维空间的所有点集等势，特别实数和复数等势。

我们来看一下这个定理的一些含义。有理数显然比自然数多得多，但居然是可数的，数的时候要小心，不然会数得乱糟糟的。下面给出一种数的办法。

每个非零有理数都可以写成两个整数a和b的商a/b，其中a和b没有大于1的公因子。于是有理数可以先按a和b的绝对值的和的大小分成若干部分排序，每一部分再数，所以一种数法是

0，1，-1，1/2，2，-1/2，-2，1/3，3，-1/3，-3，

1/4，2/3，3/2，4，-1/4，-2/3，-3/2，-4，…。

─

有理数的代数闭包Q中的数无疑比有理数多得多，居然也是可数的，这很容易让人感到惊讶。想想看，对每一个正的有理数a，都能通过开方衍生出无限个无理数，即无穷数列

1 1 1

α，α ─，α ─，…，α ─，…

2 3 n

中除有限个外都是无理数，一个结论就是现实世界中的“无理”和“不公平”的事情总比“有理”和“公平”的事情多。

一个复数称为代数数如果它是某个整系数的一元多项式的根，否则称为超越数。断言某个数是超越数远非易事，实际上，直到1844年才由刘维尔证明了超越数的存在性，1851年他给出首批超越数，其中一个是

∞

∑10⁻ᵏ！。

ₖ₌₁

最重要的超越数可能是圆周率Π和欧拉数

∞ 1

e＝∑ ─，

ₖ₌₁ k！

Π的超越性由林德曼（Lindeman）于1882年证明，e的超越性由埃尔米特（Hermite）于1873年证明。

定理2的（2）和（3）表明超越数不仅存在，而且比代数数多得多，不在一个量级上，虽然这个定理没有指出一个超越数。这很有意思，它显示了等势这个概念的威力，告诉我们恰当的概念能深刻揭示事情的本质，引导我们前行。

康托尔建立的集合论已成为现代数学的基础。德国人在19世纪和20世纪初为数学和物理学作出巨大的贡献，在概念和思维方式上都有很多的突破。可能德国发达深刻的哲学起了很大的作用，有时间看一看莱布尼茨、康德等人的哲学著作是很有益处的。

定理2引出一个很自然数的问题：在自然数全体和实数全体中间，有没有一个集合，它既不可数（即不与自然数集等势），也不与实数集等势。1878年康托尔提出了连续统假设：这样的集合不存在，也就是说，不存在一个，它的势比自然数集的势大，但比实数集的势小，犹如在1和2之间不存在整数。存在或不存在之类的问题对数学而言常常是很重要的，虽然可能不会像莎士比亚的戏剧“哈姆雷特”中的“活还是不活”（to be or not to be）那么重要。

连续统假设是那么自然的一个问题，很能吸引我们的好奇心。1900年，在巴黎举行的国际数学家大会上，希尔伯特提出了著名的23个未解决的数学问题，连续统假设排在第一个。

哥德尔（Godel），伟大的奥地利数理逻辑学家，在1940年证明了连续统假设与我们平常的公理体系是没有矛盾的，即连续统假设与策梅洛（Zermelo）-弗伦克尔（Fraenke）集合论无矛盾。没有矛盾，并不意味着它是对的。1963年科恩（Cohen）建立了强有力的方法——力迫法，用这个方法他证明了连续统假设之否与我们平常用的公理体系也是没有矛盾的，即连续统假设之否与策梅洛-弗伦克尔集合论无矛盾。也就是说在我们常用的公理系统中，加入这个假设不会产生矛盾；加入这个假设之否，也不会产生矛盾。这显然出乎常人的意料，一个重要而又自然的问题，竟在我们常用的公理体系里没法断定真假，就像我们生活里听到的一句话：说你行也行，说你不行也行。

看上去，连续统假设似乎已经弄明白了，但其实对这个问题的思考一直在延续，产生很多深刻的数学。乌丁（Woodin）的工作表明连续统假设是错的也许更合理，当然这里面有很多的条件，这些条件说出来就过于专业了，这里就不说了。我们可以把连续统假设和平面几何的平行公理比较，对平行公理的思索和研究导致了双曲几何等非欧几何的产生，黎曼几何是非欧几何的一种，是广义相对论的数学框架，所以对简单的好问题的不断思索常常给我们带来很深刻的数学新天地。

科恩因在连续统假设上的工作获得1966年的菲尔兹奖。他原来是分析数学的专家，在其中做出过重要贡献，于1964年获分析数学中的博谢（Bocher）奖。有一个传言说科恩在完成了对连续统假设的工作后觉得数学中的问题只有黎曼假设值得他去研究，有点像我国古诗“曾经沧海难为水”所描述的那样。

哥德尔对数理逻辑的贡献巨大。逻辑推理是数学的一个基础工具，在古代是作为哲学的一部分，对形式逻辑的系统研究应该始于古希腊的亚里士多德，欧几里得的《几何原本》是使用形式逻辑组织数学理论的典范。从古到今，哲学家和数学家一直在探索逻辑的本质和它的方方面面，有很多人的工作非常杰出，如莱布尼茨、弗雷格（Frege）、罗素等等。莱布尼茨可能还是迄今为止最出色的符号大师，他引进的很多特别好的符号，如微分符号dy，dx等。对数学来说，引进恰当的符号是很重要的，符号是表示内容的一种形式，形式要为内容服务，所以必须与内容相符。如果你没有很好的形式的话，很多内容是没办法恰当地表示出来的。很多时候你不要忽略形式的价值。

我们一般都相信在数学中一个陈述的真假性一定可以被证明，对逻辑本身充满了信心，君不见对说明事情的明确性常有这样的表达“逻辑上无懈可击”。但逻辑本身远非像常人所想的那样简单和无往不利，有时让人感到太不踏实，前面连续统假设的研究就是一个例子，其实在此之前哥德尔的两个不完备性定理给数学基础带来巨大的危机，宣告了弗雷格、罗素、希尔伯特等人寻找对数学足够用的公理系统的努力是不会成功的，尽管希尔伯特曾经非常乐观地认为“我们必须知道，我们将会知道”（“Wir mussen wissen，Wir werden wissen”，1930）。哥德尔地两个不完备性定理可以表述如下：

定理3（哥德尔，1931）一个无矛盾地公理化理论如果包含算术公理体系，那么在这个理论中存在一个陈述句，其真假不能在这个理论中判断。

定理4（哥德尔，1931）一个公理化理论如果包含算术公理系统，当它无矛盾时，其无矛盾性不能由这个理论自身证明。

这两个定理和我们生活中的一些感受十分类似，有些事情没法说清真假（法庭上这类事情最好少发生），一个人常常无法自证清白，需要他人的帮助才行。哥德尔的不完备性定理和其他工作不仅在数学上产生巨大的影响，在哲学上亦是如此。一本有名的书《GEB——一条永恒的金带》给人们展示了不完备定理、埃舍尔的绘画、巴赫音乐的之间的奇妙联系。

不完备定理还提示我们，人类认识的能力可以走到哪里在逻辑上很难找到一个确切的答案，但对这个问题的探讨，会帮助我们更进一步认知我们的逻辑能到达的范围。数理逻辑与计算机科学有密切的关系。理论计算机科学最有名的一个问题就是P和NP问题，这个问题是克雷数学研究所的千禧年问题之一，谁能解决这个问题就能从那儿获得一百万美元的奖金。这个问题的表述有多种，最容易明白的可能是下面这个。

P和NP 设A是有限集，由一些整数组成，用Sᴀ表A中所有数的和。问题：能否找到多项式时间的算法以确定是否存在A的子集B使得Sʙ=0。

到目前数学家的理论计算机专家对这个问题还没什么办法，一部分专家倾向于答案是肯定的，更多的专家倾向于答案是否定的，还有一部分专家倾向于这个可能在现有的框架下是无法确定对与错的，犹如连续统假设一样。如果P和NP的答案是肯定的，那表明世界上现在用的密码绝大多数在理论上是容易破解的，这对很多行业如通信、银行等来讲是个灾难。

数学联邦政治世界观提示您：看后求收藏（笔尖小说网http://www.bjxsw.cc），接着再看更方便。