反证法的妙用

中国成语中有一个“矛盾”的故事,有一个人同时贩卖矛与盾,他向买家吹嘘他的矛是“无坚不摧”的,盾呢,是刀枪不入的。于是,有人马上提议他“以子之矛,攻子之盾”来验证一下他的宣传是否可靠,于是这人当场弄得哑口无言。

数学上的反证法

在数学上人们也常用这种“以子之矛,攻子之盾”的方法来证明一些问题,这种证法不是直接证法,而是反证法,许多问题用反证法证明是比直接证法还容易些。

现在让我们看看一个例子:

那一天,牛头马面把一个高头大马的鬼带进阎王宝殿。

阎罗王把惊堂木一拍:“这厮好无礼,见到本王也不会下跪叩头。拉下,打一百棒。”

“大王,请原谅。我是洋鬼子,不知你们东方地狱的礼节请原谅。”

“好!就原谅你一次,你是谁?”

“我是Superman。”站在阎罗王旁边的师爷马上俯身对阎王解释:“Superman是超人。”

“好大的口气,苏本梅先生你怎么会是超人?”

Superman以傲慢的口气说:“当然是超人,我能做人类所不能做的事,我是万能,世上没有一件事我是不能做的。”

“好!那么你举一件事是你做不出的。”

Superman当场呆在那里。如果他能举出一件事,这就证明他不是万能。如果他不能举出这样的事,就证明在世上他不能做这件事——“举出他不能做的事”,因此也证明他不是万能。

“是嘛!你根本就不是超人,我就不相信存在超人的东西。你呀在人间以前还做些好事,可是现在西方的连环图把你弄成巧言令色,专门吊女人膀子的家伙,你这种行径败坏许多青年,我看不出你有什么英雄气色。好!判你进入第十八层地狱,等到你认清你的错误,再让你转世。”

这里阎王就是“以Superman之予,攻Superman之盾”了。

在数学上如果我们要证明一个命题p,可以推证到一个结论q,用反证法就是假定“非q”,然后由此得到和最初命题p矛盾的地方,于是得结论:由p的正确性,应该有q的结论。

读者可以再回过头去看看前面的《鸽笼原理》一文。鸽笼原理是很简单,但用途很大。这原理是这样说的:“我们有n个盒子,放进n+1个东西。一定最少有2个东西是在同一盒子里面。”我在该文里提了一些问题,有读者来信说这些问题他可以用反证法来解决。这是不奇怪的事。

首先让我们用反证法来证明“鸽笼原理”是对的。现在请看:

p=n1个东西进n个盒子

q=最少有2个东西是在同样盒子。

“鸽笼原理”就是说由p可以得q。我们现在反其道而行,证明如果不是q的话,一定不会有p的情形出现。现在我们看“非q”是什么?这时

q=每个盒子都不会多过2个东西。

现在既然每个盒子都不会多过两个东西,那么最多只有一个,而我们有n个盒子,于是所有的盒子装的东西最多就不会超过n个了,这和我们最初假设有n1个东西发生矛盾。

因此如果一个问题能用“鸽笼原理”来解决,肯定是可以用反证法来处理。在数学上利用反证法可以得到许多巧妙的证明,例如在2000多年前希腊数学家欧几里得在《几何原本》一书中就用反证法证明:“素数的个数有无穷多个”。而我们在《复数的产生》一文里证明在复数域的世界里,生物没有“大小”的概念也是用反证法证明。

 

传说毕达哥拉斯太珍惜这个发现,不打算公开这个结果。他的学生之一为了好奇,悄悄走进老师的家里偷文件,这方法才算公开出来。

我们这里介绍六个用反证法证明这结果,大家可以学习这种证明。

因此p也须是偶数(因为奇数2k1的平方后是4k24k122k22k)+1仍旧是奇数)。所以我们可以设p2a的样子,代入上式得(2a22q2,即4a2=2q2两边同时消掉2可得2a2q2,即q也是偶数。

由于pq都是偶数,它们有一个公约数2,这和我们最初假设p

对的。

2)利用整数的个位数性质:我们知道任何整数平方其最后一位数是等于原数最后一位数的平方后的最后一位数。例如(122144,最后一位数4=22。而(172=289,(72=49,最后一位数是一样。

最后一位数可能出现0123456789

因此任何数的平方最后一位数只可能是014569

因此2q2的最后一位数只可能是028

由于p2的最后一位数可能是014569。而且由P2=2q2,故必须有2q2最后一位数是0,因此推到q2的最后一位数是05

可是如果P2的最后一位数是0,而q2的最后一位数是05的话,则P的最后一位数是0q的最后一位数是05,这样5就能整除pq,这和pq无公约数的假定矛盾。

(一)任何整数不是素数就是合数。

(二)如果一个素数s能整除U×V,则必须是s能整除us能整除v

由整数的性质,我们知道由q1,存在一个素数sq的约数。

能整除P,因此我们得到s能同时整除Pq

这是不合理的。

4)用素因子的性质:由p2=2q2我们得q2=p2-q2=(p+q)(p-q

由于 q1,存在一个素数s能整除q,由此可知s能整除p+qp-q

因此p+q=supq=sv

qStt是某一个整数),因此由p+q=su,得p=sut),所以pq有公共素因子s,这产生矛盾。

a0xn+a1xn-1…+an0

的事。

6)费马的无穷下降法:(Infinite Descent)在前面我曾介绍过费马这位法国数学家创立的无穷下降法,这方法基本上是用到反证法。

