什么时候必须得用反证法?

 

原文作者:高尔斯,剑桥大学数学教授,1998年菲尔兹奖得主。

翻译作者:radium哆嗒数学网翻译组成员,就读于重庆第二师范学院。

 

投稿可发至邮箱1178853280@qq.com

 

微信、手机QQ搜索关注 DuoDaaMath 每获得更多数学趣文

新浪微博:http://weibo.com/duodaa

 

 

已经有一段时间了,自从我在“哲学点滴”条目下写了一个帖子,也是在那儿我提出了像“如何说明一个命题比另一个命题更强,或者两个命题是等价的?”这样的问题。这篇文章就是讨论这个在我脑海里思考了很久的问题,但我发现它比我预想的更难。

 

 

似乎可以将定理分为三种类型:一种是不需要运用反证法来证明的,一种是不管用不用反证法都能证明的,最后一种是似乎只能用反证法。但是如何把一条定理归为这三种类型中的一种呢?

 

这个问题源自于我教给学生们一种前人所想出来的证明方法。比如下面这个“假设数列(An)发散。由此可知...几行计算...这意味着An→A,矛盾”,当你指出这个证明的第一行和最后一行可以被删除时,他们有时会十分惊讶。

 

没那么荒谬的证明更多的是像这样的。“我们知道|y-x|<δ,假设|sin(y)-sin(x)|≥δ,因为sin导数的绝对值最大为1,它推出|y-x|≥δ,这与条件矛盾。所以|sin(y)-sin(x)|<δ”在这个证明中,显然更好的是直接从前提出发,通过引理|f(x)-f(y)|≤sup|f’|·|x-y|推导出|sin(y)-sin(x)|<δ。但是,通常是运用反证法来证明引理:假设这个结论是错误的,然后运用中值定理。

 

所有这一切的结果是,已有的形式无法给我什么提示,“如果你的定理是像这样的,那么尝试着用反证法,不然不要这样做”对于本文的剩余部分,我将讨论另外一组例子,来阐释问题的复杂性。

 

 

例1根号2的无理性

 

这当然是运用反证法的经典证明,我们甚至可以给出一个证明这个命题必须要使用反证法的“准证明”。因为“无理性”意味着“对于任何整数对(p,q),都无法使sqrt(2)(sqrt表示开根号,下同)与p/q相等”。如果这是定义,那么让我们假设证明的最后两行消失了:因此sqrt(2)有性质P,因此sqrt(2)是无理数。

 

于是我们会问“为什么有性质P意味着那个数是无理数?”这可以很明显的看出来性质P意味着无理性,但是为了证明它仍然有必要说“于是,取任意有理数x=p/q...因此x没有性质P”(为什么这个是有必要的呢?正是出于同样的原因!也许这是证明长度或其他类似东西的归纳)

 

带着这些问题,考虑以下论证,我们从计算sqrt(2)的连分数展开开始。于是我们得到sqrt(2) = 1 + ( sqrt(2)-1 ) = 1 + 1/( sqrt(2) + 1)。继续对分数的分母进行展开得到2 + ( sqrt(2)-1 ) = 2 + 1/( sqrt(2)+1 ),于是我们看到连分数展开开始出现循环,标准记法是[1;2,2,2,……]。特别是,它是无穷的,因此sqrt(2) 是无理数。

 

第一眼看这个证明的,这似乎就是直接论证而不是运用反证法证明的:我们运用假设x^2=2演绎出x具有明显的无理数性质。但是,就像我之前笼统的评述一样,一个潜在的问题就是“为什么一个具有无限连分数展开的数是无理数?”

 

答案是什么呢?很明显一个有理数是有限小数,因为当你计算的时候,它的分母不断减少...哎呦,不好意思,这又是一个反证法。

 

所以答案也许应该这么说,如果你正在试图证明一个否定性的命题,那么你就不得不用反证法,但是什么是“否定性命题”呢?以下的定理如何?

 

定理:如果p和q是整数,那么p²≠2q²

 

啊哈!你说,是因为“不等于”形成了否定。但我们可以通过快速的变形成来解决。

 

定理:如果p和q是整数,那么(p²-2q²)²>0。

这个的否定又是怎样的?如果你认为它不管怎么样都受限于“严格大于”的概念,那么下面这个又怎么样?

 

定理:如果p和q是整数,那么存在实数x使(p²-2q²)²x = 1。

 

对我来说,这个命题起来对是相当肯定的,因为它断言某种存在性。

 

 

