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

 

原文作者：高尔斯，剑桥大学数学教授，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) 是无理数。

 

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

 

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

 

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

 

定理：如果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