期中告一段落。除了下下星期要交的现文史论文以外，最近似乎又清闲了不少，又有功夫在这里写点东西了。当然，我宝贵的时间也没有荒废在论文、作业和考试上。几乎每一堂古汉课和现文史课我都在读《什么是数学》，进度算是相当快了。这可能是我近几年读的所有书中给我带来的收获最大的一本。最近好几个人问我，有什么牛B一点的数学书没。我毫不犹豫地脱口而出，《什么是数学》。如果我要去一个荒岛上，只能带三本书，我会选择《算法导论》、《组合数学》和《什么是数学》。如果叫我舍弃一样，我估计会扔掉《组合数学》。如果还得再丢弃一本，我只好忍痛丢下《算法导论》了。
读《什么是数学》的收获太多了。在这里，我只更新一些我原来不知道，又很有趣的东西。如果你希望迅速对此书有一个全面的了解，千万不要错过dd牛的《什么是数学》笔记。
阅读《什么是数学》的前面几章时，你经常会跟随着书中的文字重新看待一个显而易见的结论，然后对这个结论有了一个全新的认识。比如，书中曾提到，为什么数学归纳法是合理的？我已经知道n=1时结论成立，也知道若n=k成立则n=k+1结论也成立，那么对于任意一个给定的正整数t，n=t时的结论是成立的，因为经过有限次迭代后最终我们总可以到达n=t的情况。但是，为什么我们敢断言对所有这无穷多个n，结论都是成立的？显然，你不能说“我们可以迭代无穷多次”，一个有限的证明过程当然不允许有无限多个步骤。因此，为了说明对于所有正整数n结论都成立，我们不得不使用反证法把“无穷”变成“有穷”。我们假设对于某些n，这个结论是不成立的。那么，这里面一定存在一个最小的数p，它使得结论不成立。由于我们已知n=1时结论成立，因此p一定是大于1的。但n=p是“最早”使结论不成立的情形，因此n=p-1时结论一定为真。这就与我们已知的第二个条件“若n=k成立则n=k+1结论也成立”矛盾了。因此我们说，对于所有正整数n，结论都是成立的。
这个推理过程中用到了另一个显而易见的结论：对于一个非空的正整数集C，C中一定存在一个最小的元素。这又是为什么呢？你可能会说，废话，把所有元素拿出来两个两个的比，一定能比出一个最小的数来。这种说法是错误的。注意到集合C有可能有无穷多个元素，你是比不完的。为了更清晰地认识这个结论，我们只需要注意到，如果把条件换成“有理数集C”或者“实数集C”，结论就不再成立了，因为集合{1, 1/2, 1/3, 1/4, …}显然不存在一个最小的数。可以看到，上述结论是否成立是和数的稠密性紧紧相关的。事实上，为了说明正整数集C中存在最小元素，我们任意从集合中取出一个元素n，那么1, 2, …, n这有限多个数当中一定存在一个最小的数，它在这个集合C中。它就是整个集合的最小数。对于稠密的有理数点和实数点，这个证明显然不再适用。
下面将提到的一个定理也是看上去非常显然的。算术基本定理是说，任意一个大于1的正整数都能表示成若干个质数的乘积，且表示的方法是唯一的。换句话说，一个数能被唯一地分解成质因数的乘积。因此这个定理又叫做唯一分解定理。唯一分解定理是数论中最最基本的定理之一，如果连这个定理都错了，那整个算术也就不存在了。很多结论的证明过程都用到了这一事实，例如我们可以用这个定理来证明根号2是无理数：
假设(p/q)^2=2，那么p^2=2q^2。我们将要证明，一个数的平方等于另一个数的平方的两倍是根本不可能的。如果对一个平方数分解质因数，它必然有偶数个因子（x^2的所有质因子就是把x的质因子复制成两份）。于是，p^2有偶数个质因子，q^2有偶数个质因子，2q^2有奇数个质因子。等号左边的数有偶数个质因子，等号右边的数有奇数个质因子，大家都知道这是不可能的，因为同一个数只有一种分解质因数的方法（唯一分解定理）。
好，现在的问题是，为什么质因数分解的方法是唯一的。这个结论是如此的显然和易于接受，以致于有人会脱口而出：这当然是唯一的，不断使用越来越大的质数去试除，最后得到的肯定是唯一的质因数分解。不可否认，这个算法本身是没有任何问题的。根据合数的定义，试除与分解是一定能不断进行下去的，除非被除数本身变成了一个质数，而此时也标志着算法的结束。问题的关键就在于，这并不能说明原数能唯一地表示成质数的乘积：换一种试除的顺序会不会得出不同的分解方法？万一还有什么别的牛B大法也能用来分解质因数，而且结果与上面得到的完全不一样咋办？上面给出的算法只能说明我们能找出至少一种分解质因数的方法，用这种方法得到的结果是唯一的，但到底还有没有其它偏方秘籍能导出另外的分解方法来，我们就不得而知了。为了真正地证明，分解质因数的方法是唯一的，我们将再次用到反证法。假设存在某些数，它们有至少两种分解方法。那么根据上文提到的“非空正整数集里存在最小的元素”，一定有一个最小的数M，它能用至少两种方法表示成质数的乘积：
M = P1 * P2 * … * Pr = Q1 * Q2 * … * Qs
下面我们将看到，这种假设会推出一个多么荒谬的结果来。不妨设P1 <= P2 <= ... <= Pr, Q1 <= Q2 <= ... <= Qs。显然，P1是不等于Q1的，不然两边同时约掉它，我们就得到一个更小的有两种分解方法的数。不妨设P1 < Q1，那么我们用P1替换掉等式最右边中的Q1，得到一个比M更小的数T = P1 * Q2 * Q3 * ... * Qs。令M' = M - T，我们得到M'的两种表达：
M' = (P1 * P2 * ... * Pr) - (P1 * Q2 * ... * Qs) = P1 * (P2 * .. * Pr - Q2 * ... * Qs) …… (1)
M' = (Q1 * Q2 * ... * Qs) - (P1 * Q2 * ... * Qs) = (Q1 - P1) * Q2 * ... * Qs ……………… (2)
由于T比M小，因此M'是正整数。从(1)式中我们立即看到，P1是M'的一个质因子。注意到M'比M小，因此它的质因数分解方式应该是唯一的，可知P1也应该出现在表达式(2)中。既然P1比所有的Q都要小，因此它不可能恰好是(2)式中的某个Q，于是只可能被包含在因子(Q1-P1)里。但这就意味着，(Q1-P1)/P1除得尽，也就是说Q1/P1-1是一个整数，这样Q1/P1也必须得是整数。我们立即看出，P1必须也是Q1的一个因子，这与Q1是质数矛盾了。这说明，我们最初的假设是错误的。
唯一分解定理的一个重要的推论是，如果质数p是ab的因子，那么p或者是a的因子，或者是b的因子。我们刚才在证明过程中也不自觉地用到了这个推论。证明方法很简单，假如a和b里面都不含p，把a和b各自分解开来再乘到一起，我们就得到了数ab的一个没有因子p的分解方式；而按照前面提到的试除法，ab是可以表示成p与另一些质数的乘积的，这违背了唯一分解定理。连续多次使用该推论，我们可以很快将推论推广到多个数的情形。
事实上，假设这个推论成立，我们也能很快反过来推出唯一分解定理：写出N的两种质因数分解，在前一种分解中任取一个因子，它必然会在后一种分解方法中出现；把它们约掉之后结论继续适用，不断进行该操作直到最终两边都只余下一个1。这一系列操作说明了，两种分解方法实际上是相同的。我们看到，唯一分解定理和它的推论实际上是等价的。如果我们能够绕过唯一分解定理，用另一种方法证出这个推论，我们也就相当于找到了唯一分解定理的另一个证明。而事实上，运用扩展的辗转相除算法，我们可以飞快地完成推论的证明。我们将说明，如果质数p能整除ab，但不整除a，那它一定是b的约数。
质数p不能整除a，告诉我们a和p互质，于是存在整数k和l使得ka + lp = 1。等式两边同时乘以b，我们有kab + lpb = b。而ab能被p整除，也即存在整数r使得ab=pr。那么，kpr + lpb = p(kr + lb) = b，我们立即看出p是b的一个约数。
做人要厚道，转贴请注明出处
的确是很不错的书..只可惜在dd牛的笔记里看不到拓扑学的内容..
啊～沙发～
问一句：M牛是在哪里买到这本书的？？
由于T比M小，因此M’是正整数。从(1)式中我们立即看到，P1是M’的一个质因子。注意到M’比M小，因此它的质因数分解方式应该是唯一的，可知P1也应该出现在表达式(2)中。既然P1比所有的Q都要小，因此它不可能恰好是(2)式中的某个Q，于是只可能被包含在因子(Q1-P1)里。但这就意味着，(Q1-P1)/P1除得尽，也就是说Q1/P1-1是一个整数，这样Q1/P1也必须得是整数。我们立即看出，P1必须也是Q1的一个因子，这与Q1是质数矛盾了。这说明，我们最初的假设是错误的。
一定要(Q1-P1)/P1除得尽？
补充证明：P1/(Q1-P1)除得尽不也行？
以为P1、Q1是质数，所以Q1-P1=1，P1、Q1奇偶性不同，所以P1=2，Q1=3，P1 * P2 * … * Pr 为偶数， Q1 * Q2 * … * Qs为奇数，矛盾。
回复：如果P1不是Q1-P1的约数，那它必然等于某个Q，但这是不可能的
这个是相当NB了，很好很强大。
ps原来那个网站的数据库丢了？我怎么登录不了了？
每次看你的博客总能有不少收获，佩服啊，太牛了！
把这本书入队吧.. 排队的书太多了..
顶
我看中文翻译的还不错哦
回复：这本书翻译得相当好！！
真是精彩
一则据说最受女性欢迎的笑话
男人只有懂得了做女人的难，才会更好地理解和宽待女人，尊重和关爱这个世界的另一半……
一个男人厌倦了他每天出门工作而他的老婆却整天呆在家里。他希望老婆能明白他每天是如何在外打拼的。于是他祷告祈求：”全能的主啊，我每天在外工作整整8小时，而我的老婆却仅仅是待在屋里。我要让她知道，我是怎么过的，求你让我和她的躯体调换一天吧。”
“阿门”，无限智慧的主，满足了他的愿望。
第二天一早，他醒来，当然，是作为一个女人。他起床，为他的另一半准备早点，叫醒孩子们，为他们穿上校服，喂早餐，装好他们的午餐，然后开车送他们去学校，回到家，他挑出需要干洗的衣物，送到干洗店，回来的路上还顺路去了银行，然后去超市采购，回到家，放下东西，要缴清账单、结算支票本。
当他打扫了猫盒，给狗洗完澡，已经是下午一点了。他匆忙地整理床铺，洗衣服，给地毯吸尘，除尘，清扫，擦洗厨房的地板。他冲往学校去接孩子们，回来的路上还同他们争论了一番。他准备好点心和牛奶，督促孩子们做功课，然后架起烫衣板，一边忙着，一边看会儿电视。
四点半的时候，他开始削土豆，清洗蔬菜做沙拉，给猪排粘上面包屑，剥开那些新鲜的豆子，准备晚餐。吃完晚饭，他开始收拾厨房，打开洗碗机，叠好洗干净的衣物，给孩子们洗澡，送他们上床。
晚上九点，他已经撑不住了，然而，他的每日例行工作还没结束。他爬上床，在那里，还有人期待着他，他必须，而且不能有任何抱怨。
第二天一早，他一醒来就跪在床边，向主祈求：”主啊，我真不知道自己是怎么想的，我怎么会傻到嫉妒我老婆能成天呆在家里？求你，哦，求求你，让我们换回来吧！”
无限智慧的主，回答他：”我的孩子，我想你已经吃到苦头了，我会很高兴让一切恢复原来的样子。但是……
你不得不再等上九个月，昨晚，你怀孕了…… “
由于T比M小，因此M’是正整数。从(1)式中我们立即看到，P1是M’的一个质因子。注意到M’比M小，因此它的质因数分解方式应该是唯一的，可知P1也应该出现在表达式(2)中。既然P1比所有的Q都要小，因此它不可能恰好是(2)式中的某个Q，于是只可能被包含在因子(Q1-P1)里。但这就意味着，(Q1-P1)/P1除得尽，也就是说Q1/P1-1是一个整数，这样Q1/P1也必须得是整数。我们立即看出，P1必须也是Q1的一个因子，这与Q1是质数矛盾了。这说明，我们最初的假设是错误的。
一定要(Q1-P1)/P1除得尽？
补充证明：P1/(Q1-P1)除得尽不也行？
以为P1、Q1是质数，所以Q1-P1=1，P1、Q1奇偶性不同，所以P1=2，Q1=3，P1 * P2 * … * Pr 为偶数， Q1 * Q2 * … * Qs为奇数，矛盾。
？？？？
好象没必要补充吧？前面不是说P1已经是质数了么？你还想让他被谁整除？
多年以前看过一本书叫 数学是什么 不知道是不是同一本书
数学归纳法里那个”无穷”貌似是潜无穷而不是实无穷…..
回11楼，需要补充
P1已经是质数,但Q1-P1可能等于1，还有把这种情况说一下
@hetong_007 我的这本书是在当当上买的 还算比较便宜
很棒～
现在没时间读这本巨著，先读M牛的笔记了
是这本吗？
http://www.douban.com/subject/1320282/
matrix67 wrote:
“它在这个集合C中。它就是整个集合的最小数。对于稠密的有理数点和实数点，这个证明显然不再适用。”
对于实数，数学归纳法是没法用的。但对于有理数则是可以的，因为有理数实际上并不是稠密的，有理数可以和自然数集构成一一映射，换句话说，有理数集是可数的。一个直观的“数”的方法如下：
1/1
1/2 2/1
1/3 2/2 3/1
1/4 2/3 3/2 4/1
…
即构造一个矩阵，m(i,j) = i/j，然后照着斜线(i+j = c)数。按照这个方法，实际上归纳法是可以推广到有理数上的。
回复：注意稠密性的定义：任意小的区间内都存在这样的一个数
稠密性的定义实际上不是重点，只是一个叫法的问题。关键是有理数和自然数和正整数集合都是可以一一对应的，因此他们实际上都是“等势”的。这个意义上，实数集有本质的不同，实数集无法和它们建立一一对应。所以，数学归纳法可以推广到有理数集，却无法推广到实数集。
回复：对。数学归纳法是可以推广到有理数的，只是“归纳”的顺序和原来完全不一样。
针对有理数的数学归纳法将变得相当有趣，要是有这样的例子就好了。
显然，P1是不等于Q1的，不然两边同时约掉它，我们就得到一个更小的有两种分解方法的数。
我这个位置没有想明白，麻烦楼主解释一下，不耻下问嘛，这会这得没想明白，谢谢
那个。。dd笔记的链接好像不大对了
還有一種叫”超限歸納法”的, 即推廣到任意良序集合上.
强烈建议你在blog中添加 renren 、开心的分享，
求教 问一下那本书P27下面那个用数学归纳法时必须保证条件a)和b)是被真正满足的。那个错误的证明具体错在哪里了？ 我只是觉得a）别扭，说不清楚。谢谢。p.s.您有QQ么？
第一个问题：数学归纳法成立的基础是，自然数集合按照实数的序的定义是良序集合。所谓良序集合，就是在规定的元素之间的顺序下，每个非空集合都有最小元素。作者做为学文学、教文学、研究文学的专家，以优美的文字来说数学，感觉很不容易。因为只有理解了，才能体会到美，书法、绘画、文学是如此，数学更是如此。
这货……居然是……学……中文……的
相当NB了，很好很强大。
可否发一个英文版的电子书下载地址。
《具体数学》里有同样的内容，不过表述不如这里。中文翻译多出来一个qn.看了好久不知道干嘛的，翻了原版只看到一个after all.
关于这一点很疑惑，为什么“注意到M’比M小，因此它的质因数分解方式应该是唯一的”可以这样说，不是要证明“唯一分解定理吗”这样算不算循环引用呢？
在《具体数学》上看到了同样的节点，写了“根据归纳假设”，然后自己想的是，是不是“假设小的数有唯一分解，然后来证明大的数无法不遵守唯一分解”来证明？
我的数学归纳法似乎只有高中水平，而高中好像没有提到过“归纳假设”这个概念，或者说是类似“假设n=k时候成立”这样的东西呗成为归纳假设吗？老师讲题目的时候没用过这个词//如有误解求指出=_=||