Proofs from THE BOOK的第六章相当精彩，这一章循序渐进地介绍了多个无理性证明。先证明e是无理数，证明方法和高数课本上的基本相同；试图用类似的办法证明e^2也是无理数时，这一章的内容开始牛B了起来，一些巧妙的变换就让原来的办法继续适用于e^2的证明；加上一些更有趣的技巧，我们还能继续证明e^4也是无理数；当证明对除0外的所有有理数r，e^r都是无理数时，全章达到了高潮。
    这一章还提到了pi^2是无理数的证明方法。这个证明建立在Ivan Niven于1947年提出的“pi是无理数”的经典证明的基础上：仅仅是在原证明过程中加了一些微妙的变化就得到了pi^2也是无理数的结论。注意到，“pi^2是无理数”是一个比“pi是无理数”更强的结论。由于有理数的平方还是有理数，因此证到了pi^2是无理数也就说明了pi必然是无理数；但反过来却不行，因为无理数的平方不一定也是无理数，比如根号2的平方就不是无理数。

    证明过程用到了一个函数，其中n是一个任取的大于等于1的常数。可以想像，这个函数的分子部分展开后是一个关于x的整系数多项式，最低次数为n，最高次数为2n。我们将用到这个函数的两个性质：首先，当0<x<1时，显然有0 < f(x) < 1/n!；其次，函数f及其任意阶导数在x=0和x=1处都是整数。为了证明后一个结论，首先注意到当x=0时，不管是多少阶的导数，除了常数项以外其余项都是0；常数项只可能在n<=k<=2n时出现（k表示k阶导数），但此时它等于一个整系数乘以k!/n!，显然也是个整数。另外，由于f(x)=f(1-x)，根据复合函数的微分法我们立即得到对任意x都成立，当然也就有。

查看更多 »

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

    自然数是数学界中最自然的数，它用来描述物体的个数，再抽象一些就是集合的元素个数。在人类文明的最早期，人们就已经很自然地用到了自然数。可以说，自然数是天然产生的，其余的一切都是从自然数出发慢慢扩展演变出来的。数学家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算术体系是相容的。这个问题至今仍有争议。

查看更多 »

    警告，千万不要去计算pi的二进制表达。数学家们猜想pi是一个正规数(normal number)，也就是说它包含了任意一个有限长的01串，所有n位长的01串都以相等的概率出现在pi的二进制中。

    如果你偏要去计算它，你会：

• 侵犯版权（包括所有书籍、小说、报纸、杂志、网站、音乐、电影、软件，甚至是Windows源码）；
  
• 侵犯商标权；
  
• 拥有大量非法的激情无码大片；
  
• 拥有大量国家最高机密；
  
• 制造出非法的DVD破解软件；
  
• 制造对小胡同志的恐吓信；
  
• 拥有所有人的身份证号、信用卡号、电话号码和各种密码；
  
• 亵渎伊斯兰教（理论上并不是非法的，但你下半辈子得和Salman Rushdie躲在一起）；
  
• 亵渎科学论派（非法！问问Keith Henson就知道）。

    同时，你的电脑里会包含有目前所有已知的最邪恶的电脑病毒──事实上还包括有所有未知的最邪恶的病毒。
    我的电脑上有很多极度私密的文件，我不希望你把它们浏览个遍。
    你或许想，我只计算几位就行了；但何必去冒这个险呢？谁也说不准，算到哪一位时你会找到关于Kennedy刺杀案的秘密文件，或者你邻居的六岁小女孩和家里的狗狗XX的恶心照片，或者还未发行的最新一部Star Wars的完整拷贝。反正，千万别去算它。
    同样的警告还适用于e、根号2、Euler常数、phi、除0以外的代数数的余弦值和其它各种各样的实数。
    这也是为什么这些数总是被表示成十进制数的原因。

