你认为，是否有可能把全体正整数染成红蓝二色，使得不存在无穷等差数列，数列中的所有数都是一种颜色？如果你认为存在这样的染色方案，请给出一个构造方法；如果你认为不存在，证明之。在看下面的答案之前，不妨先仔细思考一下。

    事实上，满足题意的染色方案是存在的，构造方法非常简单，非常直接，非常暴力。显然，无穷等差数列只有可数个，不妨把它们分别叫做A_1, A_2, A_3, ...。现在，如果我们能够构造两个数列r_1, r_2, r_3, ...和b_1, b_2, b_3...，使得对于每一个i，r_i和b_i都在数列A_i中，并且r数列中的每个数都和b数列中的所有数都不相同。这样，把r数列中的所有数染成红色，把b数列中的所有数染成蓝色（其它未出现的数随意染色），就能保证每个无穷等差数列都包含了至少两种颜色。
    而这样的r数列和b数列显然存在，因为每一次选择新的r_i和b_i时，无穷数列A_i中都只有有限个数不能选，因此r_i和b_i永远都有选的。

    Update: 地基层网友给出了一个更巧妙、更简单的构造方法：对全体正整数倍长间隔染色，即把1染成红色，2和3染成蓝色，4到7染成红色，8到15染成蓝色……。显然，当染色区间的长度大于公差时，等差数列最终都将一截一截地落在不同的染色区间中。

查看更多 »

    去年就看过Proofs from THE BOOK第一章中的素数无穷多的拓扑学证明，不过当时似乎并没有看懂。今天看到cut-the-knot的一篇新文章，又把Proofs from THE BOOK拿出来翻了一下，终于看明白了，果然是一个令人拍案叫绝的经典证明，可谓又一神来之笔。

    定义N(a,b) = {a + nb| n∈Z}，例如N(1,3)就等于{..., -5, -2, 1, 4, 7, ...}。每一个N(a,b)实质上都是一个以b为公差的“双向无限等差数列”。我们说整数集Z上的一个子集S是开的，如果集合S为空，或者对于任意一个a∈S，总能找到一个b>0使得N(a,b)⊆S。形象地说，开集的意思就是，集合中的每一个元素都能在集合内扩展出一个无限长的双向等差数列。我们又称一个集合S是闭的，如果它是某个开集的补集。
    显然，有限个开集的并集仍然是开集。
    假设S_1和S_2都是开集，如果a∈S_1∩S_2，并且N(a,b1)⊆S_1，N(a,b2)⊆S_2，那么S_1∩S_2中有一个公差为b1*b2的含a的双向无限等差数列，也即a∈N(a, b1*b2)⊆S_1∩S_2。这说明，有限个开集的交集仍然是开集。
    再假设C_1和C_2都是闭集。由De Morgan定律，C_1和C_2的并集就相等于它们各自的补集相交后再取补集，由定义可知它们的补集都是开集，而由上面的结论可知开集的交集仍是开集。于是，C_1和C_2的并集是某个开集的补集，这说明闭集的并仍然是闭集。类似地，闭集的交集相当于补集的并集的补集，它也仍然是闭的。

    还有两点值得引起我们注意：
    1. 任意非空开集都是无穷的。这由定义可以直接看出来。
    2. 任一双向无限等差数列N(a,b)既是开集又是闭集。由定义可知N(a,b)是开集，而同时N(a,b)又可以看作是N(a+1,b)∪N(a+2,b)∪N(a+3,b)∪...∪N(a+b-1,b)的补集，这是有限个开集的并集的补集，说明N(a,b)也是闭集。

查看更多 »

    对于数轴上的一个点集，如果说在集合中任意两点之间都能够找到该集合中的另一个点，我们就说该点集处处稠密。例如，全体有理数集合就是稠密的，任意接近的两个有理数之间都存在其它的有理数（比如它们的算术平均值）。这样看来，两个处处稠密的点集似乎是不能共存的，但实际情况并非如此。我们将会看到越来越牛B的例子，它们将让我们对稠密性有一个全新的认识。

    1. 在数轴上找出两个处处稠密的点集，它们互不相交。
    很简单。全体有理数和全体无理数就是满足条件的两个集合。

 
    2. 在数轴上找出两个处处稠密的不可数点集，它们互不相交。
    很狡猾。集合A取全体正有理数和全体负无理数的并集，集合B取全体正无理数和全体负有理数的并集，这两个集合即可满足条件。

 
    3. 在数轴上找出无穷多个处处稠密的点集，它们两两不相交。
    令P_i表示第i个素数。则集合S_i := { √P_i + r| r为有理数 }满足条件。为了证明它们两两不相交，假设r_1 + √P_m = r_2 + √P_n，于是(r_1 - r_2)^2 = (√P_n - √P_m)^2，可得√P_m * P_n = ( P_m + P_n - ((r_1 - r_2)^2) )/2。两个素数的乘积的平方根是一个有理数，这显然是荒谬的（很多证明根号2是无理数的方法都可以证实这一点，例如这里的证法http://www.matrix67.com/blog/archives/206）。

