《什么是数学》读书笔记(二·上):从自然数到实数

    今天,我们将从一系列公理开始,从自然数的产生一直说到实数理论的完善。你或许会对数学的“科学性”有一个新的认识。注意,本文的很大一部分内容并非直接来源《什么是数学》,这篇文章可以看作是《什么是数学》中有关章节的一个扩展。

    自然数是数学界中最自然的数,它用来描述物体的个数,再抽象一些就是集合的元素个数。在人类文明的最早期,人们就已经很自然地用到了自然数。可以说,自然数是天然产生的,其余的一切都是从自然数出发慢慢扩展演变出来的。数学家Kronecker曾说过,上帝创造了自然数,其余的一切皆是人的劳作。 (God made the natural numbers; all else is the work of man.)
    随着一些数学理论的发展,我们迫切地希望对自然数本身有一个数学描述。从逻辑上看,到底什么是自然数呢?历史上对自然数的数学描述有过很多的尝试。数学家Giuseppe Peano提出了一系列用于构造自然数算术体系的公理,称为Peano公理。Peano公理认为,自然数是一堆满足以下五个条件的符号:
   1. 0是一个自然数;
   2. 每个自然数a都有一个后继自然数,记作S(a);
   3. 不存在后继为0的自然数;
   4. 不同的自然数有不同的后继。即若a≠b,则S(a)≠S(b);
   5. 如果一个自然数集合S包含0,并且集合中每一个数的后继仍在集合S中,则所有自然数都在集合S中。(这保证了数学归纳法的正确性)

    形象地说,这五条公理规定了自然数是一个以0开头的单向有序链表。
    自然数的加法和乘法可以简单地使用递归的方法来定义,即对任意一个自然数a,有:
a + 0 = a
a + S(b) = S(a+b)
a · 0 = 0
a · S(b) = a + (a·b)

    其它运算可以借助加法和乘法来定义。例如,减法就是加法的逆运算,除法就是乘法的逆运算,“a≤b”的意思就是存在一个自然数c使得a+c=b。交换律、结合率和分配率这几个基本性质也可以从上面的定义出发推导出来。
    Peano公理提出后,多数人认为这足以定义出自然数的运算,但Poincaré等人却开始质疑Peano算术体系的相容性:是否有可能从这些定义出发,经过一系列严格的数学推导,最后得出0=1之类的荒谬结论?如果一系列公理可以推导出两个互相矛盾的命题,我们就说这个公理体系是不相容的。Hilbert的23个问题中的第二个问题就是问,能否证明Peano算术体系是相容的。这个问题至今仍有争议。

Read more…

100囚犯问题、100囚犯问题加强版与选择公理(下)

    无穷个囚犯面向数轴的正方向依次就座,第i个囚犯坐在数轴上坐标为i的地方,他可以看见所有坐标大于i的囚犯头顶上的帽子。看守给每个囚犯戴上黑色或白色的帽子,然后依次叫每个囚犯猜测自己头上的帽子颜色,猜对了的予以释放。另外一点和原来不同的是,囚犯们不能听到其他人的猜测。另外注意到,由于每个人前面都有无穷多个人,因此囚犯们无法通过数他前面的人数来判断出自己的位置,于是我们不得不加上一句:每个人都知道他后面有多少人(即他是第几个被问的)。同样地,事先所有囚犯可以商量出一个策略。你认为这下囚犯们还有什么好办法没?
    这下囚犯已经不能通过自己的猜测来通风报信了,似乎每个人都只能瞎猜,任何人都无法保证自己能猜对。你相信吗,居然有这样的策略,它可以保证除了有限个囚犯之外,其他囚犯全部释放!
    考虑所有可能的颜色序列(你可以简单地想像成01串)。我们说两个颜色序列“无穷远相等”,如果经过了有限多项之后,余下的无穷多项完全相同(即存在某个数x,使得两个串在各自的第x位后面完全重合)。这种关系显然满足自反性、对称性和传递性,是一种等价关系。因此,按照这种有限位后对应相等的关系,我们可以把所有可能的颜色序列划分为一个个等价类。它们的交集为空(两个等价类如果有交集,由传递性它们立即并成了一个更大的等价类),并集为全集(若某序列不属于任何等价类,则它自己就是一个新的等价类),是全集的一个划分。你能想象出一个等价类大致是什么样子的吗?假如把同一个等价类里的所有序列对齐并排放在一起,你从前往后走过去的时候会发现这些序列“越来越相像”。你走得越远,你会发现越来越多的序列开始变得互相重合;当你走到无穷远时,所有的序列都变成一个样了。
    囚犯们事先在每一个等价类中选一个代表元,然后把所有等价类的代表元背下来。到时候,每个人都能够看到他前面无穷多个人的帽子颜色,并且知道他自己在整个序列的位置,于是能立即判断出他们现在所处的颜色序列在哪个等价类里。接下来,他们只需要按照事先背好的代表元来猜就行了。由“无穷远相等”的定义,经过有限次猜测后最终这个代表元会和他们所处的序列重合,于是除了前面有限多个人以外,以后无穷多个人都可以保证猜对。

    你是否觉得这种“策略”很不合理,虽然从逻辑上看每一步推理都是无懈可击的?有人认为,这是选择公理带来的悖论。选择公理是说,给你一系列的集合(可能有无穷多个),那么我们总可以在每一个集合里取出一个元素来。这并不是显然正确的。你不可以依次考虑每个集合,从里面随便取出一个元素来,因为集合个数有可能无穷多个(甚至不可数),这样的操作将永无止境,不允许出现在数学推理过程中。我们需要定义一套系统,使得它对于给定的每一个集合都适用,这样我们就可以“一下子”处理完所有的集合。换句话说,对于一组数量任意多的集合,我们需要定义一个函数f,使得对其中任一集合S,f(S)为S里的一个元素。我们称函数f为选择函数。例如,给出自然数集的所有子集,选择函数f可以定义为“集合中的最小元素”;给出实数集的所有有限长的区间,则选择函数f可以定义为“区间的中点”。但对于某些情况,目前还没有办法用之前已有的公理系统定义出合适的选择函数。比如,目前仍然不清楚,对于实数集的所有非空子集是否存在一个选择函数。但选择函数的存在是很多数学推理的前提假设。因此,我们有必要承认选择公理,构成新的公理体系(即ZFC公理体系)。于是在今后的数学推理中,我们可以假设存在这样一个超级选择函数f,它就是专门用来干这破事的。承认选择公理有可能推出一些与生活经验背道而驰的结论,最著名的就是Banach-Tarski悖论:你可以把一个三维球体分成有限多块,然后拼接组合成两个和原来一样大的球体。上面所提到的100囚犯问题加强版则是选择公理带来的另一个悖论。

参考资料:http://cornellmath.wordpress.com/2007/09/13/the-axiom-of-choice-is-wrong (墙就是强)