来源：http://everything2.net/index.pl?node_id=1302963

    今天的最后一篇日志了，仍然是翻译的cut-the-knot。发完我就睡觉去了。

    这里已经有五种证明根号2是无理数的方法了。现在我们算是介绍第六种方法了。
    一个有限小数的平方绝对不可能变成整数，因为小数部分不可能消失。观察有限小数的小数部分最后一个数字你会发现结论是显然的，平方后它总会产生新的“最后一位”。
    下面证明，(n/m)^2不可能等于2。n/m不可能是整数，于是把它写成小数形式，而有限小数的平方不可能是整数。如果n/m不是有限小数的话，可以把它转换成另外的进制使得n/m是有限小数，因而上面的结论仍然成立。一个进制下的无限小数可能是另一个进制下的有限小数。比如，把分数n/m转化为m进制，得到的小数肯定是有限小数。

    我喜欢各种各样的证明。有史以来我见过的最诡异的证明写在http://www.matrix67.com/blog/article.asp?id=34。人们很难想到这样一些完全找不到突破口的东西竟然能够证明得到。说“没有突破口”还不够确切。准确地说，有些命题多数人认为“怎么可能能够证明”却用了一些技巧使得证明变得非常简单。我看了五色定理的证明，定理宣称若要对地图进行染色使得相邻区域不同色，五种颜色就够了。没看证明之前，我一直在想这个玩意儿可以怎么来证明。直到看了证明过程后才感叹居然如此简单，并且立即意识到四色定理基本上也是这种证明方法。还有，像“一个单位正方形里不可能包含两个互不重叠且边长和超过1的小正方形”这样的命题竟然完全用初中学的那些平面几何知识证明到了，简单得不可思议。关键是，我们能够读懂证明过程，但只有牛人才能想到这个证明过程。
    今天在OIBH上看到了这个帖子，帖子中哲牛分享的一篇文章The Power Of Mathematics恰好说明了这一点。文章中包含有一个推翻“万物皆数”的新思路，相当有启发性。今天我想把我已经知道的四种证明连同新学到的这一个一起写下来。

    如何证明存在一种不能表示为两个整数之比的数？
    古希腊曾有“万物皆数”的思想，这种认为“大自然的一切皆为整数之比”的思想统治了古希腊数学相当长的一段时间，许多几何命题都是根据这一点来证明的。当时的很多数学证明都隐性地承认了“所有数都可以表示为整数之比”，“万物皆数”的思想是古希腊数学发展的奠基。直到有一天，毕达哥拉斯的学生Hippasus告诉他，单位正方形的对角线长度不能表示为两个整数之比。被人们公认的假设被推翻了，大半命题得证的前提被认定是错的，古希腊时代的数学大厦轰然倒塌，数学陷入了历史上的第一次危机。最后，Eudoxus的出现奇迹般地解决了这次危机。今天我们要看的是，为什么单位正方形的对角线长度不能表示为两个整数之比。
      
    单位正方形的对角线长度怎么算呢？从上面的这个图中我们可以看到，如果小正方形的面积是1的话，大正方形的面积就是2。于是单位正方形的对角线是面积为2的正方形的边长。换句话说，Hippasus认为不可能存在某个整数与整数之比，它的平方等于2。
    中学课程中安排了一段反证法。当时有个题目叫我们证根号2是无理数，当时很多人打死了也想不明白这个怎么可能证得到，这种感觉正如前文所说。直到看了答案后才恍然大悟，数学上竟然有这等诡异的证明。
    当然，我们要证明的不是“根号2是无理数”。那个时候还没有根号、无理数之类的说法。我们只能说，我们要证明不存在一个数p/q使得它的平方等于2。证明过程地球人都知道：假设p/q已经不能再约分了，那么p^2=2*q^2，等式右边是偶数，于是p必须是偶数。p是偶数的话，p^2就可以被4整除，约掉等式右边的一个2，可以看出q^2也是偶数，即q是偶数。这样，p也是偶数，q也是偶数，那么p和q就还可以继续约分，与我们的假设矛盾。

    根号2是无理数，我们证明到了。根号3呢？根号5呢？你可能偶尔看到过，Theodorus曾证明它们也是无理数。但Theodorus企图证明17的平方根是无理数时却没有继续证下去了。你可以在网上看到，Theodorus对数学的贡献之一就是“证明了3到17的非平方数的根是无理数”。这给后人留下了一个疑问：怪了，为什么证到17就不证了呢？一个俄国的数学历史家“猜”到了原因。
    他猜测，当时Theodorus就是用类似上面的方法证明的。比如，要证明根号x不是有理数，于是p^2=x*q^2。我们已经证过x=2的情况了，剩下来的质数都是奇数。如果x是奇数且p/q已经不能再约分，那么显然p和q都是奇数。一个奇数2n+1的平方应该等于4(n^2+n)+1，也即8 * n(n+1)/2 + 1，其中n(n+1)/2肯定是一个整数。如果p=2k+1，q=2m+1，把它们代进p^2=x*q^2，有8[k(k+1)/2 - x*m(m+1)/2] = x-1。于是x-1必须是8的倍数。如果当时Theodorus是这么证明的，那么他可以得到这样一个结论，如果x-1不能被8整除，那么它不可能被表示成(p/q)^2。好了，现在3、5、7、11、13减去1后都不是8的倍数，它们的平方根一定不是有理数。在x=9时发生了一次例外，但9是一个平方数。而当x=17时这种证明方法没办法解释了，于是Theodorus就此打住。

    实际上，我们上面说的这么多，在古希腊当时的数学体系中是根本不可能出现的。毕达哥拉斯时代根本没有发展出代数这门学科来，它们掌握的只是纯粹的几何。因此，Hippasus当时的证明不可能像我们现在这样搞点什么奇数x偶数y之类的高科技东西。事实上，Hippasus当时完全运用的平面几何知识来证明他的结论。有人觉得奇怪了，既然当时没有代数，古希腊人是怎么提出“所有数都可以表示为整数之比”的呢？其实古希腊人根本没有提出什么整数之比，这是后人的一个误解。当时毕达哥拉斯学派提出的，叫做“公度单位”。
    两条线段的公度单位，简单的说就是找一个公度量，使得两条线段的长度都是这个公度量的整倍数（于是这个公度量就可以同时作为两条线段的单位长度并用于测量）。寻找公度量的方法相当直观，就是不断把较长的那个线段减去短的那个线段，直到两个线段一样长。熟悉数论的同学一下就明白了这就是欧几里德的辗转相除算法求最大公约数。第一次数学危机的根结就在于，古希腊人理所当然地相信不断地截取线段，总有一个时候会截到两个线段一样长。后来，Hippasus画了这么一张图，告诉大家了一个反例：有可能这个操作会无穷尽地进行下去。
      
    现在看他怎么解释，在图中的BC和BD之间进行辗转相除为什么永远不能停止。把BD减去BC，剩下一段DE。以DE为边做一个新的小正方形DEFG，那么显然DE=EF=FC（∵△EDF为等腰直角且△BEF≌△BCF）。接下来我们应该在BC和DE间辗转相除。BC就等于CD，CD减去一个DE相当于减去一个FC，就只剩下一段DF了。现在轮到DE和DF之间辗转相除，而它们是一个新的正方形的边和对角线，其比例正好与最初的BC和BD相当。于是，这个操作再次回到原问题，并且无限递归下去。最后的结论用我们的话说就是，不存在一个数x使得BC和BD的长度都是x的整倍数。于是，BD/BC不能表示为两个整数之比p/q（否则BD/p=BC/q，这就成为了那个x）。

    有发现上面的代数证明和几何证明之间的共同点吗？它们都是这样的一个思路：假设我已经是满足这个性质的最小的那个了，那么我就可以用一种方法找出更小的一个来，让你无限循环下去，数目越来越小，永无止境。严格的数学证明中你或许会看到这样一句话：“不失一般性，设n为最小的满足……”
    这种证明方法应用很广。比如，证明3^n不能表示为两个正整数的平方和。我假设存在一个最小的n使得x^2+y^2=3^n，那么x^2+y^2可以被3整除，于是x和y也应该能被3整除（一个正整数的平方除以3，要么除尽，要么余1）。假如x=3p，y=3q，那么(3p)^2+(3q)^2=3^n，即9(p^2+q^2)=3^n，那么。p^2+q^2=3^(n-2)，这和n最小的假设矛盾。换句话说，你永远找不到最小的，你必须一直递归下去。
    对于根号2是无理数的问题，下面一个证明使用了与上例几乎相同的解决方法。
    如果√N不是整数的话，假设√N=A/B（化到最简），那么NB/A=A/B。化成带分数后，NB/A和A/B的分数部分是形如a/A和b/B的形式，其中a<A且b<B。如果两个数相同，那它们的小数部分也应该相同，于是a/A=b/B。我们发现，a/b = A/B =√N，即我们找到了√N的更简的表达形式a/b。

    接下来的两个证明才是我佩服的，真正的Very Simple & Very Tricky。
    下面的这个证明曾经是我最喜欢的关于无理数的存在性的证明，它实在是太神奇了。
    假设(p/q)^2=2，那么p^2=2q^2。我们将要证明，一个数的平方等于另一个数的平方的两倍是根本不可能的。如果对一个平方数分解质因数，它必然有偶数个因子（x^2的所有质因子就是把x的质因子复制成两份）。于是，p^2有偶数个质因子，q^2有偶数个质因子，2q^2有奇数个质因子。等号左边的数有偶数个质因子，等号右边的数有奇数个质因子，大家都知道这是不可能的，因为同一个数只有一种分解质因数的方法（唯一分解定理）。
    这个证明还有一种更加神奇的变化。p^2和2q^2的质因子中，因子2的个数肯定是一奇一偶。那么它们转化成二进制后，末尾0的个数肯定也是一奇一偶。因此，这两个数不可能相等。

    今天，我见到了一个更加简洁的证明。它就来源于哲牛介绍的那篇文章。这个证明虽然与前面的证明有些类似，但它的简洁性足以让我打算写下今天这篇4000字的文章。看后我大为折服，这真的叫做the power of simple ideas in mathematics。
    同样是证明不存在整数p, q使得p^2=2q^2，这个证明只需要一句话。假如p、q是最小的正整数使得p^2=2q^2，看图，两个边长为q的小正方形放在一个边长为p的大正方形里，那么图中深灰色正方形的面积就等于两个白色正方形面积之和（面积守恒），于是我们就找到了具有同样性质的更小的整数p和q。仔细体会一下这个“面积守恒”，如果A+B=C，那么A和B重复计算了的必然是C里还没有算过的。很有意思。

      


2007.05.21更新第六种方法：http://www.matrix67.com/blog/article.asp?id=251

Matrix67原创
转贴请注明出处