Math 版 (精华区)

发信人: rainy (段誉), 信区: Math
标  题: 证明的证明
发信站: 哈工大紫丁香 (2002年09月13日15:31:43 星期五), 站内信件


　　先让我们来看看这个颇有名的“任何三角形都是等腰三角形”的“证明”。

　　对任意三角形⊿ABC，我们要证明|AB|=|AC|。作∠BAC的角平分线AO与底BC的
垂直平分线HO，相交于O点；分别作O点到AB和AC的垂线OD和OE。现在由∠OAD=∠
OAE，∠ODA=∠OEA，|AO|=|AO|可知：⊿OAD和⊿OAE全等。于是|AD|=|AE|，
|OD|=|OE|。然后据|OB|=|OC|，|OD|=|OE|，以及∠ODB=∠OEC为直角可知⊿OBD和
⊿OCE全等，于是|DB|=|EC|。于是|AB|=|AD|+|DB|=|AE|+|EC|=|AC|。

　　这个证明当然是荒唐的。事实上，如果我们延长AO使其交BC边于L，那么按照
初等几何的一个简单的定理：|AB|/|BL|=|AC|/|LC|，于是如果事实上AB短于AC的
话，BL就会短于LC，或者说L点就会在H点的左边，BC的垂直平分线绝不会和∠BAC
的角平分线相交于⊿ABC内部！而这点在上面的“证明”中起了关键的作用。所以
这个证明的错误之处在于画了一个误导人的图。有一个类似的“所有钝角都是直角
”的“证明”。

　　看了上面这个“证明”，我们不免会有这样的疑问：如果一个几何题的证明的
正确性取决于画图的准确性，那么我们又如何能保证画图的准确性呢？尤其严重的
是，任何一个图形，即便你把它画得足够“一般”，它事实上都只能代表这个图形
所表示的具体情况。当一个几何证明依赖于这个具体的图形时，如何使人相信这个
证明其实是对所有的情况作出的呢？尤其是当几何图形相当复杂时，这种疑问会变
得很强烈：这个具体图形是否能代表一般的情况？

　　对更一般的数学证明来说，我们也会有这样的担心：我们在证明一个命题的时
候，是否会在证明里运用了太多的直觉，以至于不小心引入了事实上不存在的前提
？上面这个“证明”当然是一个构思巧妙的人工之作，并非某个人无心的错误，但
是历史上数学家不小心犯的这种错误比比皆是。

　　公理化方法的开山祖师欧几里得在他的不朽名作《几何原本》中提出了23个定
义，五条公设和五条公理（欧几里得把公设看作是只在几何中正确的公理，如第一
公设“由任一点至任一点可作一直线”，而公理则放之四海而皆准，如第二公理“
等量加等量，和相等”，现代数学中不作这样的区分，都称为公理），然后试图只
用这些定义、公设和公理来推导出整个几何学的定理。但是后人发现，其中某些定
义对于逻辑推理是不必要的，在证明几何定理的过程中永远也用不着这些定义，比
如定义一所云“点是没有部分的”；而更大的缺陷是，欧几里得在证明推导过程中
使用了隐含的没有事先列举出来的命题，比如他大量地使用“直线上两点之间的某
一点”，“在直线同一侧的点”或者“三角形内某点”诸如此类的话，但是从来没
有想到并无任何公理来保证这样的点存在。当然，这样的点的存在的确很直观，甚
至直观得欧几里得感觉不出他另作了假设，直观得一直要到十九世纪才有数学家帕
西(M. Pasch)等人详细研究这些命题并提出必须将这些点的存在性作为公理。但是
如果我们可以任意使用我们觉得直观的命题，那么为什么要明确提出“由任一点至
任一点可作一直线”这样的公理呢？它也同样很直观啊。所以所有在论证中使用的
公理都应该被明确指出，毫无遗漏。

　　考虑下面这个无穷级数：

　　1-1+1-1+1-1+……

在很长一段时间里数学家们对它迷惑不解。它似乎有两个值：

　　1-1+1-1+1-1+…… = (1-1)+(1-1)+(1-1)+…… = 0+0+0+…… = 0

　　1-1+1-1+1-1+…… = 1-(1-1)-(1-1)-…… = 1-0-0-…… = 1

而伟大的欧拉则更绝，他把等比级数公式1+x+x2+x3+……=1/(1-x)应用到x=-1的情
况下去，得到：