费马在16世纪时用这方法在数学上作了一些证明,当时许多人都不知道这方法。费马生前和一位著名的荷兰科学家克里斯汀·惠更斯(Christaian Huygens 1629-1695)时常通讯讨论各种各样的问题,惠更斯和牛顿同时代人,他提出光是波动的学说与牛顿的光“粒子说”迥然不同。

1879年人们为了研究惠更斯的工作,在荷兰的莱登市(Leiden)的图书馆发现费马给惠更斯的信谈“无穷下降法”解决一些数学问题,这方法才重见天日。

如此类推,我们可以得到无穷的正整数对(p3q3),(p4q4),

可是p是一个正整数,而对一个有限大的正整数,小於它的正整数肯定

一些无理数的证明

我们知道实数集可以分成有理数和无理数两部分。从集合论的理论中可以证明无理数的“数目”是比有理数还多。

给出一个数,比方说圆周率π,要证明它是无理数通常是非常困难,要用到超过中学数学的知识。

这问题是很有趣,你可以试试证明,如果你有不同我的下面证法可以来信告知。

我们用反证法证明这样的一个:

如果c是大过1,则由于c是正整数,存在一个素数p,使是p能整除c,则p能整除cn,由于bn=acn,因此p也能整除bn,由此p能整除b,这和假设bc无公约数发生矛盾。所以c是要等于1

由这个结果我们得到下面的:

现设n2,由于2nn1

 

反证法在数学界上的风波

荷兰在欧洲是一个小国家,但是在本世纪那里出了一个很优秀的数学家布劳威尔(LEJBrouwer 18821966)他在喝咖啡时搅咖啡给糖溶解,发现咖啡液面有一点不会动。他看小学生的地球仪转动时,南北极两点是不动。因此他研究一种抽象的空间(实际的就如液面和地球仪的表面),这空间上的连续映射(如液面和地球仪面的转动),以及什么点在映射上是不动的。他在1910年发现了在代数拓扑学上重要的“布劳威尔不动点原理”,这东西在数学上是很重要的发现,实际上也有应用的地方。

他年青时把这重要发现登在德国杂志《数学年鉴》(Mathematische Annalen)。后来这杂志请他在1913年当编辑之一,可是布劳威尔先生却很怪,他不喜欢反证法,他把那些寄给他审查的稿件,凡是不用直接证法而用反证法(reductio ad absurdum反证法的拉丁文)都一概不采纳发表。

这作风是有点霸道,许多好文章就不能见世了。于是《数学年鉴》的编辑部召开一紧急会议,然后重新选出编辑成员,选举结果是布劳威尔是唯一的落选者,这就是等于请他滚出编辑部了。

荷兰政府感到奇耻大辱,德国人把它最优秀的数学家从《数学年鉴》赶跑。为了安慰布劳威尔,荷兰政府拨出公款创办了一种新的数学杂志,并请这位怒发冲冠的布劳威尔当总编辑了。

以后数学界还为这个“反证法”的问题展开论战,这牵涉到数学基础和逻辑的问题,对一般人来说是艰深枯燥的事,我们就不谈了。

动脑筋 想想看

1)在平面上打一个垂直座标,然后取1单位。平面上一点叫格点,如果其座标(xy)中xy都是整数。

你在平面上任意选五个格点,证明最少有一对格点联线一定会经过一个格点。用“鸽笼原理”帮忙解决。

2)在3维空间任何取9个格点,证明最少有一对格点在其联线上是经过一个格点。

以上的(1)是美国中学数学比赛出过的问题。如果你能解决(1)和(2)试试考虑更一般的情形。

3)在n维空间上,任取2n1个格点,证明最少有一对格点其联线是经过一个格点。

4)证明log102是无理数。

5)解决(4)后试证明下面更一般的结果,如果ab是两个正整数,其中有一个包含其他另一个所没有的素因子,那么logab一定是无理数。

6)欧几里得的几何第一公式说:“过两点只能作唯一一条直线经过它们。”

现在利用反证法证明:如果LM是两条不同的直线而且不平行,那么它们相交于唯一的点。