康MM讲座
康MM讲座
这句话是Hilbert说的，意思是任给一个数学命题，只能有两个可能：这个命题是对的，可以证明，或者这个命题是错的，可以找出反例。做不出来是因为你自己笨，不能怪数学不好。（这个东西还有个专门名字，叫数学的完备性。）
当时所有数学家都是这样认为的，说了类似的话的估计也有不少，但是大家只记住Hilbert了。一个原因当然是因为Hilbert有名，他是当时最有名的数学家，但还有其他原因。Hilbert可不是说说就算了，他很认真地要证明这件事，他要把数学完全公理化：要把全部数学都建立在几条公理上，而且这些公理要满足1)相容性（这些公理之间没有矛盾）；2）完备性（上面提到的）；3）还有一条忘了叫什么性了，是说公理中没有多余的，每一条都不能从其他公理推出。
Hilbert首先做了几何的公理化，他引进了21条公理，整个2维与3维的几何都可以建立在这些公理之上。下一步就是整个数学的公理化了，但是后来来了一个20多岁的小子，叫Godel，给了Hilbert当头一闷棍。
Godel证明了他的不完备性定理：任一个包括所有自然数的公理系统一定是不完备的。他构造了一个命题，既不能被证明，也不能被推翻。我不知道当时Hilbert老先生是怎么想的，大概连上吊的心都有。
数学家们还没有放弃希望，他们说Godel的命题不过是一个逻辑游戏，真正有数学意义的命题还都是确定的，当然Godel的闷棍也还没有打完，他又向集合论中公认的最难的问题--连续统假设下手了。连续统假设是这样一个问题：全体整数的个数是a，全体实数的个数是c，集合论的创始人Cantor提出的连续统假设说，a与c之间没有其他数了。Hilbert把连续统假设列为他的第一问题，可见其分量。Godel这次作的事是构造了一个数学模型，在其中，连续统假设成立。这一来就麻烦了，我们现在知道了连续统假设不可能是错的，但是由于Godel的不完备定理，没人敢说它是对的，因为毕竟没有证明。
Godel搞的东西太过奇怪，最后终于把自己也绕进去了--他犯了精神病。当时Princeton数学系有两个著名的精神病，一个是Godel，另一个是John Nash。这两个人每天什么事都不做，整天游游逛逛，坐领工资。其实工资是家人领的，他们自己肯定不在乎。
因为Godel犯了精神病，给数学的确定性最后定上棺材板又要等几十年了。这时来了一个家伙叫Cohen。这个家伙也是绝顶聪明，他的本行不是集合论，而是调和分析。当时有一个人（弄不清楚到底是谁）说了一句话，他说Cohen不过有点小聪明，难题是绝对做不出来的。Cohen当然不服气，“你说什么题最难吧，”“连续统假设最难。”“好，就是连续统假设。”于是他就去做连续统假设，一下子还真让他给做出来了：他也构造了一个模型，在其中连续统假设不成立。这一下子，连续统假设真的成了一个Godel意义下的不可判定的问题，既不是对的也不是错的。
这一下子，数学家们可吓呆了，闹了半天，不是我们无能，是共军太狡猾了，问题根本就没有解，你让我们证明什么？等到数学家缓过劲来，就开始走向另一个极端了：凡是做不出来的题，就说这可能没有解。例如有些数学家就很认真地说Fermat大定理可能没有解。当然后来人家做出来了，就不能再说了。但是其他问题还是在说，甚至连Erdos也说角谷猜想（3n+1问题）可能没有解。
当然有很多问题真的就是没有解，甚至我们坛子上出现过的问题。（大家回忆一下，看看谁能想起来？如果都想不起来就看我下一篇文章。）
注：这些大多是多年以前学的，因为后来换了专业，很多都没学完，学完的也忘了很多。有不确切的地方，请大家指出。
选择公理的故事
数学的完全公理化虽然失败了，数学家们还是对数学进行了不完全的公理化。为大部分数学家所接受的Zermelo-Frankel公理系统有10条公理，其中的9条是很自然的，像两个集合的并也是一个集合这样的。但是有一条显得很奇怪，就是选择公理。
选择公理：给定任意个集合，可以从每个集合中选出一个元素，组成一个新的集合。
一般数学系学生第一次接触选择公理是在实变函数课程中构造不可测集，在数学史上选择公理是怎么出现的我不是很清楚，但是开始的时候大家都没有觉得有什么不妥。可是后来出现了一些很奇怪的，违背常识的结果，其中最奇怪的是Banach-Tarski分球定理。
Banach-Tarski分球定理：可以把一个实心单位球分成5个子集A，B，C，D，E， 使得A与B可以拼成一个实心单位球，C，D，E可以拼成另一个实心单位球。
奇怪的地方是这5个子集都是刚性的，像星球大战第三集中没建好的死星那样的，拼球的过程中不能改变形状。也就是说，我们实实在在的把一个球变成了两个球。
这些奇怪结果的根源都是用到类似于选择公理的这样一个步骤，因此一部分数学家要求禁止使用这样的数学证明，即禁止使用选择公理。但是禁止也有禁止的麻烦，首先，数学中并没有规定一个球不能变成两个球，虽然违反常理，却不能说这里引出矛盾。另外，如果不能使用选择公理，集合论的大部分都不能成立了，甚至不能比较两个无穷集合的大小。而且不光是集合论，像拓扑，代数，泛函分析等领域都有很重要的定理用到选择公理。因此多数数学家还是在提心吊胆的使用选择公理—--提心吊胆是因为不知道这样会不会哪一天出事，也许选择公理真的会引出矛盾呢。
打消数学家的顾虑还是要靠我们上次提到的Godel和Cohen，用他们的数学模型。他们的模型都是只用到另外的9条公理，构造的过程中不用选择公理。Godel的模型中，不光连续统假设成立，选择公理也成立。而Cohen的模型中，不光连续统假设不成立，选择公理也不成立。这下子数学家们终于知道了可以放心大胆地使用选择公理，不用担心会出问题，而且还知道了选择公理本身确实是一条公理，不能由其他公理推出。
倚赖选择公理的数学题比我们想象的要多得多，我们论坛上也有过几次。下面看几个例子：
问题1。设实函数f(x)满足对任意x,y, f(x+y)=f(x)+f(y)。f是否一定是线性函数f(x)=cx?
有选择公理的时候，这个问题的答案是否定的，可以有很多非线性的函数满足这个条件。而没有选择公理的时候，一种可能情况是所有的实数集合都是可测的，而满足上述条件的可测函数一定是线性的。
问题2。乱弹版主曾经给出这个圆周染色题：把单位圆周染成三种颜色，证明一定存在一个等腰三角形，其三个顶点是同色的。
这个问题本身不用选择公理。问题可以推广成n种颜色，也不用选择公理。但如果把问题推广到可数无穷种颜色：把单位圆周染成可数无穷种颜色，是否一定存在一个等腰三角形，其三个顶点是同色的？
这个问题的答案就与选择公理有关了：有选择公理的时候，答案是否定的。而没有选择公理的时候，每一种颜色的集合都可以是可测的，而有正测度的可测集中一定可以构造一个等腰三角形。
问题3。脑坛前辈野菜花曾经给出这个问题：是否存在一个空间点集，与空间中每个平面都相交，但交点都是有限个？
这个问题也是本身不用选择公理，可以找到一个点集，与空间中每个平面都相交，但交点最多是5个。现在考虑问题的推广：是否存在一个空间点集，与空间中每个平面都相交，但交点最多是３个？这个推广的问题的解我用到选择公理证明了这样的点集的存在性，但是不知道不用选择公理会有怎样的结果。
这三个问题就作为给大家的作业。前两题的提示：选择公理的一个推论是任一个线性空间都有一个基，即极大的线性无关子集，使得线性空间中任意一个点都能唯一的表示成这个子集的有限线性组合。
解答
与选择公理有关的东西非常多，但是大部分都很高深，只有两个适合我们论坛水平：一个是可测集的存在性：如果选择公理不成立，可以构造一个模型，其中任意n维空间的子集都是可测的；（注意这个时候Banach-Tarski分球定理就不成立了。）另一个是把所有实数考虑成有理数的线性空间，有选择公理的时候，这个线性空间有一组基，即一些线性无关的实数组成的一个子集，使得任一个实数都能表成这些数的有限线性组合。我们的前两个题目就用到这两条性质。
问题1。设实函数f(x)满足对任意x,y, f(x+y)=f(x)+f(y)。f是否一定是线性函数f(x)=cx?
有选择公理的时候，这个问题的答案是否定的，可以有很多非线性的函数满足这个条件：设{x_a}是实数线性空间的一组集，对每个x_a，给它一个实数y_a，然后这样定义f(x)：对x = q_1*x_1+q_2*x_2+…+q_n*x_n，f(x) = q_1*y_1+q_2*y_2+…+q_n*y_n。只有当y_a = c*x_a 时f(x)才是线性函数。
而没有选择公理的时候，有可能所有的实数集合都是可测的，而满足上述条件的可测函数一定是线性的。有正测度的可测集有这样的性质：它不会是完全均匀分布的，一定会在某个区间内很集中，即对任意给定的r<1，一定存在一个小区间，使得小区间内至少有r的部分属于该可测集。这样我们就能找到一个常数c，使得大部分x都满足f(x)=cx。再根据条件，剩下的x也必须满足这个关系。
问题2。乱弹版主曾经给出这个圆周染色题：把单位圆周染成三种颜色，证明一定存在一个等腰三角形，其三个顶点是同色的。
证明： 我们证明正十三边形中任意五个顶点 a, b, c, d, e 中必有三个是一个等腰三角形的顶点。做一个映射 f ： (x,y)
如果 f(a,b
这个问题本身不用选择公理。问题可以推广成n种颜色，也不用选择公理。但如果把问题推广到可数无穷种颜色：把单位圆周染成可数无穷种颜色，是否一定存在一个等腰三角形，其三个顶点是同色的？这个问题的答案就与选择公理有关了。
这个问题可以放到直线上去，实际上就相当于要找一个长度为3的同色的等差数列。
对n种颜色，这个问题变成了 Van Der Waerden 定理的推论：
Van Der Waerden 定理：对任意正整数 k 和 r，存在常数 n(k,r)，使得对集合 {1,2,...,n(n,k)} 的任意分解 C_1，C_2，...，C_k，一定有一个子集 C_i 包含一个长度为 k 的等差级数。
满足上面条件的常数中最小的叫做 Van Der Waerden 常数。Van Der Waerden 常数中只有非常少的几个是已知的，例如用上面的方法可以证明n(3,3)=27。
无穷种颜色的情况与选择公理有关。有选择公理的时候，答案是否定的。考虑有理数的所有可重复的有限子集：{1，1/2，1/2，1/3，1/3}这样的子集。这种子集共有可数无穷个，每一个子集给一种颜色。再把实数表成线性空间，实数x = q_1*x_1+q_2*x_2+…+q_n*x_n 的颜色就是子集{x = q_1，q_2，…，q_n}的颜色。这样染色就保证了任一种颜色都不存在长度为3的同色的等差数列。
而没有选择公理的时候，每一种颜色的集合都可以是可测的，而有正测度的可测集中一定可以构造一个等腰三角形：只要找出这种颜色很集中的小区间，对折一下，就得到了一个等腰三角形。
问题3。脑坛前辈野菜花曾经给出这个问题：是否存在一个空间点集，与空间中每个平面都相交，但交点都是有限个？
这个问题也是本身不用选择公理，可以找到一个点集，与空间中每个平面都相交，但交点最多是5个。现在考虑问题的推广：是否存在一个空间点集，与空间中每个平面都相交，但交点最多是３个？
证明： 这个证明用到了超限归纳法，即对无穷序数用归纳法。这种论证方法的基础是良序原理，而良序原理与选择公理是等价的 。
对证明中用到的术语，请参考集合论的教材。
设 c 是所有实数的基数（即连续统）。 3 位空间总共有 c 个 平面。把这些平面写成 {P_alpha : alpha 是小于 c 的所有序数 } 。对每个序数 alpha ，用超限归纳法定义一个点集 S_alpha ，使得 S_alpha 与每个平面 P_beta （ beta <= alpha ）相交，但最多相交 3 点。而且我们要求S_alpha中任意4点不共面。
对给定的 alpha ，令 S' = U {S_beta: beta < alpha} 。如果 S’ 已经与 P_alpha 相交，令 S_alpha = S' 。否则在 P_alpha 上选一点 x 使得 x 不在 S' 中任意两点形成的线上，也不在 S' 中任意三点形成的平面上。因为 S' 的基数比 c 小，这样的点一定存在。令 S_alpha = S' u {x} 。
最后令 S = U {S_alpha : alpha <= c} 。 S 满足我们的条件：
1) 对任意平面 P_alpha ， S 的子集 S_alpha 与 P_alpha 相交。 .
2) 设平面 P_alpha 与 S 相交于 4 点 x_1, x_2, x_3, x_4 。这 4 点是一个一个加入 S 中的，可以假设是按以上顺序。当 x_4 加入的时候， ( 在某一个 S_beta) ，前 3 个点已经在 S_beta 中了，因此 x_4 不会与他们共面。
类似的，可以证明存在一个空间点集与任何一条直线都相交，但都不超过两点。
最后再指出一点：实数作为线性空间是非常有用的方法，而且不是一定与选择公理有关。例如下面两个问题的解都用到这个方法，但是只涉及到有限个实数，因此不用选择公理：
问题1。也是乱弹大汗出的题：设区间[0，1]中有有限个点，包括0和1。这些点之间的距离，除了1以外，都出现至少两次。证明这些数都是有理数。
证明： 设这些点不都是有理点。令 r_1, r_2, ..., r_m 为 x_0, ..., x_n 的一个关于有理数的极大线性无关子集，即对任意不都是 0 的有理数 a_1, a_2, ..., a_m ， a_1*r_1 + a_2*r_2 + ... + a_m*r_m 也不是 0 。将其中的 m-1 个加到有理数集 Q 中，并扩展成实数集 R 的线性子空间 S 。存在一个实数 r (r 不在 S 中，也不一定是 x_i 之一 ) ，使得每个 x_i 都能被唯一的表示成 s+k*r ，其中 s 属于 S ， k 是整数。令 k_1 和 k_2 为这种 k 的最大值和最小值，则这两点 s+k_1*r 和 and s+k_2*r 之间的距离只出现一次。
问题2。这个题原来是星星司令出的，是整数。但是可以改成实数，结果仍然成立：设有11个球，重量为实数。（这是废话了，原题中是整数。）11个球中任意拿出一个，剩下的10个球都能分成重量相同的两组，每组5个球。证明这11个球重量相同。
下面按照学术路线算出来的又是必败策略：
-------------
在NIM游戏里，初始状态「3，5，7」的必胜策略是什么？状态「3，5，8」的必胜策略又是什么？状态「3，4，5，6，7」呢？
前面已经算过这个初始状态的NIM值N「3，5，7」为1，必胜策略就是从任何一堆拿一个就行了。
一般来说，先把NIM值表成二进位数，找一个在NIM值的最高位为1的子状态，然后比较整个状态和子状态的NIM值。所有整个状态为1的位上，子状态是1就改成0，是0就改成1。
例如「3，5，8」的NIM值为14 = (1110)，最高位是第四位。8 = (1000)的第四位为一，所以这个子状态的NIM值应变为(0110) = 6。必胜策略就是在8的一堆上拿两个。
「3，4，5，6，7」的NIM值是3 = (11)。要找一个第二位为1的子状态，3，6，7都可以。大家可以自己算一下应该拿几个。(答案：3，7拿3个，6拿1个)
NIM还有一个变种：走最后一步为负。这种情况下，一开始还是和普通NIM一样，但到了只有一个子状态的NIM值大于1时就不同了。如果有奇数个子状态为1，就把大的一堆拿光，如果有奇数个，就剩一个。也就是说，给对手剩下奇数个1。
---------------------
我的胜策很简单：
先拿者胜：每堆拿剩一个，最后一堆全拿光。
如果走最后一步为负，则仍在拿最后一堆时留一个。
下面这题,一步就胜了,用得着算吗?
问题4。(和上一题差不多。)有一块6X8的矩形巧克力，左下角那一块坏了。两人分吃，每次掰时，先选定一块，然后把这块及其上面和右面的都掰掉。(剩下的是锯齿形。)吃最后一块为负。第一次应该掰多少？
这一题的NIM值就很难算了，要编一个程序才行。下面是矩形的NIM值。(还不包括锯齿形。)
5，8，12，16，21，13，28，32
4，7，11，13， 6，21，23，22
3，5， 9， 6，13，16，19，12
2，4， 5， 9，11，12，13，16
1，2， 4， 5， 7， 8，10，11
0，1， 2， 3， 4， 5， 6， 7
------------