　　1-1+1-1+1-1+…… = 1+(-1)+(-1)2+(-1)3+…… = 1/(1-(-1)) = 1/2

然后他得到1=0=1/2，并由此得出“上帝从虚无中诞生的象征”。现在我们知道，
对于不收敛的级数来说，交换各项相加的次序会得出各种不同的结果，而等比级数
公式也只能应用于收敛级数，当将公式应用于并不满足条件的情形，有可能得出极
其荒谬的结论。

　　除了上面所说的在证明中有意无意地引入额外的假设，在数学证明中还有循环
论证的危险。数学发展到今天，已经不是象两千多年前那样，一个人就可以掌握其
全部分支。数以十万计的数学家同时在不同的地方工作，每个人大多只精通数学的
一个小小的分支，但是却几乎是必不可少地使用到其它分支的成果。这不禁使人担
心，如果自己使用的另一分支的结论，基于其它分支的结论，而其它分支的结论也
基于另一些分支的结论……如果按照这样的线索追踪下去，我们发现最后兜了回来
，前面那一串都要依靠自己正需要证明的结果，那么这整一系列成果就会变成基于
循环论证圈上的空中楼阁。循环论证可以看作是引入额外假设错误的一种变体：当
需要证明命题A时，引入命题B作为已知的结论进行论证，而需要证明命题B时却又
假设命题A是已知结论了。

　　另外，对一些复杂条件的逻辑上的等价变换和理解也是相当令人头痛的。比如
说函数极限的ε-δ语言定义：“对定义在实数域上的实值函数f(x)和实数x0，如
果存在实数f0，对任意δ＞0，都存在ε＞0，使得对任意x满足0＜|x-x0|＜ε，我
们都有|f(x)-f0|＜δ，那么我们说在x趋于x0时，函数f(x)的值趋于f0。”这个定
义已经足以把一般的数学分析初学者搞晕一阵子了，就不用说请他们按照这个定义
把“当x趋于x0时，函数f(x)的值不趋于f0”的定义（也就是上述命题的否命题）
写出来。这种困难也并非只有初学者才会遇到。柯西，这位将数学分析严密化的伟
大数学家，就曾错误地以为“收敛”和“一致收敛”是一回事，搞混了“存在ε，
使得对任意的整数i……”和“对任意的整数i，存在ε，使得……”两种说法。

　　毫无疑问，在数学中我们需要一种方法来排除此类证明错误。这就是形式化方
法。我们先来看看在《几何基础》这部名著中希尔伯特是如何使用形式化方法来解
决本文开始所提出的问题的。首先希尔伯特取消了欧几里得关于“点”、“直线”
、“平面”之类几何基本对象的定义。既然那些定义和证明无关，那么它们就是多
余的，所有这些基本对象的性质和它们之间的关系完全是用公理的形式来确定的。
这些基本对象的名字是什么，却是无关紧要的（当然，不同的对象应该有不同的名
字，否则我们就没法分辨它们了，而名字也仅起着用来分辨不同对象的作用）。希
尔伯特为此在书中说：“我们必须能够不用‘点、线、面’，而说‘桌子、椅子和
啤酒杯’。”书中引入了五组共二十条公理。比如第二组顺序公理的第二条是：“
对于点A和点C，直线AC上总有一点B，使得C在A和B之间。”粗看起来，这简直是大
废话，但是在形式化几何下，这是必不可少的。因为在形式化的证明中，我们并不
能使用“点”、“直线”、“在……之间”的平常意义，所能使用的只有这些公理
。事实上，上面这个公理虽然告诉你点C在点A和点B之间，你还是不能立刻说点C在
点B和点A之间！你必须引用顺序公理组中的第一条公理来证明这一点。有了这些公
理后，希尔伯特就可以只用逻辑推理，而不用借助画图，推出整个初等几何（虽然
《几何基础》一书中还是有几何图形，但是那只是用来说明问题，帮助读者理解，
真正的证明完全不依赖于这些图形。）