但如果你思考一下如何证明样的x存在,它将变的没那么肯定了。显而易见的想法是:“唯一可能出错的地方在p²=2q²上面,所以我们只须证明p²≠2q²。”那它又是否定的了。所以这是否意味着,如果对于一个命题,证明它的唯一合理的方式是将它重新归纳为一个包含否定词“非”的命题,那么这个命题就是否定性命题?即使这样看起来是正确的,似乎也很难具体化。

 

这儿还有一个对于最后一个类型的例子。无限是一种无理数性质吗?有人可能说是的,因为它意味着不是有限。但是,当我们讨论到连分数时,我们关心的是序列,我们可以定义一个无穷序列,如果它的项可以和自然数之间建立双射。(我们也可以定义一个无穷集合,如果它和它的某个真子集之间可以建立单射。但是仅仅由于真子集没有包含全部元素,我们就能称真子集是一个否定性的概念吗?)

 

 

例2.有界闭区间上的连续函数

 

直到最近我才“知道”下面是这种实例。如果你想运用[0,1]的紧性证明什么东西时,那么你既可以直接使用海涅-波莱尔定理(Heine-Borel theorem ),也可以通过反证法来处理,具体就是把区间内的数重新排成序列并应用波尔查诺-维尔斯特拉斯定理(Bolzano-Weierstrass theorem.)。

 

例如,证明连续函数f在区间[0,1]是有界的,你既可以通过找函数f在每一点的领域是有界的(由连续性的定义)且将区间[0,1]有限覆盖(运用海涅-波莱尔定理),也可以假设函数f是无界的,构造序列(xn),满足对任意n有f(xn)≥n,应用波尔查诺-维尔斯特拉斯定理通过反证法来证明。

 

我也默认有一种算法能将一种证明转换为另一种证明,虽然我从来没有实际尝试过其中的细节。

 

但是最近,在我和一个同事的谈话的过程中,谈到了下面关于这个定理的证明。在此之前我一直认为于自己对证明怎么运行的理解的很到位,但下面这个证明让我意识到事情远不止那么简单。这个想法是尽量模仿上述反证法的证明,但是最后的结果并没有用到矛盾来证明。具体的讲,构建一个序列是最有可能的引起矛盾的序列,然后证明它不会引起矛盾。下面是论证的具体内容。

 

令S∈R∪{∞}是{f(x) : x∈[0,1]}的上确界。通过上确界的定义,我们可以找到一个序列(xn)使f(xn)→S,通过波尔查诺-维尔斯特拉斯定理选择一个收敛的子序列yn,我们得到(f(yn))是(f(xn))的子序列,所以f(yn)→S。但是如果y是序列(yn)的极限,且f(yn)→f(y),所以S=f(y),即f(y)是函数f的一个上界。(注意这个证明也表明这个上界可以取到。)

 

似乎这个证明没有涉及矛盾。但是如果我们进一步思考,你会发现矛盾隐藏在证明的“明显”步骤中。例如,我们怎么知道我们可以找到一个序列(xn)使f(xn)→S?我们需要将它划分为两个问题(除非我们想要定义隐含在其中的广义实数直线的拓扑)。

 

S∈R不是值得深究的问题,因为它,我们立刻知道函数f是有界的。(尽管这一步是没有必要的,我们也可以获得其他的信息,比如函数f达到了上限)。如果我们将问题转向为S=∞,我们正在做的证明与假设函数f是无界的有什么不同?我自己也很困惑。

 

最后的感想

 

从这些例子中反映出来的一件事是,反证法的概念与你用的定义和你认为理所当然的一些小结论有关。例如,我们定义一个数是无理数,如果它的连分式展开是无限的。事实上我不会主张这样做,但如果有人这样做,那么我给出的根号2的无理性“直接”证明就是直接的。而且如果我们不准使用假设|f(x)-f(y)|≤sup|f’|·|x-y|那么要证明在|x-y|<δ的情况下|sin(y)-sin(x)|<δ就会变得没那么直接,还是需要反证法。

 

在这种情况下,也许我该给这样答复学生,虽然上面的讨论还是不很明确,但已经尽力了。——反证法是一个非常有用的工具,但是尽量不要使用它,除非你不得不用它。

 

 

微信、手机QQ搜索关注 DuoDaaMath 每获得更多数学趣文

新浪微博:http://weibo.com/duodaa

标签: none

仅有一条评论

  1. Buttercat Buttercat

    所以说还是要多留心学过的知识,尝试多角度反复理解。在不知道问题内部逻辑结构的时候,反设一个条件投石问路才是明智之选。

评论已关闭