查看更多 »

    上周六的离散数学课上，我学到了一个比较有趣的东西：有序对的定义。在引入有序对之前，所有的东西都是以集合为基础的；因此当我们讨论到有序对的概念时，我们只能用集合的语言去描述它。如何用集合来叙述有序对<a,b>，使得<a,b>=<c,d>当且仅当a=c且b=d呢？集合本身的无序性给我们带来了相当大的困难。比如，大多数人可能会想到<a,b>:={a,{b}}。可惜这种定义方法是错误的。考虑集合{ {1}, {2} }，则它既可以是<{1},2>，又可以表示<{2},1>。那么定义<a,b>:={a,{b,Ø}}呢？这样也不行，道理是一样的，{{1,Ø}, {2,Ø}}既可能是<{1,Ø},2>，又可能是<{2,Ø},1>。那么，到底应该怎样定义有序对呢？如何定义最简单呢？

查看更多 »

    网友Gestorm在TopLanguage里问到，如何构造一个[0,1]到(0,1)的一一映射。两个集合的势显然相等，它们之间一定有一个一一对应的函数。注意到(0,1)是[0,1]的子集，利用Cantor-Bernstein-Schroeder定理，只要我们能找到一个从[0,1]到(0,1)的单射函数，我们便找到了两个集合间的双射函数（因为上述定理的证明是构造性的）。这非常简单，例如f(x)表示x与0.5的平均数即可。考虑上述定理的Julius König证明，我们立即得到一个[0,1]到(0,1)的一一映射：f(0)=1/4, f(1/4)=3/8, f(3/8)=7/16, ...，不断进行(x+1/2)/2的迭代；同样地，f(1)=3/4, f(3/4)=5/8, f(5/8)=9/16, ...；对于其它所有未定义到的x，f(x)=x。这个函数显然是双射的。
    仔细观察这个函数。当你领会到这个函数的真谛时，你突然恍然大悟：我可以用类似地办法弄出无穷多个[0,1]到(0,1)的一一映射。例如，最简单的便是f(0)=1/2, f(1)=1/3；然后f(1/2)=1/4, f(1/3)=1/5, f(1/4)=1/6, ..., f(1/i)=1/(i+2)；对于其它未定义的x，f(x)=x。
    查看TopLanguage的原帖可以看到一些类似的结果。

    明天考英语，单词还没背。先冒死更新一个^_^
    我们称一个从集合A到集合B的映射是“单射”的，如果A中的任两个相异元素都不会映射到B里的同一个元素。如果一个A→B的映射是单射的，并且B里的所有元素都被射了（满射），那么这个映射就是“双射”的。Cantor-Bernstein-Schroeder定理是说，假如存在一个从集合A到集合B的单射函数f，以及一个从集合B到集合A的单射函数g，那么A与B之间一定存在一个双射函数（即能建立起一一对应的关系，两个集合有相等的势）。这个结论并不是显然的。对于无穷集合，我们可以构造出很多这样的例子，两个映射A→B和B→A都是单射，但都不是满射的。例如，给定一个正方形和正方形外的一条直线，把正方形放到直线上滚一圈所形成的对应关系是一个从正方形上的所有点到直线上的点的一个单射函数，而连接直线上的点和正方形一边中点后与正方形的另一个交点构成了一个从直线到正方形的单射关系（如图）。那么，根据Cantor-Bernstein-Schroeder定理，我们一定可以找到一种函数，使得直线上的所有点和正方形上的所有点有一一对应的关系。