　　形式化方法并不是“从公理通过逻辑方法来导出整个理论”这么简单，因为逻
辑方法本身也是有争议的。比如说直觉主义的逻辑不允许使用排中律（也就是说即
使你能证明一个命题的否命题不正确，你还是不能得出这个命题是正确的。这种逻
辑有些怪诞，但是直觉主义的数理逻辑哲学无论在历史上还是在现实中，尤其是在
信息科学被发展和应用的今天，都有极其重要的意义。对于直觉主义数理逻辑的评
价并不是本文的主题，所以在此我们不加讨论）。所以我们还得防止“一不小心”
用了一种不被允许的推理方式，被允许使用的推理方式也必须显明地写出来，也必
须有明确的机制来验证在证明中只有“合法”的公理和逻辑推理方法被使用。

　　在数理逻辑中有个分支叫“证明论”，专门以形式化的数学证明为研究对象，
来解决上面所说的问题。因为证明是数学研究的主要方式，所以证明论可以看做是
对数学研究的研究，所以它又被称做“元数学”(Metamathematics)，字面上可以
理解为“审视数学的学问”。所以在下面的讨论中，我们一定要区别两种“理论”
，一种是证明论本身这个数理逻辑的分支理论，另一种是被证明论研究的数学理论
。这就好像一本用中文写成的英语语法书一样，写这本书本身必须使用一种语言，
在这里我们用的是中文，而这书本身研究的却是另一种语言，在这里我们研究的是
英语，它们是两种不同的语言。

　　从证明论的角度看来，象初等几何，或者自然数算术这样的数学理论是什么？


　　首先，里面有一些符号。这些符号可以表示数学理论中的对象，比如代表点的
A，B，C，代表自然数的m、n或者x、y，或者是表示常量的符号1、2、3等；它们也
可以表示数学对象间的关系，比如“＞”；也可以用来表示某些逻辑关系，比如大
家熟悉的“”（对于任意）、“”（存在）或“→”（蕴涵），还可以是纯粹的辅
助符号，比如括号。不过要注意的是这些符号具体代表的是什么意思，证明论并不
关心，就象上面所说的“点”和“桌子”。如果你愿意，你完全可以用“＞”来表
示“小于”关系，或者用A来表示左括号，用α来表示右括号。只是因为出于方便
的缘故，在研究一个数学理论时，我们仍旧使用那个理论平时使用的那些符号。

　　其次，我们可以用这些符号来组成表达式，也就是一串有限长度的符号。可是
并不是无论什么表达式在这个数学理论里都有意义。比方说自然数的算术理论中“
1+1=2”或者“2+2=22”或者“(a+b)*c-d=0”都是有意义的表达式（尽管有可能是
错的或者意义并没有完全被确定），但是象“((0++a”这类字符串却毫无意义。所
以我们必须知道由什么样的方式组成的表达式是有意义的，也就是说，理论必须提
供这些有意义的表达式（我们把它们称为公式）的形成规则。

　　最后，也是最关键的，我们必须知道在这个数学理论里公式的变形规则。在这
里我们先要看看在证明论中如何定义“证明”这个概念，怎么样的一段文字才配得
上被称作是一个“证明”？一个数学证明看起来象是什么？就是一串有限个公式组
成的公式串，我们先写下第一个公式，再写下第二个，……。当然不是无论什么样
的一堆公式堆在那里就算是一个证明了。假设这个公式串看起来是这个模样：F1,
 F2, F3,……,Fn，其中每一个Fi都是一个公式，那么这里每个公式都必须满足：


1)或者它是公理（也就是一开始就规定的不需要证明就可以使用的公式）；

2)或者它可以从在它前面的那些公式推出，不过这里的“推出”不是我们平时所说
的运用逻辑来得到，因为逻辑规则本身也必须由变形规则来刻划。所以我们宁可说
，“它可以通过从在它前面的那些公式，使用允许的变形规则得来的”；

比方说，在命题逻辑中，如果我们已经证明了命题A蕴涵命题B（“如果A，则B”，
用形式的记号写作A→B），我们也知道命题A是成立的，那么我们可以得出命题B是
成立的。这里的变形规则就是：如果在前面的公式串里我们可以找到两个公式“A
→B”和“A”，那么我们就可以在这个公式串中接下去写上“B”。这里我们清楚
地看见我们如何用变形规则来刻划逻辑规则。另外，事实上公理可以看做是特别的
变形规则，就是在任何时候都可以写下的公式，而不需要考虑它的前面有没有某些
特定的公式。在这个时候，我们就称上面这个公式串是最后那个公式Fn在这个数学
理论中的一个证明，Fn就成了这个数学理论中的一个“定理”。很明显，任何一个
公理都是一个定理，只由它本身组成的公式串就是它的（显而易见的）证明；任何
一个证明中的任何一个公式也一定是定理，因为只要把这个证明截断在这个公式出
现的那个位置，就得到了它的证明。

　　如果一个数学理论被这样规定了符号，公式的形成规则，和公式的变形规则（
以及公理）后，我们就说它被形式化了，成为一个形式系统。比如说原先朴素的欧
几里得几何就被希尔伯特形式化了，而朴素的自然数算术理论则被皮亚诺公理体系
形式化了。

　　反过来说，如果我们有了一套符号和一组公式的形成规则和公式的变形规则（
以及公理），我们也就有了一个形式系统，可以在里面进行“证明”的活动了。最
好让我们来看一个例子，我举一个迷你型的形式系统。

1)这个形式系统中的符号就三个：a、b、★，前面两个我把它叫作“字母”，后面
这个叫“关联”（我随便取的名字）。

2)引入一个中间的概念“词”，一个词就是一个长度大于等于1但是有限的字母串
，比如abbabaa。

3)这个形式系统里的公式是这样的符号串：I★J，其中I和J都是词，比如aaab★
ababa就是一个公式，而aaabba★★a却不是。

4)公理就一条：a★b

5)变形规则：

　5-1)如果I★J是一个公式，那么可以同时在两个词后面加上一个字母，比如Ia★
Ja，或Ib★Jb。

　5-2)如果I★J是一个公式，那么可以在第一个词的前面或后面加上一个字母比如
aI★J，Ib★J等。

　　这里要反复提醒注意的一点是，我们这里有两个理论，一个是正在被研究的形
式系统，就是里面只有“ab★”符号的理论，另一个是研究这个理论的证明论，也
称前面这个理论的“元理论”。上面的I，J就是元理论里的符号，而不是被研究的
形式系统里的符号。这两个理论的区别一定要时刻记在心里。

　　现在我们可以试着用这个系统证明点定理。首先是公理a★b，通过变形规则
5-1)，得到aa★ba，这是我们得到的第一条不是公理的定理，再用5-2)，得aab★
ba，用两次5-1)得到aabab★baab。用公式串的形式写下这个对定理aabab★baab的
证明就是：a★b，aa★ba，aab★ba，aabab★baab。

　　再让我们看看bbab★aab不可能是系统中的定理，也就是说这个命题是在上面
那个形式系统中证明不出来的。

　　我们先来证明bba★aab是证明不出来的（注意这句话中有两个“证明”一词，
但是它们的意义是很不相同的：第一个“证明”是在元理论中的证明，是我们平时
所说的那种证明，而后一个“证明”是形式系统中的证明，就是我们上面用公式串
来定义的证明）。观察两条变形规则和唯一的公理，我们知道一个定理左边的词一
定至少和右边的一样长，或者更长，而且5-2)会使左边的词加长，所以如果bba★
aab被证出来了，那么这个证明的最后一步（就是最后一次变形）一定是用了5-1)
，但这不可能，因为通过5-1)变形出来的命题两词一定有相同的结尾，而bba和
aab却不是这样，所以bba★aab不可能是定理。

　　我们还可以发现bab★aab也不可能是定理。如果它是定理，那么证明它的最后
一步一定是用了5-1)，也就是说它必须由ba★aa推出，同样，ba★aa必须由b★a推
出。但是很明显b★a不是定理，因为很容易看出左边词长度为1的定理只有a★b这
一条。

　　于是通过上面两条，bbab★aab不可能是由5-2)证出来的，所以只能是由5-1)
证出来。于是如果bbab★aab是定理的话，bba★aa必须是定理。但是这是不可能的
，为什么？就留给大家思考了，推理完全和上面一样。

　　再强调一遍，“aabab★baab”是形式系统中的定理，而“aabab★baab是形式
系统中的定理”以及“bbab★aab不可能是系统中的定理”是元理论中的结论。  


--
想念你的笑,想念你的外套,               .oooO  Oooo.
想念你白色袜子和你身上的味道,          (   )  (   )
想念你的吻和手指淡淡芦荟味道,           \ (    ) /
静静中体味被爱的味道.                    \_)  (_/

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: sunny.hit.edu.cn]