查看更多 »

    无穷个囚犯面向数轴的正方向依次就座，第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 （墙就是强）

    Cantor对集合的一些著名的研究让我们更加清楚地认识了无穷这玩意儿。Cantor发现，无穷集合之间也有大小关系，他把这种大小关系叫做集合的势(cardinality)。正整数和正偶数都有无穷多个，但到底谁要多一些呢？我们认为，正整数和正偶数一样多，因为我们可以在它们之间建立起一一对应的关系（乘2除2），因此有多少个正整数就有多少个正偶数，反过来有多少个正偶数我就能找出多少个正整数。于是我们说，正整数集和正偶数集是等势的。
    再来想一个问题，自然数和所有整数哪个多哪个少？答案还是一样多。重新排列一下所有整数，你会看到自然数和整数之间也有一一对应的关系，它们的个数一样多，两个集合也是等势的：

自然数：0,  1,  2,  3,  4,  5,  6,  7,  8, ...
   整数：0, -1,  1, -2,  2, -3,  3, -4,  4, ...

    Cantor还发现，有理数集与自然数集也是等势的，也就是说有理数和自然数一样多！这个证明方法可谓是数学史上真正的经典：把所有有理数写成最简分数的形式，根据分子和分母的值把它们排列成二维的阵列，然后从1/1出发沿对角线方向蛇形遍历所有的数。第i个遍历到的数与自然数i对应，正有理数集与正整数集也就有了一一对应的关系。注意这里仅仅是正有理数，不过没啥，用刚才证明整数集与自然数集等势的方法，我们也可以把正有理数扩展到全体有理数。
      

    事实上，对于任何一个集合S，如果你能找出一种方法把集合里的所有元素按顺序一个不漏地罗列出来，写成a1, a2, a3, a4, ... 的形式，那么这个集合就是和自然数集等势的，因为序列的下标和自然数集就已经构成了一个一一对应的关系。我们把所有与自然数集等势的集合叫做可数集(countable set)，因为它们是可以数出来的。
    并不是所有集合都是可数的。Cantor证明了，实数区间[0,1]是不可数的集合，它的势比自然数集大。你找不出什么方法能把0到1之间的所有实数一个不漏地排列出来。这个证明方法很巧妙，假设你把实数区间[0,1]里的所有数按照某种顺序排列起来，那么我总能找到至少一个0到1之间的实数不在你的列表里。把你的列表上的数全写成0到1之间的小数：

a1 = 0.0147574628...
a2 = 0.3793817237...
a3 = 0.2323232323...
a4 = 0.0004838211...
a5 = 0.9489129145...
.........

    那么我就构造这么一个小数，小数点后第一位不等于a1的第一位，小数点后第二位不等于a2的第二位，总之小数点后第i位不等于ai的第i位。这个数属于实数区间[0,1]，但它显然不在你的列表里。这样，我就证明了实数区间是不可数的。

    最近，Matthew H. Baker找到了证明实数区间是不可数集的一种新方法。这种方法同原来的方法完全不同。新的证明方法从一个博弈游戏出发，在两个不同的数学领域间建立起了联系，非常具有启发性。
    A和B两个人在实数区间[0,1]上玩一个游戏。首先，A在(0,1)之间选一个数a1，然后B在(a1,1)里选一个数b1；接着，A在(a1,b1)之间选一个数a2，然后B在(a2,b1)里选一个数b2……总之，以后A和B轮流取数，选的那个数必须位于前面两次选的数之间。可以看到，序列a1, a2, a3, ...是一个单增的有界序列，因此游戏无限进行下去，数列{an}最终会收敛到某一个实数c。游戏进行前，A和B约定一个[0,1]的子集S，规定如果最后c∈S，则A胜，否则B胜。
    Baker发现，如果S集为可数集的话，B肯定有必胜策略。如果S集可数，那么B就可以把S集里的数排列成一个序列s1, s2, s3, ... 。B的目标就是让序列{an}的极限不等于S集里的任一个数。考虑B的这样一个游戏策略：当B第i次选数时，如果选si合法，那么就选它（这样序列{an}就不能收敛到它了）；否则如果这一步选si不合法，那就随便选一个合法的数（此时序列{an}已经不可能收敛到si了）。这种策略就可以保证A选出的数列的极限不是S集里的任一个数。
    有趣的事情来了。假如A和B约定好的S集就是整个实数区间[0,1]，那么B显然不可能获胜；但如果[0,1]是可数集的话，B是有必胜策略的。于是我们就知道了，[0,1]是不可数集。

消息来源：http://blog.sciencenews.org/mathtrek/2008/01/small_infinity_big_infinity.html
查看更多：https://www.math.gatech.edu/~mbaker/pdf/realgame.pdf